Next: The Problem Up: But Mom, I don't Previous: Motivation and Background

A Brief Digression on Representing Functions in Moby

Moby is an experiment in language design and implementation. Our goal is to combine support for class-based object-oriented programming and higher-order concurrency with the desirable features of ML-like languages: advanced module systems, parametric polymorphism, inductive datatypes, pattern matching, and first-class functions.

Internally, the Moby compiler uses a higher-order, direct-style IR called BOL (lexical average of ANF and CPS). A cluster conversion phase transforms a general BOL program into BOL clusters, which is a first-order, direct-style IR with no nested-functions (hence, explicit closures). A BOL cluster $\langle f, \mathcal{F} \rangle$ is comprised of an entry fragment and a set of internal fragments satisfying

$f \not\in \mathcal{F}$
$\mathcal{F} \subseteq \mathsf{Known}$ (all call sites of internal fragments are known)
for any $g \in \mathcal{F}$ and fragment , if had a tail call of , then $h \in \{f\} \cup \mathcal{F}$ .
for any $g \in \mathcal{F}$ , $\not\exists h$ such that has a non-tail call of

A fragment is a first-order function. Cluster conversion is comprised of frame conversion (which groups fragments into clusters) and closure conversion (which performs light-weight closure conversion on internal fragments, mapping variables free inside a fragment to fragment parameters).

Code-generation is via MLRISC. Each cluster becomes one machine procedure; control transfer within a cluster is implemented as jumps with local variables. The conclusion is we want clusters as big as possible - this enables better loop optimizations, register allocation, and instruction scheduling; it also eliminates the overhead of creating closures and making full-fledged function calls.

Next: The Problem Up: But Mom, I don't Previous: Motivation and Background

Matthew Fluet 2002-02-22