Parenthetically (Ambitious Evaluation // A New Reading of an Old Issue) Speaking (with Kent M. Pitman)

Much has been written about Lazy Evaluation in Lisp--less about the other end of the spectrum--Ambitious Evaluation. Ambition is a very subjective concept, though, and if you have some preconceived idea of what you think an Ambitious Evaluator might be about, you might want to set it aside for a few minutes because this probably isn't going to be what you expect.

A Familiar Question

It all started in 1986 when I was on staff at the MIT AI Lab and an undergrad studying Lisp asked me why the following piece of code didn't ``work'':

  (PROGN (SETQ *READ-BASE* 8.) 10)
  => 10.  ; not 8.

I chuckled for a moment with the kind of easy superiority that I have since learned to take as a sign that it's me, not the person I'm answering questions for, that really has something to learn.

I answered the question in the obvious way, explaining how of course Lisp has to read the entire form into memory before it can execute any of it. So by the time the expression above has been processed by READ and is ready to have EVAL called, it is too late for any change to the setting of *READ-BASE* to affect it. The student was mostly happy with the explanation, but the more I thought about it, I was not.

Increasingly, I've always found that the phrase ``of course'' is bandied about far too much, especially in computer science, a ``science'' which sometimes deals in provable facts (like algorithmic complexity) but that often deals in much more subjective, near-religious issues (like ``Fred implemented it this way, and Fred is generally right on such matters so everyone should do the same.'') as if they were facts.

Too often in computer science, I think, we assume that the first person to implement something had a lock on The Right Way To Think About ItTM, and we define any expectation to the contrary as an obvious illustration of why the person with that expectation is a novice and we're experts. It's not always so, and often enough so that I think we need to make a more regular practice of recognizing and questioning our design assumptions. What distinguishes experts from novices is not that they make the choices, but that their choices will provoke fewer questions and their choices will tend to stand up better to those questions that do come along afterward.


In the late 1970's and early 1980's, a technology arose at MIT, which many referred to informally as ``lisp machine style rubout handling''. It allowed a very useful modularity that fully separates parser technology from rubout handling (or general-purpose input editing). Since that time, this technology has become widespread in Lisp-based systems that do rubout handling.

To see why fully separating parsing from input editing is important, consider the following program that parses a word from a stream of input:

  (DEFVAR *WORD-DELIMITERS* '(#\Newline #\Space #\, #\.))

  (DEFUN READ-A-CHAR ()  ; This function will make sense later.

      (LOOP (LET ((C (READ-A-CHAR)))
	      (WRITE-CHAR C STR)))))

This function will work as expected when reading from non-interactive streams where there is no need for rubout handling, but if a user typing text makes a mistake, this will attempt to accumulate Rubout characters along with other characters as part of the string to be accumulated, rather than using them to repair preceding typographical errors.

To make Rubout characters work interactively, the following naive solution presents itself:

  (DEFVAR *WORD-DELIMITERS* '(#\Newline #\Space #\, #\.))

  ;;; In real code, a character like #\Rubout would be used for the
  ;;; `delete-character' character, and #\Control-U or #\Clear-Input might be
  ;;; used for the `delete-line' character.  For this article, using printing
  ;;; characters will make things clearer.

  (DEFUN READ-A-CHAR ()  ; To be explained soon.

  ;;; In a real system, this would call out to display operations to make
  ;;; the character disappear.  But for this article, this will be clearer.
    (FORMAT T "[~C]" CHAR))

    (LET ((CHARS '()))
		     (POP CHARS))
		     (SETQ CHARS '()))
		     (PUSH CHAR CHARS)))))))

Contrasting READ-A-WORD-1 and READ-A-WORD-2, we see several bad effects of including rubout handling within the definition of the word reader function itself:

In order to avoid these problems, lisp machine style rubout handling uses a modularity of full separation between input editing, in which a parser function is passed as an argument to a rubout handler, as in:


The simplest form of a rubout handler is one that simply prompts for input and then permits an activation character (such as Return or Enter) that parsing should begin. The chief problems with this solution are these:

If we could make rubout handling occur at the same time as parsing, then error detection could be made to occur at a point of error.

The Magic Revealed

``How can a program that has no understanding of rubout be magically transformed into one that does by a function which cannot see its internals?'' The answer lies in how this function gets characters from the input stream. It's not really magic--just a little ``slight of handler.''

In a real system, INVOKE-RUBOUT-HANDLER establishes an input stream which has a special method for READ-CHAR which returns characters only if they are not editing characters. After all, there is no difference between reading from a file and reading from the terminal of someone who happens never to type an incorrect character.

But what happens when an editing character is typed? In that case, rather than return normally, the stream operation for READ-CHAR throws out of the call to READ-CHAR, past the call to READ-A-WORD-1, and all the way to INVOKE-RUBOUT-HANDLER. Secretly, we now learn, that this READ-CHAR has also been remembering all of our input since we started. It then performs the editing on its remembered characters, and it restarts the read in a way that first reads characters from the remembered (and now edited) sequence of characters until it is ready for terminal input again. From the user's point of view, it is as if the editing process backed up or was changed, but really it has been started over with fewer or different characters.

Because the mechanisms for extending a stream are complicated and implementation dependent, the code I'll show here will illustrate the behavior by instead redefining the READ-A-CHAR function we've been using. Calls to READ-A-CHAR will represent the operation on the rubout-handling stream, and calls to Common Lisp's READ-CHAR will represent calls to the underlying non-rubout-handling stream. Doing the examples this way should mean you can run this code in any Common Lisp implementation:


    (LET ((*INPUT-SEEN-STACK* '())



		  (T ;; Must be done editing.

  ;;; Normally, this would be a different method on READ-CHAR, but we're just
  ;;; indirecting through a different function name for presentational simplicity.
	   (LET ((C (PEEK-CHAR NIL)))
		    (READ-CHAR) ;for effect


Given all of this code, one might expect an interaction like:

  => "beta"

The Rubout Handler Meets #.

By extension of what we've seen, if you either imagine that READ was written with READ-A-CHAR instead of READ-CHAR or imagine a version of INVOKE-RUBOUT-HANDLER which can make the right kind of stream so that native READ-CHAR can be called, then it works to do:


But what happens when we use #. in conjunction with READ using this style of rubout handler? Consider the expression:


The instant you type the ``)'' on the (PRINT 'BAR) expression, you will see BAR. But moreover, each time you're in non-editing mode and type Rubout, the next time you type a non-editing character it will restart the read and you'll see the BAR printed again! This is because as soon as you type a non-editing character, the READ restarts and the #.(PRINT 'BAR) will be reexecuted.

Ambitious Evaluation, Revisited

Armed with all of this information, we can finally revisit my original point about the design decisions inherent in a Read-Eval-Print loop. We are taught that Lisp will do:


but it's important to understand nature doesn't call for this behavior. It's just a choice. We could, for example, do:


On the other hand, this would only restart while you were typing so would give the same result. But could we write a variant of this which would co-routine EVAL and READ so that expressions were evaluated the instant enough information was available to evaluate them, rather than later? The answer is yes. I call such a facility an Ambitious Evaluator, and I offer a toy definition of a function called EVAL-WHILE-READING as a proof of concept.

A Long-Overdue Apology

One interesting consequence of using an Ambitious Evaluator is the following:

=> 8.  ; not 10.

So to that unnamed undergraduate, whose name I have sadly forgotten, I hereby publicly apologize for having ever said ``of course, the answer has to be 10.'' That turns out to have been a naive response on my part. I should perhaps have said, ``Because Lisp made the design choice of separating the reader from the evaluator, the result happens to be 10.'' There were other possible choices, as is almost always the case if you look closely enough.

It was wrong of me to have so hastily dismissed the possibility that there were other points of view. I still believe that 10, not 8, is a better value for this to return, because I believe that separate, modular definitions of READ and EVAL are superior to a combined definition--for reasons similar to why I believe rubout handling and parsing should be separated. And of course modularity is good.

An Aside about Conditions

In our sample rubout handler above, we didn't really show how lisp machine style rubout handling offers more timely correction of errors. To see how that would work, consider that a command like Rubout is a voluntary admission on the part of the user that a syntax error has occurred--one the evaluator might not notice until later. In some cases, however, the user might not be aware that an error has occurred but the parser might. In that case, the parser can cooperate with the rubout handler to force the user involuntarily into a mode in which editing is required. This might be done by:


		  :FORMAT-STRING :FORMAT-CONTROL) ;ignore CLtL2/dpANS-CL difference

This would permit the rubout handler to notice conditions relevant to parsing errors and permit user intervention. For example, we might modify the definition of our rubout handler as follows:

    (LET ((*INPUT-SEEN-STACK* '())
				#'(LAMBDA (C)
				    (THROW 'EDIT-CHARACTER-TYPED)))) ;white lie

Using such a modified rubout handler, any reader errors would be detected at the time they occurred, and an opportunity to recover from them would be immediately available:

  (invoke-rubout-handler #'eval-while-reading)
  (cond ((zerop 3) (
  This COND branch failed.
  Don't bother typing the body of the failing clause, huh? It's boring.
  %[(]) (t 3))
  => 3


My Ambitious Evaluator has really no practical value at all, really--unless you're writing a column for Lisp Pointers. And even then, someone's already done that topic so it's not much good there either.

My real goal here was partly to expose people to the way parsers and input editors are usually modularized in Lisp. And it was also partly to keep us all reminded that the reason we do things the way we do (e.g., separating input editing from parsing, and separating READ from EVAL) is not because it's the only way to do things, but because it's one of many design choices we had.

The world is full of choices. Sometime an examination of the choices leads you to the same conclusion as you'd have arrived at without examining them. But looking over all of your options when making a design decision is always a good idea if you can spare the time.


Andy Latto, Becky Spainhower, and Chris Stacy read drafts of this paper, and provided much useful feedback. It's likely that people somewhere have written papers on Ambitious Evaluation that attach a different, more serious, meaning to the topic. If so, I'd like to thank them in advance for having a sense of humor about the whimsy nature of my Ambitious Evaluator.

Proof of Concept: An Ambitious Evaluator

This is code that I wrote for fun in 1986. I've dusted it off slightly and updated the syntax so it runs in Common Lisp:
    (LOOP (WRITE-CHAR #\Newline)
	((NOT (MEMBER CHAR '(#\Space #\Tab #\Return)))
      (#\) (PARSE-ERROR "Close paren seen where not expected."))
      (#\' (READ-A-CHAR) (READ-LITERAL))
      (#\( (READ-A-CHAR)
	       (LET ((FN (READ-LITERAL)))
	(COND ((EQL VALUE *PAREN*) (PARSE-ERROR "Wrong number of args to SETQ"))
	      (T (SETQ RV (SET VAR VALUE)))))))
		 (T (PARSE-ERROR "Wrong number of args to QUOTE")))))
	   (IGNORE-REST-OF-LIST "You already passed the succeeding COND branch.
  Save yourself some work and just close off the COND, huh?")))
	((EQL C #\)))
      (COND ((EQL C #\()
	       (IF WIN? (RETURN VALUE))))
	    (T (PARSE-ERROR "Ill-formed COND clause.")))))
  (DEFUN IGNORE-REST-OF-LIST (&OPTIONAL (MSG "Just close off the list.
  I'm ignoring stuff from here on at this level anyway."))
	     (COND ((EQL C #\)) (READ-A-CHAR) NIL)
		   (T (PARSE-ERROR MSG)))))
	       ((EQL FORM *PAREN*))))))
			(IGNORE-REST-OF-LIST "This COND branch failed.
  Don't bother typing the body of the failing clause, huh? It's boring.")
	 (L '() (CONS FORM L)))
	((EQL FORM *PAREN*) ;DEFUN's body can't run until args available in a call
  (DEFUN BEEP (KIND) KIND)  ;Replace with something useful if you like.
  (DEFUN READ-LITERAL ()  ;Doesn't do whole job, but enough for this sample.
		    ((AND (NOT (ALPHANUMERICP C)) (NOT (FIND C ".+-*/=><")))
		     (UNREAD-A-CHAR C))
		  (WRITE-CHAR C S))))))

Published in hardcopy in Lisp Pointers, Volume VIII, Number 2, May-August 1995.

Hardcopy version: Copyright © 1995, Kent M. Pitman. All rights reserved.

Web version: Copyright © 1997, Kent M. Pitman. All rights reserved.