Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CE/ https://forest.topos.site/ocl-00CE /ocl-00CE/ F-expressions “F-expressions” is my uncreative name for a new lower house syntax for programming language experimentation. The “f” stands for “flexible”, “functional”, or any other flattering word starting with “f”. I believe that there have been other things in the past called f-expressions (when you google f-expression you get documentation for django queries), but it doesn't look like it is too overloaded. Here is an implemented parser for f-expressions in Rust, and here are some examples of using f-expressions in a language. Currently, the exact specification for f-expressions is in flux as I incorporate them into various PL experiments, but this document should give an overview of the design principles and motivation behind f-expressions that should remain relatively stable into the future. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CF/ https://forest.topos.site/ocl-00CF /ocl-00CF/ Review of the concept of bicameral syntax In the Bicameral, Not Homoiconic blog post, Shriram Krishnamurthi claims that the power of Lisp lies not in the specific choice of s-expressions (e.g., the parenthetical notation), but rather in the fact that a parser for lisp is split into two parts. The first part, the “lower house” syntax, is just a uniform tree. The second part, the “upper house” syntax, operates on that tree to extract the abstract syntax tree of the actual language that one cares about. For example, in the lower house syntax, (defn (f x y) (+ x y)) doesn't have any special meaning, and is treated the same as (nfed (f x y) (+ x y)) but in the upper house syntax (defn (f x y) (+ x y)) is parsed into the abstract syntax for a function definition, while (nfed (f x y) (+ x y)) is the application of the function nfed to the arguments (f x y) and (+ x y). One point of having a lower house syntax is that you can re-use the same parser/lexer (or what Krishnamurthi calls reader/scanner) across many languages, which makes developing languages much easier. But another point is that macros in your language can operate on the raw lower-house syntax, which allows adding syntactic constructs which previously did not correspond to any upper-house abstract syntax. Examples of languages with lower house/upper house syntaxes that are not s-expressions include: Julia Nim Rhombus Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CP/ https://forest.topos.site/ocl-00CP /ocl-00CP/ Some problems with s-expressions While bicameral syntax is nice, there are some things that are lacking about the s-expression realization of bicameral syntax. First of all, we have been trained through years of schooling to expect infix operators. Also, precedences for infix operators can save a lot of parentheses: I can write a * b + c instead of (+ (* a b) c). Secondly, having a more varied syntax allows conveying more information in less space. I'd rather have [a, b] than (tuple a b), not in the least because the introduction of commas give another opportunity to reduce parentheses: I can write [a + 1, b] instead of (tuple (+ a 1) b). But finally, and in my opinion most importantly, in s-expression syntax one must always have memorized a big long list of words which “don't behave like normal”. E.g. in order to understand (foo a b), one must know whether foo is a function or a special form or a macro, which requires loading the entire contex of the code into your brain. One of the motivations behind f-expressions is to realize the benefits of s-expressions while still addressing the concerns from above. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CG/ https://forest.topos.site/ocl-00CG /ocl-00CG/ The principles of f-expressions F-expressions were designed to be as simple as possible, while still affording more expressivity than s-expressions. Their design is a natural outgrowth of the following principles. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CH/ https://forest.topos.site/ocl-00CH /ocl-00CH/ Each syntactic construct means only one thing principle In many languages, the basic syntactic constructs (parentheses, brackets, etc.) are massively overloaded. For instance, parentheses in python are used for Grouping: (x + y) is the same as x + y Function application: f(x) is not the same as f x Tuples: (x,) is not the same as (x) In f-expressions, we strive to as much as possible minimize overloading. This is an overarching principle that drives many of the other principles. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CJ/ https://forest.topos.site/ocl-00CJ /ocl-00CJ/ Juxtaposition is application principle We support the ML-style version of function application, where f x is f applied to x. This produces the App1 syntax node in FExp0. Incidentally, this is also how field access works: a.x is parsed as a applied to .x (which is a field literal). We take this idea from narya. In order so that f a.x b.x parses as f (a .x) (b .x) instead of f a .x b .x we say that application without an intervening space binds tighter than application with an intervening space. Similarly, f a[1] b[1] would parse the same as f (a [1]) (b [1]). Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CL/ https://forest.topos.site/ocl-00CL /ocl-00CL/ Customizable binary operators principle We support arbitrary binary operators. These have a lower precedence than function application, so f x + g x is the same as (f x) + (g x). Binary operators produce the App2 syntax node in FExp0. The f-expression parser is parametrized over a table of precedences and associativities for binary operators, so that a user of the parser can choose how to resolve the ambiguities of code like x + y == z (we recommend the user to follow established conventions for common binary operators, but this is ultimately a matter for the language designer). In a language based on f-expressions, one may wish some binary operators to be special syntactic constructs, and others to be used as functions. We support this by allowing the user to designate some operators as “keyword operators” and others as “variable operators”. Finally, using ` one can make any binary operator into a normal variable, so that `+ 1 2 is the same as 1 + 2. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CI/ https://forest.topos.site/ocl-00CI /ocl-00CI/ Parentheses are used for grouping principle The only use of parentheses is to clarify grouping, so that we can write expressions like 5 * (2 + 1) which is parsed different than 5 * 2 + 1 = (5 * 2) + 1. As a consequence, parentheses never produce a new syntax node, they just change the parsing of existing syntax. Also, parentheses are always idempotent: (e) always has the same meaning as ((e)). Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CK/ https://forest.topos.site/ocl-00CK /ocl-00CK/ Field and tag literals principle In order to support records and tagged unions, we have field .x and tag 'cons literals, which produce the Field and Tag syntax nodes respectively. These work with the application syntax, so field access of a record r is r .x and tagged union construction for a linked list would be 'cons x xs. But language designer could choose to enhance the interpretation of these, so .x on its own could elaborate to r ↦ r.x, and 'pumpkin could elaborate to an interned symbol type. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CM/ https://forest.topos.site/ocl-00CM /ocl-00CM/ Square brackets for tuples principle There are two ways to make lists of syntax nodes in f-expressions: square brackets and curly brackets. Between square brackets, elements must be divided by commas, for instance [a, b, c]. This corresponds to the Tuple syntax node in FExp0. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CN/ https://forest.topos.site/ocl-00CN /ocl-00CN/ Curly brackets for records and blocks principle Curly brackets are the second way to make lists of expressions (the first being square brackets). Between curly brackets, expressions are separated by semicolons. Curly bracket expressions come in two variants: records and blocks. A record has a trailing semicolon, so it looks like {a = 1; b = 2;}. A block does not have a trailing semicolon, so it looks like {a = 1; b = 2; a + b}. The intuition is that blocks are syntactic sugar for {a = 1; b = 2; ret = a + b; }.ret. Thus, curly brackets may be used for both record construction and let bindings. Owen Lynch 2025 3 26 https://forest.topos.site/ocl-00CO/ https://forest.topos.site/ocl-00CO /ocl-00CO/ Primitives and specials principle Following Some problems with s-expressions, we use a reserved syntax to denote language builtins and special forms. Specifically, words starting with @ like @addU32 are intended to be used for language builtins, which is inspired by zig. These should be like ordinary functions, which follow normal evaluation rules, but just happen to be implemented by the compiler rather than implemented in user code. Words starting with like are intended to be used for special forms, which do not behave like functions and might totally reinterpret syntax. For instance, pattern matching might be implemented like: ..., 'nil => ... ]]]> which is not the application of a function to the arguments 'cons x xs => ..., 'nil => .... References Shriram Krishnamurthi 2024 https://forest.topos.site/krishnamurthi-2024-bicameral/ https://forest.topos.site/krishnamurthi-2024-bicameral /krishnamurthi-2024-bicameral/ Bicameral, Not Homoiconic Reference https://parentheticallyspeaking.org/articles/bicameral-not-homoiconic/ Context Backlinks Related Contributions