3 ms·

According to the wiki article on fexprs, they lost favor because they make it hard to statically determine whether a function call evaluates its parameters, whi

by skulk 2y ago

According to the wiki article on fexprs, they lost favor because they make it hard to statically determine whether a function call evaluates its parameters, which makes it hard for a compiler to optimize. > At the 1980 [Conference], Kent Pitman presented a paper "Special Forms in Lisp" in which he discussed the advantages and disadvantages of macros and fexprs, and ultimately condemned fexprs. His central objection was that, in a Lisp dialect that allows fexprs, static analysis cannot determine generally whether an operator represents an ordinary function or a fexpr — therefore, static analysis cannot determine whether or not the operands will be evaluated. In particular, the compiler cannot tell whether a subexpression can be safely optimized, since the subexpression might be treated as unevaluated data at run-time. I imagine this issue would persist in a compiled concatenative language. However, I don't think Joy is trying to be particularly fast or efficient.

kazinator 2y ago
Static analysis can tell what forms are invoking an fexpr and which are function calls. It's not got different from knowing which are macros. That problem can be solved. The main problem is that a language with fexprs is inherently not compilable. A second problem is that for some fexprs, compilation semantics cannot be found. A fexpr definition adds a new special operator to an interpreter. The existence of fexprs means that the repertoire of special operators is open-ended. But a compiler depends on there being a fixed set of special operators known in advance. For each kind of form the compiler has a case, which implements the translation scheme. Someone wrote that translation scheme by understanding what that special form does. When a compiler hits a form that is a fexpr invocation, there is no translation scheme for that. It is defined by piece of code in the program itself, which gives the interpretive semantics for the form. The compiler would have to read that code, understand it, and come up with a translation scheme for it from interpreted to compiled semantics. In other words do the job of a compiler writer. It requires advanced artificial intelligence. Some fexprs are not compilable. A compiler writing expert can look at the application code which defines the fexpr, and come to the conclusion that the code doesn't make sense outside of the interpreted world. Fexprs that can be compiled correspond to those forms which can be written as macros. A strategy is possible whereby for each fexpr, the application must supply a macro definition, if that application is to be compilable. The interpreter will use the fexpr, and the compiler will instead expand the macro and use that. But what is the point. You have to maintain two implementations of the same thing. Interpreters can use macros just fine. Fexprs do have an advantage over macros: lack of hygiene issues. The local variables in a fexpr are clearly in a different lexical environment from the variables of the form that it operates on/with. The fexpr function has the lexical environment of the fexpr form as an argument. When the interpreter invokes a fexpr, it hands the fexpr the current lexical environment, and the fexpr form. Whenever the fexpr code needs to evaluate some part of that form, like a variable reference, it explicitly calls eval, and passes eval that lexical environment. In no way does that get mixed up with the interpretation of the fexpr itself. There can be no capture issue. An fexpr would never need gensyms, or contain a mistake you cannot use them. Macros also don't have hygiene issues between their own variables and those in the generated code. But fexprs can you use their own variables as runtime temporaries to hold intermediate values needed by the calculation that they are interpreting. Macros cannot use their own variables this way because they are not executing at run time. They have to introduce variables into the generated code. These variables are then in the same lexical environment as that code and must be given unique symbols in order to hide these introduced variables, protecting them from conflicts. Some newcomers into the Lisp world still become fascinated by fexprs for, I suspect, mainly this reason. The lack of hygiene concerns somehow gives fexprs a kind of dignified air so to speak, like they are clean and fundamental. This view is further bolstered by that any macro could be a fexpr, but the converse isn't true. There's a kind of magic in allowing interpreter code the dynamically extended interpreter in arbitrary ways, seemingly bounded only by the limits of computation.
- MrMcCall 2y ago
  Seriously, thank you very much for that excellent breakdown. I never really got into Lisp, as I preferred imperative programming with C et al, but it looks like my preference is for my programming language requiring up-front a complete specification of the semantics of the program, i.e. no runtime dynamic parsing of strings into code or the like. From your description, it looks like the Lisp guys codified (NPI) how to mix static and dynamic abilities into the same language, thus uncovering the analysis problems for how the dynamic parts can be processed with respect to their interface with its static core. Thanks again. Learning something like this is a wonderful way to start my day in this troubled world. Peace be with you, and best of luck in your endeavors!
- tonyg 2y ago
  > Static analysis can tell what forms are invoking an fexpr and which are function calls. It's not got different from knowing which are macros. That problem can be solved. I don't think this is the case. Consider Kernel's ($lambda (f) (f (+ 3 4))) Is `f` a fexpr or a closure? We cannot know until runtime.
  - Xmd5a 2y ago
    Can you elaborate ? How do you figure it out at runtime ?
    - kazinator 2y ago
      At run time, you can inspect the current binding of f to see whether it is a macro, function or whatever. In an interpreter with fexprs, it would be late like this. At the time (f ...) is being called, if it was redefined to a fexpr, we go with that. If it is still a function, we call that.
  - kazinator 2y ago
    We look it up at compile time. If it has a function binding defined at compile time, we go with that hypothesis. If it is a macro, we expand it. If it is a fexpr, we go with that hypothesis (and then do what? check if the application provides compilation semantics for the fexpr or abort.) If it's unbound, we assume that it will be function and compile accordingly. We make a note that we did this. If, by the end of the compilation unit, a definition of f has not been seen, we issue a warning. If a conflicting definition is seen, like a macro or fexpr, we also issue a warning. (We provide a macro with-compilation-unit that the programmer or their build system can use to clump together multiple files into one compilation unit for the purpose of generating these kinds of diagnostics related to definitions.) We carefully document all of this in our reference manual, in a section about how compilation semantics can differ from interpretation semantics. This isn't rocket science. Been there, done that.

by skulk 2y ago

kazinator 2y ago

Static analysis can tell what forms are invoking an fexpr and which are function calls. It's not got different from knowing which are macros. That problem can be solved. The main problem is that a language with fexprs is inherently not compilable. A second problem is that for some fexprs, compilation semantics cannot be found. A fexpr definition adds a new special operator to an interpreter. The existence of fexprs means that the repertoire of special operators is open-ended. But a compiler depends on there being a fixed set of special operators known in advance. For each kind of form the compiler has a case, which implements the translation scheme. Someone wrote that translation scheme by understanding what that special form does. When a compiler hits a form that is a fexpr invocation, there is no translation scheme for that. It is defined by piece of code in the program itself, which gives the interpretive semantics for the form. The compiler would have to read that code, understand it, and come up with a translation scheme for it from interpreted to compiled semantics. In other words do the job of a compiler writer. It requires advanced artificial intelligence. Some fexprs are not compilable. A compiler writing expert can look at the application code which defines the fexpr, and come to the conclusion that the code doesn't make sense outside of the interpreted world. Fexprs that can be compiled correspond to those forms which can be written as macros. A strategy is possible whereby for each fexpr, the application must supply a macro definition, if that application is to be compilable. The interpreter will use the fexpr, and the compiler will instead expand the macro and use that. But what is the point. You have to maintain two implementations of the same thing. Interpreters can use macros just fine. Fexprs do have an advantage over macros: lack of hygiene issues. The local variables in a fexpr are clearly in a different lexical environment from the variables of the form that it operates on/with. The fexpr function has the lexical environment of the fexpr form as an argument. When the interpreter invokes a fexpr, it hands the fexpr the current lexical environment, and the fexpr form. Whenever the fexpr code needs to evaluate some part of that form, like a variable reference, it explicitly calls eval, and passes eval that lexical environment. In no way does that get mixed up with the interpretation of the fexpr itself. There can be no capture issue. An fexpr would never need gensyms, or contain a mistake you cannot use them. Macros also don't have hygiene issues between their own variables and those in the generated code. But fexprs can you use their own variables as runtime temporaries to hold intermediate values needed by the calculation that they are interpreting. Macros cannot use their own variables this way because they are not executing at run time. They have to introduce variables into the generated code. These variables are then in the same lexical environment as that code and must be given unique symbols in order to hide these introduced variables, protecting them from conflicts. Some newcomers into the Lisp world still become fascinated by fexprs for, I suspect, mainly this reason. The lack of hygiene concerns somehow gives fexprs a kind of dignified air so to speak, like they are clean and fundamental. This view is further bolstered by that any macro could be a fexpr, but the converse isn't true. There's a kind of magic in allowing interpreter code the dynamically extended interpreter in arbitrary ways, seemingly bounded only by the limits of computation.

MrMcCall 2y ago
Seriously, thank you very much for that excellent breakdown. I never really got into Lisp, as I preferred imperative programming with C et al, but it looks like my preference is for my programming language requiring up-front a complete specification of the semantics of the program, i.e. no runtime dynamic parsing of strings into code or the like. From your description, it looks like the Lisp guys codified (NPI) how to mix static and dynamic abilities into the same language, thus uncovering the analysis problems for how the dynamic parts can be processed with respect to their interface with its static core. Thanks again. Learning something like this is a wonderful way to start my day in this troubled world. Peace be with you, and best of luck in your endeavors!
tonyg 2y ago
> Static analysis can tell what forms are invoking an fexpr and which are function calls. It's not got different from knowing which are macros. That problem can be solved. I don't think this is the case. Consider Kernel's ($lambda (f) (f (+ 3 4))) Is `f` a fexpr or a closure? We cannot know until runtime.
- Xmd5a 2y ago
  Can you elaborate ? How do you figure it out at runtime ?
  - kazinator 2y ago
    At run time, you can inspect the current binding of f to see whether it is a macro, function or whatever. In an interpreter with fexprs, it would be late like this. At the time (f ...) is being called, if it was redefined to a fexpr, we go with that. If it is still a function, we call that.
- kazinator 2y ago
  We look it up at compile time. If it has a function binding defined at compile time, we go with that hypothesis. If it is a macro, we expand it. If it is a fexpr, we go with that hypothesis (and then do what? check if the application provides compilation semantics for the fexpr or abort.) If it's unbound, we assume that it will be function and compile accordingly. We make a note that we did this. If, by the end of the compilation unit, a definition of f has not been seen, we issue a warning. If a conflicting definition is seen, like a macro or fexpr, we also issue a warning. (We provide a macro with-compilation-unit that the programmer or their build system can use to clump together multiple files into one compilation unit for the purpose of generating these kinds of diagnostics related to definitions.) We carefully document all of this in our reference manual, in a section about how compilation semantics can differ from interpretation semantics. This isn't rocket science. Been there, done that.