Dorophone

Shadchen: A pattern Matching Library for Elisp

2012-01-18T18:30:00.000-08:00

A pattern matching library for Emacs Lisp

One of the things I like most about Racket (and other functional programming languages) is that they have good support for pattern matching, which is a great way to simultaneously dispatch on structure type, enforce constraints on values held in a data structure, and bind variables. A tremendous amount of code is devoted to these activities, and pattern matching combines them all in a succinct, easy to read form.

It's been my intent for some time to write a complete pattern matching library for Emacs Lisp, since it is a Lisp which I use very frequently. Shadchen is the first time any attempt to do so has resulted in a reasonable product. Shadchen is a Yiddish word for matchmaker, in case you were wondering about the title. The library is available in my elisp repository. Even though it comes in a giant directory full of junk, it runs standalone.

[EDIT: Here it is in a standalone repo.]

How it Works

Shadchen's interface consists of just three forms. match is the work horse - it actually performs a pattern match. match has the syntax:

(match <VALUE>
 (<PATTERN1> FORMS ...)
 (<PATTERN2> FORMS ...)
 ...
 (<PATTERNN> FORMS ...))

The <VALUE> expression is evaluated, and then each pattern attempts to match against it. If a pattern succeeds, it's associated FORMS are evaluated, in a context where the environment has been extended by the pattern's bindings. If a match fails, the next pattern is tried. If no patterns succeed, an error occurs.

Here is an example:

(match (list 1 2 3)
  ((list x y z) (+ x y z)))

The expression (list x y z) is the pattern in the above expression. Patterns are such that they resemble the code which creates the data structure in question, in this case a three element list. The pattern (list x y z) basically specifies that a match occurs when the input value is a three element list. When a match occurs, x is bound to the first element, y to the second and so on. Hence this form evaluates to 6.

Here is another example: summing a list:

(defun* dummy-sum (lst &optional (acc 0))
 (match lst
  (nil acc)
  ((cons hd tl)
   (dummy-sum tl (+ acc hd)))))

First we specify the pattern nil, which matches only nil. When the input is nil, we return the accumulator. Then we match against (cons hd tl) which matches a cons pair, binding hd to the car and tl to the cdr. We then recur, adding to the accumulator.

The pattern matching language is rich. There are patterns for matching against literals, applying functions to values, matching against arbitrary conditions, matching against structs.

Eg:

(defstruct a-struct f1 f2)

With this struct defined, the pattern:

(struct a-struct (f1 (? #'numberp x)) (f2 (? #'stringp y)))

Matches only a struct whose field f1 is a number, and whose field f2 is a string. When that is true, x and y are bound.

Extending Shadchen

The pattern matcher is user extensible using defpattern. Defpattern defines a function which receives the pattern's arguments, and returns a new pattern which effects the desired match. For instance, the struct pattern is defined thusly:

(defun cl-struct-prepend (s)
  (intern (format "cl-struct-%s" s)))

(defun make-cl-struct-accessor (struct-name slot) 
  (intern (format "%s-%s" struct-name slot)))


(defpattern struct (struct-name &rest fields)
  `(and
    (? #'vectorp)
    (? #'(lambda (x) (> (length x) 0)))
    (? #'(lambda (o)
           (eq (elt o 0) ',(cl-struct-prepend struct-name))))
    ,@(loop for f in fields collect
            `(funcall 
              #',(make-cl-struct-accessor struct-name (car f))
              ,(cadr f)))))

Note that the defpattern body must return a valid pattern in terms of previously defined patterns (or itself, patterns can be recursive). In this case we use the patterns and, ?, and funcall to create a new matcher.

Supported Patterns:

Shadchen supports the following patterns:

Shadchen supports the following built-in patterns.

<SYMBOL>

Matches anything, binding to that value in the body expressions.

<KEYwORD-LITERAL>

Matches only when the value is the same keyword.

<NUMBER-LITERAL>

Matches only when the value is the same number.

<STRING-LITERAL>

Matches only when the value is string= is the same string.

(CONS <PATTERN1> <PATTERN2>)

Matches any CONS cell, or NIL, then matches <PATTERN1> and <PATTERN2>, executing the body in a context where their matches are bound. If the match value is NIL, then each PATTERN matches against NIL.

(LIST <P1> ... <PN>)

Matches a list of length N, then matches each pattern <PN> to the elements of that list.

(LIST-REST <P1> ... <PN> <REST-PATTERN)

Matches - to elements in at list, as in the LIST pattern. The final <REST-PATTERN> is matched against the rest of the list.

(QUOTE DATUM)

Only succeeds when DATUM is EQUALP to the match-value. Binds no values.

 (AND <P1> .. <PN>)

Tests all <PN> against the same value, succeeding only when all patterns match, and binding all variables in all patterns.

 (? PREDICATE <PATTERN>)

Succeeds when (FUNCALL PREDICATE MATCH-VALUE) is true and when <PATTERN> matches the value. Body has the bindings of <PATTERN>.

 (FUNCALL FUN <PATTERN>)

Applies FUN to the match value, then matches <PATTERN> against the result.

 (BQ EXPR)

Matches as if by BACKQUOTE. If EXPR is an atom, then this is equivalent to QUOTE. If EXPR is a list, each element is matches as in QUOTE, unless it is an (UQ <PATTERN>) form, in which case it is matched as a pattern. Eg:

(match (list 1 2 3)
  ((BQ (1 (UQ x) 2)) x))

Will succeed, binding X to 2.

(match (list 10 2 20)
   ((BQ (1 (UQ x) 2)) x))

Will fail, since 10 and 1 don't match.

(values <P1> ... <PN>)

Will match multiple values produced by a (values ...) form.

(struct struct-name (field-name <P1>)
                    (field-name <P2>)
                    ...
                    (field-name <P3>))

Which matches when the input is a struct of type struct-name, whose fields match <P1> ... <PN>.

Conclusions

If you are an elisp hacker like me, now you don't have to envy those snooty Racket, ML and Haskell programmers. Happy Hacking!

(PS - the library is also available in Common Lisp, check my github).

(PPS - I love Racket, ML and Haskell programmers and they aren't at all snooty.

Literate, Racket-Styled Interpreter from Ch. 1 of Lisp in Small Pieces

2011-12-08T17:56:00.000-08:00

#lang racket

We'll need Racket's mutable pairs.

(require racket/mpair)

Our initial interpreter will not be very discriminating: it is sufficient to recognize atoms, that is, values which evaluate to themselves, by:

(define (atom? x) (not (pair? x)))

However, atoms as defined above include both symbols and things like strings and numbers. We will be using symbols to refer to variables in our interpreted code, though, so we need to draw a distinction between symbols and other atoms.

(define (atom/symbol? x) (symbol? x))
(define (atom/non-symol? x) (and (atom? x) (not (symbol? x))))

I'd like to extend my interpreter as I go, because I think that is clearer. We will take the following approach to allow this:

(define (suffix item onto)
  (reverse (cons item (reverse onto))))

(define-values (interpret extend-interpreter!)
  (let* ((interpreter-handlers '())
         (extend-interpreter!
          (lambda (dispatch-function handle-function)
            (set! interpreter-handlers
                  (suffix (cons dispatch-function handle-function) interpreter-handlers))))
         (interpret
          (lambda (exp env)
            (let loop 
                [(interpreter-handlers interpreter-handlers)]
              (match interpreter-handlers
                [(list) (error (format "Can't interpret ~a - no handler matched!" exp))]
                [(cons (cons dis han) rest)
                 (if (dis exp) (han exp env)
                     (loop rest))])))))
    (values interpret extend-interpreter!)))

The above creates a closure over three-values, the interpreter-handlers, a list of pairs, a function extend-interpreter!, which allows us to add a form-recognizer, form-handler pair to this list (at the end, using suffix) and a function interpret, which does the actual interpretation.

Interpret loops through the handlers, testing the form it is working on with the first function in each pair. If the test succeeds, it interprets the expression with the second function in the pair.

The downside to this approach is that we destructure our expressions twice - once during matching and once during interpretation. The upside is that we can extend our interpreter as we go, clearly separating concerns. This kind of interpreter is about as slow as it can be anyway, so it hardly matters.

Now we can add our first interpretation rule:

(extend-interpreter!
 atom/non-symol?
 (lambda (val _) val))

Each interpreting function takes the form to interpret and the environment. However, things like "this" and 10 don't need an environment, so we give it a name which indicates our disdain for it, _. We simply return what we were passed in.

Now a note on the environment, since we'll need it soon: since Racket lists are made of immutable pairs, and we'll need to mutate our environment, we are going to use mutable cons cells in our list. The global environment, however, is the empty one:

(define the-global-environment (list))

It needn't itself be mutable - adding items to the global environment will be accomplished by set! on the-global-environment, rather than mutation of the list itself.

We want to support adding a binding to the environment from "outside" the language, and extending the environment from inside. Respectively:

(define (add-global-binding name value)
  (if (symbol? name)
      (set! the-global-environment 
            (cons (mcons name value) the-global-environment))
      (error "Bindings must be to symbols.")))

This adds a new mutable cons pair to the global environment, created with mcons.

(define (extend-environment env vars vals)
  (match (list vars vals)
    [(list (list) (list)) env]
    [(list (cons key subs-keys)
           (cons val subs-vals))
     (extend-environment 
      (cons (mcons key val) env) subs-keys subs-vals)]))

Note that extend-environment produces a new environment without modifying the old one. This is important.

Allowing us to say:

(interpret "A string" the-global-environment)
(interpret 100 the-global-environment)

These yield their first arguments, as they should.

Now let's add a rule for symbols. First we need to know how we will look the meaning symbols up:. The simplest possible choice is that we represent the environment as a list of pairs; eg '((x . 10) (y . 11))

(define (lookup s env)
  (match env
    [(list) (error (format "No binding for ~a." s))]
    [(cons (mcons key val) env)
     (if (eq? key s) val
         (lookup s env))]))

lookup is exactly the function which evaluates symbols.

(extend-interpreter!
 atom/symbol?
 lookup)

(interpret 'x (list (mcons 'x 100)))

Which evaluates to 100, just as our environment specifies.

Now we can write the interpreter cases for special forms. Lisp In Small Pieces supports only quote,if,begin,set!, and lambda. quote first:

(define quote-expression? (match-lambda 
                           [`(quote ,exp) #t]
                           [_ #f]))

The evaluation of a quoted form is the form itself.

(extend-interpreter!
 quote-expression?
 (lambda (s env) (second s)))

(interpret '(quote x) the-global-environment)

Results in x, as it should.

Now for if:

(define if-expression?
  (match-lambda 
   [`(if ,test ,true ,false) #t]
   [_ #f]))

We restrict ourselves to ternary if.

(extend-interpreter!
 if-expression?
 (lambda (e env)
   (match e 
     [`(if ,test ,true ,false)
      (if (interpret test env)
          (interpret true env)
          (interpret false env))])))

(interpret '(if #t 'x 'y) the-global-environment)
(interpret '(if #f 'x 'y) the-global-environment)

These expressions are x and y respectively. If's interpreter only interprets the appropriate branch.

Now we implement begin:

(define begin-expression? 
  (match-lambda 
   [(cons 'begin rest) #t]
   [_ #f]))

Here we create a struct whose sole instance is the value returned by an empty begin statement. We could also forbid such a statement.

(struct Empty-begin () #:transparent)
(define the-empty-begin (Empty-begin))

(define (interpret-begin e env)
  (match e
    [`(begin) the-empty-begin]
    [`(begin ,expr) (interpret expr env)]
    [(cons 'begin  (cons expr rest))
     (interpret expr env)
     (interpret-begin (cons 'begin rest) env)]))

(extend-interpreter! 
 begin-expression?
 interpret-begin)

We can't really do anything interesting with begin without implementating side effecting expressions. However:

(interpret '(begin 'a 'b 'c) the-global-environment)

is 'c, just as we expected.

Now for set!, which will allow us to update the environment from within the language itself.

(define set!-expression? 
  (match-lambda
   [`(set! ,(? symbol? var) ,expr) #t]
   [_ #f]))

This is a side effect inducing form and we'll need to use side effects to simulate the result. To match L.I.S.P., however, we will not allow set! to introduce new bindings, only update them.

(struct Set!-result () #:transparent)
(define set!-result (Set!-result))

(define (update! env key value)
  (match env
    [(list) (error (format "Can't find a binding ~a to update." key))]
    [(cons (and (mcons lkey val) pair) rest)
     (if (eq? key lkey) 
         (set-mcdr! pair value)
         (update! rest key value))]))

set-mcdr! does the work. We search until we find the symbol requested, and then we mutate its pair. It is an error to set a symbol without a binding.

(define (interpret-set!-expression e env)
  (match e
    [`(set! ,(? symbol? var) ,expr)
     (let ((val (interpret expr env)))
       (begin (update! env var val)
              set!-result))]))

(extend-interpreter!
 set!-expression?
 interpret-set!-expression)

We will define a test environment which has a binding for 'x

And test our new form:

(interpret '(begin (set! x 100) x) (list (mcons 'x 10)))

Finally, we write our implementation of lambda:

(define lambda-expression? 
  (match-lambda 
   [`(lambda ,(? list?) ,@(list body ...)) #t]
   [_ #f]))

(define (interpret-lambda e env)
  (match e
    [`(lambda ,(? list? vars) ,body ...)
     (lambda values
       (interpret
        `(begin ,@body)
        (extend-environment env vars values)))]))

Lambda's are represented by lambdas, which is confusing, I know (wait till you see the continuation passing interpreter!). However, the way this works will be clear in the invokation word. Our lambda encloses its env, var and body lists and interprets the latter with the environment extended with the former. It receives values to bind to these symbols when it is invoked.

(extend-interpreter! 
 lambda-expression?
 interpret-lambda)

This allows us to write and evaluate lambda expressions but we can't do anything with them until we define the part of the interpreter which invokes functions.

(define invokation?
  (match-lambda 
   [(list e maybe-args ...) #t]
   [_ #f]))

(define (interpret-invokation e env)
  (match e
    [(list e maybe-args ...)
     (let ((f (interpret e env))
           (args (map (lambda (e) (interpret e env)) maybe-args)))
       (if (procedure? f)
           (apply f args)
           (error "Non-function in application position!")))]))

Invoke checks to make sure its first element is actually a function, and then evaluates the arguments. It then passes those values to the function produced by evaluating the first argument. This function contains an internal call to interpret in the extended environment of the function.

(extend-interpreter!
 invokation?
 interpret-invokation)

Ok, we should add some things to our environment so that we can actually do things.

(add-global-binding '+ (lambda args (apply + args)))
(add-global-binding '- (lambda args (apply - args)))
(add-global-binding '* (lambda args (apply * args)))
(add-global-binding '/ (lambda args (apply / args)))

(interpret '(lambda (a b c) (+ a (+ b c))) the-global-environment)

(interpret '((lambda (a b c) (- (+ a b) c)) 1 2 3) the-global-environment)

Wheeeee!

Look out for the next interpreter! Code is available on github.

Persistent Hash Tables for Elisp

2011-12-07T08:53:00.000-08:00

Another quick update: I've added an implementation of persisten hash tables to my emacs library. These are built on top of random access persistent lists and are similar to Clojure's persistent table datatype.

They are like hash tables (with similar performance) except that set operations return a new table - the old table persists unmodified.

You use them like so:

(require 'persistent-hash-tables)

(setq tbl ({} 'a 10 'b 11 'c 12))
(setq tbl2 (ptbl-set tbl 'c 100))
(ptbl-get tbl 'c) ;-> 12 
(ptbl-get tbl2 'c) ;-> 100

Such tables allow functional programming over table abstractions. These might be a better fit than association lists if you have a large number of associations and/or you are doing a lot of functional updates.

Random Access Lists for Emacs

2011-12-06T08:05:00.003-08:00

Here is a quick post: I've added an implementation of random access lists to my Emacs Lisp library. These are a persistent data structure which supports fast persistent list operations (O(1)) as well as pretty fast random-access and persistent update (O(log(n))). These data structures are someplace between a list and a vector, but have the benefit of persistence - update to a random-access-list returns a new list and leaves the old one unmodified. These are similar to Clojure's vector datatype.

You can read about these structures in srfi-101. My implementation is a cargo-cult port of the reference implementation of that srfi to Emacs Lisp.

Examples:

Creation:

(setq r (ra:list 1 2 3 4 5)) ; -> [cl-struct-pl-cons 1 1 [cl-struct-pl-cons 1 2 [cl-struct-pl-cons 3 [cl-struct-pl-node 3 4 5] nil]]]

List operations are prefixed with ra::

(ra:car r) ;-> 1
(ra:cdr r) ;-> [cl-struct-pl-cons 1 2 [cl-struct-pl-cons 3
[cl-struct-pl-node 3 4 5] nil]]
(ra:map (lambda (x) (+ x 1)) r) ;-> [cl-struct-pl-cons 1 2
[cl-struct-pl-cons 1 3 [cl-struct-pl-cons 3 [cl-struct-pl-node 4 5
6] nil]]]
(ra:cons 100 r) ; ->[cl-struct-pl-cons 3 [cl-struct-pl-node 100 1 2] [cl-struct-pl-cons 3 [cl-struct-pl-node 3 4 5] nil]]

And so on.

Random access and update are accomplished with:

(ra:list-ref r 1) ;-> 2
(ra:list-set r 1 1000) [cl-struct-pl-cons 1 1 [cl-struct-pl-cons 1
1000 [cl-struct-pl-cons 3 [cl-struct-pl-node 3 4 5] nil]]]

Note that indexing is zero based.

Once can convert between ra:lists and lists via:

(ra:random-access-list->linear-access-list r) ;-> (1 2 3 4 5)
(ra:linear-access-list->random-access-list '(1 2 3)) ;->
[cl-struct-pl-cons 3 [cl-struct-pl-node 1 2 3] nil]

Conclusion:

I wrote this library by porting over the reference implementation. There are many places where very large random access lists will blow the stack. There are also probably bugs and places where efficiency can be improved. Please let me know if you find any!

They are available from my github account.

Better Monad Parse Updated!

2011-12-02T05:44:00.002-08:00

I've made a few patches to better-monad-parse and pushed the new version to github. The improvements primarily deal with performance of parsers which parse strings, which I've found is the most common use cases.

This seems to make a big usability improvement for me.

I also improved the =number parser, which had some unexpected behavior.

Better-monad-parse is a monadic parser combinator implementation in pure Elisp which is both useful for writing parsers and understanding how monadic computations work.

Suppose you have a set of files which have names consisting of one or more characters and then a number, which you'd like to write a function to parse. You can do so like:

(require 'better-monad-parse)

(defparser =file-name-parser
 (name <- (=>one-or-more =alpha))
 (number <- =number)
 (m-return 
  `((name . ,name)
    (number . ,number))))

This binds the symbol =file-name-parser to a function which takes a string as input and returns an association list (and the leftover input) as a result, but only if parsing succeeds. Otherwise, it returns nil.

The library provides a rich set of parsers and combinators on parsers (like (=>one-or-more ...) above, which takes a parser and returns a parser which parses at least one, and potentially as many as possible, of the specified parser.

Parsers are generic over the input type, and the library knows how to parse strings, lists and emacs buffers by default. Using my implementation of multimethods, you can extend the parser for other input types.

Using better-monad-parse is kind of like the opposite of slumming - you can go visit the neighborhood of pure, functional, monadic programming from the slums of Emacs Lisp!

How to Make Emacs' Scratch Buffer Persistent Across Sessions

2011-11-30T06:13:00.001-08:00

A Quick Elisp Tutorial

Emacs has a handy, but sometimes decried, feature called the "scratch" buffer. This is a special buffer which is created upon startup and allows the user to type in and evaluate Emacs Lisp code. Handy for editing tasks too specific (or not useful enough) to put into an function and handy for exploratory Emacs Lisp interactive development (although this development is just as easily accomplished in any file in Lisp mode).

One problem with *scratch* is that its tempting to put significant bits of code (and other information) into it. This isn't a problem in itself, but *scratch* isn't associated with a file, and its contents are lost without warning when Emacs is closed. Today we'll modify the default behavior of Emacs so that it saves the scratch buffer to a file on exit and loads it back in on startup.

This will serve as a brief Elisp tutorial.

Get it?

Preliminaries

If you are totally new to Emacs, I'd just put the code we are about to write directly in your .emacs or .emacs.d/init.el file. These files are executed when emacs starts, and since we need to ensure that our behavior happens on startup, this is a reasonable place to put code. After years of emacs usage, your .emacs will balloon into an unspeakable cthonian mess, and you'll have to refactor it, but by then you'll know what you need to for that process.

Let's start by declaring a few parameters:

(defvar persistent-scratch-filename 
    "~/.emacs-persistent-scratch"
    "Location of *scratch* file contents for persistent-scratch.")
(defvar persistent-scratch-backup-directory 
    "~/.emacs-persistent-scratch-backups/"
    "Location of backups of the *scratch* buffer contents for
    persistent-scratch.")

defvar declares variables, associates them with a value (the second term), and a doc-string (the third term). Providing a doc-string will ensure that when these symbols appear in the result of an apropos search, they will have a convenient description associated with them. It also will help us out when we look at the code in 4 years. Don't forget to create these directories before trying the code! (Or, modify the code to check for their existence and create them otherwise!)

Our code is going to backup any version of the scratch contents before overwriting them, just in case something really important was hiding in there. That means we need to copy the current scratch file contents (not the contents of the scratch buffer, but the last version of it) to a backup file. That file needs to have a generated name. We'll use the date to disambiguate scratch backups:

(defun make-persistent-scratch-backup-name ()
  "Create a filename to backup the current scratch file by
  concatenating PERSISTENT-SCRATCH-BACKUP-DIRECTORY with the
  current date and time."
  (concat 
   persistent-scratch-backup-directory 
   (replace-regexp-in-string 
     (regexp-quote " ") "-" (current-time-string))))

Again, the initial string in the body of this function is documentation. Emacs will show us this description when it displays information about this function. concat concatenates strings, current-time-string does what you'd think, and we use replace-regexp-in-string to remove the spaces. regexp-quote produces a regular expression which matches exactly its input string and nothing else.

Saving the Contents of `scratch`

Next is our function to save the contents of the *scratch* buffer. We will eventually place this function on a "hook" which ensures it gets run every time emacs shuts down.

(defun save-persistent-scratch ()
  "Write the contents of *scratch* to the file name
  PERSISTENT-SCRATCH-FILENAME, making a backup copy in
  PERSISTENT-SCRATCH-BACKUP-DIRECTORY."
  (with-current-buffer (get-buffer "*scratch*")
    (if (file-exists-p persistent-scratch-filename)
        (copy-file persistent-scratch-filename
                   (make-persistent-scratch-backup-name)))
    (write-region (point-min) (point-max) 
                  persistent-scratch-filename)))

This function needs to work with the contents of the *scratch* buffer, so it uses the special form with-current-buffer to create a context where actions refer to the contents of that buffer.

We then check to see whether a file containing the previous scratch buffer is present, and if it is we use copy-file to copy it to the backup directory. We then use write-region to write the contents of *scratch* from (point-min) to (point-max) (that is, the whole thing), to the scratch file location.

Loading the Contents of `scratch`

(defun load-persistent-scratch ()
  "Load the contents of PERSISTENT-SCRATCH-FILENAME into the
  scratch buffer, clearing its contents first."
  (if (file-exists-p persistent-scratch-filename)
      (with-current-buffer (get-buffer "*scratch*")
        (delete-region (point-min) (point-max))
        (shell-command (format "cat %s" persistent-scratch-filename) (current-buffer)))))

(It has been correctly pointed out in the comments that insert-file is the more idiomatic way of getting file contents into a buffer, which I somehow forgot about!) We first check to see whether there is a file containing the previous session's scratch contents. If there is, we switch to the scratch buffer context with with-current-buffer and use shell-command and cat to insert the contents into *scratch*.

Hooking It All In

Since we are writing this in our .emacs file, we can ensure that the contents of the last session's *scratch* are read in by simply writing:

(load-persistent-scratch)

This will get executed on emacs startup, just as we want. We have to do something more complicated to ensure that save-persistent-scratch is run whenever emacs exits.

To do this, we use one of emacs's many "hooks". A hook, in emacs parlance, is a list of functions which emacs promises to run at specific times or when specific events occur. The hook we need is kill-emacs-hook. This hook is run whenever emacs is killed for any reason.

We can use the special form push, which pushes an item onto the start of a list, to add our function.

(push #'save-persistent-scratch kill-emacs-hook)

Note that save-persistent-scratch is preceded by a #'. This tells emacs that we want the function associated with the symbol save-persistent-scratch, not the value (of which there is none anyway).

That is It!

That's it. Save this into your .emacs and you should now have a scratch buffer which remembers its contents between sessions. Handy!

Is Abstraction a Double Edged Sword?

2011-11-14T14:07:00.000-08:00

I've been writing a lot about functional programming. I do so out of a two pronged interest, the first prong of which is that I'm interested in understanding things myself, and I find there are few better ways to test one's understand than to try and explain that understanding to others. The second reason is that I'm interested in education for its own sake. I've been drafting some chapters for a book in pure functional game development, mostly for reason 1, and I've run across some insights I thought I'd blog about, to see if anyone has any helpful comments.

The issue at stake is that abstraction cuts both ways. Abstract solutions are clean, simple, re-usable and reliable. But that very abstraction makes them hard to get a handle on. They seem to be cognitively slippery.

For Instance

Consider that we wish to represent a game state purely functionally, as an association list, for instance. The game I'm working on as an example is a kind of farming simulation where you grow letters and build items by spelling words. Its game state (in Racket) may look like:

(define initial-state
  '((stamina . 6)
    (total-turns . 0)
    (points . 0)
    (letters . ((f . 2) 
                (o . 4)
                (d . 2)))
    (items   . ())
    (field . ())))

This is pretty straightforward and concrete, such as these things go. Each field represents a part of the game state. stamina, for instance, represents how many more turns we can take before we we have to rest for the day, while letters is an association-list storing the number of each letter/crop we've got stocked up.

We want, however, to avoid side effects. That means we need functions to create a new association list whenever we want to "change" a field. Eg:

(define (increment-points state by)
  (let ((current-points (dict-ref state 'points)))
    (dict-set state (+ current-points by))))

Or:

(define (increment-stamina state by)
  (let ((current-stamina (dict-ref state 'stamina)))
    (dict-set state (+ current-stamina by))))

My aim is to write for a completely novice programmer, and both these solutions, I think, are pretty comprehensible for such a programmer. More advanced functional programmers might prefer to write:

(define (increment-field state field by)
  (let ((value (dict-ref state field)))
   (dict-set state field (+ value by))))

And then, perhaps:

(define (increment-stamina state by)
  (increment-field state 'stamina by))

(define (increment-points state by)
  (increment-field state 'points by))

Both functions are probably still comprehensible to new programmers. increment-field probably seems like a kind of detour or distraction, on the way to the concrete goal of changing our game state. But its a small one, and relatively concrete. Hardly distracting at all.

If I were writing this code for myself, without worrying much about teaching someone what I was doing, I'd take this approach:

(define (partial-left f . partial-args)
  (lambda rest
    (apply f (append partial-args rest))))
(define (partial-right f . partial-args)
  (lambda rest
    (apply f (append rest partial-args))))
(define (always v)
  (lambda rest v))
(define (compose f1 f2)
  (lambda (args)
    (f1 (f2 args))))

(define (dict-transform dict keys-or-key fun)
  (match keys-or-key
    [(or (? symbol? key)
         (list key))
     (let ((current (dict-ref dict key)))
       (dict-set dict key (fun current)))]
    [(list key subsequent-keys)
     (let ((sub-dict (dict-ref dict key)))
       (dict-set dict key
                 (dict-transform sub-dict subsequent-keys fun)))]))

(define (increment-field dict field by)
  (dict-transform dict field (partial-right + by)))

(define (increment-stamina dict by)
  (increment-field dict 'stamina by))
(define (increment-points dict by)
  (increment-field 'points by))

Or, if we want to go really nuts:

(define (curry-left f)
  (lambda uncurried 
    (lambda curried 
      (apply f (append uncurried curried)))))

(define (curry-right f)
  (lambda uncurried
    (lambda curried
      (apply f (append curried uncurried)))))

(define (compose-partially f . transformers)
  (lambda args
    (apply f 
           (let loop ((fs transformers)
                      (as args)
                      (acc '()))
             (if (or (empty? as)
                     (empty? fs))
                 (reverse acc)
                 (loop (cdr fs)
                       (cdr as)
                       (cons ((car fs) (car as)) acc)))))))

(define (id x) x)

(define increment-field-2 
  (compose-partially dict-transform id id (curry-left +)))

I might be ashamed to admit it publically, but I think this implementation of increment-field is kind of rad (although compose partially could probably be made more efficient or given static semantics). Using combinators like compose-partially, curry-* and partial-* we abstract away all the details involved in writing the our functions. It takes a bit of thought to write this way, but this implementation has many fewer tokens into which a mistake could creep.

And yet its completely billy bollucks pedogogically. For one thing, we're writing a ton of functions which have nothing to do with the goal at hand. They'll be useful later because they solve a class of functional programming problems. And they are useful now because they make the solution to this problem simpler, but they seem like a divergence to the reader.

They are also abstract - not only do they not refer specicically to our problem, they don't seem to refer specifically to anything. Some of that is naming (curry is not very descriptive) but some of it is that we are programming at the "function level," in APL/J parlance. The objects we are manipulating are the fundamental objects of our code themselves (functions). These functions (curry-*, partial-*, compose, etc) are all about controlling when, exactly, things are "done." They are conspicuosly not about doing things.

And then, even when we get to our function, increment-field, the implementation seems to have nothing at all to do with what we seem to want to be doing. No names appear, no values seem to be calculated (although functions are calculated, they seem invisible to a new programmer).

The Problem

Who cares, though? If you are teaching novices, just avoid this approach, you might say. Fair enough, but it seems that when functional purity is a design goal, these kinds of higher order functions really help to avoid verbose and repeatative code. How would you find a happy medium? When you restrict yourself to low level idioms, purely functional code seems to become ugly, deeply nested, and difficult to read and write. Even given that I've hammed it up seriously in this post, it seems hard to find a happy medium. What do my readers (if any there be) think?

Understanding the Haskell IO Monad.

2011-11-05T14:07:00.000-07:00

By Building a Toy Model in Scheme

Somehow or another, this blog ended up being about two basic things: Lisp and Functional Programming. I've talked about almost every Lisp species there is, but there is an Elephant in the Functional Programming room, which has only come up every so often, which is the programming language Haskell.

Lisp is the Tao, at least to awesome hippies like Mark Tarver. Image borrowed from here.

I'm quite fond of Haskell, in principle. If Lisp is the Tao -- a kind of informal, flexible cloud around the locus of the ideal programming language -- then Haskell might be a rather rigidly specified diamond right near that locus' center. Haskell trades a lot of the looseness of Lisp for a rigid semantics, but it seems there is a good argument that these semantics are much closer to the ideal of Functional Programming.

I don't have much opportunity to program in Haskell, and so I don't write a lot about it. I do program in Lisp a lot, and I think I've subconsciously been engaged in a long term project to improve my understanding of Haskell by implementing toy models of parts of it in Lisp. Hence all the posts about monads. I've recently started writing a book about pure functional programming in Scheme/Racket and initial exploratory writing has produced a few insights about Haskell's IO Monad.

The IO Monad seems to be among Haskell's most mysterious monads for new programmers. Monad tutorials and explications rarely talk about it. Haskell tutorials introduce it as an ad-hoc: they show you how to use it syntactically, but its rarely made naked. And there is a reason for this: whatever it is, precisely, that the IO Monad does isn't expressable in regular old safe Haskell.

But its pretty important, and not just because its the only kosher way for a Haskell programmer to communicate with the outside world. In a sense, a Haskell program can be viewed as a description of some IO actions. The Haskell run time can be thought of as constructing that IO action, and then, somehow, executing it. If you've heard programmers say that, even when using the IO Monad, one is still writing "pure" code, this is what they mean: the Haskell program itself simply constructs an IO action from smaller, and ultimately primitive IO actions. The actions are never run in the code itself, just constructed. Eventually the Haskell runtime executes them, but the construction of the IO commands is itself purely a matter of functional programming, without side effects.

(Note that the programmer can bail out of this paradigm using thigns like unsafePerformIO, but that is frowned upon, for the most part).

So its important, I think, to develop a mental model of what is going on here.

Enter Scheme

I Love Lisp/Scheme, because using Lisp is a great way to understand language constructs. Lisp is a kind of programming language lab, where a crappy, ad-hoc and slow implementation of a language feature is always a few hundred lines of code away. It takes serious effort to design a non-standard language on top of Lisp for an "industrial strength" application, but if you just want to understand something, Lisp can take you there. It is a great way to get to know unusual semantics.

Today we're going to use Racket, which really isn't a Scheme anymore, so much as a Scheme superset, to build a toy model of the IO monad. The bird's eye view is that we'll build a lexicon of IO actions, which will be regular old functions which take the IO state and maybe do something with it, and return a value, and then we'll build some machinery to construct more complex IO actions from simpler ones.

We'll also build an external library to execute these IO actions once they've been built, but the intent is that the user is segregated from this execution. They don't know anything about it, and all they do is build IO actions and hand them off.

Bundling Up IO

Let's start with our "low level" IO. One possibility is that we bundle up standard-input and standard-output into a type of some kind. IO actions will just, then, be functions which take this pair of standard input and output and return values. I'd like to do something a little more fun. Let's build a graphical user interface that has an input window and and output window and build an IO Monad over them, instead. This will give us a change to play around with Racket's GUI classes, which is a nice thing to get acquainted with.

Sketch

We'll write a function run-io which will take an IO action, pop up a window, and execute that action. It will have the type:

type io-action = io -> a
run-io :: io-action -> a

Where we mean by a that the function returns the type a, which can be anything. Our function takes a single value of type io-action, which we will get specific about in a bit.

This function has to do a few things. It needs to initialize a frame%, put some editor's in it with a layout of some kind, and then it needs to create the io object, pass it to the action, and then return the result of the io action. The window will be broken into an output area and an input area. The output area will have no special behavior, except, of course, that we'll be able to write to it and clear it. The input area will be a kind of "command line," - we want it to only accept one line at a time, which it detects by looking for a newline. Somehow, we want each command to end up being readable from within the monad.

Text windows are represented by two classes working in tandem in Racket, a text% class and an editor% class. We can accomplish our goals by subclassing the text% part.

(require racket/gui
     (only-in srfi/13 string-trim-both))

(define (string-contains-newline? str)
  (let loop ((chars (string->list str)))
    (match chars 
      [(list) #f]
      [(cons #\newline rest) #t]
      [(cons x rest)
       (loop rest)])))

(define input-text% 
  (class text% 
    (field (command #f))
    (define/public (text-substring start len)
      (let loop ((acc '())
                 (i 0))
        (if (< i len) (loop (cons (send this get-character (+ start i)) acc) (+ i 1))
            (list->string (reverse acc)))))
    (define/augment (after-insert start len) 
      (let ((string (send this text-substring start len)))
        (if (string-contains-newline? string) 
            (let ((a-command (send this text-substring 2 (+ start len))))
              (set! command (string-trim-both a-command))
              (send this erase)
              (send this insert "> "))
            #f)))
    (define/public (grab-command) 
      (let ((c command))
        (set! command #f)
        c))
    (super-new)
    (send this insert "> ")))

We've added a field to store the current command, with #f no command, and augmented the after-insert method to detect command entry and act appropriately. The new method grab-command fetches the current command and sets the internal command to #f again.

There is no easy way to make setting up a GUI look nice, as far as I know, so here is the gory details:

(define (setup-window)
  (let* ((frame (new frame% 
                     [label "io toy"]
                     [width 640]
                     [height 480]))
         (pane (new vertical-pane% 
                    [min-width 640]
                    [min-height 480]
                    [parent frame]))
         (output-text (new text%))
         (output (new editor-canvas% 
                      [parent pane]
                      [style '(no-hscroll)]
                      [editor output-text]
                      [min-width 640]
                      [min-height 400]))
         (input-text (new input-text%))
         (input (new editor-canvas%
                     [parent pane]
                      [style '(no-hscroll)]
                      [editor input-text]
                      [min-width 640]
                      [min-height 40]))
         (io (lambda (input)
               (match input
                 [(? string? x) (send output-text insert input)]
                 ['clear (send output-text erase)]
                 ['fetch-command
                  (let loop 
                    ((command (send input-text grab-command)))
                    (yield)
                    (if command command (loop (send input-text
                                                    grab-command))))]))))
    (send frame show #t)
    io))

The IO Window in All Its Splendor

This does the business of setting up our window and constructing our "io" value, which is apparently a function which can take either arbitrary text, which it inserts into the output buffer, or the symbols clear and fetch-command. clear, straightforwardly enough, clears the output region with the erase method. fetch-command enters a loop and doesn't return until a command is entered by the user, although it does call yield in order to let the GUI thread check for new events.

With this function, we can easily define:

(define (run-io action) 
 (let ((io (setup-window)))
    (action io)))

Now our users can concern themselves entirely with IO action construction. They trust us to execute the action later. What does an action look like?

Well:

(define (clear io) (io 'clear))
(define (get-command io) (io 'fetch-command))
(define (insert text) (lambda (io) (io text)))

Are three such commands. In fact, they are going to be our "atomic" commands, from which we'll build everything else.

One wrinkle: insert isn't itself an io action, it is a function which returns an io action which inserts the indicated piece of text. insert is a simple kind of io-action builder. We'll see how to integrate io actions together in a bit.

Let's wrap this all up in a module, only exporting our low level interface:

(provide run-io clear get-command insert)

Saving the file as toy-io.rkt will create a module. You can also download this code from my github account.

You've got to place that file somewhere where Racket can get to it, and then you can fire up Racket and say:

(require blog/toy-io)
(run-io (insert "Testing, 1, 2, 3!"))

And press go. What this should do is pop up a window with an interaction area and an output area with "Testing, 1, 2, 3!" in it. Great. Now we should focus on building up IO actions.

The IO Monad

Monads always have an associated monadic value of a particular type. In this case, our monadic values are functions which accept an IO object and return any old thing. The get-command is a monadic value - it accepts the io object and returns the command received from the user. What if you wanted a get-two-commands which read two commands and returned them as a list?

(define (get-two-commands io)
  (let ((c1 (get-command io))
        (c2 (get-command io)))
    (list c1 c2)))

Simple enough. get-two-commands is, itself, a monadic value.

Now for the monad part: what if you want to define a monadic value which gets one command, and then determines what to do based on the result of that command. We can represent the choice we'll make about what to do next with a function which is waiting for the previously read command and will eventually return an io action. Think of a lambda expression as a computation with some unbound variable which will calculate a value when that variable is provided or bound. Hence, consider the function:

(define (io-bind io-action io-action-producer)
  (lambda (io)
    (let* ((result (io-action io))
           (next-io-action
            (io-action-producer result)))
     (next-io-action io))))

io-bind is our io action construction work horse. It builds up a new io action from an io action and an io-action-producer, which is waiting for the result of the previous io action before it can decide what to do. io-bind returns an io action, of course. That io action executes the first argument to io-bind when it receives the io object. It then passes the result of that action to the producer, and executes the resulting io action on the io object.

This is sufficient to build up a large family of complex io actions which depend on the results of querying the input. We need one more function to build our monad, though:

(define (io-return value)
  (lambda (io)
     value))

This function makes the simplest kinds of io actions. They don't do anything, but they do return whatever value was specified when io-return was called. io-return, in other words, inserts values into the io monad.

Building IO Actions

Let's build an io action that checks for the command "exit." If "exit" is encountered, then the io action simply returns, but if it isn't encountered, it reads another command and so on.

(define exit-flagger 
  (io-bind get-command 
           (lambda (command)
             (if (equal? command "exit") 
                 (io-return 'exit-detected)
                 exit-flagger))))

If you then execute (run-io exit-flagger), you'll get a window which will keep accepting inputs until you type "exit," at which point, control will return to the command line.

Here we use io-bind to construct a new io action directly, but Haskell provides special syntax for monadic behavior. Let's build a version of that syntax here.

"Do" Notation

We'll create a do-io form which accepts a list of expressions of two varieties. An expression must either evaluate to an io action, or it must specify that a value should be bound to the result of an io action in the following way:

(command <- get-command)

We'd rather not get into a deep discussion about macros in Scheme, so we'll use regular old syntax-rules. Not much error handling, but its pretty simple to understand.

Consider:

(define-syntax do-io 
  (syntax-rules (<-)
   [(do-io (id <- io-action) expr ...)
     (io-bind io-action 
        (lambda (id)
          (do-io expr ...)))]
   [(do-io io-action expr ...)
    (io-bind io-action 
     (lambda (_) 
       (do-io expr ...)))]
   [(do-io io-action) io-action]))

Our syntax-extension has three cases. The most specific appears first, where we detect an expression indicating a monadic binding. We pass the monadic value io-action to io-bind along with a lambda expression consisting of the rest of the do-expression in a context where the id is bound to the result of the action. When we don't have a binding expression of the form (id <- io-action), expand the macro the same way, but don't even bother creating a variable visible in the rest of the expressions. If we only have a single expression, then we just return its value.

We can now write our exit-flagger io action as:

(define exit-flagger
 (do-io 
  (command <- get-command)
  (if (equal? command "exit") 
      (io-return 'exit-detected)
      exit-flagger)))

This resembles Haskell notation, where the same thing might look something like:

exitFlagger = do
  command <- getCommand
  if equal? command "exit" 
     then
       return "exit-detected"
     else
       exitFlagger

A Simple Example

Let's write some brains into our command interpreter.

(define (read-command str)
  (with-handlers ([exn:fail? (lambda (e) 'error)])
    (with-input-from-string 
     (string-append "(" str ")")
     (lambda () (read)))))

This function converts a string into a list of values. If it doesn't receive a string which, when wrapped with "()" evaluates to a piece of Scheme code, it just returns error. We use it to make dispatching on commands easier:

(define symbolic-command
  (do-io 
    (cmd <- get-command)
    (io-return (read-command str))))

Now we can write:

(define (repeat-char n char)
  (let loop ((n n)
             (acc '()))
     (if (<= n 0) (list->string acc)
         (loop (- n 1) (cons char acc)))))

(define dispatch
  (do-io
   (c <- symbolic-command)
   (match c
     ['error 
      (do-io
       (insert "Error reading command string.")
       dispatch)]
     [(list 'stars (? number? n))
      (do-io 
       clear
       (insert (repeat-char n #\*))
       dispatch)]
     [(list 'exit) (io-return 'exit-detected)]
     [_ (do-io
         clear
         (insert "unknown command.")
         dispatch)])))

dispatch is pretty easy to understand. It is an io action which grabs a command, converts it to a list of atoms and lists, matches that list for known commands, and loops, unless the command read is (exit). Note that dispatch is defined without ever explicitely referencing the io state that is threaded through all its parts. We've liberated the programmer from thinking about what that state is or how it is managed. They simply build up io actions like any other kind of data.

Dispatch in action!

Conclusions

Ok, so we built a low level interface which non-functionally handles input and output operations for us. Because input and output is inherently stateful, there is no real way to avoid side effects in this part of our code.

However, we then realized that we could "encapsulate" input and output operations in a few primitive io actions and provide a monadic context wherein the user can build more complex actions from simpler ones. Up until the moment the user calls run-io, she maintains complete purity. Constructing io actions can be done completely without side effects.

For bonus, we implemented a syntax mimicing Haskell's do notation in terms of the function io-bind. This gave us a toy model of Haskell's io monad, which we used to build some simple io actions.

Glazed over in all this discussion were the implications of Haskell's lazy semantics, type system, and error handling mechanisms. We might also begin to wonder how we combine this stateless io programming with other, apparently stateful tasks. We'll see how we can do that in a later post (or in the book, if I ever write it), and how these considerations relate to monad transformers!

This code is up on my github. If you are interested in monads, you can also check out my better-monads library on Planet Racket. It doesn't include an IO monad because that is kind of ridiculous in Scheme!

Thanks for reading!

Better-monad-parse Now Available

2011-10-18T06:01:00.000-07:00

I've pushed better-monad-parse.el to my github repository. This is a refactoring of monad-parse, principally to make its interface more regular and grokable. It also is more intellegently polymorphic over different kinds of parseable objects, principally by making use of my implementation of multimethods instead of EIEIO, which, as far as I'm able to ascertain, doesn't allow method dispatch on built-in classes.

Unfortunately, its a bit slow, even compiled. I'd love to have advice on how it might be sped up, although I'm thinking its a lost cause - this kind of programming might be too taxing for Emacs Lisp.

Notes

This library follows the following conventions.

Parsers are functions which accept a generic input state and return a list of cons cells, where the car is the monadic return value and the cdr is the unparsed input.
All parsers defined by the library start with the symbol =, eg =nil, =item, etc.
Parsers are often parameterized, that is, a parser will be created based on some value passed to a function. Functions which produce parsers begin with the symbol =>, eg: =>string, =>items, =>or, =>and and so forth.

New parsers should be most easily created with the parser special form, which introduces a monadic expression context for parser construction:

 (parser 
   (n <- =number)
   (letters <- (=>zero-plus-more =alpha))
   (m-return (list n letters)))

Produces a parser which binds n to a number parsed from the input, and then binds letters to a list of zero or more letters parsed from the input. All the parses defined by the library are generic, so they can parse buffers, strings or lists. There is a rich vocabulary of parsers to combine in the library, but if you wish to write your own generic parsers, you'll need to create a multimethod to cover all input types.

Understanding mulitmethods is also critical if you want to extend the parser library to cover additional input types.

This library is all about defining parsers, so there are special forms for that purpose:

(defparser =number-then-letters
   (n <- =number)
   (letters <- (=>zero-plus-more =alpha))
   (m-return (list n letters)))

Sets =number-then-letters symbol and function value to the parser produced by the body expression evaluated in the parser monad. This allows you to call the parser as a function and also refer to it as a variable, since both actions are common.

defparser allows the creation of parametric parsers too:

(defparser (=>specific-number-then-letters n)
   (n-parsed <- =number)
   (if (= n n-parsed)
       (parser 
          (letters <- (=>zero-plus-more =alpha))
          (m-return n letters))
       =nil))

defun's a function which produces the indicated parser. Arguments are automatically lexically closed over. This version doesn't set the symbol-value of the name.

As stated above, the library performance is a bit slow still - I haven't determined to what that slowness owes, but I recommend byte-compiling everything.

I'm almost certainly going to port this whole thing to Common Lisp at some point, so I can call out to it via slime. That should help with performance, as I have a nagging feeling that the bottleneck is my ad-hoc multimethod dispatch.

Update to my Monadic Parser Combinator Elisp Library (+ examples/tutorial)

2011-10-07T07:34:00.000-07:00

I've updated my emacs lisp monadic parser combinator library. The underlying mechanisms for building parsers remain unchanged, but I've introduced a few new syntactic forms to make writing parses a little easier than it used to be.

If you want to understand how the library works, under the hood, check out my screencast about monadic parser combinators in Elisp located here.

This post will introduce those features and give a quick tour of how I'm actually using them in my day to day life as a researcher.

To use the library, download my code from github, add the directory to your emacs path, and then:

(require 'monad-parse)

Which will load the parser monad and its associated functions. It really helps to byte-compile this library, because it relies on some serious macro magic behind the scenes. Performances is tolerable for the compiled version, but can be a real drag without compilation.

If you get an error about filename being undefined during compilation, evaluate:

(setq filename nil)

in your scratch buffer. This is some emacs bug that has to do with CEDIT, which I don't even use. Beats me!

We'll be using an example from my day job today. I work in an electrochemistry lab. My background is in data analysis and modeling, and so I get lots of files containing data from my colleagues. The files are given human-readable names describing the kinds of data they contain:

firstElectrode/1000uM_DA_.4-1-3bg_CV.txt
firstElectrode/500uM_DA_.4-1-3bg_CV.txt
firstElectrode/250uM_DA_.4-1-3bg_CV.txt
firstElectrode/100uM_DA_.4-1-3bg_CV.txt
firstElectrode/1000uM_DA_.4-1-3cv_CV.txt
firstElectrode/500uM_DA_.4-1-3cv_CV.txt
firstElectrode/250uM_DA_.4-1-3cv_CV.txt
firstElectrode/100uM_DA_.4-1-3cv_CV.txt
firstElectrode/1000uM_DA_.4-1-3bg_CV1.txt
firstElectrode/500uM_DA_.4-1-3bg_CV1.txt
firstElectrode/250uM_DA_.4-1-3bg_CV1.txt
firstElectrode/100uM_DA_.4-1-3bg_CV1.txt
firstElectrode/1000uM_DA_.4-1-3cv_CV1.txt
michaelElectrode/500uM_DA_.4-1-3cv_CV1.txt
michaelElectrode/250uM_DA_.4-1-3cv_CV1.txt
michaelElectrode/100uM_DA_.4-1-3cv_CV1.txt

I do analysis which requires that I grab all these files and process them together, and I need to know things like what dopamine concentration each file has and other information which is in the file name, but not easy for a computer to get at. My strategy is to write a parser which converts the human readable filenames into a data structure, and then generate a new, very easy to parse, filename to copy the file to.

This is because I'm doing the data analysis in Matlab, where its hard to write a general purpose parser. Better to let emacs do the work of parsing the complex names and generate simple names for Matlab.

Building Up a Parser

We'll start with preliminaries, little parsers we need to break up the file names:

(defparser slash (=string "/"))
(defparser underscore (=string "_"))
(defparser dash (=string "-"))

Next we need to write parsers for larger bits of text. These are still relatively simple.

(defparser experiment-label
     (characters <- (=zero-or-more (=not (=string "/"))))
     (m-return
      (alist>> :label (coerce characters 'string))))

When parsing strings and buffers, =zero-or-more creates a parser which returns a list of character codes. We bind that list to a variable, characters and coerce it into a string, which is returned to the caller as the monadic return value.

defparser's body allows you to write code more or less like you would in Haskell's do notation. It expands to a defvar expression, but the body is placed inside a parser special form. parser lets you create anonymous parsers.

We can test this parser like so:

(parse-string experiment-label "abcdef/gea") ;-> (:label "abcdef")

parse-string returns just the parsed part of the input, and throws away the leftovers. It also converts its second argument to a parser input stream. You can use a parser directly like this:

(funcall experiment-label (->in "abcdef/gea"))

Which returns the entire parser state:

(((:label "abcdef") . [object <parser-input-string> "<parser-input-string>" "abcdef/gea" 6]))

The library supports non-deterministic parsing, so parsers return a list of all the parser states produced, each of which is a pair containing the parsed value and an object represening the rest of the parse state. In most cases, you'll want to use parse-string. But the library supports buffer parsing and list parsing.

Now lets build our first multi-part parser. This will parse a quantity and its units.

(defparser amount
  (magnitude <- (=number->number))
  (units <- (=string "uM" "nM"))
  (m-return (alist>> :amount magnitude :units units)))

This parser makes use of the =number->number function, which returns a parser which converts a string representation of a base 10 decimal number into an actual number. We then use =string to capture units of either uM or nM, the only units in my data set.

These are packed into an association list for later use.

Data files come in two flavors, "background" and "cv". This parser parses the string representing one of them:

(defparser cv-type
  (type <- (=string "bg" "cv"))
  (m-return (alist>> :cvType type)))

As above, the =string combinator produces a parser which matches any of the strings it receives.

A parser for substances looks like, then:

(defparser substance
  (sub <- (=stringi "DA" "AA" "pH" "H2o2"))
  (m-return (alist>> :substance sub)))

Here we use a variant of =string, =stringi which matches any of the input strings without considering case. It returns the actual match.

Now we need a parser to deal with that soup of numbers and dashes which is supposed to represent a voltage range:

michaelElectrode/100uM_DA_.4-1-3cv_CV1.txt  
                          ------
                          this stuff

Here is the parser:

(defparser voltage-range
  (low <- (=number->number))
  dash
  (pre-decimal <- (=number->number))
  (post-decimal <- (=number->number))
  (m-return
   (alist>> :voltageLow low
            :voltageHigh (+ pre-decimal (/ post-decimal 10.0)))))

Finally, some experiments contain multiple electrodes. If this is the case, the electrode number appears. We need a parser that tries to find a number and returns 0 if it can't find one:

(defparser electrode-number
  (n <- (=maybe (=number->number)))
  (m-return (alist>> :electrode (if n n 0))))

Now we put them all together:

(defparser file
  (label <- experiment-label)
  slash
  (amt <- amount)
  underscore
  (sub <- substance)
  underscore
  (rng <- voltage-range)
  (type <- cv-type)
  underscore
  (=string "CV")
  (el <- electrode-number)
  (m-return
   (append label amt sub rng type el)))

And we make it work:

 (parse-string file "michaelElectrode/100uM_DA_.4-1-3cv_CV1.txt")

Produces:

 ((:label "michaelElectrode") 
  (:amount 100) 
  (:units "uM") 
  (:substance "DA") 
  (:voltageLow 0.4) 
  (:voltageHigh 1.3) 
  (:cvType "cv") 
  (:electrode 1))

I have a utility function in my chemistry library that will convert such an alist into a much easier to parse form:

(require 'chemistry)
(condition->filename '((:label "michaelElectrode") 
  (:amount 100) 
  (:units "uM") 
  (:substance "DA") 
  (:voltageLow 0.4) 
  (:voltageHigh 1) 
  (:cvType "cv") 
  (:electrode 1)))

"label=michaelElectrode=amount=000100=units=uM=substance=DA=voltageLow=0.400000=voltageHigh=000001=cvType=cv=electrode=000001"

That is it!

Extra Features

You can use defparser to create parameterized parsers too. That is, parsers which depend on some input. Suppose you want a parser which parses anything numerically equal to a particular value:

(defparser (parse-this-number n)
  (parsed-number <- (=number->number))
  (if (= parsed-number n) (m-return parsed-number)
      parser-fail))

(parse-string (parse-this-number 10) "10") ;-> 10
(parse-string (parse-this-number 10) "100") ;-> nil

Here is the github link again, if you want to play with the library. Documentation is coming, eventually!

I'm going to do a full rewrite of this library eventually, but it will be under a new name. This guy should stabilize eventually.

Scheme Syntax is A Monad

2011-09-06T16:33:00.000-07:00

Two Great Tastes that Taste Great Together

Monads are, in a way, all about sequences of operations which depend on data living "inside" a data structure and produce instances of that data structure with new data inside. For instance, the list monad sequences operations which depend on things inside a list, and which produce lists themselves. The state monad sequences operations which depend, in a sense, on data living inside a state function and result in new state functions. The "maybe" monad sequences operations depending on values which produce "maybe" values (like (Just x) or (Nothing)).

Fact.

Think about this enough and you start to look for monads whenever you deal with any kind of data structure. Recently, I've thought a lot about hygienic macros, of which the key component is "syntax", a kind of decorated representation of source code. If you write simple macros that don't do anything like variable capture, you basically don't have to worry about the distinction between syntax and datum, but when you start selectively messing up hygiene, it becomes important.

And you start to notice patterns. Specifically, you are often "unpacking" a piece of syntax, doing something to it, and then "resyntaxing" it when you are done. Can we conceptualize syntax as a monad? If we do so, do we get anything? It is useful? I suspect for many seasoned readers the first is obvious: any data structure which "holds things" has an associated monad. We'll see about the second - I actually don't know myself, and expect to find out as I write this post.

Better Monads

We'll be operating in my Scheme of Choice, Racket and we'll use my monad library better-monads. To define a monad in better-monads you simply create an instance of the monad struct, defined as:

(struct monad (bind return plus zero) #:transparent)

Plus and zero are optional, and you set them to #f if you can't provide meaningful values. That is:

(require functional/better-monads)

(define the-id-monad
 (monad (lambda (v f) (f v))
        (lambda (v) v)
        #f #f))

Creates the identity monad. We can then use it in an mlet* expression.

(mlet* in: the-id-monad
   ((x 10)
    (y (+ x 11)))
 (return (+ x y)))

Which will be 31, because the identity monad doesn't do anything at all. The library defines and exports some common monads:

(mlet* in: the-list-monad 
  ((x '(a b c))
   (y '(q r s)))
 (return (list x y)))

Results in:

'((a q) (a r) (a s) (b q) (b r) (b s) (c q) (c r) (c s))

If you aren't down with monads, read my tutorials on using them in Lisps. I'm told they are helpful.

The Syntax Monad

The easiest place to start with a monad is with return, since return is our simplest monadic function. That is, there is a family of functions which accept values and produce monadic values and return is often one of the simplest of these functions. What is return in the syntax monad?

The super naive but technically correct answer is:

(define (syntax-return item)
  (datum->syntax (syntax _) item))

This takes an item, any kind of datum, and wraps it into a syntax-object with datum->syntax. Datum->syntax requires, however, a "seed" syntax object from which to copy the syntactic information that helps maintain (or violate) hygiene. This version of return just creates a new syntax object with (syntax _) as the seed, but this isn't very useful. We are almost always trying to create a syntax object which borrows someone else's scope information, say to capture a variable.

If this were Haskell, we might have to live with this sub-optimal solution (you don't really need return as far as I can tell, its just a handy way to put things into the monad). However, we're using Scheme and that means we can take advantage of our greater flexibility to write this version:

(define (syntax-return item . rest)
 (match rest 
  [(list) (syntax-return item (syntax _))]
  [(list seed)
   (datum->syntax seed item)]))

This function takes an optional second argument which can specify the seed if need be. better-monads doesn't care about the fact that this return has a different signature than other returns. All that matters is that everything works out at runtime.

Bind is often a sticking point but in the syntax monad it is very easy to understand:

(define (syntax-bind stx stx<datum>)
 (stx<datum> (syntax->datum stx)))

Here we use a little notational hint I use in my code. The <datum> part of the symbol stx<datum> indicates that stx<datum> is a function waiting for a single value, the datum, to produce something, namely a piece of syntax (hence the stx). The value stx (without any <>) is a syntax object. Bind simply extracts the value in the syntax using syntax->datum and calls the function stx<datum> on that value. The rules of our monad dictate that the result must be some syntax, but this (again) is enforced at run-time, not by any type-checker.

We can define our monad in two ways, depending on the behavior of return we want. The first is:

(require functional/point-free)

(define (the-syntax-monad<stx> stx)
 (monad syntax-bind (partial< syntax-return stx) #f #f))

This monad is parametrized by the syntax we want to use as the seed for return operations. We accomplish this by partially applying syntax-return on the right with the value stx passed in during the monad creation. partial< means "partially apply on the right" (as opposed to >partial, which means "on the left") and lives in my point-free library.

As I understand it, this kind of "value parametrized monad" is difficult to represent in Haskell. I've read that the "set monad" is hard to come up with for just this reason. In scheme, you just parametrize the set monad by whatever predicate you want to constitute equality.

We can also write a regular old monad:

(define the-syntax-monad (monad syntax-bind syntax-return #f #f))

Here we just expect the user to provide an appropriate seed syntax-object when they call return. I am almost certainly sure you can't do this in Haskell without jumping through big hoops. Not really a Haskell programmer, though, so its possible I'm wrong.

But Will it Blend?

This comes up with you google image search "Two Great Tastes"...

Ok, so this is cute. We've got a monad over syntax but can we use it to do anything? Well, one application that springs to mind is that we can use it to defined syntax-oriented versions of standard list functions:

(define (syntax-car stx)
 (mlet* in: (the-syntax-monad<stx> stx)
   ((contents stx))
  (return (car contents))))

Or, using the more convenient notion of lifting a function into a monad:

(define (syntax-car stx) 
 ((lift1 car (the-syntax-monad<stx> stx))
  stx))

For functions of two arguments, this looks like:

(define (syntax-cons hd tl)
 ((lift2 cons (the-syntax-monad<stx> tl))
  hd tl))

We can use these functions like so:

(syntax-car (syntax a b c d)) ;-> (syntax a)

(syntax-cons (syntax a) (syntax b c d)) ;->
  (syntax a b c d)

In the second case, though, its important to realize that the syntax a has its syntactic metadata replaced with the meta-data for the tail, that is (syntax b c d ). If we want a to keep its own meta-data, we should write:

(define (syntax-cons hd tl)
 (mlet* in: the-syntax-monad 
   ((tl-contents tl))
  (return (cons a tl-contents) tl)))

We could define this in a point free way (if we wanted to show off), as such:

(define (syntax-cons hd tl) 
 ((lift1 (>partial cons hd)
  (the-syntax-monad<stx> tl))
  tl))

There are other various and sundry things which it might be easier to do/define using the syntax monad, but without using it a great deal, I'll just say that it seems to blend ok.

Conclusions

Finally, the real deal.

We've shown how to define and use a syntax monad for Scheme syntax objects. The essence of the implementation is the realization that syntax, as a kind of wrapper over regular Scheme data, is enough like a container that we can write a monad over it, much like we can create a list monad over lists.

The utility of the monad seems to be limited by the fact that syntax containers aren't just dumb boxes around pieces of data, but contain important meta-data which is intimately related to their intended use. It isn't clear to me whether, given this fact, really using the syntax monad would ever be a win, but who knows? At the very least it is an interesting example of what I guess you could call a monad parametrized over a run time value, which is an interesting idiom, anyway.

All this code is up on my git repository.

Monadic Turtle Graphics (Screencast Edition)

2011-08-30T16:57:00.001-07:00

Apparently the video is still borked for many users. Anyone here have any advice on the best way to record screencasts on Ubuntu Natty? A trillion apologies and abasements for any inconvenience.

Hi everyone, a few months ago I posted a lengthy article about using monads to simulate state for a turtle graphics system, including a "novel" monad to represent parallel graphics operations.

I had the opportunity to give that material as a talk at Racketcon (I used Racket as the demonstration language). There is a version available of that online someplace, I believe, but I only had 15 minutes there, and its more of a half hour or longer talk. So I recorded a screencast version, which is now available here.

The talk is in OGV format. If anyone needs it in AVI, I can probably accommodate, but I figure anyone who cares about monads can probably figure out how to watch an Ogg Video file.

Oh yeah: all the code (including the slides, which are written in Racket) is in the racketcon directory at this github repo.

A Survey of Syntactic Extension Techniques in the Lisp Family of Languages (Part 3)

2011-08-25T16:50:00.000-07:00

Last time we talked about the Lisps which use something we might call defmacro-style syntactic extensions (Common Lisp, Emacs Lisp, Clojure, Arc, and things we didn't specifically talk about, like LuSH). The time before that, we talked about dynamically scoped interpreted Lisps with fexprs in which the fact that a piece of code's value is always dynamically defined was exploited to let various run-time approaches to staging execution stand in for macros.

Hopefully, throughout the previous posts, I've impressed upon the reader the importance of scope in all of these discussions. The key reason that picoLisp or newLisp can get away with fexrp-style macros is that code literally means what it says whenever it is you evaluate it. This has some things to recommend it, but these days lexical scope is the biggest rooster in the yard. Lexical scope makes reading and writing code easier and prevents certain kinds of bugs, but it introduces problems with defmacro-style macros, which manipulate code without knowing anything about the lexical contexts associated with variables. What this principally means is that a defmacro-style macro:

Will behave incorrectly if it depends on other macros/special forms whose definitions are changed between its declaration and interpretation.
Can introduce symbol-bindings which unexpectedly shadow symbol bindings in expanded sub-forms.

In Lisps with defmacro style macros, 1 is kind of dealt with by having separate namespaces - generally, one just hopes that people won't often redefine macros and, if they do, they will do so in their own namespace. Macros implicitly invoked by a macro expansion will hopefully or by design expand into package-qualified symbols, which we trust the user not to clobber without knowing what she is doing.

Point 2 is dealt with by generating symbols during macro expansion which are guaranteed (under most circumstances) to be unique from any other symbols which are in use. This gives macros a means of expanding into code which references its own private variables without any concern of clobbering some bindings unexpectedly.

If we restrict our attention to regular old Lisp code, without macros, in a lexical Lisp, we might begin to think that syntactic extensions are kind of lacking when compared to other kinds of kinds of things with names. Of course, we can't pass syntactic extension tokens around at run time or anything like that but we might want them to behave in a way a little more like variables. That is, we want them to obey reasonable scoping relationships. In a lexically scoped language, for instance:

(let ((x 10)) (lambda (y) (+ x y)))

The x inside the lambda will always refer to the x bound in the enclosing let expression. If you want to check the value of an expression that uses that lambda, you don't have to understand the whole history of the symbol x throughout the program. You just need to know the value passed in (y), and then go look at the lexical context of the lambda to see what x is.

What if we could invent a macro system where this was true of macros? Where the meaning of a macro could be determined by looking at the inputs at the location of macro expansion, but then only look at the macro definition, and its lexical context, to understand what the expansion means?

Extending Our Code Representation

Most Lisps represent code as a list of atoms and lists. This is fine for most things, but we've discussed at length how this representation makes macro expansion problematic. Scheme extend their code representation to include extra information, most interestingly about the lexical context of a piece of code. Code, then, is represented as syntax objects.

In Racket, the Scheme(+) implementation I recommend for fiddling with Scheme, you can see this explicitly. The quotation operator still produces naked code:

> 'x ;-> x

But the sharp quote operator, short hand for syntax, produces syntax, which is a data object which contains (abstractly) lists of atoms and lists, but decorated:

> #'x -> #<syntax:11:10 x>

(Note that #' used in this way is specific to Racket).

Syntax, unlike the raw code representation of other Lisps, contains information about the lexical context and binding of symbols.

The Racket printer shows a little of the information associated with the syntax (line number, it appears), but lots of other information is stored. Racket macros transform and produce syntax, not raw lists. Except for this fact, they are the same as defmacro style macros. You may have heard people say that you can't write Scheme macros in Scheme (as you write Lisp macros in Lisp), but this isn't really true. Syntax transformations have to produce and consume syntax, but otherwise are unrestricted. It is true that Schemes vary in the degree to which you are provided tools to arbitrarily manipulate syntax, but that is at least partly a separate issue.

Introducing New Syntax

Scheme provides an operation, define-syntax, which informs the system that a symbol should be associated with a new syntax transformer. This is the equivalent of defmacro in other Lisps. It has the form:

(define-syntax <symbol> <syntax-transformer-expression>)

The first symbol is equivalent to the name of the macro in defmacro lisps. The second expression must be a piece of Scheme code that generates a syntax-transformer which is a regular function (as we shall see) that must take and return syntax¹. After executing a define-syntax, if the <symbol> is detected during macro-expansion, its contents are passed to the syntax transformer, and the results are stitched back into the code.

Simple Tools Help Maintain Hygiene

So how do we write new syntax-transformers? In Lisp, we just use the list manipulation functions, quasiquote and unquote, to take apart and build up our new source code. Schemes provide equivalent procedures for syntax objects, but most macros are simple enough to be written in a high-level form which helps maintain hygiene automatically. There are many ways to do this, the simplest of which is syntax-rules.

First in words: syntax-rules is a form which takes a series of patterns and expansions and produces a syntax-transformer which examines syntax until a pattern matches and returns the associated expansions. Critically, when a pattern is matched, the parts of the pattern are bound to pieces of syntax which can be used in the expansion. Let's do let*, like we did last time:

(define-syntax my-let*
 (syntax-rules 
  [(my-let* () body ...)
   (begin body ...)]
  [(my-let* ((id expr)) body ...)
   ((lambda (id) body ...) expr)]
  [(my-let* ((id0 expr0) (id expr) ...) body ...)
   ((lambda (id0) (my-let* ((id expr) ...) body ...)) 
    expr0)]))

I think people find syntax-rules confusing, when coming from defmacro, because it handles a lot of things for you. For one thing, the fact that this expression is a syntax transformer isn't as obvious as it could be, but think of syntax-rules as an expression which returns a function, which is exactly what it is. That isn't so odd!

But syntax-rules also handles pattern matching for you and binding the results of that matching to pieces of syntax in the expansion expression. On top of that, neither the pattern nor the expansion constitutes regular Scheme code. Each is, in fact, its own unique, but related, domain specific pattern language, a bit like a regular expression match and replacement language for syntax.

Let's look at each specific pattern and its expansion. The first pattern handles the case where someone invokes a my-let* binding expression without any bindings. It matches a piece of code which looks like:

(my-let* () body ...)

There is a piece of that domain specific pattern language in this code. The expression body ... tells syntax-rules to match zero-or-more forms of arbitrary structure and bind them to the pattern body ... in the expansion part of the clause. Since we aren't doing anything with the body we don't care if it is there or not, since we handle it the same way. We expand this clause into:

(begin body ...)

Here body ... now refers to a piece of bound syntax produced by the pattern part of the expression. When the expansion is expanded, it will contain whatever was matched to body ... in the pattern, which might be nothing.

The next clause's pattern is:

(my-let* ((id expr)) body ...)

Here we instruct the pattern language to only match when the binding part of the let contains one two-element list which should be an identifier and an expression (we will have to think about error checking later). The identifier is bound to id, the expressions is bound to expr. body ... is bound as above. The expansion is given as:

((lambda (id) body ...) expr)

Because id, body ..., and expr were bound in the pattern, they have special meaning in the expansion. The symbol lambda, however, is a piece of syntax which is corresponds to the currently operating lambda syntax. Note that syntax-rules is basically handling automatically what we would have done manually with gensym and quasiquotation/unquotation.

At the risk of being tedious, lets look at the final pattern. It doesn't contain anything new, but it does highlight some of the strategies often encountered in writing this kind of syntax transformer. The pattern is:

(my-let* ((id0 expr0) (id expr) ...)
         body ...)

Here, var0 and expr0 are bound to the first id/expr pair. We write out the first explicitely for two reasons. The first is that (id expr) ... matches zero or more expressions, and we want at least one. The second is that we need to split up the id and the expr part of our match and insert the ... rest of them somewhere else. You can't do this with the pattern ... match, which must appear in the expansion as pattern .... We could write:

(my-let* ((id0 expr0) binder ...)
    body ...)

of course, but by specifying a more concrete match we make our macro a little bit better in terms of robustness. We really want at least a pair in each binder position, so we say so directly.

We expand this pattern as:

((lambda (id0) (my-let* ((id expr) ...) body ...)) expr0)

Which should be understandable enough. The main thing to note is that we are recursively expanding this syntax-transformation with calls to itself. Because syntax-transformations often represent purely functional computations on input syntax, recursion is a common (and elegant) strategy.

The Scheme universe offers other forms that allow more complex macro expansions, but they all owe a lot to the basic shape of syntax-rules.

Shortcomings of Syntax Rules

The standard way of demonstrating the shortcomings of syntax-rules is by trying to write an anaphoric if macro. Anaphoric if is a macro that binds the result of its predicate part to a variable, which is available for use inside either branch expression (often the symbol it is used for this purpose). Since you've read Part 1 and Part 2, I can just explain this by writing the appropriate macro in Common Lisp:

(defmacro anaphoric-if (pred true &optional false)
 `(let ((it ,pred))
    (if ,it ,true ,false)))

Simple! The utility of the macro is related to the fact that if treats lots of things other than just booleans as true. Imagine you have a function which processes a command entered by the user. The command is returned by the function get-command. If the user just pressed enter, nil is returned.

(anaphoric-if (get-command) (handle-command it) nil)

it contains the result of get-command. Our macro has captured the symbol it and is using it for its own purposes. If we already had an it in scope, this might be inconvenient (and, in my opinion, there are lots of things wrong with this kind of macro, but some people are into it). Misgivings about variable capture aside, it is easy to write this variable capturing macro in Common Lisp, and it behaves just as we expect it to with our filthy, untutored brains.

We might try to write this macro using our new knowledge of syntax-rules like so:

(define-syntax anaphoric-if
 (syntax-rules ()
  [(anaphoric-if pred true false)
   (let ((it pred))
     (if it true false))]))

But if we attempt to use this syntax-transformer, we'll quickly run into problems:

(anaphoric-if 10 (format "it is ~a~n" it) #f)
  . . reference to an identifier before its definition: it
  >

We expected the string "It is 10\n", but we got an error! What is happening is that syntax-rules is trying to protect us from ourselves. Inside the expansion we introduce a piece of syntax, it. It isn't, however, simply a symbol - it is syntax, and its metadata tells the Scheme system that its scope is limited to the macro expansion context. We can use it as the predicate spot in our if statement, but any it symbols appearing in the expressions matched to true or false will only be superficially similar. The Scheme system will know that the its in those expressions are different than the one we create in our macro expansion. Hence, when the evaluator encounters it in one of our branches, it checks that symbol's original lexical context (in our example, the top-level binding environment) for a binding, which it doesn't find. Hence the error.

We can approach the solution in two ways (at least). The first is to force the user to provide the symbol name herself. Scheme will then know that the symbol, whatever it is, is meant to be the same for all appearances in the expansion:

(define-syntax named-anaphoric-if 
 (syntax-rules () 
  [(named-anaphoric-if id pred true false)
   (let ((id pred))
     (if id true false))]))

Or we can try to tell scheme we want to capture the symbol it. I don't know of any way to do this with syntax-rules, although I suspect that if you really wanted to bend over backwards, there might be some way. We need something else! Plus, there are lots of other idioms, not just the ugly duckling variable capture, which are hard to express in syntax-rules. Hence, Schemers cooked up...

Syntax-case

Before we talk about syntax-case I want to emphasize that both syntax-rules and syntax-case are just tools that produce syntax-transformers. Their unusual, domain specific languages are meant to make writing transformers correctly easier, but they are not, themselves, the Scheme macro system. They are just tools built on top of that system. The underlying system is much like the one in defmacro Lisps, except it transforms syntax, not lists.

syntax-case looks a lot like syntax-rules. Here is how you'd write the named-anaphoric-if in syntax-case:

(define-syntax named-anaphoric-if* 
  (lambda (stx) 
    (syntax-case stx ()
      [(named-anaphoric-if* id pred true false)
       (syntax (let ((id pred))
                 (if id true false)))])))

Almost identical. Sharp eyed readers will not that the expansion has been wrapped with a syntax expression, which tells the environment to evaluate the contents contained therein as syntax, which means automatically handling any syntax bound by the pattern match. We also have to wrap syntax-case in a lambda, which is the syntax-transformer proper. Unlike syntax-rules, which is a form resulting in a syntax-transformer, syntax-case merely transforms syntax. It does not produce a transformer itself.

However, since the expansion part of syntax-case clauses is not automatically interpreted as syntax, it allows us to finagle the matched syntax manually. Turns out this is just what we need to "capture" a variable. Here is how we do it:

(define-syntax anaphoric-if** 
 (lambda (stx)
  (syntax-case stx ()
   [(anaphoric-if** pred true false)
    (with-syntax ([it-id (datum->syntax (syntax true) 'it)])
     (syntax 
      (let ((it-id pred))
       (if it-id true false))))])))

So this is a syntax-case expression with one clause, which matches things like (anaphoric-if** a b c). The next part of the clause must return a piece of syntax, but it can do any arbitrary scheme activity to produce that syntax, unlike syntax-rules. The expression with-syntax allows us to introduce an environment with new syntax-bindings in addition to those produced by the match expression. We use it to introduce a binding to it-id. This means we can use the expression it-id inside our expansion (within the with-syntax body) and it will be interpreted correctly by syntax expressions. How do we actually create a new piece of syntax, though? The function datum->syntax takes a piece of data (in our case, the symbol it) and transforms it into a piece of syntax. But syntax contains much more information than just its value, and some of that information determines how it is interpreted during macroexpansion and subsequent compilation. datum->syntax allows us to pass in, as the first argument, a piece of syntax from which we will clone that additional information. Since we want to let it operate in the same environment as the true and false clauses, we clone the syntax-metadata from the true branch. We then return a piece of syntax corresponding to our entire expression. Again, syntax automatically handles the equivalent of quasi/un-quotation as we might do it in Lisp. It looks at the syntax bindings which are active and automatically interpolates them. We can now say, with a straight face:

(anaphoric-if** 10 it it)

And get 10, as we expect to. We now know how to write selectively-non-hygienic macros. Go us.

Recapitulation

We started, back in Part 1 by talking about dynamically scoped Lisps where code was always written and executed in the most obvious way possible. These Lisps maybe have been difficult to write programs in, or at least unfamiliar to modern Lispers and programmers at large, but they did have one thing going for them: their treatment of code/data was so simple that special forms could be treated identically with functions. These so-called fexprs could choose when to evaluate their inputs because they put the onus of maintaining various bindings to a single symbol on the user.

In these languages, macros were often considered to be less useful than fexprs, and why not? We could see when we looked at the defmacro Lisps shared some problems which, if not really a problem in practical use cases, at least left us philosophically unsettled. Macros could easily be written which unintentionally captured variables, they were not first class, and didn't follow regular lexical binding rules. In exchange for these shortcomings, we did get macros which were almost as nice as fexprs and worked better in lexically scoped languages, because they forced us to emphasize the fact that macro-expansion occurs before execution. Tools like gensym and packages/namespaces helped us avoid the worst hygiene problems.

And so we've finally arrived at Scheme, were macros, now called syntax-transformers work not on an undecorated representation of Lisp code, as they do in defmacro lisps, but on syntax, a code representation where information about context and binding is represented as well. Adding this additional representation to the code allows forms like syntax-rules to automatically handle syntax transformation for us while maintaining hygiene.

Finally, we grudgingly admitted that people somewhere might want to intentionally violate hygiene, and introduced the syntax-case expression, which allows the user to manipulate syntax-objects to the end of capturing variables and the like.

Back Matter

If all you care about is Lisp, then we've reached the end of this series on syntax. However, discussions with a reader, Dru Nelson, compel me to mention The Factor Language as something of a conceptual digestif. Factor is a concatenative language which has many similarities with Lisp, which puts it in the odd category of being more Lispy than Lisp in many respects.

Factor, for programmers unfamiliar with concatenative languages, in its ordinary operation, does not have variables: values are passed between subroutines (called "words") on a data stack. I strongly encourage readers to download Factor and give it a spin - I find writing Factor programs to be delightful mental calisthenics. Here is how you calculate (3 + 13) * 6 in Factor:

( scratchpad ) 3 13 + 6 *

--- Data stack:
96

A Factor program is, apparently, a flat list of "words" with data flow handled implicitly. What is the equivalent of a "lambda" expression in such an exotic language? Well, its just a list! Since there are no named things except for words, a list of the words (and literals, which can be thought of as words which "push" themselves onto the stack) which make up a subroutine is all you need or can have. In Factor, code really is data and execution of that code is even simpler than it is in dynamically scoped languages. You can't even make the common mistakes of dynamical languages respecting variable binding because, well, you don't have variables. You don't need to write Macros, such as we have them in Lisp, in Factor, because your functions are free to shuffle around, decompose, build and partially evaluate quotations to their heart's content².

Factor goes one step further towards simplicity than even picoLisp - it completely eliminates variables, and as such, data becomes even closer to code than it is in that language.

More Lispy than Lisp indeed!

¹ I'm pretty sure that syntax, as (essentially) a wrapper for data, is a monad, but that is definitely another story.

² Factor actually requires that quotations have infer-able stack-effects, which places limitations on them in practice (surprisingly few, though!)

On Discovering Programming, Age 12

2011-08-12T17:26:00.000-07:00

I discovered at once a parallel
eroticism. New and strange, unknown,
fumbling, my mind hardly able to tell
what subtle provocations meant, shown
in stipled fading purple, inkjet blown,
on pages already aged when I first
touched them and, virginal, brought them home.
Like the child I was I struggled to birth
new sensuous faculties, learned to perch
full, on the edge of abstract orgasms.
To caress the invisible shapes, to lurch
towards clasping ideas in ersatz spasms.
I still remember my naive eros,
from which a lifetime of pleasures arose.

A Survey of Syntactic Extension Techniques in the Lisp Family of Languages (Part 2)

2011-08-11T08:44:00.000-07:00

Last time we began our survey of syntactic extension technqiues in Lisp with a rather airy meditation on syntax, quotation, evaluation and lambda, all by way of picoLisp's unusual dynamic, interpreter oriented semantics. Very briefly, we looked at the way picoLisp lets regular, first class, functions specify that certain arguments should be passed in unevaluated, which the function can then selectively evaluate. Because the language is dynamically scoped and interpreted, this gets you as far as macros, and a little farther (since even "special forms" are first class).

This time, we're going to attempt to be a little more direct in our survey. But we should still think a little bit about macros before we jump in. In the Lisps we'll talk about today, syntactic extension is handled via macros. Given the flexibility of the picoLisp approach (also known as fexpr's, and also supported by newLisp, which is itself an exotic species I might write about later), you might wonder why we'd want to use macros. The principal obvious disadvantage of macros is that they are not first class objects, they can't be stored in variables or passed around, whereas picoLisp style functions/special forms are. There are lots of reasons they were abandoned, but one easy one to see is that macros make separating different stages of program interpretation and execution a bit easier.

Consider executing an fexpr. In order to correctly calculate the value of such a first class function, we need to remember not just the flow of values from one function to another, we also have to know the syntax of all the inputs. Much of the efficiency of compilation is in the ability to disregard this information, and reduce the program to a series of simple, primitive, operations. If our language is lexically scoped, then, in addition to remembering the syntax of the inputs, we also need to know the context of that syntax in order to correctly evaluate it. I'm surely oversimplifying things here, but you can read about the problems with fexpr's here (the commentary on this subject at Lambda the Ultimate is also great)¹. Kazimir Majorinc, by the way, has written a rebuttal of Pitman's original concerns. I have to admit, I find newLisp in particular to be a fascinating case study in alternative approaches to Lisp and computer programming languages in general. More people should try it out!

If we stage our syntactic extensions, as in more modern/typical Lisps, after program reading, but before execution, it simplifies the design of our compiler/virtual machine/interpreter. The macro systems we'll be discussing today operate in this way, transforming an intermediate form of Lisp code, produced by the reader, before finally handing the result to the compiler. The upside is the compiler need only concern itself with the behavior of basic lisp and its small set of special forms. The downside is that macros are stuck working only on source code: they cannot, in general, know anything about runtime, as the code has not yet been run!

The Arc Documentation has something rather insightful to say about this:

Macros live in the land of the names, not the land of the things they refer to.

So, today we'll be looking at macro systems by which the user declares that certain symbols indicate to the intermediate processing step of the language that some portion of code should be transformed by a specified piece of code and the result inserted back into the code representation where the macro appeared.

Business Time!

Macro syntax can be a bit confusing when you see it for the first time. It is useful, then, to consider what a macro might do rather than how it is written, first. Macros should almost always transform code into code, with no side effects along the way, and so we can understand a macro by writing the code before and then the code after macro expansion.

If you know some Lisp, you know that variables are introduced with let epxressions. Each binding expression in a let is executed without any of the other bindings in scope, so:

(let ((x 10)
      (y (+ x 1)))
    (+ y x))

Will produce an error, because x is not visible until the body portion of the let expression. If you want to nest references to new variables, you need let*:

(let* ((x 10)
       (y (+ x 1)))
   (+ y x)) ; -> 21

Which does work. Let's write a let* macro as an example. Expressions like let* are all about [binding][], and that means we can use lambdas to express let*. We want:

(my-let* ((x 10)
          (y (+ x 1)))
      (+ y x))

To expand to:

(funcall (lambda (x) 
   (funcall (lambda (y) (+ y x)) (+ x 1)))
   10)

Take a second to think about it, if you don't see why. The basic insight is that lambda can be used to introduce a context where a variable is bound, and funcall binds that variable.

The transformation of some code A to some other code B is the action of all but a few exotic macros. This transformation happens, conceptually, before any code is run (in practice, because many Lisps favor interactive development, macro expansion might occur after the user has executed some code, but it is highly unusual, and probably an error, for the macro expansion itself to depend on the results of previous execution (except that the macro may use previously defined functions to effect the code transformation)).

Let's write the macro, this time in Emacs Lisp:

(defmacro my-let* (bindings &rest body)
  (cond 
    ((empty? bindings) (cons 'progn body))
    (t
     (let ((pair (car bindings))
           (leftover-bindings (cdr bindings)))
      `(funcall 
         (lambda (,(car pair))
           (my-let* ,leftover-bindings ,@body))
         ,(cadr pair))))))

(my-let* ((x 10)
          (y (+ x 1)))
     (+ y x)) ;-> 21

We need to say a bit about quasi-quotation to really understand how this works, but there are some things we can explain right away. Emacs Lisp represents code as a list of symbols, other atoms, and lists. When my-let* is encountered, the source code after my-let* in the code is passed, as a list, into a function (implicitly defined by the defmacro statement. This list is destructured by this function using regular old argument specification (so that the first item in the list is bound to bindings and all the subsequent items are bound to body, in a list) and then the body of the defmacro is executed. It's result must be a piece of code, which is inserted wherever the macro appeared in the source code representation.

Let's focus on the first possibility, when the macro is called with an empty set of binding forms. Our code is:

(my-let* () "Hey there.")

This is slurped up into the Lisp interpreter as:

(list 'my-let* '() "Hey there.")

The interpreter sees my-let* and knows that this indicates a macro. To expand this macro, it calls a function based on the defmacro expression. This function doesn't have a name, but we can write what it would look like:

(defun -my-let*-expander- (binders &rest body)
   (cond 
    ((empty? bindings) (cons 'progn body))
    (t
     (let ((pair (car bindings))
           (leftover-bindings (cdr bindings)))
      `(funcall 
         (lambda (,(car pair))
           (my-let* ,leftover-bindings ,@body))
         ,(cadr pair))))))

The macro expanding part of the lisp system calls this function with the following arguments:

(-my-let*-expander- '() "Hey There")

This function returns:

'(progn "Hey There")

And the macro expanding part of the lisp system inserts that expression, whole hog, so to speak, into the place where the original form starting with my-let* was located. It then moves on. Once all the macros are expanded, the code is passed to the compiler/interpreter/etc and then executed. Viola!

Voila!

To understand the other branches, we need to cover a feature which appears in most lisps: quasiquotation.

Macros & Quasiquotation

Lisps, more or less, represent code internally as lists or/of atoms (things like numbers, strings, symbols). The code x represents, more or less, a piece of code that evalutes to the value of the symbol x. The list (+ x 1) is the piece of code that evaluates to the value of symbol x plus one. We covered last time how to enter these unevaluated pieces of code into a running lisp session using quotation. The quote operator tells a Lisp not to evaluate whatever it is applied to. So:

(setq x 10)
x  ;-> 10
'x ;-> x
(+ x 1) ;-> 11
'(+ x 1) ;-> (+ x 1)

Quote is ok when we want to write a tiny bit of code-as-data, but when we write macros, we often want to interpolate between data and code in a more dynamic way. We could, of course, use list to create our code:

(list '+ 'x 10) ;-> (+ x 10)

Because list is a function, each argument is evaluated - we quote manually whatever arguments we want to leave unevaluated as we construct our code.

Quasiquotation is kind of the opposite of list. A quasiquoted expression, by default, doesn't evaluate its inputs except when they are unquoted. Quasiquote is indicated by the back-quote character:

And, within a quasiquoted form, unquotation is indicated by a ,, which kind of makes sense. Quasiquotation works pretty much identically in Emacs and Common Lisp, so fire one of them up and try it out. You can use quicklisp to install Common Lisp quickly.

`(+ x ,(+ 10 11 12)) ;-> (+ x 33)

Should work in either Common Lisp or Emacs. Note, however, that different Lisps handle symbols slightly differently. In SBCL, a Common Lisp implementation, 'x will evaluated to X, and symbols are not case-sensitive by default. Symbols are case sensitive in Emacs Lisp.

Sometimes you want to interpolate the contents of a list into a piece of code, in which case you say ,@ instead of ,:

`(+ ,@(list 1 2 3)) ;-> (+ 1 2 3)

Without concerning ourselves with namespaces or packages (of which Emacs has neither) Clojure macros operate in the same way as Emacs/Common Lisp macros, but with some slight changes in the way operations are indicated:

(defmacro my-let* [bindings & body]
  (cond
   (empty? bindings) (cons 'do body)
   :else
   (let [[symbol value-expr & leftover-bindings] bindings]
     `((fn [~symbol] (my-let* ~leftover-bindings ~@body))
       ~value-expr))))

This piece of code reads just like the Common/Emacs Lisp except for a few details. The first is that the argument list to the macro is specified using a Clojure vector rather than a list. Unlike in Common/Emacs Lisp, the default Clojure reader is able to read more than lists and symbols. The [] syntax indicates a Clojure persistent vector. It is read into the code representation as a vector, rather than as some kind of list or atom. This is both an important and a trivial difference. Consider in Emacs Lisp:

(vector 1 2 3)

This indeed evaluates to a vector with elements 1 2 3. But it is read as a list whose head is the symbol vector. Only upon evaluation do we get a vector.

(vectorp '(vector 1 2 3)) ;-> nil
(listp   '(vector 1 2 3)) ;-> t

In Clojure, by contrast:

(vector? '[1 2 3]) ;-> true
(list?   '[1 2 3]) ;-> false

(But see this footnote:²).

(As an aside, Clojure also supports tables as part of its code representation, in keeping with its intent of expanding Lisp's philosophy to data structures other than lists.)

In Clojure, do is how you say progn, both of which introduce a form which evaluates all its parts, and returns the result of the last. Next, we follow the convention that redundant parentheses in Clojure should be elided. Because we know bindings contains a list of pairs, we just read that list by two, rather than as an actual list of pairs. You see this in Clojure's let form, which has one less layer of nesting.

Emacs:

(let* ((x 10) (y 11)) (+ x y))

Clojure:

(let [x 10 y 11] (+ x y))

(Note that picoLisp also elides redundant parentheses, but does not use vectors for binding, also note that Clojure doesn't have let*, let has that behavior).

Also by convention, we use vectors for the binding part of any form (although this macro doesn't check for that). We say fn instead of lambda in Clojure, and we use ~ for the unquote operation. In Clojure, ~@ is the way you say ,@.

Other than those differences, the Clojure macro has the same behavior as the Emacs/Common Lisp Macro. It creates an invisible function which is used to expand code tagged with that macro name during post-read processing, and then the code is passed to the Clojure compiler. It is worth noting here that Brian Goslinga has ported Scheme-style syntax-case/rules macros to Clojure, but it isn't clear to me without further study whether they truly are hygeinic. Claims of macro hygiene are often exagerrated outside of the Scheme universe.

Issues with Naive Code-Rewriting Macros

The best way to understand the motivation for Scheme hygeinic macros, as well as some of the differences between more or less conventional macro systems in other Lisps is to understand how things can go wrong. Last time we talked extensively about scope and how it effects the way we look at a piece of data that represents code. The upshot was that in languages where scope is dynamic, which means variables evaluate to whatever the current binding of the variable is at the moment of evaluation, can simply represent code (and particularly the meaning of symbols) as just lists of atoms and symbols. A piece of code "means" whatever it is you get by evaluating it in the context of the current bindings from symbols to values. Period.

Lexically scoped languages, on the other hand, impose more strenuous semantics on code. In a lexically-scoped language, variables refer to the lexical environment (the environment around them "on the page") when they are evaluated. Hence, in a lexically scoped language, a "naked" piece of code, such as the code produced by quotations, is "impoverished" - it doesn't record in any way the lexical environment in which the quotation was created, and so it is, in some sense, "meaningless," at least the extent that it contains symbols which aren't bound.

In a dynamic language, the code fragment consisting of the single symbol 'x means "Whatever value x has when you evaluate me." This representation is complete, but depends on the evaluator. In a lexically scoped language, where symbols, when they appear in code, are implicitly associated by the rules of evaluation with a lexical context they were originally created in, 'x is meaningless. It looks like a piece of code, but in a real sense it isn't quite one.

Emacs/Common Lisp/Clojure style macros, however, operate on pieces of "code" produced by ordinary quotation - that is, they operate on "hypocode," say, which just means something not quite code.

Making a Mess

Let's make a mess, by way of example. Suppose we have an object system wherin objects are collections of key -> value relations in a persistent data structure, like an association list³. We will work in Emacs/Common Lisp.

Preliminaries:

(defun empty? (x)
  (eq x nil))

(defun set-slot (obj symbol val &optional acc)
  (cond 
   ((empty? obj) 
    (cons (cons symbol val) (reverse acc)))
   (t
    (let* ((first (car obj))
           (o-key (car first))
           (rest (cdr obj)))
      (if (eq symbol o-key) 
          (append (reverse acc) (cons (cons symbol val) rest))
        (set-slot rest symbol val (cons first acc)))))))

(defun get-slot (obj symbol)
  (cond
   ((empty? obj) nil)
   ((eq (car (car obj)) symbol)
    (cdr (car obj)))
   (t
    (get-slot (cdr obj) symbol))))

(get-slot (set-slot (set-slot (set-slot '() 'x 10) 'x 11) 'y 14) 'y)

Methods will just be functions whose first argument is the self object.

(defun make-person (first last) 
  `((:first-name . ,first)
    (:last-name . ,last)))

(defun change-first-name (self new-first)
   (set-slot self :first-name new-first))

(defun change-last-name (self new-last)
   (set-slot self :last-name new-last))

(note the use of backquote outside of a macro.)

Our objects are "pure" in this example - the methods change-first-name and change-last-name don't modify self, they return a fresh self object with the appropriate changes. I prefer this behavior, but it makes chaining method application clumsy. We'll develop a macro to make method chaining for pure objects easier.

I don't know the Bionic Woman, but she comes up when you google "Woman".

I know a woman who changed both her first and last names when she got married. She went from Ami Culbert to Amy Klein (she had always resented her parents for the unusual spelling of her first name). We've got to nest our method calls or use a let to affect both renamings:

(let ((new-self 
       (change-first-name (make-person "Ami"
                                       "Culbert") "Amy")))
   (change-last-name new-self "Klein"))
 ; -> ((:first-name . "Amy") (:last-name . "Klein"))

Let's write a macro which automatically threads an object through method invokation. It should expand:

(with-object o 
  (change-first-name "Amy")
  (change-last-name "Klein"))

into something like:

(let ((new-self 
       (change-first-name o "Amy")))
   (change-last-name new-self "Klein"))

People often complain, inaccurately, I think, that macros are "hard to debug" because they aren't regular functions. It is true they aren't invoked as regular functions in the ordinary course of events, but one can certainly write the "business end" of the macro as a regular function and just have the macro definition pass the quoted inputs to this function appropriately. Then you can interactively test the macro expansion, build unit tests, etc.

(defun with-object-expander (object-expr method-applications)
  `(let* ((object ,object-expr)
          ,@(mapcar 
             (lambda (methap) 
               `(object (,(car methap) object ,@(cdr methap)))) 
            method-applications))
        object))

(with-object-expander 'test-object 
 '((change-first-name "Amy")
   (change-last-name "Klein"))) ;-> 
  (let* ((object test-object) 
         (object (change-first-name object "Amy")) 
         (object (change-last-name object "Klein"))) 
     object)

If you are new to Lisp macro writing, this probably looks like it works just fine. If you are a hoary old Lisper (and I know some of you are), then this probably looks like one of those ridiculous examples from safety videos where a goofy guy climbs up a ladder, or some such, with an aerial around some high tension power lines, which is exactly what it is. Let's sally forth like Goofus, however:

(defmacro with-object (object-expression &rest method-exprs)
  (with-object-expander object-expression method-exprs))

(with-object (make-person "Ami" "Culbert")
  (change-first-name "Amy")
  (change-last-name "Klein")) ; -> 
   ((:first-name . "Amy") (:last-name . "Klein"))

Goofus probably programs in Perl. Just sayin'.

Indeed, apparent success! However, imagine if we are instead taking the new last name from an object representing Ami's fiance:

(let ((object (make-person "Jason" "Klein")))
  (with-object (make-person "Ami" "Culbert")
    (change-first-name "Amy")
    (change-last-name (get-slot object :last-name)))) ; ->
  ((:first-name . "Amy") (:last-name . "Culbert"))

What gives? Amy's last name should be "Klein" but it is stil "Culbert". What happened? A quick look at the macro expansion of the entire expression would help, but how do we get such a thing? Emacs/Common/Clojure Lisps provide macro-expansion tools which take an expression and expand macros inside of it:

(macroexpand-all 
 '(let ((object (make-person "Jason" "Klein")))
  (with-object (make-person "Ami" "Culbert")
    (change-first-name "Amy")
    (change-last-name (get-slot object :last-name))))) ;->

    (let ((object (make-person "Jason" "Klein")))
      (let* ((object (make-person "Ami" "Culbert"))
     (object (change-first-name object "Amy"))
     (object (change-last-name object 
               (get-slot object :last-name))))
     object))

Now we can see what the problem is. We bound Amy's fiance to the symbol object, but our macro expansion also used that symbol internally, to represent the object being threaded through the method applications, which means it was bound to the Amy person by the time the call to get-slot was executed on object. Amy's last name was just her last name, so the change-last-name call changed nothing!

Note that this is, essentially, an error of context or variable interpretation. Our mental model was that the object symbol used during macro expansion was unrelated to the object symbol used in the subsequent let expression. But the Lisp has no way of knowing that. Because we are manipulating naked code, a symbol is just a symbol, and the behavior of our complete expansion is just whatever behavior it looks like it would have if someone had written it by hand. Scheme's macro system is designed to resolve this problem by separating contexts more aggressively, so that macro expansion doesn't get in the way of later variable binding unless you specifically want it to.

We don't, however, have hygeinic macros in the Lisps we are talking about today, so how do we avoid the problem specified above? There are at least two ways which are in common use. The first is to force the invoker of a macro to provide any names which might be used during expansion, so they are forced to acknowledge that those names will be rebound by the macro. The second is to make sure that the macro uses symbols which you are certain will never be used by the programmer who invokes the macro.

The former strategy looks like this:

(defmacro with-object-bound-to (sym obj &rest meths)
  `(let* ((,sym ,obj)
          ,@(mapcar
            (lambda (m)
              `(,sym (,(car m) ,sym ,@(cdr m)))) 
            meths))
        ,sym))

Invoked as:

(let ((object (make-person "Jason" "Klein")))
      (with-object-bound-to amy 
        (make-person "Ami" "Culbert")
        (change-first-name "Amy")
        (change-last-name (get-slot object :last-name))))

Which has the intended effect. However, if you don't intend on using the value bound to amy at any time, you'd probably prefer regular old with-object.

We could implement with object by just trying to use a crazy symbol for object, something we'd hope the users of our macro will never think to use. For instance, we could prepend the letter s to the md5 hash of the word "object": sa8cfde6331bd59eb2ac96f8911c4b666:

(defun with-object-expander (object-expr method-applications)
  `(let* ((sa8cfde6331bd59eb2ac96f8911c4b666 ,object-expr)
          ,@(mapcar 
             (lambda (methap) 
               `(sa8cfde6331bd59eb2ac96f8911c4b666 (,(car methap)
  sa8cfde6331bd59eb2ac96f8911c4b666 
  ,@(cdr methap)))) 
            method-applications))
        sa8cfde6331bd59eb2ac96f8911c4b666))

And that would probably work. However, Lisps usually provide a facility to generate symbols guaranteed not to be used (subject to the understanding that if symbols are read at run-time, all bets are off - althouh it is still unlikely there will be a problem). In Common and Emacs Lisp, this is accomplished via the function gensym. In these Lisps, we'd write:

(defun with-object-expander (object-expr method-applications)
  (let ((object-name (gensym "object-")))
  `(let* ((,object-name ,object-expr)
          ,@(mapcar 
             (lambda (methap) 
               `(,object-name (,(car methap) ,object-name ,@(cdr methap)))) 
            method-applications))
        ,object-name)))

The critical points are that we've introduced a variable object-name which, at macroexpansion time, is bound to a fresh symbol. We then insert that symbol wherever object used to be by unquoting it into out expanded expression.

Turns out this feature is so commonly used that Clojure provides special support for it - during backquote expansion, symbols terminated with a # character are automatically bound to appropriately generated symbols. By appropriate we mean that object# will always be expanded to the same symbol within a single backquote. In this example, since some of the uses of the object symbol are generated programmatically, we'd still need to use gensym, which Clojure also provides.

Namespaces, Packages, Hygiene

All this gensym falderal is meant to help us ensure our macros are hygienic, which informally means that in the body of a macro, the code you write behaves the way you expect it to behave, modulo whatever changes in meaning the macro implies AND that when the macro expands, it means what the macro writer meant it to mean, regardless of what symbols mean where the macro is expanded.. Variable capture, the example we looked at above, is only one of many possible hygiene complications. Another possibility is that a macro (the dependent macro, lets call it) might depend on another macro, which itself is defined one way when the dependent macro is written, but might be redefined later when someone else tries to expand the dependent macro. It's very hard to write macros that are hygienic in this sense in the Lisps we've talked about so far, but some of them do provide the faculties to at least help a bit.

Emacs Lisp is the oddball in this department, however - it has neither packages or namespaces or any other module system⁴.

Both Clojure and Common Lisp provide some conception of modules or bags of symbols. In Common Lisp these are called packages, in Clojure they are called namespaces. In both cases, macro writers can use namespaces to help avoid macro expansion problems. Consider the case where some joker redefines the let* special form. Your macro wants to use let* as it is ordinarily defined by Common Lisp. He wants to use your macro, but wants to put code in it that depends on his crazy new definition of let*. If you write your macro (expander) as:

(defun with-object-expander (object-expr method-applications)
  (let ((object-name (gensym "object-")))
  `(cl::let* ((,object-name ,object-expr)
                ,@(mapcar 
             (lambda (methap) 
               `(,object-name (,(car methap) ,object-name ,@(cdr methap)))) 
            method-applications))
        ,object-name)))

You can have your cake and the user of your macro can eat it too. The key changes is that we've qualified our let* symbol with the package it lives in. cl::let* means we want Lisp to use the meaning of let* as defined in the package cl or common-lisp (packages can have nicknames in Common Lisp). If our user redefines let* in his own package, then he can use our macro without any problems.

Clojure takes this one step further. Backquote automatically expands symbols to their namespace-qualified names, so macros automatically expand to refer to the special forms as defined in whatever namespaces they are defined in when the macro itself was defined. Material unquoted into the macro expansion is expanded appropriate to the context it was introduced in. The net result is that someone redefines let in their own package, and calls your macro, it automatically expands to use the let from the base Clojure package:


`(let [x 10 ~'y 11] (+ x y)) ;->
 (clojure.core/let [user/x 10 (quote user/y) 11] 
    (clojure.core/+
       user/x 
       user/y))

I haven't specifically mentioned Arc throughout all this, but Arc macros basically follow the same design as those in Common/Emacs Lisp and Clojure. If they are more similar to any of the above than any other, it is Emacs Lisp, since Arc doesn't appear to have, at the moment, a namespace or package system.

Conclusions

Good Lisp programmers use macros sparingly, for the most part, and so it is difficult to think up examples when you'd need more macro hygiene then what you get in Lisps with gensym and packages and namespaces. In particular, Clojure seems to provide enough protection that you won't accidentally shoot yourself in the foot unless you wander off the beaten path.

However, you might wonder if we can't come up with a more formal syntactic extension scheme which really protects us in a simple to understand way. Something that makes macro hygiene as easy to conceptualize as variable hygiene for regular code? There are lots of ways to approach this problem (more than I know of, certainly) but next time we'll discuss the way Scheme does it. Scheme syntax-rules/case macros are very different compared to defmacro style forms, and their intent is to make hygiene the default behavior, so that complex macros (that, for instance, depend on one another) can be defined easily without much extra manual fiddling (gensym, packages, etc). As we'll see, the solutions are related to the difference between lexical and dynamical behaviors, a theme which keeps coming up!

¹ See also Kernel.

² I must point out that Emacs Lisp, but not Common Lisp, has a similar read syntax:

[a b c] ;-> [a b c]

Which is sort of like the vector syntax except that it reads the elements of the vector literally, as if they were quoted. The emacs evaluator will not evaluate the elements: when it encounters a vector in the code it is evaluating, it just returns the vector. The Clojure evaluator encounters a vector, and returns the vector containing the result of evaluating each element in the vector.

In emacs:

(let ((a 10) (b 11) (c 12)) [a b c]) ;-> [a b c]

In Clojure:

(let [a 10 b 11 c 12] [a b c]) -> [10 11 12]

I wish Emacs had the Clojure behavior (or an extensible reader, like Common Lisp).

An association list is a list of pairs (created with cons). Each pair consists of a symbol and a value.

⁴

I estimate that the emacs session I'm running right now, to write this piece, has about 25,000 functions and symbols bound. The fact that emacs works at all without namespaces, with just this giant soup of symbols, is amazing and maybe even indicative of some kind of blind spot in our understanding of software development. Maybe worse is better.

A Survey of Syntactic Extension Techniques in the Lisp Family of Languages (Part 1)

2011-07-30T10:10:00.000-07:00

Lisp is famous for, and in some sense, defined by (see this), syntactic extension. Syntactic extension is Lisp is a great example of a design trade off - Lisp picks a relatively high level representation of its base syntax (lists of lists and atoms), and then writing syntactic extensions is greatly simplified, because they simply transform that high level representation. Syntax extensions don't have to worry about the nitty-gritty details of turning character streams into some kind of program representation (that is done for you, by the reader), and the code representation is simple enough to modify with the language itself, so extensions are easy to write. The trade off is that you have to stick to Lisp's baseline syntax (unless you get really tricky). What this means, in practice, is that even extended Lisp syntax will still be a list of lists and atoms (and chock full of parentheses, for which the language family is famous).

Despite the simplicity of this scheme, wherein the reader transforms text into a code-representation, which is then transformed by macros, and then finally converted to machine code or bytecode or interpreted, various Lisp dialects have approached the question of syntactic extension differently. Since I've recently gotten interested in macro hygiene, I thought it would be nice to write a series of posts about the different kinds of macro transformations available in various Lisp dialects.

picoLisp

picoLisp is a pretty bizarre Lisp variant which doesn't enjoy wide use, and has a pretty amazing set of philosophical underpinnings. PicoLisp is sufficiently different from other Lisps that I hesitated to cover it here, but it turns out to be extremely useful from a pedagogical point of view. How come? Because the code/data relationship, which is important in all Lisps, plays an even more central role in picoLisp. We are going to end this post talking about hygienic macros in Scheme, and picoLisp, in a sense, represents the polar opposite approach, with other Lisps occupying an arguably uncomfortable or impure middle ground. Code and data are so tightly coupled in picoLisp that the above picture of how syntactic extension works doesn't even really apply.

Smaller is Better

Code is Data

So what do we really mean when we say code is data? This is a bit fatuous, in a way - code is text, after all. All Lisp variants I know still require the user to write text out into a file, which is then read by the Lisp environment and acted upon. As suggested above, "code is data" really means that code is transformed from text into an intermediate form which is represented in terms of Lisp data types. We can then use the Lisp itself to transform that data or to execute it or interpret it.

What is the simplest thing we can do with Lisp data that may represent some code? This one is easy: the simplest thing we can do is nothing. Doing nothing to piece of code/data is called "quotation" in Lisp. It is represented by preceding an expression with the ' character. Quoted expressions aren't evaluated - when the interpreter hits one, it just returns the data stored in the quotation. A quoted expression is read by the reader, but not evaluated. It is just data.

'a ;-> a
'(this is some data) ;-> (this is some data)
'(if T "True" "False") ;-> (if T "True" "False")
(if T "True" "False") ;-> "True"

(N.B. You could download picoLisp and try these examples.)

Every line above except the last is quoted, and evaluates to just the quoted data. The last expression isn't quoted, and so it is actually evaluated by the interpreter. t is the true value, so the expression evaluates to the first clause, which is the "string" "True" (technically "True" is a symbol, since picoLisp only has one type which encompasses both strings and symbols). The opposite of quotation is evaluation. This is represented as the function eval in picoLisp:

(eval '(if T "True" "False")) ;-> "True"

A slightly less trivial example:

(setq x 10)
(setq q '(+ x 1))
(eval q) ;-> 11

When eval encounters a symbol, like x, above, it just replaces it with the current value of that symbol wherever eval is called. So, if we run the above code and then say:

(let x 0 (eval q)) ;-> 1

We get 1.

This is one of the ways the picoLisp differs from most other Lisps. This behavior is called "dynamic scope," and while most Lisps (even those that have this behavior) look upon it as a historical relic better thrown off or worked around, picoLisp embraces this behavior. This is because picoLisp is aiming for simplicity in its interpreter, and nothing is simpler than a symbol just meaning "get what the value of this symbol is right here, right now." As we'll see, eval in newer Lisp dialects won't work this way.

Ok, ok, we are sort of drifting. We were talking about Macros. Rather surprisingly, picoLisp's documentation says that:

Yes, there is a macro mechanism in picoLisp, to build and immediately execute a list of expressions. But it is seldom used. Macros are a kludge. Most things where you need macros in other Lisps are directly expressible as functions in picoLisp, which (as opposed to macros) can be applied, passed around, and debugged.

How can this be? Well, functions in picoLisp have the option of not evaluating their arguments. In most languages, function calls proceed by first evaluating all of their arguments, then binding those values to the variable names and then executing the body of the function. This is how it works in picoLisp too, if you say:

(de fun (A)
  (print "Inside")
  (print A))
(fun (prog (print "Argument evaluated.") 10))

You get:

"Argument evaluated.""Inside" 10-> 10

For non-Lispers, prog is just a form which evaluates each of its sub-forms in order and returns the last value. We are using it here to demonstrate when the argument expression is evaluated.

So when a function is called, its arguments are evaluated. This is true in every Lisp I know (except for exotica like Lazy Lisp, in Racket). This property is usually called, by the way, eagerness: the function is eager to know its argument's values before evaluating the body.

Unlike other Lisps, picoLisp lets you define functions which don't evaluate their arguments immediately. This is done by providing a single symbol instead of an argument list:

(de fun2 A
  (print "Inside")
  (print (eval (car A))))
(fun2 (prog (print "Argument evaluated.") 10))

(car returns the first element of a list).

Results in:

"Inside""Argument evaluated."10-> 10

The argument expression is not evaluated until we (unpack it and then) call eval on it. Using this feature, we can do something which is usually impossible in other languages: write if as a function. In most languages you can't write if in any nice way. In most Lisps, you've got to write a macro. In picoLisp you can just write if as an "ordinary" function:

(de my-if A
 (if (eval (car A))
     (eval (cadr A))
     (eval (caddr A))))

(my-if (< 1 0) 
  (prog (print "True Branch Evaled") T) 
  (prog (print "False Branch Evaled") NIL))

"False Branch Evaled"-> NIL

Note that "True Branch Evaled" is never printed. The true branch is never evaluated.

(Obviously we have to use the primitive if - the example is meant to highlight optional evaluation of arguments, not how a primitive like if makes it into a language).

Because functions can do this kind of thing, you can do some surprising things with picoLisp, like map if over lists of branches. I find it astonishing that the picoLisp docs provide this example and then say picoLisp goes for "The principle of least astonishment."

Variables, Scope, Eval, Quote and Lambda

If you are used to other programming languages, picoLisp probably seems pretty bizarre. But, if you're a little more open minded, you might think: wait a minute, this optional evaluation of input expressions is actually pretty handy! I can write all my special forms as regular functions, and then they too can be first class values! Why isn't every Lisp like this?

Well, I can't claim to understand the entire historical development of the Lisp family of languages, but I'm pretty sure that the main reason other Lisps moved away from this model is that they wanted to support lexical scope (to be discussed below). The watchword of picoLisp is simplicity: simplicity is why it is an interpreted language, rather than a compiled one, and simplicity shaped the design of the interpreter. Dynamic variable scope is the simplest thing, as far as an interpreter is concerned, and so picoLisp runs with it. Because code is always evaluated with respect to a dynamic environment, the code itself doesn't need to remember anything like "Which x did the programmer mean in the peice of code (+ x 1)." It is simply assumed that, by default, x refers to the x in the current dynamic environment. Under these semantic assumptions, a quotation is just a lambda expression without any arguments. Eval is just funcall for functions that take no arguments.

This is, in fact, literally true in picoLisp, even for functions with arguments.. There is no lambda. Anonymous functions are created with quoteation.

(mapcar '((X) (+ X 1)) (list 1 2 3 4))
; -> (2 3 4 5)

Because variable binding is assumed to be handled by eval and is assumed to be related only to where eval is called, not to anything about where the lambda was defined, code in picoLisp need have no additional information associated with it. It literally is just data.

In short, buzzword packed language: Restricting intepretation of variable binding to dynamic scope, picoLisp unifies function application and regular evaluation, and quote and lambda. With minimal convention, the distinction between functions and special forms nearly vanishes!

Lexical Scope?

I keep going on about dynamic scope above, and I even mentioned lexical scope above, but what is lexical scope and how does it impact upon the relationship between function application and evaluation and between quotation and lambda?

We are going to switch to Emacs Lisp for some examples now, because Emacs Lisp supports both lexical and dynamic scope and forces us to say explicitly which scoping rules we want to use. This helps make the discussion of scope clearer.

(If you want to follow along, Download the latest emacs, fire it up, and then press "Alt-x ielm *ENTER*". This will start up an Emacs Lisp read-eval-print loop. There are better ways to interact with the Emacs Lisp interpreter, but this is the most familiar for non-emacs users.)

Vi propaganda! (borrowed from here).

Emacs Lisp is a relatively old Lisp dialect, and by default it is dynamically scoped. There is a library that comes with Emacs that adds a lot of features from Common Lisp, including simulation of lexical-scope rules, so the first thing you need to do is require this package:

*** Welcome to IELM ***  Type (describe-mode) for help.
ELISP> (require 'cl)

A quick dynamic scope example:

(let ((x 10))
 (defun get-value-of-x () x)
 (get-value-of-x))

Obviously evaluates to 10. get-value-of-x just returns the value of x, whatever it is, when it is called. Hence:

(let ((x 11))
  (get-value-of-x))

Is 11. If we call get-value-of-x outside of a let which binds x, we'll get an error. x, at that point, has no value at all.

What if we use lexical-let instead?

(lexical-let ((x 10))
 (defun get-value-of-x () x)
 (get-value-of-x))

This is still 10.

But, perhaps surprisingly, we can now say:

(get-value-of-x)

Outside of any let expression which binds x and get 10 as the answer. Perhaps even more surprisingly:

(let ((x 11))
  (get-value-of-x))

Is still 10. Even:

(lexical-let ((x 11))
  (get-value-of-x))

Is still 10. In the context of a lexical-let, symbols bound by that lexical-let don't refer to whatever value is bound to that symbol "right now" in the dynamical environment, they refer to the particular lexical environment of the lexical-let expression. Conceptually, any lambda expression appearing in a lexical-let has to store more than just the list of symbols and lists that makes up its body; it also has to store the lexical environment to which those symbols refer.

(Lexical scope is called lexical scope because variables are interpreted by virtue of their lexical context, literally where they appear in the source code, rather than where they are evaluated when the program is executed.)

Code might still be represented as a list of symbols and lists and atoms, but that representation leaves out information about lexical context. When we finally reach hygienic macros, when we talk about Scheme, we'll see that decorating the list-of-things representation of source code with lexical information will be a key feature.

Let's drive this home before we adjourn part 1. Consider:

(let ((x 10))
  (setq code 'x)
  (eval code))

That is definitely 10.

What about if we say:

(eval code)

We get an error: "void variable x". Also expected.

Now:

(lexical-let ((x 10))
  (setq code 'x)
  (eval code))

This, maybe surprisingly, gives an error too. The real reason is that Emacs Lisp does some tricky things to simulate lexical scope, but it isn't totally obvious that eval should use the current lexical scope to evaluate terms. The meaning of symbols passed to eval in the context of lexical scope is suddenly non-trivial. We can't execute the above, but lets try:

(lexical-let ((x 10))
  (setq code 'x))

(let ((x 11))
  (eval code))

This evaluates to 11. The variable code really just contains a piece of symbolic data. That data doesn't remember anything about where it was defined - it forgets its lexical context - and so it can't evaluate correctly. The addition of lexical scope breaks the symmetry between quoteation and lambda expressions! We didn't need lambda in picoLisp because there was no lexical context to keep track of. In other Lisps we need defun and lambda to function as "smart quotations," which remember their lexical environment so that, upon invokation, they can behave correctly!

Because of the breakdown of this symmetry, and because Emacs Lisp doesn't provide picoLisp style functions, we need a whole new special form in Emacs Lisp to declare syntactic extension.

Conclusions of Part 1

Lexical scope is widely agreed to be the superior semantic mode for programming languages, principally because it makes reasoning about a piece of code mostly about looking at the text that defines the code, not at when the code is executed. But now we can see that lexical scope comes at a price: it breaks the symmetry between code and data. We get the simplicity, as programmers, of being able to understand our code based on its lexical environment "on the page". But the compiler/interpreter now has to do extra work to execute code correctly. Futhermore, naive modes of representing code as data are no longer complete: lists of lists and atoms don't contain lexical information.

Next time we'll talk about macros in Emacs/Common Lisp and Clojure (and maybe Arc (why the hell not?)). With today's lessons in mind, we'll see most of the conceptual problems with macros in these systems are associated with the fact that macros manipulate an impoverished code representation.

In subsequent posts, we'll look at macros in Scheme, and we'll see that the representation of code in that language is decorated with lexical information. This makes writing "well behaved" macros easier, but makes writing macros a little more abstract and, arguably, difficult to understand.

Thanks for reading!

Duckspeak Vs Smalltalk

2011-07-16T14:06:00.001-07:00

Duckspeak Vs Smalltalk

The Decline of the Xerox PARC Philosophy at Apple Computers

Malcolm Gladwell's recent piece, "Creation Myth", in the New Yorker, about innovation and implementation via Xerox PARC, academia and Apple Computers, tells one interesting story about that surprising time in our modern history. But the story of the tensions and synergies between visionaries and businessmen elides a few interesting details about what was going on, and why, at Xerox PARC at the time. Gladwell's version of history features a nimble entrepreneur, Steve Jobs, capitalizing on an idea the value of which a monolithic company, Xerox, can't see. But the story of Apple and Xerox PARC is also that of a design philosophy meant to empower people diverging into one meant to entertain them or to sell them things.

When Steve Jobs visited Xerox PARC and saw the first mouse, the system he was looking at, the Alto, was running a programming environment and language called Smalltalk. While the details of this system are glossed over in the Gladwell piece, they deserve more careful attention. Although The Alto bears a superficial resemblance to modern computers, it differed in one major area: the relationship between software developers and users.

For most people software is a solid edifice - it presents a few modes of interaction to the user, maybe a special panel of customization options somewhere, but is otherwise as opaque and unmodifiable as a modern car. If users bother to think about software at all, they think of it as a product, constructed somewhere by people called "programmers" and distributed to the user. If that software doesn't do what the user wants, he might send a hopeful technical support email, or he might just shop around for something else.

Of course, there is consumer software that includes more powerful extension features, so that, in principal, the user can add their own functionality, but these features don't seem to be popularly used. Firefox is an example of user-extensible software, but the vast majority of users don't use this capacity except to download what a small percentage of computer literate users write.

In other words, it is reasonably safe to say that most people who use computers have never written software.

Why should this be, and what does it have to do with Xerox PARC, Smalltalk and Steve Jobs? Well, an integral part of the Xerox PARC Philosophy was to dismantle the wall between software developers and computer users, to develop systems so easy to program that doing so would be a natural, simple aspect of computer use.

The early years of computing technology naturally produced a division between users and programmers - programming early computers was a highly technical discipline which required specific knowledge of the way the idiosyncratic hardware systems in those days worked. But while computers rapidly increased in power, the tools that programmers used to program them developed relatively conservatively. It is easy to imagine a world where those tools developed along with the computers, until programming itself became so easy that the average user would feel comfortable doing it. After all, the point of any program is to automate or facilitate tedious work, and in this respect programming itself is no different than a word processor.

That wasn't exactly how things happened, and the reason why is a fascinating and arguably still unresolved story in and of itself. Part of that story takes place at Xerox PARC.

The Xerox PARC Philosophy

I mentioned above that the computer Steve Jobs saw on his visit to to Xerox PARC, the Alto, was running something called a Smalltalk System. Smalltalk is still around, and you can even download a self-contained Smalltalk System called Squeak and play around with one yourself. What you'll see, if you do, is something which is probably very similar to what Steve Jobs saw on that day - a desktop-ish interface, with dragable windows and clickable buttons. And of course, you interact with the mouse.

The Graphical Programming Environment of Pharo Smalltalk.

Both systems also share a fascinating property which "Creation Myth" leaves unmentioned. In Smalltalk, you can, using something called "The Browser," pull up the "source code" for any object in the system. "Object" in this case means anything in the system whatsoever, including windows, widgets, numbers. "Source code" is the stuff that a compiler translates into machine code so the computer can do something with it. If you want, you can modify that code right there, or copy it and create a new object with user-customized behavior. The entire system is transparent and modifiable.

Most of the programming languages people used in 1979 would have looked very nearly like gibberish to a lay person. Early computers were slow, which meant that compilers took a long time to work unless they were very simple. This meant that most early programming languages were just thin shells on top of the numbers-as-command codes of machine language. Even by 1979, languages hadn't developed much further in public use - corporate and government users (pretty much the only users before personal computing) were interested in cost-effectiveness and systems their programmers already knew, so language and system design was very conservative. New languages came along, but often they were incremental improvements on previous designs.

The designers of Smalltalk (Alan Kay, Dan Ingalls, and Adele Goldberg principally, and others), given the resources and freedom of Xerox PARC, worked actively to reverse this trend. Whereas a hodgepodge of cultural and technical realities constrained the way most other programming languages looked and felt, both Smalltalk the language and the system were written from the ground up to be so easy that a child could use them (hence the name). It was much more ambitious than just that, however. Kay saw Xerox PARC as being on the vanguard of a real revolution in human/computer interaction. In "The Early History of Smalltalk," Alan Kay writes of this "Xerox PARC" vision of personal computing:

... the user interface would have to become a learning environment along the lines of Montessori and Bruner; and [the] needs for large scope, reduction in complexity, and end-user literacy would require that data and control structures be done away with in favor of a more biological scheme of protected universal cells interacting only through messages that could mimic desired behavior.

... we were actually trying for a for a qualitative paradigm shift in belief structures -- a new Kuhnian paradigm in the same spirit as the invention of the printing press...

It is obvious from the "The Early History of Smalltalk" that Alan Kay has a direct, emotional involvement in his subject matter (he says so in fact). What is equally obvious is that Kay's retrospective must be bittersweet at best. Smalltalk and the Alto were, at the time, the avatar of "The Xerox PARC Design Philosophy". The systems Apple went on to produce would imperfectly capture this philosophy, and arguably, later, jettison it altogether.

In one anecdote, Kay relates showing a custom system (built in Smalltalk) meant to facilitate non-expert "programming," to executives from Xerox PARC. This system was a kind of highly advanced programming language meant to make human-machine interaction at a very high level intuitive for non-expert users. At one point during a demonstration, a vice president, after an hour of working with the system, realized he was programming. What they accomplished, then, was a keystone for a software system which Kay felt bridged the gap between the numbers coursing through a CPU somewhere, and human intuitive reasoning.

Kay viewed programming as a natural aspect of human computer interaction, and he designed his systems to make programming the computer as easy and intuitive as creating a new Word Document or browsing the web is on modern computers. When Steve Jobs visited Xerox PARC and saw the Alto, he brought more than just the user interface to Apple Computers, he brought an entire philosophy of personal computing.

HyperCard

The Xerox PARC philosophy can be seen in a variety of technological lineages still discernible in the Apple universe. Objective C, a variant of the Smallktalk language, though without its attendant environment (the SmallTalk system), is still in use. Kay himself is quick to point out HyperCard, an early and still incredibly popular application environment, which encouraged user extension and programmability in a language called "HyperTalk," which was inspired by Smalltalk and the Alto, was a good realization of the Xeroc PARC philosophy on the Mac.

A screenshot of Hypercard in action. Linked from here.

HyperCard, like much of the work from this period, defies comparison to modern software. Although often described as a kind of hypertexual rolodex, its "cards" could contain more than static information - they could also contain user-created multimedia and interactive components. Users would begin by adding cards for various pieces of information, but then, say as a card representing sales data grew to require a calculator, an interactive component for that purpose could be added. These components were themselves added interactively from within HyperCard.

HyperCard, and the people using it, organically grew many applications which left a permanent mark on computer history. A particularly telling fact is that the original version of the game Myst, a fantasy adventure game, was a HyperCard App. On the other side of the Atlantic, figuratively and literally, Renault, a french car manufacturer, used HyperCard to maintain its business inventory. HyperCard became the program its users needed it to be because it was open, extensible and encouraged user programming and interaction as a fundamental use-case. Even modern extensible software like Firefox tends to separate use from extension development - the average user might have no idea that Firefox supports user extension. In Hypercard, these features were "on the surface" of the design.

HyperCard also illustrates some of the difficulties that might be responsible for the gradual shift away from Xerox PARC-like open models of personal computing. According to rumor, the developer of HyperCard, Bill Atkinson, allegedly¹ gave the product to Apple in 1987, with the understanding that it would be distributed for free with each Mac. The program was an immediate success. HyperCard produced a tremendous amount of feedback from the community, but since it was a free product, Apple wasn't sure how much internal resources should be devoted to handling HyperCard development.

Perhaps seeking a way of turning the HyperCard phenomenon into a revenue stream, Apple eventually transferred HyperCard development to a subsidiary company, which attempted to transform it into a profitable business model. HyperCard was no longer released for free, but a locked down version, capable of playing, but not developing, HyperCard Applications was freely available. The "developer's edition," recognizable as just Hypercard, was available for purchase. In an effort to make HyperCard into a business model, Apple inadvertantly had separated users into "developers" and "users." This, combined with the development of work-alikes with more features, seemed to destroy HyperCard's momentum, and, despite later attempts at revival at Apple, the system fell out of use².

Waiting for the Dynabook

Alan Kay invented the laptop computer - at least he developed a concept computer called The Dynabook which for all intents and purposes was a modern laptop and more. He envisioned that such a system, directed mostly at children (but usable by adults) would run Smalltalk, and while its possible to build the conceptual system Kay imagined in 1968 today, he still believes that the Dynabook doesn't exist. Although tablet computers resemble the Dynabook superficially, and the One Laptop Per Child project comes close, Kay believes that his essential vision is unfulfilled. Kay points out, when asked about this, that the necessary technologies for a Dynabook device are quite old, but that corporate and cultural practices simply haven't caught up to using them appropriately.

Sketch of the Dynabook design (from Wikipedia.)

Consider by contrast any one of Apple's iDevices. The touch screen, networking capability and user friendly design are reminiscent of the Dynabook, but, whereas on a Smalltalk system one could click on any widget and see and modify the source code, an iPad is essentially completely locked down. Not only does Apple require a license to develop and sell software for the iDevices in their "App Store," but to even develop, for personal use, software for your own device, a separate "Developer's Kit" (and the Apple Computer to run it on) must be acquired. Whereas Smalltalk was designed from the bottom up to facilitate programming for young and inexperienced users, the iPad targets its development tools, which are arguably byzantine by the standards of Smalltalk, to a relatively small group of developers. On top of that, software is only distributable after passing through an often arbitrary and, in any case, secretive Apple review process.

While the Dynabook was meant to be a device deeply rooted in the ethos of active education and human enhancement, the iDevices are essentially glorified entertainment and social interaction (and tracking) devices, and Apple controlled revenue stream generators for developers. The entire "App Store" model, then works to divide the world into developers and software users, whereas the Xerox PARC philosophy was for there to be a continuum between these two states. The Dynabook's design was meant to recruit the user into the system as a fully active participant. The iDevice is meant to show you things, and to accept a limited kind of input - useful for 250 character Tweets and Facebook status updates, all without giving you the power to upset Content Creators, upon whom Apple depends for its business model. Smalltalk was created with the education of adolescents in mind - the iPad thinks of this group as a market segment.

HyperCard was, by comparison, much closer to the Dynabook ethos. In a sense, the iPad is the failed "HyperCard Player" brought to corporate fruition, able to run applications but completely unsuited for developing them, both in its basic design (which prioritizes pointing and clicking as the mechanism of interaction), in the conceptual design of its software, and in the social and legal organization of its software distribution system.

It is interesting that at one point, Jobs (who could not be reached for comment) described his vision of computers as "interpersonal computing," and by that standard, his machines are a success. It is just a shame that in an effort to make interpersonal engagement over computers easy and ubiquitous, the goal of making the computer itself easily engaging has become obscured. In a world where centralized technology like Google can literally give you a good guess at any piece of human knowledge in milliseconds, its a real tragedy that the immense power of cheap, freely available computational systems remains locked behind opaque interfaces, obscure programming languages, and expensive licensing agreements.

The last 30 years have accustomed us to breakneck advancements in the technology we use every day, and yet at the personal level these advancements have been limited almost exclusively to communication and entertainment - so much so that arguably the public lacks even the the vocabulary to express what it is that modern computing could be doing for them or what they could be doing with modern computing. Spreadsheets are the closest most people get to "computing" with their personal computers. The electronic spreadsheet, which is itself an adaptation of an analog technology, was conceptualized in 1961.

If you ask Alan Kay about personal computing now, he is remarkably upbeat. In his view, the rapid development of technology simply outpaces the ability of corporate and educational systems to adapt, and this leads to a "pop culture" of sorts which dominates the culture of computer use. In other words, the divide between users and programmers, or at least between the truly computer literate and the merely casual computer user, isn't a top down phenomena imposed upon the people by those in control of technology. It is an inevitable result of the rapid pace of development.

I think one of the main consequences of the inventions of personal computing and the world wide Internet is that everyone gets to be a potential participant, and this means that we now have the entire bell curve of humanity trying to be part of the action. This will dilute good design (almost stamp it out) until mass education can help most people get more savvy about what the new medium is all about. (This is not a fast process). What we have now is not dissimilar to the pop music scene vs the developed music culture (the former has almost driven out the latter -- and this is only possible where there is too little knowledge and taste to prevent it). Not a pretty sight.

Alan Kay is still pushing for more symbiotic conceptualization of human/computer interaction, although he describes Smalltalk as part of his "distant past". He presently heads a non-profit organization he co-founded called "Viewpoints Research Institute," whose purpose is to continue to consider the questions of educational and personal computing. We'd never have gotten the iPhone if it hadn't been for his influence at Xerox PARC. Maybe one day we'll be lucky enough to get the Dynabook.

¹ Bill Atkinson is presently a nature photographer and couldn't be reached for comment.

² However, HyperCard's influence is still felt today. Last year, Dale Dougherty, editor of Make Magazine, wrote in wired that the iPad needed a HyperCard-type application. Tilestack, a web based, HyperCard-a-like with a pay-to-distribute model, recently went bust. Squeak Smalltalk includes a "Morph," a kind of extendable program, which is loosely based on HyperCard. Although from a parallel technological lineage altogether, Emacs, which is still in wide use, and which the author used to write this article, resembles HyperCard in many respects.

Cross Post (also on The New Yorker) about Smalltalk

2011-06-22T05:02:00.000-07:00

A letter to the editor I wrote to the New Yorker is in this month. See it here or read it in replicate here:

"When Jobs visited Xerox PARC and saw the company’s Alto computer, the windowed environment that so impressed him was running a system called Smalltalk, invented by Alan Kay, Dan Ingalls, and others. It was designed specifically with children in mind, to make examination, modification, and extension of the system easy for non-technical users. For example, in most Smalltalk systems, any visible object can be clicked on, and its source code inspected, copied, and modified. In contrast, the iPad and other iDevices available from Apple hide the source code for the system (by both legal and technical artifice). This barrier effectively destroys the system as a platform for exploratory, educational use. The Apple / Xerox story isn’t just one of a nimble young company snatching innovation from the jaws of an aging dinosaur. It is also the story of a corporate entity neutering a design philosophy meant to empower computer users and replacing it with one meant to sell them things."

I'm writing a full length article on this subject which I may publish here. Wait for it!

A Hyperturtle Monad Makes Pretty Pictures

2011-05-30T07:43:00.000-07:00

In the Monads of Madness

One thing about monad tutorials is that they almost universally cover simple monads - often the most complex monad you get is the Sequence monad. The Error or Maybe monads are also common examples, but in those dynamic languages which most folks are familiar with there are already facilities for dealing with Errors or Exceptions and so these monads seem like trinkets. Why bother?

(Keep reading, I promise we will make pretty pictures.)

This seems to lead to the commonly expressed opinion that monads aren't really useful in anything but Haskell, and that unless you live there, there isn't any point in understanding them. I can see this perspective, particularly because unless you work in Lisp or want to bang around with some heavyweight meta-programming tool like Metalua, the syntax which makes using monads convenient isn't available anyway.

Another part of me, however, thinks its too bad. There are some problems which find elegant expression by recourse to monadic computation. Monadic parser combinators are an example, I think. I'd always found parsing to be an unapproachable activity, requiring special use tools and an understanding of and separate domain specific languages to program them. If one develops monadic parser combinators in Lisp, with the appropriate binding expressions to clean up the monadic details, parsing pops out as just one more programming task.

This post covers another example of a monad coming to the rescue when a complex problem needs solving. It is also an example of a monad which I've never seen before (although it is some unnamed state flavored monad transformer on the result of using the standard state monad transformer on the sequence monad, I believe). I'm going to try and present things in the order they occured to me, and hopefully give one a flavor of how one constructs a monad for a specific purpose, rather than grabbing one off the shelf. Also, for variety, we'll be using Scheme, rather than Emacs Lisp. While the code here is probably a stone's throw away from any Scheme implementation, I'm working in Racket.

Remember Turtle Graphics?

Back when I was but a wee lad in Louisiana, I went to nerd camp. This was a program called ADVANCE for kids who wanted to spend three weeks of their summer in intense study - you could get credit to skip highschool classes. For brainy kids, this was also a place where you could expect to be around a lot of other brainy kids, and if that didn't exactly lift the pall of awkwardness which hung over most of us, it surely made us feel less strange for it all.

Anyway, I never took a programming class any of the summers I spent at ADVANCE, but I do remember walking past the computer labs a couple of times and seeing a little blinking triangle and a window beneath. This is probably familiar to some other readers. It was some implementation of Turtle Graphics.

In a Turtle Graphics system one is given a special programming language with most of the usual fixings and one other distinguishing feature: the language includes primitive operators for controlling the motion of that little triangle on the screen - the titular Turtle. You can tell the turtle to move forward or to rotate in place or to lift up or place the "pen" it carries in its little forelimb. When the pen is down, the turtle leaves a line on the screen.

That first figure up there, for instance, was produced using the library we'll build today. The following code does it:

(turtles-go
  (mlet* m-turtles
         ((new-pos (jump-to 150 150))
          (len     (setl 'len 2))
          (new-pos (n-times
                    (mlet* m-turtles
                      ((len (getl 'len))
                       (p   (move* len))
                       (r   (turn (/ pi 1.99)))
                       (len (setl 'len (+ len 2))))
                      (m-return p))
                    200)))
         (m-return new-pos)))

Here is the result again, since its not on the screen anymore:

You can imagine that with such a system, one can very quickly convince the turtle to draw all sorts of spirographical images, telling the turtle to repeat some sequence of commands which accumulate into elaborate patterns. Pretty neat stuff.

At first I wanted to create a turtle graphics system in a purely functional style (at least as purely functional as possible), as a learning exercise. But then I got to thinking:

What about a Hyperturtle?

Symmetry is an extremely important aesthetic principle which is somewhat difficult to capture in Turtle Graphics. It you want to describe a system with bilateral symmetry using the turtle, you've got to convince him to traverse the two sides of the figure in one go. If you want to draw a Y, for instance, you have to say something like (in pseudo code):

(face north)
(move 10)
(rotate 45)
(move 5)
(rotate 180) ; these lines describe 
(move 5)     ; backtracking 
(rotate 90) 
(move 5)

What if you could just move the Turtle up to the stem of the Y and then tell it to rotate BOTH 45 degrees and -45 degrees and then tell it to follow the rest of the instructions. To satisfy your demands, the Turtle must split itself into two turtles, but after that point each turtle follows exactly the same directions, and you save yourself a few commands and some complexity.

An even simpler approach might be to tell the turtle to have two different "helicities," that is, one turtle interprets (turn 45) as meaning to turn clockwise, and the other interprets it to mean counter-clockwise. Now any sequence of drawing commands will produce a symmetric figure, all for free. State dependent computations with multiple possible outcomes?

Is anyone else's monad sense tingling!?

Monads in Scheme (a diversion)

If you've read any of my other posts about monads, you know how this is going to go. We are going to define a macro to facilitate monadic computation. Since this is a kind of advanced article, I'm going to assume you have the basic idea about bind and return more or less down. If I say that:

(mlet* sequence-monad
  ((x '(1 2 3))
   (y '(4 5 6)))
 (m-return (+ x y)))

Expands to:

(sequence-bind '(1 2 3) 
 (lambda (x)
  (sequence-bind '(4 5 6)
    (lambda (y)
      (sequence-return (+ x y))))))

You should follow what I mean and why. As it happens, this monadic binding expression is defined in the racket library associated with this article, in functional/monads. (Except there sequence-monad is called m-list). The mlet* defined in that library provides one additional feature which I've found useful. You can interpolate monadic and non-monadic binding:

(mlet* sequence-monad
  ((x '(1 2 3))
   (non-monadically: 
     ((q (+ x 1))))
   (y '(4 5 6)))
 (m-return (+ q y)))

Causes q to be bound only once per x, rather than bound as a monadic value. We're going to be liberally using mlet* throughout the rest of the article, so if you don't see how it works, check out the other monad tutorial.

Turtle Functions

Let's backtrack and think about the regular old turtle monad. A basic turtle might be implemented as a dictionary containing keys like position, direction, pen-status, etc. In the land of imperative, side-effect producing programs we'd probably just have a global dictionary someplace holding these values. In an object oriented language we might do something obscene like a singleton class. Both would involve side effects. Suppose we wanted to avoid side effects forever (or at least until we had to talk to the hardware handling rendering)?

The obvious solution is to thread our turtle state through tons of functions which non-destructively modify it. Our turtle may as well carry around a representation of whatever "drawing" it has done in its mind, too. Once we pass the state through all of the state-dependent functions we want to, we'll extract that representation of the drawing and pass it on to our GUI to draw. The modification of the memory of the screen will be the only conceptual side effect.

What about querying the state? We might want, for instance, to make our turtle avoid certain regions of space, which means we'll need to make inquiries into the state of the turtle, and we'd like to do so in a standard way. We'd also like to be able to combine queries with modification. What kind of function enables this behavior? Well, consider these:

(Note for non-lispers, cons simply consstructs a pair or tuple.)

(require racket/dict)

(define (turtle-position^ turtle)
 (cons (dict-ref turtle 'position) turtle))

(define (try-to-move turtle amt)
 (let* ((pos (dict-ref turtle 'position))
        (dir (dict-ref turtle 'direction))
        (new-position 
         (move-point-in-dir pos dir amt)))
  (if (point-on-screen? new-position)
      (cons new-position (dict-set turtle 'position new-position))
      (cons #f turtle))))

So, in order to let our turtle-dependent function communicate information to us other than a possibly modified state value, we will let them return a pair of things. The first part of the pair is the returned value, the second part is the possibly modified state. turtle-position^ just fetches the turtle's position into the first part of the pair, returning the unmodified turtle in the second part of the pair. try-to-move actually uses the facility to return values in a non-trivial way. It calculates the new position of the turtle, tests to see if it is on the screen and then returns the new point and modified turtle if it is, and otherwise simply returns #f and the unmodified turtle. A caller of this function can inspect the first value to see if it succeeded without knowing too much about the internal representation of the turtle itself. That's hott.

I want to point out something about the try-to-move function at this point. Note that it takes more arguments than just the turtle. Somewhere down the line we might want to reduce it to a function of just the turtle-state. In fact, this is such a common thing to do that we should really rewrite the function in a curried form:

(define (try-to-move amt)
 (lambda (turtle)
   (let* ((pos (dict-ref turtle 'position))
          (dir (dict-ref turtle 'direction))
          (new-position 
           (move-point-in-dir pos dir amt)))
    (if (point-on-screen? new-position)
        (cons new-position (dict-set turtle 'position new-position))
        (cons #f turtle)))))

Now we've got a function which returns a compliant turtle function - a function of just state and which returns a pair. When we finally figure out the machinery to combine such functions, we can just pass in amt before we pass the resulting state function to that machinery, where it can be handled in a uniform way.

Now that we've factored the functionality in this way, we can recognize try-to-move as a function which produces a turtle-function. This is an important class of functions which we'll call "turtle combinators." Think of such a function as a turtle function "waiting" for a value before it commits to being a particular turtle function. try-to-move represents the family of all movement functions parametrized by amt. Each call to try-to-move returns such a function.

Thinking Monadically

Ok, so we've cooked up an ad-hoc formalism for dealing with our purely functional turtle. Lets relate this to a monad. A monad relates the following types of interest:

Values These are just any old kind of value held "in" the monad.
Monadic Values These are the "container" into which values go.
Monadic Functions These are functions which take a Value and return a Monadic Value.

Graphically:

So one way of thinking about monads that comes up a lot is that there is a monad for every data structure. Lists form a monad, Trees form a monad, the maybe monad is just a data type consisting of two kinds of things, (Just <something>) and (None) (in much the same way that a list is either an element and a pointer to another list or nil).

We can imagine that a function of state which returns a value and a new state is a kind of data structure. The analogy isn't that tortured, really. You can put an element "into" a state function:

(define (insert-into-state x)
  (lambda (state) 
    (list x state)))

Returns a state function that itself returns x when you ask for it with a state. In terms of our types of interest: x is a Value, (lambda (state) ...) is a Monadic Value and insert-into-state is a Monadic Function.

You get data out of a state function by passing a state in:

(define (val-of pair) (car pair))
(define (state-of pair) (cdr pair))
(val-of ((insert-into-state 10) '() )) -> 10

For the sake of driving the analogy home,

(first (list 10)) -> 10

(Type note: 10 is a Value, (list 10) is a Monadic Value.)

is the equivalent code for the data structure called a list. We put things in, and take them out again. So if these state functions are a data structure, what is the associated monad? Welp, a monad exists when you have a return and a bind operation. For the list monad these are:

(define (list-return x) (list x))

(Type note: list-return is a Monadic Function.)

(define (reduce f lst)
  (foldl f (car lst) (cdr lst)))

(define (list-bind monadic-val monadic-fun)
  (reduce append (reverse (map monadic-fun monadic-val))))

It should be reasonably clear why insert-into-state is state-return. It constitutes the operation of placing any object into the monad.

Graphically:

What about bind? Well, squint at the list-bind operation and dig this: its essence is that it takes the monadic function (a function which represents a monadic value "waiting" for some input to compute itself) maps it over the values in the monad, and collects each of them into a complete list. Monadic functions must take values and return monadic values, so the map returns a list of lists, which we reduce with append. If you squint, you can pull out the following all right description for what bind does:

Monadic bind takes values out of the monad, applies a monadic function to them, which results in lots of little monadic values. These monadic values are combined, finally, into one big monadic value, which is returned.

Graphically:

List-bind takes the elements out of a list, applies a function to them to generate a bunch of lists, and combines them together.

What is the equivalent operation for the state monad? Well, bind has to return a monadic value, which is a state function in our case. So we know that bind will return a lambda. And we know bind has to extract the value from the state function passed in, and we know to do that, bind will need the state value, so everything interesting has to happen inside the returned state function. What has to happen in there?

Well, we will apply the monadic value to the state passed into the function we are returning. This generates a pair, the first part of which is the "value" extracted from the monad. We'll pass this value to the monadic function, which will generate a new state function. We will then pass the new state function the second part of the previously produced pair, which is the new state value. The return value of the new state function on the new-state will be the return value of the function we return.

Ok, I admit, that is a lot to follow. Read the code:

(define (state-bind state-fun state-fun-producer)
  (lambda (state)
    (let* ((pair (state-fun state))
           (val1 (val-of pair))
           (new-state (state-of pair))
           (new-state-fun 
            (state-fun-producer val1)))
      (new-state-fun new-state))))
(define state-return insert-into-state)

It is slightly more obvious as source code than text. That has got to mean something about language, the power of abstraction, etc. The state monad is already implemented in functional/monads, so we can write:

(require functional/monads
         racket/dict)

(define (st-fetch key . or-val)
  (if (not (empty? or-val))
   (lambda (state) 
    (list (hash-ref state key or-val) state))
   (lambda (state)
    (list (hash-ref state key) state))))

(define (st-set key val)
  (lambda (state)
    (list val (hash-set state key val))))

(define (point+ p1 p2)
  (map + p1 p2))

(define (dir->vec dir)
  (list (cos dir) (sin dir)))

(define (point* p scalar)
  (map (lambda (x) (* x scalar)) p))

(define (move amount)
  (mlet* m-state
    ((position (st-fetch 'position '(0 0)))
     (direction (st-fetch 'direction 0))
     (non-monadically:
      ((new-position (point+ position 
                      (point* amount
                        (dir-vec direction))))))
     (_ (st-set 'position new-position)))
   (m-return new-position)))

Let's focus on the last function - move. The body is a monadic expression in the state monad, which means that it returns a function itself. Specifically, it returns a function which takes a state and returns a value/state pair. Each expression in the binding part of the mlet* threads the value produced by each right hand expression through state-bind and binds the variable in the left hand side to the "value" part of the value returned by the state function in the subsequent expressions. The body of mlet* provides a final location to evaluate expression in the monad. It must evaluate to a state function, hence we use m-return.

The Hyperturtle Monad

Our mask slipped above and we just started calling the turtle monad the state monad, which is exactly what it is. Astute readers might notice that it is also, for all intents and purposes, equivalent to the parser monad (types notwithstanding, obviously) seen from a different perspective.

The whole reason I'm writing this up is because I've never read a really lengthy development of a novel monad. Most tutorials say "you don't really have to understand how to write one, just how to use them," but I think this is a shame. As we'll see, the right monad will enable an almost magical extension to the notion of turtle graphics.

Ok, so lets think some about the hyperturtle we want to create. The basic idea is that our turtle can be told to do multiple things at once. That is, we want to be able to say something like

(parallel-rotate (/ pi 2) (- (/ pi 2)))

And have our system interpret it as a command which results in the turtle splitting into two turtles, one which rotates +pi/2 and the other which rotates -pi/2. In other words, we want to allow multiple possible outcomes to each monadic function, which sounds a lot like the list monad. Monadic functions of the list monad take a single value and return a list of values. Depending on one's perspective, it can be meaningful to view this list of results as a list of possible return values over which subsequent computation in the monad is split:

(mlet* m-list
 ((x '(1 2 3))
  (y (list (+ x 1) (- x 1))))
 (m-return (list x y)))

Will evaluate to:

((1 2) (1 0) (2 3) (2 1) (3 4) (3 2))

by this very logic. For each possible value of x we have multiple values of y. We finally return all the combinations of these possible bindings in a list of possible results.

But the hyperturtle monad can't be the list monad alone. After all, each expression in the binding has to depend on the previous turtle state, and the result of a monadic expression needs to be like a state function somehow. Turns out there is a standard way of constructing the monad we are interested in using monad-transformers, but we'll do it the hard way for now so as to elucidate how one goes about it.

Let's think carefully. We still need state functions, but now they are going to be returning "virtually" more than one possible outcome. Since each possible outcome might also involve a separate modification of the state, as well as a distinct value, it might make sense for our functions to accept a single state but return a list of value/state pairs. So, our monadic values are functions which take a state and return a list of possible outcomes.

What does return look like for this hypothetical monad? Well:

(define (pstate-return val)
  (lambda (state)
    (list (pair val state))))

Bind is going to be a bit more difficult, but we can keep our head straight by just remembering what bind always does. It returns a new monadic value, so its got to return a function which takes a state and returns a list of pairs. Inside that function, we've got to use the state to produce a list of state/val pairs. Then we need to use each pair to produce the next state function, which we apply to the new-state to get a list of state/val pairs. We collect all these pairs back together into a single list of state/val pairs, which is our return value.

Might be clearer in code:

(define (pstate-bind pstate-fun pstate-fun-producer)
  (lambda (state)
    (let* ((pairs (pstate-fun state))
           (new-results
             (map 
               (lambda (pair)
                 (let ((val (car pair))
                       (state (cdr pair)))
                  ((pstate-fun-producer val) state)))
               pairs)))
      (reduce append new-results))))

Ok, so there we go. We've got a parallel state monad where we can orchestrate multiple results. But wait? What if turtles need to share information with one another or reference a "global" state? For instance, a turtle might wish to avoid an area if a line has already been drawn there. We need an additional level of global state? How might we represent that?

One way is to consider functions which accept a pair of states, one representing a possible "local" state and the other representing the shared "global" state. These functions want to reflect that the local state might split into many new local states (or none at all), and they also might modify the global state. So its got to return the list of new local states, the new global state and the local results of each possible outcome. The functions can sensibly return this collection of things by returning a pair consisting of a list of value/local-state pairs and a global state. Consider the return operation for this new monad:

(define (ps-return val)
 (lambda (st-pair)
  (pair (list (pair val (car st-pair)))
        (cdr st-pair))))

We return a state function which destructures the st-pair input, returning a pair containing a list with one element, a val/local-state pair, and the global state.

Now the coup de grace, what is the bind operation for this crazy monad? Well, it is similar to the bind operation for the sequence-of-state monad, except we have to deal with the global state. Each monadic value needs to use the previously calculated global state function. The named let expression below amounts to a fold operation over the global state.

(define (ps-bind monadic-val monadic-fun)
  (lambda (state-doublet)
    (let* ((results/global
            (monadic-val state-doublet))
      (let loop ((global-state (cdr results/global))
                 (pairs (car results/global))
                 (results-acc '()))
         (if (empty? pairs) (reduce append (reverse results-acc))
             (let* ((pair (car pairs))
                    (rest (cdr pairs))
                    (val (car pair))
                    (new-mv (monadic-fun val))
                    (new-res (new-mv (cons (cdr pair)
                               global-state))))
              (loop (cdr new-res)
                    rest
                    (cons (car new-res) results-acc)))))))))

Ok, this is kind of complicated - but we've expressed it in just 17 lines of code. Include return and we're up to 21 lines. Once we define a few "primitive" monadic functions/values we'll be able to write incredibly concise and arguably expressive hyperturtle code.

Useful Hyperturtle Functions

We'll want to tell a branch of our computation to simply terminate. This corresponds to returning no values whatever in the local part of a state function, and leaving the global state unmodified:

(define (poof st-doublet)
  (cons '() (cdr st-doublet)))

We're going to use the good old association list to represent our local and global states. That way we can add and remove arbitrary data from them. Just in case we want to use another table abstraction later, though, we're going to use racket's dict library to wrap them:

(require racket/dict)

(define (setl key val) ; setl = set local
 (lambda (state-doublet)
   (cons (list (cons val
                     (dict-set (car state-doublet) key val)))
         (cdr state-doublet))))

(define (setg key val) ; setg = set global
 (lambda (state-doublet)
   (cons (list (cons val (car state-doublet)))
         (hash-set (cdr state-doublet) key val))))

Ok, so our pattern sense should be tingling. We keep writing functions which take some parameters now and return a state function. Let's whip up some notation for this kind of common task. Eventually our library of combinators/monadic functions/monadic values will be large enough that merely mlet* will be sufficient to write most functions of interest, but until then, its nice to have some syntactic sugar. Consider the hygienic macro:

(require racket/match)

(define-syntax (define<turtles> stx)
  (syntax-case stx (^)
    [(_ (id lstate-id gstate-id) body ...)
     (syntax (define (id dblt)
               (match dblt
                 [(cons lstate-id gstate-id) 
                  (begin body ...)])))]
    [(_ (id lstate-id gstate-id ^ var) body ...)
     (syntax (define (id var)
               (lambda (dblt)
                 (match dblt
                   [(cons lstate-id gstate-id)
                    (begin body ...)]))))]
    [(_ (id lstate-id gstate-id ^ var ...) body ...)
     (syntax (define (id var ...)
               (lambda (dblt)
                 (match dblt
                   [(cons lstate-id gstate-id)
                    (begin body ...)]))))]
    [(_ id val)
     (syntax (lambda (dblt)
               (match dblt
                 [(cons lstate-id gstate-id) 
                  (cons (list (cons val lstate-id)) gstate-id)])))]))

This lets us write the above two functions like so:

(define<turtles> (setl local global ^ key val)
  (cons (list (cons val (dict-set local key val))) global))

(define<turtles> (setg local global ^ key val)
  (cons (list (cons val local) (dict-set global key val))))

Ahhhhhh. Much more concise. For those not too familiar with syntax-rules style macros, this:

(define<turtles> (setg local global ^ key val)
  (cons (list (cons val local) (dict-set global key val))))

expands to:

(define (setg key val)
 (lambda (state)
  (match state
   [(cons local global)
    (begin (cons (list (cons val local) (dict-set global key
 val))))])))

The ^ character is just a piece of visual lint meant to help distinguish between the fact that the first two arguments are curried off from the rest of the arguments.

We've now constructed enough machinery to understand the actual code used in my implementation. There is just one note I should make before we switch over to looking at actual code. Since we are returning a list of pairs and we're using association-lists, which are just lists, after all, and lists are made of pairs, I felt that we were just overburdening cons a little too much to make the code easy to debug. Hence, instead of using pairs where I wasn't using a list, I created a new structure:

(define doublet (a b))
(doublet-a (doublet 10 11)) -> 10
(doublet-b (doublet 'x 'y)) -> 'y

So with doublets,

(define<turtles> (setg local global ^ key val)
  (cons (list (cons val local) (dict-set global key val))))

Becomes

(define<turtles> (setg local global ^ key val)
  (doublet (list (doublet val local) (dict-set global key val))))

This change gives the Racket environment a little hand when it comes to checking types.

I promise, things are about to get RAD. We just need a few more primitives:

(define<turtles> (getg lo g ^ symbol)
  (doublet (list (doublet (dict-ref g symbol #f) lo))
        g))

(define<turtles> (getl lo g ^ symbol)
  (doublet (list (doublet (dict-ref lo symbol #f) lo))
        g))

(define<turtles> (getl-or lo g ^ symbol or-val)
  (doublet (list (doublet (dict-ref lo symbol or-val) lo))
        g))

(define<turtles> (getg-or lo g ^ symbol or-val)
  (doublet (list (doublet (dict-ref g symbol or-val) lo))
        g))

These primitives let us fetch values from either the local state or the global one.

Ok, now here is the cool step. Consider the function:

(define<turtles> (split-setl lo g ^ key vals)
  (doublet 
   (map (lambda (val)
          (doublet val (dict-set lo key val)))
        vals)
   g))

This function lives in the turtle-state monad, evidently enough. It takes a key and a list of values in vals. It then returns a list of new local states where the key has been set to each of the values in turn. Any further state function when used within the monad will now execute in multiple contexts, one for each possible assignment of the key.

Representing the Drawing

All turtles will share a global representation of the drawing, which we will store in a global key as a series of objects to draw. Hence, the function to add a line to a drawing might be:

(struct point (x y))
(struct line (p1 p2))

(define (add-line x1 y1 x2 y2)
  (mlet* m-turtles 
         ((lines (getg 'draw-these))
          (lines (setg 'draw-these (cons (line 
                                          (point x1 y1)
                                          (point x2 y2))
                                         (if lines lines '())))))
         (m-return lines)))

(define (add-line-pts p1 p2)
  (mlet* m-turtles 
         ((lines (getg-or 'draw-these '()))
          (lines (setg 'draw-these (cons (line 
                                          p1
                                          p2)
                                         lines))))
         (m-return lines)))

These functions also provide an example of using the turtle monad with monadic notation to write monadic functions. In add-line we write a function which takes four values and returns a state function produced by the mlet* form using the turtles-monad (incidentally, this is:

(define m-turtles
  (list (cons 'bind m-bind)
        (cons 'return m-return)
        (cons 'plus #f)
        (cons 'zero poof)))

Monads are simply dictionaries containing the appropriate operators.

add-line fetches the value of the global key draw-these or an empty list, conses a new line onto that list, and finally sets the value of that key with setg. To finally draw our drawing, we'll call our monadic function on an initial state (

(define init-state (doublet '() '()))

), take apart the returned state doublet, grab the draw-these data from the global state, and pass it to Racket's GUI library. This tutorial is already too long to provide all the code to do that, but you can download it all from my github. The interface is easy enough. The function called turtles-go takes a turtle-state fun and applies it to an empty initial state, pulls out the drawing after the function is finished, and draws it.

Let's practice using the turtle monad to draw something. How about a regular n-gon? A regular n-gon is defined by an edge length and a number of sides. A regular n-gon's interior angles are all the same and add up to (n-2)pi radians, which means they must each be ((n-2)pi)/n radians. To draw such a figure, we can just move by and edge length, rotate by the appropriate angle and repeat the process until we reach the number of sides the polygon has.

We'll need a move and a turn function:

(define (turn amount)
  (mlet* m-turtles
         ((helicity (getl-or 'helicity 1))
          (facing (getl-or 'facing (/ pi 2)))
          (new-facing (setl 'facing
                            (+ (* amount helicity) facing))))
         (m-return new-facing)))

(define (move amt)
  (mlet* m-turtles
         ((pos (getl-or 'pos (point 0 0)))
          (facing (getl-or 'facing (/ pi 2)))
          (non-monadically: 
           ((facing-vector 
             (direction->vector facing))))
          (new-pos (setl 'pos (point+ 
                               pos (scale facing-vector amt)))))
         (m-return new-pos)))

(define (move-line amt)
  (mlet* m-turtles
         ((pos (getl-or 'pos (point 0 0)))
          (new-pos (move amt)))
         (add-line-pts pos new-pos)))

The turtle's current direction is stored in the local variable facing, its current position stored in pos. turn also uses a value called helicity to determine which way the turtle turns. For now, we'll always use the default value of 1. move-line just does the appropriate move and adds a line between the previous and new-current point.

(define (n-times fun n)
  (if (= n 1) fun
      (mlet* m-turtles
             ((_ fun))
             (n-times fun (- n 1)))))

n-times takes a monadic function and causes it to execute n times. Ok, here is our polygon drawing routine:

(define (n-gon n edge-len)
  (let* ((int-ang (/ (* (- n 2) pi) n))
         (ext-ang (- pi int-ang)))
    (n-times
     (mlet* m-turtles
            ((p (move-line edge-len))
             (a (turn ext-ang)))
            (m-return p))
     n)))

And here is how we use it:

(turtles-go
 (mlet* m-turtles
        ((p (jump-to 150 150))
         (p2 (n-gon 6 30)))
        (m-return p2)))

And here is the result:

So we're still in regular old turtle territory. Can we see an example of hyper turtle action? Well, what would you think the following will produce?

(turtles-go
 (mlet* m-turtles
        ((p (split-setl
             'pos
             (list (point 150 150)
                   (point 200 150)
                   (point 150 200)
                   (point 200 200))))
             (p2 (n-gon 6 30)))
            (m-return p2)))

Instead of just jumping to the single point 150 150 we've instructed our turtle to jump in parallel to four different points, and then to cruise along drawing a polygon just as before. What is the result?

We can do some pretty neat things in short order by changing the way motion commands are interpreted by the turtle. Remember the helicity option? Helicity changes the way individual turtles interpret turn commands:

(turtles-go
 (mlet* m-turtles
        ((p (split-setl
             'pos
             (list (point 150 150)
                   (point 200 150)
                   (point 150 200)
                   (point 200 200))))
         (h (split-setl
             'helicity '(-1 1)))
          (p2 (n-gon 6 30)))
         (m-return p2)))

Results in:

We can do tons of things by modifying helicity, but lets do one more different trick:

(turtles-go
 (mlet* m-turtles
        ((p (jump-to 150 150))
         (n (split-setl
             'n '(3 5 7 9 11 13)))
          (p2 (n-gon n 30)))
         (m-return p2)))

Results in:

Eee gads! We've drawn the first six prime n-gons all at once! I leave you to consider what could be done with the following combinator:

(define (move* amt)
  (mlet* m-turtles 
         ((jitter-mag (getl-or 'jitter-mag 0))
          (non-monadically:
           ((amt (+ amt (random-normal 0 jitter-mag)))))
          (pos (getl-or 'pos (point 0 0)))
          (_ (move amt))
          (pos2 (getl 'pos))
          (f (getl-or 'move*-fun (lambda () add-line-pts)))
          (_ (f pos pos2)))
         (m-return pos2)))

Musings on Monads

Besides drawing pretty pictures, what are we trying to accomplish here? Well, if you go sniffing around the internet about monads, you'll often hear that monads "don't work" programming languages besides Haskell. Reasons proferred include "it is easier to use side-effects," "there isn't syntactic support," and "you need static typing." I'm not a Haskell programmer, so I can't speak too authoritatively on the subject static typing, but I think that at least in Lisp dialects, where the second argument can be easily dispensed with, the first argument doesn't hold water.

If you look up the Forth pages on the C2 Wiki you'll eventually come across the programmer's meme: Do the Simplest Thing That Could Possibly Work. This means what it says: when you've got a problem, don't worry about picking an optimal solution, just do the simplest thing that could possibly work.

In my mind, this was the simplest implementation of a hyperturtle graphics system.

Now, I know that is going to seem pretty crazy to a person just trying to wrap their heads around monads. Surely, you'll object, this can't be the simplest possible implementation! To that, I'd say go back and look at the implementation of return and bind which together add up to 21 or so lines of code. If we had the right monad transformers at our disposal, we could write the same monad in one line of code! Assuming we had a handle on each of the monads in question, what we'd have accomplished is the creation of a sub-langage with entirely novel semantics in a few tokens. Add the mlet* syntax (itself about 20 lines of syntax-case macro) and the minimal subset of turtle primitive functions, and we are suddenly looking at a domain-specific-language on steroids.

But this is a very simple solution! You write a short bind and return function, use the already "standard" monadic syntax, and inside those expressions, you've got a whole new programming language. Because everything is purely functional, up to this point you've made no hard design decisions. You haven't declared any global variables, thought about how to represent the persistent state of anything. The monad provides a clean bed to write code in - and you don't need much code to get somewhere interesting.

Performance might be a problem - but I'd suggest that as a prototype system the monad provides excellent semantics for any more efficient implementation to target. This is enhanced because of the very compactness of the implementation! You know what your system does when you design it this way, because all the important behavior is specified in one place.

Secondly, I hope the article has provided an example of the process by which monads are constructed and used that isn't particularly artificial. Most monad tutorials provide ad-hoc examples which don't do anything interesting, and use pre-fab monads. I hope this development of a free-form monad for a novel problem is interesting.

And that is about it!

As always, the code for this project is hosted on my github. Comments, critiques, corrections are extremely welcome!

Monadic Parser Combinators in Elisp, A Screencast

2011-05-25T17:03:00.001-07:00

Edit: Hosting back up, split over Ubuntu One and Amazon S3. Should be good for awhile! Sorry for any inconvenience.

So I recently gave a talk to the Triangle Area Functional Programmer's Group about Monadic Parser Combinators. If you don't know what these are, they essentially constitute a formalism for creating purely functional parsers by building them up from simpler ones. I really dig their minimal elegance, pure functionality and the fact that they are a monad that isn't the list or maybe monad, which is always what people use as examples. Oh, and the whole thing is in Emacs Lisp, which I think has lots of didactic benefits.

Oh Where Can I Get A Screencast of this Fascinating Talk??

If you'd like to see the talk, I've create a screencast of it in either AVI or OGV format. If you can use Ogg Video (and you should) that version is a lot cleaner looking and easier to read.

I'd like to point everyone to Drew Crampsie's SMUG Library for Common Lisp. Although I develop the MPCs from the ground up in the screencast, the basic shape of the library owes itself to Drew's very nice implementation notes on the library. And SMUG is more powerful in a variety of ways too. Check it out.

As usual, the whole talk (which is a series of elisp files) is available on my github.

Emacs Lisp Curios (some useful, some fanciful)

2011-04-25T18:51:00.000-07:00

A Quick Overview of the Curios in this Library

Since I've been place on the planet emacs blog roll, I thought I'd do a quick summary of the things it might be interested in that I've worked on. Code is available on my github.

Clojure-Style Destructuring Bind/Function Definitions

This library, defn.el, supports an approximation of Clojure's destructuring bind syntax. If you are familiar with Clojure, the following code will be recognizable:

(require 'defn)
(defn prod 
  ([[el & tail :as lst] acc]
   (if lst (recur tail (* el acc))
       acc))
  ([lst] (prod lst 1)))
(prod '(1 2 3 4)); -> 24

The above code demonstrates the declaration of a function, prod which has two arities: the number of arguments determines which body is executed. If one arg is passed in, prod calls itself with the appropriate initial value for its accumulator. If two arguments are provided, it uses a recur expression to call itself repeatedly, calculating the produce of a list passed in. This is done without growing the stack. You can recur within a single body perpetually.

defn and its anonymous cousin fn support destructuring on hash tables and association lists where each element in the list is a proper list:

(defn dst-demo [[:: x :x y :y]]
  (list x y))

(dst-demo (tbl! :x 10 :y 11)); -> (10 11)
(dst-demo '((:x 40) (:y 50))); -> (40 50)

Default values may be provided for both sequential and table forms using the :or keyword (clojure doesn't support :or for sequences). Destructuring can be nested arbitrarily deeply as well. There are also let forms which provide the same destructuring for let-like situations. All these forms expand to lexical-closures, but there are forms like defn_ which are identical but create dynamic scopes instead.

As with most heavy macro magic, you can't really use this library without byte compiling, but when this is done, it can be reasonably zippy.

Standalone Recur

I really like the recur feature from Clojure. I like it so much I factored it out of the defn implementation so that it can be used in situations where a lighter touch is required.

(require 'recur)
(recur-defun* prod (lst &optional (acc 1))
  (if (empty? lst) 
      acc
      (recur (cdr lst) (* acc (car lst)))))

Again, this won't blow the stack. The lambda list supports the whole cl style lambda list. Also provided is a let form which can recur on itself, recur-let.

Multi-methods

Another Clojure-inspired feature is multi-methods. These are a kind of proto-multiple dispatch "object" system, by which I mean they are slightly more general than any concrete object system. You can use them to implement a single-dispatch object system-like functionality, for instance:

(require 'multi-methods)
(defmulti volcalize-n-times (lambda (&rest args)
                          (pseudo-class-of (car args)))
  "Volcalization multi-method.") ;Must be executed before defunmethod

(defunmethod volcalize-n-times :cat (thing n)
  (loop for i from 1 to n do (print "Meow")))

(defunmethod volcalize-n-times :dog (thing n)
  (loop for i from 1 to n do (print "Woof")))

(defunmethod volcalize-n-times :human (thing n)
  (loop for i from 1 to n do (print "Lorem ipsum dolor sit
  amet, consectetur adipiscing elit. Nulla sed sapien ligula. Sed
  luctus cursus consequat. Morbi egestas magna auctor dui
  sagittis bibendum. Ut in felis sit amet eros eleifend ultricies
  gravida id ligula. Suspendisse potenti. Nulla semper porttitor
  massa, sed feugiat mauris tempor nec.")))

(defun pseudo-class-of (val)
  (gethash :pseudo-class val :thing))

(volcalize-n-times (tbl! :pseudo-class :cat :name 'tibald) 10)
; prints "meow" 10 times.
(volcalize-n-times (tbl! :pseudo-class :human :name 'vincent) 2)
; prints lorem-ipsum fragment twice.

Multimethods match their arguments via isa? predicate, which can be extended with functions like derives. For instance:

($ :cat derives-from :quadraped)
($ :dog derives-from :quadraped)
($ :human derives-from :biped)
($ :emu derives-from :biped)

Note that $ is a simple infix macro that swaps the function position with the first argument position in the top level of the subsequent forms.

(defmulti n-legs 
  (lambda (&rest args)
   (pseudo-class-of (car args)))
  "Number of legs multi-method")

(defunmethod n-legs :biped (o) 2)
(defunmethod n-legs :quadraped (o) 4)

(n-legs (tbl! :pseudo-class :human)) ;-> 2
(n-legs (tbl! :pseudo-class :cat)) ;-> 4

By writing the appropriate dispatch function you can create many kinds of crazy object systems. Dispatch is cached, so if the derives hierarchy doesn't change, dispatch is fast after the first method call.

Partial Application

Particularly because emacs lisp is dynamically scoped, its handy to have functions to create functions which handle lexical static for you. If you (require 'functional), you'll have access to these functions, which make point free programming more fun:

(mapcar (par #'+ 5) '(1 2 3));-> (6 7 8)

par partially applies a function on the right. pal does the same on the left. Both always return a function, so you can partially apply more arguments than a function has, in which case when you call the result, you'll get an error. Considering that elisp functions have variable and unlimited arity, this seemed like the most idiomatic accomidation. There are also some other interesting things in functional.el, though it probably should be called point-free.el.

With-stack

with-stack.el is an emacs lisp embedded stack language in the mode of Factor or Joy. It looks like this:

(||| 4 4 + ) ;-> 8

The macro ||| introduces a stack language form. Subsequent objects are interpreted as in a stack languages, with atomic forms pushing themselves onto the stack and symbols acting as "words" which manipulate the stack. The file stack-words.el defines many basic stack words, but you can define your own using the word: word.

(||| word: plus-four 4 + end: 10 plus-four ) ;-> 14

||| returns whatever is on the top of the stack at the end of evaluation. The stack is discarded between invocations of |||. The language supports the notion of regular "words" and parsing or immediate words, which are executed when they are encountered during the compilation scan of the stack language segment. An immediate word is written in the stack language itself, and sees the "future" stream of tokens as its stack. It may manipulate that stack as it sees fit before terminating, at which point, compilation continues till the next immediate word or the end of the stack segment.

(||| immediate-word: -lisp-val: '1>eval swap end:)
(||| -lisp-val: '(+ 1 1) ) ;-> 2

The language supports Factor/Joy style quotations and stack-words defines the most common combinators (if,loop,bi, etc). You can call emacs functions using a bit of sugar (shown above). The syntax 2>concat, for instance, means "call concat with two values from the stack." These glue-words are assumed to return 1 value, so don't forget to drop nils.

Conclusion

That is a bunch of the crazy stuff I have been working on. There are other projects in a half-way state of completion. All of these projects are on my github, as is this document. They depend on my giant pile of utils library utils.el.

Lexical-let Corner Case

2011-04-22T08:13:00.000-07:00

Emacs 24 will have actual lexical binding, but until that becomes the standard, we've got to satisfy ourselves with cl.el's lexical-let form, a codewalker which does some magical things to simulate lexical scope. Today I discovered the following corner case when combining lexical and dynamic scope on variables with the same name. Consider:

(setq x "Hi there")
(defun return-x () x)
(return-x) -> "Hi there"
(let ((x "Yo."))
  (return-x)) -> "Yo." ; Dynamic scope in action, 'x is shadowed.
(lexical-let ((x "Yo."))
  (return-x)) -> "Hi there." 
; lexical-let doesn't create a dynamic binding, so x
; is not shadowed
(lexical-let ((x "Yo."))
  (let ((x x))
    (return-x))) -> "Hi there", but should be "Yo."
; This is unexpected behavior.

What is the problem? The let expression in the last example is rewritten by the codewalker, which replaces the x in the binding form with a hidden name. This prevents x from being dynamically bound, even though the let should shadow the x inside return-x. I am not sure if there is a way around this that isn't incredibly baroque. Probably best to just be aware of it.

Deep Emacs Lisp Part 2

2011-04-16T13:32:00.000-07:00

Streams

Last time we went through a lengthy development of monads in emacs lisp. Most of our attention was focused on just getting the idea down, and we developed a pretty full list monad.

It was intimated at the time that the list monad can be thought of as a "possibilities" monad. That is, we have functions which depend on a single input, but can produce many possible outcomes.

Suppose we wish to understand the probabilty of of rolling a given number when combining N dice with different numbers of sides. Characterizing a particular fair die is easy enough.

(require 'utils)
(defun die-outcomes (n-sides) 
  (range 1 (+ n-sides 1)))
(die-outcomes 6) ;-> (1 2 3 4 5 6)

(Note: All the code here depends on my utils.el and other packages available from my github page).

You might want to know: what is the probability of rolling a 10 when I roll three six sided dice? You might have noticed that die-outcomes is a monadic function in the list monad. It takes a number and returns a list of outcomes. How can we use the monad to calculate the probability in question?

(require 'monads)
(let* ((outcomes (mlet*_ monad-seq
                  ((d1 (die-outcomes 6))
                   (d2 (die-outcomes 6))
                   (d3 (die-outcomes 6)))
                  (m-return (+ d1 d2 d3))))
       (n-outcomes (length outcomes))
       (n-tens (length (filter (par #'= 10) outcomes) )))
   (* 100 (/ n-tens (* 1.0 n-outcomes)))); ->  12.5 percent chance

This is a kind of interesting thing, if you think about it. While this certainly represents a brute force approach, the really neat thing is that we only just described the possible outcomes of each die. This is a very easy problem. We then just let the list monad sort out the details.

I just joined the Triangle Area Functional Programmers Group, and they recently considered the "Cracker Barrel Peg Board Puzzle" question. If you aren't familiar with the game, here is a guy solving it with a mnemonic device:

But mnemonic devices are pretty crappy programs for pretty crappy computers (brains). Can we do better? Well, in the spirit of the above dice example, instead of considering the problem "how do we solve the peg board puzzle?", let us consider instead the simpler problem: given a peg board, how do we enumerate all the moves that we can make on any given turn?

We're going to be working functionally, so lets decide an on a persistent representation of a game board. By persistent we here mean that when we modify such a structure, we actually get a copy of that structure back. One such representation is :

(defun fresh-board ()
  (alist>>
   0 '(0)
   1 '(0 1)
   2 '(0 1 2)
   3 '(0 1 2 3)
   4 '(0 1 2 3 4)))

We just represent a board as an alist with row indexes as keys and each row represented by a list of occupied positions. alist>> is a function from my utilities which just turns the above into:

((0 (0)) (1 (0 1)) (2 (0 1 2)) (3 (0 1 2 3)) (4 (0 1 2 3 4)))

Adding a removing a peg are somewhat obvious. We just dip into the alist to the appropriate row and remove the number of the peg we want to take out. Adding is the opposite operation. We will handle error checking at another level of abstraction, but we will at least maintain at this point that each row contains only unique peg positions.

We'll represent positions as cons cells with column as the cdr and row as the car.

(defun pos (x y)
  (cons x y))

And we'll be destructuring positions a lot, so lets whip up a quick macro for that:

(defmacro let-pos (peg-binders &rest body)
  (cond ((empty? peg-binders) `(progn ,@body))
        (t (let ((binder (car peg-binders))
                 (peg-sym (gensym "peg-")))
             `(let* ((,peg-sym ,(cadr binder))
                     (,(car (car binder)) (car ,peg-sym))
                     (,(cadr (car binder)) (cdr ,peg-sym)))
                (let-pos ,(cdr peg-binders) ,@body))))))

Example:

(let-pos (((x y) (pos 3 4)))
  (list :x x :y y)) ;-> (:x 3 :y 4)

There are more general destructuring bind operations lurking in the fetid depths of my emacs lisp library, but clarity demands we use this simple solution. Note that the macro accepts any number of position binding forms.

Now those board-related functions:

(defun peg-at-board? (board pos)
  (let-pos (((x y) pos))
           (mlet* monad-maybe^i
                  ((row (alist board y))
                   (at? ($ x in row)))
                  at?)))

(defun remove-peg (board pos)
  (let-pos (((x y) pos))
           (alist-conjugate board
                            y
                            (lambda (row)
                              (filter 
                               (f-not (par #'= x)) row)))))

(defun n-sort-cons (n n-list)
  (cond ((empty? n-list) (list n))
        ((= n (car n-list)) n-list)
        (($ n < (car n-list)) (cons n n-list))
        (t (cons (car n-list) (n-sort-cons n (cdr n-list))))))

(defun add-peg (board pos)
  (let-pos (((x y) pos))
           (alist-conjugate board
                            y (pal #'n-sort-cons x))))

Note: I snuck in a maybe-monad use up there. We will talk about it in a bit.

Don't worry too hard about these functions. They just do what they say on the tin, with the understanding that they return a new board with the indicated changes, rather than modifying the board. n-sort-cons is not tail recursive, but since there are no more than five pegs in a row, we aren't likely to blow the stack.

It will be handy to simulate moving pegs in a way that results in failure when we try to move off the board.

(defun on-board? (pos)
  (let-pos (((x y) pos))
           (and (>= y 0)
                (<  y 5)
                (>= x 0)
                (<= x y))))

(defun move1 (pos direction)
  (let-pos (((x y) pos))
           (let* ((new-pos
                   (case direction
                     (:nw (pos (- x 1) (- y 1)))
                     (:ne (pos x (- y 1)))
                     (:e (pos (- x 1) y))
                     (:w (pos (+ x 1) y))
                     (:sw (pos x (+ y 1)))
                     (:se (pos (+ x 1) (+ y 1))))))
             (if (on-board? new-pos)
                 new-pos
               nil))))

move1 takes a starting position and a direction (one of (:nw :ne :e :w :sw :se)) and returns the new position, if it is on the board. Using move1 we can define move-n which just repeats this process N times, or until we fall off the board. You can see this code on the github, its straightforward.

Ok, finally something interesting:

(defun generate-hop (board pos dir)
  (lexical-let ((pos pos))
    (mlet*_ monad-maybe^i 
            ((origin-occupied? (peg-at-board? board pos))
             (over (move1 pos dir))
             (target (move-n 2 pos dir))
             (over-occupied? (peg-at-board? board over))
             (target-empty? (not (peg-at-board? board target))))
            `((:remove ,pos)
              (:remove ,over)
              (:place ,target)))))

This function takes a board, a position, and a direction and generates a hop in that direction if one is allowed. It returns nil otherwise. This kind of thing is built for the maybe monad, so most of the function lives there. It is a good time to remind ourselves of how monads work. mlet*_ tells use we are going to be chaining our binding through a monad, in this case monad-maybe^i, which is defined in monads.el:

(defvar monad-maybe^i
  (tbl!
   :m-zero nil
   :m-return (lambda (x) x)
   :m-bind (lambda (v f)
             (if (not v) v
               (funcall f v))))
  "The (implicit) MAYBE monad.  
   NIL indicates failure.  
  MaybeVal is the identity.  
  Just is the identity.")

This monad is a variation on the regular old maybe monad which just lets the programmer express failure with a regular old lisp nil instead of a tagged value. Hence the zero of this monad is just nil. Return is the identity function, and bind is almost funcall, but not quite. If the monadic value passed in is nil, it doesn't apply the monadic function. It just returns nil. The net effect is that if any expression in the mlet* expression above is nil, the whole expression evaluates to nil, short circuiting through the subsequent expressions. Handy. Monads are cool (see footnote 1 for why this monad has an ^i).

Ok, so now we have a function which can generate a hop. It returns a list of instructions on how that hop is implemented which we can use to modify a board to effect that hop. These instructions can be thought of as a really dead simple programming language, so we can write a function:

(defun interpret-hop (board hop)
  (reduce 
   (lambda (board move) 
     (let ((what (car move))
           (where (cadr move)))
      (case what
        (:remove (remove-peg board where))
        (:place  (add-peg board where)))))
   hop
   :initial-value board))

Which takes a hop and modifies the board to account for that move. Apart from a bit of book keeping, we've solved the peg-puzzle. We can write a function which returns all the legal hops for a given board quite easily using the list-monad.

(defun generate-hops (board)
  (if (board-solved? board) (list board)
      (mlet*_ monad-seq^i 
        ((direction       (list :nw :ne :e :w :sw :se))
         (position        (generate-positions))
         (hop             (generate-hop 
                           board position
                           direction)))
       hop)))

(Astute readers might notice we could partially apply the board argument of generate-hop and then lift-2 the resulting function into the sequence monad, then apply it to the lists of positions and directions. The provided approach is probably easier to read for people not too familiar with monads.)

Now solving the problem is just matter of applying generate-hops thirteen times, taking care to produce a new set of boards from the generate hops at each step.

If you try this, you'll find that it takes a very long time. The peg game has a pretty large state space, and its a hassle to generate ALL solutions when we really don't want all of them, at least not all at once. Can we recapture the elegance of this simple, declarative solution without having to calculate every single win condition?

Enter Streams

One way we can use essentially the same methodology but not have to calculate all the answers is to use lazy lists or streams. Emacs doesn't have them, so we are going to have to roll our own, but they aren't conceptually that difficult. A stream is simply a conceptual pair of objects. The first object represents the head of a the stream. The second object is a function which returns the rest of the stream when called. From these simple beginnings we can produce a data structure with all sorts of unusual behaviors. For instance, its possible to create an infinitely long stream of, for instance, all the integers starting with 1 or all the Fibonacci numbers. Even though such streams are conceptually infinite, we can pass then around and operate on them almost as we would any list. We can even do things which seem counter-intuitive at first, for instance, mapping a function over an infinite stream to produce a new, infinite stream.

Streams take some getting used to, but the process can be very enlightening. For instance, one learns quickly why Haskellers are not as concerned about non-tail recursion when writing stream functions. If the recursion occurs inside the "future" of the stream, you get a free trampoline.

Laziness, however, takes special care in Emacs Lisp, because variables are not lexically scoped by default. This means every time you create a lambda which you intend to be called later, you have to make sure to explicitly lexically-let over it, indicating whatever variables the lambda depends upon. In a way, this is good, because it forces us to think consciously about closures, which are important ideas in functional programming. However, it can get syntactically busy to be wrapping up things in lexical-let forms all the time, particularly because we often want only to create a lexical copy of a dynamically bound variable.

Ergo, our very first step in creating a stream library is to create a nice form for delaying computations.

(defun single-symbol-list? (item)
  (and (listp item)
       (= (length item) 1)
       (symbolp (car item))))
(defun binderish? (item)
  (and (listp item)
       (= (length item) 2)
       (symbolp (car item))))

(defun with-form->binder (item)
  (cond ((symbolp item )(list item item))
        ((listp item)
         (cond ((single-symbol-list? item)
                (cons (car item) item))
               ((binderish? item)
                item)
               (t (error "with-forms require symbols, 
                          a single symbol list, or a binder-like 
                          expression.  Got %S." item))))
        (t (error "with-forms require symbols, 
                   a single symbol list, or a binder-like 
                   expression.  Got %S." item))))

(defmacro* later (expr &key (with nil) (with* nil))
  (cond (with 
         `(lexical-let ,(mapcar #'with-form->binder with)
            (later ,expr :with* ,with*)))
        (with* 
         `(lexical-let* ,(mapcar #'with-form->binder with*)
            (later ,expr)))
        (t `(lambda () ,expr))))

The macro later takes a single expression and wraps it in a lambda with no arguments. This is exactly the sort of lambda which forms the tail of streams. Because the contents of the tail expression often depend on variables dynamically bound at the time the lambda is created, later lets you specify which values to produce a closure over in several ways.

(later 10) ;-> (lambda () 10)
(let ((x 10))
  (later x :with (x))) -> (let ((x 10))
                            (lexical-let ((x x))
                             (lambda () x )))
(let ((x 10)) 
   (later y :with ((y (+ x 1))))) ->
 (let ((x 10)
    (lexical-let ((y (+ x 1)))
      (lambda () y))))

(let ((x 10))
  (later z :with* ((y (+ x 1))
                   (z (+ x y))))) ->
  (let ((x 10))
    (lexical-let* ((y (+ x 1))
                   (z (+ x y)))
      (lambda () z)))

In words, later takes an expression and a list of binding expressions which are similar to let binders, but which can be single symbols, which expand to a (x x) binding expression. Now we are equipped to do a reasonable job implementing streams.

(Note: These streams are based loosely on those covered in "The Reasoned Schemer", although they've been adapted to stand alone from the Kanren interpreter and also to be more easily understood (to me)).

We could represent streams as cells, build them using "cons," etc, but I prefer to have a bit more error detection built into the implementation. I don't want to accidentally use a list as a stream or vice versa. Emacs provides some basic facilities for defining new "types," with defstruct (see Footnote 2).

(defstruct stream head future)
(defun stream (hd &optional future)
  (make-stream :head hd :future future))

This defines the functions make-stream, stream-head, stream-future and stream-p. Good enough for use to get started, certainly. The function stream is just the stream analog of cons, it creates a stream cell. We allow the tail to be optional, because we'll want to create streams of one element frequently. Incidentally, stream with one element is our return operation for the stream monad.

What about car and cdr? Stream car (scar) is easy enough:

(defun scar (stream)
  (cond ((not stream) nil)
        (t 
         (progn
           (if (not (stream-p stream))
               (error "Tried to take the scar of a non-stream %S." stream))
           (stream-head stream)))))

The first cond checks for the nil stream, which we represent with nil. If the stream isn't nil, it returns the head portion of the stream. Easy enough.

(defun scdr (stream)
  (cond ((not stream) nil)
        (t
         (progn
           (if (not (stream-p stream))
               (error "Tried to take the scdr of a non-stream %S." stream))
           (let ((fut (stream-future stream)))
             (if fut
                 (progn 
                   (if (not (functionp fut)) 
                    (error "The future of a stream must be 
                            either nil or a function.  Instead its %S" fut))
                   (let ((fut (funcall fut)))
                     (if (not (stream-p fut)) 
                      (error "The future of a stream must 
                              evaluate to a stream.  Instead it was %S" fut))
                     fut))
               nil))))))

scdr is longer, but it is simple enough. Check for nil, in which case the scdr is nil. Otherwise, grab the lambda in the second half of the stream and call it, checking to make sure that the output is itself a stream. Return that.

defstruct created stream-p for us, which tests to see if an object counts as a stream, but we want the definition to include the nil object, so we should define for later:

(defun stream? (x) (or (not x) (stream-p x)))

I like the question-mark indicates predicate style better anyway.

It is convenient to split a stream into three cases. The first case is the nil stream, the second is a stream with one element, and the third is a stream with a future. Lots of algorithms need to act differently in these cases, so we should write a macro over them:

(defun stream-future-nil? (object)
  (nil? (stream-future object)))
(defun stream-with-future? (object)
  (not (nil? (stream-future object))))

 (defmacro stream-case (stream
                        nil-case
                        =a=expressions
                        =a-f=expressions)
   (with-gensyms 
    (stream%)
    `(let ((,stream% ,stream))
       (if (not (stream? ,stream%)) 
          (error "Stream-case needs a stream 
                  input, got instead %S." ,stream%))
       (cond 
        ((nil? ,stream%)
         ,@nil-case)
        ((stream-future-nil? ,stream%)
         (let ((,(car (car =a=expressions)) (scar ,stream%)))
           ,@(cdr =a=expressions)))
        ((stream-with-future? ,stream%)
         (let ((,(car (car =a-f=expressions)) (scar ,stream%))
               (,(cadr (car =a-f=expressions)) (stream-future ,stream%)))
           ,@(cdr =a-f=expressions)))
        (t (error "Couldn't figure out what to do 
                   with stream %S.  This should never 
                   happen." ,stream%))))))

Stream case figures out which condition our stream is in, and then destructures the stream into the appropriate parts. When the stream is nil, the first body form is simply executed. When the stream is a singleton, the value contained in the stream is bound to a symbol the user passes in and the bodyforms are executed in that context, and when there is a value and a future-stream, those are bound to user defined symbols in a body for that case. It is all wrapped up in a hidden cond.

Example:

(let ((s (stream 'x (later (stream 'y nil)))))
  (stream-case s
    ((print "this is not executed because s is not nil")
    ((a) (print "If the stream had a single element, a would be
  bound to it here"))
    ((a f) 
     (print "This case is executed becase s has a future, a is the
  `scar` of s, f is the function which produces the future
  stream.")))))

About the simplest function we can write acting on streams is take-n, which simply takes a limited number of elements from a stream and converts them into a list.

(defun take-n (stream n &optional acc)
 (if (= n 0) (reverse acc)
   (stream-case stream 
     ((reverse acc))
     ((a) (reverse (cons a acc)))
     ((a f) (take-n 
             (funcall f) (- n 1) (cons a acc))))))

This function will return fewer than the requested number of elements if the stream ends before n is reached. Readers might notice this is a tail-recursive function. Emacs doesn't support tail-recursion natively, but I wrote a library that does, so we can define this function this way:

(require 'recur)
(recur-defun* take-n (stream n &optional acc)
  (if (= n 0) (reverse acc)
    (stream-case stream
                 ((reverse acc))
                 ((a) (reverse (cons a acc)))
                 ((a f) (recur (funcall f) (- n 1) (cons a acc))))))

This will never blow the stack, which is important, since we want to take many elements off a stream without worrying about whether the stream is shorter than the recursion limit.

Ok. With just these few functions we can play with some non-trivial streams.

(defvar *ones*
   (stream 1 (later *ones*))
   "Infinite stream of ones.")

(defun ints-from (n)
  (stream n (later (ints-from (+ n 1)) :with (n))))

(take-n (ints-from 5) 10) ;-> (5 6 7 8 9 10 11 12 13 14)
(take-n (ints-from 10) 10);-> (10 11 12 13 14 15 16 17 18 19)

These are really just parlor tricks, though. See if you can figure out how to define forever, which is a function which takes a value and returns a stream of that value forever. Or repeating, which takes a list and returns a stream which is that list repeated over and over again.

Note that even though functions like ints-from appear to call themselves, they do so only after they return their stream. There isn't any real recursive call - the stream serves as a trampoline. These functions won't blow the stack.

Building Towards the Stream Monad

Streams are obviously somewhat analogous to lists. Lists form a monad with list and map-cat as the return and bind operations respectively. We'd like to form a monad with streams too. Then we could do some truly interesting things with mlet* like notation, cuing up potentially infinite calculations into a nice list-like package.

We've already determined that the return operation for a stream monad would simply be the function which puts a single value into a singleton stream:

(defun stream-return (x) (stream x))

We need to build up to mapcat for streams, and then we will have our monad.

Streams get a little confusing at this point. The key to keeping our head straight is to remember that the tail of the stream always needs to be handled in such a way as to maintain the laziness of the stream. When you map over a stream, you don't actually visit the rest of the stream at the time of the map. You simply return a new stream whose future includes the fact that it needs to apply a function to each value before returning it. stream-map is just as lazy, in other words, as our streams.

Let's write smapcar, that is stream-map-car. The exact analog of the list mapcar function. It will take a function and a stream and return a new stream which is that function applied to every element in the input stream.

(defun smapcar (f stream)
  (stream-case stream
    (nil) ; empty stream -> empty stream
    ((a) ; singleton stream -> singleton stream of (f a)
     (stream (funcall f a) nil))
    ((a future)
     (stream (funcall f a)
       (later (smapcar f (funcall future)) :with (f future))))))

The only case which might be confusing is the last case. The stream-case expression extracts a, the value at the head of the stream, and future, the function which returns the future of the stream. We form a new stream whose head is (f a) and whose future is the mapping of f onto the future of the input stream. This mapping occurs later, only when someone asks for the future of the output stream.

It is possible to write a generalization of this function which maps a multi-input function over multiple streams. I'll leave such a function to the reader, but I will provide here a function smapcar2 which maps over two streams, because it will let us construct some interesting streams.

(defun smapcar2 (f-of-2 stream1 stream2)
  (stream-case stream1
               (nil)
               ((a) (stream-case stream2
                     (nil)
                     ((b) (stream (funcall f-of-2 a b) nil))
                     ((b g)
                      (stream (funcall f-of-2 a b) nil))))
               ((a f)
                (stream-case stream2 
                 (nil)
                 ((b) (stream (funcall f-of-2 a b) nil))
                 ((b g)
                   (lexical-let ((f-of-2 f-of-2)
                                 (f f)
                                 (g g))
                    (stream (funcall f-of-2 a b) 
                     (lambda () (smapcar2 f-of-2 (funcall f)
                      (funcall g))))))))))

With smapcar2 we can finally create things like the stream of Fibonacci Numbers:

(defvar fibs (stream 1
                      (later 
                        (stream 1 
                                (later (smapcar2 #'+ fibs (scdr fibs))))))
   "The stream of Fibonacci numbers")
(take-n fibs 10) ;-> (1 1 2 3 5 8 13 21 34 55)

Whee! An eternal golden braid, etc!

Stream Map & Concatenate

We might think that all we need to do now is define stream-map and stream-cat and then stream-map-cat would be the composition of these functions. This might almost be made to work except that either operation might be produce an infinite stream of results. It is more straightforward to interleave the concatenation with the map operation. We can define stream-cat by itself:

(defun stream-cat (stream1 stream2)
  (stream-case 
   stream1
   (stream2)
   ((a) (stream-case stream2 
                     ((stream a nil))
                     ((b) (stream a (lexical-let ((b b)) 
                                      (lambda () (stream b nil)))))
                     ((b g)
                      (stream a (lexical-let ((b b)
                                              (g g))
                                  (lambda () (stream b g)))))))
   ((a f)
    (stream-case stream2
                 ((stream a f))
                 ((b) (stream a 
                              (lexical-let ((f f)
                                            (stream2 stream2))
                                (lambda () (stream-cat (funcall f) stream2)))))
                 ((b g) 
                  (stream a 
                          (lexical-let ((f f)
                                        (stream2 stream2))
                            (lambda () (stream-cat (funcall f) stream2)))))))))

This function is a doozy, but the upshot is simple. If either stream is empty, we return the other stream, obviously. Otherwise we lazily pass stream two down stream one, until we find the tail of stream one, whereupon we fasten stream two. A call to stream cat doesn't instantaneously modify the entirety of stream1, it should be noted. It modifies just the tail, essentially passing instructions "down the line" to further modify each tail until a nil.

We can now define stream-map-cat.

(recur-defun* stream-map-cat (mf stream)
  (lexical-let ((mf mf))
    (stream-case stream
                 (nil)
                 ((a) (funcall mf a))
                 ((a f) 
                  (lexical-let ((interior-stream (funcall mf a))
                                (f f))
                    (stream-case 
                     interior-stream
                     ((recur mf (funcall f)))
                     ((b) (stream b 
                                  (later
                                   (stream-map-cat mf (funcall f)))))
                     ((b g) (stream b
                                    (lexical-let ((g g))
                                      (later 
                                       (stream-cat (funcall g)
                                                   (stream-map-cat mf (funcall f)))))))))))))

stream-map-cat is actually pretty easy to understand if you remember that mf is going to be a monadic function of the stream monad, and so whatever is passed in, mf always returns a stream (see Footnote 3 for a subtlety). Obviously if the input stream is nil, the output is also. If input has a single element, then mf on that element is the output stream. When there is a non-trivial stream, then we evaluate the monadic function to get the interior-stream and lazily concatenate it on the tail of the result of map-cat on the rest of the input stream.

That is it. We have the stream monad:

(setq monad-stream 
      (tbl! :m-bind #'stream-bind
            :m-return #'stream-return
            :m-zero nil))

So what can we do with it?

We'll, besides implement Kanren, the point of all this, I can think of at least one interesting example. Emacs provides functions to generate random numbers with a uniform distribution. random* from the cl.el library is able to produce such numbers in any given range. Consider the function:

(defun* random-numbers (lim &optional (state (make-random-state)))
  (let* ((*random-state* state)
         (val (random* lim)))
    (lexical-let ((new-state (make-random-state))
                  (lim lim))
      (stream val (lambda () 
                    (random-numbers lim new-state))))))

This function takes a limit and an optional state and returns a stream of uniformly distributed numbers. Using a dynamically bound *random-state* and the fact that make-random-state returns the current state, the resulting stream returns an infinite, but repeatable, list of uniformly distributed numbers.

Uniform distributions are fine, but we often want Guassian numbers. There are several ways to get them if you have uniform distributions. One way is to take the average of many uniformly distributed numbers. These averages will have a Gaussian distribution which can be scaled to whatever standard deviation is desired. A way which is less computationally intensive, however, is the Box-Muller transformation, which takes two independent distributions of uniformly distributed numbers and returns two distributions of Guassian numbers. If u and v are uniformly distributed, then

p = sqrt(-2*log u)*cos(2 pi v)
q = sqrt(-2*log u)*sin(2 pi v)

p and q are two independent but normally distributed numbers. If we don't care about the seeds in particular, only that they are different, we can create a stream of Guassian numbers like so:

(defun zip-streams (&rest streams)
  (apply #'smapcar* #'list streams))


(setq normal-numbers 
      (mlet**_ monad-stream ((pair
                  (zip-streams (random-numbers 1.0)
                               (random-numbers 1.0
                     (make-random-state t)))))
               (lexical-let ((u (car pair))
                             (v (car pair))
                             (r (sqrt (* -2 (log  u))))
                             (s (* 2 pi v)))
                 (stream (* r (cos s))
                         (later (stream (* r (sin s)) nil))))))

The monad handles collecting the two results into a single stream for us, and the result is itself an infinite list of normally distributed numbers. I don't know about you, but I think that is pretty cool.

Don't Interleave Just Yet

Because streams can be infinite, sometimes we don't want to strictly concatenate them. We can certainly concatenate a stream of infinite ones and a stream of infinite twos, but the result will be, effectively, a stream of infinite ones. The twos will be conceptually at the end of this stream, but you'll never reach them. Because of this, we sometimes want to interleave the results of monadic functions. Hence, this library provides an alternative monad monad-stream^i which has this behavior. In this case i means "interleave" rather than implicit. I'm going to have to do something about that.

The Peg Puzzle

If you return to the peg puzzle, making the minor changes you need to adapt the functions which enumerate possible moves so that they return streams, you can use almost the exact same code to produce a lazy-list of all possible solutions to the peg game. The full code is available in the examples directory. Using this code, one can queue up all the solutions to the puzzle, actually examining and returning only those which are needed.

I've implemented a slightly more complex version of the peg puzzle problem so that we end up with not just a stream of solved puzzles, but a stream of solved puzzles AND the included solution as a list of instructions. It's too lengthy to reproduce here, but you can see the code here.

As always, all the code here, and this tutorial, are available from my github account.

Footnote 1: I've found it handy define a set of "implicit" monads, the defining feature of which is bind does a lot more heavy lifting, basically squeezing non-monadic values into the monad if it encounters them during its work. For instance, the implicit list monadic bind operation takes two arguments. When the first is a list, bind is identical to the non-implicit list monad, but when it isn't a list it is wrapped in one before things proceed. Similarly, monadic functions may return non-lists, and when this happens, they are simply loaded into lists before being treated normally. The end effect is that you don't have to decorate all your expressions with m-return all the time. The only time you need to use one is when you really mean to return a list of nil rather than nil itself.

This might be a crazy thing, but seems ok to me! It seems to be more appropriate for dynamically typed languages because functions are always modifying their behavior to fit the input types anyway.

Footnote 2: Deftype produces a type which is unfortunately true under vectorp. Too bad.

Footnote 3: The function shown here is technically correct, in terms of the final values that appear in the stream and where. However, it is not as lazy as it could be. The key recognition is that, while mf is not the tail of a stream, the partial application of mf to a is a function which takes no arguments and returns a stream. That is, (lambda () (funcall mf a)) is an acceptable stream tail, and we don't need to evaluate mf a to use it as such. The following code implements this fully lazy version of stream-map-cat, here called stream-map-cat-tail. The only thing you need to understand in addition to the above is that par in the following code stands for partially apply on the right.

(defun stream-cat-tail (head-stream tail)
  (if (stream? head-stream)
      (stream-case head-stream
                   ((funcall tail))
                   ((a) (stream a tail))
                   ((a f)
                    (stream a 
                            (later 
                             (stream-cat-tail (funcall f) tail) :with (f tail)))))
    (stream-cat-tail (funcall head-stream) tail)))

(defun* stream-map-cat-tail (mf instream)
  (stream-case instream
               (nil)
               ((a) (funcall mf a))
               ((a f)
                (let ((tail (par mf a)))
                  (stream-cat-tail tail
                                   (later
                                    (stream-map-cat-tail mf (funcall f))
                                    :with (mf f)))))))

stream-cat-tail pins the function tail at the end of the stream head-stream. It turns out to be convenient to pass functions returning streams into the head-stream position, so this function checks for that case and extracts the head stream if needed. The library actually uses these functions rather than the slightly less lazy version in the tutorial body. I found that version easier to understand at first.

Deep Emacs Lisp Part 1 (Basically, a Monad Tutorial)

2011-04-09T08:27:00.000-07:00

Implementing Monads

(Note: everything in this tutorial (and this tutorial) is available on my github)

I've started working on an implementation of Kanren, the logic mini-language covered in The Reasoned Schemer, in Elisp. I want to write about this process vis-a-vis the unique considerations of Emacs Lisp as a language, but its a middle sized project, which depends on several pieces of code, which themselves depend on code which I haven't described in detail anywhere. Kanren depends on a monad (the "stream of substitutions" monad, for the nerds out there). An implementation of this monad is a good place to start when thinking about implementing Kanren itself, but I've never written up a piece of documentation on the implementation of Monads I've cooked up for Elisp, so I thought I'd start there.

So, this document one part monad tutorial and one part introduction to the monads.el implementation.

First, credit where its due: the following implementation of Monads owes is basic form to the monad library in Clojure-contrib. I wrote it while reading through Jim Duey's completely excellent monad tutorials for clojure.

Besides minor considerations associated with dealing with the default dynamic scope in Elisp, the implementation here is basically that of the Clojure Contrib library. And I could never have understood what I was doing without the tutorial.

Onto the Monads

We've reached the monad tutorial part of this document. Like most people, I found monads pretty hard to understand when I first encountered them. Most monad tutorials speak in Haskell, which I think can be doubly confusing because its hard to tell exactly where Haskell ends and where monads begin, since Haskell has special syntax built in to the language just for the purpose of dealing with monads. You can, of course, use the functions >>= and return outside of do notation, as many tutorials do, but at least dealing with >>= requires a fair amount of comfort with Haskell's infix operator system. At least it seemed that way to me.

I really had to implement monads in Elisp to finally get it. I think this worked because every part of the monad beastiary had to be built from the ground up. If you want "do notation," for instance, it isn't just there, you have to write a macro for it, and understand it. The uniformity of Lisp syntax (which some people hate, I know) also helps keep things focused on the ideas. That is the approach we will take here. We'll start just kicking around some general ideas and gradually build up to do notation, making constant analogy to well understood lisp and programming concepts. I think this is better than throwing oneself in head first.

Notes on Types

I think of a monad as a way of decorating function composition. If I have a group of functions that conform to a particular input and output constraint, a monad associated with that constraint tells me how to combine those functions so that something interesting happens. The fact that these functions all have the same type of input and output is critical, otherwise the "plumbing" specified by the monad won't work. Such functions are called "monadic functions" and when we try to understand monads, or a specific monad, we must meditate on the type of these functions.

When coming to monads from dynamic languages, it can be easy to gloss over all the type language used to describe them. But it really helps to think about types in a loosy-goosey way, at the very least, because type constraints are what make the plumbing in a monad work. Monads generally contain things. In statically typed languages the monad type depends on the type of the things it holds, so it would be specified, but we'll just refer to these things as "values". Their type isn't terribly important except that they are distinct from the type of monadic values.

A monadic value can be thought of as an abstract container which contains regular values. Sometimes this is a rather obvious kind of relationship. A list "contains" values, for instance. Sometimes it can be much more abstract.

Finally, there are monadic functions. A monadic function is a function which takes a regular value and returns a monadic value. It is important to think about these types while we work on the rest of the tutorial, so take a second to look at the diagrams, and then get into the habit of calling to mind the types of various objects whenever you get confused. It really helped me.

The List or Sequence Monad

We'll be talking about the sequence monad first. We will represent sequences with regular old lisp lists, which can hold values of any lisp type. The monadic values, then, are lists. Lists "contain" (they also contain) lisp data. Let us meditate upon the type of monadic functions in the sequence monad.

==== this space reserved for meditation ====

If you guessed in your meditation that the monadic functions associated with the sequence or list monad (we'll use the two interchangeably from here on) are functions which take a single value, which is any lisp data, and return a list of lisp-values, you got it.

So, whatever the hell a "list monad" is, its got something to do with composing functions which take a single lisp value and return a list.

What kind of functions might do this? Well, a common idea is that functions in the list monad represent computations with multiple possible outcomes or values. A person might have multiple friends, so a function get-friends might return a list of persons rather than a single person. We might want to go on to calculate those persons' friends (or enemies, relatives, lovers). All these get- functions would be monadic functions in the list monad, and the list monad will help use deal with them.

Let's start kicking around ideas about composing these functions. To do that we need a few functions to consider explicitly. What are the simplest monadic functions of the list monad? Well list is certainly such a function when you call it with one argument, so lets put that on the pile. In that spirit, consider:


(defun stub (x) nil)
(defun list-return (x) (list x))

list-return can be thought of as a sort of "default" or "simplest possible" monadic function. We've just wrapped up list so that it takes but one argument. Every monad needs a return, and every return does something like the above - it wraps its input into the monad in a simple way.

stub is also a monadic function - it ignores its inputs and returns the empty list.

Ok, lets write some semi-meaningful list-monadic functions. Consider:


(defvar *people* '(:ted :lea :leo :james 
                   :harvey :sally :jane :andrew 
                   :catherine) 
                   "A list of all the people that matter.")
(defvar *friends-db* 
      '((:ted (:lea :leo :sally :andrew :catherine :leo :jane))
        (:lea (:ted :leo :jane :andrew :harvey :sally :catherine))
        (:leo (:ted :lea :ted :harvey :sally :jane :andrew 
                    :catherine :harvey :andrew :catherine))
        (:james (:jane :harvey :jane))
        (:harvey (:leo :lea :leo :james :harvey :harvey :sally))
        (:sally (:ted :leo :lea :harvey :jane :andrew))
        (:jane (:lea :leo :james :sally :ted :james :andrew :catherine))
        (:andrew (:ted :lea :leo :sally :jane :leo))
        (:catherine (:ted :leo :lea :leo :jane :catherine :catherin))) 
"Our database of friend connections.")

(defun friends-of (person) 
  "Return a list of all the people in friends-db."
  (alist *friends-db* person)
         ;alist is a function which retrieves
         ;a key's data from an association list.
)

(defun mutual-friends-with (person1)
  "Return a monadic function which returns 
   the friends person1 has in common with person2."
  (lexical-let ((p1-friends (friends-of person1)))
    (lambda (person2) 
      (let ((p2-friends (friends-of person2)))
       (filter (lambda (friend)
                 (in friend p1-friends)) p2-friends)))))

Friends-of is more or less obvious enough. It simply retrieves the database entry in the friends database, here represented as an association list. It takes a person and returns a list of persons, so it is a monadic function.

The second function is a little more complicated. It takes a person and returns a function, so its not a monadic function itself. It does, however, return a monadic function - one parameterized on person1. It returns the friends of person2 that are also friends with person1. This business of having a function which returns a parameterized monadic function is pretty common, and it will lend monadic expressions a certain domain-specific-language feel, as you'll see. Note that we need a lexical-let in the function body to create a closure around p1-friends. If we used a let, p1-friends would be out of scope by the time someone called the lambda. If this is confusing, see the wikipedia article on scope in programming languages. Emacs has a default dynamic scope, but most modern languages are lexical².

But we were meditating on function composition. Before going any further lets implement a function which composes functions. The only wrinkle here is that order of composition is reversed from the order of application (f1 is applied before f2) because this looks more natural in an applicative language.


(defun compose2 (f2 f1)
  "Compose F2 and F1 by returning a new function which
   calls F1 on its arguments, then calls F2 on the result"
   (lexical-let ((f1 f1)
                 (f2 f2))
    (lambda (&rest args)
      (funcall f2 (apply f1 args)))))

(defun compose (&rest fs)
  "Compose the functions FS (FN FN-1 FN-2 ... F1) 
   beggining with F1 and working backwards."
  (let ((rfs (reverse fs)))
   (reduce
     (lambda (acc-f f)
       (compose2 f acc-f))
     (cdr rfs)
     :initial-value (car rfs))))

Let's try just composing some of our list monadic functions. We might actually want a function to calculate the friends-of the friends-of someone:


(compose #'friends-of #'friends-of)

Because this is Elisp, this doesn't cause an error. Of course, if we think about this, we know it can't work. As soon as well call this function, we'll get an error (actually, it will return nil, because a list of friends is not a key in the friends db), because the second friends-of will be applied to a list, rather than a single person. Try it, if you are having trouble seeing it.

Suppose we were dead set on jamming these two functions together and, in particular, we want to make sure that the resulting function can be used wherever either of the two functions might have been used. That is, we want the result type to be the same as the input types. There are several approaches, obviously, but here is a sort of obvious one (read the comments here, they are important):


(defun list-func-compose (f2 f1)
   (lexical-let ((f1 f1)
                 (f2 f2))
    (lambda (arg) ; lambda need take only a single arg, as f1 must
      (let* ((r1 (funcall f1 arg)) 
        ; r1 is a list, because it is the result of f1, a monadic function.
        ; f2 accepts regular old values, though, and r1 could
        ; concievably have many values in it.
             (r2s (mapcar f2 r1)))
          ; now r2s contain the results of applying f2 to ALL
          ; the values in r1.  Each of these values in r2s is
          ; itself a list, because f2 always returns a list (it 
          ; is a monadic function itself)
             (reduce #'append r2s)
          ; Well, we want a list of things in the monad, not a
          ; list of lists, so we just append all the r2s together 
          ; (see footnote #1).
          ; Now we've got a list of lisp values, which  means
          ; that this lambda is a monadic function in its own
          ; right.  Success!!
          ))))

(n.b. If something about r2s type strikes you as odd, see footnote 1.)

Pause to consider what happened here. We apply f1 to the input, which produces a list (a monadic value). F2 takes values, not monadic values, so we just mapcar f2 over the values in the list. F2, like f1 returns a list, so now we have a list of lists, which we concatenate into a big list, which is now our output monadic value.

I hate when, in the course of a didactic development, something springs from nowhere with the proviso that "it will be useful later." This kind of thing is typical of physics and math texts, and I think its part of the reason they are so difficult to read. However, for the sake of future utility, we are going to factor out a piece of the above code. Consider the function list-bind which takes a monadic value and a monadic function and returns a new monadic value:


(defun list-bind (mon-val mon-fun) ; -> mon-val 
       (let ((results (mapcar mon-fun mon-val)))
          (reduce #'append results)))

We can rewrite list-func-compose like this, now:


(defun list-func-compose (f2 f1)
  (lexical-let ((f1 f1)
                (f2 f2))
    (lambda (value) 
       (let ((monadic-value (funcall f1 value)))
          (list-bind monadic-value f2)))))

Ok, what is so special a priori about list-bind (post priori, its one of the monad functions which any monad needs)? List-bind is, in a way, the fundamental operation relating monadic functions and monadic values in the list monad. List-func-compose might seem more directly useful, but it is kind of strange that the resulting function takes a non-monadic value and returns a monadic one.

List-func-compose relates monadic functions and other monadic functions, but it doesn't reveal much about how they are combined with values. List-bind describes that process, and it turns out this is more interesting.

Another way of thinking of it is that if list describes how to turn a value into a monadic value, list-bind relates a mondadic function to a function which both operates on and returns monadic values.

Ok, believe it or not, we've basically covered the entire sequence monad already. All that is left is to really get the idea and to understand how it relates to Haskell's do notation and the canonical monad operations. But it bears repeating - "do notation" isn't the same thing as monads. It is just syntactic sugar. Its might be best to understand monads before do notation, depending on your temperament.

Let's try things out, however.


(funcall (list-func-compose #'friends-of #'friends-of) :leo) 
(:lea
 :leo :sally :andrew :catherine :leo :jane :ted :leo :jane :andrew
 :harvey :sally :catherine :lea :leo :sally :andrew :catherine :leo
 :jane :leo :lea :leo :james :harvey :harvey :sally :ted :leo :lea
 :harvey :jane :andrew :lea :leo :james :sally :ted :james :andrew
 :catherine :ted :lea :leo :sally :jane :leo :ted :leo :lea :leo
 :jane :catherine :catherin :leo :lea :leo :james :harvey :harvey
 :sally :ted :lea :leo :sally :jane :leo :ted :leo :lea :leo :jane
 :catherine :catherin)

(We're probably really interested in the unique values of this list. We could use something called the set monad to get those, or we could just pass this result through unique.

Pretty anti-climactic, for sure. But we can do more interesting things:


(funcall 
  (list-func-compose 
     (mutual-friends-with :lea) #'friends-of)
  :leo)

This composition gives a list of the friends of Leo who are also friends with Lea. As indicated above, what we've done here is inserted a parameterized monadic function into the composition. This turns out to be useful. It also hints at the next step. What if we wanted to parameterize a monadic function based on some of the values "coming down the pipe" in the monad? How could we do that? In a regular function composition all those values are invisible. Is there way we can name them which preserves the utility of this approach?

Stepping Back

Monads in one sentence: a monad is set of operations which relate specific functions called monadic functions and specific values, which are either naked values (the input type to monadic functions) or monadic values, which is the output type of monadic functions.

In particular, the bind operation knows how to pull values out of monadic values, apply monadic functions to them, and collect all the resulting monadic values into one big monadic value. Using bind we can compose or otherwise manipulate monadic functions in a controlled way.

Everything else is window dressing.

Window Dressing

Let's talk about let*. We've been twisting up our brains into knots over monads, so let's let those knots untwist and return to this simple, clean, construct. In Lisp, variable bindings are explicitly introduced. You don't just declare a variable and go, you create a context for that variable with a let or let* statement. You probably know that if you only had lambda and defmacro you could define let like so:


(defmacro my-let (bindings &rest body)
  (funcall (lambda ,(mapcar #'car bindings)
             ,@body)
      ,@(mapcar #'cadr bindings)))

eg:


(my-let ((x 1) (y 2)) (+ x y))

expands to


(funcall (lambda (x y) (+ x y)) 1 2)

It is clear that x and y can't depend upon one another in this form:


(funcall (lambda (x y) (+ x y)) 1 (+ x 2))

Obviously won't work (why?). let* is the form which lets us chain together multiple variable bindings so that previous bindings are active during the expression form of subsequent bindings. Of course you can implement it as a series of nested lets, but its useful to write an implementation using only lambda.


(defun empty? (x) (not x)) ; sugar to test if a list is empty.
                           ; nil is the empty list, (not nil) -> t
(defmacro my-let* (bindings &rest body)
  (cond
    ((empty? bindings) `(progn ,@body))
    (t 
     `(funcall (lambda (,(car (car bindings)))
          (my-let* ,(cdr bindings) ,@body))
        ,(cadr (car bindings))))))

Don't get spooked by this recursive macro. All it means is that


(my-let* ((x 10)
          (y (+ x 11)))
   (+ x y))

expands to


(funcall 
      (lambda (x)
        (funcall (lambda (y) (progn (+ x y))) (+ x 11))
     10))

That is, each subsequent bind value expression is evaluated in the context of a function where the previous binding symbols are already bound.

Holy balls! This is almost function composition! The lambda containing our body (the progn form) is f1 and each containing lambda represents a composition onto this inner function. The only difference is that we're threading function application through the composition in such a way as to provide named values into more deeply nested contexts. Things are about to get serious!

Also, we are just throwing the word bind around like crazy! Does this use of the word bind have something to do with the list-bind function?

You bet it does! You know, ordinarily I could take or leave Lisp-2's. It seems kind of crufty to me to have to worry about a second namespace, to have to remember to type (funcall f-var a b c) or (funcall #'f a b c) but in this one case, its actually really useful that we have to write out funcall explicitly. Its useful because it reminds us something is going on there. What would happen if we replaced those funcalls in the above expansion of let* with some other function? Let's kick this can around a bit, and see if something falls out, shall we?


(defun regular-bind (v f)
  (funcall f v))

So in the let* expansion funcall is only ever taking functions with one argument, so the first thing we do is declare a new function which applies a single argument function to a single value. Why did we name it regular-bind? Well, think about the expression:


(regular-bind 10 (lambda (x) (+ x 1))); -> 11

In (lambda (x) (+ x 1)) x is unbound. That is what a lambda is, essentially, a chunk of code in which the arguments are unbound, waiting to be bound so the body can be evaluated. Regular-bind is just a function which binds a value (10, above) to a variable and executes the code. Note: funcall takes f and then v, but regular-bind takes v and then f. This might make more sense depending on how you read code ("bind v in f") or it might not. It is just convention. It is called regular-bind because it doesn't really do anything that funcall doesn't already do. Monads, though, are all about irregular bind operations.

Let's rewrite let* so that it uses bind instead of funcall:


(defmacro my-let* (bindings &rest body)
  (cond
    ((empty? bindings) `(progn ,@body))
    (t 
     `(regular-bind
        ,(cadr (car bindings))
        (lambda (,(car (car bindings)))
                      (my-let* ,(cdr bindings) ,@body))))))

Easy enough.

let* is how you thread together computations in the "identity monad". You may have heard someone say something like "regular lisp lives in the identity monad." This is what they mean. Normally, all bind does is associate a value with a symbol and go. The above let* expression now expands to:


(funcall 
      (lambda (x)
        (regular-bind  (+ x 11) (lambda (y) (progn (+ x y)))))
     10)

You should be chomping at the bit now, because we've basically invented do notation. The question you should be asking is "What happens when we replace bind with some other function?" Let's make a slightly newer macro to play with that idea.


(defmacro monadic-let*-inner (bind-symbol binders &rest body)
   (cond 
     ((empty? binders) `(progn ,@body))
     (t 
       (let ((symbol (car (car binders)))
             (bind-expression (cadr (car binders)))
             (leftover-bindings (cdr binders)))
      `(funcall ,bind-symbol 
          ,bind-expression
           (lambda (,symbol)
              (lexical-let ((,symbol ,symbol)) ; create a lexical 
                                               ; over ,symbol.  
                                               ; we want one
                                               ; for lots of monads.
               (monadic-let*-inner 
                   ,bind-symbol ,leftover-bindings ,@body))))))))

(defmacro monadic-let* (bind-f-expression binders &rest body)
  (let ((bind-symbol (gensym "temporary-bind-symbol-")))
    `(let ((,bind-symbol ,bind-f-expression))
          (monadic-let*-inner ,bind-symbol ,binders ,@body))))

This new form takes an expression which evaluates to a bind function, a set of let-like binders, and a list of body forms and then it just builds the same code as a let* except that it uses the specified bind operation rather than a mere funcall. Let* sequences computations. Monadic-let* sequences operations through a monad, the behavior of which is specified in bind.

Let's try this crazy thing out:


(monadic-let* 
       #'list-bind 
       ((x '(1 2 3)) 
        (y (list (+ x 1) (- x 1))))
     (list y)) ; -> (2 0 3 1 4 2)

Congratulations, friends, we are now living in the list monad.

Let's think about what this is doing one more time. We have a series of expressions (the right hand portion of each binding form). The monadic bind operation assumes each expression is a monadic value. In our case, these values are lists of lisp data. Rather than bind the result of this expression to the symbol on its left directly, our bind specifies that we should bind the symbol to each value inside the monad in turn, evaluate the subsequent binding expressions in the same way, evaluate the body, which must be a monadic value, collect each of those values, and then, finally, combine them back into a monadic value again before returning the result.

That is really complicated

Why would anyone do this?

The reasons for doing something like this are as varied as the kinds of monads that are out there. In Haskell, monads are a way of writing imperative style code in a pure fashion, but even in non-static, non-pure languages, monads can pull some neat tricks. The sequence monad, combined with monadic-let* is essentially a list comprehension. Suppose we want to collect all the combinations of two numbers less than 100 whose sum is less than 10.


(monadic-let*
 #'list-bind 
 ((x (range 1 101))
  (y (range 1 101)))
  (if (< (+ x y)  10) (list (vector x y)) nil))

;-> ((1 1) (1 2) (1 3) (1 4) (1 5) (1 6) (1 7) (1 8) 
       (2 1) (2 2) (2 3) (2 4) ...)

Here we simply return the empty list when we don't want to put anything into the monad because appending the empty list onto something does not change it. Other applications in an impoverished language like emacs is to use the continuation monad to fake co-routines or to use a stream monad to make dealing with lazy lists easier. We'll revisit this in another post.

Notes about the monads.el library

(note: I've made some changes to the `monads.el` library so that there are monad sequencing forms that cover a large range of possible intents. I've also renamed some of the forms, which I've tried to reflect here. If you can't get some code to run, look at `monads.el`. Each of the forms is documented.)

It turns out its handy in the context of monadic operations to have bind and return (and some other things) dynamically defined, so in the monads.el library, monadic-let* is slightly different. In that library, monads are defined as hash tables containing :m-bind and :m-return keys which associate with the appropriate functions. Eg:


(defvar monad-seq 
  (tbl! 
   :m-zero (list)
   :m-return (lambda (x) (list x))
   :m-bind (lambda (v f) (apply #'append (mapcar f v))))
 "The list/sequence monad.  
  Combine computations over multiple possibilities.")

Note here that tbl! is is just sugar for make-hash-table. The nearest equivalent to what we've called monadic-let* is mlet which takes as its first argument a monad represented as a hash table. In addition to the bind-chaining described above, it introduces a dynamic context wherein the functions m-bind and m-return are defined for that monad. Because we're in emacs, and everything just sits in one giant rotting pool of symbols, we prefix the monadic functions with m- to avoid future name collisions.


(mlet
 monad-seq
 ((x (range 1 101))
  (y (range 1 101)))
 (if (< (+ x y) 10) (m-return (list x y)) nil))

Note that we can use m-return inside mlet-like forms, because they define them automatically.

Monads.el defines several common monads in addition to the sequence monad. These include the state monad, the continuation monad, the set monad (parameterized on an equality predicate), an Error monad, and a Maybe monad. Monad-parse.el defines a monadic parser combinator library which is really useful (to me, anyway).

Sujar

The monad library can make use of my implementation of Clojure-style destructuring bind too. One can write the above expression as


(domonad monad-seq 
 [x (range 1 101)
  y (range 1 101)]
 (if (< (+ x y) 10) (m-return (list x y)) nil))

Besides the superficial change of using a vector for the binding expressions, you can use arbitrary nested binding forms inside. If you are familiar with clojure, it works basically like that, except that tables are destructured with [:: ] instead of { } and you can use table-destructuring on hash tables and alists.

Conclusions

For me, monads didn't hit home until I walked through the process of creating a new monad from scratch based on my own ideas. This is described in weighted-graph-monad.el, but in order to move forward in our discussion of Kanren, the logic language, we'll need to develop a stream monad, which facilitates work with lazy lists. That will be the next example.

Footnote 1: Here is a bit of a confusing thing. The monadic values of the list monad are lists of lisp data types. So a list of lists is, in fact, a monadic value, which means that r2s above could be considered, itself, to be a monadic value. If this didn't occur to you, just skip the rest of this note. I bring it up only because if it has occured to you, it might be somewhat confusing. You might ask: why don't we just return r2s instead of (reduce #'append r2s)? This kind of of conceptual confusion is related to the fact that Lisp is not statically typed (or is statically typed but you are restricted to a single type of which the various "types" of values constitute classes).

In a statically typed language the sequence monad would be parameterized on the type of its contents, which we'd specify where we were using it. So we'd have a type like SeqM Int (read that as "the sequence of ints monad") which would tell use that our monadic values were lists of integers only, and consequently r2s above would be manifestly not a monadic value, and it would be more obvious that we needed to append its contents together before recapturing a monadic value. In a dynamic language this isn't as obvious, but its still conceptually necessary. The upshot is that the fact that r2s is a monadic value is a coincidence, the essence of the list monad is still to combine the results of monadic functions, rather than to merely collect them, which is what returning r2s itself would represent. If you did read this despite my warning, you're probably really confused. Its ok. This stuff is confusing at first.)

Footnote 2: This is a long, diversionary footnote. Probably its best to finish the rest of the document before reading.

For some reason I find it useful/pleasurable/amusing to consider the question of monads in languages without scope at all. Namely, stack languages like Factor or Joy. Not only are these languages without scope, by default, variables are not even named. Values are merely pushed onto and pulled off of a stack which is passed implicitly between "words," the analog of functions:


(require 'with-stack)
(||| 4 4 + 3 -) ; -> 5

Here we are using a stack language interpreter which lives inside emacs lisp. You can get "with-stack.el" from my github.

Without a means of binding variables, "lambdas" become merely "quotations," simple lists of literals and words which can be executed by words like call.


(||| 4 '(4 +) call '(3 -) call) ; -> 5

In the "emacs stack language" quotation serves directly as the quote operator, and quotations are represented as lists. Executing a quotation is the same looping over it, executing each word as it is encountered, or pushing atoms onto the stack.

The nakedness of these quotations encourages languages to use them as blocks in control structures:


(||| 1.0 1>random* .5 > '("true" print) '("false" print) if)

The above will print "true" 50% of the time and "false" 50% of the time. I don't want to get bogged down with a full with-stack tutorial, but "1.0 1>random*" means "push 1.0 onto the stack and call the emacs lisp function random* with 1 argument from the stack, pushing the result". The word if takes a boolean and two quotations, executing the first when the bool is true and the second when it is false.

Ok, so quotations are lambdas. What are monadic quotations of the list monad? These must be quotations which take a value off the stack and return a list of values. The quotation version of return for the list monad would be:


(||| word: list-return 1>list end:)

That is, take a value off the stack and return a list with that value in it.

What about bind?


(require 'stack-words)
(||| word: list-bind ;( mv f (v ;; mv) ;; mv )
     map '(append) reduce end:)

Characteristically, the word version is quite terse. Interestingly, we hardly need to have an analog of do notation, because variables are not named and application is merely juxtaposition:


(||| word: bi>list ;( item qtn1 qtn2 ;; ( res1 res2 ) )
     bi 2>list end:)
(||| '(1 2 3) 
     '( '(1 +) '(1 -) bi>list )
     list-bind
     '( '(3 +) '(3 -) bi>list )
     list-bind) ;-> (5 -1 3 -3 6 0 4 -2 7 1 5 -1)

(The word bi>list takes an item and two quotations, applies the quotations each to the item and collects the results into a list of two elements. It assumes the quotations take one item off and push one onto the stack.)

Wherever we want to use monadic behavior, we simply replace call with list-bind. We can write a word to make this more pleasant:


(||| word: fold-bind-into ; ( qtnseq bind-qtn ;; qtnseq )
      '( curry ) curry map 1>flatten-once end:)
(||| word: monadically ; ( init-val qtnseq bind-qtn ;; result )
       fold-bind-into call end:)

(||| '(1 2 3)
       {{ '( '(1 +) '(1 -) bi>list )
          '( '(3 +) '(3 -) bi>list ) }}
     '(list-bind) monadically )

Where {{ is a parsing word which makes a list of what is on the stack between {{ and }}. We could have used quote to make the list of quotations, but we'd be getting a lot of quote marks on the screen. All this word does is fold the contents of a binding quotation (here a simple call to list-bind) into the sequence of quotations we want to operate monadically. Then we simply call the resulting quotation.

Assuming some comfort with the idioms of concatenative languages, the result is an incredibly simple demonstration of the essence of monadic operation. It strikes me that it is often the lowest-level words which are the hardest to read and write in concatenative languages, while high level code has an almost comic simplicity. I wonder what this means?

The Fetishist

2011-03-21T09:14:00.000-07:00

Slow mottled gray skies, the empty plains
somewhere in the blown out corridor from
Houston to Galveston. Highway and plane
noise, far enough for privacy but frisson-
near enough for wanderers to run, run
the risk of observation, forced sight:
so much more than the dead camera, glum
in its facile adsorption of light.
An old abandoned pool languishing right
behind an encroached upon foundation,
obscenely, a chimney still stands, a blight
within a blight within a blight within station-
ary air. He mugs against the gray sky
and falls into shit for the camera's eye.

How to use a codewalking macro to implement a lexically scoped delay in Emacs Lisp

2010-08-21T09:07:00.000-07:00

Lazyness is all the rage in these days of Haskell and Clojure, and it comes in many forms. Haskell is lazy by default, clojure supports laziness extensively, but it is still voluntary. Some scheme implimentations provide promises, which are delayed computations, and almost every high level programming language provides the basic building block of laziness via closures and anonymous functions.

We might, for instance, implement laziness in Scheme with a macro which transforms:

(delay expr1 ... exprN)

(lambda () expr1 ... exprN)

and then force is simply implemented as a function call:

(define (force thunk) (thunk))

Something which I think is a key insight here is that lambda is intelligent quotation. I'm not a programming language theorist, so I don't know if this constitutes a particularly novel insight, but to me it was a crucial step towards understanding the semantics underlying most programming languages. What does "lambda is intelligent quotation" mean, though? Well, we can imagine writing a very primitive delay macro thusly (in some kind of lisp):

(defmacro (delay . args) `(quote (begin ,@args)))

and then force is just eval:

(define force eval)

While this certainly "gets the job done" for expressions containing only atoms, it doesn't work on any expression containing variables. Depending on how your Lisp works, and when you call force, you can get anything from a straight up error to a mysterious result. If you use a lambda instead, however, you tell your language "quote this expression, but make sure all the symbols in the expression refer to the values described by the lexical context."

So here is a question: if we want to implement delay and force in emacs lisp, how do we do it? An extremely naive guess would be just to use lambda:

(defmacro delay (&rest body) `(lambda () ,@body))

Force is still:

(defun force (thunk) (funcall thunk))

But this doesn't quite work as we expect.

(let ((thunk 
  (let ((x 10))
    (delay (+ x x)))))
      (force thunk))

This will produce an error - that x is undefined. This is because, vexingly, Emacs Lisp is an old Lisp and has dynamic scope. That means x in the lambda created by delay refers to whatever the outermost x binding is, which, by the time we've arrived at the force is just nothing.

"Fear not," I hear you say! "I've read that Emacs Lisp has lexical closures via the cl.el package. Why don't we just use those?"

The item in question is cl.el's lexical-let form. Lexical-let lets you do things like

(funcall (lexical-let ((x 10))
           (lambda () (+ x 101)))) ; -> 111

It uses some trickery which I frankly haven't gotten too deeply into to simulate a lexical closure so that lambda grabs the right variable in the body of a lexical-let. However, note that we have to enumerate the variables we'd like to close over. We could write a macro to the effect of delay-with which had a body and a list of variables to close over, but can we do better?

We can, in fact, do better with a codewalking macro. Most macros which take a "body" do something simple. A good example is emacs lisp's save-excursion, which basically just inserts code to save and restore the current editing state around an unmodified body.

A codewalking macro takes a set of lisp forms, walks over them, inspecting and transforming, and finally generates a perhaps radically transformed new set of lisp expressions. We can write a codewalking macro to implement delay. All it has to do is walk over the body of the code and collect all the symbols and functions that are lexically free in it, and then lexically close around these symbols. Then, as if by magic, delay becomes a "smart" quotation.

So if our body is something like (+ x y z), then our job is pretty easy: x, y, and z are obviously free variables in the expression, so our macro takes:

(delay (+ x y z))

(lexical-let ((x x)
              (y y)
              (z z))
  (lambda () (+ x y z)))

If we put this in context:

(setq thunk (let ((x 10) (y 11) (z 12))
              (delay (+ x y z))))
(force thunk) ; -> 33

Note that above the let expression forms a dynamic scope, but our delay macro calculates the free variables and lexically closes over them before the dynamic values are popped of the stack. Then, when thunk is called, everything works out all right.

A couple of objections ought to be appearing in your mind right now. One of them focuses on the fact that lisp expressions are not as simple as just function calls, and that, in particular, a variety of lisp expressions introduce variable bindings which influence nested expressions. Most obviously,

(setq thunk (let ((y 1001) 
                  ((x 10)))
            (delay (let ((x (+ x 100)))
                  (+ x y)))))
(force thunk)

involves some thinking about what values we should close over. Rather obviously we need to capture the lexical binding of y, but what about x. Within the body of the inner let expression, x will be dynamically bound, but the value it takes depends on the non-lexically bound outer x. If we traversed the code tree, just counting x occurences, we might miss the fact that let treats the symbol part of its binding expressions differently than the value parts. Not only that, but we have to consider the dynamic and lexical binding of function applications, which are treated separately in emacs lisp because it is a lisp-2. This problem is tractable, however, because emacs lisp has a small number of simple fundamental expression types. We can, therefore, hope to write a parser which traverses arbitrary lisp code, collecting information about which variables are locally bound or lexically free within an expression.

Here comes the second objection, however. It is true that lisp defines only a small number of fundamental special forms, but any arbitrary piece of lisp code may be peppered with a variety of user defined special forms created via macros. It may be within our capabilities to parse a lisp expression containing only fundamental forms, but can we reasonably expect ourselves to parse the binding information contained in the clauses of a loop expression, much less any unique, ad-hoc, user created macro? The good news is that we don't have to - we can call macroexpand-all on the body before parsing it, guaranteeing that we will have only naked lisp to parse.

Now that those objections are out of the way, we can begin to tackle the problem formally. We'd like to write a function which reads a piece of lisp code and and records the number of times a symbol is used without a binding, either as a function or as a value. Once we have this list we can wrap up our expanded body in lexical-let and labels forms, to provide local definitions of functions and values which are lexically scoped.

The skeleton to collect the symbol usage information is, thus;

(defun* collect-usage-info (form &optional (global-info (alist>>))
                                 (local-info (alist>>)))
"(collect-usage-info FORM &optional GLOBAL-INFO LOCAL-INFO)

Collects information about the usage of variables and functions in the form FORM.
When called recursively, it may be appropriate to provide GLOBAL-INFO, an alist 
describing the collected information so far, and LOCAL-INFO, an alist describing
the binding information of variables locally.  

GLOBAL-INFO is returned.  It is an alist of the form;
  (list 
    (<symbol> (<n-bound-symbol-usages>
               <n-bound-function-usages>
               <n-unbound-symbol-usages>
               <n-unbound-symbol-usages>))
    ...)

LOCAL-INFO is recursively defined, but is of the form
  (list 
    (<symbol> (<bound-as-symbol>
               <bound-as-function>))
    ...)

  Where bound-as-(function/symbol) are either t or nil."
  (cond
   ((symbolp form)
    (cond ((eq 't form) global-info)
          ((eq 'nil form) global-info)
          (t
           (dlet [[bound-s bound-f] (symbol-binding-info form local-info)
                  [s-count f-count s-unbound-count f-unbound-count] (symbol-bind-counts form global-info)]
             (alist>> global-info form (list 
                                        (if bound-s (+ 1 s-count) s-count)
                                        f-count
                                        (if (not bound-s) (+ 1 s-unbound-count) s-unbound-count)
                                        f-unbound-count))))))
   ((listp form)
    (cond 
     ((quotep form)
      global-info)
     ((prog-like form)
      (collect-usage-info-prog-like form global-info local-info))
     ((letp form)
      (collect-usage-info-let form global-info local-info))
     ((let*p form)
      (collect-usage-info-let* form global-info local-info))
     ((function-formp form)
      (collect-usage-info-function form global-info local-info))
     ((ifp form)
      (collect-usage-info-if form global-info local-info))
     ((condp form)
      (collect-usage-info-cond form global-info local-info))
     ((defunp form)
      (collect-usage-info-defun form global-info local-info))
     ((setqp form)
      (collect-usage-info-setq form global-info local-info))
     (t ; function application
      (collect-usage-info-prog-like (cdr form)
                                    (collect-usage-info-function `(function ,(car form)) global-info local-info)
                                    local-info))))))

Anyone familiar with SICP will recognize this pattern. We have a case statement which determines what sort of expression we are looking at, and then dispatches handling of that expression type to a specific handler, which may call collect-usage-info recursively. The base cases are symbols and atoms. Atoms are ignored, whereas symbols, when encountered, are counted appropriately depending on the information in local-info. You can see all the details in the source code, available at my git-hub, but to give you an idea of how this works, lets look at the case of the let expression.

We detect a let-expression with the letp predicate;

(defun letp (form) 
   (and (non-empty-listp form)
        (eq (car form) 'let)))

(all these predicate functions are defined in macro-utils.el.)

Handling a let form is relatively simple. We will read each binding clause, count the variable usage in the expression providing the value thereof, and then collect all the symbols bound in the expression. We then call collect-usage-info-prog-like on the body, providing an augmented local-info which indicates that the variables described in the let expression now have bindings. collect-usage-info-prog-like simply folds collect-usage-info over the forms in the body.

This idea is repeated for all forms in the basic emacs-lisp language. Using this function we can finally define our delay macro thusly:

(defmacro* delay (&body body)
  (let* ((expanded (macroexpand-all `(progn ,@body)))
         (info (collect-usage-info expanded))
         (unbound-symbols (get-unbound-symbols-list info))
         (unbound-functions (get-unbound-function-symbols-list info))
         (temporary-function-names 
           (loop for f in unbound-functions collect (gensym (format "%s-old-" f)))))
           `(lexical-let ,(loop for s in unbound-symbols collect `(,s ,s))
                          (labels ,(loop for old-f in temporary-function-names 
                                          and f in unbound-functions collect 
                                          (let ((arglist (gensym "arglist")))
                                            `(,old-f (&rest ,arglist) (apply #',f ,arglist))))
                                   (labels ,(loop for f in unbound-functions 
                                                   and old-f in temporary-function-names collect 
                                                   (let ((arglist (gensym "arglist")))
                                                     `(,f (&rest ,arglist) (apply #',old-f ,arglist))))
                                            (lambda () ,expanded))))))

As promised, there isn't much by way of magic here. We expand the body as a progn-like form, collect the information about variable binding from it, and then create the appropriate lexical closures. The only wrinkle is in the precise use of the labels form. Functions introduced in a labels form are allowed to be mutually and self recursive, so we can't just do the equivalent of:

(let ((x 10))
   (lexica-let ((x x))
       (+ x x)))

which is,

(flet ((f (q) (+ q 1)))
  (labels ((f (&rest arglist) (apply #'f arglist)))
      (f 1)))

Because the labels form above introduces a recursive function f which calls itself indefinitately. There are several possible solutions to the problem. The simplest, but perhaps not the best, is to use two independent labels forms, the first of which creates new bindings for the functions, and the second of which creates the lexical bindings with the correct names. Perhaps the ultimate solution is to pick new names, and walk the code, replacing each function application with the new name. This is probably overkill for this example.

So we've finally arrived! Now we can delay and force to our heart's content, and emacs will do its best to pretend it is a lexically scoped language:

(let ((x 10))
   (setq thunk (delay (+ x 1))))
(force thunk) ;-> 11 
x ;-> undefined variable

As an exercise to the reader, you can try to implement two functions which are provided in the source code, but not reproduced here: lexical-lambda and lexical-defun. They have the following behaviors.

(funcall 
  (let ((x 10))
    (lexical-lambda (y) (+ y x)))
  100) ; -> 110


(let ((x 10))
  (lexical-defun f (y) (+ x y)))

(f 10) ;-> 20

The Fork As Blasphemer

2010-06-29T08:35:00.001-07:00

Few artifacts have insinuated themselves so comfortably into our lives as the modern fork, which is neither given with a superstitious penny taped to its tines¹ nor is it ever mightier than the sword. This comfortable arrangement is reflected in the difficulty with which the amateur researcher finds information about the utensil. So far as I am able to ascertain, UNC has only two books on the subject of the history of flatware and one of which is a children's book. That book, "From Hand to Mouth," devotes one casually written chapter to the fork - a volume of text amounting to no more than 15 pages with large type, simple sentences and many illustrations.

If, in frustration, one consults the internet², they will find a similar paucity of information. The wikipedia article on the fork appears to be lifted in its entirety from an article written for the Society for Creative Anachronism about the proper use of the fork while pretending to be a person from Europe's past. The basic format and flow of this article strongly suggests that its one source was "From Hand to Mouth," although a second 1927 book is cited which was unavailable to me.

The fork's history, like that of many human conveniences, is lost to antiquity. Its steely fingers merely rise up from the mists of time sometime before the 11th century, when it was introduced in Europe for the purposes of eating. Before then, forks were used to serve and mince meat and to heave hay to horses, but at the table we still ate with our hands. In what may be one of the earliest uses of the fork, some mice asphyxiate themselves on forked twigs³, running, I suppose, from whatever agonies mouse life presents.

How Europeans began to use the fork for more than feeding and slicing pigs is better understood. The story goes that in the 11th Century Domenico Selvo, the Doge of Venice, acquired somehow a Byzantine wife. In the East the fork was apparently in common use at tables and she brought with her to that watery city a set of flatware for her personal use. This, surprisingly, engendered the scorn of the locals, who saw it as excessively delicate⁴. Apparently her table manners were so noteworthy that when she died shortly after arriving, the passing was blamed on her use of the fork, which, the suggestion goes, caused her to waste away. But physical deterioration was the least of the problems facing people who chose to eat without dirtying their hands.

"God in his wisdom has provided man with natural forks - his fingers. Therefore it is an insult to Him to substitute artificial metallic forks for them when eating." Giblin attributes this quotation to mysterious "church leaders" and provides only the most tenuous of context. The idea that such a statement carried even an iota of the Magisterium of the Roman Catholic Church is not so much doubtful as it is ridiculous, yet, this tiny quotation may be one of the most interesting things about the fork, as it implies that it was resisted for a moment on account of its violation of a divinely decreed natural order.

This is not the only instance of this kind of reasoning in response to new technology. In 1752 or thereabouts Benjamin Franklin succeeded in demonstrating⁵ the sameness of electricity and the substance of lightning. Previous to this discovery, the caprices of the heavens had been associated for some time (perhaps all time) with the caprices of Heaven - and upon the introduction of Franklin's lightning rods, which sprouted, like fungus after a rain, on the roofs of Churches and Gunpowder Warehouses all across The United States, objections were raised to their use on account of the way they seemed to divert Divine Punishment. "An Entertainment for Angels," a very entertaining little book (even for us corporeals) about electricity in the Enlightenment, points out that the Papacy supported the use of rods to protect churches, but local leaders frequently objected on religious grounds⁶.

What is interesting about both the controversy over the lightning rod and the fork is that neither are ongoing. The lightning rod and the fork have integrated themselves into our pictures of the human world. Franklin said of the objections to the rod "Surely the Thunder of Heaven is no more supernatural than the Rain, Hail or Sunshine of Heaven, against the inconvenience of which we guard by Roofs and Shades without Scruple." Like rain, hail and sunshine, both lightning and messy eating have become simple inconveniences to avoid rather than indications of a Divine Will.

These two worlds humans live in, one of unavoidable divine consequences and another of mutable human problems, still coexist today of course. A person hardly passes without relatives declaring that it was, in the end, God's Will that he be taken - and yet before the death frequently every measure of human ingenuity is applied to the frustration of that Will. That the theology of free will is intricate and sensible is in many ways besides the point, since it hardly enters into the thinking of the average person. To be caught in a rain storm might have led to a protracted death by consumption in the time of Jane Austin, but now days a common cold isn't worth a moment's thought or prayer. Because we have wrested from the common cold its fatal power we no longer think of it as representing anything but the mundane.

Can we imagine a world in which all human inconveniences have been dispensed with by science? Where voracious nano-machines destroy viruses and bacteria with an efficiency to which evolution is simply unable to adapt, where death is forstalled indefinitely by careful genetic manipulation? In such a world, where death will be reduced to gnawing at the edge of the human world in the realm of freak accidents, we will no doubt continue to blame our mountain climbing accidents, our spontaneous human combustions and other unavoidable inconveniences on some external agency.

In any case, the fork is stuck comfortably in the heart of human destiny.

Footnotes:

¹ Apparently it is the tradition in some cultures to attach a penny to the blade of a knife given as a gift. The penny is immediately returned to the giver as "payment" for the knife so as to mitigate the negative consequences of giving a knife, which supposedly heralds the end of the friendship.

² Who looks on the internet after checking the library?

³ This may be a lie.

⁴ At least it was surprising to me initially. I then imagined what my reaction would be to a fellow diner taking from her hand bag a sterilized assortment of surgical tools and, with excessive precision, quartering and requartering her food (perhaps with the aid of a protractor or a compass) and then carefully placing it into her mouth one morsel at a time. To a Medieval whose every meal had been taken with his hands to no noticeable harm, the Princess' caution would probably have seemed similarly strange.

⁵ "An Entertainment for Angels" by Patricia Fara tells that the first experiment was actually conducted by Frenchmen, with a retired soldier and a priest being the first humans to draw electricity from the sky. The famous kite scene was played out slightly later by Franklin, and so the image of the scientist replaced that of the soldier and the priest - a fairly evocative circumstance.

⁶ The debate eventually solidified somewhat into an argument about whether rods should be pointed or rounded. For political and scientific reasons, the main proponents of using rounded rods were Jean Nollet of France and Benjamin Wilson of Great Britain. For religious and practical reasons, it was thought that using rounded rods was preferable because they did not attract lightning as well, the idea being to avoid the collateral damage of lightning strikes and specifically attracting the wrath of God. Pointed rods eventually won out, but apparently the debate still churns in the form of lightning rod dissipators - whose stated purpose is to reduce the likelihood of lightning strikes and whose efficacy is still debated.

Farmville and the Face of Transdehumanism

2010-04-12T05:58:00.000-07:00

At this year's D.I.C.E. conference (Design, Innovate, Communicate, Entertain) Carnegie Melon's Jesse Schell gave a presentation which, even as it diverged into parody towards its energetic end, presented us with an incredibly depressing view of the future. In 1984, George Orwell writes "If you want a picture of the future, imagine a boot stamping on a human face - forever." Happily, this industrial image, from an industrial era, has not come to pass, but I don't think it is because of any underestimation of the benign nature of humankind on Orwell's part. On the contrary, our negative impulses have only found more efficient means of expression, so that the idea of exploitation by a monolithic force seems quaint in a world of constant advertising, 20 page credit card contracts, and a political system so based on subverting the average citizen's rational decision making that the fate of the nation depends on who more skillfully manipulates the psychological vapors of the electorate. It is no exaggeration to say that we have entire industries devoted to rational subversion of the human will. If anyone can provide a better definition for contemporary advertising and political consulting businesses, I'd love to hear it.

Almost every aspect of post-industrial collective action is rationalized or in the process of being rationalized. Research is conducted on the best way to squeeze every ounce of efficiency out of workers for the lowest possible salaries. Google, with its vast infrastructure, is leading the way in making sure that every ad you see is targeted directly to your preferences. Modernity is swiftly devoting itself to the problem of identifying what it is you want, and offering it to you just as you want it the most. In other words, the world is learning ever more clever ways to selfishly manipulate your psychology.

Jesse Schell's talk extrapolates the primitive kind of manipulations you see in Facebook games like Farmville and Mafia Wars. He openly discusses the ways in which these games exploit the psychology of adults and children, suggesting that such exploitation is the future of game design. He imagines a world in which everything, from your reading habits, to your sleeping habits, is monitored at all times by benevolent corporations, who use that data to tug constantly on the strings of your motivation, to direct you to buy, to offer you your desires. He imagines a government which uses a vast sensor network to gently encourage prosocial behavior.

In one example, he hypothesizes that your toothbrush will be equipped with a sensor that monitors the amount of time spent brushing your teeth. Although he flirts with the possible benefits to dental hygiene, he eventually comes right out and says that the real value will come from the creation of a brushing "game" that will help drive sales for toothpaste companies. With each instance, he dangles a possible good in front of the audience, only to say, actually, there is a profit stream to be made here. If we get a little benefit out of it, all the better!

His vision of perpetual surveillance by a myriad of omnipresent sensing devices, all as a means of shaping human behavior is similar to the vision of the transhumanists, where individuals extend their awareness and capabilities with the same kind of technology in the service of their will. The transhumanist imagines that he will be at the center of a phalanx of personal information collectors, the product of which he can analyze with ever increasing computational resources made available by ever-cheapening, general purpose computer hardware. But Schell's vision is the perverse opposite of transhumanism: technology becomes the means by which external forces exert a super-human control over the individual, not with the Orwell's boot or his comparatively clunky "Ministry of Information," but with rationally constructed, constantly adjusted psychological lures. Technology does not become ever more cheap and multipurpose, used by its owner for its owner's purpose. It becomes fractured, each device a sensor only nominally controlled by the "owner", its collected data analyzed by the distributor, not the user. This philosophical universe which tolerates such a conception of the future is transdehumanism. In it, a distributed, technological storm turns the average person into a constantly manipulated purchaser of both real and psychological goods.

I find the idea very distasteful, and I believe that the vast majority of humans, if they were to lay it up against whatever measuring stick they use to tally value, would agree. Schell's talk should serve only as a roadmap of where not to go.

The last ten years have seen an incredible proliferation of technology into the hands of people ordinarily deprived of such powerful means of cultural expression. It was a common assumption that technology would inevitably cause all ships to rise, enhancing the expression of the individual will which is so crucial to the human experience. Schell's imaginary future shows a different path, one which we should avoid. While continued agitation for open computing platforms and software is a good start, we should reconfigure our society to prevent the manipulation facilitated by our ever growing understanding of human psychology. Right now if an advertiser invents a new mechanism of capturing your attention, or discovers via focus group testing a way of increasing the impulse buy rate of candy at a grocery store, we at best muster a vague sense of unease. But such advancements are an assault on our ability to exercise our wills and and we should react accordingly. The alternative is to imagine a future where a cloud of media suffocates a human face, forever.

Clojure-style destructuring binding for Emacs Lisp

2009-05-30T08:55:00.000-07:00

I like to write Lisp, but like a lot of people it took me a long time to get used to the verbosity of the language and the number of parenthesis. In a lot of ways, complaining about parenthesis and the fundamentally nested style of lisp is praising with faint damnation, since it is exactly this property which encourages the programmer to write short, concise functions and the "grow the solution" rather than attack it top down¹. Also, like a lot of people, I hate boiler plate code. One area in which Clojure really improves on traditional lisps is its support for destructuring bind. With this construct, the decomposition of data structures is represented concisely in the binding form of a let or lambda list, so that the body of the function can focus exclusively on logic, rather than decomposition. Thus, a simple implementation of map might look like:


(define (map f lst)
  (if (empty? lst) '())
      (cons (f (car lst)) (map f (cdr lst)))))

While a Clojure implementation would look like


(defn map [f [head & tail :as lst]]
  (if (empty? lst) '()
      (cons (f head) (map f tail)))

Which is shorter and clearer and has fewer parenthesis. The real power of destructuring bind becomes obvious when you realize you can use it with anonymous functions and the reduce/fold operation to decompose complex accumulators in a concise manner, as in this code:


(defn file-name-parser [next-character 
      [total-ac 
       element-ac]]
  (cond 
   (nil? (last element-ac)) ;; first call
   (do
  (list 
   total-ac ;; should be nil anyway
   (conj element-ac next-character)))

   (same-class? next-character (last element-ac))
   (do 
  (list
   total-ac
   (conj element-ac next-character)))

   (not-same-class? next-character (last element-ac))
   (do 
  (list
   (conj total-ac element-ac)
   [next-character]))))

(defn parse-file-name [name]
  (let 
   [[total rem] (foldl
         file-name-parser (list [] []) (seq name))]
 (map (comp parse-number-or-leave #(apply str %)) (conj total rem))))

I like this aspect of clojure a lot. However, like most people, the lisp I write the most code in is emacs lisp. So I wrote a destructuring bind and defn form for emacs lisp which mimics clojure's style. With it you can write in emacs lisp:

(defn demo [a b [c d] & rest] (list a b c d rest))
(demo 1 2 '( 3 4 ) 5 6 7) -> (1 2 3 4 (5 6 7))

It supports destructuring on hash-tables also, but since emacs lisp does not have reader macros or any other way to directly represent them, you need to indicate a hash table with the special form ::.

(defn demo [a b [c [:: d :x]]] (list a b c d)))
(demo 1 2 (list 3 (tbl! :x 33))) -> (1 2 3 33)

(tbl! is a short hand for creating a hash table, it is also included with the code). The functions are lexically scoped but otherwise can be used as emacs functions, including using the (interactive) form. The code also includes a clojure-style destructuring let form called dlet. ie:

(dlet [x 10 [a b] (list 1 2)] (+ a b x)) -> 13

Both also support the :as name feature of clojure's binding forms.

(dlet [ [a b :as lst] (list 1 2) ] (list a b lst)) -> (1 2 (1 2))

It doesn't yet support default values (even of nil) for sequences or hash tables and it probably has a few bugs, but you call pull it from github with:

git://github.com/VincentToups/emacs-utils.git

Anyway, it is neat and hopefully useful and if anyone wants to see what a language extension in emacs lisp might look like, or just get a feel for the power of Lisp, then the code might be interesting. (Edit: I added a fn form to the library as well as made a few bug-fixes. Unfortunately because of limitations within Emacs Lisp, you cannot quite use macros that expand into lambdas exactly like you would use lambdas, but fn should be ok everywhere that you would pass a function around. The only place it doesn't work, I think, is in the call-position of an s-expression encountered by the reader.) ¹ Also true of Forth and Factor.

On "Buy Local"

2009-05-19T07:40:00.001-07:00

(crosspost from the comments to Distributist Review.) I think the issues around globalism are complex. For instance, when you say "Buy local," what do you mean? Do you mean culturally local, geographically local, or "energetically" local (as in, it does not require much expenditure of energy to move the good from the provider to the consumer). I am pretty sure a definition of local based on cultural similarity is exactly what people mean when they say Buy American is a chauvinistic movement - its subtext (albeit barely sub) is "Americans deserve to have jobs more than people in another society". The idea that one person deserves a living and another does not depending on whether they are of a particular culture is obviously amoral. I think most moralists agree that the culture one incidentally belongs to ought not to prevent you from working and living. If this is the case, then saying it is geographic locality which matters (and cultural locality is just a coincidence due to the fact that people with similar culture tend to live near one another) then we are in the position of making an even more ridiculous moral statement: that people deserve to work based on whether they live near you or not. This is even more coincidental than the culture to which one belongs. By local we must therefore mean energetically local - that is, that it does not require very much energy to transport the good from the producer to the consumer. This definition, however, must depend on the state of technology surrounding the economic transaction. If we invented teleporters powered by solar energy, for instance, then everyone would be local to you. Intellectual trade has already reached this point - no one talks of "supporting local bloggers" because the blog is an essentially free to move object. One consequence of accepting this view is that if technological changes, such as the invention of fossil fuel powered vehicles and ships, occur, then the notion of energetically local will necessarily change. This is quite arguably the cause of the phenomenon of globalization in the last two centuries. It seems to me that if someone in Bangalore makes something which is expensive or impossible to make here in North Carolina and we make something else that they want (even if that thing is just capital) then it makes more sense, both morally and practically, to buy from the people in Bangalore. They, after all, need to make a living just like anyone else, and their local circumstances might not allow for them to diversify their production sufficiently to support a good quality of life if they were restricted to local trade. It seems like what you really object to is the people in North Carolina (for instance) "producing" nothing but capital. But we both agree that this is (in the long term) impossible. In any case, it is a separate problem if North Carolinians are not actually producing valuable commodities. One not really addressable by merely buying local (except that doing so artificially constrains us). Shouldn't we be more concerned about making sure our investments are sound in the long term and that our transactions are moral and forget about geography or culture altogether when making economic decisions?

Morse Code in Factor

2009-04-30T08:54:00.000-07:00

I am getting the hang of this. This is a string>morse code and morse code>string converter as per this programming praxis problem. My implementation ignores extra whitespace in the morse code stream.

USING: ascii lists sequences regexp ;

: ch>morse ch>upper ( char -- morse-str )
         { { CHAR: 0 [ "— — — — —" ] }
           { CHAR: 1 [ "• — — — —" ] }
           { CHAR: 2 [ "• • — — —" ] }
           { CHAR: 3 [ "• • • — —" ] }
           { CHAR: 4 [ "• • • • —" ] }
           { CHAR: 5 [ "• • • • •" ] }
           { CHAR: 6 [ "— • • • •" ] }
           { CHAR: 7 [ "— — • • •" ] }
           { CHAR: 8 [ "— — — • •" ] }
           { CHAR: 9 [ "— — — — •" ] }
           { CHAR: A [ "• —" ] } 
           { CHAR: B [ "— • • •" ] }
           { CHAR: C [ "— • — •" ] } 
           { CHAR: D [ "— • •" ] } 
           { CHAR: E [ "• • •" ] }
           { CHAR: F [ "• • — •" ] }
           { CHAR: G [ "— — •" ] }
           { CHAR: H [ "• • • •" ] } 
           { CHAR: I [ "• •" ] } 
           { CHAR: J [ "• — — —" ] } 
           { CHAR: K [ "— • —" ] } 
           { CHAR: L [ "• — • •" ] } 
           { CHAR: M [ "— —" ] } 
           { CHAR: N [ "— •" ] } 
           { CHAR: O [ "— — —" ] } 
           { CHAR: P [ "• — — •" ] } 
           { CHAR: Q [ "— — • —" ] } 
           { CHAR: R [ "• — •" ] } 
           { CHAR: S [ "• • •" ] } 
           { CHAR: T [ "—" ] } 
           { CHAR: U [ "• • —" ] } 
           { CHAR: V [ "• • • —" ] } 
           { CHAR: W [ "• — —" ] } 
           { CHAR: X [ "— • • —" ] }  
           { CHAR: Y [ "— • — —" ] }  
           { CHAR: Z [ "— — • •" ] } [ drop " " ] } case ;

: morse>ch ( morse-substring -- char )
         { { "— — — — —" [ CHAR: 0 ] }
           { "• — — — —" [ CHAR: 1 ] }
           { "• • — — —" [ CHAR: 2 ] }
           { "• • • — —" [ CHAR: 3 ] }
           { "• • • • —" [ CHAR: 4 ] }
           { "• • • • •" [ CHAR: 5 ] }
           { "— • • • •" [ CHAR: 6 ] }
           { "— — • • •" [ CHAR: 7 ] }
           { "— — — • •" [ CHAR: 8 ] }
           { "— — — — •" [ CHAR: 9 ] }
           { "• —" [ CHAR: A ] } 
           { "— • • •" [ CHAR: B ] }
           { "— • — •" [ CHAR: C ] } 
           { "— • •" [ CHAR: D ] } 
           { "• • •" [ CHAR: E ] }
           { "• • — •" [ CHAR: F ] }
           { "— — •" [ CHAR: G ] }
           { "• • • •" [ CHAR: H ] } 
           { "• •" [ CHAR: I ] } 
           { "• — — —" [ CHAR: J ] } 
           { "— • —" [ CHAR: K ] } 
           { "• — • •" [ CHAR: L ] } 
           { "— —" [ CHAR: M ] } 
           { "— •" [ CHAR: N ] } 
           { "— — —" [ CHAR: O ] } 
           { "• — — •" [ CHAR: P ] } 
           { "— — • —" [ CHAR: Q ] } 
           { "• — •" [ CHAR: R ] } 
           { "• • •" [ CHAR: S ] } 
           { "—" [ CHAR: T ] } 
           { "• • —" [ CHAR: U ] } 
           { "• • • —" [ CHAR: V ] } 
           { "• — —" [ CHAR: W ] } 
           { "— • • —" [ CHAR: X ] }  
           { "— • — —" [ CHAR: Y ] }  
           { "— — • •" [ CHAR: Z ] }
           [ drop 32 ] } case ;


: string>morse ( string -- morse-string )
         sequence>cons { } [ ch>morse suffix ] foldl
         "  " join ;

: morse>string ( morse-string -- string )
         R/ [ ]{2,}/ re-split
         [ >string morse>ch ] map >string ;

The Python Tail Call Hullabu

2009-04-29T17:49:00.000-07:00

Guido Van Rossum has done it again, causing a great blogging uproar over his decision to keep tail call elimination out of Python. The argument boils down to Van Rossum feeling as though tail calls encourage a kind of non-obvious style of programming and make debugging more complicated anyway (you can read the whole thing here. Those few (none) of you who have followed this blog might guess, given my penchant for functional languages, that I am on the pro-tail-call-elimination group and, I suppose, I probably am¹. However, my position is perhaps more nuanced, at least enough that I thought it worth explicating. The problem might be cast into relief by pointing out we'd really like, as programmers of an abstract bent, to ignore the existence of the computer our code is running on entirely. Even the Turing machine, arguably the least abstract conception of computing, has an infinite amount of tape. The lambda calculus doesn't have any machine aspect at all - no memory, processors, none of that crap. In a completely abstract world, the difference between a tail call and a call in a non-tail position is immaterial - you have an infinite amount of stack (or whatever it is) to accumulate, and all that really matters is whether the computation terminates (and not even that, if you are working on streams or some other meaningfully infinite data structure). In real life, much to the chagrin of us abstract types, computers have a finite amount of call stack and all sorts of other limitations. But the elimination of tail calls lets us pretend, in certain cases and for certain, carefully crafted algorithms, that the limitation of the stack does not exist. There is a grace and elegance to this which is very attractive, which is why we like it. But it also is clunky and weird. Why, after all, should a tail call be different than a call in a non-tail position? In Scheme, nothing distinguishes a tail call syntactically or semantically (at least not without bursting the bubble of abstraction around the language). As far as the abstract nature of programming is concerned tail and non-tail calls are identical. So even though tail calls let us code in a way which seems abstract, they are really coding to an optimization. In other words, the most abstract of us are spending a lot of time thinking about a non-abstract question anyway. The tail call is a sort of a farce. It is this very reality which I think the non-abstract crowd claims is confusing, and when I really think about it, I can see the point. I'd still like it in Python, but I guess I might just have moved on to other languages. ¹ I'd rather have proper lambdas first.

Dorophone

Shadchen: A pattern Matching Library for Elisp

A pattern matching library for Emacs Lisp

How it Works

Extending Shadchen

Supported Patterns:

Conclusions

Literate, Racket-Styled Interpreter from Ch. 1 of Lisp in Small Pieces

Persistent Hash Tables for Elisp

Random Access Lists for Emacs

Examples:

Conclusion:

Better Monad Parse Updated!

How to Make Emacs' Scratch Buffer Persistent Across Sessions

A Quick Elisp Tutorial

Preliminaries

Saving the Contents of *scratch*

Loading the Contents of *scratch*

Hooking It All In

That is It!

Is Abstraction a Double Edged Sword?

For Instance

The Problem

Understanding the Haskell IO Monad.

By Building a Toy Model in Scheme

Enter Scheme

Bundling Up IO

Sketch

The IO Monad

Building IO Actions

"Do" Notation

A Simple Example

Conclusions

Better-monad-parse Now Available

Notes

Update to my Monadic Parser Combinator Elisp Library (+ examples/tutorial)

Building Up a Parser

Extra Features

Scheme Syntax is A Monad

Two Great Tastes that Taste Great Together

Better Monads

The Syntax Monad

But Will it Blend?

Conclusions

Monadic Turtle Graphics (Screencast Edition)

Apparently the video is still borked for many users. Anyone here have any advice on the best way to record screencasts on Ubuntu Natty? A trillion apologies and abasements for any inconvenience.

A Survey of Syntactic Extension Techniques in the Lisp Family of Languages (Part 3)

Extending Our Code Representation

Introducing New Syntax

Simple Tools Help Maintain Hygiene

Shortcomings of Syntax Rules

Syntax-case

Recapitulation

Further Reading

Back Matter

On Discovering Programming, Age 12

A Survey of Syntactic Extension Techniques in the Lisp Family of Languages (Part 2)

Business Time!

Macros & Quasiquotation

Issues with Naive Code-Rewriting Macros

Making a Mess

Namespaces, Packages, Hygiene

Conclusions

A Survey of Syntactic Extension Techniques in the Lisp Family of Languages (Part 1)

picoLisp

Code is Data

Variables, Scope, Eval, Quote and Lambda

Lexical Scope?

Conclusions of Part 1

Duckspeak Vs Smalltalk

Duckspeak Vs Smalltalk

The Decline of the Xerox PARC Philosophy at Apple Computers

The Xerox PARC Philosophy

HyperCard

Waiting for the Dynabook

Cross Post (also on The New Yorker) about Smalltalk

A Hyperturtle Monad Makes Pretty Pictures

In the Monads of Madness

Remember Turtle Graphics?

What about a Hyperturtle?

Saving the Contents of `scratch`

Loading the Contents of `scratch`