6 ms·

Thank you very much for the publicity, I greatly appreciate it! Prolog is rather unique in that it admits a meta-interpreter in roughly 3 lines of code. Contra

by triska 8y ago

Thank you very much for the publicity, I greatly appreciate it! Prolog is rather unique in that it admits a meta-interpreter in roughly 3 lines of code. Contrast this with other languages, where writing an evaluator typically takes much more code, even for quite high-level languages. This brevity is possible mainly because Prolog - like Lisp and assembly language - is a homoiconic language, and in addition to that, 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. Enjoy!

fusiongyro 8y ago
The three or so times I've needed to build a metainterpreter, I have always referred back to your page for help, so thanks for taking the time to make it! It's greatly appreciated!
- YeGoblynQueenne 8y ago
  Too true, I've had to write a good few meta-interpreters in the last nine months or so and Markus' page is permanently open in a tab in my browser :)
agumonkey 8y ago
any favorite websites / book about this topic ? thanks for writing this
- pjmlp 8y ago
  A bit outdated by now, but a favourite book of mine was " The Art of Prolog, Advanced Programming Techniques". https://mitpress.mit.edu/books/art-prolog-second-edition https://mitpress.mit.edu/books/art-prolog-second-edition
  - agumonkey 8y ago
    Ha I didn't know it talked about meta-interpretations.. I've read the name many times but never the TOC D:
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.
3rdAccount 8y ago
Can you explain to me what you use Prolog for and why you chose it over something more popular? What are the pros/cons in your mind? Everytime I get started, I eventually stop when I realize I'm not an alien named Spock :). In all seriousness, it is very challenging to me, so kudos to you. My bucket list has Forth, APL, Lisp, Smalltalk, and Prolog on it.
- triska 8y ago
  Learning Prolog was very challenging for me too! I was extremely lucky though in that I had one of the world's greatest Prolog experts as instructor, using the world's most sophisticated Prolog teaching environment: https://www.complang.tuwien.ac.at/ulrich/gupu/ https://www.complang.tuwien.ac.at/ulrich/gupu/ You can take a short pictorial tour of GUPU: https://www.complang.tuwien.ac.at/ulrich/gupu/d-2-europastadt-dax https://www.complang.tuwien.ac.at/ulrich/gupu/d-2-europastad... However, these pictures can at best give a small glimpse of what GUPU actually is, so I also recommend a longer paper: https://www.complang.tuwien.ac.at/ulrich/papers/PDF/gupu-wlpe2002.pdf https://www.complang.tuwien.ac.at/ulrich/papers/PDF/gupu-wlp... For me, a major attraction of Prolog is the balance it strikes between readability, versatility and convenience. I know languages that sometimes admit shorter programs, but they then are - at least in my experience - not as readable as a Prolog version, or not as versatile. I am using Prolog for many different tasks, such as hosting web pages, prototyping showcases, and solving combinatorial optimization problems.
  - 3rdAccount 8y ago
    I have to make extensive use of Linear Programming & Mixed-Integer Linear Programming in my day job. This all runs on CPLEX. It would be really cool to do that sort of thing in Prolog, but I doubt it could handle massive models. Anyway you could explain what combinatorial optimization is for and how it differs from the things commonly seen in operations research?
    - triska 8y ago
      For solving linear programs and mixed-integer linear programs with Prolog, I recommend the CLP(Q) and CLP(R) libraries of SICStus Prolog. See for example: https://sicstus.sics.se/sicstus/docs/3.7.1/html/sicstus_32.html https://sicstus.sics.se/sicstus/docs/3.7.1/html/sicstus_32.h... For discrete optimization tasks, also check out the integer constraint solver that ships with SICStus Prolog. See especially the combinatorial constraints: https://sicstus.sics.se/sicstus/docs/4.1.0/html/sicstus/Combinatorial-Constraints.html#Combinatorial-Constraints https://sicstus.sics.se/sicstus/docs/4.1.0/html/sicstus/Comb... As to the relation between Prolog and operations research: Prolog systems internally use methods from operations research to efficiently solve optimization tasks; in addition to that, you can of course also implement every OR algorithm in Prolog. For many commercial users of SICStus Prolog, the efficiency of its constraint solvers are an important reason for buying a licence.

by triska 8y ago

fusiongyro 8y ago

The three or so times I've needed to build a metainterpreter, I have always referred back to your page for help, so thanks for taking the time to make it! It's greatly appreciated!

YeGoblynQueenne 8y ago
Too true, I've had to write a good few meta-interpreters in the last nine months or so and Markus' page is permanently open in a tab in my browser :)

agumonkey 8y ago

any favorite websites / book about this topic ? thanks for writing this

pjmlp 8y ago
A bit outdated by now, but a favourite book of mine was " The Art of Prolog, Advanced Programming Techniques". https://mitpress.mit.edu/books/art-prolog-second-edition https://mitpress.mit.edu/books/art-prolog-second-edition
- agumonkey 8y ago
  Ha I didn't know it talked about meta-interpretations.. I've read the name many times but never the TOC D:

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.

3rdAccount 8y ago

Can you explain to me what you use Prolog for and why you chose it over something more popular? What are the pros/cons in your mind? Everytime I get started, I eventually stop when I realize I'm not an alien named Spock :). In all seriousness, it is very challenging to me, so kudos to you. My bucket list has Forth, APL, Lisp, Smalltalk, and Prolog on it.

triska 8y ago
Learning Prolog was very challenging for me too! I was extremely lucky though in that I had one of the world's greatest Prolog experts as instructor, using the world's most sophisticated Prolog teaching environment: https://www.complang.tuwien.ac.at/ulrich/gupu/ https://www.complang.tuwien.ac.at/ulrich/gupu/ You can take a short pictorial tour of GUPU: https://www.complang.tuwien.ac.at/ulrich/gupu/d-2-europastadt-dax https://www.complang.tuwien.ac.at/ulrich/gupu/d-2-europastad... However, these pictures can at best give a small glimpse of what GUPU actually is, so I also recommend a longer paper: https://www.complang.tuwien.ac.at/ulrich/papers/PDF/gupu-wlpe2002.pdf https://www.complang.tuwien.ac.at/ulrich/papers/PDF/gupu-wlp... For me, a major attraction of Prolog is the balance it strikes between readability, versatility and convenience. I know languages that sometimes admit shorter programs, but they then are - at least in my experience - not as readable as a Prolog version, or not as versatile. I am using Prolog for many different tasks, such as hosting web pages, prototyping showcases, and solving combinatorial optimization problems.
- 3rdAccount 8y ago
  I have to make extensive use of Linear Programming & Mixed-Integer Linear Programming in my day job. This all runs on CPLEX. It would be really cool to do that sort of thing in Prolog, but I doubt it could handle massive models. Anyway you could explain what combinatorial optimization is for and how it differs from the things commonly seen in operations research?
  - triska 8y ago
    For solving linear programs and mixed-integer linear programs with Prolog, I recommend the CLP(Q) and CLP(R) libraries of SICStus Prolog. See for example: https://sicstus.sics.se/sicstus/docs/3.7.1/html/sicstus_32.html https://sicstus.sics.se/sicstus/docs/3.7.1/html/sicstus_32.h... For discrete optimization tasks, also check out the integer constraint solver that ships with SICStus Prolog. See especially the combinatorial constraints: https://sicstus.sics.se/sicstus/docs/4.1.0/html/sicstus/Combinatorial-Constraints.html#Combinatorial-Constraints https://sicstus.sics.se/sicstus/docs/4.1.0/html/sicstus/Comb... As to the relation between Prolog and operations research: Prolog systems internally use methods from operations research to efficiently solve optimization tasks; in addition to that, you can of course also implement every OR algorithm in Prolog. For many commercial users of SICStus Prolog, the efficiency of its constraint solvers are an important reason for buying a licence.