Fexpress🔗ℹ

Fexpress is a compilation-friendly fexpr language. As far as feasible, it macroexpands expressions ahead of time instead of just interpreting everything.

At some point, there may be two variants of Fexpress.

The current variant—fexpress/proof-of-concept—is intended to help demonstrate the principles at work. For this reason, it has only a minimalistic set of features, it doesn’t have deep library dependencies, and we haven’t gone to any special effort to harden its API for future stability. If the concepts that need to be demonstrated change, we might add newly needed methods to some of the generic interfaces, might allow an env? to be something more expressive or restrictive than a hash table, and so on.

The other variant of Fexpress—potentially the fexpress module proper, once it exists—could be a more full-fledged system for using fexprs in Racket programs. This variant could better preserve Racket syntax object metadata for error reporting and Racket-style hygiene, and it could introduce features like editor highlighting to show what subexpressions of a program are making unoptimized fexpr calls. We can test the limits of how seamless an addition they can be to the Racket language.

However, there’s a certain kind of seamlessness Fexpress won’t attempt: Racket’s and can’t be passed into Racket’s map, and sometimes this surprises people who expect macros to act like functions. In languages with fexprs as the default abstraction, it tends to be easy to implement and and map in such a way that this interaction succeeds. However, that amounts to a much different design for these operations, and not a better one. If Racket’s map refuses to pass its internal code to an fexpr, that’s good encapsulation of its implementation details. And Racket’s and is designed to operate on input that’s an unevaluated syntax object (along with various macroexpansion-time parameters), so if the input it receives is actually a run-time collection of positional and keyword arguments, it’s quite reasonable for it to reject that input as a likely mistake by the user. These would be good design choices even in a language that had fexprs in it, and we don’t intend to circumvent them with Fexpress.

Anyhow, the Fexpress that exists now is the simplified proof of concept. Our hope is to demonstrate that a viable strategy exists for mixing fexprs with compilation. Thanks to extension points like gen:fexpr, it could be put to some fun use, but keep in mind the instability of the API.

(TODO: Currently, there isn’t a dedicated operation for writing simple fexprs. Fexpress users can build one out of gen:fexpr, or just use makeshift-fexpr in Fexpress code directly, but let’s provide one at some point to ease the analogy between Fexpress and other fexpr-equipped languages.)

1 The Fexpress Proof of Concept🔗ℹ

This module provides an open-faced implementation of a minimalistic, experimental Fexpress language. Not all the contracts documented here are completely enforced, nor are they stable.

The building blocks provided here make the language capable of doing simple lambda calculus, with more or less efficiency depending on the use of fexpress-ilambda or fexpress-clambda. This language can be extended by implementing more gen:fexpr values in Racket, and possibly more gen:continuation-expr, gen:type+, and gen:type_ values for them to interact with.

1.1 Entrypoint🔗ℹ

An env? maps Fexpress variables to positive types that compile to references to the same variables, so this wraps up the values in specific-value/t+ and sets up their compilation behavior with at-variable/t+.

• Evaluation of Racket code, so that we can inspect what kind of Racket code Fexpress produces.

• Moments where the compiled Racket code reenters the interpreter in order to call an fexpr. These moments are worth knowing about so we can optimize them away.

1.2 Fexprs🔗ℹ

An fexpr (sometimes known as a first-class macro) is a kind of abstraction that’s existed since the earliest implementations of Lisp.

An fexpr is something in between a function and a macro. Like a function, it’s a first-class value that can do its work at run time. Like a macro, it receives its arguments unevaluated, and—at least in the better incarnations—it also receives some kind of access to its caller’s local scope with which to understand these arguments’ intended semantics.

This combination lets programmers express a few things that they can’t express with functions and macros, since fexprs can compute their results based on a synthesis of run-time information and source code information.

However, this combination generally means programs can’t be compiled effectively, because certain expressions need to be preserved as-is until run time. If a programmer wants to express a compilable program, fexprs usually get in the way of that, and the combination of macros and functions is arguably more expressive than fexprs for that task.

The Fexpress proof of concept shows how to get around this limitation by giving fexprs even more information to work with. These fexprs receive a continuation expression which contains a negative type where they can find optimization hints to apply in their behavior.

There are also positive type values, which are types that can perform some fexpr-calling behavior on behalf of their potential values. Positive types are the tool the fexpr evaluator needs to proceed into binding forms like fexpress-clambda and implement some of their behavior early, before the actual values of the variables are known. With careful programming, the remaining part of the behavior is compiled code, allowing Fexpress to express compilable programs.

(TODO: How new are the things we’re demonstrating here? Fexprs have been in active use in the newLISP, PicoLisp, and (arguably) R communities. There’s been a lot of research on compiling reflective languages, as seen in "Collapsing Towers of Interpreters." There’s also a potential connection to JIT in general, and possibly to the compilation of algebraic effect systems.)

There are many ...-continue-eval/t+ and ...-apply/t+ operations in Fexpress, and this is the one to call when the actual value of the original type is known and is definitely an fexpr that is definitely being invoked.

The given val/t+ type should be a type which evaluates to the value val.

This may be more convenient than defining an instance of gen:fexpr.

1.2.1 Fexprs for Lambda Operations🔗ℹ

When calling this fexpr, the subforms should be parseable according to parse-lambda-args.

When calling this fexpr, the subforms should be parseable according to parse-lambda-args.

The number n should be the length of arg-vars.

The arg-vars should be mutually unique.

The body should be an s-expression representing an Fexpress expression.

1.2.2 An Fexpr for Type Ascription🔗ℹ

As the following example shows, it’s possible to use fexpress-the to declare that the local variables f and g are non-fexprs. This allows their use sites to be compiled into procedure calls rather than less efficient fexpr calls:

> (define my-compose     (fexpress-eval-and-log       `(the ,(->/t_ (list (non-fexpr-value/t+))                (->/t_ (list (non-fexpr-value/t+))                  (any-value/t_)))          (clambda (f)            (clambda (g)              (clambda (x)                (f (g x))))))))

'("Evaluating Racket code:"   (lambda (env)     (lambda (-f) (lambda (-g) (lambda (-x) (#%app -f (#%app -g -x)))))))

> (logging (lambda () (((my-compose sqrt) add1) 8)))

3

If we don’t declare that g is a non-fexpr, what happens is that the call to g is compiled into an invocation of the Fexpress interpreter. In order to pass a lexical environment into that interpreter, each surrounding fexpress-clambda (or similar binding syntax) updates the local binding of env so that the bindings held in env always correspond to the lexical scope:

> (define my-less-typed-compose     (fexpress-eval-and-log       `(the ,(->/t_ (list (non-fexpr-value/t+))                (->/t_ (list (any-value/t+))                  (any-value/t_)))          (clambda (f)            (clambda (g)              (clambda (x)                (f (g x))))))))

'("Evaluating Racket code:"   (lambda (env)     (lambda (-f)       (let ((env              (hash-set* env 'f (at-variable/t+ 'f (specific-value/t+ -f)))))         (lambda (-g)           (let ((env                  (hash-set*                   env                   'g                   (at-variable/t+ 'g (specific-value/t+ -g)))))             (lambda (-x)               (let ((env                      (hash-set*                       env                       'x                       (at-variable/t+ 'x (specific-value/t+ -x)))))                 (#%app                  -f                  (begin                    ((current-fexpress-logger) "Reentering the interpreter")                    (type+-eval                     (type+-continue-eval/t+                      env                      (apply/ce '(x) (done/ce (any-value/t_)))                      (specific-value/t+ -g)))))))))))))

> (logging (lambda () (((my-less-typed-compose sqrt) add1) 8)))

"Reentering the interpreter"

3

If we don’t use fexpress-the at all, then we get the least optimized version of the code. This time, the call to f reenters the interpreter, and the call to g is just taken care of during that interpretation:

> (define my-untyped-compose     (fexpress-eval-and-log       `(clambda (f)          (clambda (g)            (clambda (x)              (f (g x)))))))

'("Evaluating Racket code:"   (lambda (env)     (lambda (-f)       (let ((env              (hash-set* env 'f (at-variable/t+ 'f (specific-value/t+ -f)))))         (lambda (-g)           (let ((env                  (hash-set*                   env                   'g                   (at-variable/t+ 'g (specific-value/t+ -g)))))             (lambda (-x)               (let ((env                      (hash-set*                       env                       'x                       (at-variable/t+ 'x (specific-value/t+ -x)))))                 (begin                   ((current-fexpress-logger) "Reentering the interpreter")                   (type+-eval                    (type+-continue-eval/t+                     env                     (apply/ce '((g x)) (done/ce (any-value/t_)))                     (specific-value/t+ -f))))))))))))

> (logging (lambda () (((my-untyped-compose sqrt) add1) 8)))

"Reentering the interpreter"

3

1.3 Continuation Expressions🔗ℹ

An Fexpress continuation expression is a representation of the syntax around the evaluating part of an Fexpress expression.

Usually, this is a series of pending fexpr applications (apply/ce) to perform in the current env?, followed by an ascribed negative type to optimize the overall result by (done/ce). Other kinds of copatterns or spine elements, like field or method accessor syntaxes, could fit in here as well.

In order to perform compilation, Fexpress fexprs usually need to know the structural details of the continuation expression that holds their arguments. Thus, when defining new continuation expressions, it’s typical to define a structure type that does more than just implement the gen:continuation-expr interface. For instance, it can also provide its predicate and field accessors as part of its intended API, or it can implement other interfaces on the side.

There are many ...-continue-eval/t+ and ...-apply/t+ operations in Fexpress, and this is the one to call when the positive type’s fexpr-calling behavior should be ignored but its values’ fexpr-calling behavior, if any, should not be ignored. This will usually result in code that consults the value at run time and makes fexpr calls to it dynamically. A positive type usually delegates to this itself when its type+-continue-eval/t+ behavior has no better idea for what to do.

1.3.1 Essential Continuation Expressions🔗ℹ

In typical code, the args to an fexpr call are usually a proper list.

1.4 Positive Types🔗ℹ

A positive type in Fexpress essentially acts like a symbolic value. Like other type systems, this kind of type designates a set of potential values. Depending on what assumptions it carries, it can produce a value (type+-eval) and/or a compilation-result? that evaluates to a value (type+-compile).

The type system in the Fexpress proof of concept exists only for the purpose of optimization, and it has only the bells and whistles that serve that purpose. In particular, this type system makes no attempt to be sound. A variable associated with a positive type can turn out to have a value that defies that type’s assumptions or has been computed in a different way than the type would have computed it.

• type+-eval

• type+-compile

• at-variable/t+

• type+-continue-eval/t+

The implementations of these methods should satisfy certain algebraic laws:

If both type+-eval and type+-compile both successfully produce results and don’t perform any side effects along the way, the evaluation result should be the same as running the compilation result with compilation-result-eval in any env? where the bindings for its free variables have their own successful and pure type+-eval and type+-compile behaviors.

The at-variable/t+ method should observe the lens laws with respect to type+-compile: The result of getting a compilation result with type+-compile after it’s been replaced with at-variable/t+ should be the same as just calling var-compile on the variable that was passed to the replacer. The result of replacing a compilation result with itself should be the same as not using at-variable/t+ at all. The result of replacing a compilation result and replacing it a second time should be the same as just skipping to the second replacement.

Any type that’s added to an env? should be transformed this way, since it’s now in scope under a dedicated name.

There are many ...-continue-eval/t+ and ...-apply/t+ operations in Fexpress, and this is the most general one; it delegates to the others.

The resulting type doesn’t carry any assumptions about the potential values’ fexpr-calling behavior. That is to say, its type+-continue-eval/t+ behavior only gives up and delegates to continuation-expr-continue-eval/t+.

1.4.1 Essential Positive Types🔗ℹ

1.5 Negative Types🔗ℹ

A negative type in Fexpress essentially acts like an optimization hint for compiling an expression of that type.

In order to perform compilation, Fexpress fexprs sometimes need to know the structural details of the negative type they’re expected to create a value in. Thus, when defining new negative types, it’s typical to define a structure type that does more than just implement the gen:type_ interface. For instance, it can also provide its predicate and field accessors as part of its intended API, or it can implement other interfaces on the side.

1.5.1 Essential Negative Types🔗ℹ

If we unpack the meaning of positive and negative types in Fexpress, this is a compilation hint for expressions that return functions. It offers the given symbolic values as approximations for the function arguments, and it offers further hints for compiling the function body.

1.6 Phases of the Language🔗ℹ

1.6.1 Representing Concepts in the Source🔗ℹ

1.6.2 The Combination Evaluator-Compiler🔗ℹ

There are many ...-continue-eval/t+ and ...-apply/t+ operations in Fexpress, and this is the one to call when a type’s potential values are assumed not to be fexprs and yet they’re definitely being invoked with an fexpr call. This is called either when a value turns out to be a non-fexpr at run time or when it’s assumed to be a non-fexpr using non-fexpr-value/t+.

The given op/t+ type should be a type which evaluates to the result of get-op.

In typical code, the args to an fexpr call are usually a proper list. This operation raises an error if they’re not.

There are many ...-continue-eval/t+ and ...-apply/t+ operations in Fexpress, and this is the one to call when the actual value being called is known and can potentially be an fexpr with its own idea of how to proceed. A positive type processing a type+-continue-eval/t+ call usually delegates to this itself when the type’s value is known at compile time, and a continuation expression processing a continuation-expr-continue-eval/t+ call usually delegates to this itself once the value is finally known at run time.

The given val/t+ type should be a type which evaluates to the value val.

There are many ...-continue-eval/t+ and ...-apply/t+ operations in Fexpress, and this is the one to call when the positive type and its values should have their custom fexpr-calling behavior ignored. Fexpress doesn’t usually ignore values’ fexpr-calling behavior like this, but since this can lead to better performance, it can be explicitly requested by using (fexpress-the ...) to ascribe a type that uses non-fexpr-value/t+.

1.6.3 Compiling to Racket🔗ℹ

The expr should be an s-expression of Racket code. It may have free variables corresponding to the var-representation-in-racket versions of the Fexpress free variables listed in free-vars. It may also have the free variable env if depends-on-env? is #t. The env variable refers to the current lexical environment. It should not have other free variables, but if it needs to refer to Racket module bindings, it may do so with an embedded identifier? syntax object.

Depending on the lexical environment using depends-on-env? can lead to performance degradation in the surrounding parts of the Fexpress program, since an up-to-date first-class environment value must be constructed whenever variables come into scope.

While we could make more extensive use of Racket syntax objects, we keep their use to a minimum here to demonstrate this language in a way that can be easily ported to other Lisp dialects and other languages with eval variants available.