Naredimo na tablo primer za jezik za manipulacijo s seznami: left premakne kurzor levo, right desno, swap pa zamenja element v seznamu, na katerega kaže kurzor, z njegovim levim sosedom. Notranje stanje programa je tako urejen par (R,C), torej seznam R in pozicija kurzorja C.

prog_listswap(In-->Out) -->
    [begin], instructs((In,1)-->(Out,_)), [end].

instructs((R0,C0)-->(R,C)) -->
    instr((R0,C0)-->(R,C)).
instructs((R0,C0)-->(R,C)) -->
    instr((R0,C0)-->(R1,C1)),
    instructs((R1,C1)-->(R,C)).

instr((R0,C0)-->(R0,C)) -->
    [left],
    { C0 > 1, C is C0 - 1 ; C0 =< 1, C is C0 }.
instr((R0,C0)-->(R0,C)) -->
    [right],
    { len(R0, LenR0), (C0 < LenR0, C is C0 + 1 ; C0 >= LenR0, C is C0) }.
instr((R0,C0)-->(R,C0)) -->
    [swap],
    { swap(R0,C0,R) }.

Najprej napišeš samo sintakso z DCG, nato narišeš parse tree za recimo program/stavek [begin,right,swap,end]. Zanimivo: prvo preslikovalno pravilo je podobno flower (samo, da sta [begin] in [end] namesto [+]), drugo in tretje pa minus –> [-] | [-], minus.

?- conc(W,_,_), prog_listswap(W, []).
  W = [begin,left,end] ;
  W = [begin,right,end] ;
  …

Razložiš, da denotacijska semantika vsakemu nekončnemu simbolu gramatike pripiše semantično funkcijo, ki slika iz sintakse (tega nekončnega simbola) v semantiko (iz pač neke, poljubne, lastno-definirane semantične domene).

NB: –> v (R,C)–>(R1,C1) je glavni funktor strukture in nima posebnega pomena!

Tu se dobro ilustrira še Ivanov stavek iz prosojnic: „Denotacijski princip definiranja semantičnih funkcij: pomen celote je kombinacija pomenov sestavnih delov“. Ta kombinacija navadno zgleda, kot da je program kompozitum funkcij. To se lepo vidi iz zaporedja ukazov, kjer nadaljnji ukazi delujejo na spremenjenem stanju od prvega ukaza. Skratka: vhod v semantično funkcijo so pomeni spodaj ležečih (v parse tree-ju) nekončnih simbolov; končni simboli so tu za sintakso.

?- conc(W,_,_), prog_listswap([1,2,3,4]-->Out, W, []).
  W = [begin, left, end],
  Out = [1,2,3,4] ;
  …
  W = [begin,right,swap,end],
  Out = [2,1,3,4] ;
  …

Dobimo lahko tudi splošno preslikovalno pravilo za nek program:

?- prog_listswap([A,B,C]-->Out, [begin,right,swap,right,swap,end], []).
  Out = [B,C,A].

Vaja je definicija jezika za 8-puzzle. Pri tem lahko uporabljajo pomožna predikata swap/4 in findblank/2. Fino je, ker dobijo program (zaporedje potez), ki nek začetni puzzle reši!