[Haskell-cafe] Using "syntactic" to implement the lambda calculus
Alex Rozenshteyn
rpglover64 at gmail.com
Tue Jul 3 20:18:37 CEST 2012
(This is intended as a simplification of the problem I actually need to
solve.)
I'm trying to implement the lambda calculus (with CBV evaluation) using the
"syntactic" package, in such a way that a simple extension is also simple
to implement.
I am stuck on the fact that it seems that the Value type needs to be
parametrized over the Expr type and I can't seem to figure out how to do it.
I've read this post<http://www.haskell.org/pipermail/haskell-cafe/2011-May/091770.html>from
the archives, but I still seem to be missing something.
Does anyone have any suggestions?
> -- Lambda calculus
> type Ident = String
> data Value = VLam Ident Expr
> data Expr = Var Ident | Lam Ident Expr | App Expr Expr
> eval :: Expr -> Value
> eval e =
> case e of
> Var _ -> error "not closed"
> Lam i e' -> VLam i e'
> App e1 e2 ->
> case eval e1 of
> Lam i e' -> subst e' (eval e2) i
> _ -> error "illegal application"
> -- Lambda calculus with integers and addition
> data Value = VLam Ident Expr | VInt Integer
> data Expr = Var Ident | Lam Ident Expr | App Expr Expr | Plus Expr Expr
> eval e =
> case e of
> ...
> Plus e1 e2 ->
> case (eval e1, eval e2) of
> (VInt x1, VInt x2) -> VInt $ x1 + x2
> _ -> error "illegal addition"
--
Alex R
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120703/b5e71420/attachment.htm>
More information about the Haskell-Cafe
mailing list