<?php include 'HEADER.php'; ?>

<h1>Functional Programming (Lisp, Scheme, Clojure, etc.)</h1>
<p>Lisp is an old yet adaptable programming language with its roots in early artificial intelligence work. It's a very flexible language, though it's often closely associated with functional programming. The two most popular Lisp camps these days are Common Lisp (which is an ANSI standard that unified lots of earlier Lisp dialects) and Scheme (which is more of a pure/academic dialect heavily focused on functional programming and recursion). <a href="http://clojure.org/">Clojure</a> is a lisp-like language that compiles for the JVM, and can access Java's libraries.</p>

<h2>Basics</h2>
<p>Comments in Lisp, Scheme, and Clojure begin with a semi-colon (;).</p>
<p>Scheme files usually have the extension <code>.scm</code>. Lisp files might have the extension <code>.lisp</code> or <code>.lsp</code>. Clojure uses the file extension <code>.clj</code>.</p>
<p>A good multi-platform lisp is <a href="http://www.gnu.org/software/clisp/">clisp</a>, and a good scheme is <a href="http://www.gnu.org/software/guile/guile.html">guile</a>.</p>
<p>This is a <a href="http://hyperpolyglot.org/lisp">Rosetta Stone between lisp, scheme, and clojure</a>, with content like:</p>

<table style="border-color:black;border-style:solid;border-spacing:6px;border-width:1px;border-collapse:separate;">
<tr><th>Common Lisp</th><th>Scheme</th><th>Clojure</th>
<tr><td>(atom x)</td><td>(not (pair? x))</td><td>(not (list? x))</td></tr>
<tr><td>quote</td><td>quote</td><td>quote</td></tr>
<tr><td>eq, equal, =</td><td>eq?, equal?, =</td><td>=</td></tr>
<tr><td>car, first</td><td>car</td><td>first</td></tr>
<tr><td>cdr, rest</td><td>cdr</td><td>rest, next</td></tr>
<tr><td>cons</td><td>cons</td><td>cons</td></tr>
<tr><td>(lambda (x) (* x x)</td><td>(lambda (x) (* x x))</td><td>#(* % %) (fn [x] (* x x)</td></tr>
<tr><td>set, setq, defun</td><td>define</td><td>def, defn</td></tr>
</table>

<h2>Lessons from the Little Schemer</h2>
<p>First, go buy <a href="http://www.amazon.com/gp/product/0262560992?ie=UTF8&tag=whatspaulread-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0262560992">The Little Schemer</a><img src="http://www.assoc-amazon.com/e/ir?t=whatspaulread-20&l=as2&o=1&a=0262560992" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" /> by Dan Friedman and Matt Felleisen. It's not only a good initial intro to functional programming, but also one of the best instructional books of any kind.</p>

<h3>Atoms</h3>
<p><code>foo</code> is an atom. <code>42</code> is an atom. <code>*uck_!0u</code> is an atom. All of those are also S-expressions. <code>()</code> is not an atom; it's an empty list.</p>

<h3>Lists</h3>
<p><code>(foo bar bat)</code> is a list. <code>(Nerf)</code> is a list. <code>((pizza pie) garlic breath)</code> is a list. These are all S-expressions.</p>

<h3>car</h3>
<p><code>car</code> returns the first element of a  list. <code>(car '(ice cream sandwich)</code> returns <code>(ice)</code>. <code>(car '((a b c) x y z))</code> returns <code>(a b c)</code>. <code>(car '())</code> has no answer, because <code>car</code> only works on non-empty lists. <code>(car 'elephant)</code> has no answer, because <code>car</code> doesn't do anything with atoms.</p>

<h3>cdr</h3>
<p><code>cdr</code> is pronounced "could-er" (although I always say it to myself as "cedar").</p>
<p><code>cdr</code> takes a list, and returns all but the first element. <code>(cdr '(a b c d))</code> returns <code>(b c d)</code>. <code>(cdr '((rabbit fox) (bear eagle) pterodactyl)</code> returns <code>((bear eagle) pterodactyl)</code>. <code>(cdr '(hedgehog))</code> returns <code>()</code>. <code>(cdr 'Lamp)</code> give no answer, because <code>cdr</code> only works on lists not atoms. <code>(cdr ())</code> is also gives no answer, because <code>cdr</code> doesn't work on empty lists.</p>

<h3>cons</h3>
<p><code>cons</code> takes two arguments&mdash;any S-expression, and a list&mdash;and returns a combined list. <code>(cons 'happy '(trails again))</code> returns <code>(happy trails again)</code>. If the first argument is not an S-expression or the second argument is not a list, <code>cons</code> gives no answer.</p>

<h3>null?</h3>
<p><code>(null? '())</code> returns True. <code>(null? '(x y z))</code> returns False. <code>(null? Sandwich)</code> gives no answer, because <code>null?</code> only works on lists.</p>

<h3>atom?</h3>
<p>This is not a built-in&mdash;it's code from LS:</p>
<pre>(define atom?
    (lambda (x)
        (and (not (pair? x)) (not (null? x)))))</pre>

<h3>eq?</h3>
<p>It works as expected. <code>(eq 'foo foo)</code> if True. Both the arguments of <code>eq?</code> must be non-numeric atoms.</p>

<h3>lat?</h3>
<p><code>lat?</code> is a function in LS that returns true if a list contains only atoms. It demonstrates recursion.</p>
<pre>(define lat?
    (lambda (l)
        (cond
            ((null? l) #t)
            ((atom? (car l)) (lat? (cdr l)))
            (else #f))))</pre>

<h3>rember (building lists with cons)</h3>
<p>The <code>rember</code> function takes two arguments&mdash;an atom and a list&mdash;and returns a list with the first instance of the specified atom removed.</p>
<pre class="prettyprint">(define rember
    (lambda (a l)
        (cond
            ((null? l) (quote ()))
            ((eq? (car l) a) (cdr (l))
            (else (cons (car l)    ;Describes expected first element
                (rember a (cdr l))))))))    ;Recurse through list</pre>
<p>So, it may not be obvious what's going on here. I don't totally understand it myself yet, but believe it has to do with evaluation rules: <code>cons</code> effectively "holds" until the value of its arguments are evaluated to their full depth (i.e.&mdash;through all the recursive calls to <code>rember</code>.</p>
<p>That's why <code>rember</code> works as it should rather than returning a truncated or otherwise mangled list. The values from all the recursive calls to <code>rember</code> basically queue-up for <code>cons</code> until they're all fully evaluated.</p>
<p>Here's another example of list building. The function <code>firsts</code> recurses through a list of lists, building a new list that contains only the first atoms in each of the original sublists.</p>
<pre class="prettyprint">(define firsts
    (lambda (l)
        (cond
            ((null? l) quote())
            (else (cons (car (car l))    ;Describes expected first element
                (firsts (cdr l)))))))    ;Recurse through list</pre>
<p>The thing of interest about these (apart from the recursion) is that <strong>the first argument to <code>cons</code> should describe the expected first element</strong> (LS call this The Third Commandment).</p>

<h2>Emacs</h2>
<p>People who write Lisp tend to do so using Emacs. <a href="http://common-lisp.net/project/slime/">SLIME</a> is an  Emacs IDE for Common Lisp. To start SLIME in Emacs: <code>ALT-x slime</code>. To quit SLIME, type a comma at the REPL prompt, then <code>quit</code> on the Emacs command line.</p>
<p>I tried this. Looks like I'm still a vim guy.</p>

<h2>Links</h2>

<ul>
    <li><a href="http://mitpress.mit.edu/sicp/">Structure and Interpretation of Computer Programs</a></li>
    <li><a href="http://htdp.org/">How to Design Programs</a> another free book from MIT</li>
    <li><a href="http://www.cs.berkeley.edu/~bh/ss-toc2.html">Simply Scheme</a> an intro book</li>
    <li><a href="http://www.lisperati.com/casting.html">Casting Spells with Lisp</a>, a fun basic intro</li>
    <li><a href="http://common-lisp.net/project/slime/">SLIME</a> Lisp IDE for Emacs</li>
    <li><a href="http://www.gigamonkeys.com/book/">Practical Common Lisp</a> free ebook</li>
    <li><a href="http://www.scheme.com/tspl2d/">The Scheme Programming Language</a> free ebook</li>
    <li><a href="http://en.wikibooks.org/wiki/Clojure_Programming/Tutorials_and_Tips#Clojure_for_Scheme_Programmers">Clojure Tips</a></li>
    <li><a href=""></a></li>
    <li><a href=""></a></li>
</ul>

<?php include '../FOOTER.php'; ?>
