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.
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.
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):
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.
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.
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!).
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.
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").
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).
>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.
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).
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).
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!
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 [–]
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.
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
> 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.
Thanks for explaining this. I've been wondering about why FEXPRs disappeared ever since the first time I read about them. Such a simple and elegant idea that for some reason was replaced by macros which are much harder to understand. Also explains why functions aren't lists of code fragments which you can manipulate.
>Why not just base everything on FEXPRs and force evaluation on the receiving side when needed?
PostScript is a lot like Lisp, where everything is an FEXPR. You pass around executable arrays to control flow functions like "if" and "for", and can write your own like "send".
NeWS used an object oriented programming system that was a lot like Smalltalk with multiple inheritance, which leveraged the PostScript dictionary stack so it was quite efficient. PostScript object references (independent of the object it points to) can be executable or literal. Code in PostScript is represented by executable arrays, executable names are looked up on the dictionary stack, and their corresponding values are executed (literal arrays and other objects are pushed, executable arrays have their elements executed in order, etc.)
As well as "send"ing an executable name to an object to execute a method by that name in its scope (by loading its instance/class/superclass/etc onto the dictionary stack), you could also "send" an executable array to an object to execute that code in the context of the object. (But that was not a common practice, just the way it happened to work because of how it was implemented.)
James Gosling's Emacs Mocklisp was like FEXPRs on PCP, with support for prompting the user to supply omitted arguments.
DonHopkins on May 10, 2017 | parent | context | favorite | on: Emacs is sexy
Hey at least Elisp wasn't ever as bad as Mock Lisp, the extension language in Gosling (aka UniPress aka Evil Software Hoarder) Emacs.
It had ultra-dynamic lazy scoping: It would defer evaluating the function parameters until they were actually needed by the callee (((or a function it called))), at which time it would evaluate the parameters in the CALLEE's scope.
James Gosling honestly copped to how terrible a language MockLisp was in the 1981 Unix Emacs release notes:
12.2. MLisp - Mock Lisp
Unix Emacs contains an interpreter for a language
that in many respects resembles Lisp. The primary
(some would say only) resemblance between Mock Lisp
and any real Lisp is the general syntax of a program,
which many feel is Lisp's weakest point. The
differences include such things as the lack of a
cons function and a rather peculiar method of
passing parameters.
"Rather peculiar" is an understatement. More info, links and code examples:
I was just recently writing about how PostScript is "homomorphicier" than Lisp, because it has a shorter more elegant Quine (but let's try not to think about BASIC):
Speaking of writing PostScript with PostScript, Stan also wrote an elegant PostScript Quine, which is even shorter than the Lisp Quine (PostScript is like a cross between Lisp and Forth, but homomorphic and more like Lisp actually -- but PostScript is even homomorphicier than Lisp because it has an even shorter Quine!):
> PostScript is a lot like Lisp, where everything is an FEXPR. You pass around executable arrays to control flow functions like "if" and "for", and can write your own like "send".
TECO had that property too and it made it easy to write incomprehensible code (even for those of us who grokked the syntax)
> PostScript is a lot like Lisp, where everything is an FEXPR.
I view PostScript as a Forth rather than a Lisp. That may not be correct--as I'm by no means an expert in either.
> ...because it can eval? ;)
Perty much. :)
> It had ultra-dynamic lazy scoping: It would defer evaluating the function parameters until they were actually needed by the callee (((or a function it called))), at which time it would evaluate the parameters in the CALLEE's scope.
And that hits at one of the problems that Shutt hits in his thesis, dynamic default scope (aka global variables) interacts very badly with FEXPRs (and macros and lots of other things, too).
There is a reason why everybody abandoned dynamic scoping and went to lexical scoping as soon as memory got large enough. The problem of lexical scoping is that now you have to deal with the fact that your variables need a stack. The downside of lexical scoping is the memory consumption of holding the variable bindings as recursion proceeds--that kicks up a lot of garbage to be collected and complicates your name resolution data structure. This is why Scheme was so insistent on tail calls.
Shutt deals with the scoping ambiguity by keeping the references to the environments so they can be explicitly accessed as required. Thus, your "argument evaluator" can access the required environment. Do you need the environment of the original definition? You have that as an explicit variable. Do you need the current environment? You have that as an explicit variable. Most things are "lexical scope and argument evaluation", but they don't have to be. And that's important because, as we've found out over time, if you only have one or the other, some cases don't work. (ie. short-circuit "and" likely wants the "and" from the definition environment but wants to evaluate the arguments it chooses to evaluate in the current environment)
Of course, all that costs memory and CPU (especially GC!) cycles--both of which were in short-supply in 1980 and laughably abundant in 2010 (date of Shutt's thesis).
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.
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).
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.
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.
31 comments
[ 2.7 ms ] story [ 75.2 ms ] thread> 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.
[1] http://www.lispworks.com/documentation/HyperSpec/Body/s_eval...
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.
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.
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...
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").
A more recent language with FEXPRs seems to be the language R.
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).
If you want to see the full text of what's being rebutted in this essay.
https://en.wikipedia.org/wiki/David_A._Moon
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/
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://hanshuebner.github.io/lmman/title.xml
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=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
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
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.
On Fexprs and Defmacro - https://news.ycombinator.com/item?id=24932701 - Oct 2020 (10 comments)
On fexprs and defmacro (2011) - https://news.ycombinator.com/item?id=15209377 - Sept 2017 (3 comments)
Alan Kay on Lisp and Fexprs - https://news.ycombinator.com/item?id=1125109 - Feb 2010 (15 comments)
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
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.
...because it can eval? ;)
>Why not just base everything on FEXPRs and force evaluation on the receiving side when needed?
PostScript is a lot like Lisp, where everything is an FEXPR. You pass around executable arrays to control flow functions like "if" and "for", and can write your own like "send".
NeWS used an object oriented programming system that was a lot like Smalltalk with multiple inheritance, which leveraged the PostScript dictionary stack so it was quite efficient. PostScript object references (independent of the object it points to) can be executable or literal. Code in PostScript is represented by executable arrays, executable names are looked up on the dictionary stack, and their corresponding values are executed (literal arrays and other objects are pushed, executable arrays have their elements executed in order, etc.)
As well as "send"ing an executable name to an object to execute a method by that name in its scope (by loading its instance/class/superclass/etc onto the dictionary stack), you could also "send" an executable array to an object to execute that code in the context of the object. (But that was not a common practice, just the way it happened to work because of how it was implemented.)
James Gosling's Emacs Mocklisp was like FEXPRs on PCP, with support for prompting the user to supply omitted arguments.
https://news.ycombinator.com/item?id=14312249
DonHopkins on May 10, 2017 | parent | context | favorite | on: Emacs is sexy
Hey at least Elisp wasn't ever as bad as Mock Lisp, the extension language in Gosling (aka UniPress aka Evil Software Hoarder) Emacs.
It had ultra-dynamic lazy scoping: It would defer evaluating the function parameters until they were actually needed by the callee (((or a function it called))), at which time it would evaluate the parameters in the CALLEE's scope.
James Gosling honestly copped to how terrible a language MockLisp was in the 1981 Unix Emacs release notes:
https://archive.org/stream/bitsavers_cmuGosling_4195808/Gosl...
"Rather peculiar" is an understatement. More info, links and code examples:https://news.ycombinator.com/item?id=8727085
I was just recently writing about how PostScript is "homomorphicier" than Lisp, because it has a shorter more elegant Quine (but let's try not to think about BASIC):
https://news.ycombinator.com/item?id=29929367
Speaking of writing PostScript with PostScript, Stan also wrote an elegant PostScript Quine, which is even shorter than the Lisp Quine (PostScript is like a cross between Lisp and Forth, but homomorphic and more like Lisp actually -- but PostScript is even homomorphicier than Lisp because it has an even shorter Quine!):
https://www.donhopkins.com/home/archive/NeWS/news-tape/fun/q...
TECO had that property too and it made it easy to write incomprehensible code (even for those of us who grokked the syntax)
I view PostScript as a Forth rather than a Lisp. That may not be correct--as I'm by no means an expert in either.
> ...because it can eval? ;)
Perty much. :)
> It had ultra-dynamic lazy scoping: It would defer evaluating the function parameters until they were actually needed by the callee (((or a function it called))), at which time it would evaluate the parameters in the CALLEE's scope.
And that hits at one of the problems that Shutt hits in his thesis, dynamic default scope (aka global variables) interacts very badly with FEXPRs (and macros and lots of other things, too).
There is a reason why everybody abandoned dynamic scoping and went to lexical scoping as soon as memory got large enough. The problem of lexical scoping is that now you have to deal with the fact that your variables need a stack. The downside of lexical scoping is the memory consumption of holding the variable bindings as recursion proceeds--that kicks up a lot of garbage to be collected and complicates your name resolution data structure. This is why Scheme was so insistent on tail calls.
Shutt deals with the scoping ambiguity by keeping the references to the environments so they can be explicitly accessed as required. Thus, your "argument evaluator" can access the required environment. Do you need the environment of the original definition? You have that as an explicit variable. Do you need the current environment? You have that as an explicit variable. Most things are "lexical scope and argument evaluation", but they don't have to be. And that's important because, as we've found out over time, if you only have one or the other, some cases don't work. (ie. short-circuit "and" likely wants the "and" from the definition environment but wants to evaluate the arguments it chooses to evaluate in the current environment)
Of course, all that costs memory and CPU (especially GC!) cycles--both of which were in short-supply in 1980 and laughably abundant in 2010 (date of Shutt's thesis).
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.
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).
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.