That may be, but my library is your programming language

In another instance of look-what-I-can-do-with-closures-and-late-binding, Benjamin Pollack offers a criticism of C# and Linq.

On the value of metaprogramming

Several weeks ago I wrote about a way to implement Smalltalk-style predicate function-to-SQL translation in Common Lisp, so I was amused to come across Dejavu for Python (via Jonathan Ellis), which implements the same technique by inspecting CPython bytecode.

It's amazing what kind of dumb hoops people will jump through when they don't have a system that permits real metaprogramming.

Closure-oriented metaprogramming via dynamically-scoped functions

Today I came across this post from the ll1 mailing list (almost 7 years old now, via Patrick Collison's blog) from Avi Bryant explaining how Smalltalk's message-based dispatch permits a type of metaprogramming with closures, as an alternative to macros.

Of course if you've read Pascal Costanza's Dynamically Scoped Functions as the Essence of AOP (and if you haven't, click the link and do it now; it's one of my favorite CS papers), you will realize that there is no need for message-based dispatch or any kind of object-oriented programming to do that. All we need are dynamically-scoped functions.

Here is how I approached the problem:

(defpackage "BAR"
  (:use "COMMON-LISP")
  (:shadow #:=))

(in-package "BAR")

(defmacro dflet1 ((fname &rest def) &body body)
  (let ((old-f-def (gensym)))
    `(let ((,old-f-def (symbol-function ',fname)))
       (unwind-protect (progn (setf (symbol-function ',fname) (lambda ,@def))
                              ,@body)
         (setf (symbol-function ',fname) ,old-f-def)))))

(defmacro dflet* ((&rest decls) &body body)
  (if decls
      `(dflet1 ,(car decls)
         (dflet* ,(cdr decls)
           ,@body))
      `(progn ,@body)))

(defun first-name (x) (gnarly-accessor1 x))
(defun address-city (x) (gnarly-accessor2 x))
(defun = (&rest args) (apply 'common-lisp:= args))
(defmacro & (a b) `(block-and (lambda () ,a) (lambda () ,b)))
(defun block-and (a b) (when (funcall a) (funcall b)))

(defun some-predicate (x)
  (& (= (first-name x) "John") (= (address-city x) "Austin")))

(defun make-parse-tree-from-predicate (predicate-thunk)
  (dflet* ((first-name (x) '#:|firstName|)
           (address-city (x) '#:|addressCity|)
           (= (a b) `(= ,a ,b))
           (block-and (a b) `(& ,(funcall a) ,(funcall b))))
    (funcall predicate-thunk nil)))

Then (make-parse-tree-from-predicate #'some-predicate) yields (& (= #:|firstName| "John") (= #:|addressCity| "Austin")), which we can manipulate and then pass to a SQL query printer.

Here I implemented dynamically-scoped functions using unwind-protect, which is not as powerful (or, possibly, efficient) as the implementation presented in Costanza's paper, but is simpler (I also used the same trick to implement dynamically-scoped variables in Parenscript).

The property of the same Lisp code to mean different things in different contexts is called duality of syntax by Doug Hoyte in his excellent book Let Over Lambda (almost finished reading, promise to write a review soon). Lisp offers this property both at run-time (via late-binding and closures) and at macro-expansion time (via homoiconicity and the macro-expansion process itself).

Another technique from Let Over Lambda illustrated in the above code is the recursive macro. This one is a personal favorite of mine; I find that the iterative simplification that recursive macros express provides very clean and maintainable code.

This code also provides examples of the two problems that the closure-oriented metaprogramming approach encounters in Common Lisp:

The first is the fact that we had to shadow = in our package. Common Lisp forbids the redefinition of the functions, macros and special forms defined in the standard, so we have to go out of our way if we want to achieve that effect. Barry Margolin provided a rationale for this in comp.lang.lisp post.

The second is the fact that Common Lisp has so many special forms and macros - and just happens to be one of them. Smalltalk avoids this problem by doing virtually everything via message passing and closures. In Common Lisp we don't have this straightjacket, but we also don't have this luxury of assuming that everything is an object or a closure.

Another Common Lisp feature that might break this example is function inlining (then again, I did just write about the benefits of late-binding...).

Complete computing system in 20,000 lines of code

I just finished watching Ian Piumarta's talk on the project at Viewpoints Research Institute to build a complete (metal up) personal computer system in 20,000 lines of code. While the easy way to do this would be to use APL, Ian, Alan Kay, Dan Ingalls, and the others working on the project have instead opted to go for building metacircular/self-describing systems instead. Of course, in modern parlance this is called "reflection," a very crappy version of which can be found in the Java language and runtime system. Among fascinating programming language and compiler topics, Ian discusses Schorre's Meta-II compiler compiler (developed in 1962), which had a self-describing grammar. Fascinating stuff, and in my opinion critically important, since the only proven way to reduce software complexity has been, to, well, reduce software complexity - less lines of source code written in a simpler way makes for better, more maintainable software, and this is exactly what the project aims to do.

Here is the link to the video:

http://stanford-online.stanford.edu/courses/ee380/070214-ee380-300.asx