May | JUN | JUL
| 16 |
2006 | 2007 | 2008

12 captures 16 Jun 07 - 14 Apr 09 |

Close Help

# sjs

## geeky ramblings

## More Scheming with Haskell 2

Posted by sjs
on Thursday, June 14

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).

### Pasing 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.

- Tags: coding haskell scheme
- Meta: 2 comments, permalink

##### Comments

Leave a response

1. whoopee – June 14, 2007 @ 08:57 AM

   thanks! just last night i was thinking – hmm, i have this haskell program that takes what i want to be an Integer from the command line – how do i enforce this? your post is relevant to these issues…thanks!

2. sjs – June 15, 2007 @ 09:39 AM

   Sure, it’s good to know that someone found something I said useful. :)

Comment

Name:

Email Address:

Website:

Comment: