Lambda the Ultimate

...have been done a million times in a hundreds of different programming languages. It's one of the real beauties of Scheme that building an Eval/Apply engine can be done by most any hack (myself).

Haskell is a much more involved language with only a handful of compilers available - and those are rather large ticket items. For the most part, Scheme interpreters (of the type being discussed) serve limited purposes - either didactic or special purpose DSLs. It's unlikely that a Haskell compiler could be written in 48 hours - the code would be rather large for the mere purpose of instructional aid. And for DSLs, Scheme has much easier ways than to embed Haskell.

Actually, what would be nicer is to implement Haskell in Haskell, much as HaMLet implements Standard ML. A meta-circular interpreter is useful for experimenting with a language. I'm not sure if this has been done for Haskell?

Turing completeness says it's possible. What kind of technical hurdles did you have in mind?

As a proof-by-implementation-in-a-related-language, Yale Haskell was implemented in Common Lisp. Here's an announcement of v2.1 from 1994:

The Yale Haskell systems is available on a number of popular systems;
binaries are provided for Sun/Sparc and Macintosh, but it is possible to
build the system on virtually any system that runs one of a number of
Common Lisp implementations.

Not sure where the source can be found these days.

I remember from reading the paper detailing the history or Haskell that there was at least one compiler which compiled Haskell to Common Lisp, with appropriate type tags for optimization.

Anton, I definitely will check out that link about Yale Haskell, thanks!

I realize that the Turing completeness of both languages allows them to be implemented in each other. I probably chose poor wording when asking about 'technical' hurdles.

I guess what I'm really wondering is it seems that its trivial to bootstrap a Scheme (dynamic typing*,eager eval) in Haskell (static typing*, lazy eval), is it that much more difficult to do the reverse (perhaps not even Haskell, how about just a static-typed, lazy Scheme)?

*If I have identified these type-systems erroneously, mea culpa!

There's no technical obstacle, except that Haskell is a really big language. There's just gobs and gobs of stuff you have to do before you have a working Haskell type-checker. By way of comparison, SML (with modules) is medium-sized, and without modules core ML is small. Scheme is tiny.

I have been having trouble forming my question, so I must apologize that I believe my first post was done somewhat prematurely.

The core that I was trying to get at was this. Presuming you had a virtual machine which could only execute valid Scheme programs; if you had a compiler for this machine which transformed a Haskell program into its Scheme equivalent, would the compiled program retain the type safety that Haskell provides?

And the answer, which I found after reading more on Haskell, and which neelk points out, is that the answer would be yes. All due to the Type Checker. This was the bit I was leaving out in my thought exercises.

Ehud, I think you had it right saying that I was talking closer to embedding than implementing.

Perhaps Scheme can be thought of as read-eval-print, and Haskell as read-check-eval-print?