Ilya Klyuchnikov and Sergei Romanenko wrote a program, in kindof a lot of different languages, called SPSC-lite: "Small Positive Supercompiler".
I wanted to use the python version, but it took me some figuring out.
Now that I've figured it out, I don't want to forget it.
from residual_program_generator import *
from sll_parser import pExp, pProg
from advanced_process_tree_builder import *
def runAdvancedSupercompiler(prog, e):
nameGen = NameGen("v", 100)
tree = buildAdvancedProcessTree(nameGen, 100, prog, e)
return ResidualProgramGenerator(tree).genResidualProgram()
# the program is a sequence of definitions
# a definition can be of an "indifferent" function,
# which must start with "f", and performs no pattern matching
# a definition can be of a "curious" function,
# which must start with "g", and performs pattern matching soley
# on the first argument.
#
# Constructors begin with capital letters
# variables begin with lowercase letters
# (opposite of Prolog convention)
#
# The expression is like 'main' in C.
prog = """
gCons(Nil, a) = Cons(a, Nil);
gCons(Cons(x, y), a) = Cons(a, Cons(x, y));
gHead(Nil) = Nothing;
gHead(Cons(x, y)) = Just(x);
gTail(Nil) = Nothing;
gTail(Cons(x, y)) = Just(y);
fTriple(x) = gCons(gCons(gCons(Nil, x), x), x);
"""
e = """
gHead(fTriple(x))
"""
resTerm, resProgram = runAdvancedSupercompiler(pProg(prog), pExp(e))
print resTerm
print resProgram
The program looks silly because it is silly. It takes a thing x, constructs a list [x, x, x], and then finds the first thing in that list.
Supercompilation is related to partial evaluation and/or deforestation. It automatically figures out an equivalent program-and-expression, in this case eliminating a wasteful intermediate data structure, which in this case means that the output equivalent program-and-expression is:
Just(x)