Lambda the Ultimate

Why do you need recursive types? Maybe it would be more useful to use one of the already well-documented state transition machines such as TIM, G-Machine, and STG

 data Un =
    Var Un
  | Lam (Un -> Un)
  | App Un Un
 
 eval (Var v) = Var v
 eval (Lam b) = Lam b
 eval (App m n) = eval m * n
  where Lam b * n = eval (b n)
        m * n = App m n

Recursive types are needed because the untyped type is really U->U, where U is the untyped type. An example of something that causes a problem is (\x.x x).

I'll try the code based on the shortest beta-normalizer and test its efficiency. I think it is similar to what Tromp used in his interpreter, which was not that fast, but maybe the compiler can make it efficient. Might take me a while to post results, I am a Haskell newbie.

Thanks both for your advice, if it isn't fast I'll try a lower level machine next.

PLT Scheme and its Lazy Scheme module.

After learning some Haskell I made an interpreter based on the shortest beta normalizer that vicky posted. But instead of converting it back into an AST I convert it directly to the output string. I benchmarked it using the prime number printer from lazy k, s, k, and i are just defined as lambda expressions at the top then rest of code can be used as is. To print out the first 3000 characters it took 64 seconds, much faster than I thought it would be, whereas with the lazy-k interpreter it takes 42 seconds. This is plenty fast since the lazy-k interpreter is really efficient. Normally I would run a size optimizer on the source first (since it is for golf after all), that took the time down to 30 seconds (it just looks to make applications that result in shorter code).

Thanks for your help and patience. I should have a web page up soon with a tutorial and tools for golfing. Although nothing new and interesting about the language (it is just a rip off of Tromp's), mainly a toy for learning functional programming which it seems everyone here already knows :)

John Smith: Hmm sounds like a good idea, I'll stick with the Haskell method for now though.

Philippa Cowderoy: Is your method of fusing the AST away just like using the eval function (from the shortest beta normalizer) on it?

Edit: If instead of interpreting the source, converting it to Haskell and letting the compiler work its magic, resulted in 4 second runtime (16 seconds for non size optimized version). This is even better, but I would have thought it would be just as fast for non size optimized version, I guess ghc doesn't look for those types of optimizations.

Edit#2: Actually the standard lazy-k isn't that fast, I was comparing speed to the wrong interpreter, the fast one is here (and probably a good reference for making a fast untyped lambda calculus interpreter).