Kirjeldus
Kirjuta mõnes funktsionaalses keeles (näiteks Idris, OCaml või Haskell) interpretaator, mis loeb sisse allpool kirjeldatud formaadis antud programmi koodi, teisendab selle konstantidega lambda-termiks ja redutseerib selle normaalkujule. Interpretaatorile peab saama anda parameetriks, kas redutseerimine peaks toimuma normaal- või aplikatiivjärjekorras ning kas interpretaator peaks trükkima välja kõik sammud või ainult lõpptulemuse.
NB! Ülesande kirjeldus on jäetud meelega üldsõnaliseks, et tudengitel oleks võimalus loovalt probleemile läheneda.
Programmi koodi spetsifikatsioon
Programmi kood on .lam laiendiga failis, näiteks test1.lam
Koodis on definitsioonid kujul <nimi> = <lambda-term> ; . Ühe definitsiooni nimi on main. Lambda abstraktsiooni sümboliks on langjoon \ kui ka lambda sümbol λ.
Lambda termides on lubatud kasutada mitme parameetriga abstraktsioone, näiteks \ x y. add (mul x 2) y.
Termides on lubatud konstandid add, sub, mul, iszero, true, false, cond, nil, cons, tl, hd, null, Y. Konstandid redutseeritakse vastavalt delta-reduktsiooni reeglitele.
Muutujad algavad tähega aga võivad sisaldada ka numbreid. Näiteks λ x1a x20. x1a.
Koodi teisendamine lambda-termiks
Lambda-termiks on main-i definitsioon. Mitterekursiivsed definitsioonid asendada termi sisse. S.t. koodile test1.lam vastab term (\ x. add x x) ((\ x. add x x) 2).
Rekursiivsed definitsioonid kujul nimi = \ x1 ... xn. t, kus term t sisaldab vabalt muutujat nimi, teisendada enne kujule nimi = Y (\ nimi x1 ... xn. t).
Nõuded
Miinimumnõuded. (Kui pole täidetud, siis null punkti)
- Interpretaator on kirjutatud FP keeles ja FP stiilis.
- Interpretaatori esitaja (autor) saab ise aru, mida interpretaator teeb.
- Kõik näitefailid parsitakse korrektselt
- Puhta lambda reduktsioonides pole vigu.
Hindamiskriteerium. (Maksimumpunktid saab, kui on täidetud.)
- Konstantide redutseerimiesl ei tehta vigu.
- Kood on loetav ja kasutab mõistlikult FP mustreid (foldl, foldr, map, Monad jne.)
- Lisatud vähemalt üks täiendus, mis näitekoodis ei kasutata.
Soovitused
Parsimiseks võib kasutada näiteks parserit moodulis Data.String.Parser (contrib paketis).
import Data.String.Parser
-- Parsime avaldisi järgneva AST jaoks
data Expr = Variable String | Const Integer | Add Expr Expr | Mul Expr Expr
-- kasutades monaadi liidest ja do-süntaksit saame parsida asju järjest
name : Parser String
name = do x <- letter
xs <- many alphaNum
pure (singleton x ++ foldr strCons "" xs)
-- kuna parserid on rekursiivsed, peame olema ettevaatlikud, et definitsioonid tsükklisse ei lähe -- Lazy
parensP : Lazy (Parser a) -> Parser a
parensP p = do
_ <- lexeme (char '(')
x <- p
_ <- lexeme (char ')')
pure x
-- kasutades Alternative liidest (<|>) saame defineerida erinevad juhud
-- kasutades Applicative liidese mustrit f <$> m1 <*> m2 <*> m3, saame funktsioonirakenduse monaadide peale "tõsta"
-- tavaliselt on mõistlik defineerida erinevad pretsendentside tasemed: siin l1 ja l2
expr : Parser Expr
expr = add <|> l1
where
mutual
add : Parser Expr
add = do x <- l1
_ <- char '+'
y <- expr
pure (Add x y)
mul : Parser Expr
mul = do x <- l2
_ <- char '*'
y <- l1
pure (Mul x y)
l1 : Parser Expr
l1 = mul <|> l2
l2 : Parser Expr
l2 = parensP expr <|> (Variable <$> name) <|> (Const <$> integer)
-- Näide, kuidas sõnet parsida
parseExpr : String -> Maybe Expr
parseExpr s =
case parse expr s of
Right (t, _) => Just t
Left _ => Nothing
Main> parseExpr "1+2*3+z1" Just (Add (Const 1) (Add (Mul (Const 2) (Const 3)) (Variable "z1")))
NB! Sellise teegiga saab teha väga hästi loetavaid FP parsereid aga selliste parserite kirjutamine võtab oma aja. Pole mõtet loota, et töötava parseri saab valmis viie minutiga. Pigem läheb parseri töölesaamiseks paar päeva aega aga seejärel saab selle nii loetavaks kirjutada, et tunub nagu selle võiks viie minutiga valmis teha.