Write Yourself a Haskell in Lisp

tikhonj 13 years ago |

If you're interested in something similar but a little more theoretical, take a look at "Simply Easy"[1], a little paper on implementing a couple of variations on the lambda calculus. The main idea is to demonstrate how to evaluate a dependently typed language.

It starts by looking at how to evaluate the simply typed lambda calculus and then going from that to a dependently typed lambda calculus. Surprisingly, the transformation is not all that complicated!

The actual code is in Haskell.

[1]: http://strictlypositive.org/Easy.pdf

saosebastiao 13 years ago |

Cool. Does it qualify as some sort of mutual recursion if you use haskell to build a lisp which builds haskell?

m_for_monkey 13 years ago | |

You can use this tutorial for the first step if you want to do it: Write Yourself a Scheme in 48 Hours by Jonathan Tang. http://jonathan.tang.name/files/scheme_in_48/tutorial/overvi...

robinh 13 years ago | | |

It would be interesting to see how many languages you could nest before the interpreter becomes too slow to be of use.

Patient0 13 years ago | | |

I've always thought that this would be a better definition of what a "compiler" is vs what an "interpreter" is:

A compiler, if asked to "execute" itself a million times will generate code that is still reasonably fast.

An interpreter, if asked to "execute" itself a million times, will generate code that is a million times slower.

robinh 13 years ago | | |

Theoretically, one could write an interpreter specifically for the purpose of nesting other interpreters, which would then (nearly) remove itself from memory as it transfers control to the second interpreter, but I know I'm not quite insane enough to start working on such a thing.

pekk 13 years ago | | |

What would be interesting about it?

mayneack 13 years ago | | |

seeing how many languages you could nest before the interpreter becomes too slow to be of use.

Quiark 13 years ago |

Hehe, I love this. I have been doing something similar, writing a compiler of Scheme-like language to x86 in Haskell.

https://bitbucket.org/quiark/hsc

The whole purpose of that mental gymnastics was to learn x86 assembly while practicing my Haskell ;)

huhsamovar 13 years ago |

Another 'X written in Y' post. Awesome.

I think I'll save myself the wasted time and just use X from the get-go.

cdmoyer 13 years ago | |

The point isn't to replace X. It's to learn more about X and Y.

emillon 13 years ago | |

Well, the semantics of a lazy language are a bit different than usual. While I agree that pages of s-expressions are hard to feel, seeing the graph reduction algorithm on a few examples was quite refreshing.

Raphael 13 years ago |

Make the Yule-tide gay.