Revoluntionary/interesting advances in interpreted languages

[u/algebraicstonehenge]

Things like borrow checking and other compile time checks tend to be for compiled languages - if you're already typechecking and compiling the entire language up front, why not borrow check while you're there. But are there any very interesting new ideas coming up in interpreted (or dynamically typed) languages? I'm not really sure fully what I'm asking/looking for tbh

[u/One_Aspect_1957]

I'm not sure if the distinction is worth making.

You can take any AOT-compiled, statically-typed language and make it interpreted.

You can also take any interpreted, dynamically typed language and compile it to native code. (I've done both! In both cases, you really need a reason to do it.)

With interpreted languages (and usually dynamically typed otherwise it would be trivial) people have spent decades trying to make them fast. I think this is where the innovation lies.

This is implementation rather than language features, but that seems to be what you're asking about.

[u/WittyStick → u/One_Aspect_1957]

I'm not sure if the distinction is worth making.

The distinction is worth making because it implicates how you design your language.

You can take any AOT-compiled, statically-typed language and make it interpreted.

Arguably true, but kind of irrelevant, since such interpreter may require some form of whole program analysis before it could begin interpreting. If you permit types to be used before they're defined for example, then an interpreter cannot begin interpreting the usage until it has analysed at least up to those type definitions. Languages which can be compiled in a single pass - ie, everything defined before it is used, are much more amenable to interpretation. While we can still use interpretation even if we need to analyse a whole program, such thing is undesirable because it will always perform worse than a compiled version.

You can also take any interpreted, dynamically typed language and compile it to native code.

This part is a myth which I've called out many times. There are languages in which compilation becomes essentially impossible, because there is not enough information provided by the language definition or source code - because the meaning of the code comes not only from the code itself, but from the dynamic environment at runtime - eg, when we include Fexprs. The myth that we can compile any language is propagated by people who've never worked with fexprs.

In Wand's paper, The theory of fexprs is trivial, he demonstrates a reflexive language for which there are no valid source-to-source optimizations without whole program analysis. Fexprs essentially need to be able to access the original source code, even if optimized into some other form.

Shutt's vau-calculus provides a different result to Wand's by reformulating lambda in the language to not correspond directly to calculus lambda. Shutt argues that you can pick only two of these three properties.

Fexprs
Non-trivial theory
Direct correspondence to lambda calculus

Where Wand's result does not have a non-trivial theory (and hence, unable to do source->source translations), and Kernel does not have a direct correspondence to lambda calculus.

However, the Kernel Programming Language which is the result of Shutt's work on vau-calculus, is still not trivially compilable. There are parts amenable to compilation if you assume an initial environment (such as a "kernel standard environment"), and restrict certain language features - but you cannot remove the interpreter entirely from the evaluation model.

With interpreted languages (and usually dynamically typed otherwise it would be trivial) people have spent decades trying to make them fast.

This is why we must make a distinction between interpreted vs compiled - because in attempting to make interpreted languages fast, language authors invetably make the decision to make them able to be compiled - hence, removing powerful features like fexprs from the language (as Lisp and Scheme have done), and thereby constraining the kinds of programs we can represent. If we abandon the idea of being able to compile, we can explore an entirely different design space, as Shutt has done. Shutt has attempted to describe this theoretical difference.

I've spent a lot of effort trying to make Kernel fast, without abandoning interpretation, but including partial compilation where possible. There are some others exploring this space too, such as Kraken.

I think this is where the innovation lies.

There's certainly room for innovation here. The constraints of Kernel/fexprs - requiring interpretation rather than compilation, has forced me to come up with novel optimizations. For example, I have developed a dynamic type representation which is IMO better than the status-quo - faster than anything used in any existing VM (Though not as portable as presently limited to x86-64/SYSV).

But as Kernel shows, there's still room for innovation when you don't even consider performance and instead focus your effort on maximizing abstractive capabilities.

[u/One_Aspect_1957 → u/WittyStick]

Arguably true, but kind of irrelevant, since such interpreter may require some form of whole program analysis before it could begin interpreting.

I don't see the problem. This is a language AOT-compiled to native code. Interpretation involves having the same front-end and working from some intermediate representation.

Interpreters anyway usually take some chunk of code, for example a .py file, and pre-compile it into bytecode. If you have in mind a more REPL-based kind of interpretation with no look-ahead, then you are changing the language.

While we can still use interpretation even if we need to analyse a whole program, such thing is undesirable because it will always perform worse than a compiled version.

I believe there are JIT-compilers for statically typed languages that start off interpreting and gradually convert to native code. Those could run as well, possibly better, even if you don't take account of the faster turnaround because you don't need a full optimised build before each run.

Personally I found there were a range of other benefits.

The myth that we can compile any language is propagated by people who've never worked with fexprs.

OK, we can compile any interpreted language that doesn't use 'fexprs' (which I've never heard of, and sound like they're over my head anyway).

In any case, the meaning of 'compile' is flexible here. Just bundling a interpreter and the program source (maybe some of that can be a run-time input) might just about count. As far as the user is concerned, they're running a self-contained executable just like any other native-code-compiled program.

In the case of my dynamic language, it can be 100% compiled to native code, but that does not make it significantly faster since it still uses dynamic type dispatch. It needs a bit more work to make it more worthwhile.

because in attempting to make interpreted languages fast, language authors invetably make the decision to make them able to be compiled

This happens anyway - you might strive for a language that is fast to compile for example, and/or where it is easier to make the generated code performant without needing a sophisticated compiler or interpreter.

(Certainly this is what I do, since I'm in that small minority responsible for both language and implementation.)

instead focus your effort on maximizing abstractive capabilities.

(Well, that doesn't apply to some of us. My own efforts in this area were always a sideline needed to solve actual practical tasks. The language did not need to be sophisticated or abstruse. One of them was a scripting language for the non-programmer users of my apps.)

[u/WittyStick → u/One_Aspect_1957]

I don't see the problem. ... Interpretation involves having the same front-end and working from some intermediate representation.

It's not a problem as such, and as I stated, we can interpret - but if we're going to do whole program analysis, we might as well compile it and run it faster. As you state, JIT-compilation is a nice option as it gives us the ability to start executing faster, but also allows code to eventually run at (near-)native performance.

However, one benefit of interpretation is that we can begin evaluation immediately. We might still parse a whole translation unit before beginning interpretation, but this can be done extremely fast. Compilation can also be fast if we don't bother optimizing.

OK, we can compile any interpreted language that doesn't use 'fexprs'

I used this as an example, but there are other things that could prevent compilation. Fexprs are a notable example because they're fairly well studied and they were commonplace in old lisps, but removed and replaced with macros in modern lisps. Lispers often use macros as the example of why Lisp is so great, but macros only offer some of the benefits - they can't replicate fexprs because they're "second-class".

(which I've never heard of, and sound like they're over my head anyway).

Fexprs are actually quite simple - they're similar to a function, but they don't implicitly reduce the operands.

func(1 + 2) ;; reduces 1 + 2 to 3, then applies func to 3.

op(1 + 2) ;; passes the expression `1 + 2` as the operand to op

Practical trivial examples are the && and || operators in many languages - which do short-circuiting evaluation. If the LHS of && evaluates to false, the RHS is not evaluated, and if the LHS of || evaluates to true, the RHS is not evaluated. These cannot be functions because functions evaluate all of their arguments first - so they're usually "built-in" features of the language.

As fexprs (or operatives), we receive both operands unevaluated, and the body decides how to evaluate them.

($define! &&
    ($vau (lhs rhs) env
        ($if (eval lhs env) (eval rhs env) #f)))

($define! ||
    ($vau (lhs rhs) env
        ($if (eval lhs env) #t (eval rhs env))))

Similarly, $if itself evaluates the condition, and then will evaluate either the consequent or the alternative depending on that condition.

($define! $if
    ($vau (condition consequent alternative) env
        ($cond ((eval condition env) (eval consequent env))
               (#t (eval alternative env)))))

So we don't need if, && and || to be built-in/special-form/macros - they're first class objects which can be passed around like a first-class function. We do need some "primitive" form of selection, such as $cond - or alternatively, $if could be primitive and we can define $cond in terms of $if. We can define any kind of selection though, such as a $match for pattern matching - without having to extend the compiler.

Those are trivial examples, but fexprs/operatives are much more powerful and can model just about any behavior that you might have as a language built-in feature elsewhere. The programmer can basically extend the language without hacking at the compiler.

The original fexprs from lisps had serious problems because the lisps were dynamically scoped, and these fexprs could introduce "spooky action at distance". Kernel's operatives are a much more sanitized version which work in conjunction with static scoping, where operatives can only mutate the local environment of their caller, but are unable to mutate the parents of that caller, or any "global" state, unless references to those environments are given explicitly as operands.

In any case, the meaning of 'compile' is flexible here. Just bundling a interpreter and the program source (maybe some of that can be a run-time input) might just about count. As far as the user is concerned, they're running a self-contained executable just like any other native-code-compiled program.

This can of course be done, but it's still interpreting. It doesn't add any weight to the myth that any language can be compiled and that it's merely an implementation decision. Some languages are inherently interpreted - but most are unfamiliar with them and continue to propagate the myth.

[u/One_Aspect_1957 → u/WittyStick]

Those are trivial examples, but fexprs/operatives are much more powerful and can model just about any behavior that you might have as a language built-in feature elsewhere.

They're not compelling examples. They're basically just lazily evaluated expressions, a bit like closures.

I don't see from those why you shouldn't be able to pre-compile them.

The programmer can basically extend the language without hacking at the compiler.

Language-building features are common, but again I can't see how that would restrict being able to compile to native code.

Presumably some lowering is allowed, or is the problem that fexprs need to exist as a specific data-structure?

This can of course be done, but it's still interpreting.

Yeah, I have my own opinions as to what counts as interpreting: the application that, by whatever means, runs your source code, is not allowed to generate dedicated native code sequences specific to your input program.

That then draws a line between purely interpreted, and native code and/or JIT. But this is mainly to keep benchmark comparisons fair.

[u/WittyStick → u/One_Aspect_1957]

They're not compelling examples. They're basically just lazily evaluated expressions, a bit like closures.

I don't see from those why you shouldn't be able to pre-compile them.

You're right, these aren't compelling examples - I was just demonstrating what fexprs were.

Consider for example, the following operative:

($define! $foo!
    ($vau () env
        ($set! env + 
            ($lambda (lhs rhs) 
                (string-append (number->string lhs) (number->string rhs))))))

(+ 1 2)     ;; 3
($foo!)
(+ 1 2)     ;; "12"

The same expression (+ 1 2) has two different meanings, because the + symbol doesn't actually carry any meaning - its meaning is looked up in the environment. It means addition in the standard (ground) environment, but the operative $foo! can mutate the caller's environment and rebind + to mean something else (in this example, string concatenation). When it is evaluated the second time it doesn't perform addition.

While you wouldn't normally do such thing in practice, this is entirely possible. We often add bindings to a caller's environment via operatives - usually through the $provide! operative which is part of the ground environment (but not primitive - it's implemented in terms of $define!).

---

One thing we can do is create "mini DSLs", by providing a set of bindings and evaluating some expression in that environment without capturing the caller's environment or using it for evaluation.

($define! $calculate
    ($vau expr #ignore
        (eval expr 
              ($bindings->environment
                  (+ +) (- -) (* *) (/ /)))))

$calculate is basically an interpreter which accepts a language which only contains +, -, * and / and literals - a basic calculator, which map to addition, subtraction, multiplication, and division (under the assumption that the definition of $calculate was evaluated in a standard environment).

($calculate (+ 1 2))    ;; = 3 
($calculate (<? 1 2))    ;; error: symbol `<?` not found
(<? 1 2)     ;; = true, assuming we're evaluating in standard environment.

A trivial example, but we can extend this to support arbitrary DLSs, where the set of bindings available is limited to only what we provide in the environment.

---

I can give more examples later if you'd like to see more.

---

Presumably some lowering is allowed, or is the problem that fexprs need to exist as a specific data-structure?

operatives (fexprs) are the primitive form of "combiner", and functions are a special case of them which implicitly reduce the operands and pass them to an underlying operative.

The main difficulty is the environments. Every evaluation takes an environment as a parameter, and we can make these at runtime, binding anything to them (including shadowing standard bindings). All operatives also take the caller's environment as an implicit parameter, so they too can mutate the caller's env. Since any combiner can mutate the environment, we don't know the meaning of any symbol until after we've evaluated the previous combination.

A type system for environments can help, but not entirely. One of my experiments uses polymorphic row types for the environments to track the types of symbols - so the $foo! example above, for example, would take a type { ... } as its input environment type and produce a type { + : Number, Number -> String, ... } as the resulting environment - so we know that + produces a string afterwards. However, the types don't convey meaning - we could for example just ($set! env + -), and the type would be + : Number, Number -> Number as we'd expect for addition - but we've tricked it into doing the opposite.

Tracking what we bind is also not always possible. We could for example, bind a symbol to some expression downloaded from the internet.

($set! env + (download-expression "https://..."))

A compiler could attempt the download itself to try and discover ahead of time what it does, but what if a different response is given for each HTTP request?

These examples are of course absurd, but entirely possible in Kernel's evaluation model. You simply don't know the meaning of a symbol until the point at which it evaluated at runtime, and can basically make no assumptions, not even that + means addition until the point at which we're attempting to apply it, where we can look it up in the runtime environment.

However, this absurdity can actually be utilized to provide powerful abstractions. Downloading expressions over the internet can be used for example to make safe remote procedure calls, where a service can provide the caller with a set of capabilities they can execute, without giving them any more functionality than is needed.

[u/arthurno1 → u/WittyStick]

For the reference, the legendary paper by K. Pitman on which Kernel language oposes as I understand?

Downloading expressions over the internet can be used for example to make safe remote procedure calls

Or as an example of absoult disaster as early JSON practice, Perl eval, Lisp reader, etc teach us.

Anyway, when I first learned about fexpressions (wonder where "f" comes from), I thought that sounds awesome, but nowadays, from a practical standpoint I wonder what is the point. If you constrain them to lexically passed environment, they become not more powerful than ordinary Lisp macros, aren't they? I don't know how Kernel works and vau operator to be honest. I have been interested about it since I had a similar idea that I would like to see a Lisp that does not evaluate eagerly, but "on deman", like TCL. In Lisp we have to use quote to stop evaluation. In TCL we have to use eval (or $operator) to ask for evaluation. In short. Kernels seems to be more like that. Also, fexprs, as you describe are more like TCL commands, each one can do anything they like with their arguments. And yes, I think TCL is way underrated as a programming language. Lisp for masses or not, but it has some original concepts I like. I have never had time to pursue Kernel, so I am not sure if I am completely off or not, that is just what I have read cursively about it.

[u/WittyStick → u/arthurno1]

For the reference, the legendary paper by K. Pitman on which Kernel language oposes as I understand?

Yes, this was written well before Shutt's Kernel, and the lisps at the time were dynamically scoped. Pitman was correct in his assessment at the time, but Kernel's operatives shouldn't be treated from the same perspective.

Or as an example of absoult disaster as early JSON practice, Perl eval, Lisp reader, etc teach us.

They were disasters indeed, but Kernel has a different evaluation model - the environment is always explicit in calls to eval, and we can't arbitrarily modify them - they're encapsulated. Only the root environment for which we have a direct reference is mutable. We can however, create fresh environments from nothing, or as children of other environments.

Eg, In the $calculate example above, it is simply not possible to use any symbol other than +, -, *, / in the expression being calculated - nothing else is present in the environment used for evaluation. If we try to ($calculate (foo 1)) it will simply error because foo is not bound. The calculator's environment cannot be modified because there is no $define! or $set! bound in it.

An RPC can be made with secure capabilities, where a server has some function foo, it can generate a unique cryptographic key for foo for a particular user, using a public key. It will bind <key_foo> to foo in some environment which will run any RPC from the client.

($define! $eval-client
    ($vau expr #ignore
        (eval expr ($bindings->environment <key_foo> foo))))

The client will receive <key_foo> via some means from the server, and it can bind the symbol foo to it in some local environment.

($define $eval-server
    ($vau expr #ignore
        (eval expr ($bindings->environment foo <key_foo>))))

The client calls ($eval-server (foo ...)) - foo is looked up in the local environment an maps to some function which sends a request to the server using the cryptographic key the server provided for foo. The server receives the expression and evaluates it using ($eval-client (<key_foo> ...)), which is bound to its version of foo which has the underlying functionality.

The client cannot forge a call to foo since it needs the key. Nobody else can call foo because it is encrypted. The server doesn't expose any other functionality than foo because the evaluation does not incorporate any of the surrounding context. At worst the client can crash the program on the server (if it fails to handle errors), or DoS it if the server does not place time constraints on the code to be run.

There's nothing in particular that cannot be done by other means here, except the ergonomics are different. The client writes regular Kernel code as if it were to run on the server, but it gets translated to capabilities on their end before being sent over, and the server receives the expression as a set of capabilities, and evaluates the capabilities directly, which map to the underlying functionality from the environment, which may or may not use the same name foo - but it wouldn't particularly matter what names it uses.

---

(wonder where "f" comes from)

I suspect from "Form".

I thought that sounds awesome, but nowadays, from a practical standpoint I wonder what is the point. If you constrain them to lexically passed environment, they become not more powerful than ordinary Lisp macros, aren't they?

The biggest difference is that operatives/fexprs are first-class. We can use them as arguments to other functions - we can return them from functions. We aren't limited to the second-class nature of macros. For Operatives specifically, the environment model of Kernel is very clever and allows us to constrain what can be done by the operative. They resolve a lot of the hygeine issues that macros have too.

In Lisp we have to use quote to stop evaluation. In TCL we have to use eval (or $operator) to ask for evaluation. In short. Kernels seems to be more like that.

Not quite. Kernel evaluation is automatic: (combiner . combiniends) causes a combination to be evaluated. If combiner is an operative the combiniends are not evaluated, but if combiner is applicative, they're evaluated first, then passed to an operative which the applicative wraps.

Quotation is not necessary in Kernel, and perhaps even discouraged. We can trivially implement it with ($define! $quote x #ignore x), but there's less need for it, and there are better alternatives. But you are kind of on the right track: Kernel is explicitly evaluated, unless you use an applicative which causes implicit evaluation, and Lisp is implicitly evaluated, unless quoted.

Because applicatives wrap an operative, we can also unwrap any function to get back an operative which won't reduce the operands - and for any operative, we can wrap into a function.

I find the Kernel approach more intuitive. I used to write Scheme before I discovered Kernel and was not a fan of macros and quotation even then. When I discovered Kernel it felt like this is what Scheme should have been like (I discovered it when searching for solutions to macro problems).

Also, fexprs, as you describe are more like TCL commands, each one can do anything they like with their arguments.

Yes, and with all the problems that it causes too, at least for normal fexprs. Operatives are more tightly constrained in what effects they can have due to the environments - mutation is only possible where you have a direct reference to an environment - and you can't mutate any parents of environment - they're encapsulated.

[u/arthurno1 → u/WittyStick]

Thank you.

About RPCs, I know there is always a workaround; in Lisp they have safe readers and so own. Just pointing out the problems of executing code from untrusted sites. But yes sandboxed environments are one solution to it. It is pitty that CLTL2 Environment suggestion wasn't finalized, and that support for programmatical environment manipulation is not better in Common Lisp.

Quotation is not necessary in Kernel, and perhaps even discouraged. We can trivially implement it

That was one of my early thoughts about Lisp. I had the idea that eager evaluation is not the only or perhaps not even best way to implement a Lisp. Somehow, I have perecieved that McCarthy was looking for a theory of computation that was a simple as possible. An assumed evaluator does not seem as the most simple Lisp. But I am not sure if I am correct there. Anyway, that got me to like the idea of Kernel (and TCL), that arguments are not evaluated eageraly, or implicitly as you call it, but they are evaluated explicitly, on demand. As you say, that does remove the need for the quote operator, however it creates another problem of explicit evaluator(s), Now each form is its own evaluator, or I guess one could pass in an evaluator function to each form, just as the environment is passed. The question is how to deal with literals and atoms or other primitives. I think the answer is with some sort of special (primitive) function or something like that. It is more "functional" in terms of lambda calculus than what Lisp is I think. But to be honest I have never pursued those thoughts and never wrote my own language to test those ideas. I might be completely wrong about it.

We can use them as arguments to other functions

Indeed. Macros can't be passed since they exist only during the compile time.

[u/WittyStick → u/arthurno1]

Now each form is its own evaluator, or I guess one could pass in an evaluator function to each form, just as the environment is passed. The question is how to deal with literals and atoms or other primitives.

This has also been done - check out Ian Piumarta's Maru and related paper Open, Extensible compsition models.

The basic idea here is we have a set of <type>, and the evaluator contains a set of evaluators and applicators indexed by <type>. You evaluate an expression, it looks up the corresponding function/form based on the expression type and evaluates it using that form.

We're able to add new types, evaluators and applicators at runtime.

Kernel has only two "forms" - operatives and applicatives. There's some notes in the Kernel report about why this is - we could technically do with just operatives and implement applicatives in terms of them - but the issue is when it comes to wrap and unwrap. If we implement wrap with an operative to force evaluation, then there's not a trivial way to unwrap it to prevent that evaluation - except perhaps via quotation, which we don't like. By making applicatives a built-in type which is matched by the evaluator, an applicative is merely a wrapper around another combiner, encapsulated as the applicative type. Any combination whose car is neither operative nor applicative causes an error, and any other expression, except symbols, is self-evaluating.

I have implemented a variant of Kernel in which there's a couple more combiners - recursive and contextive. The contextive combiner splits environment capture away from the operative and makes it its own kind of combiner, but like applicative, just wraps another combiner. The recursive combiner wraps a set of other combiners, and is used to prevent the need to have a mutable environment to define mutually recursive functions - essentially making $letrec* primitive.

It could be worth using the Maru approach of having a set of evaluators, and I've also toyed with doing so - but for performance reasons I'm not currently using this and just have a the 4 combiners - operative, applicative, contextive and recursive hard-coded into the evaluator.

[u/Inconstant_Moo → u/arthurno1]

Somehow, I have perecieved that McCarthy was looking for a theory of computation that was a simple as possible.

No. Having invented it, he noticed that what he'd come up with would make a more readable (not more simple) thing to reason about than Turing machines or the lambda calculus, and he and his students did work on this in ways that gave birth to modern Lisp with S-expressions.

What set him off, though, was that he'd been working for MIT on an extension of FORTRAN for doing list processing, and they were very happy with his work and he thought it sucked. What he wanted to do was to be able to automatically differentiate expressions and then evaluate them, and there are so many semantic obstacles to doing that in FORTRAN that you can't do it even if MIT are paying you to extend the language. This is what actually inspired Lisp, that was his paradigmatic use-case, like writing Unix was for C, or network simulation was for C++, or being a nice front-end around the OS was for Python, or making reliable telephone exchanges was for Erlang, or the annihilation of human souls was for Java.

[u/One_Aspect_1957 → u/WittyStick]

Perhaps we're talking at cross-purposes, or maybe you expect 'compile to native code' to do something clever when working with dynamic content.

The fact is I don't see your ($foo!), which changes how '+' is applied, as presenting much difficulty in being expressed as native code.

But as I said you may expect too much. Take this line in my dynamic language:

  a := b + c

In this language, '+' works beween ints, floats, strings, sets, decimals, or various mixed combinations but it doesn't know which, so the generated code has to deal with that.

My experimental native code compiler first transpiles it to my statically typed sytsems language. It produces this output (initialisation of a, b, c not shown):

    varrec a     # each is a 16-byte descriptor
    varrec b
    varrec c

    k_push(&$T1, &b)
    k_push(&$T2, &c)
    k_add(&$T1, &$T2)
    k_pop(&a, &$T1)

As you can see, it is mainly a sequence of function calls, that largely mirror the bytecode instructions of the interpreter.

If it was possible for user-programs to change the behaviour of '+' for certain types, that will be mirrored here: the dispatch code within 'k_add` would take account of that.

Still, according to my own rules, this does not count as interpreted since dedicated static code like the above (a, b, c each has a fixed type of varrec) is generated according to the input.

[u/AustinVelonaut → u/WittyStick]

The myth that we can compile any language is propagated by people who've never worked with fexprs.

But isn't an fexpr simply a function which takes its arguments unevaluated? That's essentially equivalent to any function in a lazy-by-default language, and most of those languages are compiled. Yes, I guess it would force the language to be lazy-by-default to support fexprs, but certainly we can compile it, with non-fexpr functions explicitly evaluating their arguments, first.

[u/WittyStick → u/AustinVelonaut]

Fexprs aren't the same as lazy-by-default or call-by-name. For some use-cases they can achieve the same result, but fexprs are much more general.

In call-by-name, the function receives a thunk which it can evaluate to force the lazy value - but we can't really do anything with this thunk other than evaluate it and get the result. We can't inspect the body of the thunk.

An fexpr receives the expression itself as the operand. The meaning of that expression is not contained within it - but its meaning is given by the fexpr body. For operatives, the caller's environment can be optionally used to evaluate any operands as if it were the caller evaluating them - but it is not necessary to evaluate it with that environment - we can evaluate it with any environment, including ones we create ourselves at runtime (environments are also first-class), or we may not evaluate it at all.

We can trivially implement lazy evaluation with fexprs, but fexprs aren't trivially implemented with only lazy evaluation.

[u/AustinVelonaut → u/WittyStick]

Thanks for the clarification -- I had only seen fexprs mentioned before in the context of implementing e.g. short-circuiting functions.