Comment by kazinator | Hacker News Reader

Comment by kazinator | Hacker News Reader

Parent Full thread

That exact way of being dynamic was identified as a poor idea by around the end of just the first decade of Lisp. This is all documented.

Early Lisp was able to bind an operator symbol two four kinds of procedures:

  EXPR   SUBR

  FEXPR  FSUBR

The left column is the exprs; the right subrs. The top row means "machine coded / intrinsic"; the F prefix on the bottom ones refers to interpreted mode: the F is of unclear origin. It might refer to "form" or "formula", conveying that those procedures are made of symbolic expressions, not machine code.

The subrs are just functions: arguments are evaluated and passed to them.

The exprs operate on expressions: they receive expressions unevaluated, like in Io.

Roughly speaking EXPRs implement special operators that are built into Lisp, written in assembly language.

FEXPRS are defined by the program: they add new kinds of special operators, whose actions are interpreted; they decide at run time what to do with the argument expressions.

Loosely speaking, today's mainstream Lisp dialects still have the equivalent of EXPRs (special operators) as well as SUBRs (built-in/compiled functions) as well as possibly FSUBRS (uncompiled functions in some Lisp dialects that support interpretation). The FEXPR has disappeared; it is not found in e.g. Scheme or Common Lisp.

About macros, macros can evaluate things in their own runtime. In a compiled setting, the run-time of a macro is compile time. Macros don't make decisions in the run-time of the code they expanded; macros are gone at that point. All decisions have to be expressed as generated code which refers to information available at run-time in that environment.

> This is all documented.

Things have changed. Fexprs are coming back in a big way.

You need to check out John Shutt's Kernel language https://web.cs.wpi.edu/~jshutt/kernel.html

Yes, older Lisps messed fexprs up. Kernel fixes this. The vau calculus used by Kernel is simply a lambda calculus that, unlike CBN and CBV, doesn't implicitly evaluate arguments. The rest of the calculus is the same.

What this means is you get powerful hygienic metaprogramming (arguably as powerful or even more powerful than Scheme's most advanced macro systems) at a low low price and with very elegant theoretical properties. In Kernel, hygiene is achieved simply with the usual lexical scope that's already in lambda calculus.

So vau calculus is simpler than the CBV lambda calculus used by Lisps. Because it doesn't evaluate arguments, so it does less than those calculi. And by doing less it gains the great power of being able to do hygienic metaprogramming in the same calculus, without second-class contraptions like macros.

I last looked at that maybe eight years ago? The web page has undergone some updates, but the PDF paper is still from 2009.

Older Lisps didn't mess up fexprs. The developers wanted (ahead of time) compiling and moved on.

Using lexical scope in the context of fexprs is only a minor (and obvious) improvement. If fexprs made a comeback in, say, Common Lisp, it is painfully obvious they would be functions, whose parameters and locals are lexical by default.

Under a single dynamic scope, what it means is that when a fexpr is evaluating the argument code, its own local variables are possibly visible to that code. If the fexpr binds (let ((X 42) ...) and inside there it calls EVAL on an argument which contains X, that argument's X resolves to 42.

That could be fixed by using two dynamic scopes: the fexpr having one implicit dynamic scope for its own execution (perhaps newly created for each call to the fexpr), and using an explicit dynamic scope for evaluating the argument material (that scope coming in as an argument).

Under a single dynamic scope, if the number of fexprs in the system is small, they can stick to some namespace for their own variables, and all non-FEXPR routines stay out of that namespace. fexprs have to then be careful when they pass pieces of their own code to other FEXPRS.

In a program with large numbers of fexprs, symbol packages would solve the problem: there would be multiple modules providing FEXPRS, which would use identifiers in their own package. Then only fexprs in the same package could clash when they use each other, which is resolved by inspection locally in the module. (E.g. use unique symbols across all the FEXPRS.)

I don't suspect hygiene was a problem in practice; during the heyday of fexprs, there wouldn't have been programs with huge numbers of FEXPRS (let alone programs with churning third-party libraries containing fexprs). Everything would have been done locally in one site, by a small number of authors working in their own fork of Lisp as such.

Thus, I don't think this was the main problem identified of fexprs; it was really that impediment to compiling. Schutt's paper doesn't seem to attack this problem at all.

Hygiene is a non-problem; we are still cheerfully using Lisps without hygienic macros in 2023, whereas fexprs not being compilable was clearly a pain point in 1960-something already.

Lack of compilation for fexprs is:

A) An exciting research problem! Shutt himself says that he doesn't see any fundamental obstacles to compiling them. It's just that nobody has done it yet.

B) Actually not a big deal for many applications. Take PicoLisp, which has been cheerfully used in customer-facing applications for decades. It's an ultra-simple interpreter (its GC is 200 LOC https://github.com/picolisp/picolisp/blob/dev/src/gc.c ) The same architecture can be used for Kernel implementations.

We have learned a few things about compiling in the last fifty years though. The assumption that fexpr thwart compilation is not well founded.

Enjoying the discussion. Here’s a related paper: https://docplayer.net/137462966-Towards-jit-compilation-for-...

I think this is the same paper, docplayer is not looking great on mobile. Will read it, thanks! https://static.csg.ci.i.u-tokyo.ac.jp/papers/10/zakirov-jsss...

Covers the right sort of thing. It makes a guess at what a function call will be, inlined that guess, and if it turned out to be wrong restarts from the start of the function in the interpreter. Doesn't explicitly call out the function calling convention but guarded inlining has much the same effect.

Maybe worth noting that inlining a fexpr is semantically very close to expanding a macro. Identical if symbol renaming is done the same way for each.

> Things have changed. Fexprs are coming back in a big way.

I agree that Lisp dropped the ball on fexpr. It seems to be a combination of dynamic scoping, well founded performance concerns and some conflation of syntax and semantics. The special forms must appear under their own names thing is a related performance hack.

Lisp no longer has performance concerns. SBCL is excellent. Speculative JIT techniques would roll right over the "is this a function or a fexpr?" branch in apply with no trouble. I'm convinced there's no inherent overhead there.

I don't see much evidence that fexpr's are coming back though. Kernel is superb, though I'm unconvinced by the handling of cycles, but doesn't seem to be in use. Qi/shen is a similar sort of do-things-right effort with limited uptake. What do you have in mind?

My working theory is that lisp is niche enough that and a better lisp (which I contend kernel is - replacing the layers of macros with fexpr guts a lot of complexity from the language, and that was meant to be the driving motive behind Scheme) hits a subset of the first niche.

Those things take time. I am convinced that the next big Lisp dialect will be a Kernel.

Reply on news.ycombinator.com