sjs

Well it has been a while since my last post. I’ll try not to do that frequently. Anyhow, on to the good stuff.

I’ve been developing a Scheme interpreter in Haskell called ElSchemo. It started from Jonathan’s excellent Haskell tutorial which I followed in order to learn both Haskell and Scheme. Basically that means the code here is for me to get some feedback as much as to show others how to do this kind of stuff. This may not be too interesting if you haven’t at least browsed the tutorial.

I’m going to cover 3 new special forms: and, or, and cond. I promised to cover the let family of special forms this time around but methinks this is long enough as it is. My sincere apologies if you’ve been waiting for those.

Update: I’ve cleaned the code up a little bit by having LispNum derive Eq, Ord and Show.

NB: My Scheme interpreter is based on Jonathan Tang’s Write Yourself a Scheme in 48 hours Haskell tutorial. Not all of this makes sense outside that context, and the context of my previous posts on the subject.

My scheme interpreter has been christened ElSchemo, since it was sorely in need of a better name than “my Scheme interpreter”. It’s also seen far too much of my time and sports jazzy new features. I’ll probably post the full code up here sooner or later, including my stdlib.scm and misp slightly modified to run with ElSchemo’s limited vocabulary (namely the lack of define-syntax).

But that will be for another day, because today I want to talk about implementing floating point numbers, from parsing to operating on them.

It’s been a little while since I wrote about Haskell and the Scheme interpreter I’ve been using to learn and play with both Haskell and Scheme. I finished the tutorial and got myself a working Scheme interpreter and indeed it has been fun to use it for trying out little things now and then. (Normally I would use Emacs or Dr. Scheme for that sort of thing.) There certainly are interesting things to try floating around da intranet. And also things to read and learn from, such as misp (via Moonbase).

I’m going to describe two new features of my Scheme in this post. The second one is more interesting and was more fun to implement (cond).

Parsing Scheme integers

Last time I left off at parsing R5RS compliant numbers, which is exercise 3.3.4 if you’re following along the tutorial. Only integers in binary, octal, decimal, and hexadecimal are parsed right now. The syntaxes for those are #b101010, #o52, 42 (or #d42), and #x2a, respectively. To parse these we use the readOct, readDec, readHex, and readInt functions provided by the Numeric module, and import them thusly:

import Numeric (readOct, readDec, readHex, readInt)

In order to parse binary digits we need to write a few short functions to help us out. For some reason I couldn’t find binDigit, isBinDigit and readBin in their respective modules but luckily they’re trivial to implement. The first two are self-explanatory, as is the third if you look at the implementation of its relatives for larger bases. In a nutshell readBin says to: “read an integer in base 2, validating digits with isBinDigit.”

-- parse a binary digit, analagous to decDigit, octDigit, hexDigit
binDigit :: Parser Char
binDigit = oneOf "01" 

-- analogous to isDigit, isOctdigit, isHexDigit
isBinDigit :: Char -> Bool
isBinDigit c = (c == '0' || c == '1')

-- analogous to readDec, readOct, readHex
readBin :: (Integral a) => ReadS a
readBin = readInt 2 isBinDigit digitToInt

The next step is to augment parseNumber so that it can handle R5RS numbers in addition to regular decimal numbers. To refresh, the tutorial’s parseNumber function looks like this:

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

Three more lines in this function will give us a decent starting point:

parseNumber = do char '#'
                 base <- oneOf "bdox" 
                 parseDigits base
           <|> (many1 digit >>= return . Number . read)

Translation: First look for an R5RS style base, and if found call parseDigits with the given base to do the dirty work. If that fails then fall back to parsing a boring old string of decimal digits.

That brings us to actually parsing the numbers. parseDigits is simple, but there might be a more Haskell-y way of doing this.

-- Parse a string of digits in the given base.
parseDigits :: Char -> Parser LispVal
parseDigits base = do digits <- many1 d
                      return . Number . fst . head . f $ digits
                      where f = case base of
                                  'b' -> readBin
                                  'd' -> readDec
                                  'o' -> readOct
                                  'x' -> readHex
                            d = case base of
                                  'b' -> binDigit
                                  'd' -> digit
                                  'o' -> octDigit
                                  'x' -> hexDigit

The trickiest part of all this was figuring out how to use the various readFoo functions properly. They return a list of pairs so head grabs the first pair and fst grabs the first element of the pair. Once I had that straight it was smooth sailing. Having done this, parsing R5RS characters (#\a, #\Z, #\?, ...) is a breeze so I won’t bore you with that.

The cond function

It still takes me some time to knit together meaningful Haskell statements. Tonight I spent said time cobbling together an implementation of cond as a new special form. Have a look at the code. The explanation follows.

1
2
3
4
5
6
7
8
9

eval env (List (Atom "cond" : List (Atom "else" : exprs) : [])) =
    liftM last $ mapM (eval env) exprs
eval env (List (Atom "cond" : List (pred : conseq) : rest)) = 
    do result <- eval env $ pred
       case result of
         Bool False -> case rest of
                         [] -> return $ List []
                         _ -> eval env $ List (Atom "cond" : rest)
         _ -> liftM last $ mapM (eval env) conseq

• Lines 1-2: Handle else clauses by evaluating the given expression(s), returning the last result. It must come first or it’s overlapped by the next pattern.
• Line 3: Evaluate a cond by splitting the first condition into predicate and consequence, tuck the remaining conditions into rest for later.
• Line 4: Evaluate pred
• Line 5: and if the result is:
• Line 6: #f then look at the rest of the conditions.
• Line 7: If there are no more conditions return the empty list.
• Line 8: Otherwise call ourselves recursively with the remaining conditions.
• Line 9: Anything other than #f is considered true and causes conseq to be evaluated and returned. Like else, conseq can be a sequence of expressions.

So far my Scheme weighs in at 621 lines, 200 more than the tutorial’s final code listing. Hopefully I’ll keep adding things on my TODO list and it will grow a little bit more. Now that I have cond it will be more fun to expand my stdlib.scm as well.

Basically, a monad is a way of saying “there’s some extra information attached to this value, which most functions don’t need to worry about”. In this example, the “extra information” is the fact that this action performs IO, and the basic value is nothing, represented as “()”. Monadic values are often called “actions”, because the easiest way to think about the IO monad is a sequencing of actions that each might affect the outside world.

I really like this tutorial. I’m only on part 3.3 of 12, parsing, but I’m new to Haskell so I’m learning left, right & centre. The exercises are taking me hours of reading and experimenting, and it’s lots of fun! ghc’s errors are usually quite helpful and of course ghci is a big help as well.

I’m going to explain one of the exercises because converting between the various syntax for dealing with monads wasn’t plainly obvious to me. Perhaps I wasn’t paying enough attention to the docs I read. In any case if you’re interested in Haskell at all, I recommend the tutorial and if you’re stuck on exercise 3.3.1 like I was then come on back here. Whether you’re following the tutorial or not the point of this post should stand on its own with a basic knowledge of Haskell.

Last night I rewrote parseNumber using do and >>= (bind) notations (ex. 3.3.1). Here’s parseNumber using the liftM method given in the tutorial:

parseNumber :: Parser LispVal
parseNumber :: liftM (Number . read) $ many1 digit

Okay that’s pretty simple right? Let’s break it down, first looking at the right-hand side of the $ operator, then the left.

• many1 digit reads as many decimal digits as it can.

• Number . read is a function composition just like we’re used to using in math. It applies read to its argument, then applies Number to that result.

• liftM is concisely and effectively defined elsewhere, and I’ll borrow their description:

liftM f m lets a non-monadic function f operate on the contents of monad m

liftM’s type is also quite telling: liftM :: (Monad m) => (a -> b) -> (m a -> m b)

In a nutshell liftM turns a function from a to b to a function from a monad containing a to a monad containing b.

That results in a function on the left-hand side of $, which operates on and outputs a monad. The content of the input monad is a String. The content of the output monad is a LispVal (defined earlier in the tutorial). Specifically it is a Number.

The $ acts similar to a pipe in $FAVOURITE_SHELL, and is right associative which means the expression on the right is passed to the expression (function) on the left. It’s exactly the same as (liftM (Number . read)) (many1 digit) except it looks cleaner. If you know LISP or Scheme (sadly I do not) then it’s analogous to the apply function.

So how does a Haskell newbie go about re-writing that using other notations which haven’t even been explained in the tutorial? Clearly one must search the web and read as much as they can until they understand enough to figure it out (which is one thing I like about the tutorial). If you’re lazy like me, here are 3 equivalent pieces of code for you to chew on. parseNumber’s type is Parser LispVal (Parser is a monad).

parseNumber -> liftM (Number . read) $ many1 digit

parseNumber -> do digits <- many1 digit
                  return $ (Number . read) digits

If you’re thinking “Hey a return, I know that one!” then the devious masterminds behind Haskell are certainly laughing evilly right now. return simply wraps up it’s argument in a monad of some sort. In this case it’s the Parser monad. The return part may seem strange at first. Since many1 digit yields a monad why do we need to wrap anything? The answer is that using <- causes digits to contain a String, stripped out of the monad which resulted from many1 digit. Hence we no longer use liftM to make (Number . read) monads, and instead need to use return to properly wrap it back up in a monad.

In other words liftM eliminates the need to explicitly re-monadize the contents as is necessary using do.

parseNumber -> many1 digit >>= \digits ->
               return $ (Number . read) digits

At this point I don’t think this warrants much of an explanation. The syntactic sugar provided by do should be pretty obvious. Just in case it’s not, >>= passes the contents of its left argument (a monad) to the function on its right. Once again return is needed to wrap up the result and send it on its way.

When I first read about Haskell I was overwhelmed by not knowing anything, and not being able to apply my previous knowledge of programming to anything in Haskell. One piece of syntax at a time I am slowly able to understand more of the Haskell found in the wild.

I’m currently working on ex. 3.3.4, which is parsing R5RS compliant numbers (e.g. #o12345670, #xff, #d987). I’ll probably write something about that once I figure it out, but in the meantime if you have any hints I’m all ears.

Update #1: I should do more proof-reading if I’m going to try and explain things. I made some changes in wording.

While reading a Haskell tutorial I came across the following code for defining the Fibonacci numbers:

fib = 1 : 1 : [ a + b | (a, b) <- zip fib (tail fib) ]

After reading it a few times and understanding how it works I couldn’t help but think how beautiful it is. I don’t mean that it’s aesthetically pleasing to me; the beautiful part is the meaning and simplicity. Lazy evaluation is sweet.

Haskell is the most challenging real language I have tried to wrap my head around. I haven’t done much with any functional languages yet but they are truly fascinating. I’m beginning to understand monads¹ but I’m quite sure I don’t see the whole picture yet.

Erlang looks like it may be more suited to real world apps so I would like to learn that some time. The pragmatic guys have a book on Erlang in the works, and I love every book of theirs which I have read.

Going deeper down the functional rabbit-hole you’ll find things like this polyglot quine, which absolutely blows my mind. I used to be impressed by the JAPH sigs or some of the various obfuscated contest winners but that first one definitely cleans the rest up with a perfect 10 in geekiness.

[1] The following links have all been helpful while trying to wrap my head around monads.

• A Gentle Introduction to Haskell (link is directly to chapter 9)
• What the hell are Monads?
• Monads on WikiBooks
• Monads for the Working Haskell Programmer

Last summer I did some reading about Haskell and read some intros on using it. I never got into it though as I was busy working and learning other things at the time. Today I was reminded about Haskell and decided to really put an effort into learning the basics and coding a few small programs.

Classes in Haskell are very interesting, and fairly different from classes I’m used to in Ruby or Java. One feature about them that struck me as particularly cool is that you can define methods in terms of each other, and if the minimum requirements are met then the others are automatically defined in terms of the provided methods. It’s genius I tell you, but my explanation is lacking so check the linked Wikibook at the beginning of this paragraph to grasp what I’m talking about. When you get back the rest of this should make sense…