• A way of expressing grammars in Prolog
• Extension of context-free grammars:
  • Context through additional arguments and semicontext
  • Approach to return values
  • Usage of built-in Prolog predicates
• Syntactic sugar for the description of lists

Head --> Body.

• Head
  Non-terminal of any arity
• Body
  Sequence of terminals, non-terminals, and Prolog predicates
• Terminal
  Prolog list of any type, possibly strings
• Prolog code
  Built-in or user-defined Prolog predicates, enclosed in curly braces

• Usage of well-known Prolog control predicates:
  ;/2 and |/2,
  ->/2,
  \+/1,
  !/1
• Head can be any callable term:
  a,
  a(X),
  a(b,2)

% structure
sentence    --> noun_phrase, ws, verb_phrase.
noun_phrase --> determiner, ws, noun.
verb_phrase --> verb, ws, noun_phrase.

% vocabulary
determiner  --> "a".    % = [a]
determiner  --> "the".
noun        --> "cat".
noun        --> "mouse", { is_mouse_allowed }.
verb        --> "chases".
ws          --> " ".

% user predicate
is_mouse_allowed.

% structure
sentence    --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
verb_phrase --> verb, noun_phrase.

% vocabulary
determiner  --> "a".    % = [a]
determiner  --> "the".
noun        --> "cat".
noun        --> "mouse", { is_mouse_allowed }.
verb        --> "chases".

% user predicate
is_mouse_allowed.

• Natural Language Processing
• Formal languages, e.g., library(http/html_write)
• Formal languages using quasi-quotations

Since SWI-Prolog 6.3 (Wielemaker & Hendricks, WLPE 2013)

{| Tag || Content |}

?- Person = {| type ||
   name:    String!
   age:     Integer
   books(favourite: Boolean): [Book]
   friends: [Person]
|}.

Falco Nogatz and Dietmar Seipel. 2016. Implementing GraphQL as a Query Language for Deductive Databases in SWI-Prolog Using DCGs, Quasi Quotations, and Dicts. In Proc. 30th Workshop on Logic Programming (WLP 2016).

Handle embedded code as preconditions (blackbox), correct line numbers

Extend existing DCGs and Prolog systems

Reasonable overhead, pre-compilation in mind

% structure
sentence    --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
verb_phrase --> verb, noun_phrase.

% vocabulary
determiner  --> "a".    % = [a]
determiner  --> "the".
noun        --> "cat".
noun        --> "mouse", { is_mouse_allowed }.
verb        --> "chases".

% user predicate
is_mouse_allowed.

sentence(A, C) :-
  noun_phrase(A, B),
  verb_phrase(B, C).
...
determiner([a|A], A).
determiner([t,h,e|A], A).
noun([c,a,t|A], A).
noun([m,o,u,s,e|A], A) :- is_mouse_allowed.
...

sentence(sentence(NP,VP)) --> noun_phrase(NP), verb_phrase(VP).
noun_phrase(noun_phrase(D,N)) --> determiner(D), noun(N).
verb_phrase(verb_phrase(V,NP)) --> verb(V), noun_phrase(NP).
determiner(determiner("a")) --> "a".
determiner(determiner("the")) --> "the".
noun(noun("cat")) --> "cat".
noun(noun("mouse")) --> "mouse", { is_mouse_allowed }.
verb(verb("chases")) --> "chases".

?- Input = "the cat chases a mouse",
   phrase(noun_phrase(NP), Input, Rest).
Rest = "chases a mouse",
NP = noun_phrase(determiner("the"), noun("cat")).

Simple implementation using term expansion

Name clash
Can not use existing programs
Only successful applications

prolog_trace_interception(Port, Frame, Choice, Action) :-
  % retrieve unique program counter
  get_counter(N),
  % get information about current event
  prolog_frame_attribute(Frame,goal,Goal),
  prolog_frame_attribute(Frame,parent,Parent),
  prolog_choice_attribute(Choice,frame,ChoiceFrame),
  % ...
  % assert information as predicate `step/N`
  assert(step(N,Port,Frame,Goal,Parent,Choice,ChoiceFrame, ...)),
  % continue with the execution
  Action = continue.

?- Input = "the cat chases a mouse",
   trace, phrase(noun_phrase, Input, Rest), notrace.
Rest = "chases a mouse".
?- listing(step).
% ...
step(3,unify,235,noun_phrase(A,[]),
   $dcg:call_dcg(noun_phrase,A,[]), ...).
step(4,call,255,determiner(A,B),
   noun_phrase(A,[]), ...).
% ...

Native support for backtracking
Information about current port, stack frame, choice points

No unique identifiers (in deterministic predicates)
No easy distinction between non-terminals and Prolog predicates
No way to re-use existing tracer

prolog_trace_interception(Port, Frame, Choice, Action) :-
  % retrieve unique program counter
  get_counter(N),
  % get information about current event
  prolog_frame_attribute(Frame,goal,Goal),
  prolog_frame_attribute(Frame,parent,Parent),
  prolog_choice_attribute(Choice,frame,ChoiceFrame),
  % ...
  % assert information as predicate `step/N`
  assert(step(N,Port,Frame,Goal,Parent,Choice,ChoiceFrame, ...)),
  % continue with the execution
  Action = continue.

vanilla(true).
vanilla((A , B)) :- vanilla(A), vanilla(B).
vanilla((A = B)) :- A = B.
vanilla(A) :- 
   A \= (_ , _), A \= (_ = _), A \= true,
   clause(A, B),
   vanilla(B).

?- Input = "the cat chases a mouse", 
   vanilla(noun_phrase(Input, Rest)).
Rest = "chases a mouse".

Leon Sterling and Ehud Y Shapiro. 1994. The art of Prolog: advanced programming techniques. MIT press.

mi_tree(true, true).
mi_tree((A, B) , (TA, TB)) :- mi_tree(A, TA), mi_tree(B, TB).
mi_tree((A = B), (A = B)) :- A = B.
mi_tree(A,(A:T)) :-
   A \= (_ , _), A \= (_ = _), A \= true,
   clause(A, B), 
   mi_tree(B, T).

?- ..., mi_tree(noun_phrase(Input, Rest), T).
Rest = "chases a mouse",
T = noun_phrase("the cat chases a mouse", "chases a mouse"):(
      determiner("the cat", "cat"):true,
      noun("cat", ""):true ).

mi_print(true, _Level).
mi_print((A , B), L) :-
   mi_print(A, L), mi_print(B, L).
mi_print((A = B), L) :-
   ( A = B ~> print_indented((A = B):exit, L)
   ; print_indented((A = B):fail, L), fail ).
mi_print(A, L) :- L1 is L+1,
   A \= (_ , _), A \= (_ = _), A \= true,
   print_indented(A:call, L),
   nth_clause(A, Index, Sign),
   ( clause(A, B, Sign), mi_print(B, L1) ~>
     print_indented(A:Index:exit, L)
   ; print_indented(A:Index:fail, L), fail ).
print_indented(A, L) :-
   Indent is 2*L, tab(Indent), writeln(A).

?- mi_print(verb_phrase("chases a dog", ""), 0).
verb_phrase("chases a dog",""):call
   verb("chases a dog",_6966):call
   verb("chases a dog","a dog"):1:exit
   noun_phrase("a dog",""):call
      determiner("a dog",_7198):call
      determiner("a dog",_7198):1:fail
      determiner("a dog","dog"):2:exit
      noun("dog",""):call
      noun("dog",""):1:fail
      noun("dog",""):2:fail
      determiner("a dog",_7198):2:fail
   noun_phrase("a dog",""):1:fail
   verb("chases a dog",_6966):1:fail
verb_phrase("chases a dog",""):1:fail
false.

mouse_phrase --> determiner, "mouse", { is_mouse_allowed }.

mouse_phrase(A, C) :-
   determiner(A, B),
   B = [m,o,u,s,e|C],
   is_mouse_allowed.

mouse_phrase(A, C) :-
   'DCGBody'(determiner, A, B),
   'T'("mouse", B, C),
   'P'(is_mouse_allowed).

Tag{
   key1: Value1,
   key2: Value2, ... }

event{
   step: <N>,
   type: <unify | exit | fail | depth>,
   redo: <Redo>,
   goal: <Goal with current variable bindings>,
   line: <Line number of associated clause
            | 'T' | 'P' | 'DCGBody'>
}

• Dicts
• Pengines

• Dicts
• Pengines

• HTML5
• JavaScript
• CSS3
• MUI, jQuery, CodeMirror

• Discussion about Tracing with Meta-Interpreters
• DCG Tracer: Tracing Meta-Interpreter
• DCG Visualiser: Pengine- and web-based Visualisation

• Support for full DCG spec
• EDCG