compiling pattern matching to point-free combinators sequence

[Cyrille Duret]

hello,

I am working on a postfix language based on term rewriting system.

The language is very simple and operators are defined as rules of the form :

x dup => x x.

x y swap => y x.

[x_] call => x_.

..

The rewriting method works fine except for the poor performance of the interpreter.

I would like to create a compiling stage to generate bytecode.

My problem is to translate "quadratic" like rules to point-free expression.

For example :

a b toto => a a * 3 b * +. 

2 1 toto

@ 2 1 toto

@ 2 2 * 3 1 * +

@ 4 3 1 * +

@ 4 3 +

@ 7

toto_point_free => 3 * swap dup * +.

2 1 toto_point_free

@ 2 1 toto_point_free

@ 2 1 3 * swap dup * +

@ 2 3 swap dup * +

@ 3 2 dup * +

@ 3 2 2 * +

@ 3 4 +

@ 7

I am looking for a way to find the good combinators sequence to translate from toto to toto_point_free.

Is it possible to find such an algorithm ?

thanks ;-)