Eliminate non-local references from closure

For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure:

{
  var a;
  var b;

  var f = function() {
    a = 5;
    b = 6;
  }

  f();
}

would be converted into something like:

{
  var a;
  var b;

  var f = function() {
    var a = 5;
    var b = 6;
    return tuple(a, b);
  }

  a, b = f();
}

Another approach would be:

{
  var world;
  var a;
  var b;

  var f = function(world) {
    world = update_world(world, "a", 5);
    world = update_world(world, "b", 6);
    return world;
  }

  world = f(world);
  a = get_world(world, "a");
  b = get_world(world, "b");
}

Basically, convert a stateful program to a purely functional one. The goal is then to transform the resulting program into the lambda calculus, normalize and look for isomorphic subtrees.

Is there a formalization of what I'm trying to do?

I think what you want is essentially conversion to static single assignment (SSA) form, followed by closure conversion, followed by conversion to continuation passing style.

Static single assignment form guarantees that each variable is written exactly once in the program text. That this is the key step in converting imperative to functional programs is argued by


Andrew W. Appel. SSA is functional programming.
SIGPLAN Notices, 33(4), 1998.


Richard A. Kelsey. A correspondence between continuation
passing style and static single assignment form.
Proc ACM SIGPLAN Workshop on Intermediate
Representations, January 1995.


Peter J. Landin. The mechanical evaluation of expressions.
Computer Journal, 6(4):308–320, 1964.

This starts to get really interesting for programs with loops. You need to convert the loops into recursive calls, and make a unique copy for the variables written in each iteration of the loop. In the traditional loop optimization community this technique is called scalar expansion or (sometimes) dynamic renaming.


David J. Kuck, R. H. Kuhn, David A. Padua, B. Leasure,
and Michael Wolfe. Dependence graphs and compiler
optimizations. In Conference Record of the Eighth
Annual ACM Symposium on Principles of Programming
Languages, pages 207–218, Williamsburg, VA, January
1981.


Ron Cytron and Jeanne Ferrante. What’s in a name?
The value of renaming for parallelism detection and
storage allocation. In Proceedings of the 16th Annual International
Conference on Parallel Processing, pages 19–27,
St. Charles, IL, August 1987.

In the functional programming community this involves making closures and continuations explicit:


Andrew W. Appel and Trevor Jim. Continuation passing,
closure-passing style. Proc. Symp. on Principles of Programming Languages (POPL),
1989.


Guy Lewis Steele. RABBIT: A compiler for Scheme.
Technical Report AITR-474, MIT Artificial Intelligence
Laboratory, May 1978.

I needed to do these conversions, for the automatic parallelization techniques described in my dissertation. Chapters 3, and 9.1.


Matthew Frank, SUDS: Automatic Parallelization for Raw Processors, Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 23, 2003.

StackExchange Computer Science Q#44454, answer score: 7