Joy (programming language) interpreter in Prolog

https://groups.google.com/d/msg/comp.lang.prolog/X0ujdV9ML5U/AU0UFMZ7EAAJ

by triska • 8 years ago

56 15 8 years ago

groups.google.com

sevensor3• 8 years 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?

macintux4• 8 years 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.

triska2• 8 years ago

One such discussion was in the context of the BEAM compiler:

https://news.ycombinator.com/item?id=17671478

macintux4• 8 years ago

Some recent relevant discussions:

https://news.ycombinator.com/item?id=17698534

https://news.ycombinator.com/item?id=17739569#17742934

https://news.ycombinator.com/item?id=17674859

https://news.ycombinator.com/item?id=17671478

ofrzeta• 8 years ago

Also this one about Factor: https://news.ycombinator.com/item?id=17726634 including another Joy implementation in Prolog https://news.ycombinator.com/item?id=17750910

garmaine• 8 years ago

Not a particularly special connection, but there are interesting combinations of the two. See also:

https://github.com/HackerFoo/poprc

YeGoblynQueenne• 8 years 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 :)

sevensor3• 8 years ago

Thank you for a very detailed and helpful answer! I particularly like the symmetry of being able to generate all of the strings in the language.

macintux4• 8 years ago

Joy was discussed here recently, not a lot of comments though:

https://news.ycombinator.com/item?id=17685548

jshap70• 8 years ago

cool, I've recently needed some help interpreting joy

lalos• 8 years 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.

triska2• 8 years 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• 8 years 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.

Joy (programming language) interpreter in Prolog

Related Stories