OpenCogPrime:Transformation of complex programs

From OpenCog

One of the most important components of MOSES is the Reduct library, which reduces program trees to a normal form, so as to enable easier probabilistic modeling.

As of July 2008, however, Reduct does not handle reduction of program trees containing variables or equivalent representational mechanisms like general combinators. This is a shortcoming that needs to be overcome if OpenCog is to achieve its AGI goals. This page summarizes some of the literature that is relevant to this task.

Note, however, things are changing: the cog-reduce! function is able to reduce atomspace expressions containing variables, viz combinations of VariableNodes, NumberNodes, PlusLink and TimesLink. More general reduction has also been implemented in the FoldLink.

Mostly the references here come from the literature on the automated program transformation of functional languages. There is plenty of work that can be ported to the Combo context, but that some in-depth reading will need to be done to figure out exactly which of the several program transformation approaches we want to use. There are several approaches with complex strengths and weaknesses, and basically all of them have been elaborated with a view toward accelerating rather than normalizing programs, which means that all of them will have to be carefully evaluated with a different view than the one their creators were taking.

Here is a pertinent quote from

which is a good recent PHD thesis in the area

There are numerous methods for transforming functional programming languages. In their survey paper [56], Partsch and Steinbrueggen classify various methods for program trans- formation into two basic approaches: (1) the generative set approach, which is based on a small set of simple rules which in combination are very expressive and (2) the schematic approach which is based on using a large catalog of laws, each performing a significant transformation. Fold/unfold [15] and expression procedures [69] are examples of the for- mer. The Bird-Meertens Formalism (or Squiggol) [11, 48, 49] is an example of the latter.

In that thesis an approach called PATH is proposed, that synthesizes the generative and schematic approaches in an application to Haskell program transformation.

Assorted, Possibly Useful Approaches

On the other hand, this approach

automates program transformation for functional languages with strict rather than lazy typing.

This paper presents an approach to automated program transformation

based on term rewriting rules, which is interesting (note that Luke Kaiser's Speagram interpreter is based on term rewriting internally).

This paper is also somewhat interesting:

Moshe found a nice paper called "A Tutorial on the Universality and Expressiveness of Fold", at

which describes the algebra of the fold operator and suggests that this might be usable as the central feature of our program transformation framework. But even if we go with this, it's not clear at the moment what the "node vocabulary" within the normalized trees would be. Fold only, or do we use other constructs, using the fold algebraic rules to derive the algebraic rules for the other constructs?

Relatedly, this paper gives a nice summary of how any "list primitive recursive function" can be generated using the foldr operator

Sinot's "Director Strings As Combinators"

Most interesting, perhaps, the following paper seems to contain a workable solution to dealing with variables and combinators together ...

Sinot's papers on "efficient reduction with director strings" seem particularly relevant, and useful.

Those papers used to be available for free download through Sinot's academic site, but unfortunately he seems to have left academe for industry and taken the papers offline. If anyone can find them for free please let me know.

What he describes is a generalization of the old idea of "director strings."

This is my best bet as to the path we should take (Ben Goertzel).

See also the wikipedia entry Director string.