hn.today

The Magic of Partial Evaluation

jimmyhmiller.com100 points25 comments
Screenshot of The Magic of Partial Evaluation

Partial evaluation specializes a program when some of its inputs are already known, producing a new program that handles the remaining inputs more directly. The central idea is that this can turn an interpreter into a compiler without separately writing one. For example, supplying a fixed Brainfuck program to an interpreter can produce a specialized function; a fixed validation schema can similarly yield faster, schema-specific validation code. Specialization is useful not only for speed: it can avoid maintaining both an interpreter and a hand-built compiler when configurations or programs become available only at runtime.

The deeper result is expressed through the Futamura projections. The first specializes an interpreter for a particular program, effectively compiling that program. The second specializes a partial evaluator for a particular interpreter, producing a compiler for that language. The third specializes the partial evaluator with itself, yielding a compiler generator that can create compilers for interpreters generally. A small example shows how specializing an interpreter for “prompt” and “print” instructions produces JavaScript that directly performs those operations. The author presents partial evaluation as a compelling way to understand the relationship between interpreters and compilers, even where practical applications are limited, and describes a modest Rust implementation for JavaScript that supports some of these techniques.

Read on jimmyhmiller.com25 comments on Hacker News

Summary generated by AI from the linked article. hn.today is not affiliated with Hacker News or Y Combinator.

More in Programming

Sarasa Gothic Mono

Sarasa Gothic Mono

Sarasa Gothic Mono is a free, open-source monospace typeface built for multilingual programming, combining Source Han Sans and Iosevka. It offers coding ligatures, pixel-friendly hinting, condensed characters, and support for Latin, Cyrillic, Greek, and East Asian scripts. (picaq.github.io)

The daily digest

Today's best Hacker News stories, summarized and screenshotted, one email a day.