Why Haskell?

So how long does it take for a completely fledgling Haskell programmer to implement a weird language? 2 nights.

 

Its pretty amazing if you think about it – and it fun and not stressful as well. If I did as much in C or Cpp it would have been significantly more stressful and would have take a over a weekend for sure. And even after that it wouldn’t be as flexible as this is.

 

In some sense, in my current limited opinion, Haskell is to Scheme what Ruby is to C++. To add to it, it is purely functional than scheme, is lazy, comes with A REAL library, allows for pattern matching and discriminated unions etc… the goodness goes on – as matter of fact, it can even pretend to be imperative for a bit. Also, GHC generates actual Win32 exes that I can run. If you are a languages person you might think it’s a moot point, but for someone who likes to build tools and wants to sometimes share them with his (less inclined) friends, this is essential.

 

So I think Haskell is going to takes its place in my bag of tools. The only thing I really miss from Scheme land are macros. I wish Haskell had macros – better, I wish Haskell had multistage evaluation.

 

Being a almost ‘pure’ imperative programmer when I joined college, Prof Dan Friedman’s Programming languages class hurt my head really badly. And I was coming to terms with functional programming.

 

Last semester I also took a class with Prof Amr Sabry – Quantum computing – and this was my first real introduction to Haskell. I am working with him this semester and of late I have been trying to understand Monads. Its one thing to have working knowledge of a concept, and its quiet another to formally study it. Monads hurt like few other things hurt before – and the fact is that it makes you look at imperative programming in this totally other way.

 

So that’s the context for why this is in Haskell. The blog entry is really about this little language I wrote in .. in all fairness a little more than a late night. And I haven’t used the parser generator or other tools before this.

 

Yield Language 1.0

So whats the language like? Well, you’re not going to want to use it at all. But all the same it is the lambda calculus with the following additions (some of which take away its purity) – yield (with all the right behavior in place), if-then-else, numbers (+, -, ==), strings (+, ==). In other words, it’s a simple higher order language with strings and numbers and fancy control flow operator called yield, which is the only “impure” part of the language.

 

To support yield I introduce a funny tagging operator I call ‘pi’ to tag a sub-expression that can yield. A pi-expression can be called like a normal application, or can be used as a coroutine using co, next and run.

 

The actual internal implementation is what is best described as “stackless”.

 

 

f = \x ->

  ((("x = " + x) + ", ") +

  if (x == 0)

    "zero"

  else

    "not zero");

 

(f 10)

 

This evaluates and returns “x = 10, not zero”

 

Basic syntax

e =     \x->e

| x

| e1 e2

| if e1 e2 else e3

| (e1 + e2)

| (e1 – e2)

| (e1 == e2)

| <num>

| <string>

| x = e1; e2

 

The above syntactic categories as basically all pure. The last rule is a let. There is no fixed point operator and you will need to add one of your own to do recursion. Evaluation is strict, applicative order. The following are the extensions for yield support.

 

      | pi e

      | yield e

      | co e

      | next e1 e2

      | run e1 as x1 x2 -> e2 or x3 -> e3

 

Some more examples, assume that we have an applicative order Y combinator called “fix”.

-- Applicative Y combinator

fix = \f -> ((\x -> (f \y -> ((x x) y)))

          (\x -> (f \y -> ((x x) y))));

 

Here  is a relatively simple function that takes a number and yields as many times. I have used the fixed point operator so that I can loop inside the pi block.

-- An iterator that yields 'x' times

iter = \x ->

  (pi  (((fix \loop -> \x -> \s ->

                  if (x == 0)  s

                  else v = yield x;

                        ((loop (x-1)) (v+s)))

            x)

      0));

 

One can call this function in two ways – simple invocation –

((iter 1000) \x->(x+x))

 

Or using the coroutine-like behavior, that is sometimes called external-iterators or generators.

call = (fix  (\call -> \c ->

                  run c

                  as (x1 x2) -> (call (next x2 (x1 + x1)))

                  or x1 -> x1));

 

 

v1 = (call (co (iter 1000)));

 

So one can save the following code into a file and execute it from command line using the command –

langy.exe < filename.txt

 

[update: made some simple syntactic niceties to the language]

 

-- Applicative Y combinator

fix = \f -> (\x -> (f \y -> (x x y))

             \x -> (f \y -> (x x y)));

 

-- An iterator that yields 'x' times

iter = \x ->

       (pi  ((fix \ loop x s ->

              if (x == 0)  s

              else v = yield x;

              (loop (x-1) (v+s)))

             x 0));

       

                                  

-- Call will invoke an iterator any number of times

-- At each point it thunks the return value and then uses that as the

-- next value paramter.

call = (fix  \ loop c ->

        run c

        as x1 x2 -> (loop next x2 (x1 + x1))

        or x1 -> x1);

                        

 

v1 = (call co (iter 1000));

                      

v2 = (iter 1000 \x->(x+x));

                      

("Values are " + v1 + ", " + v2)

 

And this outputs –

"Values are 1001000, 1001000"

 

Downloads