2 ms·
Your "Power of Prolog" book/site has been a great help to me just this last week or so. I had developed a simple type inference algorithm for a stack-based lan
by carapace 8y ago
Your "Power of Prolog" book/site has been a great help to me just this last week or so. I had developed a simple type inference algorithm for a stack-based language called Joy, using knowledge of unification gained from studying a Python implementation of miniKanren. At some point I realized that, if I wanted to do anything "fancy" with my types like propagating constraints or something, I should switch to Prolog (or Kanren.)
> Prolog has powerful built-in mechanisms that can be used in interpreters, and in addition to that, Prolog variables on the object-level (the program to be interpreted) are also variables on the meta-level (the interpreter). As a consequence, Prolog's implicit mechanisms can be absorbed in interpreters: They need not be encoded explicitly.
Brother, you're not kidding! I reimplemented the semantics of Joy in Prolog and when I had boiled off the cruft included due to my ignorance an inexperience with the language the resulting interpreter was very elegant. Several pages of Python became about a half-page of Prolog.
Not only that, but when I went to implement the type inferencer I realized I had just reimplemented the interpreter, only it was more elegant. In Prolog, the interpreter and the type inferencer are the same thing. (I feel foolish for not catching on and using Prolog, et. al. sooner.)
For what it's worth, here's the Joy-in-Prolog code (the library of functions is incomplete but the thun() relation works.):
/*
Interpreter
thun(Expression, InputStack, OutputStack)
Copyright © 2018 Simon Forman
This file is part of Thun.
Thun is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Thun is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Thun. If not see <http://www.gnu.org/licenses/>.
*/
:- use_module(library(clpfd)).
thun([], S, S).
thun( [Func|E], Si, So) :- func(Func, Si, S), thun(E, S, So).
thun([Combo|E], Si, So) :- combo(Combo, Si, S, E, Eo), thun(Eo, S, So).
thun( [Lit|E], Si, So) :- thun(E, [Lit|Si], So).
combo(i, [P|S], S, Ei, Eo) :- append(P, Ei, Eo).
combo(dip, [P, X|S], S, Ei, Eo) :- append(P, [X|Ei], Eo).
combo(dipd, [P, X, Y|S], S, Ei, Eo) :- append(P, [Y, X|Ei], Eo).
combo(branch, [T, _, true|S], S, Ei, Eo) :- append(T, Ei, Eo).
combo(branch, [_, F, false|S], S, Ei, Eo) :- append(F, Ei, Eo).
combo(loop, [B, true|S], S, Ei, Eo) :- append(B, [B, loop|Ei], Eo).
combo(loop, [_, false|S], S, E, E ).
func(cons, [A, B|S], [[B|A]|S]).
func(swap, [A, B|S], [B, A|S]).
func(dup, [A|S], [A, A|S]).
func(pop, [_|S], S ).
func(+, [A, B|S], [C|S]) :- C #= A + B.
func(-, [A, B|S], [C|S]) :- C #= B - A.
func(*, [A, B|S], [C|S]) :- C #= A * B.
func(nullary, [P|S], [X|S]) :- thun(P, S, [X|_]).
func(concat, [A, B|S], [C|S]) :- append(B, A, C).
func(>, [A, B|S], [true|S]) :- B #> A. /* Is this really necessary? */
func(>, [A, B|S], [false|S]) :- A #>= B.
func(<, [A, B|S], [true|S]) :- B #< A.
func(<, [A, B|S], [false|S]) :- B #>= A.
func(Name, Si, So) :- define(Name, Body), thun(Body, Si, So).
define(swons, [swap, cons]).
define(x, [dup, i]).
define(sqr, [dup, *]).
define(ifte, [[nullary], dipd, swap, branch]).
define(while, [swap, [nullary], cons, dup, dipd, concat, loop]).
And an example run:
?- thun([[], 3, sqr, swons], [], So).
So = [[9]] .
And, showing the ridiculous power of Prolog:
?- thun([sqr, swons], Si, So).
Si = [_8302, _8308|_8310],
So = [[_8332|_8308]|_8310],
_8302^2#=_8332,
_8332 in 0..sup .
That is:
?- thun([sqr, swons], Si, So).
Si = [A, X|...],
So = [[B|X]|...],
A^2 #= B,
B in 0..sup .
Which says, correctly, that "sqr swons" expects a number A and a list X on the stack, and returns just the list X with the square of A cons'd onto it.
Now, as if that weren't messed up enough:
?- thun([sqr, swons], Si, [[9]]).
Si = [_10164, []],
_10164 in -3\/3 .
Like I said, I feel kinda stupid for not using Prolog sooner.
- triska 8y agoWow! This is very elegant and general Prolog code, thank you for sharing it, and for your kind words! Regarding the handling of ">" and "<", one possible alternative is to use constraint reification to reason about the truth values of arithmetic relations. For instance, we can equivalently describe the semantics of ">" as: func(>, [A,B|S], [T|S]) :- B #> A #<==> R, r_truth(R, T). r_truth(0, false). r_truth(1, true). As in the context of meta-interpreters, reification also here means to "make it a thing" (from Latin res, rei f.: "thing", "matter") - in this case, to reflect the constraint's meta-level truth in a Boolean value on the object-level.
- carapace 8y ago> Wow! This is very elegant and general Prolog code, thank you for sharing it, and for your kind words! Thank you! You're very kind but the credit goes to Manfred von Thun, he came up with Joy. And your book has helped a lot. > Regarding the handling of ">" and "<", one possible alternative is to use constraint reification to reason about the truth values of arithmetic relations. This is exactly what I wanted! Thank you. I'm just starting out with Prolog so it's difficult to know what to reach for, I spent twenty minutes looking for docs on "true" and "false" before realizing they weren't built in! Heh. ?- thun([dup, 0, >, [+], [-], branch], Si, So). Si = [_9700, _9706|_9708], So = [_9724|_9708], _9700 in 1..sup, _9724+_9700#=_9706 ; Si = [_9800, _9806|_9808], So = [_9824|_9808], _9800 in inf..0, _9800+_9806#=_9824 ; false. Awesome. (Both solutions, ta-daaa!) Based on what you recommend about avoiding "defaulty" representations I've added a literal predicate: thun( [Lit|E], Si, So) :- literal(Lit), thun(E, [Lit|Si], So). literal([]). literal([_|_]). literal(I) :- number(I). literal(true). literal(false). Right now I'm reading up on compiling and code generation, and your "Thinking in States" chapter is a big help.