Friday, August 10, 2012

Compositional Separate Compilation, Take Three

In the post Separate Compilation, Take Two, Compositionally, I tried to write down a trace-based semantics for the lambda calculus that was compositional, that is, a semantics that could tell us the meaning of an individual compilation unit. The result was a semantics that wasn't quite right. A call to an external function could return a function masquerading as an internal function but that was never created by the compilation unit. Here I solve the problem in a fairly straightforward way, by threading an internal function map through the semantics.


The syntax is the same as before:


We make a few changes to the definition of traces and behavior. Our representation of a function now has an extra parameter for the internal function map. We only have one kind of action, the function-call action, whose argument and result are now required to be exportables. A function map is just a map from function names to functions. Behavior is now a set of 3-tuples, whose parts include the trace, result value, and updated internal function map.

Trace Semantics

To handle external function calls, we'll need to be able to convert from values to exportables and back again. If the value being exported is a function, we need to create a new name for it and add it to the internal function map. On the way back, if the function reference is to an internal function, we need to look it up in the internal function map. The and functions handle this logic. Both of these functions act like the identify function on integers and external functions. The meaning function for expressions now takes two more parameters, the name of the current compilation unit and the internal function map. As before, the result is the behavior of the expression. where handles calls to internal functions and handles calls to external functions To wrap things up, we define the meaning of a compilation unit as follows, with the internal function map not part of the observable behavior.

No comments:

Post a Comment