3 ms·

I've been on a bit of a lisp kick recently. Coming across the description of fexprs in earlier (pre Common Lisp and Scheme) Lisp dialects was interesting to me

I've been on a bit of a lisp kick recently. Coming across the description of fexprs in earlier (pre Common Lisp and Scheme) Lisp dialects was interesting to me since it I'm familiar with uplevel and upvar in Tcl, and appears that Tcl's upvar/uplevel is closely related to Lisp's fexprs. It was interesting to see that fexprs basically give all of the power of macros, although possibly (probably?) at a performance cost due to compilation difficulties. The obvious advantage of fexprs is that they are functions and therefore can be applied or passed along as functional arguments in ways that macros cannot. I've been trying to understand why they were dropped from Common Lisp and the mainline Lisp descendants. From the comments I've seen in other locations, (and in the sibling linked paper) it seems that the performance issues of fexprs was a strong reason for the advocacy of dropping them (from Common Lisp especially). Some of the other online references that I've seen mention that perhaps fexprs would not continue to have the same degree of compilation problems in the modern lexically scoped Lisps that they had in the dynamically scoped earlier lisp dialects. One of the things that was interesting about this fragment of document was that it seems to imply that fexprs are explicitly tied to the evaluation strategy, whereas it seems like maybe macros are less intimately tied to the direct structure of the evaluator. As an aside, there are a couple of contemporary Lisp variants (PicoLisp and newLISP) that still maintain implementations of fexprs.

kazinator 6y ago
Lisp compilers assume that certain things are available at compile time, but not at run-time. These assumptions are supported by the particular set of special forms that is handled, and that set is not extensible. Fexprs make the set of special forms open-ended, and allow anything to be available at run-time. If a new special form is introduced which allows something to be dynamic which was previously static, it can cause major work in the compiler. It is not usually reasonable to do major work in the compiler for the sake of some special form that an application needs. It is not even possible unless the users have buildable sources for the compiler. One example of an important facility about which static assumptions are made is lexical scope (a.k.a. static scope). Lisp compilers use a completely different representation for the static scope from interpreters. In a lexically scoped Lisp dialect, fexprs receive the lexical environment as an argument (necessarily so). This is a run-time object, which a fexpr can easily leak to the application directly, or else indirectly (by providing semantics like looking for a variable using a run-time symbol as a key). That is like the upvar business in tcl. It relies on the existence of a searchable structure at run time, which is the antithesis of lexical scope. Still, there can be fexprs that don't require the application writer to hack he compiler. Why don't we just have those? fexprs users who want their code to compile will just have to write a macro. If they are not able to, then they don't get to compile the code. But those who want to compile the code don't want to do the work twice: why write a fexpr and a macro, if you can just write a macro? The interpreter can work with the macro expansion, just like the compiler. Application writers want to implement something once, in one way. If you implement something twice, you have to maintain both. Basically, Lisp users historically expressed the desire to compile the code without hacking the compiler, and that steered things away from fexprs toward macros. Here is a big one: macros can be functionally written even if the construct they implement is imperative. Expanding a macro can be a side-effect-free, pure operation. If it is so, you can trust it to produce he same results on the same inputs. It's often possible to check that a macro is doing the right thing just from example expansions. The expansion works right there at the call site. A fexpr carries out operations "remotely", so to speak, because it's a function. It's a function which has to receive contextual arguments and then uses an API to access the scope. The resulting code is harder to read. The (non-hygienic) macro user just performs an expansion and sees an expression like A or #:G0025, denoting the access to a variable. He or she just has to imagine that code in place of the macro call. To debug fexpr, the user has to read code that uses some API like (get-var env third-var) to do the same thing. Common Lisp's mixture of lexical and dynamic scope could cause challenges for fexprs also.
- sea6ear 6y ago
  Thanks for that response. Your explanation makes a lot of things clear that I hadn't fully parsed out from what I've been reading recently.

kazinator 6y ago

Lisp compilers assume that certain things are available at compile time, but not at run-time. These assumptions are supported by the particular set of special forms that is handled, and that set is not extensible. Fexprs make the set of special forms open-ended, and allow anything to be available at run-time. If a new special form is introduced which allows something to be dynamic which was previously static, it can cause major work in the compiler. It is not usually reasonable to do major work in the compiler for the sake of some special form that an application needs. It is not even possible unless the users have buildable sources for the compiler. One example of an important facility about which static assumptions are made is lexical scope (a.k.a. static scope). Lisp compilers use a completely different representation for the static scope from interpreters. In a lexically scoped Lisp dialect, fexprs receive the lexical environment as an argument (necessarily so). This is a run-time object, which a fexpr can easily leak to the application directly, or else indirectly (by providing semantics like looking for a variable using a run-time symbol as a key). That is like the upvar business in tcl. It relies on the existence of a searchable structure at run time, which is the antithesis of lexical scope. Still, there can be fexprs that don't require the application writer to hack he compiler. Why don't we just have those? fexprs users who want their code to compile will just have to write a macro. If they are not able to, then they don't get to compile the code. But those who want to compile the code don't want to do the work twice: why write a fexpr and a macro, if you can just write a macro? The interpreter can work with the macro expansion, just like the compiler. Application writers want to implement something once, in one way. If you implement something twice, you have to maintain both. Basically, Lisp users historically expressed the desire to compile the code without hacking the compiler, and that steered things away from fexprs toward macros. Here is a big one: macros can be functionally written even if the construct they implement is imperative. Expanding a macro can be a side-effect-free, pure operation. If it is so, you can trust it to produce he same results on the same inputs. It's often possible to check that a macro is doing the right thing just from example expansions. The expansion works right there at the call site. A fexpr carries out operations "remotely", so to speak, because it's a function. It's a function which has to receive contextual arguments and then uses an API to access the scope. The resulting code is harder to read. The (non-hygienic) macro user just performs an expansion and sees an expression like A or #:G0025, denoting the access to a variable. He or she just has to imagine that code in place of the macro call. To debug fexpr, the user has to read code that uses some API like (get-var env third-var) to do the same thing. Common Lisp's mixture of lexical and dynamic scope could cause challenges for fexprs also.

sea6ear 6y ago
Thanks for that response. Your explanation makes a lot of things clear that I hadn't fully parsed out from what I've been reading recently.