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: