> module Lambda where

Variables 

> data X = X
> data Next a = Next a
> type X0 = X
> type X1 = Next X0
> type X2 = Next X1
> type X3 = Next X2
> type X4 = Next X3
> type X5 = Next X4
> type X6 = Next X5

> x0 = X
> x1 = Next x0
> x2 = Next x1
> x3 = Next x2
> x4 = Next x3
> x5 = Next x4
> x6 = Next x5

Lambda abstraction : \x->y
Use Xi as variables.

> data L x y = L x y | x :\ y

Application : x y

> data A x y = A x y | x :/ y

Generate fresh variables for alpha-conversion.

> class FreshVar a b | a -> b where
>   freshVar :: a -> b
>   freshVar = undefined

> instance FreshVar X (Next X)
> instance FreshVar (Next x) (Next (Next x))

> class MaxVar a b c | a b -> c where
>   maxVar :: a -> b -> c
>   maxVar = undefined

> instance MaxVar X X X
> instance MaxVar X (Next x) (Next x)
> instance MaxVar (Next x) X (Next x)
> instance MaxVar a b c => MaxVar (Next a) (Next b) (Next c)

> instance (FreshVar v x, FreshVar t x', MaxVar x x' y) => 
>          FreshVar (L v t) y

> instance (FreshVar t x, FreshVar t' x', MaxVar x x' y) =>
>          FreshVar (A t t') y

Some utility classes and types.

> data T = T
> data F = F

> class Or x y z | x y -> z
> instance Or F F F
> instance Or T F T
> instance Or F T T
> instance Or T T T

> class Chose x y z t | x y z -> t
> instance Chose T y z y
> instance Chose F y z z

> class SameVar x y z | x y -> z
> instance SameVar X X T
> instance SameVar X (Next x) F
> instance SameVar (Next x) X F
> instance SameVar x y z => SameVar (Next x) (Next y) z

This will be useful...

> instance SameVar X (A x y) F
> instance SameVar (Next x) (A x y) F
> instance SameVar X (L x y) F
> instance SameVar (Next x) (L x y) F

> class FirstOrSecondPlus a b c d | a b c -> d
> instance FirstOrSecondPlus T b c b
> instance FirstOrSecondPlus F b c (Next c)

Substitutions.

> class Subst var forTerm inTerm result tryAgain |
>         var forTerm inTerm -> result tryAgain where
>   subst :: var -> forTerm -> inTerm -> (result, tryAgain)
>   subst = undefined

Substitute a variable.

> instance Subst X forTerm X forTerm T
> instance Subst (Next x) forTerm X X F
> instance Subst X forTerm (Next x) (Next x) F
> instance (Subst x forTerm y result tryAgain,
>           FirstOrSecondPlus tryAgain result y result') =>
>          Subst (Next x) forTerm (Next y) result' tryAgain

> instance (Subst var forTerm inTerm1 result1 tryAgain1,
>           Subst var forTerm inTerm2 result2 tryAgain2,
>           Or tryAgain1 tryAgain2 tryAgain) =>
>          Subst var forTerm (A inTerm1 inTerm2) (A result1 result2) tryAgain

Utility rule.

> class SubstIfNot doit var forTerm inTerm result tryAgain |
>       doit var forTerm inTerm -> result tryAgain
> instance SubstIfNot T var forTerm inTerm inTerm T
> instance Subst var forTerm inTerm result tryAgain =>
>          SubstIfNot F var forTerm inTerm result tryAgain

Oi! Alpha-conversion.

> instance (FreshVar forTerm fresh1,
>           FreshVar inTerm fresh2,
>           FreshVar var' fresh3,
>           MaxVar fresh1 fresh2 fresh4,
>           MaxVar fresh3 fresh4 newFresh,
>           Subst var' newFresh inTerm result ignore,
>           Subst var forTerm result result' tryAgain) =>
>          Subst var forTerm (L var' inTerm) (L newFresh result') tryAgain

Now do reductions.

> class Reduce e e' tryAgain | e -> e' tryAgain where
>   reduce :: e -> (e', tryAgain)
>   reduce = undefined

Reduce variable to itself.

> instance Reduce X X F
> instance Reduce (Next x) (Next x) F

Reduce lambda abstraction.

> instance Reduce y y' tryAgain => Reduce (L x y) (L x y') tryAgain

Application.

> class Apply fun arg result tryAgain | fun arg -> result tryAgain

Apply variable.

> instance (Reduce y y' tryAgain) => Apply X y (A X y') tryAgain

Apply lambda abstraction : eta or beta?

> instance (SameVar x arg same,
>           SubstIfNot same x arg fun result tryAgain,
>           Chose same fun result result') =>
>          Apply (L x fun) arg result' tryAgain

Another utility rule.

> class ReduceIfNot tryit e e' tryAgain | tryit e -> e' tryAgain
> instance ReduceIfNot T e e F
> instance Reduce e e' tryAgain => ReduceIfNot F e e' tryAgain

Apply application.

> instance (Apply x y axy xTryAgain,
>           ReduceIfNot xTryAgain z rz tryAgain) =>
>          Apply (A x y) z (A axy rz) tryAgain

Reduce application.

> instance Apply x y result tryAgain =>
>          Reduce (A x y) result tryAgain

Loop!

> class ReduceLoop loop e e' | loop e -> e'

This instance is undecidable!

> instance ReduceLoop F e e
> instance (Reduce e e' tryAgain,
>           ReduceLoop tryAgain e' e'') => 
>          ReduceLoop T e e''

> class Eval e e' | e -> e' where
>   eval :: e -> e'
>   eval = undefined

This one is flagged as undecidable as well.

> instance ReduceLoop T e e' => Eval e e'

Example: evaluate pairs.

> instance (Subst var forTerm a a' aTryAgain,
>           Subst var forTerm b b' bTryAgain',
>           Or aTryAgain bTryAgain' tryAgain) =>
>          Subst var forTerm (a,b) (a', b') tryAgain

> instance (Reduce a a' aTryAgain,
>           ReduceIfNot aTryAgain b b' tryAgain) =>
>          Reduce (a,b) (a',b') tryAgain
