====== Denotacijska semantika ======

===== Jezik za manipulacijo s seznami =====

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].

===== Naloga =====

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!

Primer besede: ''[begin,right,down,left,end]''. Ukazi ''down'', ''left'', ''right'' in ''up'' premaknejo prazno mesto v dano smer; pri tem je npr. ukaz ''left'' veljaven tudi, če je prazno mesto na levem robu polja - v tem primeru se ne zgodi nič.