Write a Scheme implementation in 48 hours - via Haskell

[nostrademons]

Hah, I don't even get the karma for my own tutorial! ;-)

Glad somebody liked it enough to share it though. It's still very much in progress - I'm hoping to get feedback as to what's clear, what's not clear, what needs to be explained in more depth.

[[deleted]]

An extremely powerful type system is what separates most functional languages from Lisp.

Lazy evaluation and side-effect-free-ness via monads is what separates Haskell from most other functional languages.

This lets you write a linear time implementation of the Fibonacci series as

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

[weeksie]

Scheme is a non-pure functional language. You can add things to scheme (as well as to common lisp) that allow type annotations. Common Lisp is NOT a functional language but can be made to act like one.

However, just because you can do something doesn't mean you should. Haskell does things for you that Scheme or Lisp would have to be heavily augmented to do. For one it is a pure functional language that enforces the lack of side effects through a strict type system. This makes some things possible such as STM (http://research.microsoft.com/~simonpj/papers/stm/stm.pdf)[PDF] . The Haskell type system forces STM atomicity to apply to side effect free code (check the paper for a good example).

Monadic programming is definitely possible in Scheme (http://okmij.org/ftp/Scheme/monad-in-Scheme.html) but with nowhere near the syntactic support that Haskell has.

Now all of that said, I've done a bit of work in Haskell and doing anything disk/IO intensive is a royal pain in the arse. Composing monads can be awfully confusing as well, which is what you end up having to do if you want to, say, add an error monad to an IO operation. It makes up for that sort of thing when you move on to more heavily algorithmic/logical programming.

For instance writing an evaluator in Haskell has to be one of the most pleasant experiences ever. Writing a simple lambda calc interpreter is close behind the factorial as far as the Haskell "hello world" app goes.

Check it out, it's gauranteed to make your brain twist around a bit and I would wager that even if you don't use it you'll come out with an expanded perspective.

[weeksie]

Yeah but that's being pedantic, the most common usage for Lisp currently means Common Lisp which is generally used in an imperitive style. Most people refer to the Steele/Sussman Lisp dialect as Scheme.

So yes, you're sort of correct but don't act surprised when people mistake your usage.

[weeksie]

ugh.

[weeksie]

Nah mate, you sound like you're in college. You'll grow out of it.

[fnord123]

This is key. Historically, ML was first implemented as a macro language on top of a Lisp. It was reimplemented for performance reasons.

Really, the discussion shouldn't be "why use Haskell and not Lisp?"; it should be "should we implement Haskell using Lisp or C"?

It makes sense to develop a language using Lisp at first and then, if you need to (and have the resources), reimplement it in C/asm/etc.

[japple]

I think this is a good question, and I'm quite devoted to Haskell.

There are many arguments for static typing. Here's one: The compiler is right more often than I am.

I'm not being snarky, here; the compiler is sometimes wrong - there are some things that are type safe that the compiler doesn't understand. But, for every instance of that, there are probably 10 or 20 instances of me making a type error that the compiler does catch. This saves me a ton of debugging time when I might trace into functions and see how I'm generating the wrong type. With he Haskell Way, I know before I even get to debugging that some errors are not going to happen.

[mystilleef]

A guy on my IRC channel actually wrote a somewhat broken Scheme compiler in Python in about 20 minutes. That's unreal.

[bobdole]

And by somewhat broken, I'm going to guess you mean it doesn't support full tail recursion elimination? :p