Fast and Extensible Hybrid Embeddings with Micros DOI: 10.1145/3759537.3762696 ISBN: 979-8-4007-2162-5/25/10 Conference: Proceedings of the 26th ACM SIGPLAN International Workshop on Scheme and Functional Programming; October 12–18, 2025; Singapore, Singapore Proceedings of the 26th ACM SIGPLAN Inte

Sean Bocirnea, William J. Bowman · 2025

Read Fast and Extensible Hybrid Embeddings with Micros DOI: 10.1145/3759537.3762696 ISBN: 979-8-4007-2162-5/25/10 Conference: Proceedings of the 26th ACM SIGPLAN International Workshop on Scheme and Functional Programming; October 12–18, 2025; Singapore, Singapore Proceedings of the 26th ACM SIGPLAN Inte by Sean Bocirnea, William J. Bowman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07551.txt.

Introduction

Sean Bocirnea and 1 co-author revisit micros in 2025 as a faster route to extensible language embeddings. An embedding implements one language inside another. Macro embedding, the popular approach in Scheme-like hosts such as Racket, rewrites source syntax into source syntax and can support extensible typed languages, but compile-time performance suffers as macros stack up.

Micros instead translate syntax into an intermediate representation, an efficient internal form, and stop there, producing a deep embedding that compile-time functions can process quickly. The IR is then shallowly embedded back into source syntax. Design patterns make both the IR and its functions extensible, recovering the flexibility of macros. The authors report significantly improved compile times for extensible statically typed languages and propose new abstractions that package the patterns. The work targets language builders who need both extensibility and speed.

Catalog record

CREATORSean Bocirnea, William J. Bowman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-07551

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast and Extensible Hybrid Embeddings with Micros DOI: 10.1145/3759537.3762696 ISBN: 979-8-4007-2162-5/25/10 Conference: Proceedings of the 26th ACM SIGPLAN International Workshop on Scheme and Functional Programming; October 12–18, 2025; Singapore, Singapore Proceedings of the 26th ACM SIGPLAN International Workshop on Scheme and Functional Programming (Scheme ’25), October 12–18, 2025, Singapore, Singapore CCS: Software and its engineering Extensible languages CCS: Software and its engineering Software performance CCS: Software and its engineering Frameworks Sean Bocirnea, William J. Bowman Abstract . Macro embedding is a popular approach to defining extensible shallow embeddings of object languages in Scheme-like host languages. While macro embedding has even been shown to enable implementing extensible typed languages in systems like Racket, it comes at a cost: compile-time performance. In this paper, we revisit micros —syntax to intermediate representation (IR) transformers, rather than source syntax to source syntax transformers (macros). Micro embedding enables stopping at an IR, producing a deep embedding and enabling high performance compile-time functions over an efficient IR, before shallowly embedding the IR back into source syntax. Combining micros with several design patterns to enable the IR and functions over it to be extensible, we achieve extensible hybrid embedding of statically typed languages with significantly improved compile-time compared to macro-embedding approaches. We describe our design patterns and propose new abstractions packaging these patterns. † † cc-license: by 1. Introduction Contemporary macro systems have features for linguistic reuse and interposition, enabling macro embedding whole general-purpose languages with sophisticated static type systems as libraries ( Tobin-Hochstadt et al. 2011 ) . Macro embedding is even expressive enough to enable user-extensible dependent type systems ( Chang et al. 2017a ; Chang et al. 2020 ) . However, macro embeddings can suffer serious performance problems. Shallowly embedding object languages through macros provides an elaboration into a host language, but means there is never a direct representation of the whole embedded language program. Exposing such a representation would require stopping macro expansion at some intermediate point and inverting the usual outside-in order of macro expansion, or decompiling fully expanded programs back into an intermediate representation. This makes implementing optimizations, particularly non-local transformations, difficult or impossible. Worse, it can dramatically affect compile time. By inverting expansion order, stopping expansion, or decompiling, the eventually emitted syntax objects will be re-expanded, resulting in worst-case quadratic expansion cost, and thus quadratic time algorithms for what would otherwise be a linear time AST traversal. As we will show, this is particularly noticeable when embedding typed languages with sophisticated type systems. An alternative to shallow embedding, deep embedding, would provide a full AST that could be traversed and manipulated efficiently. Deep embeddings can even be integrated with a macro system, so that the macro system essentially provides the frontend, generating an full AST that can then be manipulated efficiently, before finally shallowly embedding back into the host language ( Ballantyne et al. 2020 ; Ballantyne et al. 2024 ) . Unfortunately, this approach gives up on the extensibility of the IR (although the source language remains macro-extensible). In this paper, we present an approach to hybrid embedding languages with good compile-time performance and extensibility of both the surface language and internal representation. We develop a taxonomy for extensibility, and use it to compare and contrast our approach with the state of the art. We revisit micros as a key abstraction for creating an extensible deeply embedded IR ( Krishnamurthi 2001 ) . Our micros target compile-time structs in Racket for an efficient AST representation. For extensible manipulation of the object language AST, we use generics to attach each compile-time function (such as the type checker) to its AST node. We use an extensibility pattern atop structs and generics to navigate the expression problem ( Wadler 1998 ) , and propose as future work two new abstractions packaging these patterns. This enables users to extend the IR both with new nodes and their compile-time functions, and override previous behaviour, similar to Racket objects but with better compile-time performance. We present a brief case-study of a dependently typed language micro embedded in Racket, extended with gradual typing, and a brief performance analysis of the type checker. 2. Related Work To understand the language embedding design space, we first survey existing tools for creating language embeddings, which we refer to as embedding language frameworks ( ELFs ). Turnstile turnstile+ ( Chang et al. 2019 ) , a dependent-type-supporting extension of the turnstile ELF described by Chang et al. 2017b , uses Racket macros to provide object language extensibility. turnstile+ encodes object language forms as macros and performs type-checking operations as object languages are macro-expanded into core Racket forms. Adding new forms is as simple as importing a base language and defining new macros for new language forms. Since Racket’s macros expander is open recursive, redefinition of old language forms is almost as easy: elide old terms in the import specification and define new terms with the same syntax. Interoperability of object languages with Racket is also easy, since everything expands into a shallow Racket embedding. While turnstile+ offers good extensibility characteristics, it fails to offer good compile time performance (see Section 5.2 ). Since turnstile+ performs type checking during macro expansion, the competing expansion orders of macro expansion and type checking cause a worst-case quadratic expansion time. Typically, macros are expanded in order from outside in, meaning that in a run-of-the-mill macro invocation a term is walked only once by Racket’s macro expander. Type checking requires sub-terms be checked, and thus expanded, prior to making a judgement on the type of parent terms. Since sub-terms must be fully expanded into Racket core syntax to be type checked, each term must first be completely expanded, with each sub-term recursively type checked, prior to its shallow embedding being walked by Racket’s macro expander again after expansion. In dependent type systems, like those targeted by turnstile+ , type checking is significantly more complex than for simply typed languages, worsening performance. Furthermore, type checking in turnstile+ is performed on syntax objects, requiring the traversal and pattern matching of an inefficient linked-list representation of the object language AST. This incurs poor compile time memory allocation and access performance when compared to a struct-based AST implementation, and makes common optimizations like in-place mutation impossible. syntax-spec and ee-lib syntax-spec ( Ballantyne et al. 2024 ) is an ELF which provides a DSL for defining macro-extensible object language syntax, and generates its expansion into an object-language-specific base language. syntax-spec is implemented in Racket, and is built over ee-lib ( Ballantyne et al. 2020 ) , a compatibility layer between object languages and a host language’s macro and binding system. Languages defined with syntax-spec expand into a base object language without performing type checking or fully elaborating into core Racket syntax. syntax-spec does not allow for extension of this base language, instead opting for macro-extensibility of the object language. Once elaborated into the base language, a program written in the object language can then be compiled by any method of the implementer wishes, even one which is non-extensible. syntax-spec also allows an object language to define boundary macros, with which object language users can mix object and host language code. Given the flexibility it affords in compiler design for the

Read the complete text