What is a fexpr?!
As discussed in earlier blog posts, Programming Language design is an area of interest for Jon and me. When I came across a paper called Fexprs as the basis of Lisp function application or $vau : the ultimate abstraction, I couldn’t help but wonder what in the world a fexpr was and how it enabled “the ultimate abstraction”. That paper is a 300 odd page dissertation so I’m not going to attempt to defend or even fully explain, for that matter, its claim here but I’m hopeful that by the end of this you’ll understand what a fexpr is and how it enables things that are difficult or impossible in other languages.
My first stop, as usual, was Wikipedia:
In Lisp programming languages, 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.
(Side note: If you’re curious about the meaning behind the name “fexpr”, prepare to be dissappointed. It was created in the 1960s when the best name was the shortest name. How intuitive a name was didn’t really factor in. Nominally -expr was short for expression but it really meant function and f was just a way of saying this is a special function. You can’t say I didn’t warn you! :) )
If you, like me, were raised on imperative programming, the above definition may not have done much for you, but they provide some entry points to start teasing apart what a fexpr is.
function - If you’re reading this blog post, I’m assuming you’re at least somewhat familiar with the concept of functions. In this post, we’ll be using Lisp-style functions which include the name of the function in the parentheses instead of before them and separate arguments with spaces. It looks a bit funny at first but you’ll get used to it. e.g:
(function-name arg1 arg1) or(add 1 2) -> 3operand - the thing that’s passed into the function at the call site for example in the multiply function here “(multiply (add 2 4) (add (3 5))” the operands are (add 2 4) and (add 3 5)
argument - the evaluated value of an operand. Using that example above, the arguments to the multiply function are 6 and 8.
In most programming languages I’ve worked with (Java, JavaScript, TypeScript, C++), operands weren’t an important concept because there was the implicit assumption that the operand would be evaluated and turned into an argument before they were passed into the function.
Fexprs break that assumption and they hand control of evaluating the operands to the body of the function itself.
To understand how this might be used let’s look at a simple example in the Kernel language which is a flavor of Lisp that supports Fexprs as a first class citizen. This snippet defines an if statement using a fexpr:
1 ($define! $if 2 ($vau (x y z) env 3 ($cond ((eval x env) (eval y env)) 4 (#t (eval z env)))))
The first line just indicates that we’re naming this fexpr $if (the dollar sign is just a convention).
On line 2: $vau indicates that we’re declaring a fexpr, and that the operands shouldn’t be evaluated before being passed in.
(x y z) is the parameter list for this fexpr
env is the environment that these expressions should be evaluated in.
(Side note: vau, is the name of a Hebrew letter, if you’re familiar with the idea of using the keyword lambda to declare a non fexpr function, this is the fexpr counterpart.)
On line three, we have cond which is essentially a shorthand for a series of if/elses by specifying a series of tuples the first element being the conditional, the second being the body of the if statement. We evaluate the first operand x and then if it is true, we evaluate y.
Finally, on line four, we have the default case with the literal boolean true #t and we evaluate z.
This might seem pretty simple since this looks kind of like any other if statement but the noteworthy thing here is that we were able to define this if in the language itself. Now this if looks like any other built-in in the language but we didn’t need to write any special handling for this.
Now we can write:
1 ($if (< 3 4) 7 4)
and the result will be 7. Perhaps not the most exciting if statement but if one of these branches took a very long time to compute or had a side effect, we’d be happy that we can avoid the cost or effect of evaluating it!
Isn’t this just lazy evaluation?
When I initially read about fexprs, I thought this was basically just a fancy name for doing lazy evaluation. The answer is it depends. If you define lazy evaluation as a language implicitly delaying the evaluation of an argument until the moment that the argument is needed, the answer is no. However, if you take the broader view of lazy evaluation meaning delaying/avoiding the evaluation of something that is not necessary than then yes. In some ways, this is an idealized form of lazy evaluation since the program can delay the evaluation even further than before.
So this was a short peek into the strange world of Lisps and Fexprs. Hopefully this was interesting and able to clarify what a fexpr is. I still have another 200 pages to go in that dissertation so I imagine there’ll be more exciting stories to report in the future from Lisp-land!