lisp2prolog je jednoduchý, v jazyku Common LISP implementovaný, překladač programů v programovacím jazyku Common LISP do jazyka Prolog.

Program umí překládat aritmetické výrazy s proměnnými, čísly a operátory +, -, *, /. Podporovány jsou funkce car, cdr, cons manipulující s cons buňkami. Nerovnost může být otestována operátory >, <, >=, <=. Rovnost pomocí =, eq a null. Nil reprezentuje prázdný seznam. Nejvýznamnější vlastností překladače je podpora větvení kódu přikazem cond, který se může nacházet v libovolném místě, kde se očekává výraz, např. jako operand aritmetického výrazu.

Vstupní gramatika překladače

G=({PROGRAM, LP, RP, DEFUN, PARAMETERS, PARAMETERS_REST, SPACE, EXPRESSIONS, ONE_EXPRESSION, FUNCTION, EQUALITY_OP, BIN_ARITHM_OP, RELATION_OP, COND_VARIANTS, ONE_COND_VARIANT, OTHER_FUNCTION, VARIABLE, IDENT, NUMBER}, {(, ), ` ', +, -, *, /, >, >=, <, <=, nil, null, cond, cons, car, cdr}, Rules, PROGRAM)

Rules:
PROGRAM          -> LP defun DEFUN RP PROGRAM
                  | epsilon
LP               -> (
RP               -> )

DEFUN            -> IDENT LP PARAMETERS RP EXPRESSIONS

PARAMETERS       -> IDENT PARAMETERS_REST
                  | epsilon
PARAMETERS_REST  -> SPACE IDENT PARAMETERS_REST
                  | epsilon
SPACE            -> ` '

EXPRESSIONS      -> ONE_EXPRESSION EXPRESSIONS
	          | epsilon
ONE_EXPRESSION   -> LP FUNCTION RP
                  | NUMBER
                  | VARIABLE
FUNCTION         -> EQUALITY_OP ONE_EXPRESSION ON_EXPRESSION
                  | BIN_ARITHM_OP ONE_EXPRESSION ONE_EXPRESSION
                  | RELATION_OP ONE_EXPRESSION ONE_EXPRESSION
                  | null
                  | cond COND_VARIANTS
                  | cons ONE_EXP ONE_EXP
                  | car ONE_EXP
                  | cdr ONE_EXP
                  | OTHER_FUNCTION
EQUALITY_OP      -> =
                  | eq
BIN_ARITHM_O     -> +
                  | -
                  | *
                  | /
RELATION_OP      -> >
                  | >=
                  | <
                  | <=
COND_VARIANTS    -> ONE_COND_VARIANT COND_VARIANT
                  | epsilon
ONE_COND_VARIANT -> LP ONE_EXPRESSION EXPRESSIONS RP

OTHER_FUNCTION   -> IDENT PARAMETERS

VARIABLE         -> nil
                  | IDENT

Jak to pracuje?

Vetšina funkcí překladače očekává parametr stav nebo seznam stavů a vrací modifikovaný seznam stavů (dále jen výstupní seznam stavů). Stav je pětice reprezentující kód v Prologu, tvoří ji:

• návratová hodnota,
• příznak jednoduchého přiřazení - návratovou hodnotou každého stavu ve výstupním seznamu stavů může být i aritmetický výraz;
  není-li tento příznak nastaven, přípustnými návratovými hodnotami jsou pouze proměnná, číslo nebo speciální hodnota reprezentující prázdný seznam.
• seznam proměnných a jejich hodnot,
• kód v Prologu, ve kterém však ještě nejsou nahrazeny proměnné svými hodnotami
• seznam argumentů funkce - tento parametr je používán, aby identifikátory parametrů funkce v LISPu zůstaly zachovány i v Prologu a nedošlo k jejich nahrazení za vygenerované identifikátory.

Ukázka vnitřní formy

Vnitřní formu si ukážeme na příkladu faktoriálu s koncovou rekurzí.
Nejprve zdrojový soubor v LISPu:

(defun factorialTR (X TMP)
  (cond ((= X 0) TMP)
	((factorialTR (- X 1) (* X TMP)))))

Výstupem překladače bude následující kód v Prologu:

FACTORIALTR(0,TMP,TMP).
FACTORIALTR(X,TMP,T3) :-
   T1 is X - 1,
   T2 is X * TMP,
   FACTORIALTR(T1,T2,T3).

A nyní konečně následuje vnitřní forma - seznam stavů.

(((PRINT-VALUE . TMP) NIL (X 0 TMP TMP) ((FACTORIALTR (PRINT-PARAMS)))
  (X TMP))
 ((PRINT-VALUE . T3) NIL (X X TMP TMP T1 T1 T2 T2 T3 T3)
  ((FACTORIALTR (PRINT-PARAMS))
   ((PRINT-VALUE . T1) " is " (PRINT-VALUE . X) " - " 1)
   ((PRINT-VALUE . T2) " is " (PRINT-VALUE . X) " * "
    (PRINT-VALUE . TMP))
   (FACTORIALTR "(" (PRINT-VALUE . T1) "," (PRINT-VALUE . T2) ","
       (PRINT-VALUE . T3) ")"))
  (X TMP)))

Z uvedeného příkladu je patrné, že každý stav reprezentuje právě jednu klauzuli Prologu. Pod klauzulí zde rozumíme fakt nebo pravidlo. Kód Prologu tvoří seznam prvků, z nichž každý reprezentuje jeden "řádek" pravidla.

Práce se seznamy stavů

Při překladu volání funkce jsou nejprve vyhodnoceny její parametry (výrazy), všem těmto parametrům se předá "vstupní" seznam stavů s obsahem platným v okamžiku před zavoláním této funkce. Každý parametr při svém vyhodnocování vytvoří modifikovaný seznam stavů. Vlastní funkce pak je zodpovědná za sloučení seznamů stavů všech svých parametrů.

Ze vstupní gramatiky je vidět, že příkaz větvení cond se může nacházet v libovolném místě programu, kde je očekáván výraz. Musíme odlišit jednotlivé varianty větvení - seznam stavů musíme naklonovat tolikrát, kolika větvemi se může program vydat. Výrazům v jednotlivých variantách však samozřejmě předáváme pouze jednu kopii původního seznamu stavů.

Každý parametr funkce nám tedy vrací seznam stavů, který může být v důsledku větvení libovolně dlouhý. To nám působí problémy. První parametr může například vracet seznam se 4 stavy, druhý se 3 a třetí pouze s jedním stavem. Proto si opět naklonujeme každý z těchto seznamů tolikrát, abychom dostali úplnou množinu permutací stavů těchto seznamů. Nyní už můžeme přikročit ke slučování vlastních stavů.

Při slučování stavů dochází k prostému sjednocování kódů v Prologu a k modifikaci seznamů proměnných a jejich hodnot.

Reprezentace cons buněk

Pro každou cons buňku je vytvořena nová pomocná proměnná, hodnotou je seznam obsahující příznak cons buňky, car výraz a cdr výraz. Funkce cons vrací tuto proměnnou jako návratovou hodnotu stavu.
Primárním účelem generovaných proměnných je vlastnost Prologu - nevyhodnocování aritmetických výrazů, které jsou parametry predikátu. Aritmetické výrazy nejsou totiž pro Prolog ničím jiným než strukturovanými objekty. Vyřešit problém cons buněk tímto způsobem se však ukázalo jako velice elegantní řešení.

Další informace

Pro více úspěšných a neúspěšných překladů spolu s jejich popisem klikněte sem.