Studijní materiály

Zpět

Hromadně přidat materiály

Vzorovy_tahak_2007_06_06

IA014 - Funkcionální programování

Hodnocení materiálu:

Zjednodušená ukázka:

Stáhnout celý tento materiál

= {f :: Vα.(α → α ) → α → α}
let f = λxλy.x y 0 in f f (+) :: Nat
Odvození základního typu: f f (+) ≈ (λxλy.x y 0) (λxλy.x y 0) (+) ≈
2β
(λxλy.x y 0) (+) 0 ≈
2β
(+) 0 0 :: Nat
Odvození základního typu: f f succ 0 ≈ (λxλy.x(x y)) (λxλy.x(x y)) succ 0 ≈
2β
(λxλy.x(x y))((λxλy.x(x y)) succ) 0 ≈
2β

((λxλy.x(x y)) succ)(((λxλy.x(x y)) succ) 0) ≈
1β
(λy.succ(succ y))((λy.succ(succ y)) 0) ≈
1β
(λy.succ(succ y))(succ(succ 0)) ≈
1β
(succ(succ(succ(succ 0)))) :: Nat
LET
APP
APP
SPECSPEC
CON
PARSER - SYNTAKTICKÁ ANALÝZA
Příklad 1: V následujícím programu na syntaktickou analýzu lambda-termů parser term analyzuje termy složené z (jednopísmenných)
proměnných, aplikací a z abstrakcí tvaru \v.M . Vícenásobné abstrakce vyžaduje ve tvaru např. \x.\y.\z.M . Předefinujte dvě lokální
hodnoty variables a mklam v definici parseru lam tak, aby parser term akceptoval vicenasobné abstrakce i ve tvaru \x y z.M .
data Term = Var Char | App Term Term | Lam Char Term
lam = do symbol "\\"
s ← many1(token letter) \\přičtení 1 písmenka a mezery za ním
symbol "."
t ← term
return (foldr Lam t s) \\Lam ‘x’(Lam ‘y’ (Lam ‘z’ t)) - funkce foldr nám to takto uspořádá
foldr l t [x
1
, x
2
, ..., x
n
] = l x
1
(l x
2
(... (l x
n
t)...))
term :: Parser Term
term = atom ‘chainl1’ return App
atom :: Parser Term
atom = var +++ lam +++ paren
var :: Parser Term
var = token letter >>= return . Var
lam :: Parser Term
lam = symbol "\\" >> variables >>= \v -> symbol "." >>
term >>= return . mklam v
where variables = token letter
mklam = Lam
parent :: Parser Term
parent = bracket (symbol "(") term (symbol ")")
(\x.x y) y (\y.z)
term :: Parser Term
term = atom ‘chainl1’ return App \\z minulého příkladu
atom :: Parser Term
atom = var +++ lam +++ paren
var :: Parser Term
var = token letter >>= return . Var
lam :: Parser Term
lam = symbol „\\“ >> variable >>= \x -> symbol „.“ >>
term >>= return . Lam x
parent :: Parser Term
parent = bracket (symbol „(„) term (symbol „)“)
variable :: Parser Char
variable = token ident >>= return . head

Stáhnout celý tento materiál

Předchozí

1 2 3

Vloženo: 26.04.2009

Velikost: 61,35 kB

Stáhnout celý tento materiál

Komentáře

Tento materiál neobsahuje žádné komentáře.

Mohlo by tě zajímat:

Skupina předmětu IA014 - Funkcionální programování
Reference vyučujících předmětu IA014 - Funkcionální programování