On Pitman's „Special forms in Lisp“

Kazimir Majorinc
19th November 2011

1. Introduction

It appears that during last few years controversial concept of fexprs is actualized in Lisp community. Newlisp and Picolisp, two small, dynamically scoped Lisps supporting fexprs are actively developed and respective communities slowly, but consistently, grow. Fexprs are frequently discussed on authoritative Lambda the Ultimate web site, passionately advocated by Schemers Thomas Lord and Ray Dillinger. Related links and discussions appear in other Internet forums and blogs. Recently, John Shutt published Ph.D. thesis on programming language Kernel, his attempt to extend Scheme with fexprs, while keeping lexical scope. Shutt's ideas attracted significant attention and few efforts for implementation are reported.

On the first sight, fexprs are elegant and powerful feature. The reason for their discontinuation in most important Lisp dialects is not obvious. According to Christian Quiennec, fexprs were „put to death“ by Kent Pitman who in his 1980 conference presentation „Special Forms in Lisp“

„suggested that, in the design of future Lisp dialects, serious consideration be given to the proposition that FEXPR's should be omitted from the language altogether.“

Pitman's opinion was representative:

„It is widely held among members of the MIT Lisp community that FEXPR, NLAMBDA, and related concepts could be omitted from the Lisp language with no loss of generality and little loss of expressive power, and that doing so would make a general improvement in the quality and reliability of program-manipulating programs.“

The presentation “Special forms in Lisp” covers many fexpr related issues. Unfortunately, some relevant properties of fexprs could be misunderstood or omitted.

2. Importance of Fexprs

It appears that Pitman's conclusion cited above is more result of the counting small and practical pros and cons of fexprs than making of “the big picture.” And that is exactly where fexprs shine. That argument is expressed on particularly strong and inspiring way by Smalltalk designer Alan Kay :

„I could hardly believe how beautiful and wonderful the idea of LISP was. I say it this way because LISP had not only been around enough to get some honest barnacles, but worse, there were deep flaws in its logical foundations. By this, I mean that the pure language was supposed to be based on functions, but its most important components -- such as lambda expressions, quotes, and conds -- were not functions at all, and instead were called special forms ... My next questions was, why on Earth call it a functional language? Why not just base everything on FEXPRs and force evaluation on the receiving side when needed? I could never get a good answer...“

Fexprs really do add to the generality of the language, on particularly interesting way – by exposing the most important elements of Lisp language to processing as a first class objects, during runtime, like functions and other data are processed.

Furthermore, fexprs can replace both functions and macros, making Lisp not only more general, but also conceptually simpler, with more regular semantics. The implementation of Lisp can be, at least theoretically, smaller. Even the number of basic, built-in fexprs can be reduced, since quote is equivalent to (lambda-fexpr(x)x), if lambda-fexpr is, conveniently, fexpr version of lambda.

3. Expandability of Fexprs

Second, comparison of macros and fexprs is done in “macros in general” vs “fexprs in general” fashion. In such comparison, all macros have some desirable properties that all fexprs cannot have. Pitman wrote:

Perhaps the most important reason why macro's are important is that they offer transparency of functionality. It is possible, without evaluating the macro form, to determine what the form will do in terms of primitive lisp operations. This is true because the macro definition need not be invoked only by the evaluator.

That means, macros are expandable during compile time. Particularly, expansion allows "code walking" and various optimizations during compile time. Unlike macros, in general case, fexprs cannot be expanded at all, let alone before runtime. However, comparison is not fair, because fexprs in general are more expressive than macros in general. The macros should be compared with fexprs that could be used as an alternative.

For a given macro M, defined with

(define-macro (M v1 ...  vn) _ _ _)

we can easily define associated macro-like fexpr with

(define-fexpr (F v1 ...  vn)(eval (begin _ _ _))).

Fexpr F is equivalent to macro M in following sense: every program P that uses M, and the program P[F/ M], obtained by replacement of M with F evaluate to same result. Furthermore, if F is macro-like fexpr equivalent to macro M, we can define expansion of fexpr call (F ... ) as expansion of macro call (M ... ). Macro-like fexpr calls can be expanded during compiling, and expansion can be used in “code walkers” as well. It could be said that macros are equivalent to one class of fexprs that can be inlined and optimized during compile time.

typical macro:
(define-macro (ifnt condition
                   else-branch
                   then-branch)
  `(if ,condition
       ,then-branch
       ,else-branch))
typical fexpr:
(define-fexpr (ifnt condition
                    else-branch
                    then-branch)
    (if (eval condition)
        (eval then-branch)
        (eval else-branch))
macro-like fexpr:
(define-fexpr (ifnt condition
                    else-branch
                    then-branch)
   (eval `(if ,condition)
              ,then-branch
              ,else-branch)))

Possible objection is that compiler cannot know that particular fexpr is not used as the first class object. But programmer can do that; he only needs to recognize that fexpr can be implemented as macro. It is sound approach: programmer, generally, knows more than it can be deduced from the code he wrote. Another possible objection is that, if fexprs are used as macros, the advantage of the fexprs is lost. It is true if programmer limits himself on macro-like fexprs. But, he can also use more general fexprs – if loss of "transparence of functionality" is acceptable.

Assuming that compiler can optimize fexprs on described – indeed, very simple way – then, for every program that uses macros, there is equivalent and equally fast program that uses fexprs instead of macros. Inverse is not true. Neither one macro can replace fexpr in programs that use fexpr as the first class value. Rare Lisp dialects support the first class macros (not fexprs!), but these are not discussed here.

4. The Price of Macro Expansion

Third, although Pitman warned that macro expansion is space-demanding, the possibility that macro expansion can be time-demanding was not discussed. Usually, time required for macro-expansion is not important, because expansion is done only once, before compiling, and after that, the program is used in executable form only. However, Lisp, perhaps more than other languages, is designed to be used for generation of the code during runtime. Generated code can be evaluated using eval; in that case, macro calls are expanded during runtime. Slightly less obviously, if program generates lambda-expressions and compile (convert, coerce) these in form that can be “applied” or “funcalled” then expansion during runtime is unavoidable, even if eval isn't explicitly used.

The problem of macro expansion during runtime was known in Lisp community and some efforts were invested in solving it. See “Evolution of Lisp” for discussion. The problem can be avoided if non-expanding fexprs are used instead of macros. Surprisingly, that comparative advantage of fexprs is not well described in literature. Pitman doesn’t discuss it. Few years later, Z. Lichtman reported moderate slowdown (15%) if macros are used instead of fexprs. As shown in some earlier posts, the price can be higher.

It can be confusing that I wrote about expandable fexprs, and now, I claim that fexprs benefit from non-expanding. There is no single fexpr alternative to given macro; there are many of these. Some are expandable, and others are not.

For instance, take a look on fexpr at-least, generalized or, such that

(at-least e0 e1 ... en)

is true if and only if, well, at least e0 of expressions e1, ..., en evaluate to true. There are many ways this fexpr can be defined – some of these expand, and others do not. For instance, the first of the following two fexprs (slightly changed Newlisp) doesn’t expand, and second expands - and expansion can be done before runtime:

(define-fexpr (at-least n) (let ((en (eval n))) (doargs(i (zero? en)) (when (eval i) (dec en))) (zero? en))) (define-fexpr (at-least n) (eval (let ((central (cons 'or (map (lambda(x)(list 'and x '(inc counter) '(= counter n))) (args))))) (expand '(let((counter 0)) central (= counter n)) 'central 'n))))

As a side note (because that issue is not discussed in “Special forms”) careless use of fexprs, just like careless use of macros, might result in accidental overshadowing of variables. The solutions are similar (i.e. using gensyms or some kind of predefined “hygiene”). Shutt's approach is novel.

In “Special forms” the technique of wrapping macro around function for reduction of size of the expanded code is described:

(DEFUN f FEXPR (var) . body)
 
=>
 
(DEFUN f MACRO (FORM)
       (LIST 'EXPR-f
             (LIST 'QUOTE (CDR FORM))))

(DEFUN EXPR-f (var) . body)

The same technique can improve speed of macro expansion of the code during runtime; it alleviates the problem, but doesn’t solve it completely.

5. Conclusions

Although Pitman's article contains number of valid arguments, including some in favour of fexprs - three important arguments seem to be omitted:

  1. Lisp with fexprs has simpler, more regular and more expressive semantics than Lisp with functions, with or without macros.
  2. The existance of expandable, macro-like fexprs is not recognized. For every macro, there is equivalent expandable, macro-like fexpr with same desirable properties. Particularly, if simple optimization of expandable fexprs is applied, for every program that uses macros there is at least equally fast equivalent program that uses fexprs.
  3. In some cases, the programs using fexprs are much faster than programs using macros.

These claims constitute strong case for fexprs, particularly because one of the main arguments against fexprs was their influence on the speed of the programs.

References

  1. Kay A., The early history of Smalltalk, in: Bergin, Jr., T.J., and Gibson, R. G., History of Programming Languages - II, ACM Press, New York, and Addison-Wesley Publ. Co., Reading 1996, pp. 511-78.
  2. Burger A., The Picolisp reference, retrieved 25 October 2010.
  3. Jaffer A., SCM, Scheme implementation, retrieved 25 October 2010.
  4. Lichtman Z., Sometimes an FEXPR is better than a macro, ACM SIGART Bulletin archive, Issue 97, July 1986, pp. 20-2.
  5. Majorinc K., Challenged By Common Lispers,  On macro expansion, EVAL and generated Code, Symbols as S-exprs and hygienic FEXPRs, posts on kazimirmajorinc.blogspot.com
  6. Mueller L., Newlisp user manual and report, the post on newlisp.org, retrieved 25 October 2010.
  7. Pitman K., Special forms in Lisp, Conference Record of the 1980 Lisp Conference, Stanford University, August 25-27, 1980.
  8. Queineec, C., Lisp in small pieces, Cambridge University press, Cambridge, 1996.
  9. Shutt J. N., Abstraction in programming -- working definition, Worcester Polytechnic Institute, Worcester, 1999.
  10. Shutt J. N., S-expressiveness and the abstractive power of programming languages, W orcester Polytechnic Institute, Worcester, 1999.
  11. Shutt J. N., Revised-1 report on the Kernel programming language, Worcester Polytechnic Institute, Worcester, 2009. retrieved 25 October 2010.
  12. Shutt J. N., Fexprs as the basis of Lisp function application or $vau: the ultimate abstraction, Worcester Polytechnic Institute, Worcester, 2010.
  13. Steele, G. L., Gabriel, R. P., The evolution of Lisp, extended version, retrieved 25 October 2010.