Fexpress🔗 i

1.1Entrypoint🔗 i

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.2Fexprs🔗 i

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.3Continuation Expressions🔗 i

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.4Positive Types🔗 i

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.5Negative Types🔗 i

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.6Phases of the Language🔗 i