Into CPS, Never to Return
The article discusses a CPS transformation for a simplified Scheme-like language in Python, emphasizing function calls without returns, optimizations like constant folding, and the importance of managing continuations for efficiency.
Read original article
Continuation-Passing Style (CPS) is an intermediate representation used in compilers for functional programming languages like SML and Scheme. In CPS, function calls do not return, and arguments must be trivial. This article introduces a CPS transformation for a simplified Scheme-like language, implemented in Python. The transformation involves compiling expressions into a form where continuations are passed as arguments to functions, ensuring that functions never return values directly. The article details the compilation of various constructs, including integers, variables, function calls, arithmetic operations, lambda expressions, and conditional statements. It also discusses optimizations such as constant folding and beta reduction, which can simplify the generated code. The implementation highlights the importance of managing continuations effectively to avoid code bloat and maintain efficiency. The author suggests that while the basic CPS transformation is straightforward, more complex optimizations can be applied to enhance performance, particularly in resource-constrained environments.
- CPS is a crucial intermediate representation in functional programming compilers.
- The transformation ensures that functions do not return values directly, using continuations instead.
- The article provides a Python implementation for compiling a simplified Scheme-like language.
- Optimizations like constant folding and beta reduction can significantly improve the efficiency of the generated code.
- Effective management of continuations is essential to prevent code bloat during compilation.
Related
Continuations by Example
Continuations are powerful in control-flow constructs, enabling exceptions, search, threads, generators, and coroutines. They capture remaining computation steps, aiding in non-deterministic choices and efficient iteration over data structures.
CPS in Hoot
The Hoot Scheme-to-Wasm compiler uses CPS transformation to handle push calls in WebAssembly. Strategies like generic slicing and CPS transformation are explored, enabling features like Fibers and promise integration. Performance impact is under evaluation.
A Practical Introduction to Constraint Programming Using CP-SAT and Python
Constraint programming (CP) is a declarative paradigm for solving discrete optimization problems using variables and constraints. CP-SAT, an open-source solver by Google, can handle complex problems efficiently, like fair contribution distribution and employee scheduling.
Pseudo Scheme: Scheme Implemented on Top of Common Lisp
The Pseudo Scheme, created by Jonathan Rees, is an implementation of Scheme on Common Lisp. It follows IEEE and Revised^4 Scheme standards, offers a high-level macro facility, and allows seamless interaction between Scheme and Common Lisp programs. It can be easily ported to different Lisp environments and is available for use, copying, and distribution. Join a mailing list for updates.
The Ultimate Conditional Syntax
The paper introduces a new pattern-matching syntax for functional programming, enhancing expressiveness and readability, supporting complex matches, and ensuring semantics preservation through a desugaring process for integration into existing languages.
9 commentsThe second, although more obscure, is that you can use it in languages that do not have "non-local exits" to terminate a deeply nested computation early or return to an earlier point in the call stack. For example, Clojure does not have nonlocal exits, as only the final form of the function is returned. However, using CPS, you can terminate the expression early and return to the original caller without executing the rest of the function. You probably only want to use this in specialized cases though or it may upset your team, they are tricky to debug.
Lastly and probably most controversially, you can make an extensible "if" statement using CPS if you are in a dynamic language and you have no other tools to do so. Admittedly I do sometimes use this in ClojureScript. This allows you to write "append only" code without continually growing the "cond". Again, most teams don't like this, so it depends on the circumstances, but might be nice to have in your back pocket if you need it.
[1]: https://github.com/norvig/paip-lisp/blob/main/docs/chapter12...
Instead, the normal loops are used, and the subresults are accumulated in some builder structure which is then finalized to produce a complete tree of a CPS expression. The main trick is to figure out just what this builder structure should be, and it turns out it's a tree zipper of sorts!
The margins of this comment are not big enough to sketch the whole thing but it's actually not as formidable as it sounds ("tree zipper", wooooh): it's mostly just a stack of tree-building instructions which can be easily extended/completed. An alternative would be to have a mutable CPS expression as the result, and keep appending things into it, but it requires lots of tree traversal and lot of care to not accidentally leave the thing in not quite constructed state which is way too easy in my experience.
I think I'll make and publish a gist with it when I get home because I don't believe I've ever seen it done this way anywhere.
Just wanted to add that this is very similar to how async/await JavaScript code was compiled for runtimes that didn't support generators back in the day: http://facebook.github.io/regenerator/
But CPS isn't really the state of the art for functional compilers anymore. It's complex for a human to read and hard to optimize. Something like A-normal form is much easier to work with for a compiler intermediate representation
Related
Continuations by Example
Continuations are powerful in control-flow constructs, enabling exceptions, search, threads, generators, and coroutines. They capture remaining computation steps, aiding in non-deterministic choices and efficient iteration over data structures.
CPS in Hoot
The Hoot Scheme-to-Wasm compiler uses CPS transformation to handle push calls in WebAssembly. Strategies like generic slicing and CPS transformation are explored, enabling features like Fibers and promise integration. Performance impact is under evaluation.
A Practical Introduction to Constraint Programming Using CP-SAT and Python
Constraint programming (CP) is a declarative paradigm for solving discrete optimization problems using variables and constraints. CP-SAT, an open-source solver by Google, can handle complex problems efficiently, like fair contribution distribution and employee scheduling.
Pseudo Scheme: Scheme Implemented on Top of Common Lisp
The Pseudo Scheme, created by Jonathan Rees, is an implementation of Scheme on Common Lisp. It follows IEEE and Revised^4 Scheme standards, offers a high-level macro facility, and allows seamless interaction between Scheme and Common Lisp programs. It can be easily ported to different Lisp environments and is available for use, copying, and distribution. Join a mailing list for updates.
The Ultimate Conditional Syntax
The paper introduces a new pattern-matching syntax for functional programming, enhancing expressiveness and readability, supporting complex matches, and ensuring semantics preservation through a desugaring process for integration into existing languages.