7 ms·

An embeddable Prolog scripting language for Go

131 points by triska 5y ago

RcouF1uZ4gsC 5y ago
What are the trade offs of embedding a Prolog interpreter versus having a library that implements prolog logic without having to have another language. Are there any high quality prolog as a library implementations in languages such as Rust, C++, Java, Go?
- exDM69 5y ago
  > What are the trade offs of embedding a Prolog interpreter versus having a library that implements prolog logic without having to have another language. A library that implements Prolog logic is an interpreter. The difference here is that Prolog source code is passed in as a string as opposed to having an embedded domain specific language where you construct the abstract syntax tree. Go is a very simple language and it doesn't have the kind of metaprogramming facilities that are typically used for creating embedded DSLs. Hence it's a reasonable choice to just have a parser and pass in the logic code as a string. There's probably a way to pass in the AST as well but it may not be very ergonomic. Parsing the source and constructing the AST isn't very expensive and it's only done once per program, so the runtime cost isn't huge. There are Prolog and Prolog-like embeddable interpreters and logic programming systems for many other prorgamming languages, including Rust, C++ and Java. The best known ones are Clojure's core.logic (based on the logic interpreter in the SICP book) and Minikanren.
  - tgv 5y ago
    Indeed. Text is "unreasonably efficient" in this case. Passing a struct is easy enough in go, but that's all it can do for you. So you'd have to pass arguments like PLClauseList{PLLoadClause{...}, ..., PLFact{Head: PLAtom{"human"}, Arguments: PLArgList{PLAtom{"socrates"}}}, ...}. Unwieldy, unreadable, and hard to edit.
  - vvern 5y ago
    There are advantages to embedding. You can retain the host language type system and and object model. If you have a great query language and model but have to write a ton of code to marshal back and forth, it might not be adding that much value (classic impedance mismatch). While go’s compile time metaprogamming is virtually non-existent, it’s runtime metaprogramming with reflection is more or less complete. There’s a runtime cost to using it, but that can be mitigated. See https://github.com/cockroachdb/cockroach/tree/master/pkg/sql/schemachanger/rel https://github.com/cockroachdb/cockroach/tree/master/pkg/sql... for a reflection-driven, embedded logic query language in go that achieves pragmatic goals of writing logic queries over data structure graphs at reasonable performance and pretty good expressibility.
- aarroyoc 5y ago
  IMHO you loose a lot of expresiveness. Real Prolog code is not just simple rules and facts. They can be more complex than that. For example, in my case, I'd like to use DCGs a lot, which are a bit difficult to translate using "normal languages" constructs. Many Prolog systems implement DCGs with Prolog macros because Prolog is homoiconic, which most normal languages aren't (Lisp is homoiconic too). Also "logic" arithmetic (clpz, clpfd,...) is not the one that comes with normal languages and that breaks a lot of logical properties. Doing the sum of two variables in Java side will not respect logical properties. Standard is/2 in Prolog is also bad, but at least you can replace it with #= and that's it.
- Avshalom 5y ago
  I've never used it but for Java there's https://gitlab.com/pika-lab/tuprolog/2p-in-kotlin https://gitlab.com/pika-lab/tuprolog/2p-in-kotlin ( documentation seems to be lagging but here's the 3.3 manual https://gitlab.com/pika-lab/tuprolog/2p/-/wikis/uploads/d67e89c81da28d33cf7c8241cc35cab2/tuprolog-guide-3.3.0.pdf https://gitlab.com/pika-lab/tuprolog/2p/-/wikis/uploads/d67e... ) And specifically for Javascript there's http://tau-prolog.org/ http://tau-prolog.org/ Also pretty much every lisp that's gotten past toy stage has a Prolog implementation Although both Sicstus and SWI have strong Java and C(++) interop https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/Mixing-C-and-Prolog.html#Mixing-C-and-Prolog https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.ht... https://www.swi-prolog.org/pldoc/doc_for?object=packages https://www.swi-prolog.org/pldoc/doc_for?object=packages
- jfmc 5y ago
  Some Prolog systems (like Ciao Prolog https://github.com/ciao-lang/ciao/blob/master/core/lib/foreign_interface/embedding_example/test.c https://github.com/ciao-lang/ciao/blob/master/core/lib/forei...) implement bidirectional foreign interfaces. Once you have C bindings it is easy to write bindings from Rust, C++, or any other language (that can interoperate with C). I give here some details about Ciao because this is the system I know better but it should be similar for other popular Prolog implementations. The tradeoffs depend on the complexity of the Prolog code and your needs for performance and features: pure LP, Prolog (search+unification+cut), garbage collection, dynamic database updates, constraint domains, etc. The Ciao Prolog engine is around 300-400KB. Adding a few libraries, compiler, etc. it goes to 2MB. Naive Prolog systems can be one order of magnitude smaller at the cost of sacrificing ISO compatibility, performance, etc. Note that "performance" can be very misleading. Some Prolog programs may run particularly fast in some Prolog system and very badly in others.
LeonidBugaev 5y ago
If you are interested in logic programming itself, check http://minikanren.org/ http://minikanren.org/. Go community has a bunch of its implementations.
vvern 5y ago
What does the interop with go look like? Is there a story for writing prolog queries over go data structures and iterating the results. If this could be made ergonomic, it’d be very cool.
- zimpenfish 5y ago
  From the given example, basically the same as `database/sql` - you `Exec` or `Query` a Prolog doodah, iterate over the solutions with `Next`, and `Scan` the results into your structs.
gmfawcett 5y ago
Every language should come with a Prolog interpreter. :) Well done, ichiban team!
- para_parolu 5y ago
  I never used prolog. In my mind it is some old unused language. What is good about it and why should it be embedded into other languages?
  - convolvatron 5y ago
    rule-based programming is a slightly different take than procedural programming, and can be quite a bit more expressive and efficient to evaluate than procedural for the right kind of problems. 'make' is pretty good example, but 'package manager' might be more relevant to people. instead of having explicit control flow you have rules that say 'this is the case if these other things are the case', and they get triggered to evaluate implicitly (and recursively). variables and values in declarative languages are implicitly quantified to be sets of objects, so we say 'for all X where' .. instead of '_the_ X where', which makes it similar to SQL. actually there you go - pretend this is an embedded database - that's clearly useful, except with a better query language.
  - Avshalom 5y ago
    My elevator pitch for Prolog is this: It's a constraint solving language, linear problem solving language, a database query language, a parsing language, and an expert systems language. All unified (sorry that's a pun) transparently in a single language suitable for general purpose programming instead of half a dozen partially interoperable DSLs.
  - ModernMech 5y ago
    For the same reasons that LINQ is used in C# programs.
  - Jtsummers 5y ago
    A practical (but not fielded) use that I found with Prolog: programs are multi-use. That is, if you mentally model (and I think this is natural for new Prolog programmers) a program as running in one direction, you will be pleasantly surprised to find that you can use the same program to accomplish multiple effects. Using the built-in append/3 as an example: % find the list resulting from appending two lists append([1],[2],C). %% => C = [1,2] % find the prefix given a suffix append(A,[2],[1,2]). %% => A = [1] % find the suffix given a prefix append([1],B,[1,2]). %% => B = [2] % find all prefixes and suffixes append(A,B,[1,2]). A = [], B = [1,2]; A = [1], B = [2]; A = [1,2], B = []; false ;; no more results The first line is what most programmers new to Prolog will be used to, a function performs a computation in a forward fashion (here: given two knowns, calculate something). But all the others come along "for free" (if you write it correctly, which isn't too hard once you've learned a bit of the language and style). My practical use for this was with a (prototyped, not fielded) scenario generator. Using the rules (specification for the protocol) I could generate arbitrary scenarios. I could constrain them by filling in some variables, but leaving others blank. And I could take an existing scenario and determine if it was even valid. Using append again: append(A,[3],[1,2]). %% => false Now, in my situation instead of a hardcoded [1,2] I had a recording of an exchange between nodes, and I could use this to get an answer to why it didn't conform to the spec. One program that could be used in many different ways. The other reason to use Prolog, this was a much higher level of abstraction to work with than what we ended up using. It was much shorter, but less familiar to others. So we ended up with a C# + SQL solution where we had to write each variation of the program (generate, test for validity, identify problems).
stryan 5y ago
I've been keeping an eye on this to use for the rules engine in a card game I'm writing[0]. Very excited to get back into using Prolog; I think it's fallen by the wayside a bit in the last decade or two but there's some sectors that still have strong arguments for using it if not as the main language then at least an extension language. [0] Inspired by a HN comment a while back about Gleemin, the MTG expert engine in Prolog: https://github.com/stassa/Gleemin https://github.com/stassa/Gleemin
- YeGoblynQueenne 5y ago
  Oh, hey, that's cool! Good luck with your card game, I hope we'll get to see a "Show HN" soon (no pressure!) :)
  - stryan 5y ago
    Thanks! Your post was really inspiring to me because I'd been grappling with the issue for a while; the rules are all hardcoded in Go right now and I'd been slowly trying to migrate the engine to either Guile or (more likely, since Guile in Go is through cgo) Lua. Reading your comment reminded me that A) that's similar to how Magic Arena handles cards and B) I studied Prolog back in uni and totally could do something similar. If something interesting comes out of it I'd love to do a Show HN but I'd probably have to work things out with my colleague first: he's the brains behind the game design and project, I'm just the code monkey :).
    - YeGoblynQueenne 5y ago
      Haha, OK, no pressure :) Yeah, that's how Arena does it also. There was an earlier M:tG computer game, called Duels of the Planeswalkers where each card had to be scripted manually in Lua embedded in a proprietary markup. Ouch. That just made it very hard to add new sets to the game, whereas with Arena, the cardpool is updated around the same time as the physical set hits shelves, it's amazing. That's the power of a good abstraction! I'm still half-interested in M:tG, as a subject for academic research although it puts me off a bit that it's proprietary. It would be great if there was a community-based, open-source alternative. So what I'd like to do at some point is design a generic card game engine, sort of like a virtual machine with registers representing parts of the game board (like M:tG zones) and player resources (like M:tG life) and so on and with an instruction set to manipulate those. Then different games could be implemented on top of that low-level machine in some higher-level language, compiling to the virtual machine's assembly. The high-level language could be purpose-built, or it could be an existing language, Prolog or Python or whatever, although a compiler would need to be written in each high-level language to compile down to game machine bytecode. The interesting idea would be to have the higher-level language also be the language on the cards (if that works for the game that is). So that'd be like implementing an M:tG rules engine in M:tG ability text, only ability text would be really unwieldy for that kind of thing, whereas a more convenient language could be created from scratch for this purpose. The final game could be a physical game, or a graphics engine could be bolted on top of the high-level engine to make a computer game. All this comes from the observation that, in M:tG at least and I think in all other card games I've played (I've played a few :) there are some basic operations, particularly moving a card between parts of the board (zones, in M:tG) that can be abstracted away as virtual machine instructions that push bits into registers. Anyway a generic card-game engine like that could free designers to implement their ideas quickly without having to write a completely new engine from scratch everytime, which is a big stumbling block for people who want to design new card games (I hung around the M:tG Forge forums for a while and there were lots of people planning to start their own M:tG engine, or their own card game, but many seemed to stumble on the implementation details). It would be like Unity or Unreal Engine but for card games. Then we might even see an open-source, community-maintained M:tG clone, as I hope to see at some point. Or a completely different game, of course not necessarily a clone. Anyway, rambling! Best of luck with your project. I hope it goes well and I get to hear about it.
yichiban 5y ago
Thank you for posting this, @triska!
yencabulator 5y ago
I see it claiming to have a sandbox but at the same time it seems to allow the program to read and write arbitrary files? open(File, Mode, Stream, Options) https://github.com/ichiban/prolog/blob/8e3dafd6d29334417a793f38df71190d9e584f06/engine/stream.go#L137-L154 https://github.com/ichiban/prolog/blob/8e3dafd6d29334417a793...
- yichiban 5y ago
  Good point! `open(File, Mode, Stream, Options)` and other builtin predicates are available if you construct an interpreter with `p := prolog.New(nil, nil)`. On the other hand, `p := new(prolog.Interpreter)` constructs a sandbox interpreter without any builtin predicates. You can explicitly register builtin predicates as you wish.

131 points by triska 5y ago

What are the trade offs of embedding a Prolog interpreter versus having a library that implements prolog logic without having to have another language. Are there any high quality prolog as a library implementations in languages such as Rust, C++, Java, Go?

exDM69 5y ago
> What are the trade offs of embedding a Prolog interpreter versus having a library that implements prolog logic without having to have another language. A library that implements Prolog logic is an interpreter. The difference here is that Prolog source code is passed in as a string as opposed to having an embedded domain specific language where you construct the abstract syntax tree. Go is a very simple language and it doesn't have the kind of metaprogramming facilities that are typically used for creating embedded DSLs. Hence it's a reasonable choice to just have a parser and pass in the logic code as a string. There's probably a way to pass in the AST as well but it may not be very ergonomic. Parsing the source and constructing the AST isn't very expensive and it's only done once per program, so the runtime cost isn't huge. There are Prolog and Prolog-like embeddable interpreters and logic programming systems for many other prorgamming languages, including Rust, C++ and Java. The best known ones are Clojure's core.logic (based on the logic interpreter in the SICP book) and Minikanren.
- tgv 5y ago
  Indeed. Text is "unreasonably efficient" in this case. Passing a struct is easy enough in go, but that's all it can do for you. So you'd have to pass arguments like PLClauseList{PLLoadClause{...}, ..., PLFact{Head: PLAtom{"human"}, Arguments: PLArgList{PLAtom{"socrates"}}}, ...}. Unwieldy, unreadable, and hard to edit.
- vvern 5y ago
  There are advantages to embedding. You can retain the host language type system and and object model. If you have a great query language and model but have to write a ton of code to marshal back and forth, it might not be adding that much value (classic impedance mismatch). While go’s compile time metaprogamming is virtually non-existent, it’s runtime metaprogramming with reflection is more or less complete. There’s a runtime cost to using it, but that can be mitigated. See https://github.com/cockroachdb/cockroach/tree/master/pkg/sql/schemachanger/rel https://github.com/cockroachdb/cockroach/tree/master/pkg/sql... for a reflection-driven, embedded logic query language in go that achieves pragmatic goals of writing logic queries over data structure graphs at reasonable performance and pretty good expressibility.
aarroyoc 5y ago
IMHO you loose a lot of expresiveness. Real Prolog code is not just simple rules and facts. They can be more complex than that. For example, in my case, I'd like to use DCGs a lot, which are a bit difficult to translate using "normal languages" constructs. Many Prolog systems implement DCGs with Prolog macros because Prolog is homoiconic, which most normal languages aren't (Lisp is homoiconic too). Also "logic" arithmetic (clpz, clpfd,...) is not the one that comes with normal languages and that breaks a lot of logical properties. Doing the sum of two variables in Java side will not respect logical properties. Standard is/2 in Prolog is also bad, but at least you can replace it with #= and that's it.
Avshalom 5y ago
I've never used it but for Java there's https://gitlab.com/pika-lab/tuprolog/2p-in-kotlin https://gitlab.com/pika-lab/tuprolog/2p-in-kotlin ( documentation seems to be lagging but here's the 3.3 manual https://gitlab.com/pika-lab/tuprolog/2p/-/wikis/uploads/d67e89c81da28d33cf7c8241cc35cab2/tuprolog-guide-3.3.0.pdf https://gitlab.com/pika-lab/tuprolog/2p/-/wikis/uploads/d67e... ) And specifically for Javascript there's http://tau-prolog.org/ http://tau-prolog.org/ Also pretty much every lisp that's gotten past toy stage has a Prolog implementation Although both Sicstus and SWI have strong Java and C(++) interop https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/Mixing-C-and-Prolog.html#Mixing-C-and-Prolog https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.ht... https://www.swi-prolog.org/pldoc/doc_for?object=packages https://www.swi-prolog.org/pldoc/doc_for?object=packages
jfmc 5y ago
Some Prolog systems (like Ciao Prolog https://github.com/ciao-lang/ciao/blob/master/core/lib/foreign_interface/embedding_example/test.c https://github.com/ciao-lang/ciao/blob/master/core/lib/forei...) implement bidirectional foreign interfaces. Once you have C bindings it is easy to write bindings from Rust, C++, or any other language (that can interoperate with C). I give here some details about Ciao because this is the system I know better but it should be similar for other popular Prolog implementations. The tradeoffs depend on the complexity of the Prolog code and your needs for performance and features: pure LP, Prolog (search+unification+cut), garbage collection, dynamic database updates, constraint domains, etc. The Ciao Prolog engine is around 300-400KB. Adding a few libraries, compiler, etc. it goes to 2MB. Naive Prolog systems can be one order of magnitude smaller at the cost of sacrificing ISO compatibility, performance, etc. Note that "performance" can be very misleading. Some Prolog programs may run particularly fast in some Prolog system and very badly in others.

LeonidBugaev 5y ago

If you are interested in logic programming itself, check http://minikanren.org/ http://minikanren.org/. Go community has a bunch of its implementations.

vvern 5y ago

What does the interop with go look like? Is there a story for writing prolog queries over go data structures and iterating the results. If this could be made ergonomic, it’d be very cool.

zimpenfish 5y ago
From the given example, basically the same as `database/sql` - you `Exec` or `Query` a Prolog doodah, iterate over the solutions with `Next`, and `Scan` the results into your structs.

gmfawcett 5y ago

Every language should come with a Prolog interpreter. :) Well done, ichiban team!

para_parolu 5y ago
I never used prolog. In my mind it is some old unused language. What is good about it and why should it be embedded into other languages?
- convolvatron 5y ago
  rule-based programming is a slightly different take than procedural programming, and can be quite a bit more expressive and efficient to evaluate than procedural for the right kind of problems. 'make' is pretty good example, but 'package manager' might be more relevant to people. instead of having explicit control flow you have rules that say 'this is the case if these other things are the case', and they get triggered to evaluate implicitly (and recursively). variables and values in declarative languages are implicitly quantified to be sets of objects, so we say 'for all X where' .. instead of '_the_ X where', which makes it similar to SQL. actually there you go - pretend this is an embedded database - that's clearly useful, except with a better query language.
- Avshalom 5y ago
  My elevator pitch for Prolog is this: It's a constraint solving language, linear problem solving language, a database query language, a parsing language, and an expert systems language. All unified (sorry that's a pun) transparently in a single language suitable for general purpose programming instead of half a dozen partially interoperable DSLs.
- ModernMech 5y ago
  For the same reasons that LINQ is used in C# programs.
- Jtsummers 5y ago
  A practical (but not fielded) use that I found with Prolog: programs are multi-use. That is, if you mentally model (and I think this is natural for new Prolog programmers) a program as running in one direction, you will be pleasantly surprised to find that you can use the same program to accomplish multiple effects. Using the built-in append/3 as an example: % find the list resulting from appending two lists append([1],[2],C). %% => C = [1,2] % find the prefix given a suffix append(A,[2],[1,2]). %% => A = [1] % find the suffix given a prefix append([1],B,[1,2]). %% => B = [2] % find all prefixes and suffixes append(A,B,[1,2]). A = [], B = [1,2]; A = [1], B = [2]; A = [1,2], B = []; false ;; no more results The first line is what most programmers new to Prolog will be used to, a function performs a computation in a forward fashion (here: given two knowns, calculate something). But all the others come along "for free" (if you write it correctly, which isn't too hard once you've learned a bit of the language and style). My practical use for this was with a (prototyped, not fielded) scenario generator. Using the rules (specification for the protocol) I could generate arbitrary scenarios. I could constrain them by filling in some variables, but leaving others blank. And I could take an existing scenario and determine if it was even valid. Using append again: append(A,[3],[1,2]). %% => false Now, in my situation instead of a hardcoded [1,2] I had a recording of an exchange between nodes, and I could use this to get an answer to why it didn't conform to the spec. One program that could be used in many different ways. The other reason to use Prolog, this was a much higher level of abstraction to work with than what we ended up using. It was much shorter, but less familiar to others. So we ended up with a C# + SQL solution where we had to write each variation of the program (generate, test for validity, identify problems).

stryan 5y ago

I've been keeping an eye on this to use for the rules engine in a card game I'm writing[0]. Very excited to get back into using Prolog; I think it's fallen by the wayside a bit in the last decade or two but there's some sectors that still have strong arguments for using it if not as the main language then at least an extension language. [0] Inspired by a HN comment a while back about Gleemin, the MTG expert engine in Prolog: https://github.com/stassa/Gleemin https://github.com/stassa/Gleemin

YeGoblynQueenne 5y ago
Oh, hey, that's cool! Good luck with your card game, I hope we'll get to see a "Show HN" soon (no pressure!) :)
- stryan 5y ago
  Thanks! Your post was really inspiring to me because I'd been grappling with the issue for a while; the rules are all hardcoded in Go right now and I'd been slowly trying to migrate the engine to either Guile or (more likely, since Guile in Go is through cgo) Lua. Reading your comment reminded me that A) that's similar to how Magic Arena handles cards and B) I studied Prolog back in uni and totally could do something similar. If something interesting comes out of it I'd love to do a Show HN but I'd probably have to work things out with my colleague first: he's the brains behind the game design and project, I'm just the code monkey :).
  - YeGoblynQueenne 5y ago
    Haha, OK, no pressure :) Yeah, that's how Arena does it also. There was an earlier M:tG computer game, called Duels of the Planeswalkers where each card had to be scripted manually in Lua embedded in a proprietary markup. Ouch. That just made it very hard to add new sets to the game, whereas with Arena, the cardpool is updated around the same time as the physical set hits shelves, it's amazing. That's the power of a good abstraction! I'm still half-interested in M:tG, as a subject for academic research although it puts me off a bit that it's proprietary. It would be great if there was a community-based, open-source alternative. So what I'd like to do at some point is design a generic card game engine, sort of like a virtual machine with registers representing parts of the game board (like M:tG zones) and player resources (like M:tG life) and so on and with an instruction set to manipulate those. Then different games could be implemented on top of that low-level machine in some higher-level language, compiling to the virtual machine's assembly. The high-level language could be purpose-built, or it could be an existing language, Prolog or Python or whatever, although a compiler would need to be written in each high-level language to compile down to game machine bytecode. The interesting idea would be to have the higher-level language also be the language on the cards (if that works for the game that is). So that'd be like implementing an M:tG rules engine in M:tG ability text, only ability text would be really unwieldy for that kind of thing, whereas a more convenient language could be created from scratch for this purpose. The final game could be a physical game, or a graphics engine could be bolted on top of the high-level engine to make a computer game. All this comes from the observation that, in M:tG at least and I think in all other card games I've played (I've played a few :) there are some basic operations, particularly moving a card between parts of the board (zones, in M:tG) that can be abstracted away as virtual machine instructions that push bits into registers. Anyway a generic card-game engine like that could free designers to implement their ideas quickly without having to write a completely new engine from scratch everytime, which is a big stumbling block for people who want to design new card games (I hung around the M:tG Forge forums for a while and there were lots of people planning to start their own M:tG engine, or their own card game, but many seemed to stumble on the implementation details). It would be like Unity or Unreal Engine but for card games. Then we might even see an open-source, community-maintained M:tG clone, as I hope to see at some point. Or a completely different game, of course not necessarily a clone. Anyway, rambling! Best of luck with your project. I hope it goes well and I get to hear about it.

yichiban 5y ago

Thank you for posting this, @triska!

yencabulator 5y ago

I see it claiming to have a sandbox but at the same time it seems to allow the program to read and write arbitrary files? open(File, Mode, Stream, Options) https://github.com/ichiban/prolog/blob/8e3dafd6d29334417a793f38df71190d9e584f06/engine/stream.go#L137-L154 https://github.com/ichiban/prolog/blob/8e3dafd6d29334417a793...

yichiban 5y ago
Good point! `open(File, Mode, Stream, Options)` and other builtin predicates are available if you construct an interpreter with `p := prolog.New(nil, nil)`. On the other hand, `p := new(prolog.Interpreter)` constructs a sandbox interpreter without any builtin predicates. You can explicitly register builtin predicates as you wish.