Friday, March 2, 2007

Language feature request: define by renaming

A few weeks back, I was looking at Prism. Prism is a probabilistic model checker. This means it can answer interesting questions about your model. For example, when designing a protocol, you can ask it: what is the probability that a message is lost? Or, when building a model of a soft realtime system, you can ask it: what is the probability that an operation will take longer than 100ms. etc.

Anyway, that's besides the point. What I want to talk about today is a feature that I've seen in Prism's model description language (which looks a lot like Promela). Here is the second part of the Prism tutorial. It introduces a language feature that I loved instantly. It is called module renaming and it rocks.

Module renaming basically works in the following way: take this function, which does this. Then create another function, which is exactly the same, but replace this symbol by another.

I can imagine how this can work for a general-purpose programming language. Define a function which sums two numbers:

pseudocode: sum x y = x + y


Then define the product to be like the sum, except replace + by *.

pseudocode: product = sum where + = *


That's nice. So I thought I'd try and see if I can implement this using lisp macros. I don't have much experience with lisp, but here's how I sort-of did it:

First thing's first. Create a function that takes a list and replaces every "source" with "target".

(defun rename-symbol (list source target)
(if (eq list nil)
nil
(cons
(if (listp (first list))
(rename-symbol (first list) source target)
(progn
(if (eq (first list) source)
target
(first list))))
(rename-symbol (rest list) source target))))


Here's how it works:

CL-USER> (rename-symbol `(+ 1 2) '+ '*)
(* 1 2)


Well, I actually want to perform multiple renamings, so I replaced source and target with an association list (sort of like a hash table):

(defun association (item alist)
(rest (assoc item alist)))

(defun rename-symbols (list alist)
(if (eq list nil)
nil
(cons
(if (listp (first list))
(rename-symbols (first list) alist)
(if (not (eq (association (first list) alist) nil))
(association (first list) alist)
(first list)))
(rename-symbols (rest list) alist))))


Which does the same thing, except it takes an association list and can replace multiple symbols. Here's how it works:

CL-USER> (rename-symbols `(defun sum (a b) (+ a b)) '((+ . *) (sum . product)))
(DEFUN PRODUCT (A B) (* A B))


See where we're going? Now let's write a simple macro:

(defun rename (list alist)
(eval (rename-symbols list alist)))


And here's how Lisp's syntax can be extended to allow renaming:

(setq my-function `(defun sum (a b) (+ a b)))

(rename my-function nil)
(rename my-function '((+ . *) (sum . product)))


When evaluating the above, you'll end up with two functions, sum and product, which do what you expect.

Disclaimer: I am a Lisp beginner and I've probably made some mistakes.

I welcome any and all corrections/improvements/suggestions. I would be especially interested in creating a rename macro that works as follows:

(defun sum (a b) (+ a b))
(rename sum product '((+ . *)))


If there is any Lisp guru reading this, please let me know ;-)

Also, I am curios about how this could be implemented in languages such as Ocaml or Haskell. Some of the readers will be quick to point out that this feature is not really required, because you can get the same benefit by creating a function which is more generic that product and sum, which would look like this in Haskell:

combine op x y = op x y
sum = combine (+)
product = combine (*)


But I find the rename feature extremely geeky and cool. So let me have it :D.

2 comments:

Drew Crampsie said...

I've got a couple comments about the article, after which i'll post what i think is a somewhat nicer solution. This was fun!

First off:

(defun rename-symbol (list source target)
(if (eq list nil)
nil



what you really want to say here is 'when this list is not the empty list'. In common lisp the empty list is also the false value, and there is a WHEN macro to avoid all the (if t nil) mess, so (when list ...) is more what you want here.


(cons
(if (listp (first list))
(rename-symbol (first list) source target)
(progn
(if (eq (first list) source)
target
(first list))))
(rename-symbol (rest list) source target))))


COND is what you want here, the multiple IFS and PROGN are a sure sign.

So, something like:


(defun rename-symbol (list source target)
(when list
(cons
(cond ((listp (first list))
(rename-symbol (first list) source target))
((eq (first list) source)
target)
(t
(first list)))
(rename-symbol (rest list) source target))))


... is a little more lispy. Note that this function is not tail recursive and will blow the stack if LIST is too large.

As for RENAME-SYMBOLS, i think an alist is the wrong datatype, a plist is better for this use, especially with a creative use of the default parameter to getf. Also, i like LOOP and find it makes for much more readable code when doing something like this:


(defun rename-symbols (form symbol-map-plist)
(loop
:for sexp :in form
:collect
(if (symbolp sexp)
(getf symbol-map-plist sexp sexp)
(rename-symbols sexp symbol-map-plist))))


I think that's a little cleaner myself.
then you say

"See where we're going? Now let's write a simple macro:

(defun rename (list alist)
(eval (rename-symbols list alist)))"


This is most certainly _not_ a macro. This is a function that calls EVAL (in general a bad idea as EVAL runs in its very own lexical environment..).

That said, this is an excellent example of how code-as-data and macros can help to make lisp into whatever you want, and i'm sure it was a lot of fun :).

Here is my solution for you.


#| FUNCTION-RENAME is a Prism-like thing

Example usage:


CL-RENAME> (defun sum (a b) (+ a b))
CL-RENAME> (get 'sum 'source)
((A B) (+ A B))
CL-RENAME> (function-rename 'sum 'product '(+ *))
#FUNCTION (LAMBDA (A B)) {B2274AD}>
CL-RENAME> (function-rename 'sum 'subtract '(+ -))
#FUNCTION (LAMBDA (A B)) {B24678D}>
CL-RENAME> (function-rename 'sum 'div '(+ /))
#FUNCTION (LAMBDA (A B)) {B267555}>
CL-RENAME> (sum (subtract (product 2 2) (div 256 2)) 4)
-120

|#
(defpackage #:cl-rename
(:use #:common-lisp)
(:shadow #:defun))

(defmacro defun (name function-lambda-list &body body)
`(progn
;; set a 'source property on the symbol plist
(setf (get ',name 'source)
(cons ',function-lambda-list
',body))
(cl:defun ,name ,function-lambda-list ,@body)))

(defun rename-symbols (form symbol-map-plist)
(loop
:for sexp :in form
:collect
(if (symbolp sexp)
(getf symbol-map-plist sexp sexp)
(rename-symbols sexp symbol-map-plist))))

;; I don't really like this name.
(defun function-rename (function-name new-name symbol-map-plist)
(setf (symbol-function new-name)
(coerce (cons 'lambda
(rename-symbols
(get function-name 'source)
symbol-map-plist))
'function)))

stefan.ciobaca said...

Thanks for the hints about my Lisp style. I know what a macro is, that was a typo :D

That being said, your solution is exactly the thing I hoped I would get. It looks very clean I hope people find it useful.