News for hackers. Stuff that matters.
Re:Joy (programming language) interpreter in Prolog by YeGoblynQueenne on Saturday August 18, 2018 @07:11AM (#17787965)
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 :)

Re:Joy (programming language) interpreter in Prolog by sevensor on Monday August 20, 2018 @10:29AM (#17800169)
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.