HOUSE_OVERSIGHT_013238.jpg

322
18 Advanced Self-Modification: A Possible Path to Superhuman AGI

schema are implicitly variables – they vary from one instance of schema execution to the next
– and may be treated as such for supercompilation purposes.

The metaprogram executes a program without assuming specific values for its input variables,
creating a tree as it goes along. Each time it reaches a statement that can have different results
depending on the values of one or more variables, it creates a new node in the tree. This part
of the supercompilation algorithm is called driving – a process which, on its own, would create
a very large tree, corresponding to a rapidly-executable but unacceptably humongous version
of the original program. In essence, driving transforms a program into a huge “decision tree”,
wherein each input to the program corresponds to a single path through the tree, from the root
to one of the leaves. As a program input travels through the tree, it is acted on by the atomic
program step living at each node. When one of the leaves is reached, the pertinent leaf node
computes the output value of the program.

The other part of supercompilation, configuration analysis, is focused on dynamically reduc-
ing the size of the tree created by driving, by recognizing patterns among the nodes of the tree
and taking steps like merging nodes together, or deleting redundant subtrees. Configuration
analysis transforms the decision tree created by driving into a decision graph, in which the
paths taken by different inputs may in some cases begin separately and then merge together.

Finally, the graph that the metaprogram creates is translated back into a program, embody-
ing the constraints implicit in the nodes of the graph. This program is not likely to look anything
like the original program that the metaprogram started with, but it is guaranteed to carry out
the same function [NOTE: Give a graphical representation of the decision graph corresponding
to the supercompiled binary search program for L=4, described above.].

18.3.2 Supercompilation for Goal-Directed Program Modification

Supercompilation, as conventionally envisioned, is about making programs run faster; and as
noted above, it will almost certainly be useful for this purpose within CogPrime.

But the process of program modeling embedded in the supercompilation process, is poten-
tially of great value beyond the quest for faster software. The decision graph representation of a
program, produced in the course of supercompilation, may be exported directly into CogPrime
as a set of logical relationships.

Essentially, each node of the supercompiler’s internal decision graph looks like:

Input: List L

Output: List

If ( P1(L) ) N1(L)

Else If ( P2(L) ) N2(L)

. . .

Else If ( Pk(L) ) Nk(L)

HOUSE_OVERSIGHT_013238