I'm hacking on TXR these days which contains a Lisp dialect called TXR Lisp. Lisp hacking and research is fun, in particular if you have the freedom of your own dialect.
The current public release TXR Lisp still has an embarrassingly shoddy implementation of "places": expressions which not only evaluate, but serve as assignable locations. I implemented most of the place-manipulating operators (set, inc, push, ...) as special forms, and only a small repertoire of places is hard-coded in the interpreter. (And that, by the way, creates one of the impediments against going to a compiler.)
I have thrown all that out and created a macro-based system for places. Instead of copying the Common Lisp one, I drummed up something new.
Common Lisp lets programmers register assignment places as "setf expanders" which return five values: lists of temporary variables, access and store forms and such. (Google for "CLHS get-setf-expansion").
I have taken a somewhat different, though necessarily closely-related approach. The creator of a new place provides two or three functions. These functions take a place and a piece of code, and wrap it with macrolets for accessing the place. These macrolets are given names that the caller specifies. Of course, I have a macro for writing these functions as a capsule.
The three functions provide a way for handling the access and update of a place, a simple store to a place without an access, and the deletion of a place.
This third item is new. In TXR Lisp, there is a del operator: a place can be vaporized. Not all places support deletion, but many do. For instance you can do (del [some-vector 3]) to delete an item from a vector. Or a range. Hashes support deletion. (del (car x)) works: what happens when you delete the car of a cons cell is that the cdr is popped, and the popped item is transferred into the car. Thus if x holds (1 2 3), the (2 3) part is popped to produce (3) and the 2 moves into the car, resulting in X holding (2 3). (I just realized that we need place insertion to complement place deletion!)
Here is how a (vecref <vector> <index>) place is defined:
The rlet macro is something I just invented days ago. It is like let, but it detects and optimizes cases when a symbol is bound to another symbol, and turns these into symbol macrolets. Demo:
$ ./txr -p "(sys:expand '(rlet ((a b) (c (form))) (list a b c)))"
(let ((c (form))) (list b b c))
Look, the (a b) disappeared in the form expansion, and b was replaced by a. That's because the macro expansion is this:
$ ./txr -p "(macroexpand '(rlet ((a b) (c (form))) (list a b c)))"
(symacrolet ((a b)) (let ((c (form))) (list a b c)))
rlet also propagates simple constants, as shown by the variable d:
$ ./txr -p "(sys:expand '(rlet ((a b) (c (form)) (d 42)) (list a b c d)))"
(let ((c (form))) (list b b c 42))
Of course, let can only be replaced by rlet in certain circumstances, when we don't rely on the binding actually providing storage semantics. Above, we can only replace a with b, if a is not assigned anywhere. And since d is replaced with 42 blindly, it cannot be assigned.
Obviously, rlet is something you don't need if you have an optimizing compiler which eliminates useless temporary variables and propagates constants! I just wanted nicer expansions from the places system.]]
So anyway, the defplace creates three functions which provide advice for how to correctly access, update and delete a place. They wrap this advice, which takes the form of local functions or macros, and any additional lexical definitions they need, around a supplied piece of code, and that code can refer to that.
Here is how this advice is used, in the implementation of the swap operator. This shows you the real beauty of the system, because we can write a completely robust swap, but we don't have to use anything resembling CL's get-setf-expansion and its five cumbersome return values:
What is the env doing there? We have to pass the macro-time environment down, because places can be macros! For instance what if we do (swap a b), but a is actually a lexical symbol macro for (car x) and b is something similar: the with-update-expander macro will take care of expanding these places, so it fetches the correct advice for the expanded places.
So note how we have a completely naive looking pieces of code, a three point swap:
All we did was generate some gensyms, use a couple of macros to obtain the place-accessing expertise from some generated lexical helpers, and then wrote a straightforward swap.
$ ./txr -p "(sys:expand '(swap a b))"
(let ((#:g0044 a)) (sys:setq a b) (sys:setq b #:g0044))
$ ./txr -p "(sys:expand '(swap (car c) (cdr c)))"
(let ((#:g0044 (car c))) (sys:rplaca c (cdr c)) (sys:rplacd c #:g0044))
$ ./txr -p "(sys:expand '(swap 1 2))"
./txr: unhandled exception of type eval-error:
./txr: during expansion at string:1 of form (swap 1 2)
./txr: message: form 1 is not syntax denoting an assignable place
$ ./txr -p "(sys:expand '(swap [f x] [g y]))"
(let ((#:g0067 [f x])) (let ((#:g0056 [g y])) (let ((#:g0044 #:g0067))
(sys:setq f (sys:dwim-set f x #:g0056)) (sys:setq g (sys:dwim-set g y #:g0044)) #:g0044)))
Note the [] notation is completely generic, so f and x could be lists (or vectors, hashes, strings). In this case, f and x are themselves expected to be places. Thus [f x] must be a place, and f also must be a place. The reason is that if we manipulate a list, we may have to assign the new list to the old variable. In general, sys:dwim-set could cons up a new list.
So in summary, Lisp is always fresh and keeps me interested in hacking. Even old things (solved problems like assignment places) can be looked at in a new light.
Check out this recursive implementation of shift, which is like Common Lisp's shiftf:
(defmacro shift (:env env . places)
(tree-case places
(() (eval-err "shift: need at least two arguments"))
((place) (eval-err "shift: need at least two arguments"))
((place newvalue)
(with-update-expander (getter setter) place env
^(prog1 (,getter) (,setter ,newvalue))))
((place . others)
(with-update-expander (getter setter) place env
^(prog1 (,getter) (,setter (shift ,*others)))))))
$ ./txr -p "(sys:expand '(shift a b c d))"
(prog1 a (sys:setq a (prog1 b (sys:setq b (prog1 c (sys:setq c d))))))
> The expressive power of Lisp has drawbacks. There is no such thing as a free lunch.
This line doesn't hold on its own but as the ending of the article it was very powerful.
I had heard that extra power can make it easier to do things wrong, but the idea that extra power can cause problems even when you do things right is fascinating.
The current public release TXR Lisp still has an embarrassingly shoddy implementation of "places": expressions which not only evaluate, but serve as assignable locations. I implemented most of the place-manipulating operators (set, inc, push, ...) as special forms, and only a small repertoire of places is hard-coded in the interpreter. (And that, by the way, creates one of the impediments against going to a compiler.)
I have thrown all that out and created a macro-based system for places. Instead of copying the Common Lisp one, I drummed up something new.
Common Lisp lets programmers register assignment places as "setf expanders" which return five values: lists of temporary variables, access and store forms and such. (Google for "CLHS get-setf-expansion").
I have taken a somewhat different, though necessarily closely-related approach. The creator of a new place provides two or three functions. These functions take a place and a piece of code, and wrap it with macrolets for accessing the place. These macrolets are given names that the caller specifies. Of course, I have a macro for writing these functions as a capsule.
The three functions provide a way for handling the access and update of a place, a simple store to a place without an access, and the deletion of a place.
This third item is new. In TXR Lisp, there is a del operator: a place can be vaporized. Not all places support deletion, but many do. For instance you can do (del [some-vector 3]) to delete an item from a vector. Or a range. Hashes support deletion. (del (car x)) works: what happens when you delete the car of a cons cell is that the cdr is popped, and the popped item is transferred into the car. Thus if x holds (1 2 3), the (2 3) part is popped to produce (3) and the 2 moves into the car, resulting in X holding (2 3). (I just realized that we need place insertion to complement place deletion!)
Here is how a (vecref <vector> <index>) place is defined:
[[ Digression: what is rlet in the above?The rlet macro is something I just invented days ago. It is like let, but it detects and optimizes cases when a symbol is bound to another symbol, and turns these into symbol macrolets. Demo:
Look, the (a b) disappeared in the form expansion, and b was replaced by a. That's because the macro expansion is this: rlet also propagates simple constants, as shown by the variable d: Of course, let can only be replaced by rlet in certain circumstances, when we don't rely on the binding actually providing storage semantics. Above, we can only replace a with b, if a is not assigned anywhere. And since d is replaced with 42 blindly, it cannot be assigned.Obviously, rlet is something you don't need if you have an optimizing compiler which eliminates useless temporary variables and propagates constants! I just wanted nicer expansions from the places system.]]
So anyway, the defplace creates three functions which provide advice for how to correctly access, update and delete a place. They wrap this advice, which takes the form of local functions or macros, and any additional lexical definitions they need, around a supplied piece of code, and that code can refer to that.
Here is how this advice is used, in the implementation of the swap operator. This shows you the real beauty of the system, because we can write a completely robust swap, but we don't have to use anything resembling CL's get-setf-expansion and its five cumbersome return values:
What is the env doing there? We have to pass the macro-time environment down, because places can be macros! For instance what if we do (swap a b), but a is actually a lexical symbol macro for (car x) and b is something similar: the with-update-expander macro will take care of expanding these places, so it fetches the correct advice for the expanded places.So note how we have a completely naive looking pieces of code, a three point swap:
All we did was generate some gensyms, use a couple of macros to obtain the place-accessing expertise from some generated lexical helpers, and then wrote a straightforward swap. Note the [] notation is completely generic, so f and x could be lists (or vectors, hashes, strings). In this case, f and x are themselves expected to be places. Thus [f x] must be a place, and f also must be a place. The reason is that if we manipulate a list, we may have to assign the new list to the old variable. In general, sys:dwim-set could cons up a new list.So in summary, Lisp is always fresh and keeps me interested in hacking. Even old things (solved problems like assignment places) can be looked at in a new light.
Check out this recursive implementation of shift, which is like Common Lisp's shiftf: