# [Haskell-cafe] Lazy Lambda Calculus implementation

Thomas Horstmeyer horstmey at Mathematik.Uni-Marburg.de
Tue Feb 11 16:00:12 UTC 2014

```Hello Chris,

it looks to me like it should be shared.

One approach to test this is "println-debugging". The Module Debug.Trace
has functions to let you write to stdout as side-effect, outside the IO

import Debug.Trace(trace)

eval' (Lam   f) env
= Now (F (\a -> eval' f (trace "evaluating element" a:env)))

With this, you would get the output "evaluating element" whenever an
entry in the list env is evaluated.

HTH
Thomas

Am 07.02.2014 15:27, schrieb Chris Warburton:
> Hello all, I've written the following implementation of Lambda Calculus,
> which will evaluate its Terms non-strictly. I've verified this since the
> Y combinator works without diverging:
>
> data Term a = Const a
>              | Var Nat
>              | Lam (Term a)
>              | Term a :@ Term a
>
> data Val a = C a
>             | F (Partial (Val a) -> Partial (Val a))
>
> type Env a = [Partial (Val a)]
>
> eval' :: Term a -> Env a -> Partial (Val a)
> eval' (Const c) env = Now (C c)
> eval' (Var   n) env = let Just x = lookUp env n in x
> eval' (Lam   f) env = Now (F (\a -> eval' f (a:env)))
> eval' (f :@  x) env = do F f' <- eval' f env
>                           Later (f' (eval' x env))
>
> eval t = eval' [] t
>
> Nat, Partial, lookUp, etc. have pretty obvious implementations.
>
> My question is, will this behave lazily? In other words will the
> contents of the 'env' lists be shared between the different contexts,
> such that forcing an element the be evaluated twice will only perform
> the evaluation once? Note that the first "do" line is the only place
> where evaluation is forced.
>
> If anyone could point out an 'obvious' reason why it will or will not be
> shared, or approaches I can take to check or infer this myself (eg. a
> Term which would show wildly different RAM usage in each case), I'd be
> very interested to know. I'd also be interested if someone spots a bug ;)
>
> For those who are curious, the code is living at
> https://gitorious.org/lazy-lambda-calculus and I've written a blog post
> detailing the iteration's I've been through at