Title: More Scheming with Haskell
Date: June 13, 2007
Timestamp: 1181783340
Author: sjs
Tags: coding, haskell, scheme
----

<p>It’s been a little while since I wrote about Haskell and the <a href="http://web.archive.org/web/20070616135646/http://sami.samhuri.net/2007/5/3/a-scheme-parser-in-haskell-part-1">Scheme interpreter</a> 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 <a href="http://web.archive.org/web/20070616135646/http://www.lshift.net/blog/2007/06/11/folds-and-continuation-passing-style">interesting things</a> to try floating around da intranet. And also things to read and learn from, such as <a href="http://web.archive.org/web/20070616135646/http://cubiclemuses.com/cm/blog/tags/Misp">misp</a> (via <a href="http://web.archive.org/web/20070616135646/http://moonbase.rydia.net/mental/blog/programming/misp-is-a-lisp">Moonbase</a>).</p>


	<p><em>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).</em></p>


	<h3>Pasing Scheme integers</h3>


	<p>Last time I left off at parsing <a href="http://web.archive.org/web/20070616135646/http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3.5"><span class="caps">R5RS</span> compliant numbers</a>, 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 <code>#b101010</code>, <code>#o52</code>, <code>42</code> (or <code>#d42</code>), and <code>#x2a</code>, respectively. To parse these we use the <code>readOct</code>, <code>readDec</code>, <code>readHex</code>, and <code>readInt</code> functions provided by the Numeric module, and import them thusly:</p>


<pre><code>import Numeric (readOct, readDec, readHex, readInt)</code></pre>

	<p>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 <code>binDigit</code>, <code>isBinDigit</code> and <code>readBin</code> 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 <a href="http://web.archive.org/web/20070616135646/http://www.cse.ogi.edu/~diatchki/MonadTransformers/pfe.cgi?Numeric">implementation</a> of its relatives for larger bases. In a nutshell <code>readBin</code> says to: “read an integer in base 2, validating digits with <code>isBinDigit</code>.”</p>


<pre><code>-- 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</code></pre>

	<p>The next step is to augment <code>parseNumber</code> so that it can handle <span class="caps">R5RS</span> numbers in addition to regular decimal numbers. To refresh, the tutorial’s <code>parseNumber</code> function looks like this:</p>


<pre><code>parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit</code></pre>

	<p>Three more lines in this function will give us a decent starting point:</p>


<pre><code>parseNumber = do char '#'
                 base <- oneof="oneOf" bdox="bdox" parsedigits="parseDigits" base="base"></-></code></pre>

	<p>Translation: First look for an <span class="caps">R5RS</span> style base, and if found call <code>parseDigits</code> with the given base to do the dirty work. If that fails then fall back to parsing a boring old string of decimal digits.</p>


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


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

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


	<h3>The cond function</h3>


	<p>It still takes me some time to knit together meaningful Haskell statements. Tonight I spent said time cobbling together an implementation of <a href="http://web.archive.org/web/20070616135646/http://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.5">cond</a> as a new special form. Have a look at the code. The explanation follows.</p>


<table class="CodeRay"><tr>
  <td class="line_numbers" title="click to toggle" onclick="with (this.firstChild.style) { display = (display == '') ? 'none' : '' }"><pre>1<tt>
</tt>2<tt>
</tt>3<tt>
</tt>4<tt>
</tt>5<tt>
</tt>6<tt>
</tt>7<tt>
</tt>8<tt>
</tt>9<tt>
</tt></pre></td>
  <td class="code"><pre ondblclick="with (this.style) { overflow = (overflow == 'auto' || overflow == '') ? 'visible' : 'auto' }">eval env (List (Atom "cond" : List (Atom "else" : exprs) : [])) =<tt>
</tt>    liftM last $ mapM (eval env) exprs<tt>
</tt>eval env (List (Atom "cond" : List (pred : conseq) : rest)) = <tt>
</tt>    do result &lt;- eval env $ pred<tt>
</tt>       case result of<tt>
</tt>         Bool False -&gt; case rest of<tt>
</tt>                         [] -&gt; return $ List []<tt>
</tt>                         _ -&gt; eval env $ List (Atom "cond" : rest)<tt>
</tt>         _ -&gt; liftM last $ mapM (eval env) conseq</pre></td>
</tr></table>


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


	<p>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 <span class="caps">TODO</span> list and it will grow a little bit more. Now that I have <code>cond</code> it will be more fun to expand my stdlib.scm as well.</p>
