5 ms·

On Pitman's “Special forms in Lisp” (2011)

56 points by HexDecOctBin 5y ago

anderspitman 5y ago
Pitman with one "T" is relatively rare. I wonder if we're relatively related.
foldr 5y ago
This is an interesting article, but it unaccountably fails to say what an fexpr is. As fexprs are not present in either Common Lisp or Scheme, only aficionados of the history of Lisp will know. Here is the definition from the Wikipedia article: > A fexpr is a function whose operands are passed to it without being evaluated. When a fexpr is called, only the body of the fexpr is evaluated; no other evaluations take place except when explicitly initiated by the fexpr.
- User23 5y ago
  That sounds a lot like a macro. Is the main difference that macros evaluate at compile time and fexprs evaluate at EVAL time? I imagine a facility like EVAL-WHEN[1] can blur the distinction. [1] http://www.lispworks.com/documentation/HyperSpec/Body/s_eval_w.htm http://www.lispworks.com/documentation/HyperSpec/Body/s_eval...
  - HexDecOctBin 5y ago
    The fundamental difference as far as I can see will be removing the distinction between macros and function. For example, (assuming parameters starting with @ are fexprs): (defun if (bool @then @else) (cond (bool (eval @then))) (t (eval @else))))
    - Jtsummers 5y ago
      The parameters aren't the fexprs, the function is the fexpr. Even bool will need to be wrapped in an eval.
  - agumonkey 5y ago
    I guess there's no more 'time' because it can happen anytime on any fexpr due to any reason.
  - dragonwriter 5y ago
    > That sounds a lot like a macro Yes, with fexprs, functions can serve as (runtime-evaluated) macros. REBOL used this (though they aren't call fexprs in REBOL) so that its functions could also serve the role of Lisp macros, and it was pretty awesome. It’s too bad that REBOL became such a dead end for nontechnical reasons.
  - sparkie 5y ago
    Macros are also not first-class, whereas fexprs are. Macros and other special forms must appear in their own name when they are called. You can't necessarily bind them to a symbol and then use that symbol in its place with the same behavior. Consider a symbol which could represent some abstract "binary function", which you might later call. You can bind functions like `add` and `mul` to this without trouble, but if you try to bind `and` or `or` to it, you might not be able to (depending on which lisp you are using). You could try to wrap the call to `and` in a function, like `(define (and* x y) (and x y))`, but this `and*` does not actually have the correct behavior, because `y` should not be evaluated if `x` evaluates to `#f` - but being a function, both arguments are evaluated implicitly. If using fexprs, this issue is non-existent. `and` and `or` are simply defined as fexprs, are first-class, and their operands are not implicitly evaluated.
- rjsw 5y ago
  If people want to see how fexprs can be implemented they could look at the Franz Lisp sources.
- afranchuk 5y ago
  Thanks for filling in the blanks. To clarify (hopefully): I think it's a bit odd to refer to fexprs as if they are an expression themselves. A language could potentially implement it as a flag on an expression to indicate how it should be evaluated, but normally one says that a language/expression has fexpr semantics, meaning that it is passed unevaluated forms. If a language has fexpr semantics, you can for instance implement both macros and "normal" functions (among many other things) in very similar ways, since the only difference is that a normal function will first evaluate its arguments and then use the results of evaluation, whereas a macro may not do that (or may conditionally evaluate them!). Hope that helps a little...
  - kazinator 5y ago
    The term FEXPR most likely refers to the fact that in the original LISP, a FEXPR is an interpreted function: it contains expressions which the interpreter must process. All the built-in functions in LISP which do the same thing are called FSUBR, and are written in machine language. For instance LET has a binding to a FSUBR, whereas a user-defined LET-like operator would be a FEXPR. While that adds a new construct to the language, it must itself be interpreted to evoke its semantics.
- tromp 5y ago
  So fexprs are just like functions in Haskell, which is lazy by default?
  - martinflack 5y ago
    I think the difference is what the function can "see." e.g. if you have x and y in the environment as variables, and call your fexpr with (max x y) as the single argument called m: (myfexpr (max x y)) In haskell, m is not calculated (i.e. "max" is not run, nor x or y consulted) until "used". But the function doesn't "know" that it's max that's waiting to run, just that m is available if needed. In a fexpr, you get something like a macro does, so you can see '(max x y) if you care to examine m, and you must call (eval m) to get the answer, but you could theoretically decide to do something else, like form a new expression if you walk m and make a decision based on the code itself (i.e. that it's a call to "max").
- lispm 5y ago
  Example on a Lisp Machine in ZetaLisp: Command: (zl:defun my-if zl:fexpr (form) (list :my-if form)) MY-IF Command: (my-if (> a b) a b) (:MY-IF ((> A B) A B)) Thus one can see that the original source of the arguments is bound to the symbol FORM as a list. A more recent language with FEXPRs seems to be the language R.
- kazinator 5y ago
  Fexprs are present in many Lisps that have an interpreter. They are just not application definable. If your interpreter processes special forms by looking up the operator symbol in a table and calling a retrieved function, that's an fexpr. If the application can wire its own entries into that table, then it can extend the language with new special forms. The original terminology in LISP was that the FSUBR was a machine-language coded special operator. When the program wired its own interpreted funtion to create a new operator, that was a called FEXPR. FEXPR is an extension of the interpreter which is itself an interpreted function. The name probably alludes to the FEXPR containing a body of expressions that must be evaluated. Whereas the machine language analog, the FSUBR, is a pure subroutine: the interpreter isn't required to process expressions inside it (though of course it calls the interpreter, as necessary).
Jtsummers 5y ago
Pitman's "Special Forms in Lisp" is available online at: https://www.nhplace.com/kent/Papers/Special-Forms.html https://www.nhplace.com/kent/Papers/Special-Forms.html If you want to see the full text of what's being rebutted in this essay.
- DonHopkins 5y ago
  Kent Pitman also wrote the "Revised Maclisp Manual (Saturday Evening Edition)" aka the "Pitmanual". https://en.wikipedia.org/wiki/David_A._Moon https://en.wikipedia.org/wiki/David_A._Moon http://www.nhplace.com/kent/publications.html http://www.nhplace.com/kent/publications.html >In 1983, I finished the multi-year task of writing The Revised Maclisp Manual (Saturday Evening Edition), sometimes known as The Pitmanual, and published it as a Technical Report at MIT's Lab for Computer Science. In 2007, I finished dusting that document off and published it to the web as the Sunday Morning Edition. http://www.maclisp.info/pitmanual/ http://www.maclisp.info/pitmanual/ Not to be confused with David Moon who wrote the "MacLISP Reference Manual" aka the "Moonual", and who co-authored the "Lisp Machine Manual" with Richard Stallman and Daniel Weinreb, which had big bold lettering that ran around the spine and back of the cover, so it was known as the "LISP CHINE NUAL" (reading only letters on the front). https://news.ycombinator.com/item?id=15185827 https://news.ycombinator.com/item?id=15185827 https://hanshuebner.github.io/lmman/title.xml https://hanshuebner.github.io/lmman/title.xml https://news.ycombinator.com/item?id=15186998 https://news.ycombinator.com/item?id=15186998 DonHopkins on Sept 6, 2017 | next [–] The cover of the Lisp Machine Manual had the title printed in all caps diagonally wrapped around the spine, so on the front you could only read "LISP CHINE NUAL". So the title was phonetically pronounced: "Lisp Sheen Nual". My friend Nick made a run of custom silkscreened orange LISP CHINE NUAL t-shirts (most places won't print around the side like that). https://www.facebook.com/photo.php?fbid=74206161754&l=54ec4efc30 https://www.facebook.com/photo.php?fbid=74206161754&l=54ec4e... I was wearing mine in Amsterdam at Dappermarkt on Queen's Day (when everyone's supposed to wear orange, so I didn't stand out), and some random hacker (who turned out to be a university grad student) came up to me at random and said he recognized my t-shirt! http://www.textfiles.com/hacking/hakdic.txt http://www.textfiles.com/hacking/hakdic.txt CHINE NUAL (sheen'yu-:l) noun. The reference manual for the Lisp Machine, a computer designed at MIT especially for running the LISP language. It is called this because the title, LISP MACHINE MANUAL, appears in big block letters -- wrapped around the cover in such a way that you have to open the cover out flat to see the whole thing. If you look at just the front cover, you see only part of the title, and it reads "LISP CHINE NUAL" toomanybeersies on Sept 7, 2017 | parent | next [–] Link to an image of the manual, for the lazy: https://c1.staticflickr.com/1/101/264672507_307376d26c_z.jpg https://c1.staticflickr.com/1/101/264672507_307376d26c_z.jpg
phoe-krk 5y ago
How do you efficiently compile a language where the lexical environment must be fully available at runtime in order to be fully accessible by an F-expression? Having any Fexpr in a form to be compiled seems to prevent a lot of possible optimizations and requires raw Lisp forms to be present so they can be passed to an Fexpr as arguments. If I read this article correctly, then it states that Fexprs can help with the speed of macroexpansion, but I see that this cost is then moved to runtime execution of Fexprs; so, since macros are meant to be expanded at compile-time, we get faster compilation, but slower runtime.
dang 5y ago
Past related threads (not about this article, but in case anyone's curious). Others? On Fexprs and Defmacro - https://news.ycombinator.com/item?id=24932701 https://news.ycombinator.com/item?id=24932701 - Oct 2020 (10 comments) On fexprs and defmacro (2011) - https://news.ycombinator.com/item?id=15209377 https://news.ycombinator.com/item?id=15209377 - Sept 2017 (3 comments) Alan Kay on Lisp and Fexprs - https://news.ycombinator.com/item?id=1125109 https://news.ycombinator.com/item?id=1125109 - Feb 2010 (15 comments)
- twoodfin 5y ago
  $vau: the ultimate abstraction - https://news.ycombinator.com/item?id=18405014 https://news.ycombinator.com/item?id=18405014 - Nov 2018 (25 comments)
gumby 5y ago
At the end of the day several things made fexprs unnecessary. One was the development of the macro which offered more powerful syntactic transformations (i.e. greater expressive power) in a simpler way. The second was that they weren’t really powerful enough to provide metasyntactic extension at runtime. You could get a lot of that power by running the macroexpander at runtime but I’ve never seen anyone do that…because who really needs it? I worked on the 3-Lisp implementation at PARC. What I realized was that while indeed it unlocked the power to write metasyntactic operations (I.e. special forms like new control flow) it turned out the same set of existing control flow operators (e.g. cond, booleans, throw) seem to be adequate. The overhead (cognitive and in the implementation) of fexprs isn’t really worth the ability to do things like lazy evaluation and generators when there are already perfectly adequate mechanisms available
- bsder 5y ago
  > The overhead (cognitive and in the implementation) of fexprs isn’t really worth the ability to do things like lazy evaluation and generators when there are already perfectly adequate mechanisms available I would argue precisely the opposite. FEXPRs went away because they were too powerful. You don't need a macro system when you have FEXPRs as it doesn't buy you anything. Compiling FEXPRs can be difficult, however. Compiling MACROs is easy because they are, by definition, bounded--they just go from source-to-source (more on this later). And everybody in Lisp-land who weren't just computation theorists were obsessed with speed back then. So, FEXPRs had to go. Tcl is very close to FEXPRs; Shutt's thesis shows it just didn't quite go far enough. In addition, Steve Russell didn't add these to Lisp just because. Every piece of code was precious back in those days. If Steve Russell added it, he had a really good reason. I mean, he didn't even invent continuations until faced with mutual recursion. "quote" is actually the interloper--not FEXPRs. Even Alan Kay saw this way back. Quoting Alan Kay: > The biggest hit for me while at SAIL in late '69 was to really understand LISP. Of course, every student knew about car, cdr, and cons, but Utah was impoverished in that no one there used LISP and hence, no one had penetrated the mysteries of eval and apply. I could hardly believe how beautiful and wonderful the idea of LISP was [McCarthy 1960]. 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. Landin and others had been able to get quotes and conds in terms of lambda by tricks that were variously clever and useful, but the flaw remained in the jewel. In the practical language things were better. There were not just EXPRs (which evaluated their arguments), but FEXPRs (which did not). My next question 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 ... So, even as far back as 1969, the fact that FEXPRs were "theoretically messy" was already causing them to be ignored. The "big thinkers" required source-to-source transformation or they couldn't publish papers--run-time interpretation need not apply. Look at how long "mutation" remained a "problem" in the theoretical computation community while FORTRAN just simply trundled along and solved people's problems. Now, think about what those same theoreticians would think about FEXPRs that takes "mutation" and turns it up to 11. The theoreticians simply banished FEXPRs rather than have to think about them.
tgbugs 5y ago
The fact that fexprs are not easily accessible in the major lisp and scheme dialects is quite unfortunate because it makes it difficult to express certain process structures. Like with all advanced language features they would have to be used carefully, but from reading Shutt's discussion of fexprs and interpreters it seems that adding them would move a language to nearly complete expressiveness. There are invariants that you would like to be able to express as part of a specification for a process where the exact implementation is unknown at compile time. Further, the exact choice of implementation may depend on the runtime results of a previous step, requiring nested fexprs. There are many processes that are more naturally expressed in this way. Consider for example trying to specify a function that transforms an environment from one where a package is not installed to one where it is installed. There are a huge number of ways that this might be implemented, and an fexpr can serve as a specification for the information that must be provided so that it can be carried out automatically, e.g. rather than specifying the name of the package, the name of the package manager, the name of the source repository, a dependency list, etc. that can all be ignored and instead a single function implementing install-package can be provided. Some of the simpler examples can be implemented using only first class functions and closures, however as soon as there are expressions where the evaluation of the arguments need to be deferred then you need fexprs.
dfox 5y ago
The main issue with fexprs is that while it is neat way to generalize straightforward interpreter it makes implementation of compiler (or in fact almost anything requiring code walking, including some more advanced macros) unnecessarily complex or even impossible. On the other hand, anything that you can do with fexprs can be implemented by macro if the macro facility offers some way of accessing the outer lexical environment (and there is not that many situations when you need that).
- sparkie 5y ago
  A key difference is that an fexpr can access its caller's dynamic environment, which obviously, must happen at runtime and cannot be reasoned about statically. There are plenty of opportunities to access the caller's environment once you get used to having the ability to do so. I find macros far less intuitive than I do Kernel's operatives, but as you've mentioned, this comes at the cost of performance with the inability to compile the code.
dmux 5y ago
Are f-expressions needed in normal-order evaluation models or only in applicative-order evaluation models? From SICP, it seems that applicative-order (evaluate the arguments and then apply) is what necessitates the need for special forms.

56 points by HexDecOctBin 5y ago

Pitman with one "T" is relatively rare. I wonder if we're relatively related.

This is an interesting article, but it unaccountably fails to say what an fexpr is. As fexprs are not present in either Common Lisp or Scheme, only aficionados of the history of Lisp will know. Here is the definition from the Wikipedia article: > A fexpr is a function whose operands are passed to it without being evaluated. When a fexpr is called, only the body of the fexpr is evaluated; no other evaluations take place except when explicitly initiated by the fexpr.

User23 5y ago
That sounds a lot like a macro. Is the main difference that macros evaluate at compile time and fexprs evaluate at EVAL time? I imagine a facility like EVAL-WHEN[1] can blur the distinction. [1] http://www.lispworks.com/documentation/HyperSpec/Body/s_eval_w.htm http://www.lispworks.com/documentation/HyperSpec/Body/s_eval...
- HexDecOctBin 5y ago
  The fundamental difference as far as I can see will be removing the distinction between macros and function. For example, (assuming parameters starting with @ are fexprs): (defun if (bool @then @else) (cond (bool (eval @then))) (t (eval @else))))
  - Jtsummers 5y ago
    The parameters aren't the fexprs, the function is the fexpr. Even bool will need to be wrapped in an eval.
- agumonkey 5y ago
  I guess there's no more 'time' because it can happen anytime on any fexpr due to any reason.
- dragonwriter 5y ago
  > That sounds a lot like a macro Yes, with fexprs, functions can serve as (runtime-evaluated) macros. REBOL used this (though they aren't call fexprs in REBOL) so that its functions could also serve the role of Lisp macros, and it was pretty awesome. It’s too bad that REBOL became such a dead end for nontechnical reasons.
- sparkie 5y ago
  Macros are also not first-class, whereas fexprs are. Macros and other special forms must appear in their own name when they are called. You can't necessarily bind them to a symbol and then use that symbol in its place with the same behavior. Consider a symbol which could represent some abstract "binary function", which you might later call. You can bind functions like `add` and `mul` to this without trouble, but if you try to bind `and` or `or` to it, you might not be able to (depending on which lisp you are using). You could try to wrap the call to `and` in a function, like `(define (and* x y) (and x y))`, but this `and*` does not actually have the correct behavior, because `y` should not be evaluated if `x` evaluates to `#f` - but being a function, both arguments are evaluated implicitly. If using fexprs, this issue is non-existent. `and` and `or` are simply defined as fexprs, are first-class, and their operands are not implicitly evaluated.
rjsw 5y ago
If people want to see how fexprs can be implemented they could look at the Franz Lisp sources.
afranchuk 5y ago
Thanks for filling in the blanks. To clarify (hopefully): I think it's a bit odd to refer to fexprs as if they are an expression themselves. A language could potentially implement it as a flag on an expression to indicate how it should be evaluated, but normally one says that a language/expression has fexpr semantics, meaning that it is passed unevaluated forms. If a language has fexpr semantics, you can for instance implement both macros and "normal" functions (among many other things) in very similar ways, since the only difference is that a normal function will first evaluate its arguments and then use the results of evaluation, whereas a macro may not do that (or may conditionally evaluate them!). Hope that helps a little...
- kazinator 5y ago
  The term FEXPR most likely refers to the fact that in the original LISP, a FEXPR is an interpreted function: it contains expressions which the interpreter must process. All the built-in functions in LISP which do the same thing are called FSUBR, and are written in machine language. For instance LET has a binding to a FSUBR, whereas a user-defined LET-like operator would be a FEXPR. While that adds a new construct to the language, it must itself be interpreted to evoke its semantics.
tromp 5y ago
So fexprs are just like functions in Haskell, which is lazy by default?
- martinflack 5y ago
  I think the difference is what the function can "see." e.g. if you have x and y in the environment as variables, and call your fexpr with (max x y) as the single argument called m: (myfexpr (max x y)) In haskell, m is not calculated (i.e. "max" is not run, nor x or y consulted) until "used". But the function doesn't "know" that it's max that's waiting to run, just that m is available if needed. In a fexpr, you get something like a macro does, so you can see '(max x y) if you care to examine m, and you must call (eval m) to get the answer, but you could theoretically decide to do something else, like form a new expression if you walk m and make a decision based on the code itself (i.e. that it's a call to "max").
lispm 5y ago
Example on a Lisp Machine in ZetaLisp: Command: (zl:defun my-if zl:fexpr (form) (list :my-if form)) MY-IF Command: (my-if (> a b) a b) (:MY-IF ((> A B) A B)) Thus one can see that the original source of the arguments is bound to the symbol FORM as a list. A more recent language with FEXPRs seems to be the language R.
kazinator 5y ago
Fexprs are present in many Lisps that have an interpreter. They are just not application definable. If your interpreter processes special forms by looking up the operator symbol in a table and calling a retrieved function, that's an fexpr. If the application can wire its own entries into that table, then it can extend the language with new special forms. The original terminology in LISP was that the FSUBR was a machine-language coded special operator. When the program wired its own interpreted funtion to create a new operator, that was a called FEXPR. FEXPR is an extension of the interpreter which is itself an interpreted function. The name probably alludes to the FEXPR containing a body of expressions that must be evaluated. Whereas the machine language analog, the FSUBR, is a pure subroutine: the interpreter isn't required to process expressions inside it (though of course it calls the interpreter, as necessary).

Jtsummers 5y ago

Pitman's "Special Forms in Lisp" is available online at: https://www.nhplace.com/kent/Papers/Special-Forms.html https://www.nhplace.com/kent/Papers/Special-Forms.html If you want to see the full text of what's being rebutted in this essay.

DonHopkins 5y ago
Kent Pitman also wrote the "Revised Maclisp Manual (Saturday Evening Edition)" aka the "Pitmanual". https://en.wikipedia.org/wiki/David_A._Moon https://en.wikipedia.org/wiki/David_A._Moon http://www.nhplace.com/kent/publications.html http://www.nhplace.com/kent/publications.html >In 1983, I finished the multi-year task of writing The Revised Maclisp Manual (Saturday Evening Edition), sometimes known as The Pitmanual, and published it as a Technical Report at MIT's Lab for Computer Science. In 2007, I finished dusting that document off and published it to the web as the Sunday Morning Edition. http://www.maclisp.info/pitmanual/ http://www.maclisp.info/pitmanual/ Not to be confused with David Moon who wrote the "MacLISP Reference Manual" aka the "Moonual", and who co-authored the "Lisp Machine Manual" with Richard Stallman and Daniel Weinreb, which had big bold lettering that ran around the spine and back of the cover, so it was known as the "LISP CHINE NUAL" (reading only letters on the front). https://news.ycombinator.com/item?id=15185827 https://news.ycombinator.com/item?id=15185827 https://hanshuebner.github.io/lmman/title.xml https://hanshuebner.github.io/lmman/title.xml https://news.ycombinator.com/item?id=15186998 https://news.ycombinator.com/item?id=15186998 DonHopkins on Sept 6, 2017 | next [–] The cover of the Lisp Machine Manual had the title printed in all caps diagonally wrapped around the spine, so on the front you could only read "LISP CHINE NUAL". So the title was phonetically pronounced: "Lisp Sheen Nual". My friend Nick made a run of custom silkscreened orange LISP CHINE NUAL t-shirts (most places won't print around the side like that). https://www.facebook.com/photo.php?fbid=74206161754&l=54ec4efc30 https://www.facebook.com/photo.php?fbid=74206161754&l=54ec4e... I was wearing mine in Amsterdam at Dappermarkt on Queen's Day (when everyone's supposed to wear orange, so I didn't stand out), and some random hacker (who turned out to be a university grad student) came up to me at random and said he recognized my t-shirt! http://www.textfiles.com/hacking/hakdic.txt http://www.textfiles.com/hacking/hakdic.txt CHINE NUAL (sheen'yu-:l) noun. The reference manual for the Lisp Machine, a computer designed at MIT especially for running the LISP language. It is called this because the title, LISP MACHINE MANUAL, appears in big block letters -- wrapped around the cover in such a way that you have to open the cover out flat to see the whole thing. If you look at just the front cover, you see only part of the title, and it reads "LISP CHINE NUAL" toomanybeersies on Sept 7, 2017 | parent | next [–] Link to an image of the manual, for the lazy: https://c1.staticflickr.com/1/101/264672507_307376d26c_z.jpg https://c1.staticflickr.com/1/101/264672507_307376d26c_z.jpg

phoe-krk 5y ago

How do you efficiently compile a language where the lexical environment must be fully available at runtime in order to be fully accessible by an F-expression? Having any Fexpr in a form to be compiled seems to prevent a lot of possible optimizations and requires raw Lisp forms to be present so they can be passed to an Fexpr as arguments. If I read this article correctly, then it states that Fexprs can help with the speed of macroexpansion, but I see that this cost is then moved to runtime execution of Fexprs; so, since macros are meant to be expanded at compile-time, we get faster compilation, but slower runtime.

dang 5y ago

Past related threads (not about this article, but in case anyone's curious). Others? On Fexprs and Defmacro - https://news.ycombinator.com/item?id=24932701 https://news.ycombinator.com/item?id=24932701 - Oct 2020 (10 comments) On fexprs and defmacro (2011) - https://news.ycombinator.com/item?id=15209377 https://news.ycombinator.com/item?id=15209377 - Sept 2017 (3 comments) Alan Kay on Lisp and Fexprs - https://news.ycombinator.com/item?id=1125109 https://news.ycombinator.com/item?id=1125109 - Feb 2010 (15 comments)

twoodfin 5y ago
$vau: the ultimate abstraction - https://news.ycombinator.com/item?id=18405014 https://news.ycombinator.com/item?id=18405014 - Nov 2018 (25 comments)

gumby 5y ago

At the end of the day several things made fexprs unnecessary. One was the development of the macro which offered more powerful syntactic transformations (i.e. greater expressive power) in a simpler way. The second was that they weren’t really powerful enough to provide metasyntactic extension at runtime. You could get a lot of that power by running the macroexpander at runtime but I’ve never seen anyone do that…because who really needs it? I worked on the 3-Lisp implementation at PARC. What I realized was that while indeed it unlocked the power to write metasyntactic operations (I.e. special forms like new control flow) it turned out the same set of existing control flow operators (e.g. cond, booleans, throw) seem to be adequate. The overhead (cognitive and in the implementation) of fexprs isn’t really worth the ability to do things like lazy evaluation and generators when there are already perfectly adequate mechanisms available

bsder 5y ago
> The overhead (cognitive and in the implementation) of fexprs isn’t really worth the ability to do things like lazy evaluation and generators when there are already perfectly adequate mechanisms available I would argue precisely the opposite. FEXPRs went away because they were too powerful. You don't need a macro system when you have FEXPRs as it doesn't buy you anything. Compiling FEXPRs can be difficult, however. Compiling MACROs is easy because they are, by definition, bounded--they just go from source-to-source (more on this later). And everybody in Lisp-land who weren't just computation theorists were obsessed with speed back then. So, FEXPRs had to go. Tcl is very close to FEXPRs; Shutt's thesis shows it just didn't quite go far enough. In addition, Steve Russell didn't add these to Lisp just because. Every piece of code was precious back in those days. If Steve Russell added it, he had a really good reason. I mean, he didn't even invent continuations until faced with mutual recursion. "quote" is actually the interloper--not FEXPRs. Even Alan Kay saw this way back. Quoting Alan Kay: > The biggest hit for me while at SAIL in late '69 was to really understand LISP. Of course, every student knew about car, cdr, and cons, but Utah was impoverished in that no one there used LISP and hence, no one had penetrated the mysteries of eval and apply. I could hardly believe how beautiful and wonderful the idea of LISP was [McCarthy 1960]. 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. Landin and others had been able to get quotes and conds in terms of lambda by tricks that were variously clever and useful, but the flaw remained in the jewel. In the practical language things were better. There were not just EXPRs (which evaluated their arguments), but FEXPRs (which did not). My next question 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 ... So, even as far back as 1969, the fact that FEXPRs were "theoretically messy" was already causing them to be ignored. The "big thinkers" required source-to-source transformation or they couldn't publish papers--run-time interpretation need not apply. Look at how long "mutation" remained a "problem" in the theoretical computation community while FORTRAN just simply trundled along and solved people's problems. Now, think about what those same theoreticians would think about FEXPRs that takes "mutation" and turns it up to 11. The theoreticians simply banished FEXPRs rather than have to think about them.

tgbugs 5y ago

The fact that fexprs are not easily accessible in the major lisp and scheme dialects is quite unfortunate because it makes it difficult to express certain process structures. Like with all advanced language features they would have to be used carefully, but from reading Shutt's discussion of fexprs and interpreters it seems that adding them would move a language to nearly complete expressiveness. There are invariants that you would like to be able to express as part of a specification for a process where the exact implementation is unknown at compile time. Further, the exact choice of implementation may depend on the runtime results of a previous step, requiring nested fexprs. There are many processes that are more naturally expressed in this way. Consider for example trying to specify a function that transforms an environment from one where a package is not installed to one where it is installed. There are a huge number of ways that this might be implemented, and an fexpr can serve as a specification for the information that must be provided so that it can be carried out automatically, e.g. rather than specifying the name of the package, the name of the package manager, the name of the source repository, a dependency list, etc. that can all be ignored and instead a single function implementing install-package can be provided. Some of the simpler examples can be implemented using only first class functions and closures, however as soon as there are expressions where the evaluation of the arguments need to be deferred then you need fexprs.

dfox 5y ago

The main issue with fexprs is that while it is neat way to generalize straightforward interpreter it makes implementation of compiler (or in fact almost anything requiring code walking, including some more advanced macros) unnecessarily complex or even impossible. On the other hand, anything that you can do with fexprs can be implemented by macro if the macro facility offers some way of accessing the outer lexical environment (and there is not that many situations when you need that).

sparkie 5y ago
A key difference is that an fexpr can access its caller's dynamic environment, which obviously, must happen at runtime and cannot be reasoned about statically. There are plenty of opportunities to access the caller's environment once you get used to having the ability to do so. I find macros far less intuitive than I do Kernel's operatives, but as you've mentioned, this comes at the cost of performance with the inability to compile the code.

dmux 5y ago

Are f-expressions needed in normal-order evaluation models or only in applicative-order evaluation models? From SICP, it seems that applicative-order (evaluate the arguments and then apply) is what necessitates the need for special forms.