Joy (programming language) interpreter in Prolog

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.

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

https://github.com/HackerFoo/poprc

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 :)

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.

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.