The Making of Cells: A Case Study in Dumb Luck

Preamble

Almost ten years ago I wrote up a library I had developed twelve years earlier, in another post named The Cells Manifesto.

Cells and the many other dataflow/reactive libraries like it are great but developers generally are immune to the paradigm shift. I do not feel bad: they are also immune to Lisp.

And Lisp is quite the analog for the dataflow paradigm: the deader each gets, the more you run into them. C++ and Java have discovered lambda, and good luck finding a UI framework that does not have "data-binding" or some reactive hack behind it.

What the Hell does this have to do with the invention of Cells? Well, I have a chance to land my second Cells user and he keeps saying he needs a deeper understanding and I flashed back to a crazy talk before Jay Sulzberger's Linux group on the Isle of Manhattoes as Jay likes to say in which a digression on Lisp led to an unplanned re-invention of Cells over the keyboard as a pack of FSF "C" programmers looking over my shoulder shouted out Lisp bug fixes (they did pretty good, and loved Cells) and it occurred to me that maybe the problem is that when programmers get excited about a new coding trick they start chewing the scenery with Holy Grail hyperbole and turn everyone off. Where was I?

Oh, right. The idea here is to finally get across the incredible power of dataflow by just talking about the problem we were trying to solve and how we solved it and how we then fixed the solution and slippery sloped up to dataflow.

The Problem: Dynamic, Nested UI Layout

We were building an educational math app aimed at struggling students, so the last thing we wanted was for them to be fighting to type in their math. We developed a WYSIWYG maths editor as a start and at a higher level of layout worried about them running out of room as they worked away. Resize bars need not apply, these kids and grownups are unhappy already.

I came up with a dynamic layout calculation scheme and on like day two my lead developer JD reported a problem with my approach. The use case was quite specific: fractions.

Background: the geometry I conceived for any visual element consisted of (a) that element's (x,y) offset within its parent container, and (b) the element's local bounds: left, top, right, bottom relative to (0,0) (hence "local"). Where did a box get drawn? Sum the offsets of my containers starting from the window's (0,0) and shift the local bounding box accordingly.

Fun note: a later subordinate complained (to others) that my geometry was understandable only to myself. Harrumph. I felt better when I learned OpenGL has the same system.

 So what was the problem with fractions? My algorithm hoped to calculate a child's geometry before calculating its parent's geometry, but to keep the operands of a fraction centered vertically the numerator, e.g., had to be horizontally inset half the difference between the fraction's width and the numerator's width. But the fraction did not know its width until the numerator had decided its width, because the fraction would take the max of the numerator and denominator. So neither child nor parent could go first.

Ok, ok: later I realized fractions should have a vertical alignment attribute saying "centered" and that the numerator should simply position itself horizontally at minus half its width, but I looked at this accidental use case and realized my overall idea of deciding an element's entire geometry in one go would never hunt. I also knew there was no circularity in fact, only in my algorithm.

"Everyone to the whiteboard!", I called out as if it were a breach in the city wall of Harfleur.

The Invention

True to my insight that it was not just fractions, I started with laying out the problem number (be it "1." or "42(a)."), the problem statement (be it "Simplify" or "Solve and characterize as conditional, contradiction, or identity") and below them the problem of any size the student typed in.

Step Zero

"OK, what is the left edge of the problem number?", I asked rhetorically, accidentally solving the first problem: my "baby steps" habit when struggling with hard problems had led me to contemplate the derivation of one bit of the widget's geometry, not its full geometry, 

"Zero," I concluded. "Same with the top." Unlike OpenGL, screen geometries tend to grow as you go down the screen.

"We are on a roll," I said, sensing Harfleur was ours. "Now what is the right edge?"

Step 1

 Nah, we need some caveats here.

One. All code below was just typed in using the Blogger text editor. Parens will not balance, typos will abound.

Two. If you do not know Lisp, the code may be a challenge. A good example is that (defstruct a b c) is a raely used short from that defines a struct of type 'a with slots b and c.

Three, Hell, it has been a year since I coded Lisp in anger. If something below looks like Clojure, it probably is.

Four. Goofs and obscurity aside, if like me you stare hard at examples and try to work out what must be going on, you will come away with a ton of questions and "that won't work!"s. The story here of incremental elaboration continued for weeks at a steady pace and for years in fits and starts as new challenges to the scheme arose. Maybe this one time, do not stare too hard.

We return you now to our show, picking up with Step 1 where, after luckily shifting to slot-wise thinking for the left edge (and top) of a widget, I contemplated the right edge of the same widget, which we wanted to grow and shrink as the student edited the problem number.

Step 1

"OK, the right edge is the left edge plus the string width of the problem number given the font metrics of the chosen font," I stated rather obviously since we were already doing that. But Harfleur was ours.

A value had been specified as a function of other values. When making the instance of the textedit widget, we would not specify a reasonable width of 42, too big for most problem numbers and scrolling for larger numbers, we would specify:

  (make-instance 'textedit

    ...etc...

    :lr (lambda (self)

          (+ (ll self)

             (fontStringWidth (text self) (math-font *app*))))

Cool. We never again have to worry about in which order to calculate things: other values we read will be calculated JIT. Er, how?

We just need an accessor (reader) that knows what we are up to (and a new defmodel macro to write all these accessors):

    (defmethod lr ((self textedit))

        (let ((sv (slot-value self 'lr)))

            (if (functionp sv)

               (funcall sv self)

               sv)))

Yeah, we need to do better because a function is a fine value for a slot so we cannot assume it is a rule to be funcalled, but it is a fair assumption for screen locations and it will not last long anyway.

JD knocked it off in an afternoon and we were delighted. Then of course the wheels came off: forever recomputing geometry was too slow. Note that this is an exponential problem, because property P might  compute off several other properties and several other properties might compute off P, and recursively so as container after nested container computes their properties.

Step 2

We cache the calculation, and now we need a struct:

     (defstruct cell rule value)

Note this solves our earlier problem: we no longer need to assume a function is a formula. Indeed, a function is a function, we are looking for cells now.

Brilliant: when we get a Mac OS update event we recompute the whole geometry but never recompute anything twice. We clear all the cached values and recompute and redraw. 

That lasted two days. Back then 100mhz was fast so soon enough we had enough stuff on the screen that a full recomputation too slow.

The good news is that I knew it would not scale, but when it comes to optimizing performance it is always nice to be asked. We had been asked.

Step 3

To get past this we have to recalculate only as needed. If the student types another digit in the denominator, we need to recalculate the denominator's width, recalculate its horizontal offset within the fraction, and -- iff the denominator is wider than the numerator -- recalculate the width of the fraction and pass that up the container hierarchy.

Note the happy optimization: if the denominator was sufficiently less wide than the numerator, the fraction would decide on the same width as before and there would be no need to recompute further up the container hierarchy. I digress.

So how do we decide "recalculate only as needed"?

   (defstruct cell rule value users)

A cell needs to know what other cells used its value in their calculations, so it can tell them to recalculate if it changes. Hold onto your hats (and this is just the first gust):

   (defmethod lr ((self textedit))
        (let ((sv (slot-value self 'lr)))
            (if (typep sv 'cell)
                (progn
                  (when *user*
                      (c-record-user sv *user*))
                  (let ((*user* sv))
                      (setf (value sv) (funcall rule self))
                sv)))

Ya gotta love Lisp special variables: above we are at once (a) tracking who might be using us and (b) letting anyone our rule happens to access know that we are using them. What may not jump out at the reader is that this works recursively because, at start-up of new structure, the variables our rule accesses may have to JIT compute their values, rebinding *user* to themselves.

Thanks to Lisp macros, this does not require too much typing (so the semantics stand out). First, the macro:

   (defmacro c? (rule)
       `(make-instance 'cell
            :rule (lambda (self)
                         ,rule)))

(The sick thing above is that the lambda parameter self will be captured by the code of the rule. Hygiene? We don't need no stinkin' hygiene!)

And now:

  (make-instance 'textedit

    ...etc...

    :lr (c? (+ (ll self)

               (fontStringWidth (text self) *math-font*)))

But that only records the dependency. Gust two:

    (defmethod (setf lr) (new-value self)
      (let ((sv (slot-value self 'lr)))
        (if (typep sv 'cell)
           (progn
              (when (not (eql new-value (value sv)))
                (setf (value sv) new-value)
                (dolist (user (users sv))
                   (c-recompute user))) ;; <---- dominos="" fall="" font="" the="">
              new-value)
           (setf (slot-value self 'lr) new-value))))

Note how propagation halts on a non-changing change. We are really making functional scream.

Note also that I was so focused on making functional fast that I missed that the world had turned upside down.

Those are inversion goggles. Wear them for a few days non-stop and suddenly the world becomes easily navigable; the brain flips the world back, as if a single bit controlled our vision.

In this case, the better metaphor might be of a river changing direction. Yes, the original problem knowing in what order to pull information into a computation, but after tweak number three the library was about empowering some initial change in state to domino efficiently to other state. Pull had become push, causation had been harnessed.

There we go again, chewing the scenery. Let's do practical again: how does the screen actually get updated? Let us just look at the snippet above where change is detected, now with a simple trick to do more than just change other computed values:

      (when (not (eql new-value (value sv)))
         (c-observe self 'lr new-value (value sv)) ;; <--- font="" the="" trick="">
         (setf (value sv) new-value)
         (dolist (user (users sv))
            (c-recompute user)))

c-observe is a generic multi-method we author any way we like as an "on-change" callback:

   (defmethod c-observe ((self vis-obj) (slot (eql 'lr)) new old)
       ... insert here code to trigger the update of the
       union of the old + new rectangles of self...)

Not only are we arranging for efficient, minimal, and complete change, we now have a hook to augment change processing arbitrarily.

One final point: we mentioned up front that nowadays everyone is doing reactive. That is true, but Hoplon/Javelin is the only one that does not require explicit subscribe and notify (and that works by code inspection so it recomputes excessively). Thanks to Lisp macros and some relatively modest engineering, subscribe looks like this (again):

  (make-instance 'textedit

    ...etc...

    :lr (c? (+ (ll self)

               (fontStringWidth (text self) *math-font*)))

...and notify looks like this:

     (setf (text self) (concatenate 'string (text self) new-char))

ie, Invisible. No need to break my coding flow and code up a publisher at a new source and subscription here, I just write my code and let the engine note the dependency. The more complicated a UI gets, the exponentially greater this win.

Tilton's Un-Law: Treasure the First Problem

Here is a good one from the trenches.

Once upon a time I said that when a multitude of problems present themselves we should decide which seems most like the first (independent of anything else the first observed, etc) and solve that first.

Perhaps I should have said identify the fault underlying the first problem.

This morning I am hacking away at Tilton's Algebra getting ready for a big pilot test and looking at several observed problems trying to help the student factor -x^2-2x-1, which can be solved as -(x2+2x+1) then -(x+1)(x+1) and finally -(x+1)^2.

• The app will not accept -(x+1)^2 as the answer. It says I can do more work.
• When then asked for a hint, it does not have one to offer. Wait, you said I could do more work!
• When asked for a hint after -(x+1)(x+1) it says it does not have one to offer, either.
• If I then ask if -(x+1)(x+1) is the answer, it says no (which is fine but again inconsistent with not having a hint to offer.)
• Final observed oddity: on a different problem such as -x^2-5c-6 -> -(x+2)(x+3) it will accept that as the answer.

So what is the first observed problem? It is a tie:

• If I first ask for a hint on -(x+1)(x+1), it has none to offer.
• If I first say -(x+1)^2 is the answer, it says I can do more work.

So here I would say the failure to hint comes first, because I could reasonably ask for a hint before reaching what I think is the answer. Put another way, it is not so much the order actually encountered, it is more that I can see a problem exists as early as when I might ask for a hint.

And the underlying fault is quickly found:

The hint mechanism looks at where the student has gotten in a solution to decide what to suggest next. In this case, the engine thinks the student is just plain wrong, because it itself came up with a weak answer: (x+1)(-x-1). 

But why did it accept -(x+1)(x+1)? Aha! Big story begins: this is an educational app, designed mostly with struggling, unhappy students in mind. It does so with an expert system engine programmed to be able to do Algebra. This engine sometimes goes wrong, as in this case. When that happens it tells the student they are wrong when they are not. I for one consider that a Deadly Sin.

It occurred to me that simple numerical methods would be able to determine that a "wrong" entry by the student was consistent at least with the original problem, so a failsafe mechanism was introduced to let slide anything that looked wrong but was not, in the hope that it would work out in the end.

That trick actually fools the hinting mechanism, which looks back to the last correct step to decide what to hint. Unfortunately the safeguard decided to say a step (mistakenly) considered wrong should be labelled correct. As we learned in the movies 2001 and 2010, it is not wise to deceive software. Better would have been to flag the step accurately as "wrong but consistent", so the hinting engine would not try to hint off it.

And in the case of -x^2-5x-6 the safeguard does succeed at least when it comes to accepting the answer. But in neither case is it able to offer a hint once the student enters, say, -(x+2)(x+3) because it thinks they are just wrong and as noted above the engine looks to see where they are in the solution. In this case it decides nowhere, so it has no hint to offer.

Interestingly, when asked if -(x+1)(x+1) is the answer it says no because it sees it can be rewritten as -(x+1)^2! This then reveals a second fault:

The engine when looking for a hint and checking if they are done looks in two different places, so it can say "not done" then have no hint to offer. This sin is not as bad, but it could be deadly: the student will lose confidence in the software, at which point no matter what mistake they make they will think the app is at fault.

Re that last: helluva war story from the enterprise trenches when a single bug trashed insurance enrollment data significantly but not so badly that it got noticed immediately. By the time the complaints had rolled in and enough investigated to reveal the corruption reversion to a backup was not viable. Users had to deal with complaints for weeks while a fix was found, so once it was they continued to question the data for an additional month or two before confidence was restored.

 Now it may well be that fixing the original fault (the engine's answer of (x+1)(-x-1) will eliminate all the other misbehavior, but remember the spirit behind the failsafe: if we can avoid abusing the user when the engine goes wrong (as it may) we should.

Now in the past I have come this way before and simply fixed the engine and moved on, but then it was impossible later to design a safeguard! The engine flaw has to be authentic, because a fix for a contrived flaw might well not work on the real thing. And engine flaws are rare enough that I just forget the whole thing until a day like today comes along.

So this time I am not fixing the first problem, Go-live is approaching and soon living breathing struggling unhappy students will be at my app's mercy. I am treasuring this problem for the stress it puts on the rest of my app, because I accept that the expert engine will not always be so expert.

Only after all the downstream misbehavior has been addressed will the first problem be fixed.

 

Wow, even Lispers hate Lisp!

Not sure yet what is going on here but someone on comp.lang.lisp just made an interesting post, interesting because it seems to reflect a substantial and well-informed effort (nice!) all to denigrate -- wait for it -- a computer language. (Really?)

Not sure how that works. I think Python bites so I do not use it, I do not labor over detailed treatises to post on comp.lang.python. But it is a great treatise so I will promote it some here.

We have perhaps yet another measure of how great is Lisp: even its haters are its fans. They come to boo, but come they do. Like Gorgeous George and his understudy, Muhammad Ali, Lisp puts ticket buyers in seats as much to be hated as used.

WJ on comp.lang.lisp wrote:

Worshippers of CL (COBOL-Like)

Dying is easy, comedy is hard. Humor must have within it some truth for it to work. The laugh comes from the accuracy followed by a sharp turn to a put-down, the sharp turn being the key. If Lisp is not like COBOL there is no sharp turn and the put-down becomes mere name-calling. Sticks and stones and all that.

Please try not to try to be funny again.

are the most slavish punks that
the world has ever known.  The hypertrophied CL hyper-spec is
their Holy Bible.

Their are the worst enemies that Lisp has.  (And they never win.
Only the most mediocre of programmers are willing to slave over
the CL hyper-spec.) 

We need the spec when we want to get fancy with format, 'mkay?

And yes, it is actually a Religion to these degenerates.
Don't believe me?

Kenny Tilton:
We are the Priesthood.  Offerings of incense or cash will do. 

I take it back. I have now worked with some pretty awful Lisp programmers. They are better than any non-Lisp programmers, but any incense or cash should go to me alone.

Here's what the experts say about COBOL Lisp:

"an unwieldy, overweight beast" 

The only thing I do not use is series.  Hmmm, I should go look that up.

"intellectual overload" 

For most of you, yes. Lisp is for smart people.

"did kill Lisp" 

That explains the smell. Sorry, I forget the author of that one.

"A monstrosity"
"ignores the basics of language design"
"killed Lisp"
"sucks"
"an aberration"
"the WORST thing that could possibly happen to LISP"
"incomprehensible"
"a nightmare"
"not commercially viable"
"no future"
"hacks"
"unfortunate"
"bad"

In context:


Guy L. Steele, Jr., July 1989: 

He went from Lisp to Constraints and butchered that, from there to Java and can take a lot of credit for that steaming pile of turd, and has now abandoned that failure to work on... Fortran?

I think we may usefully compare the approximate number of pages
in the defining standard or draft standard for several
programming languages:

  Common Lisp   1000 or more
  COBOL          810
  ATLAS          790
  Fortran 77     430
  PL/I           420
  BASIC          360
  ADA            340
  Fortran 8x     300
  C              220
  Pascal         120
  DIBOL           90
  Scheme          50 

50? Check again.

-----


Brooks and Gabriel 1984, "A Critique of Common Lisp":

Every decision of the committee can be locally rationalized
as the right thing. We believe that the sum of these
decisions, however, has produced something greater than its
parts; an unwieldy, overweight beast, with significant costs
(especially on other than micro-codable personal Lisp
engines) in compiler size and speed, in runtime performance,
in programmer overhead needed to produce efficient programs,
and in intellectual overload for a programmer wishing to be
a proficient COMMON LISP programmer. 

Yeah, Graham said that, too: a language has to fit in your head. I am thinking he did not program enough to learn it really well*. And he prolly did not have the hyperspec an F1 away either.

* I am pretty sure a constraint on a language I intend to use all the time should not be that I have to be able to remember it all when I am not using it all the time.

-----


Bernard Lang:

Common Lisp did kill Lisp. Period. (just languages take a
long time dying ...)

You know Lisp is the perfect language precisely because it lost its momentum (died) and lives on. Other languages need their Next Big Thing momentum.

It is to Lisp what C++ is to C.  A
monstrosity that totally ignores the basics of language
design, simplicity and orthogonality to begin with.


-----

Gilles Kahn:

To this day I have not forgotten that Common Lisp killed
Lisp, and forced us to abandon a perfectly good system,
LeLisp. 

The French are still pissed off about Lance Armstrong!

-----


Paul Graham, May 2001:

A hacker's language is terse and hackable. Common Lisp is not.

The good news is, it's not Lisp that sucks, but Common Lisp.

Historically, Lisp has been good at letting hackers have their
way. The political correctness of Common Lisp is an aberration.
Early Lisps let you get your hands on everything.

A really good language should be both clean and dirty:
cleanly designed, with a small core of well understood and
highly orthogonal operators, but dirty in the sense that it
lets hackers have their way with it. C is like this. So were
the early Lisps. A real hacker's language will always have a
slightly raffish character. 

Come on, we have "goto". What else does he want?

Organic growth seems to yield better technology and richer
founders than the big bang method. If you look at the
dominant technologies today, you'll find that most of them
grew organically. This pattern doesn't only apply to
companies. You see it in sponsored research too. Multics and
Common Lisp were big-bang projects, and Unix and MacLisp
were organic growth projects.


-----

Jeffrey M. Jacobs:


I think CL is the WORST thing that could possibly happen to LISP.
In fact, I consider it a language different from "true" LISP.

  *****

Common LISP is the PL/I of Lisps.  Too big and too
incomprehensible, with no examination of the real world of
software engineering.

...  The CL effort resembles a bunch of spoiled children,
each insisting "include my feature or I'll pull out, and
then we'll all go down the tubes".  Everybody had vested
interests, both financial and emotional.

CL is a nightmare; it has effectively killed LISP
development in this country.  It is not commercially viable
and has virtually no future outside of the traditional
academic/defense/research arena. 

Can I respond to all these "CL killed Lisp" quotes by pointing out that they are wrong? I am developing The World's Greatest Algebra software on Windows 8 (after 7 and Vista and XP), pushing to GitHub, pulling onto Linux and away we go*. Standards avoid the disaster of Scheme, which brilliantly recreated the problem CL had to fix: disparate implementations leading to unshareable code. *Okay, I am using compilers from the same vendor, but I am also using a ton of open source written mostly for SBCL.

Common Lisp worked, but it got the blame for Minsky's (inter alia) over-promising and under-delivering on AI.

-----

Paul Graham:

Do you really think people in 1000 years want to be
constrained by hacks that got put into the foundations of
Common Lisp because a lot of code at Symbolics depended on
it in 1988? 

Constrained? Where? Who? How? I am writing amazing code and having a blast between bong hits. Where's the problem?

-----

Daniel Weinreb, 24 Feb 2003:

Having separate "value cells" and "function cells" (to use
the "street language" way of saying it) was one of the most
unfortunate issues. We did not want to break pre-existing
programs that had a global variable named "foo" and a global
function named "foo" that were distinct.  We at Symbolics
were forced to insist on this, in the face of everyone's
knowing that it was not what we would have done absent
compatibility constraints. It's hard for me to remember all
the specific things like this, but if we had had fewer
compatibility issues, I think it would have come out looking
more like Scheme in general. 

I think DW meant "looking more like Scheme" as a good thing. Ouch. I used Arc for a while and it had one namespace and it was not fun.

-----

Daniel Weinreb, 28 Feb 2003:

Lisp2 means that all kinds of language primitives have to
exist in two versions, or be parameterizable as to whether
they are talking about the value cell or function cell. It
makes the language bigger, and that's bad in and of itself. 

I think some of these smart guys are thinking themselves into to many rules and regulations and way too much "should". I am not that bright so I am free to just get on with the programming, and when one is programming one knows what works and what does not. One namespace does not.

-----

Paul Graham:

I consider Loop one of the worst flaws in CL, and an example
to be borne in mind by both macro writers and language designers. 

Except there is no non-Loop code posted to comp.lang.lisp that I cannot make clearer and faster with loop. And it took me a very long time to come around to loop, so I should know. Yes, the syntax can make you weep*. Until you learn it. Then it is an undisputable win.  * Hey, it is a DSL. Ya gotta learn it, like any language. And it is a DSL for iteration, something that comes up more than a little in programming, so the effort (and the DSL itself) are justified.

-----

Dan Weinreb, one of the designers of Common Lisp:

... the problem with LOOP was that it turned out to be hard to
predict what it would do, when you started using a lot of
different facets of LOOP all together. This is a serious problem
since the whole idea of LOOP was to let you use many facets
together; if you're not doing that, LOOP is overkill. 

I wonder if Dan wrote enough code. Loop never surprises me, now that I have learned not to close over loop variables.

-----


From: John Foderaro
Newsgroups: comp.lang.lisp
Subject: Re: the "loop" macro
Date: Sun, 26 Aug 2001 10:51:26 -0700

I'm not trying to join a debate on loop.  I just wanted to present
the other side of [the issue so that] the intelligent people can
then weigh the arguments on both sides.

I'm not suggesting that loop can be fixed either by adding
parenthesis or coming up with ways of indenting it to make it
understandable.  It's a lost cause. 

Hey, that's the guy that did IF*, a DSL for conditions!

Why does all the above miss its mark? Because it is 2013 and all that was written when CL got created back in the eighties and we are still using Lisp and when we do we use Common Lisp. All those quotes are by people who saw the politics and the big spec and were unhappy about the compromises and the size of the resulting language. But I use it all (except series) so they were wrong about the size.

Meanwhile the raison d'etre of unification was achieved. Yobbos are writing open source on SBCL and I am going to use it to change the way the world learns math, atop AllegroCL. A brave attempt to resume the fragmentation (scheme) failed. Mostly because they were wrong about language design, but also because of -- wait for it -- fragmentation. Perfect.

Fortune Cookie File Number Two

Wow, what an effort! Nice followup to part one! Thx, Madhu!


%
Are you trying to win a Moron Contest*, or did I miss a joke?
-- Kenneth Tilton
%
[Quoting some "Bell Labs engineer" from the Newark Star Ledger]

"The hardest part for me was realizing I was being tolerated by all the people I had been tolerating."
-- Kenny
%
That is a metaquestion. No metaquestions allowed under Obama. Note that this is a metametaanswer, it's like minus signs, ya got two ya ain't got any. With me so far?
-- Kenneth Tilton
%
Let's decide on the shape of the table before deciding if the discussion to decide if free open software is ethical is going anywhere.
-- Ken Tilton
%
Pioneers do not wait for the rest areas on the interstate highway to
have sushi bars.
-- Kenny
%
The Mac I have now sounds like a 747 turbine after spinning up, can't
even hear The Voices let alone program a computer.
-- Kenny <490ba086$0$5643$607ed...@cv.net>
%
What part of Anna Kournikova do you not understand?
-- Kenny
%
That will be well-received, and when Anna Kournikova sends you an
email asking you to come spend a week with her you complain that she misspelled Tahiti and the airline tickets she sent were not first-class and write back asking if she knows anyone prettier you could stay with?
-- Ken Tilton
%
I think Celtk just needs Cells. This is like saying that if you want
Anna Kournikova to have your baby then you have to sleep with her.
-- Ken Tilton
%
Anna played tennis?
-- Ken Tilton
%
Muhammed ibn Musa al-Khowarizmi! He wrote the book on Algebra!
Literally. Not sure where I can get a picture, tho. Maybe I can give
Anna a beard...
-- Ken Tilton
%
I feel a naggum coming on. When you think you know what I am thinking try to stop thinking.
-- Kenny
%
[...] you should -- I feel a naggum coming on -- stop trying to impose
your prior understanding on a new experience. You are like an
American tourist landing in Kinshasha and going in search of a Burger
King. Sadly they do not have to go far.
-- Kenny
%
I feel a Naggum coming on. Before you contradict me or challenge me or quote me, please make sure you are not in fact talking about an inferior model of me rooting around somewhere in your cortex (and what a scary image that is).
-- Ken Tilton
%
New Yorkers are not offensive. The joke is a good one (The proper way to ask for directions in NYC? "Excuse me, can you tell me the way to Lincoln Center, or should I go fuck myself?") but the reality is New Yorkers are so nice they will gladly give you directions whether or not they know the way.
%
[...] the mentally ill are often the most compassionate because of what they have endured.
-- Kenny
%
Instead you are like a new yorker asked for directions and before they
can even get out the words "...to Carnegie Hall" you have responded
"Use Google Maps. And rent the French Connection. The chase scene
covers most of Manhattan."
-- Ken Tilton

[Actually it was shot in Brooklyn -- rc]
%
Your other mistake is thinking I was planning a 500-page treatise
complete with suggested legal forms. I am an American, we have Cliff
Notes for haiku.
-- Ken Tilton
%
I will be honest here, I am just a humble application programmer, and as an American I barely know where Monte Carlo is because we only need to know where is Las Vegas.
-- Ken Tilton
%
> "If Lisp is so great why don't libraries, etc. exist for it like
> they do for Ruby, Python, ...".

You are wondering why Shakespeare never conceived a hit game show like
Deal Or No Deal, and why Tiger Woods sucks at miniature golf. Why
Pavarotti never has and never will make it to the Billboard Pop 100,
and why Dale Earnhart got fired after one week driving a taxi in NYC
(he could only make left turns).
-- Ken Tilton
%
The first time you run into something is only the first time you will run into it.
-- Ken Tilton
%
Then again, I do not see why you even want to see it, you already have that sanctimonious glow from using free as in how we defined it software.
-- Ken Tilton
%
What I saw was a defense of Java as being halfway to Lisp and the bit about him having a chart trying to close all the possible holes where behavior was unspecified. True Lispers laugh in the face of unspecified. Hell, we pay extra for it.
-- Ken Tilton
%
Meanwhile Steele famously claims Java is halfway to Lisp. Perhaps he
meant starting from the stone axe?
-- Ken Tilton
%
Apparently these geniuses think it matters one whit whether the spec
in its entirety can be carved on the head of a pin.
--Ken Tilton
%
Now there's a language design principle. Another good one is that you
can sing it to the tune of Camptown Races.
-- Ken Tilton
%
"...Those who can't do, teach. Badly. I am reminded of the New Math,
which made Principia Mathematica (?) a first-grade textbook."
-- Ken Tilton
%
".... Never heard from again, though rumor has it Steele found work
as a tech writer for Sun."
-- Ken Tilton
%
[on motivation to finish his product]

Not to worry, I have a friendly letter here from the IRS asking when
they might expect to see last year's taxes, those tend to focus the
mind wonderfully as well. :)
-- Ken Tilton
%
wants to follow The One True Lisp Way and trust us to know what we are
doing, so compliance here would be compliance for it's own sake.

I must need a drink, that last word looks like a Japanese malt brew.
-- Ken Tilton
%
Had you responded here instead of by email I could have eviscerated you in public (the only thing I really enjoy, the only thing that sets me apart from serial killers).
-- Ken Tilton
%

> And thank you all, (every #'primep ...) worked great. I found it is
> a very nice and helpful place here!

Just wait until you put a parens on its own line, the honeymoon will
be over fast.
-- Ken Tilton
%
> I try never to memorize what I can just look up.

Right. I never memorized C precedence, I dog-eared that one page in
K&R and/or threw in a pair of air-bag parens and skipped the lookup
altogether,
-- Ken Tilton
%
But that code is quite solid and close to Deeply Correct. I know because it has not changed much in years and handles new requirements effortlessly, generally by /taking out/ code that was enforcing disciplines which turned out not to be necessary (and in Lisp we hold inalienable the right to shoot off our own toes).
-- Ken Tilton
%
In the end I remembered that I have never let a concern for accuracy
get in the way of my rants, way too much work.
-- Ken Tilton
%
hard-charging newbies such as yourself landing in Lispville dumbfounded by all the dust, cobwebs, rust, and neglect giving the boot to the war-weary, disheartened, parentheses-mocked old soldiers rolling up your sleeves and setting about dragging the damn language out of the seventies and into the 21st century just in time for the asteroid to hit. What was the question?
-- Ken Tilton
%
You want there to be a problem, just like the strong static typers
want there to be a problem. Unfortunately for all you finger shaking,
rule making, strait jacket wearing school marms we have a nonexistence
proof of craploads of great code being written without a problem in
spite of your sky is falling obsessive compulsive gnashing of the
teeth.
-- Ken Tilton

%
>> Wow, that is two non-required requirements in a week. Me, I am
>> looking for a transmission that can go from forward to reverse at
>> fifty miles an hour without self-destructing. I don't have a need
>> for this, I am just looking for it.
> Easily done. Not so easy is to allow any human passengers to
> survive the event.

Reminds me of the guy I met who said he and his buddy agreed at
sixty-five miles an hour to find out what would happen if they applied
the parking brake. Let's just say it is a good thing that they had
agreed on it, and that the rental car company did not ask how their
car ended up upside down.
-- Ken Tilton
%
If you have to use so many big words, you must be wrong.
--Ken Tilton
%
Please follow up, I want to see if my killfile is working.
--Ken Tilton
%
Yeah, yeah, it was just a rant, you never want those held back by
concerns over accuracy. The sexp/mexp thing esp. suggests divine
inspiration might be a better model than alien arrival.
-- Ken Tilton
%
Unlike the inability of a deliberate mention of Hitler to function as
would an emotionally honest invocation of same to signal the end of a
flamewar, one can apparently climb up on top of the nearest car hood
and announce one is starting a flamewar just to irritate people and a
crowd will immediately form to argue with one over doing so.

I once saw a nature special in which some insect or other dragged some other dead insect somewhere then turned around and dug a whole for it to bury it but the researchers moved the dead insect a bit while it was digging so it had to drag it back but while it did they filled in the hole and back and forth this insect went indefinitely until a PETA sniper took out the researchers. Where was I?
-- Ken Tilton
%
>>I realize other people prefer other environments, they are just
>>mistaken. My ideal setup happens to be the best, hands down.

Wow, I am really out on a limb there. It would be pretty easy to take me down by naming a superior or even near equal environment. Or you could back down in the face of my confidence and resort to, I don't know, name-calling?

> You're clearly deluded.

Understood.
-- Ken Tilton
%
I am not, really. I will do a year or two of Algebra and then have
enough money to open a bar, do what I really want, tend bar.
-- Ken Tilton
%
Mind you I /have/ AG, but there is no point in doing cells-rdf if the
rest of you food-stamp licking, government cheese eating, thrift
shopping oooh-its-gotta-be-free pikers won't be able to benefit from
my unceasing thankless toil on your behalf.
-- Ken Tilton
%
> Cells or Cello might be the solution. But getting mad at people won't
> help.

Thanks for your concern!

Not to worry, I abuse these yobbos for fun, not out of anger. And I
am not sure c.l.l would know what to do with KGK (Kindler Gentler
Kenny), but...
-- Ken Tilton
%
Otherwise, sorry Karl, we are discussing the best way to learn Lisp
(free ACL trial on win32), not the best way to resurrect your six-feet
under commie pinko socioeconomic theory.
-- Ken Tilton
%
> Can someone with a bigger brain than me please elucidate.

I think the problem is not brain-size so much as your admirable attempt to understand a tool by reading about it. That puts you at the mercy of technical writers, who combine an inability to program at all well with an inability to write.
-- Ken Tilton
%
> check this out buddies

I have a buddy?!!! woo-hoo! I thought I had alienated everyone with
my sarcasm!!!!
-- Ken Tilton
%
Tell us more about your home planet.
-- Ken Tilton
%
I'm gonna hurl. Come on, everyone, newsgroup hug....
-- Ken Tilton
%
(a) You seem to be unaware of the Laws of Conservation of Hyphen
Momentum: according to the CLHS, a term in hyphen motion tends to
remain in motion, a term at hyphen rest tends to remain at rest.

(b) Really, the worst thing you can do in CL is use a macro where a
function would do. The Pope does not sudo ex cathedra to say, "It's
not the heat, it's the humidity."
-- Ken Tilton
%
Was the author writing under the cloak of infallibility, channeling
the word of G*d, and is our Talmudic interpretation of those awkward
words precise? The legislative history shows that CL got designed to
address concerns of The Big Customer over language fragmentation, so
it is hard to imagine an intent other than to define one language.
The next step was a pretty tight ANSI standard language specification.

Too easy? (I know, it is more fun being contrarian.)
-- Ken Tilton
%
The language lawyers cannot save you. I am your only hope. I am a
simple application programmer.
-- Ken Tilton
%
Fine, bring me a single malt, a pint of amber back, a wedge of cheddar and some saltines. And we'll need more napkins before we're done with this design.

ps. Oh, and another jar of dijon, and ask the redhead under the moose head if she would like to join us.
-- Ken Tilton
%
> What is a `hacker', or `programmer', or `computer scientist'?

The last two were dragged to their death in the last thread. Hacker is a term used by us computer geeks in a desperate attempt to glamorize our bit-ridden asses, as if the best of us will ever get laid as often as the tone-deaf, rhythym-blind bassist of a third rate cover band on Long Island, let alone the rock stars we pose as when we call ourselves hackers. Paul Graham, who I generally greatly admire and hope will because I said that fund my start-up but more lavishly than he does those Y-Combinator conscripts, drove a stake through the heart of the term here: [snip]
-- Ken Tilton
%
I actually had a business card that just said "Programmer". Got everyone quite upset, they wanted "Systems Analyst" or "Software Engineer" or "Database Administrator" or something. My point was that one cannot program a computer effectively without doing all those things, so "Programmer" was sufficient.
-- Ken Tilton
%
Now can we get back to name-calling? Stop trying to civilize this
brawl.
-- Ken Tilton
%
>> I always tell youngsters it is OK to take one year off before grad
>> school, but for the love of god don't take two.
> I think this depends on the person.

Never look a gift joke in the mouth.
-- Ken Tilton
%
> My theory is that is we bought and open-sourced [...] we could get
> the community to rally around that one,....

The idea of this Lisp community "rallying" is about as conceivable as
a hootenany down at the cemetery.
-- Ken Tilton
%
It is the mouse that feels bad, not the cat playing with it.
-- Ken Tilton
%
The big mistake is thinking Lisp is going to grow by first being
adopted in Tall Buildings. They are the drones, the lemmings, the
sheep. They follow where We the Blessed Gurus lead them. But this
time it is to the slaughterhouse, because the world needs only fifty
Lisp programmers to write All the Code.
-- Ken Tilton
%
... listening instead of yapping? Read my frickin lips: I am talking
about actual tall-office design reviews in which well-paid engineers
... pragmatically suggested design disasters because they objected to
anything a pet rock (sorry, Rockie) could not code.
-- Ken Tilton
%
Anyway, if one has not programmed heads down for three years one likely does not know much about design. I am sure I write more code in a year than academics write in a lifetime, because we are doing different things. Hell, they have the sorry task of trying to pretend there /is/ such a thing as computer science. If there was, wouldn't everyone be using Lisp?
-- Ken Tilton
%
Unfortunately I still do not understand the question, and I am a
frickin genius, I have a three-digit IQ, 50% more than 2.
-- Ken Tilton
%
Well the trick of folks like H.. is to listen just enough so that one can respond to a direct hit with multiple non-pointing counterpoints, each more retarded than the last and each stated in an artfully needling fashion guaranteed to make the sanest NG denizen continue the thread, as if the /next/ direct hit will achieve any more than the last.

It's like playing paintball with a guy who keeps running around and
shooting, covered head to toe in paint.
-- Ken Tilton
%
> deal more. But after seeing your behaviour in cll you can be
> assured that I will never, ever consider any functional programming
> language. I can just do without languages that attract that kind of
> behaviour.

-- tim (and yes, before you respond, that is one reason I
don't use CL so much any more as well.)

Abandoning something wonderful because of who else uses it makes
perfect sense. Why did I give up sex? One word: Joey Buttafucco.
-- Ken Tilton
%
Never been to a code review, have you? You are blessed. The worst crap in the world gets protected by the manager because he is the only person in the room more clueless than the author of the crap and dies when the author dies because the author is in effect a buoyancy device for the in effect non-swimmer manager. But I digress.
-- Ken Tilton
%
I cannot write correct code to save my life, I just throw out any bad code. Only trick there is to distract the author with a banana while deleting their code.
-- Ken Tilton
%
You know, the oil companies have developed a car that runs on carbon dioxide and has like 800 horsepower. Where you can buy one is another question.
-- Ken Tilton
%
Me, I saw the "Microsoft Research" oxymoron and did not get much
further. Unless by research they mean using Google to find out what
ideas other people have successfuly developed and commercialized so
they can copy it badly and crush them.
-- Ken Tilton
%
> Yawn. You must be a riot at parties.

And you must be the life of a funeral.
-- Ken Tilton
%
The way to get this going is to post here an especially good RQ
question and your Lisp solution, see if you can drum up interest. If
it takes off, you start a Web site or something. If not, the ball
game comes on at two.
-- Ken Tilton
%
ps. I agree, the "fingers will be chopped off" sign should not have
been Comic Sans. :)
-- Ken Tilton
%
Well whaddya know. I do GUIs, leave file work to the chimps. You win
a banana.
-- Ken Tilton
%
Can we continue this over on comp.lang.turing.complete?
-- Ken Tilton
%
...the only thing that matters is Becoming the Latest Thing. What is
the latest thing? The (a) new thing (b) being recommended (c) by
Famous People (d) in respectable places
-- Ken Tilton
%
The operator helpfully suggests that I could avoid this problem by simply saying that my mother's maiden name is YOBBO, no one will make fun of me. He also takes care of confirming the purchase over the phone, while I try to figure out how to sell "Hi, I need to change my mother's maiden name..." to the next operator.
-- Ken Tilton
%
So I am working in a lab? That would explain all the beakers.
-- Ken Tilton
%
That rose girl is drying up and a few volcanos need sweeping.
-- Ken Tilton
%
Grapette this: no, Jodie Foster is /not/ responsible for John Hinckley
shooting three people including the President. The correct question
was "Who is John Hinckley?".

Really, kiddies, it is OK to blame the perpetrator. Not that I do in
this case. The OP is clearly an unhappy puppy deserving nothing other
than compassion for the demons that drive them to randomly attack
Usenet blowhards like me.
-- Ken Tilton
%
And Uhl says Kenny has made the South forget the Civil War, not sure
how I could top that. The hounds are exhausted, smiling in their
sleep. It's all good -- but someone has to talk Bubba and Jethro down
from their sniper nests.
-- Ken Tilton
%
Do they have the distinction between a priori and a posteriori in your
banjo-pickin, moonshine-slurping, carcinogen-growing,
basketball-playing neck of the woods? How about de jure vs. de facto?
Simular.
-- Ken Tilton
%
That /was/ a despicable and wholly unjustified ad stateum low-blow, a
cheap shot deliberately designed to make me look bad. It crosses a
shocking line, beneath contempt, really. Clearly I had cut in my
flamethrower after-booster and lost all reason or sense of decency.
It almost makes me wonder if I was even serious...
-- Ken Tilton
%
See, this is what happens when you get all riled up and change the
subject to whether Kenny is consistent or not, you get so emotional
you cannot read straight. And my inconsistency varies quite a bit, so
I do not know if you can build an argument on that anyway.

ps. Random problem cloning is going well, but obviously slowly enough
to have me dashing here to hide pretty regularly. :) What kind of Lisp
did you write today?
-- Ken Tilton
%
MWUAHAHAHAHAHHAHAA!!!!! Yes, palindromeloopstate set to 1 makes the
movie run endlessly forth and back. Picture looks fine running
backwards, but instead of the spoken words coming out in reverse,
well, it is just unrecognizable noise. Working on that now...
-- Ken Tilton
%
Fine, but anyone who uses Usenet knows that that is not how one says
"Thanks". Which is why I felt safe moving directly to defcon 3, just
to see how big an *sshole we had on board. His defcon 1 "Rot in hell
jackass" response merely, well, QED.
-- Ken Tilton
%
[...] the serious answer comes from the Tao Te Ching, lessee, on about
every other page:

"A man on tiptoe cannot walk easily."

Or:
"Never trying to impress, their being shines forth Never
saying 'this is it', people see what the truth is -- Never
boasting, they leave the space in which they can be valued ...
And since they never argue, no one argues with them either."

Lao Tzu clearly would be no fun in a flame war.
-- Ken Tilton
%
"Gotcha" is like analogies, they lead to arguments about the
gotchaness of the gotcha, an exponential explosion guaranteed.
-- Ken Tilton
%
Despite copious opinion to the contrary, I speak not as Grand Poobah
of Common Lisp and have not the power to marshall our forces to
maximize the benefit of their labor. I can only pause between rides
to town on my pushbox to wonder aloud in camp why a serous chunk of
our tribe is over there under the tree working on the wheel and
axle -- ones no better than the one on my pushcart.

Kenzo: "Dudes, it's been twenty-five years, prices down at Throg's
Wheel & Axle aren't all that bad. Why not work on a mast and sail?"
-- Ken Tilton
%
A subtle execution of the tip of a tongue pressed against the upper
teeth with sprays of spittle coming out either side probably is not
what you had in mind.

Hmmm. Then we change the spelling to Lithp, and never have to hear
that stupid joke again. Our slogan can be "Thay it loud, thay it
proud."*, and we already have the frickin lambda.

Or "Out With Lithp!".
-- Ken Tilton
%
Barker: "Stairway to Heaven! Open to all! Come on up! One-day
amnesty!"

Kenny: "No elevator?"
-- Ken Tilton
%
No, I made a few changes and sent it to the Copyright Office.

For Mom I am holding out for the cover of Wired. (She already takes
America's Most Wanted.)
-- Ken Tilton
%
"you also physically incapable of understanding that your opinions are
not the words of God". Nice comeback on originality! Physical
understanding? What part of the mind-body problem do you not
understand?
-- Ken Tilton
%
No, I would mock you for being so locked into mob-rule and aggression that you think my insistence on walking to a different drummer entails also abusing anyone not conforming to my non-conformity.
-- Ken Tilton
%
"wet feet" might not do justice to the 3D learning curve -- that
subsonic rumble shaking your kayak is Niagara Falls.
-- Ken Tilton
%
"Feeling no pain, Kevin?"
"Sorry?"
"You just came out of the women's rest room."
"Look, I had to take a leak. Odd, no urinals, just sit-downs."> & no
'bouncers' made any approach..

It's crowded, they are still working their way through the crowd.
Don't worry, we'll explain about the Lisp "high".
-- Ken Tilton
%
er, um... no. OO is about managing huge wadges of code in huge
systems that will be spending most of their lives waiting on disk I/O
so WTF cares about OO overhead, we need to manage these huge
codebases!!! ie, OO is for lazy-ass mo-fos who cannot be bothered to
toss of a few dozen lines of code and reinvent "objects" in a fashion
screamingly optimized for their application.
-- Ken Tilton
%
So it samples the pitch and guesses at rhythm and provides tutoring
similar to what I would get from a good music teacher? Astonishing.
AI has been solved! Stop the presses on the emasculation of George
Bush, we have real news!!!
-- Ken Tilton
%

> if Clisp is so good where are the commonly used apps?

If George and Barbara had such great sex, how did they produce Jeb and Dubbya?
-- Ken Tilton
%
> I like the lizard.

No, you don't, you are just saying that. Think again.

> But then, I like the Geico gecko, too.

Everybody likes the GG. It has an australian accent.

> And I like Common Lisp, too. Guess I'm weird, hunh? ;-}

I was thinking "doomed".
-- Ken Tilton
%
And a mascot like Joe Camel to suck in the kiddies, gotta have a
mascot.
- Ken Tilton
%
You yobs might want to ... oh, what's the use? Lisp is dying. The next generation of Lispniks is over on #lisp worshipping themselves and learning nothing and achieving less. My god, another two years and Slime may be half the power of the ACL IDE. What is the word I am looking for... ah, here it is: PFFFFFFFT!
-- Ken Tilton
%
You French really are pissed off about Lance Armstrong, aren't you?
-- Ken Tilton
%
* reminds me of part of a route description to a rock climb called
Death's Door: "Don't use the jug handle just to the right of the
finger jam, that hold is part of Cakewalk."
-- Ken Tilton
%
I have worked with body shop programmers who could not be bothered to write structured code. Are the concepts of structured programming too hard? Nah, those people just "refused to be bothered" (a direct quote), meaning they were too inured to the pain of spaghetti coding to realize how much "bother" structured programming could save them. They thought spaghetti code was /easier/ because, hey, how hard does one have to think to add another GOTO? It breaks somewhere else? Add another GOTO! C'mon, this is easy! Breaks somewhere else...read my lips: GOTO!
-- Ken Tilton
%

The King is Dead!? Long live... Scala? Clojure?!

Whoa, why wasn't I told Java is closing its doors? I guess I have been out of touch, word seems to be everywhere. I had to go here (blog of the guy who created Groovy) to find out. James is whooping it up over Scala as Java's successor. Yes, the guy who invented Groovy prefers Scala. Quite a bit:

I can honestly say if someone had shown me the Programming in Scala book by by Martin Odersky, Lex Spoon & Bill Venners back in 2003 I'd probably have never created Groovy. -- James Strachan

Damn. So he pretty much invented Groovy by mistake? Did not know about the two-year old Scala? No one mentioned it to him? Groovy got admitted to the standard in the meantime?

Well, Johnathan Edwards reinvented Python Trellis (ergo Cells) without knowing it, and I did not know about Garnet's KR or constraints -- but Groovy got adopted as official Java! You think Scala might have come up over coffee. Anyway...

Steele said Java brought the world half-way to Lisp. I do not think Lisp means what he thinks it means. Proof might be how hard it is for folks to climb out of the pit of javathink. If Java had been a stepping stone to Lisp it would have made the next step easier, not harder. But Java still cannot do closures. Please. And a quick look at closures in Scala has me thinking, omigod, they call that closures?

Clojure starts to look like a Good Move. I see it mentioned in writings on the death throes of Java and that is a big marketing win. The superwhacky thing here is that both Scala and Clojure are syntactically discontinuous from Java. Folks always thought successors had to have syntax similar to the succeeded though Dylan should have served as cautionary counter-evidence.

No, it is not the syntax. The necessary bridging element seems to be....wait for it...the Java runtime! How did that tail end up wagging the language adoption dog? But Clojure gets the nod along with Scala just for sitting atop the JRE! You people scare me.

Well, if Steele were right Clojure would prevail over Scala. Right now googlefight has Scala winning five to one. Maybe Rich Hickey can move 17% of the world 90% of the way to Lisp?

To write, or not to write?

>> By the way, to change the subject a little, who was it who said,

>> "there are no dead languages, only dead minds"?

>

> Dunno, but to change the subject even more, Socrates objected to writing

> since it deprives an idea of a mind in which it can "live". So yeah.

Interesting. "Free writing" is a form that lives within a mind but also create a permanent record and slow the mind down enough to achieve more coherence so the mind can work out hard problems. Comedy writing is necessary to trigger a laugh response because every word matters, but then the words must be delivered as if they were coming live from a mind. Exceptions are improv and semi-improv such as Eddie Izzard, of which Mr. Socrates would approve because they arise within a living mind.

I get a lot of complaints about the writing in this blog because I deliberately write as chaotically as I think. Other times I found I gave a much better talk if I read from something written beforehand precisely because otherwise the living mind is too chaotic to get the talk done in anywhere near the time available.

I was just getting ready to videotape an improvised bit to get the good bits to then pull into a fixed, written bit because I am finding good stuff comes out only if the mind is not slowed down as by free writing.

The question is whether Eddie Izzard is lazy, or if Socrates is right on this. Does Izzard do better by capturing his improv and distilling it down to a precise fixed bit, or does he do worse? Or does he just lack the ability to deliver the prepared as if it were unprepared.

We're getting pretty close to talking about programming in Lisp vs NotLisp now. Lisp programming unconstrained by static typing and blessed with a rich library once that library is mastered such that it is all at the programmer's fingertips allows the code to flow freely yet mostly correctly from a live mind even as that mind is forming the solution the code embodies. Diagram that.

I Feel A Naggum (RIP) Coming On: Quads

I sometimes begin c.l.l rants with "I feel a naggum coming on...". What is a naggum? Normally:

naggum (n): A rant along one of Erik Naggum(1965-2009)'s themes.

That might be self-referentially hopeless which is fine because that is not what I am talking about, I just thought that would be a clever title. In this case a "naggum" is a nugget of Erikian technology. First, his specification of what he called quads (see below), and my poor implementation (even further below and good luck even figuring out how to test it) .

kt

#|

From: Erik Naggum (erik@naggum.no)

Subject: Re: XML->sexpr ideas

Newsgroups: comp.lang.lisp

Date: 2004-01-19 04:24:43 PST

* Kenny Tilton

| Of course it is easy enough for me to come up with a sexpr format off

| the top of my head, but I seem to recall someone (Erik? Tim? Other?)

| saying they had done some work on a formal approach to an alternative

| to XML/HTML/whatever.

|

| True that? If so, I am all ears.

Really? You are? Maybe I didn't survive 2003 and this is some Hell

where people have to do eternal penance, and now I get to do SGML all

over again.

Much processing of SGML-like data appears to be stream-like and will

therefore appear to be equivalent to an in-order traversal of a tree,

which can therefore be represented with cons cells while the traverser

maintains its own backward links elsewhere, but this is misleading.

The amount of work and memory required to maintain the proper backward

links and to make the right decisions is found in real applications to

balloon and to cause random hacks; the query languages reflect this

complexity. Ease of access to the parent element is crucial to the

decision-making process, so if one wants to use a simple list to keep

track of this, the most natural thing is to create a list of the

element type, the parent, and the contents, such that each element has

the form (type parent . contents), but this has the annoying property

that moving from a particular element to the next can only be done by

remembering the position of the current element in a list, just as one

cannot move to the next element in a list unless you keep the cons

cell around. However, the whole point of this exercise is to be able

to keep only one pointer around. So the contents of an element must

have the form (type parent contents . tail) if it has element contents

or simply a list of objects, or just the object if simple enough.

Example: 123 would thus be represented by (foo nil "123"),

123456 by (foo nil "123" bar nil "456"), and

123456 by #1=(zot nil (foo #1# "123"

bar #1# "456")).

Navigation inside this kind of structure is easy: When the contents in

CADDR is exhausted, the CDDDR is the next element, or if NIL, we have

exhausted the contents of the parent and move up to the CADR and look

for its next element, etc. All the important edges of the containers

that make up the *ML document are easily detectible and the operations

that are usually found at the edges are normally tied to the element

type (or as modified by its parents), are easily computable. However,

using a list for this is cumbersome, so I cooked up the «quad». The

«quad» is devoid of any intrinsic meaning because it is intended to be

a general data structure, so I looked for the best meaningless names

for the slots/accessors, and decided on QAR, QBR, QCR, and QDR. The

quad points to the element type (like the operator in a sexpr) in the

QAR, the parent (or back) quad in the QBR, the contents of the element

in the QCR, and the usual pointer to the next quad in the QDR.

Since the intent with this model is to «load» SGML/XML/SALT documents

into memory, one important issue is how to represent long stretches of

character content or binary content. The quad can easily be used to

represent a (sequence of) entity fragments, with the source in QAR,

the start position in QBR, and the end position in QCR, thereby using

a minimum of memory for the contents. Since very large documents are

intended to be loaded into memory, this property is central to the

ability to search only selected elements for their contents -- most

searching processors today parse the entire entity structure and do

very little to maintain the parsed element structure.

Speaking of memory, one simple and efficient way to implement the quad

on systems that lack the ability to add native types without overhead,

is to use a two-dimensional array with a second dimension of 4 and let

quad pointers be integers, which is friendly to garbage collection and

is unambiguous when the quad is used in the way explained above.

Maybe I'll talk about SALT some other day.

--

Erik Naggum | Oslo, Norway

Act from reason, and failure makes you rethink and study harder.

Act from faith, and failure makes you blame someone and push harder.

|#

(in-package :ukt)

;;;(defstruct (juad jar jbr jcr jdr)

(defun qar (q) (car q))

(defun (setf qar) (v q) (setf (car q) v))

(defun qbr (q) (cadr q))

(defun (setf qbr) (v q) (setf (cadr q) v))

(defun qcr (q) (caddr q))

(defun (setf qcr) (v q) (setf (caddr q) v))

(defun qdr (q) (cdddr q))

(defun (setf qdr) (v q) (setf (cdddr q) v))

(defun sub-quads (q)

(loop for childq on (qcr q) by #'qdr

collecting childq))

(defun sub-quads-do (q fn)

(loop for childq on (qcr q) by #'qdr

do (funcall fn childq)))

(defun quad-traverse (q fn &optional (depth 0))

(funcall fn q depth)

(sub-quads-do q

(lambda (subq)

(quad-traverse subq fn (1+ depth)))))

(defun quad (operator parent contents next)

(list operator parent contents next))

(defun quad* (operator parent contents next)

(list operator parent contents next))

(defun qups (q)

(loop for up = (qbr q) then (qbr up)

unless up do (loop-finish)

collecting up))

(defun quad-tree (q)

(list* (qar q)

(loop for childq on (qcr q) by #'qdr

while childq

collecting (quad-tree childq))))

(defun tree-quad (tree &optional parent)

(let* ((q (quad (car tree) parent nil nil))

(kids (loop for k in (cdr tree)

collecting (tree-quad k q))))

(loop for (k n) on kids

do (setf (qdr k) n))

(setf (qcr q) (car kids))

q))

#+test

(test-qt)

(defun test-qt ()

(print (quad-tree #1='(zot nil (foo #1# ("123" "abc")

. #2=(bar #1# (ding #2# "456"

dong #2# "789")))))))

(print #1='(zot nil (foo #1# ("123" "abc")

. #2=(bar #1# (ding #2# "456"

dong #2# "789")))))

#+xxxx

(test-tq)

(defun test-tq ()

(let ((*print-circle* t)

(tree '(zot (foo ("123")) (bar (ding) (dong)))))

(assert (equal tree (quad-tree (tree-quad tree))))))

(defun testq ()

(let ((*print-circle* t))

(let ((q #1='(zot nil (foo #1# ("123" "abc")

. #2=(bar #1# (ding #2# "456"

dong #2# "789"))))))

(print '(traverse showing each type and data preceded by its depth))

(quad-traverse q (lambda (q depth)

(print (list depth (qar q)(qcr q)))))

(print `(listify same ,(quad-tree q))))

(let ((q #2='(zot nil (ding #2# "456"

dong #2# "789"))))

(print '(traverse showing each "car" and itd parentage preceded by its depth))

(print '(of data (zot (ding (dong)))))

(quad-traverse q (lambda (q depth)

(print (list depth (qar q)

(mapcar 'qar (qups q)))))))))

;;;(defun tree-quad (tree)

(defun testq2 ()

(let ((*print-circle* t))

(let ((q #2='(zot nil (ding #2# "456"

dong #2# "789"))))

(print '(traverse showing each "car" and itd parentage preceded by its depth))

(print '(of data (zot (ding (dong)))))

(quad-traverse q (lambda (q depth)

(print (list depth (qar q)

(mapcar 'qar (qups q)))))))))