Thursday, February 28, 2008

Macro-ro-ro Your Code Gently Down the Screen...

Sorry about the title but I just feel a little silly having to explain why macros rock so hard when the C preprocessor has been doing them almost as long as Lisp. It just ain't that hard an idea to get. It seems to me anyone writing a sufficient amount of code will notice recurring patterns not susceptible to attack by encapsulation in a function. Consider OpenGL.

With OpenGL, certain things have to happen between a glBegin and a glEnd, and certaing things are not allowed between a glBegin/End pair. One of them being a second glBegin. The poor OpenGL programmer now has one more thing to worry about, and tedious boilerplate to write like a robot (in this case just a one-liner glEnd() but try not to lose the big picture principle, OK Sparky? This is a deliberately simple example). Is there any way to alleviate this drudgery?

Well, quite a few statements will be squeezed of between glBegin and glEnd, cuz OpenGL is no joy to code. We can write a function called do-between-begin-end and pass it a first class function (unless your BDFL does not see the need), but then (in CL) we end up with:
(lambda ()
...your dozen lines of code here...

Not the end of the world, but remember, I am just warming up. These macro posts will go on forever. Anyway, with a macro we lose the lambda speed bump:
(with-gl-begun ()
...your dozen lines here...)

What's with the ()? Well, truth is glBegin takes a parameter that says what we are beginning (line strip? triangles? quads?) so I kinda lied, the contrast should be...
(do-between-begin-end gl_quads
(lambda ()
...your dozen lines of code here...))

(with-gl-begun (gl_quads)
...your dozen lines here...)

So, yeah, I can write do-between-gl-begin-end and never worry about begin and end again, but I am stuck with a little line noise there.

If we look at a classic example of how Lisp macros hide boilerplate, we see this more egregious after/before pair:
(with-open-file (f "xxx")
(print "line 1 of xxx:")
(print (read-line f)))

Versus what I have to write without with-open-file:
(let ((f (open "xxx"))
(success nil))
(print "line 1 of xxx follows:")
(print (read-line f))
(close f))
(setf success t))
(unless success
(close f :abort t))))

The odd thing is that Pythonistas reject macros while fervently embracing tidy code -- and Python code does look very clean -- but all we are doing with macros (so far) is making code neater. Well, no, we are also releaving the programmer of drudgery and making the code more reliable by automating the insertion of necessary boilerplate such as error checking.

Let's turn now to a dead simple hiding of boilerplate, Paul Graham's AIF swiped from the inestimable On Lisp:
(defmacro aif (test-form then-form &optional else-form)
‘(let ((it ,test-form))
(if it ,then-form ,else-form)))

The alternative is:
(let ((temp (big-long-fn a b c)))
(if temp
(handle-it temp x y)
(do-something-else a x))

By the way, if you do not like Graham's anaphoric thing (using "it" as the implicit temporary variable), use my BIF which takes a mnemonic for the intermediate result:
(defmacro bif (bindvar boundform yup &optional nope)
`(let ((,bindvar ,boundform))
(if ,bindvar ,yup ,nope)))

And then a more realistic use:
(bif sol (math-problem-solution prb mx)
(display-solution sol)
(tell-user "No can do!"))

In this just my first offering on macros I have discussed only the advantages of automatically generating boilerplate. There is much more to come, but I would like to close by reiterating my befuddlement that this even needs explaining, and in the context of the C preprocessor precedent mentioned above:

I just dug into the old C version of my Algebra software for just one out of hundreds of macros, one which iterates over the children of a node (a custom tree struct in my application) in something akin to the C "for" statement:
#define fork(PAR,TMP_KID,NXT_KID)      \
for ( NXT_KID = (TMP_KID = firstk( PAR))? nexts(TMP_KID):NIL \

The crucial thing to note is that this macro is meant to allow children to be unlinked from the parent during the traversal, so it is necessary to capture the next child after the current child before processing the current child, because parents only see their first and last child as I had things arranged.

So now I could write code like this (instead of something like the macro definition above):
fork( usg, tusg, nusg) {
kidDetach( tusg); ;; losing the "next child" link
xInsKid( tpar, pusg, tusg);

Next time we will do something even jazzier.

Tuesday, February 26, 2008

Ooh! Ooh! My turn! Why Lisp?

Brace yourself. The first reason you should be using Lisp is a non-reason, an answer to an objection, a negation, a let-down: Lisp is just an ordinary programming language.

I'll wait while you pick yourself off the floor. What a terrible place to start! But it must be said. It is the first hurdle on the road to Lisp. Xenophobia never feels like fear of the strange, it feels like dislike. But one of the best young Lispers to show up at a Lisp-NYC meeting sat down, ordered a beer, and was smart enough to make it his first question: Can you use Lisp for conventional programming? Can it read a database? Can it run a GUI?


Lisp at one level of understanding is just a normal high level programming language. Those parentheses look quite different but constitute only a superficial difference from the conventional chicken scratch syntax of semi-colons, braces, full stops, and brackets. When a conventional programmer sits down to program Lisp, they feel quickly at home: Lisp is just another 3GL.

I feel terrible about this. I am supposed to be up on a soapbox preaching eternal salvation and ecstasies glorious and unknown and we will touch on that below but in the end your correspondent is just a simple application programmer and if you check my Road to Lisp you will discover that I (re)discovered Lisp just to find an easier way to create educational math software.

Lispers are accused of religous fanaticism and zealotry -- nope, our enthusiasm is all about getting applications built faster with less pain. Which brings me to the bad news: the next reason I have to offer for using Lisp is almost as boring as the first: Lisp is mature. Turns fifty or so in 2008. In 1994 when it was old enough to be President of the United States it got an ANSI Standard. How stable can you get?

So far we have ordinary, old, and codified and I am losing my audience. Send in the clowns!

Fine, a little pizazz: it ain't just old. The old translates to polish. Lisp did not begin with a standard and it did not begin as a single-implementation BDFL strangulation such as Python or Perl or Ruby. It began experiment?

Two score and ten years ago our foregeeks started from the simple idea that code and data were one and began evolving a huge tool chest of HLL functionality spread across several competing dialects. For some reason they took the engineering so seriously that whenever a nooby picks up one of these tools surprise! surprise! it turns out to work precisely the way they need it to. It seems like magic but it is not. The magic is just a long history of use and careful refinement by very good engineers and was possible precisely because there was no standard and there was no BDFL.

Back to the yawns: most Common Lisp implementations are native compiled. Yeah, yeah, I know, computers are fast and we are all doing Web apps where network latency decides all but I work on a desktop interactive expert system that needs all the horsepower it can get and to tell you the truth when building something like that more horsepower makes more better features possible so isn't it nice to compile down to the metal?

More yawns: ephemeral GC, the best OO model you can imagine, multiple implementations to choose from including free ones.... hey, even I am getting bored. But my Road also reveals that I stumbled onto this staid dependable workhorse only after squandering mucho dollars and hours on half-baked gleams-in-the-eye programming tools that promised a world of productivity and delivered only reboots. At which point boring looks pretty damn exciting.

Left as an exercise is connecting the stable/standard/refined dot with other dots of dynamic interactive languages still emerging from sea and periodically burying their installed bases in volcanic ash. Can you scream Perl 6? Sher ya can. Has Guido finally axed first-class functions yet? It is fun watching languages evolve, but if you will excuse me I really do have an application to get out.

With the dull stuff out of the way we can indulge at long last in some Why Lisp? fireworks.

We'll build slowly, starting with Lisp being interactive, dynamic, reflective, functional, compiled, mature, standardized, has a vast array of library functions and data structures (including the wonderful and ubiquitous list), multiple value return, special variables, CLOS (including multiple inheritance and multi-methods), the MOP, first-class functions and omigod! closures, destructuring-bind, LOOP, lexical scope, untyped variables, typed data, object identity for everything but numbers and characters and now repeat a few of those things a few times to make clear how helpful they are to getting applications built, such as the vast toolchest. Gasp.

I call that starting slowly because everything above can be found in some language. It is wonderful that only Common Lisp has them all, but is there anything that really sets Lisp off? Is there some protein that cannot be mimicked by other invading dynamic language organisms, some shibboleth their tongues cannot form?

More prosaically, is there some quality those languages cannot copy without becoming Lisp?

At ILC 2002 former Lisp giant now Python advocate Peter Norvig was for some reason allowed to give the keynote address like Martin Luther leading Easter Sunday mass at the Vatican and pitching Protestantism because in his talk Peter bravely repeated his claim that Python is a Lisp.

When he finished Peter took questions and to my surprise called first on the rumpled old guy who had wandered in just before the talk began and eased himself into a chair just across the aisle from me and a few rows up.

This guy had wild white hair and a scraggly white beard and looked hopelessly lost as if he had gotten separated from the tour group and wandered in mostly to rest his feet and just a little to see what we were all up to. My first thought was that he would be terribly disappointed by our bizarre topic and my second thought was that he would be about the right age, Stanford is just down the road, I think he is still at Stanford -- could it be?

"Yes, John?" Peter said.

I won't pretend to remember Lisp inventor John McCarthy's exact words which is odd because there were only about ten but he simply asked if Python could gracefully manipulate Python code as data.

"No, John, it can't," said Peter and nothing more, graciously assenting to the professor's critique, and McCarthy said no more though Peter waited a moment to see if he would and in the silence a thousand words were said.

Come to think of it...

Monday, February 18, 2008

Arc!Cells: It's Alive!!!

In the Cells Manifesto I explained what all the Cells hoopla was about, including the vast array of other people doing the same thing only not as well as His Kennyness.

In the Baby Steps article we saw a primitive exploration of the mere beginnings of a partial implementation.

Well I am through kidding around! Below the fold you will find what should be standalone code for a solid Arc implementation (albeit not as fully splediferous as The Real (Common Lisp) Deal) of vanilla Cells. Also available from CVS.

The furnace example at the end will (a) provoke even more nutty ads for furnace installations (sigh) and provide a rough idea of the magic: make one state change and like so many dominoes other state change follows as effect follows cause, with user-defined observer callbacks invoked so our virtual models can act on the world outside the model, all under a declarative paradigm the academics call reactive programming because a better name like dataflow would not make them sound so... I digress.

Enjoy. Arc code enhancements always welcome, especially where I have reinvented built-in Arc constructs.

;; - - - - - - - - - - - - - cut here - - - - - - - - - - - - - -
;; copyright 2008 by Kenny Tilton
;; License: MIT Open Source

;;; --- detritus ------------

(def prt args
; why on earth does prn run the output together?
(apply prs args)

(def tablemap (table fn)
; fns are always huge and then a tiny little table ref just hangs off the end
(maptable fn table)

(def cadrif (x) (when (acons x) (cadr x)))

(mac withs* (parms . body)
; faux dynamic binding
(let uparms (map1 [cons (uniq) _] (pair parms))
`(do ,@(map1 (fn ((save curr val))
`(= ,save ,curr ,curr ,val)) uparms)
(do ,@body)
,@(map1 (fn ((save curr val))
`(= ,curr ,save)) uparms)))))

;;; -------------------- Cells ----------------------
;;; A partial implementation of the Cells Manifesto:
;;; --- globals --------------------

(= datapulse* 0) ;; "clock" used to ensure synchronization/data integrity
(= caller* nil) ;; cell whose rule is currently running, if any
(= mds* (table)) ;; model dictionary
(= obs* (table)) ;; global "observer" dictionary

;;; --- md -> modelling ----------------------------------------

(mac defmd ((type-name (o includes)
(o pfx (string type-name "-")))
. slot-defs)
(deftem (,type-name ,@includes)
ctype ',type-name
cells nil
,@(mappend (fn (sd) (list (carif sd)(cadrif sd))) slot-defs))
; define readers
,@(map (fn (sd)
`(def ,(coerce (+ (string pfx) (string sd)) 'sym) (i)
(slot-value i ',sd)))
(map carif slot-defs))
; define writers
,@(map (fn (sd)
`(def ,(coerce (+ "set-" (string pfx) (string sd)) 'sym) (i v)
(set-slot-value i ',sd v)))
(map carif slot-defs))))

;;; --- model initialization

(def to-be (i)
(do1 i
(md-finalize i)
(md-awaken i)))

(def md-finalize (i)
(do1 i
(if (acons i)
(map md-finalize i)
; register instance in a namespace for inter-i dependency
(= (mds* (md-name i)) i)

; move cells out of mediated slots into 'cells slot
(tablemap i
(fn (k v)
(when (c-isa v 'cell)
(= v!model i v!slot k)
(push (list k v) i!cells)
(= (i k) 'unbound))))))))

(def md-awaken (i)
(do1 i
(if (acons i)
(map md-awaken i)
(do ; bring each slot "to life"
(tablemap i
(fn (k v)
(aif (md-slot-cell i k)
(slot-ensure-current it)
(slot-value-observe i k v 'unbound))))))))

(def md? (name)

;; --- start of cells stuff ------------------

(def cells-reset ()
(= datapulse* 1) ; not sure why can't start at zero
(= caller* nil)
(= mds* (table)))

(def ctype-of (x)
(when (isa x 'table)

(def c-isa (s type)
(is ctype-of.s type))

(defmd (cell nil c-) ;; the c- gets prefixed to all accessor names
(pulse 0)
(pulse-last-changed 0)
(cache 'unbound)

(defmd (model nil md-)
; any template to be mediated by cells must include model
name ; used so one instance can find another by name

(def md-slot-cell (i s)
(alref i!cells s))

;;; --- reading a slot -------------------------

(def slot-value (i s)
(aif (md-slot-cell i s)
(do (when caller*
(pushnew caller* it!users)
(pushnew it caller*!useds))
(slot-ensure-current it))
(i s)))

(def calculate-and-set (c)
; clear dependencies so we get a fresh set after each rule run
(each used c!useds
(= used!users (rem c used!users)))
(= c!useds nil)

; run the rule
(let nv (withs* (caller* c)
(c!rule c!model))
(unless c!useds
; losing rules with no dependencies
; is a big performance win
(optimize-away c))
(slot-value-assume c nv)))

(def optimize-away (c)
(pull (assoc c!slot ((c-model c) 'cells)) ((c-model c) 'cells))
(each user c!users
(pull c user!useds)
(unless user!useds ; rarely happens
(optimize-away user))))

(def slot-ensure-current (c)
; It would be fun to figure out a more readable
; version of the next consition. I tried, can't.
(when (and c!rule
(or (is 0 c!pulse-last-changed)
(no (or (is c!pulse datapulse*)
(no (any-used-changed c c!useds))))))
(calculate-and-set c))

(= c!pulse datapulse*)

(when (is 0 c!pulse-last-changed) ;; proxy for nascent state
(= c!pulse-last-changed datapulse*)
(slot-value-observe c!model c!slot c!cache 'unbound))

(def any-used-changed (c useds)
(when useds
; So happens that FIFO is better order for this
(or (any-used-changed c (cdr useds))
(let used (car useds)
(slot-ensure-current used)
(> used!pulse-last-changed c!pulse)))))

;;; --- writing to a slot -----------------------

(def set-slot-value (i s v)
(aif (md-slot-cell i s)
(do (++ datapulse*)
(slot-value-assume it v))
(prt "you cannot assign to a slot without a cell" i s)))

(def slot-value-assume (c v)
(= c!pulse datapulse*)
(with (i c!model ov c!cache)
(unless (is v ov)
(= c!cache v)
(= (i c!slot) v)
(= c!pulse-last-changed datapulse*)
(slot-propagate c ov)))

;;; --- dataflow --------------------------------
;;; Propagate state change from cell to cell and
;;; as needed from Cell to outside world
(def slot-propagate (c ov)
(let caller* nil
(each user c!users
(slot-ensure-current user))
(slot-value-observe c!model c!slot c!cache ov)))

(def slot-value-observe (i s v ov)
(awhen (md-slot-cell i s)
(observe it!observers i s v ov))
(observe (alref i!observers s) i s v ov)
(observe obs*.s i s v ov))

(def observe (o i s v ov)
(if (acons o)
(map (fn (o2) (o2 i s v ov)) o)
o (o i s v ov)))

;;; --- constructor sugar --------------------

(mac imd (name (type) . inits)
`(inst ',type 'name ',name
,@(mappend (fn ((s v)) `(',s ,v)) (pair inits))))

(def c-in (v)
(inst 'cell 'cache v))

(mac c? (rule . observers)
`(inst 'cell
'rule ,rule
'observers (list ,@observers)))

;;; --- example --------------------------------

(defmd (furnace (model) fur-)
on temp (fuel 0)
;;; another way to do observers, at the class level
;;; observers `((fuel ,(fn (i s v ov)
;;; (prt 'md-defined-observer-sees i!name s v ov))))

(defmd (thermostat (model) thermo-)
preferred actual)

(def test-furnace ()
(do (cells-reset)
(prt '----------start-------------------)
(let (th f) (to-be
(imd th42 (thermostat) preferred (c-in 70) actual 70)
(imd f-1 (furnace)
fuel 10
on (c? [let th (md? 'th42)
(< (thermo-actual th)(thermo-preferred th))]
; an instance-level observer
(fn (i s v ov)
(prt "Sending"(if v 'on 'off) "control sequence to furnace f-1"))))))
;;; A global observer of any slot called "on"
;;; (push (fn (i s v ov)
;;; (prt 'on-global-obs-1 i!name s v ov))
;;; obs*!on)

(prt "After awakening the model the furnace is" (if (fur-on f) 'on 'off))
(set-thermo-preferred th 72) ;; the furnace comes on cuz we want it warmer


;;; Output:
; ----------start-------------------
; Sending off control sequence to furnace f-1
; After awakening the model the furnace is off
; Sending on control sequence to furnace f-1

A Terrible Thing

some comp.lang.lisp yobbo wrote:
You know, with you, I just don't know how to read your posts (I mean all the stuff about arc). You're like one of those oriental mysteries that this sub-linear mind just cannot fathom.

Google Adsense feels your pain. This is a Lisp blog and I have seen ads for furnace installations and nursing jobs in Hawaii. Well, what do you want from people who use Python?

Lemme help. In your country, do you have the game "in plain view"? The inventor was a genius of psychology, especially perception. Here in Umaguhwallaweeland we like to do it with chocolate candies on Easter aka find-the-candy-day. We take little candies (or for the adults splits of vodka) and scatter them around the house in plain view of anyone standing in any normal location.

The seekers run about frantically freaking out over the fact that they know they are missing chocolates or Stolys just there for the taking while the hiders try not to lose bladder control looking straight at the candies watching the seekers burn more calories than a seagull in a headwind.

Something like this:: Maybe I was too hard on Sohail

That said, your confession indicates you are almost ready to leave the temple. You just need to make the Giant Kenny Leap (GKL). This was when I realized that when I had these weird feelings of dissonance that G*d was speaking to me so I would never be wrong if I just listened, that the dissonance meant something and that for the love of G*d I should not ignore the dissonance.

When writing code, that is, but I recognize the rule in your inner conflict.

Bullseye. Arrow. Just let go.

The GKL moment came working on The Greatest Lisp Application ever now sadly lost to mankind (another story) but during whose creation I realized nothing more sophisticated than that if it feels bad stop it and if it feels good yadda yadda. As you in your temple-leavingness detected this is not and should not be subjected to the impotence of conscious reason, the mistake that doomed AI but I digress.

One of the quotations in my fortune cookie file covers someone who came close but in the end failed on one of my he-cannot-be-serious posts and decided I was serious... when your pattern recognition system recognizes irony, why are you are arguing? Your PRS safely jaywalks you across a dimly lit four-lane highway in a driving rainstorm while it is a crapshoot whether that is deoderant or hairspray your cortex is applying to your underarm.

Just Listen to these vagosities percolating up from neural regions unknown--there is no truer guide. Shakespeare almost had it right:
What a tangled web we weave when first we reason. 

And the United Negro College Fund was just a hair outside as well:
The mind is a terrible thing.

Oops, here comes The Odd Couple re-run, gotta go.

Friday, February 15, 2008

Faux dynamic binding for Arc

The objective in what follows is to simulate one of my favorite features of CL, which is dynamic binding of special variables. If you ever programmed QuickDraw for the Mac and tediously had to code up GetPort, SetPort, and then a SetPort back when finished drawing, just imagine having the ability simply to code:

(let grafport* (grafPort my-window)

...and get the whole save, re-bind, and restore taken care of for you. Does not come up a lot, but when it does this rocks (and Cells uses it for its core behavior of tracking dependencies). You see this sort of thing especially in cases exactly like the drawing GrafPort, something so fundamental that the lowest level functions will need it so it is either a global of some kind or every function in the API needs it as a parameter.

In the case of Cells, without dynamic binding almost every function in the application would need it. Not a pretty thought.

Caveat emptor: The following has been lightly tested with only one variable pseudo-dynamically bound. Bug reports welcome, but if the report is "Listen, dummy, Arc already has that."...well, I'll just be a normallispweeny for a week:

(mac withs* (parms . body)
(let uparms (map1 [cons (uniq) _] (pair parms))
`(do ,@(map1 (fn ((save curr val))
`(= ,save ,curr ,curr ,val)) uparms)
(do ,@body)
,@(map1 (fn ((save curr val))
`(= ,curr ,save)) uparms)))))

(= stak* (list 'top))

(def pstack (k)
(prs k stak*)(prn))

(pstack 'start)
(with* (stak* (cons 'me stak*))
(prt 'with-me stak*)
(pstack 'confirm-with-me))
(pstack 'bye-bye))

Output should be:

start (top)
with-me (me top)
confirm-with-me (me top)
bye-bye (top)

Enjoy. (And with* left as an exercise. :)

Thursday, February 14, 2008

Meaningless First Impressions of Arc

Almost posted on comp.lang.lisp:

> I think porting Cells is a very good test of Arc as a practical
> language (even at this early stage),

Yep, but it occurred to me that Mr. Graham would protest that transliterating a project however interesting is about as far as one can get from exploratory programming and he would be right. Hell, even someone working from a system spec still has to come up with the code.

> I appreciate you jumping in
> as the guinea pig.

I must confess, it is more like guinea frog (inside cll joke). But this dry material probably will not make me the next Imus in the Morning.

> I think it's much more informative than the "I
> wrote a wiki in 10 lines" that we've been seeing. What's your
> impression so far? Is there anything that really stands out, good or
> bad, while you've been working on the Cells port?

With 1% of the polls reporting, I miss my mud (the forty-six page index of Common Lisp the Language). No matter whether I reach for the #3 Torx driver or the articulating socket wrench extender I come up with the same vice-grip. I doubt I will ever get over this.

As for the brevity, that feels more like friction than grease, and I cannot even touch type.

But most of all I feel like I was right: it will be hard to tell until I have done a lot more Arc coding, because the brevity might feel like friction only because I have not gotten used to it. Especially fun is stuff that newly appeared in Arc 1 (click only to download) such as a hashtable lookup normally coded thus:
 (my-table sought-key)

...which can now be coded thus:

...and when the key is a literal we can rewrite:
  (oed 'peloria) as oed!peloria

This notation is generally applicable where one has a one-parameter function:
  abs.-42 -> 42

So the potential for code obfuscation is terrific. :) To get Cells to work I will have to write readers and writers, so you might see code like:
 (pressure my-boiler)

...which could as well be:

...and since the boiler will be a hashtable, one would normally read the hashtable like this:

My head is spinning. With Cells that would be a backdoor which would bypass the Cells mechanism entirely a la slot-value in Common Lisp. Bad client! Bad!

If Lisp is a local maximum in language design, all-sexprs-all-the-time might be the knife-edge ridge on which it stands. See we will.

Arc!Cells: Baby Steps

[This first article on doing Cells (see the "Cells Manifesto" entry in this blog) in Arc serves more to motivate the idea than anything else. In a nutshell, we want to be able to do something like this:

(= a (ci 3))
(= b (ci 4))
(defobserver c ()
(prs "Hey, C is now" new-value
"was" old-value))
(= c (c? (sqrt (+ (expt (cval a) 2)
(expt (cval b) 2)))))
Hey, C is now 5 was unbound
(cset a 6 b 8)
Hey, C is now 10 was 5

In other words, values are not just functions of values but also active bits of state which can have arbitrary observer logic bound to them.

In a subsequent (next?) blog I plan to easy up on the tutorial angle and just present a decent port of what I called Cells II, which was powerful but had theoretical holes closed in Cells3.

A close version of what follows is in CVS here (as cells-1.arc in case this link does not fly):


First a couple of utilities:

(def prt args
(apply prs args)

(mac prun (banner . forms)
`(do (prn ,banner)
(prn '(do ,@forms))

Let's start with the moral equivalent of a C++ member function, or at least I think that's what they call it. Something that looks like a stored data member or slot of an attribute of an object but is in fact implemented as a function of that object.

An example would be having a rectangle object with data members where one could store length and width and then have an area attribute implemented (in C++) as:

area = this.length * this.width;

Aside from saving a little memory, one gets a guarantee that the area will always be consistent with the length and width, which is not the case if one is writing code that says oh gosh I just changed the length I better go change the area.

As our 'application pushing down on the core' we'll use my favorite, a furnace boiler.

(= b* (obj outside-temp 72
on? [< _!outside-temp 50])))

No, the outside temp is not an attribute of a boiler, we're just keeping things in one table as a convenience until we get the ball rolling, later on we'll deal with multiple objects.

That anonymous function above boils down to:

If the outside temp is less than 50,
then turn on the boiler,
otherwise turn it off.

First, let's see if the rule works (not a big accomplishment)

(prt 'boiler b*!outside-temp (if (b*!on? b*) 'on 'off)))

-> boiler 72 off

Good, now change temp to 32 and see if the boiler comes on:

(= b*!outside-temp 32)
(prt 'boiler b*!outside-temp (if (b*!on? b*) 'on 'off)))

-> boiler 32 on

Super. Now let's hide the fact that on? is a function
behind a reader function:

(def on? (i) (i!on? i)))

...and ease inspection:

(def pr-boiler (b)
(prt 'boiler 'temp b*!outside-temp (if (on? b) 'on 'off)))

Test new slot reader, setting temp high enough this time
so that the boiler should go off:

(= b*!outside-temp 80)
(pr-boiler b*))

-> boiler temp 80 off

But we want more flexibility than having an attribute always defined by a function. Maybe we just want to store nil or t in on? and maintain it as usual, via assignment. Now on? can no longer be assumed to be a function. Fortunately we already have it behind a reader in our burgeoning little OO system, so we just need to enhance that (and get a redefinition warning):

(def on? (i)
(awhen i!on?
(if (isa it 'fn)
(it i)

Just test that our new accessor for on?:

(= b* (obj outside-temp -10
on? nil)) ;; we'll ignore the outside-temp for this test
(pr-boiler b*))

boiler temp -10 off

Now assign t to on?:

(= b*!on? t) ; We'll hide the assignment implementation later.
(pr-boiler b*))

boiler temp -10 on

Good. We will want all our attributes to work this way, so we may as well generalize the on? behavior now:

(def slot-value (i slot-name) ;; i is like self ala Smalltalk
(awhen i.slot-name
(if (isa it 'fn)
(it i)

(mac defslot (name)
`(def ,name (i) (slot-value i ',name)))

(defslot outside-temp)
(defslot on?)
(defslot inside-temp) ;; Let's start elaborating the model

(def pr-boiler (i)
(prt 'boiler
'outside-temp (outside-temp i)
(if (on? i) 'on 'off)
'inside-temp (inside-temp i)))

And test:

(= b* (obj outside-temp 20
on? nil
inside-temp [if (on? _)

boiler outside-temp 20 off inside-temp 20

Now let's bring back the automatic boiler:

(= b*!on? [< _!outside-temp 50]))

...and step the outside temperature up from freezing to torrid.

(loop (= b*!outside-temp 30)
(< b*!outside-temp 100)
(= b*!outside-temp (+ b*!outside-temp 10))
(pr-boiler b*)))

Looks like we need an air conditioner. And let's get more realistic about the model

(= outside* (obj temp 20))
(defslot temp)

(= furnace* (obj on? [< (temp outside*) 50]))
(= ac* (obj on? [> (temp outside*) 75])) ;; air conditioner
(= inside* [if (on? furnace*) 72
(on? ac*) 68
(temp outside*)])

(def dumpworld ()
(prt "outside" (temp outside*))
(prt "furnace" (if (on? furnace*) 'on 'off))
(prt "a/c" (if (on? ac*) 'on 'off))
(prt "inside" (temp inside*)))

Step temperature up from freezing to torrid, but with an air-conditioner:

(loop (= outside*!temp 30)
(< outside*!temp 100)
(= outside*!temp (+ outside*!temp 10))

Nice. We have built a working model that runs by itself given simple declarative rules, meaning we state the rules and an engine sees to it that the model runs. But we have a problem. Let's add a debug option to our slots:

(def slot-value (i slot-name (o debug))
(awhen i.slot-name
(if (isa it 'fn)
(when debug (prt "Running the rule for slot" slot-name))
(let result (it i)
(when debug (prt "...slot" slot-name "is" result))

(mac defslot (name (o debug))
`(def ,name (i) (slot-value i ',name ,debug)))

(defslot on? t)

Same test tracing the on? slots

(loop (= outside*!temp 30)
(< outside*!temp 100)
(= outside*!temp (+ outside*!temp 10))

Looks OK, but watch what happens even if nothing is going on:


Ah, the downside of the functional paradigm: the code runs and runs. For simple functions that is no problem, but if we build an entire application this way things bog down (we learned the usual way).

What we need to cache the result of a calculation and then return the cached result when queried a second time. But then there is a new problem: when do we refresh the cache? Answer: when we have to in order to stay current with the changing world arounds us, more plainly when one of the values used in a calculation changes.

So we need to keep track of who uses whom in their calculations, and when one value changes notify its users that they need to recalculate.


Wednesday, February 13, 2008

Maybe I Was Too Hard On Sohail

Background: Sohail tried to contradict an article of mine on comp.lang.lisp in which I compared Arc unfavorably to Common Lisp with some code proving CL was almost as good as Arc. Think about that for a second. I ripped him a new one for poor reading comprehension and guessed correctly (he confirmed) that his understanding was blinded by another mistake, misconstruing my impatience with Arc's detractors as meaning somehow a preference of Arc over CL.

Great Lisp-NYC chug-a-lug last night. But... everyone who came up to me to talk about Arc said, "So you like Arc, eh?" Every last one. And most of those who did are smarter than I.

Each time I responded, "No, I never said that. I just rag on people for ragging on Arc without trying it."

It gets worse. Half the people responded they were in fact aware that I had merely ragged on naysayers for their unreasoned opining. And they still thought I liked Arc.

Meanwhile over on Reddit someone wants to know if I am gay because I whined publicly about Turing being persecuted for being gay. Sure and I am also black, Comanche, Jewish, Palestinian, Mexican, an Iraqi civilian, and I died in the plane that hit the South Tower of the WTC.

We all know everyone sees the world differently. What I realized last night is that the differences go beyond the differences in the observers themselves, their different tastes, upbringings, cultures, and DNA. People just plain get things wrong.

We get things wrong all the time. As a matter of course. Our world views form a scatter plot around the bullseye of reality.

Not because of lack of intellect or through lack of attention, though those explain the worst misses. Just because the brain registers new information using a sloppy indexing scheme that settles for bad matches because they are the closest matches and because those matches are affected by what we had for lunch.

We need a new song. Maybe "I say potato, you say Hunh? More day-glo?".

One of my favorite lines to deliver upon completing a task: "That's close enough for government work." I think the brain's ethic is "That's close enough for this bozo carrying me around."

Super. Billions of us walking around trying to deal with each other while each of us is working from more or less faulty copies of reality. Explains a lot.

I realize now I never bought having conflict and injustice explained as the natural consequence of different tastes and life experiences. Nope. We are all just more or less wrong about more or less everything, each of us in different ways, and so no, Rodney, we can never just get along. We will always be in conflict because we will never agree because we are all carrying around different broken realities and broken realities will clash more violently than realities varying merely by taste.

Why do I find this so comforting?

Monday, February 11, 2008

A Tall Ship and a Star to Steer Her By

A few things collided yesterday. Background: I slammed Scheme and academia for the star by which they chose to steer Scheme's design, namely purity and a small specification. Yep, you heard me right. A design goal was a small spec, nothing to do with making programming easier. From the FAQ:
Advocates of Scheme often find it amusing that the Scheme standard is shorter than the index to CLtL2.
Amuse this. Anyway, after that I got yelled at for being mean to Scheme and academia. Hey, I thought that was what blogs were for.

Now the other thing that happened. Paul Graham released a new Lisp called Arc for which his guiding star is the brevity of the *application code* written in Arc. (He also likes a language to be small but I cannot be mean to him because he once was nice enough to give me a tip on how my RoboCup team could play better defense.)

Mr. Graham further mentioned that Arc development includes a Web app library because he wants there to be a real-world application "pushing down" on the core language design. This reminds me of my cherished Cells library whose twelve-year evolution has always been pushed by application development mostly because I am just a simple application programmer not smart enough to come up with fancy theories in the abstract so I just use things till they break and then fix them just well enough to get them working again. But I digress.

The idea of having an application shape Arc went down well -- no one whined about it and on Usenet that is tantamount to a standing ovation -- but Mr. Graham's choice of brevity as a pole star in navigating his Arc led to a raucous of blogwar and I still had that defender of academia challenging me with "Hey, McCarthy was an academic". Things got ugly, the lights went out, I took a chair over the head, and here is what we (I) decided.

First principles are Good Things. In Lisp, every form returns a value. That first principle works great. This despite Tilton's Law of Programming:

All X all the time is the root of all evil.

Examples: Prolog where it is all logic and unification and Smalltalk and Java where it is all objects. So how did "every form returns a value" get past Tilton's Law? Beats me, must be a Deep Truth somewhere about the power of the functional paradigm which is not all that hard to understand if one has worked on even a small amount of stateful code. At any rate, we will not reject out of hand the idea of one idea shaping a language, but we do see that we gots to pick the right idea.

Next question: are we OK with shorter being better, all other things being equal? Yes, that is correct. Note that reductio adsurbum counterexamples such as APL and K and Perl do not work because in those cases the shorterness takes us out of the space of all other things being equal. Changing Lisp's lambda to Arc's fn makes it shorter without making it obscurer, but changing lambda to a hieroglyphic would.

Next issue: the shorter specs of Scheme and Arc. Would you walk up to a working programmer and start jumping up and down about this amazing new language guess what it's spec fits on one page!!! The working programmer would worry about you. Yeah it makes the compiler easier to write but do we working programmers tell you compiler writers our problems?

Small specs. Pfft. Ever walk into an auto garage and see one of those huge red chests filled with drawer after drawer of tools? Those chests are the seven years of med school for a mechanic. We civilians might think it an overwhelming selection but the mechanic knows it by heart, even those tools used like every two months.

Mr. Graham talked at one point about a language being small enough to keep in one's head. I think the mistake there is the assessment of how big that small can be. People using something a lot (and I hope we are talking about designing a language for someone using it every day) can keep quite a bit in their heads. Meanwhile, hey, these are computers, a good IDE lets us zero in on documentation with a minimum of keystrokes to get the details of a keyword we forget, including zero keystrokes cuz as I finish typing the name of a function my IDE status bar shows the expected parameter list.

On the flip side of big, a scanty starting tool chest means everyone either reinvents the missing bits or grabs one or another incompatible library off the shelf which is why Scheme programmers cannot share their work. Some of them point to specific implementations such as DrScheme and say Hey, it has everything! in which case what was the point of the small standard? You now have a big language unlike anyone else's. Juusst peachy.

All that has been achieved with a small starting standard is making my code incompatible with someone else using some other big Scheme implementation. Lisp went through that without trying to because it too started small, insanely small, but then they cured the natural outcome (a fragmented community) when that threatened its DARPA contracts by creating Common Lisp the standard and everyone saluted and conformed. They still lost the DARPA contracts but those will be back eventually because the standard now has the Common Lisp community all pulling in the same direction: I can use Other People's Code and they can use mine.

The subtext here is that CL may be a big language but I use all of it (except series, but give me time, it has only been thirteen years). One of the classic auto mechanic sayings is that any given task is easy when you have the right tool, and all of us shade tree mechanics forced into retirement by ever more complex automobiles remember how great were those moments when someone handed us the right tool and we were able to put down the Vice-Grips.

Brevity of application code? Great! Brevity of spec, not so much. Scheme needs to close up shop because if they fix what is wrong with it (hygienic macros, NIL not being false, a tiny standard) they end up with CL.

Arc is differentiated by its use of syntax to yield shorter applications, so it can stay, but it does need to add some drawers to the tool chest. And academia needs to start writing applications at the same time they are having bright ideas so they stop designing cool things that happen to be useless for programming. More on constraints later.

What the Hell is a Fortune Cookie File Anyway?

Just to get strangers up to speed quickly on your correspondent, here is what other people say I said, according to their sigs:

I think it would be harder for a good programmer to change editors than to change languages.
Parentheses? What parentheses? I haven't noticed any parentheses
since my first month of Lisp programming. I like to ask people who
complain about parentheses in Lisp if they are bothered by all the
spaces between words in a newspaper...
Lisp gives you a kazillion ways to solve a problem.
(1- kazillion) of them are wrong.
My dream of a Cells consulting business is fading as user after user
turns out to be hindered not at all by my deliberate withholding
of documentation.
Lisp nearing the age of fifty is the most modern language out there. GC, dynamic, reflective, the best OO model extant including GFs, procedural macros, and the only thing old-fashioned about it is that it is compiled and fast.
Eight years to do TeX? How smart can [Knuth] be? He should have used Lisp.
[This one apparently stopped the quoter from trying Lisp. The quoter suspected irony but finally decided I was serious.]
Yeah, I'm a gifted guru. Since you called me that, I guess I'll talk to you a little bit.
There are no average Lisp programmers. We are the Priesthood. Offerings of incense or cash will do.
I suppose if what you said had any merit it would occasion hostility.
Yeah, what the hell can anyone accomplish with beauty and power? (in response to a linked blog entry saying Lisp was beautiful and powerful but unuseable)
No, you are an asshole doing his best to despoil c.l.l, and I am an
asshole doing his best to hose out your crap.
Liars need good memories, trolls need NG readers with bad ones.
We all need early warning systems for "they might have heard this a million times before". I once destroyed any nano-chance I had with a stunning, taller woman by asking her how tall she was.
"Six foot two," she replied. "How short are you?"
Programmers who lock onto a design decision and cling to it in the face of contradictory new information -- well, that's almost everyone in my experience, so I better not say what I think of them or people will start saying bad things about me on c.l.l.
This reminds me of the NYC cabby who accepted a fare to Chicago. When they got there and could not find the friend who was supposed to pay the fare the cabby just laughed and said he should have known.
> Actually, I believe that Aikido, Jazz and Lisp are different appearances of the same thing.
Yes, the Tao. /Everything/ is a different appearance of the tao.
"Ken, I went to the library and read up on Buddhism, and believe me, you are no Buddhist."
-- Kenny's Mom
That absolutely terrifies the herd-following, lockstep-marching, mainstream-saluting cowards who obediently dash out to scoop up books on The Latest Thing. They learn and use atrocities like Java, C++, XML, and even Python for the security it gives them and then sit there slaving away miserably, tediously, joylessly paying off mortgages and supporting ungrateful teenagers who despise them, only to look out the double-sealed thermo-pane windows of their central-heated, sound-proofed, dead-bolted, suffocating little nests into the howling gale thinking "what do they know that I do not know?" when they see us under a lean-to hunched over our laptops to shield them from the rain laughing our asses off as we write great code between bong hits.... what was the question?
Shut up! (That last phrase has four or more syllables if pronounced as intended.)
Nonsense. You'll be using it for the GUI, not protein-folding.
(in response to a comment that LTk was slow)
Continuations certainly are clever, but if we learned anything from the rejection of the cover art for "Smell the Glove", it is that "there is a fine line between stupid... and clever".
Ah, there's no place like academia for dispassionate, intellectually honest discussion of new ideas on their merits. Thank god for tenure giving your bold antagonist the protection they needed to shout down your iconoclastic..... hang on...
Whoever objected must be in my killfile, ...
From memory (but I think I have it right): "But Jesus said, Suffer captured variables, and forbid them not to come unto thine macro bodies, for of such are DSLs made." Can I get an Amen?
Awareness of defect is the first step to recovery.
You made a bad analogy (there are no good ones, but you found a new low) ...
Yes, it is true that Kent Pitman was raised by a closet full of Lisp Machines, but the exception only proves the rule. (in a postscript after positing that computer languages are not learned in infancy)
I suggest you try bartender's school to support yourself, start programming for fun again.
(responding to a comment that 98% of anything to do
with computers was not interesting code)
I could add four lanes to my carpal tunnel and still not write all the code I am dying to write.
Neutrality? I want to bury other languages, not have a gateway to them.
Ken: "Cute puppy. Did you get it for companionship or to pick up chicks?"
Simon: "Hunh? My puppy /always/ gives me companionship."
(on how he was understood by a native English speaker)
> Yeah. In case you guys didn't quite get it, this particular site
> targets (among other things) the Turkish lisp effort. Yours truly and
> others have also been accused of being destructive to Turkish youth
They want you to copy them first?
You can lead a horse away from water, but if it wants to drink you
better have a big frickin stun gun. No, I have no idea what I just said.
PWUIAHAHAHAHA. This is Lisp. We never use anyone else's code. Hell, most of us won't even use Lisp, insist on creating our own with C.
OK, who is going to head over to c.l.python and suggest parentheses instead of whitespace? It could be a pretty funny post. "Hey, guys! I was looking at Lisp, had this great idea...keep an open mind!"
Educational software itself is now an acknowledged joke precisely because of people who try to foist on others "Oh, look, we used a computer, it must be in-frickin-credible".
Horse. Cart. Please note order.
Start this thread again. Change the subject to "Lisp Sucks! Molasses is faster!!" and post the code and some timings and the whole community will be working for you for free.
We live here. Every week we see noobs stumble in the door, trip over the upturned rug, bang their heads on the too-low hanging lamp, and then ease into Lisp pretty easily after being pointed to Lisp-aware editors, Slime, PCL, etc etc directed by living Lisp Gods, dynamic and interactive, not some two-dimensional billboard of an FAQ that just raises more questions.
Are you looking for that "friends" stuff from C++ (if I have that right, unless it was Java ). This is Lisp, we just shoot from the hip.
You people do not listen to me on AllegroCL, you do not listen to me on Cells, why am I not surprised you do not listen to me on the tao?
Two prehensile toes up!
-- reporting on behalf of his development team their review of Peter Seibel's "Practical Common Lisp"
Pearls. Swine. Please note order.
> I think it's a fairly large assumption that this problem is soluble...
If not work on it should be suspended.
This will be a commercial "Hello World" app that displays "Hello", asks you to login or buy, then displays "world". More soon.
> Callbacks are a form of continuation.
Yes, in the same sense that a shoe is a form of aircraft carrier.
Lisp is no longer the crazy aunt in the attic, she is now out in the front parlor where her admirers come to pay homage and learn at her feet.
> fred gilham wrote:
>> kenny tilton wrote:
>>> fred gilham wrote:
>>> Become a celebrity like Kenny Tilton.
>> I am a simple Lisp programmer.
>> --
>> "I am a simple Buddhist monk. "
>> -- Tenzin Gyatso, the Fourteenth Dalai Lama
> On top of everything else, humble too! :-)

My Road to Lisp

I, Kenny Tilton, do solemnly offer these my responses to The Road to Lisp Survey:

When did you first try Lisp seriously?

1995. My initial interest in programming when I went shopping for my first computer in 1977 was artificial intelligence so of course I heard about Lisp,and when I ran across a Lisp 1.5 Manual in some geek shop I snagged it. But I could not make any sense out of it.

Fast forward five years and now I am a VAX/VMS consultant doing business apps in tall buildings, and while reading some geek rag I am stunned to see Lisp listed as a 4GL based on the 4GL definition of being an order of magnitude more productive than a 3GL. This was strange because 4GLs generally created the illusion of greater productivity with screen builders and a super high level hence inflexible language with database stuff done for you and I knew Lisp was not like that. I filed this datapoint away and went on with my life.

Five years later I decide to write a program which could check intermediate steps of arbitrary first-year high school algebra problems as part of a math tutorial. I see Microsoft (!) offers a Logo, and I remember the 4GL datapoint and decide what the hell let's learn a new language at the same time.

I loved it and went amazingly far with Logo on the tutorial before realizing it would have to be ported to C (a most unpleasant exercise) and it was another ten years before I found my way out of the desert and back to Lisp.

Which Lisp did you try?

Common Lisp. Digitool's MCL, to be specific.

What led you to try Lisp?

I was looking for A Better Way than C for version two of my algebra tutorial. I knew I wanted OO because I could see in my C code that I was using structs in an OO kinda way. I also knew I wanted a dynamic, interactive development environment and it had to run on the Mac where I made most of my sales.

The first thing I tried was Stoney Ballard's Component Workshop, a brave attempt at a dynamic C++ which never even got to "Hello world" before Stoney gave up. Then I got Symantec C++ (I had used it when it was Michael Kahl's Think C) and freaked out when I saw incremental linking was gone and every edit-run cycle now included a twenty second link from scratch. And I was just appalled by C++ the language.

Next up was SmalltalkAgents from Quasar Knowledge Systems. QKS kept saying how great they were and how great they were going to be. Perhaps, but not by crashing my Mac every five minutes.

I then announced on Compuserve's MACDEV forum that I was giving up and was going to use C++,when a kind soul from Cambridge, Mass suggested I look at MCL. He said it was compiled, fast, mature, object-oriented and a few other things.

Well the amazing thing is that I had been skipping MCL ads in the Apple Developer association catalog for months because of my earlier experience with Logo. I had no idea of the progress in Lisp compilers.

I also had come incredibly close when I got the pre-alpha Dylan CD from Apple Computer and played with that. Dylan was being developed for Apple by Digitool and it ran atop (wait for it) Macintosh Common Lisp! Who knew?

But having read the message from Cambridge I promptly ordered a copy of MCL. It came a few days later and just while assembling the manual pages into a binder I concluded I had found The One. I gave the install CD to my two developers, told them to dump QKS, then ordered two more copies to stay honest.

The next few weeks involved everyone taking turns running to each others desk to show them neat new features we had just discovered and I have never looked back.

If you were trying Lisp out of unhappiness with another language, what was it and what did you not like about it, or what about Lisp were you hoping to find different?

I wanted a dynamic development modality, no linker especially. And an end to pointers and dereferencing and manual memory management. ie, I was looking for a better way than C and when I looked at C++ I did not find it.

How far have you gotten in your study of Lisp?

Well, it's been thirteen years, so as an application developer I am fluent.

What do you think of Lisp so far?

Perfect. Whatever it does not do, macros let me coax from CL. Being able to restart from a backtrace after hours of debugging or while trying twenty things a minute apart to get something working is an enormous win. CLOS is unspeakably powerful. A simple thing like special variables is magnificent when you really need them. Of course garbage collection is a stupendous win. The speed is crucial. Multiple inheritance and multi-methods are vital.

One thing a lot of newbies experience as did I is that when I go to find out how some function works it always turns out to work just the way I happen at that time to expect or want or need it to work. Clearly Common Lisp is the product of a long history of refinement by good engineers with a strong ethic of doing things well.

And if you have to know, Lawdy, I never want to edit without parentheses again. When reworking code the code tree is perfect for moving chunks of semantics around. And the autoindentation is a significant time saver. I refactor a lot so a lot of time in other languages goes into tediously realigning code.

The Cells Manifesto

[We may as well get this out of the way, an explanation of my pet project Cells, the kind of thing I'll be sitting in a rocking chair twenty years from now mumbling how the CIA stole it from me but they don't have the latest version I have that in a floppy disk here in my shirt pocket.]

In the text that follows, [xxx] signifies a footnote named "xxx" and listed alphabetically at the end.

Cells is a mature, stable extension to CLOS[impl] allowing one to create classes whose instances can have slot values determined by instance-specific formulas. It is useful for any application involving an interesting amount of long-lived state and a stream of unpredictable inputs. Two examples are any GUI-based application and a RoboCup client (trying to simulate a soccer player given a stream of sensory data fed it by the game server).

For example, in a text editor application we might have (condensed, and with the symbol ".w." macroexpanding to code that returns the relevant window)):

 (make-instance 'menu-item
:label "Cut"
:enabled (c? (bwhen (f (focus .w.))
                       (and (typep f 'text-widget)
     (selection-range f)))))

Translated, the enabled state of the Cut menu item follows whether or not the user is focused on a text-edit widget and whether they have in fact selected a range of text, the trick being that nil is treated as false by (decent) Lisp dialects.

Meanwhile, the selection-range rule might be:
(let (start)
 (c? (if (mouse-down? .w.)
         (bwhen (c (mouse-pos-to-char self (mouse-pos .w.)))
           (if start
               (list start c)
             (setf start c)))
       (setf start nil))))

Now the only imperative code needed is some glue reading the OS event loop onverting raw mouse down and mouse move events into window attributes such as mouse-down? and mouse-pos. The desired functionality is achieved by declarative rules which (like selection-range above) are entirely responsible for deciding the selection range.

A final trick comes from slot observers. Suppose we are thinly wrapping a C GUI and need to do something in the C library to actually make menu items available or not. It might look something like this:
(defobserver enabled ((self menu-item) new-value old-value old-value-bound?)
    (menu-item-set (c-ptr self) (if new-value 1 0)))

ie, Some model attributes must be propagated outside the model as they change, and observers are callbacks we can provide to handle change.

As a child I watched my father toil at home for hours over paper spreadsheets with pencil and slide rule. After he changed one value, he had to propagate that change to other cells by first remembering which other ones included the changed cell in their computation. Then he had to do the calculations for those, erase, enter...and then repeat that process to propagate those changes in a cascade across the paper.

VisiCalc let my father take the formula he had in mind and put it into (declare it to) the electronic spreadsheet. Then VisiCalc could do the tedious work: recalculating, knowing what to recalculate, and knowing in what order to recalculate.

Cells do for programmers what electronic spreadsheets did for my father. Without Cells, CLOS slots are like cells of a paper spreadsheet. A single key-down event can cause a cascade of change throughout an application. The programmer has to arrange for it all to happen, all in the right order: delete any selected text, insert the new character, re-wrap the text, update the undo mechanism, revisit the menu statuses ("Cut" is no longer enabled), update the scroll bars, possibly scroll the window, flag the file as unsaved...

Here is a real-world case study:

"The last company I worked with made a product that was a control unit for some mechanical devices, presenting both sensor readings coming in from those devices and an interface to program the devices. Consider it like a very sophisticated microwave oven, perhaps with a temperature probe.

"The UI code was a frighteningly complex rat's nest. Input data arriving from the sensors changed certain state values, which caused the display to update, but the system state also changed, and rules had to be evaluated, the outcome of which might be tuning to the running job or warning messages presented to the user, and in the meantime the user may be adjusting the running job. I'm sure there are even more interactions I'm leaving out.

"There was no "large idea" in this code to organize these dependencies or orchestrate the data flow. The individual facilities were well-formed enough: "message" input and output, GUI widgets and forms, real-world entities modeled as entities in the code. However, the connections between these things were ad-hoc and not formalized. Every change to the system would provoke defects, and the failure usually involved not propagating some event, propagating it at the wrong time, or propagating it to the wrong recipients."
--- Steven Harris, on comp.lang.lisp

What Mr. Harris describes is what Fred Brooks [bullet] said was an essential property of software development, meaning by essential that there was no way around it, and thus his prediction that a software silver bullet was in principle impossible.

Which brings us to Cells. See also [axiom] Phillip Eby's developing axiomatic definition he is developing in support of Ryan Forseth's SoC project.

DEFMODEL and Slot types
Classes, some of whose slots may be mediated by Cells, are defined by DEFMODEL, which is exactly like DEFCLASS but adds support for two slot definition options, :cell and :unchanged-if. Classes defined by DEFMODEL can inherit from normal CLOS classes.

New slot definition options
:cell {nil | t | :ephemeral}

:cell is optional. The default is ":cell t", meaning the Cells engine will manage the slot to give it the spreadsheet-like characteristics. Specifying NIL signifies that this slot is entirely outside any handling by the Cells engine; it is just a plain CLOS slot.

This next bit will not make sense until we have explained propagation of state change, but specifying :ephemeral causes the Cells engine to reset the apparent slot value to NIL immediately and only after fully propagating any value assumed by the slot, either by assignment to an input Cell (the vastly more common case) or by a rule calculation.

Ephemeral cells are necessary to correctly model events in the otherwise steady-state spreadsheet paradigm.


Specifying :unchanged-if is optional. [Come to think of it, it should be an error to specify both :cell nil and :unchanged-if.] If specified, the named function is a predicate of two arguments, the new and old value in that order. The predicate determines if a subsequent slot value (either computed or assigned to an input) is unchanged in the sense that no propagation is necessary, either to dependent ruled cells or (getting ahead of ourselves again) "on change" observers.
The default unchanged test is EQL.

Cell types
The Cells library allows the programmer to specify at make-instance time that a Cell slot of an instance be mediated for the life of that instance by one of:

-- a so-called "input" Cell;
-- a "ruled" Cell; or
-- no Cell at all.

Note that different instances of the same class may do different things Cells-wise with the same slot. One label widget may have a fixed width of 42 and text "Hi, Mom!", where another might have an input Cell mediating the text (so edit logic can assign new values as the user types) and a rule mediating the width so the widget can have a minimum width of 42(so it does not disappear altogether) yet grow based on text length and relevant font metrics to always leave room for one more character (if the GUI design calls for that).

To summarize, the class specification supplied with DEFMODEL specifies whether a slot can /ever/ be managed by the Cells engine. For those that can, at and only at instance initialization time different instances can have different Cell types and rules specified to mediate the same slot.

Input Cells
A slot mediated by an input Cell may be assigned new values at runtime. These are how Cell-based models get data from the world outside the model -- it cannot be rules all the way down. Typically, these input assignements are made by code polling OS events via some GetNextEvent API call, or by callbacks registered with an event system such as win32 WindowProc functions. Other code may poll sockets or serial inputs from an external device.

Ruled Cells
Ruled Cells come with an instance-specific rule in the form of an anonymous function of two variables, the instance owning the slot and the prior value (if any) computed by the rule. These rules consist of arbitrarily complex Common Lisp code, and are invoked immediately after instance initialization (but see the next bit on lazy cells).

When a rule runs, any dynamic read (either expressly in the rule source or during the execution of some function invoked by the rule) of a slot of any instance mediated by a Cell of any type establishes a runtime dependency of the ruled cell on the slot of the instance that was read. Note then that thanks to code branching, dependencies can vary after every rule invocation.

Lazy Ruled Cells
Laziness is cell-specific, applies only to ruled cells, and comes in four varieties:

:once-asked -- this will get evaluated and "observed" on initialization, but then not get reevaluated immediately if dependencies change, rather only when read by application code.

:until-asked -- this does not get evaluated/observed until read by application code, but then it becomes un-lazy, eagerly reevaluated as soon as any dependency changes (not waiting until asked).

:always -- not evaluated/observed until read, and not reevaluated until read after a dependency changes.

When application code assigns a new value to an input Cell (a quick way of saying an instance slot mediated by an input Cell) -- typically by code polling OS events or a socket or an input device -- a cascade of recalculation ensues to bring direct and indirect ruled dependents current with the new value assigned to the input Cell.

No Cell at All
Because of all that, it is an error to assign a new value to a slot of an instance not mediated by any Cell. The Cells engine can do a handy optimization by treating such slots as constants and not creating dependencies when ruled Cells read these. But then we cannot let these Cells vary and still guarantee data integrity, because we no longer know who else to update in light of such variation. The optimization, by the way, extends to eliminating ruled Cells which, after any computation, end up not depending on any other cell.

Again, note that this is different from specifying ":cell nil" for some slot. Here, the Cells engine has been told to manage some slot, but for some instance the slot has been authored to bear some value for the lifetime of that instance.

To allow the emergent animated data model to operate usefully on the world outside the model--if only to update the screen--programmers may specify so-called observer callbacks dispatched according to: slot name, instance, new value, old value, and whether the old value actually existed (false only on the first go). Observers are inherited according to the rules of CLOS class inheritance. If multiple primary observer methods apply because of inheritance, they all get run, most specific last.

ie, observers are a GF with PROGN method combination.

Observers get called in two circumstances: as part of Model object initialization, in a processing step just after CLOS instance initialization, and when a slot changes value. Any observer of a Cell slot is guaranteed to be called at least once during intialization even if a cell slot is bound to a constant or if it is an input or ruled Cell that never changes value.

It is legal for observer code to assign to input Cells, but (a) special syntax is required to defer execution until the observed state change has fully propagated; and (b) doing so compromises the declarative quality of an application -- one can no longer look to one rule to see how a slot (in this case the input slot being assigned by the observer) gets its value. A reasonable usage might be one with a cycle, where changing slot A requires a change to slot B, and changing slot B requires a change to slot A, such as the scroll thumb position and the amount a document has been scrolled.

Finally, to make it possible for such a declarative model to talk intelligibly to imperative systems such as Tcl/Tk which sometimes requires a precise sequence of commands for something to work at all, a mechanism exists by which client code can (a) queue tasks for execution after a data change has fully propagated and (b) process those tasks with a client-supplied handler. Tasks are queued with arbitrary keying data which can be used by the handler to sort or compress the queued tasks.

Data Integrity
When application code assigns to some input cell X, the Cells engine guarantees:

- recomputation exactly once of all and only state affected by the change to X, directly or indirectly through some intermediate datapoint. note that if A depends on B, and B depends on X, when B gets recalculated it may come up with the same value as before. In this case A is not considered to have been affected by the change to X and will not be recomputed.

- recomputations, when they read other datapoints, must see only values current with the new value of X. Example: if A depends on B and X, and B depends on X, when X changes and A reads B and X to compute a new value, B must return a value recomputed from the new value of X.

- similarly, client observer callbacks must see only values current with the new value of X; and

- a corollary: should a client observer SETF a datapoint Y, all the above must happen with values current with not just X, but also with the value of Y /prior/ to the change to Y.

- Deferred "client" code must see only values current with X and not any values current with some subsequent change to Y queued by an observer

Program state guaranteed to be self-consistent, without programmer effort. Dependencies are identified by the engine, and change propagation happens automatically.

Greater object re-use. Slots of instances can be authored with rules, not just literal values. In a sense, we get greater reuse by allowing instances to override slot derivations instance by instance. But not slot expressions, which are still class-oriented. By this I mean the observers expressing changes in value are dispatched by the class of the instance and so are not instance-specific. (Such a thing has been suggested, however.) Another strong bit of class-orientation comes from the fact that code reading slot X of some instance Y obviously does so without knowing how the returned value was derived. It knows only that the slot is named X, and will do things with that value assuming only that it has the X attribute of the instance Y. So again: the derivation of a slot value is potentially instance-oriented under Cells, but its expression or manifestation is still class-oriented.

Natural decomposition of overall application complexity into so many simple rules and slot observers. Let's return for a moment to VisiCalc and its descendants. In even the most complex financial spreadsheet model, no one cell rule accesses more than a relatively few other spreadsheet cells (counting a row or column range as one reference). Yet the complex model emerges. All the work of tracking dependencies is handled by the spreadsheet software, which requires no special declaration by the modeller. They simply write the Cell rule. In writing the rule, they are concerned only with the derivation of one datapoint from a population of other datapoints. No effort goes into arranging for the rule to get run at the right time, and certainly no energy is spent worrying about what other cells might be using the authored cell. That cell has certain semantics -- "account balance", perhaps -- and the modeller need only worry about writing a correct, static computation of those semantics.

Same with Cells. :) The only difference is that VisiCalc has one "observer" requirement for all cells: update the screen. In Cells applications, a significant amount of application functionality -- indeed, all its outputs -- end up in cell observers. But as discussed above, this additional burden falls only on the class designer when they decide to add a slot to a class. As instances are created and different rules specified for different slots to achieve custom behavior, the effort is the same as for the VisiCalc user.

Model Building
Everything above could describe one instance of one class defined by DEFMODEL. A real application has multiple instances of multiple classes. So...

-- cells can depend on other cells from any other instance. Since a rule gets passed only "self", Cell users need something like the Family class included with the Cells package effectively to turn a collection of instances into a network searchable by name or type.

-- The overall model population must be maintainable by Cell slots such as the "kids" slot of the Family class. The burden here is on the Cells engine to allow one cell of one child to ask for the value of a cell of another child and vice versa (with different Cells), when both children are the product of the same rule, or different rules when "cousins" are exchanging information. So we must gracefully traverse the parent/kids tree dispatching kids rules just in time to produce the other instance sought.

-- kid-slotting: used almost exclusively so far for orderly GUI layout, a parent must be able to specify rules for specific slots of kids. Example: a "stack" class wants to provide rules for child geometry specifying left, right, or centered alignment and vertical stacking (with optional spacing) one below the other. The idea is that we want to author classes of what might be GUI subcomponents without worrying about how they will be arranged in some container.

-- finalization: when an instance appears in the "old kids" but not in the "new kids", a Cells engine may need to arrange for all Cells to "unsubscribe" from their dependents. Cells takes care of that if one calls "not-to-be" on an instance.

Suggested Applications

Any application that must maintain an interesting, long-lived data model incorporating a stream of unpredictable data. Two examples: any GUI application and a RoboCup soccer client.

An application needing to shadow data between two systems. Examples: a Lisp GUI imlemented by thinly wrapping a C GUI library, where Lisp-land activity must be propagated to the C GUI, and C GUI events must propagate to Lisp-land. See the Cells-Gtk or Celtk projects. Also, a persistent CLOS implementation that must echo CLOS instance data into, say, SQL tables.

Prior/Concurrent Art (in increasing order of priorness (age))

[Note: everywhere we look these days we see dataflow aka reactive aka FRP, so once intended to persuade of relevance this now just documents history.]

Functional reactive programming
This looks to be the most active, current, and vibrant subset of folks working on this sort of stuff. Links:

Hoplon/Javelin: Very similar syntax, but it works by "lifting" so lotsa deficits.

FlapJax (FRP-powered web apps)

FrTime (scheme FRP implementation, no great links)

Adobe Adam, originally developed only to manage complex GUIs. [Adam]

COSI, a class-based Cells-alike used at STSCI in software used to
schedule Hubble telescope viewing time. [COSI]

Programming with AgentsMike Travers covers much the same territory exploring the agent-based programming metaphor:

Garnet's KR:
Also written in Lisp. Cells looks much like KR, though Cells was developed in ignorance of KR (or any other prior art). KR has an astonishing number of backdoors to its constraint engine, none of which have turned out to be necessary for Cells.

The entire constraint programming field, beginning I guess with Guy Steele's
PhD Thesis in which he develops a constraint programming language or two:

Sutherland, I. Sketchpad: A Man Machine Graphical Communication System. PhD thesis, MIT, 1963. Steele himself cites Sketchpad as inexplicably unappreciated prior art to his Constraints system.

See also:

  • The spreadsheet paradigm:
  • The dataflow paradigm:
  • Frame-based programming
  • Definitive-programming


-- Jack Unrue, comp.lang.lisp
"Cells provides the plumbing for data dependency management which every non-trivial program must have; a developer using Cells can focus on computing program state and reacting to state changes, leaving Cells to worry about how that state is propagated. Cells does this by enabling a declarative mechanism built via an extension to CLOS, and hence achieves its goal in a way that meshes well with with typical Common Lisp programming style."

-- Bill Clementson,
"Kenny Tilton has been talking about his Cells implementation on comp.lang.lisp for some time but I've only just had a look at it over the past few evenings. It's actually pretty neat. Kenny describes Cells as, conceptually, analogous to a spreadsheet cell (e.g. -- something in which you can put a value or a formula and have it updated automatically based on changes in other "cell" values). Another way of saying this might be that Cells allows you to define classes whose slots can be dynamically (and automatically) updated and for which standard observers can be defined that react to changes in those slots."

-- "What is Cells?", Cells-GTk FAQ,
"If you are at all familiar with developing moderately complex software that
is operated through a GUI, then you have probably learned this lesson: Keeping what is presented through the GUI in-sync with what the user is allowed to do, and in-sync with the computational state of the program is often tedious, complicated work. .... Cells-GTK helps with these tasks by providing an abstraction over the details; each of the tasks just listed can be controlled by (a) formula that specify the value of attributes of graphic features in the part-subpart declaration (that declaration is called 'defpart' in cells-gtk); and, (b) formula that specify the value of CLOS slots."

-- Phillip Eby, PyCells and, "What I discovered is quite cool. The Cells system *automatically discovers* dynamic dependencies, without having to explicitly specify that X depends on Y, as long as X and Y are both implemented using cell objects. The system knows when you are computing a value for X, and registers the fact that Y was read during this computation, thus allowing it to automatically invalidate the X calculation if Y changes.... Aside from the automatic dependency detection, the cells system has another trick that is able to significantly reduce the complexity of event cascades, similar to what I was trying (but failing) to do using the "scheduled  thread" concept in Specifically, the cells system understands how to make event-based updates orderly and deterministic, in a way that cannot. It effectively divides time into "propagation" and "non-propagation" states. Instead of simply making callbacks whenever a computed value changes, the system makes orderly updates by queueing invalidated cells for updating. Also, if you write code that sets a new value imperatively (as opposed to it being pulled declaratively), the actual set operation is deferred until all computed cells are up-to-date with the current state of the universe."


-- Josh Marchan, internal company email:
"some obscure technology that only theoretically benefits us.... I'm not even sure what the advantage here would be."

-- Peter Seibel, comp.lang.lisp:
"I couldn't find anything that explained what [Cells] was and why I should care."

-- Alan Crowe, comp.lang.lisp:
"Further confession: I'm bluffing. I've grasped that Cells is interesting, but I haven't downloaded it yet, and I haven't checked out how it works or what /exactly/ it does."


[Adam] "Adam is a modeling engine and declarative language for describing constraints and relationships on a collection of values, typically the parameters to an application command. When bound to a human interface (HI) Adam provides
the logic that controls the HI behavior. Adam is similar in concept to a spreadsheet or a forms manager. Values are set and dependent values are recalculated. Adam provides facilities to resolve interrelated dependencies and to track those dependencies, beyond what a spreadsheet provides."
[bullet] This resolves a problem Fred Brooks identified in 1987: ""The essence of a software entity is a construct of interlocking concepts: data sets, relationships among data items, algorithms, and invocations of functions... Software systems have orders-of-magnitude more states than computers do...a scaling-up of a software entity is not merely a repetition of the same elements in larger sizes; it is necessarily an increase in the number of different elements. In most cases,
the elements interact with each other in some nonlinear fashion, and the complexity of the whole increases much more than linearly."
[COSI] "The Constraint Sequencing Infrastructure (COSI) is an extension to
the Common Lisp Object System (*(CLOS)) which supports a constraint
based object-oriented programming model. .....

"A constraint is a specialized method which will be automatically re-run by the COSI infrastructure whenever any of its input values change. Input values are any of the object attributes that are accessed by the constraint, and which are therefore assumed to alter the processing within the constraint.

"Whenever a state change occurs those constraints which depend upon that state are added to a propagation queue. When the system is queried a propagation cycle runs ensuring that the state of the system is consistent with all constraints prior to returning a value."
[impl] The Cells library as it stands is all about doing interesting things
with slots of CLOS instances, but Cells is not only about CLOS or even Lisp.
One Cells user is known to have mediated a global variable with a Cell, some work was done on having slots of DEFSTRUCTs mediated by Cells, and ports to C++, Java, and Python have been explored.

[axiom] Phillip Eby's axiomatic specification of Cells:

Data Pulse Axioms

Overview: updates must be synchronous (all changed cells are updated at
once), consistent (no cell rule sees out of date values), and minimal (only
necessary rules run).

1. Global Update Counter:
There is a global update counter. (Guarantees that there is a globally-consistent notion of the "time" at which updates occur.)

2. Per-Cell "As Of" Value:
Every cell has a "current-as-of" update count, that is initialized with a value that is less than the global update count will ever be.

3. Out-of-dateness:
A cell is out of date if its update count is lower than the update count of any of the cells it depends on.

4. Out-of-date Before:
When a rule-driven cell's value is queried, its rule is only run if the cell is out of date; otherwise a cached previous value is returned. (Guarantees that a rule is not run unless its dependencies have changed since the last time the rule was run.)

5. Up-to-date After:
Once a cell's rule is run (or its value is changed, if it is an input cell), its update count must be equal to the global update count. (Guarantees that a rule cannot run more than once per update.)

6. Inputs Move The System Forward
When an input cell changes, it increments the global update count and
stores the new value in its own update count.

Dependency Discovery Axioms

Overview: cells automatically notice when other cells depend on them, then
notify them at most once if there is a change.

1. Thread-local "current rule cell":
There is a thread-local variable that always contains the cell whoserule  is currently being evaluated in the corresponding thread. This variable can be empty (e.g. None).

2. "Currentness" Maintenance:
While a cell rule's is being run, the variable described in #1 must be set to point to the cell whose rule is being run. When the rule is finished, the variable must be restored to whatever value it had before the rule began. (Guarantees that cells will be able to tell who is asking fortheir value s.)

3. Dependency Creation:
When a cell is read, it adds the "currently-being evaluated" cell as a listener that it will notify of changes.

4. Dependency Creation Order:
New listeners are added only *after* the cell being read has brought itself up-to-date, and notified any *previous* listeners of thechange. (En sures that the listening cell does not receive redundant notification if the listened-to cell has to be brought up-to-date first.)

5. Dependency Minimalism:
A listener should only be added if it does not already present in the cell's listener collection. (This isn't strictly mandatory, the system behavior will be correct but inefficient if this requirement isn't met.)

6. Dependency Removal:
Just before a cell's rule is run, it must cease to be a listener for any other cells. (Guarantees that a dependency from a previous update cannot trigger an unnecessary repeated calculation.)

7. Dependency Notification
Whenever a cell's value changes (due to a rule change or input change), it must notify all of its listeners that it has changed, in such a way that *none* of the listeners are asked to recalculate their value until *all* of the listeners have first been notified of the change. (This guarantees that inconsistent views cannot occur.)

7a. Deferred Recalculation
The recalculation of listeners (not the notification of the listeners' out-of-dateness) must be deferred if a cell's value is currently being calculated. As soon as there are no cells being calculated, the deferred recalculations must occur. (This guarantees that in the absence of circular dependencies, no cell can ask for a value that's in the process of being calculated.)

8. One-Time Notification Only
A cell's listeners are removed from its listener collection as soon as they have been notified. In particular, the cell's collection of listeners must be cleared *before* *any* of the listeners are asked to recalculate themselves. (This guarantees that listeners reinstated as a side effect of recalculation will not get a duplicate notification in the current update, or miss a notification in a future update.)

9. Conversion to Constant
If a cell's rule is run and no dependencies were created, the cell must become a "constant" cell, and do no further listener additions or notification, once any necessary notifications to existing listeners are completed. (That is, if the rule's run changed the cell's value, it must notify its existing listeners, but then the listener collection must be cleared -- *again*, in addition to the clearing described in #8.)

10. No Changes During Notification:
It is an error to change an input cell's value while change notifications are taking place.

11. Weak Notification
Automatically created inter-cell links must not inhibit garbage collection of either cell. (Technically optional, but very easy to do.)