7 ms·

Joy (programming language) interpreter in Prolog

56 points by triska 8y ago

sevensor 8y ago
This seems neat, and I'd like to know more about why it was done. Is there a particular link between logic programming and concatenative programming?
- macintux 8y ago
  I don't know the answer, but there was a fair bit of discussion here on HN recently that Prolog made for a nice platform for building out a new language. I'll try to find the comments.
  - triska 8y ago
    One such discussion was in the context of the BEAM compiler: https://news.ycombinator.com/item?id=17671478 https://news.ycombinator.com/item?id=17671478
    - macintux 8y ago
      Erlang is by far my favorite language for anything more complex than a Perl script. I definitely enjoyed that piece.
  - macintux 8y ago
    Some recent relevant discussions: https://news.ycombinator.com/item?id=17698534 https://news.ycombinator.com/item?id=17698534 https://news.ycombinator.com/item?id=17739569#17742934 https://news.ycombinator.com/item?id=17739569#17742934 https://news.ycombinator.com/item?id=17674859 https://news.ycombinator.com/item?id=17674859 https://news.ycombinator.com/item?id=17671478 https://news.ycombinator.com/item?id=17671478
    - sevensor 8y ago
      Thanks for digging up the context!
  - ofrzeta 8y ago
    Also this one about Factor: https://news.ycombinator.com/item?id=17726634 https://news.ycombinator.com/item?id=17726634 including another Joy implementation in Prolog https://news.ycombinator.com/item?id=17750910 https://news.ycombinator.com/item?id=17750910
- garmaine 8y ago
  Not a particularly special connection, but there are interesting combinations of the two. See also: https://github.com/HackerFoo/poprc https://github.com/HackerFoo/poprc
- deleted 8y ago
  [deleted]
- deleted 8y ago
  [deleted]
- YeGoblynQueenne 8y ago
  I think the most important point is that writing a parser and therefore an interpreter or a compiler in Prolog is child's play. This is thanks to the Definite Clause Grammars formalism, which also comes with a special syntactic sugar that starts out very similar to BNF. For instance, the following is a short grammar for the aⁿbⁿ CFG: 'S' --> 'T', 'U'. 'S' --> 'T', 'S', 'U'. 'T' --> [a]. 'U' --> [b]. The symbols on the left-hand side of '-->' (read as "expands to") are nonterminals. On the right-hand side, symbols in square braces are terminals, the others non-terminals. Capitalised symbols are variables in Prolog, hence the need to enclose in single quotes. Loaded into a suitable Prolog compiler (i.e. one that recognises the DCG syntactic sugar) and called through the phrase/2 predicate for convenience, the grammar above will recognise strings of the aⁿbⁿ language: ?- phrase('S', [a,b]). true . ?- phrase('S', [a,a,b,b]). true . ?- phrase('S', [a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,b,b,b]). true . It will also reject strings that don't belong to the grammar: ?- phrase('S', [a,a,b,b,b]). false. Or split a string into the tokens accepted by the grammar and a suffix: ?- phrase('S', [a,a,b,b,b], R). R = [b] . And finally also generate (eventually all) strings in the aⁿbⁿ language: ?- phrase('S', P). P = [a, b] ; P = [a, a, b, b] ; P = [a, a, a, b, b, b] ; P = [a, a, a, a, b, b, b, b] ; P = [a, a, a, a, a, b, b, b, b|...] . The phrase/2 and phrase/3 predicates used above are interfaces to difference lists, a Prolog formalism used to concatenate lists in a single operation. The aⁿbⁿ grammar given above in DCG syntactic-sugar notation is translated internally to ordinary Prolog clauses: ?- listing(['S','T','U']). 'S'(A, C) :- 'T'(A, B), 'U'(B, C). 'S'(A, D) :- 'T'(A, B), 'S'(B, C), 'U'(C, D). 'T'([a|A], A). 'U'([b|A], A). (listing/1 output edited for brevity). The two predicates, 'T'/2 and 'U'/2 use a difference list to split their "input" to a prefix and a suffix. So, in 'T'([a|A], A), "a" is the token accepted by that rule, "[a|A]" is a difference list with "a" at its head and the variable, "A" in its tail, and the second argument, A, unifies the output of the rule to the tokens remaining in the input after "a" is accepted - or, in other words, the suffix to the string "a" that must be parsed by the rest of the grammar. Accordingly, in the first clause of the grammar, 'S'(A, C) :- 'T'(A, B), 'U'(B, C), the variable "A" is the start of the input that is accepted by 'T'/2 (i.e. a single "a"), the variable "B" is the input remaining after "A", and "C" is the list of tokens remaining in the string once "B" has been accepted by 'U'. DCGs can also accept arguments in the left-hand side (which, as far as I can tell, BNF notation doesn't). For instance, the following is a short grammar of a subset of the Magic: the Gathering ability text language: ability(destroy, X) --> destroy(X). destroy(X) --> [destroy], target(X). target(X) --> [target], permanent(X). permanent(X) --> [creature], creature(X). permanent(X) --> [artifact], artifact(X). permanent(X) --> [land], land(X). spell(X) --> [sorcery], sorcery(X). spell(X) --> [instant], instant(X). creature('Llanowar Elves') --> []. artifact('Ankh of Mishra') --> []. land('Mountain') --> []. % etc permanents sorcery('Duress') --> []. instant('Lightning Bolt') --> []. From which the following strings can be derived: ?- phrase(ability(destroy, X), P). X = 'Llanowar Elves', P = [destroy, target, creature] ; X = 'Ankh of Mishra', P = [destroy, target, artifact] ; X = 'Mountain', P = [destroy, target, land]. You can also test the grammatical type of a string (and at the same time, the M:tG type of a card): ?- phrase(instant(X), []). X = 'Lightning Bolt'. ?- phrase(creature(X), []). X = 'Llanowar Elves'. And so you can't destroy sorceries or instants: ?- phrase(ability(destroy, 'Duress'), P). false. ?- phrase(instant(X), []), phrase(ability(destroy,X), R). false. In short, no matter the target language, it is natural to express its grammar in Prolog as a DCG - and very profitable to do so, since one gets a parser, which is also a generator at no added effort. Indeed, the article above uses DCG notation to declare the Joy grammar. I probably don't need to point out what a hassle it is to achieve the same results in typical compiler-generators, where defining a grammar is only the start of your troubles :)
macintux 8y ago
Joy was discussed here recently, not a lot of comments though: https://news.ycombinator.com/item?id=17685548 https://news.ycombinator.com/item?id=17685548
jshap70 8y ago
cool, I've recently needed some help interpreting joy
lalos 8y ago
I've been seeing more movement here around Prolog, any idea why? Prolog has existed for a long time so that's why I'm surprised.
- triska 8y ago
  The core language has indeed been around for several decades. However, many important features that are necessary for more interesting Prolog programs have become widely available and implemented with acceptable efficiency only in the much more recent past. For example, this concrete Joy interpreter depends on features (call_residue_vars/2, copy_term/3 etc.) that were added to a development version of SWI-Prolog only a few years ago. It takes at least several months, often even years, until development features make it into stable versions and distributions, and until application programmers get accustomed to them or even start using them.
- agumonkey 8y ago
  Too esoteric when cpp/java was the norm. Nowadays pure functional programming is a thing on the main stream, it gives logic programming an narrower gap.

56 points by triska 8y ago

This seems neat, and I'd like to know more about why it was done. Is there a particular link between logic programming and concatenative programming?

macintux 8y ago
I don't know the answer, but there was a fair bit of discussion here on HN recently that Prolog made for a nice platform for building out a new language. I'll try to find the comments.
- triska 8y ago
  One such discussion was in the context of the BEAM compiler: https://news.ycombinator.com/item?id=17671478 https://news.ycombinator.com/item?id=17671478
  - macintux 8y ago
    Erlang is by far my favorite language for anything more complex than a Perl script. I definitely enjoyed that piece.
- macintux 8y ago
  Some recent relevant discussions: https://news.ycombinator.com/item?id=17698534 https://news.ycombinator.com/item?id=17698534 https://news.ycombinator.com/item?id=17739569#17742934 https://news.ycombinator.com/item?id=17739569#17742934 https://news.ycombinator.com/item?id=17674859 https://news.ycombinator.com/item?id=17674859 https://news.ycombinator.com/item?id=17671478 https://news.ycombinator.com/item?id=17671478
  - sevensor 8y ago
    Thanks for digging up the context!
- ofrzeta 8y ago
  Also this one about Factor: https://news.ycombinator.com/item?id=17726634 https://news.ycombinator.com/item?id=17726634 including another Joy implementation in Prolog https://news.ycombinator.com/item?id=17750910 https://news.ycombinator.com/item?id=17750910
garmaine 8y ago
Not a particularly special connection, but there are interesting combinations of the two. See also: https://github.com/HackerFoo/poprc https://github.com/HackerFoo/poprc
deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
YeGoblynQueenne 8y ago
I think the most important point is that writing a parser and therefore an interpreter or a compiler in Prolog is child's play. This is thanks to the Definite Clause Grammars formalism, which also comes with a special syntactic sugar that starts out very similar to BNF. For instance, the following is a short grammar for the aⁿbⁿ CFG: 'S' --> 'T', 'U'. 'S' --> 'T', 'S', 'U'. 'T' --> [a]. 'U' --> [b]. The symbols on the left-hand side of '-->' (read as "expands to") are nonterminals. On the right-hand side, symbols in square braces are terminals, the others non-terminals. Capitalised symbols are variables in Prolog, hence the need to enclose in single quotes. Loaded into a suitable Prolog compiler (i.e. one that recognises the DCG syntactic sugar) and called through the phrase/2 predicate for convenience, the grammar above will recognise strings of the aⁿbⁿ language: ?- phrase('S', [a,b]). true . ?- phrase('S', [a,a,b,b]). true . ?- phrase('S', [a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,b,b,b]). true . It will also reject strings that don't belong to the grammar: ?- phrase('S', [a,a,b,b,b]). false. Or split a string into the tokens accepted by the grammar and a suffix: ?- phrase('S', [a,a,b,b,b], R). R = [b] . And finally also generate (eventually all) strings in the aⁿbⁿ language: ?- phrase('S', P). P = [a, b] ; P = [a, a, b, b] ; P = [a, a, a, b, b, b] ; P = [a, a, a, a, b, b, b, b] ; P = [a, a, a, a, a, b, b, b, b|...] . The phrase/2 and phrase/3 predicates used above are interfaces to difference lists, a Prolog formalism used to concatenate lists in a single operation. The aⁿbⁿ grammar given above in DCG syntactic-sugar notation is translated internally to ordinary Prolog clauses: ?- listing(['S','T','U']). 'S'(A, C) :- 'T'(A, B), 'U'(B, C). 'S'(A, D) :- 'T'(A, B), 'S'(B, C), 'U'(C, D). 'T'([a|A], A). 'U'([b|A], A). (listing/1 output edited for brevity). The two predicates, 'T'/2 and 'U'/2 use a difference list to split their "input" to a prefix and a suffix. So, in 'T'([a|A], A), "a" is the token accepted by that rule, "[a|A]" is a difference list with "a" at its head and the variable, "A" in its tail, and the second argument, A, unifies the output of the rule to the tokens remaining in the input after "a" is accepted - or, in other words, the suffix to the string "a" that must be parsed by the rest of the grammar. Accordingly, in the first clause of the grammar, 'S'(A, C) :- 'T'(A, B), 'U'(B, C), the variable "A" is the start of the input that is accepted by 'T'/2 (i.e. a single "a"), the variable "B" is the input remaining after "A", and "C" is the list of tokens remaining in the string once "B" has been accepted by 'U'. DCGs can also accept arguments in the left-hand side (which, as far as I can tell, BNF notation doesn't). For instance, the following is a short grammar of a subset of the Magic: the Gathering ability text language: ability(destroy, X) --> destroy(X). destroy(X) --> [destroy], target(X). target(X) --> [target], permanent(X). permanent(X) --> [creature], creature(X). permanent(X) --> [artifact], artifact(X). permanent(X) --> [land], land(X). spell(X) --> [sorcery], sorcery(X). spell(X) --> [instant], instant(X). creature('Llanowar Elves') --> []. artifact('Ankh of Mishra') --> []. land('Mountain') --> []. % etc permanents sorcery('Duress') --> []. instant('Lightning Bolt') --> []. From which the following strings can be derived: ?- phrase(ability(destroy, X), P). X = 'Llanowar Elves', P = [destroy, target, creature] ; X = 'Ankh of Mishra', P = [destroy, target, artifact] ; X = 'Mountain', P = [destroy, target, land]. You can also test the grammatical type of a string (and at the same time, the M:tG type of a card): ?- phrase(instant(X), []). X = 'Lightning Bolt'. ?- phrase(creature(X), []). X = 'Llanowar Elves'. And so you can't destroy sorceries or instants: ?- phrase(ability(destroy, 'Duress'), P). false. ?- phrase(instant(X), []), phrase(ability(destroy,X), R). false. In short, no matter the target language, it is natural to express its grammar in Prolog as a DCG - and very profitable to do so, since one gets a parser, which is also a generator at no added effort. Indeed, the article above uses DCG notation to declare the Joy grammar. I probably don't need to point out what a hassle it is to achieve the same results in typical compiler-generators, where defining a grammar is only the start of your troubles :)

macintux 8y ago

Joy was discussed here recently, not a lot of comments though: https://news.ycombinator.com/item?id=17685548 https://news.ycombinator.com/item?id=17685548

jshap70 8y ago

cool, I've recently needed some help interpreting joy

lalos 8y ago

I've been seeing more movement here around Prolog, any idea why? Prolog has existed for a long time so that's why I'm surprised.

triska 8y ago
The core language has indeed been around for several decades. However, many important features that are necessary for more interesting Prolog programs have become widely available and implemented with acceptable efficiency only in the much more recent past. For example, this concrete Joy interpreter depends on features (call_residue_vars/2, copy_term/3 etc.) that were added to a development version of SWI-Prolog only a few years ago. It takes at least several months, often even years, until development features make it into stable versions and distributions, and until application programmers get accustomed to them or even start using them.
agumonkey 8y ago
Too esoteric when cpp/java was the norm. Nowadays pure functional programming is a thing on the main stream, it gives logic programming an narrower gap.