Adventures with the untyped lambda calculus

Question

We occasionally have people ask about implementing the untyped lambda calculus in Haskell. [Naturally, I now cannot find any of these questions, but I'm sure I've seen them!] Just for giggles, I thought I'd spend some time playing with this.

It's trivial enough to do something like

i = \ x -> x
k = \ x y -> x
s = \ f g x -> (f x) (g x)

This works perfectly. However, as soon as you try to do something like

s i i

the type-checker rightly complains about an infinite type. Basically everything in the untyped lambda calculus is a function — which essentially means all functions have infinite arity. But Haskell only allows functions of finite arity. (Because, really, why would you want infinite arity?)

Well, it turns out we can easily side-step that limitation:

data Term = T (Term -> Term)

T f ! x = f x

i = T $ \ x -> x
k = T $ \ x -> T $ \ y -> x
s = T $ \ f -> T $ \ g -> T $ \ x -> (f ! x) ! (g ! x)

This works perfectly, and allows arbitrary lambda expressions to be constructed and executed. For example, we can easily build a function to turn an Int into a Church numeral:

zero = k ! i
succ = s ! (s ! (k ! s) ! k)

encode 0 = zero
encode n = succ ! (encode $ n-1)

Again, this works perfectly.

Now write a decode function.

…yeah, good luck with that! The trouble is, we can create arbitrary lambda terms, but we can't inspect them in any way. So we need to add some way to do that.

---

So far, the best idea I've come up with is this:

data Term x = F (Term x -> Term x) | R (Term x -> x)

F f ! x =            f x
R f ! x = R $ \ _ -> f x

out :: Term x -> x
out (R f) = f (error "mu")
out (F _) =   (error "nu")

i = F $ \ x -> x
k = F $ \ x -> F $ \ y -> x
s = F $ \ f -> F $ \ g -> F $ \ x -> (f ! x) ! (g ! x)

I can now do something like

decode :: Term Int -> Int
decode ti = out $ ti ! R (\ tx -> 1 + out tx) ! R (\ tx -> 0)

This works great for Church Bools and Church numerals.

---

Things start to go horribly wrong when I start trying to do anything high-order. Having thrown away all the type information to implement the untyped lambda calculus, I'm now struggling to convince the type checker to let me do what I want to do.

This works:

something = F $ \ x -> F $ \ n -> F $ \ s -> s ! x
nothing   =            F $ \ n -> F $ \ s -> n

encode :: Maybe x -> Term x
encode (Nothing) = nothing
encode (Just  x) = something ! x

This does not:

decode :: Term x -> Maybe (Term x)
decode tmx = out $ tmx ! R (\ tx -> Nothing) ! R (\ tx -> Just tx)

I've tried a dozen slight variations on this; none of them type-check. It's not that I don't understand why it fails, but rather than I can't figure out any way for it to succeed. (Most particularly, R Just is clearly ill-typed.)

It's almost as if I want a function forall x y. Term x -> Term y. Because, for pure untyped terms, this should always be possible. It's only terms involving R where that won't work. But I can't figure out how to phrase that in the Haskell type system.

(For example, try changing the type of F to forall x. Term x -> Term x. Now the definition of k is ill-typed, since the inner F $ \ y -> x cannot actually return any type, but only the [now fixed] type of x.)

Any anybody smarter than me have a better idea?

Answer 1

OK, I've found a solution:

The code above has Term x, parameterised by the result type for R. Instead of doing that (and freaking out the type checker), construct some type Value that can represent every result type you will ever want to return. Now we have

data Term = F (Term -> Term) | R (Term -> Value)

Having collapsed all possible result types into a single opaque Value type, we can do our work.

Concretely, the type I chose is

data Value = V Int [Term]

So a Value is an Int representing an ADT value constructor, followed by one Term for each field of that constructor. With this definition, we can finally do

decode :: Term -> Maybe Term
decode tmx =
  case tmx ! R (\ _ -> V 0 []) ! R (\ tx -> V 1 [tx]) of
    V 0 []   -> Nothing
    V 1 [tx] -> Just tx
    _        -> error "not a Maybe"

Similarly, you can encode and decode lists like so:

null =                        F $ \ n -> F $ \ c -> n
cons = F $ \ x -> n $ \ xs -> F $ \ n -> F $ \ c -> c ! x ! xs

encode :: [Term] -> Term
encode (  []) = null
encode (x:xs) = cons ! x ! encode xs

decode :: Term -> [Term]
decode txs =
  case out $ txs ! R (\ txs -> V 0 []) ! F (\ tx -> R $ \ txs -> V 1 [tx, txs]) of
    V 0 []        -> []
    V 1 [tx, txs] -> tx : decode txs
    _             -> error "not a list"

Of course, you have to guess which decode function(s) you need to apply. But that's the untyped lambda calculus for you!

Answer 2

This is not an answer, but commenting is too restrictive.

R Just is ill-typed, because its type is recursive, but we can always wrap this type-level recursion in a data type:

data Fix2 g f = Fix2 { run :: g (f (Fix2 g f)) }

Fix2 can be represented in terms of Fix and composition of type constructors, but I don't want to complicate things.

Then we can define decode as

decode :: Term (Fix2 Maybe Term) -> Maybe (Term (Fix2 Maybe Term))
decode tmx = run $ out $ tmx ! R (Fix2 . const Nothing) ! R (Fix2 . Just)

Some tests:

isSomething :: Term (Fix2 Maybe Term) -> Bool
isSomething = isJust . decode

i = F id

main = do
    print $ isSomething (something ! i) -- True
    print $ isSomething  nothing        -- False

But clearly Term (Fix2 Maybe Term) is far from Term a.