shivers@A.GP.CS.CMU.EDU (Olin Shivers) (09/22/90)
Some of the recent techniques discussed on the Scheme Digest remind me of a document I wrote back in 1983 about programming style in Lisp. I hand this document out to all my beginning students each year when I teach Intro Lisp. I make an effort to sketch out some of the academic underpinnings behind each technique I present, to give them some feeling for the intellectual origins of the ideas. Most intro students have never heard of Knuth, Hoare, Steele, et al., so it's an opportunity to explain what these people stand for. In any event, this is how I try to inculcate a sense of style in new generations of programmers. After all, novices don't have any bad habits to unlearn, and you have a chance to get in there and really shape them. By the way, all the examples shown are real franz lisp, and were taken from a transcript of a real execution trace. Mapping them over to Scheme is pretty straightforward; the fundamental ideas apply to either language. I hope the readers out on the net will find these techniques useful in their production coding. Yours for cleaner code, -Olin =============================================================================== Stylish Lisp programming techniques. As the size of software systems being created and -- more importantly -- maintained increases, it becomes more important than ever to write clean, robust, modular programs. Hoare's "Emperor's New Clothes" is a spectre that haunts anyone engaged in the task of creating complex software systems today. And in a future that promises automatic generation and verification of programs, programming constructs and techniques that have simple, rigorous semantics will be of primary importance to help these intelligent tools function. In light of this, I've put together a short list of lisp programming techniques that increase the clarity, robustness, and elegance of your code. Some have been floating around for years, but I don't think they've ever been collected in one place. So have fun... Technique n-2: Even though dynamically scoped lisps lack the ability to close a function over some piece of local state, we can get the same effect with clever manipulation of quoted constants inside a function. Consider the following function, ELEMENT-GENERATOR. On every call, it side effects a quoted list which is part of its definition. Thus, each time we call it, it returns the next element in its state list. > (defun element-generator () (let ((state '(() . (list of elements to be generated)))) ;() sentinel. (let ((ans (cadr state))) ;pick off the first element (rplacd state (cddr state)) ;smash the cons ans))) ELEMENT-GENERATOR > (element-generator) LIST > (element-generator) OF > (element-generator) ELEMENTS > (element-generator) TO > (element-generator) BE > (element-generator) GENERATED It is a simple matter to generalise this function to take an argument, which, if non-nil, is the new list to smash into STATE's cdr. Thus we can determine at runtime which list ELEMENT-GENERATOR will generate its elements from. Technique n-1: Some purists, concerned with style and readability, will object to the above function, claiming that it is difficult to perceive what is going on. They have a point, which leads us to the following technique. We can write a generator as a macro, where all the generator's state is represented explicitly as arguments to the macro. The macro simply expands into its next incarnation, displacing its old instantiation, and returns its true computation, quoted if need be. Consider, for instance, a generator for the positive integers. Every time we evaluate it, we want to get the next integer. When the evaluator tries to evaluate (GEN-COUNTER 5), it replaces itself with (GEN-COUNTER 6) in the body of the program, and returns 5. This is the sort of thing the functional programming advocates are referring to when they talk about making the state of a system explicit in the arguments. Note that this macro rewrites itself, which is what Steele is referring to in the Lambda papers when he describes macros as "syntactic rewrite rules." > (defun gen-counter macro (x) ;X is the entire form (GEN-COUNTER n) (let ((ans (cadr x))) ;pick the ans out of (gen-counter ans) (rplaca (cdr x) ;increment the (gen-counter ans) form (+ 1 ans)) ans)) ;return the answer > ;this prints out the numbers from 0 to 9. (do ((n 0 (gen-counter 1))) ((= n 10) t) (princ n)) 0.1.2.3.4.5.6.7.8.9.T > Technique n: The dogma of structured programming frowns on the use of all-powerful constructs such as GOTO in favor of more restricted constructs such as WHILE and nested IF. We can take this even one step farther -- producing comparable gains in clarity -- if we take advantage of our ability to pass circular list structure to the evaluator. An unconditional loop implemented by a PROGN with a circular tail is surely more copacetic and pleasing to the eye than a Lisp DO, with all its complex syntax. We can further replace conditional loops with COND's whose clause bodies are actually circular pointers back to the top of the loop. Note, of course, that this is a much more powerful technique than simple WHILE-DO, enabling us to generate clean solutions to Knuth's examples of loops hard to implement with previous structured programming imperative constructs. Looping with circular progs: > (defmacro circularize (&rest forms) ;replace the forms with (cons 'progn (nconc forms forms))) ;a circular list of the forms. CIRCULARIZE > (let ((a 0)) ;Simple increment-and-print loop (circularize (princ a) ;Indentation is important (setq a (+ a 1)))) ;for clear code! 0.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27. 28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52 .53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.7 7.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.96.97.98.99.100.10 If we implement all our branching and looping this way, we can remove the very notion of looping from EVAL, who never has to worry about anything but following "sequential" list structure. This simplification of EVAL naturally brings consequent efficiency and performance benefits. Some short-sighted individuals will point out that these programming techniques, while certainly laudable for their increased clarity and efficiency, would fail on compiled code. Sadly, this is true. At least two of the above techniques will send most compilers into an infinite loop. But it is already known that most lisp compilers do not implement full lisp semantics -- dynamic scoping, for instance. This is but another case of the compiler failing to preserve semantic correctness. It remains the task of the *compiler implementor* to adjust his system to correctly implement the source language, rather than the user to resort to ugly, dangerous, non-portable, non-robust "hacks" in order to program around a buggy compiler. I hope this provides some insight into the nature of clean, elegant Lisp programming techniques. -Olin Shivers
gateley@rice.edu (John Gateley) (09/23/90)
In article <9009220456.aa01422@mc.lcs.mit.edu> shivers@A.GP.CS.CMU.EDU (Olin Shivers) writes:
Technique n-1:
<self modifying code>
This technique can cause problems - what if you need to fix a bug and
reload the file; how do you make sure the counter is reset to the
appropriate number? This problem is exacerbated (my big word for the
week) by multiple files. Suppose you make one of these macros
available as part of a general macro pagkage, and a programmer uses
one of these macros for two different purposes. The counter will be
interleaved between the two, which is not what he wants.
Technique n:
<loops implemented as circular lists>
A minor point here: you claim that this allows loops to be implemented
efficiently (because there is no explicit branch instruction I think).
However, a compiler which recognizes loops (and all the ones I know
about recognize them from more normal constructs) has the ability to
do many optimizations on them. In addition, the branch instruction
that you think you are saving is not really saved - it is still
present in the branch of the interpreter loop which is running.
Some short-sighted individuals will point out that these programming
techniques, while certainly laudable for their increased clarity and
efficiency, would fail on compiled code.
Okay, call me short sighted, I don't care :^).
Sadly, this is true. At
least two of the above techniques will send most compilers into an
infinite loop. But it is already known that most lisp compilers do
not implement full lisp semantics -- dynamic scoping, for instance.
This is no longer true - consider Common Lisp. All CL compilers do
implement dynamic scoping (and it's not even hard). In fact, it is
possible to write a Lisp compiler which can handle the two techniques
given above. The self modifying code raises some questions about what
exactly the semantics of macros are, but it is still doable. Catching
recursive lists is easily done (similar to *print-circle* of CL) and
then the compiler has a handle on the looping structure.
John
gateley@rice.edu
--
Edweena went to Calumet and left from there to college the
she took along her porcupine whose name was known as knowledge res
Now their relationship was filled with pangs of loving hunger ide
the porcupine would question all but all she knew was slumber nts