# compiling pattern matching to point-free combinators sequence

## Cyrille Duret — 2014-04-30 07:04:36

    hello,I have good interest in postfix concatenative languages for some years now, I discover the postfix notation with forth and saw the beauty of joy and now I try to experiment the benefit of a concatenative language for distributed application, user interface ( I am thinking of a visual touch based programming environment a bit like hopscotch https://www.gethopscotch.com/) , etc..

    My language of prototyping is javascript and my language of choice for implementation is ATS2 (http://www.ats-lang.org/)
    I have already done a conventional implementation of a very basic language here https://github.com/cduret/stk.js , but I want to go further.
    At the time I read this paper (http://mitarbeiter.hs-heilbronn.de/~herzberg/Publications/ICSOFT.2009.pdf), I saw the power and simplicity of a concatenative language based on a rewriting system.

    So I began my implementation of a basic rewrite system :The words can be defined with pattern matching as follow :

    x dup => x x.
    x y swap => y x.
    [x_] call => x_.
    ...

    Rewriting system is powerful and can compute symbolic expression as well but the explosion of rewriting steps can lead to slow execution time.
    That's why I try to think about a compiler that would transform the rule-based program into a stack oriented bytecode.

    My first problem is to find a way of rewriting a rule with named parameters into a point-free word (in a forth or factor meaning).

    How I could compile the rule :

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

    into

    toto => 3 * swap dup * +.

    I am looking for such an algorithm if you have some advices..

    thank you very much ;-)

## William Tanksley, Jr — 2014-04-30 16:18:40

    That's fun!

    There have been a couple of concatenative systems based on rewriting,

    and you'll probably want to learn from them; the one I can recall

    offhand is "Enchilada" and its author's next language "SPREAD", the

    latter at http://oercode.blogspot.nl/. (I don't remember where

    Enchilada lives.)

    However, rewriting lambdas is a little different. iepos wrote a paper

    that includes discussion of that at http://tunes.org/~iepos/joy.html.

    It's fairly simple compared to general concatenative rewriting.

    -Wm

    Cyrille Duret <cduret@...> wrote:

     >

    >

    >

    > hello,

    > I have good interest in postfix concatenative languages for some years now, I discover the postfix notation with forth and saw the beauty of joy and now I try to experiment the benefit of a concatenative language for distributed application, user interface ( I am thinking of a visual touch based programming environment a bit like hopscotch https://www.gethopscotch.com/) , etc..

    >

    > My language of prototyping is javascript and my language of choice for implementation is ATS2 (http://www.ats-lang.org/)

    >

    > I have already done a conventional implementation of a very basic language here https://github.com/cduret/stk.js , but I want to go further.

    > At the time I read this paper (http://mitarbeiter.hs-heilbronn.de/~herzberg/Publications/ICSOFT.2009.pdf), I saw the power and simplicity of a concatenative language based on a rewriting system.

    >

    > So I began my implementation of a basic rewrite system :

    > The words can be defined with pattern matching as follow :

    >

    > x dup => x x.

    > x y swap => y x.

    > [x_] call => x_.

    > ...

    >

    > Rewriting system is powerful and can compute symbolic expression as well but the explosion of rewriting steps can lead to slow execution time.

    > That's why I try to think about a compiler that would transform the rule-based program into a stack oriented bytecode.

    >

    > My first problem is to find a way of rewriting a rule with named parameters into a point-free word (in a forth or factor meaning).

    >

    > How I could compile the rule :

    >

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

    >

    > into

    >

    > toto => 3 * swap dup * +.

    >

    >

    > I am looking for such an algorithm if you have some advices..

    >

    > thank you very much ;-)

    >

    >

    >

## Jon Purdy — 2014-04-30 18:20:09

    > Rewriting system is powerful and can compute symbolic expression as well but the explosion of rewriting steps can lead to slow execution time.

     I think it is possible to produce a fast implementation of a

    concatenative system based on pure rewriting. I was working on such a

    thing a few years ago. My approach (as I remember it) was to collect

    all rewrite rules, sort them in order of specificity, and group those

    by the head word if there was one; the result was an O(1) hash table

    lookup plus an O(log n) search for the most specific pattern, each

    rewriting step. Seemed fast enough, though I never benchmarked it. I

    will see if I can dig up the code or rewrite it for fun.

     > My first problem is to find a way of rewriting a rule with named parameters into a point-free word (in a forth or factor meaning).

     That’s called an “abstraction algorithm”—converting lambdas into

    combinators. The Brent Kirby article that William Tanksley linked is a

    good start, but it would require a good deal of optimisation to be

    suitable.

    You can also think of a concatenative expression with local variables

    as a data flow graph—directed and acyclic, hopefully—and try to reduce

    the graph as much as possible. But that breaks down with higher-order

    functions, which seem to be the best way to make concatenative

    expressions succinct, legible, and efficient.

## William Tanksley, Jr — 2014-04-30 18:22:21

    I found Enchilada:

    http://www.enchiladacode.nl/

    On Wed, Apr 30, 2014 at 9:18 AM, William Tanksley, Jr

    <wtanksleyjr@...> wrote:

     > That's fun!

    >

    > There have been a couple of concatenative systems based on rewriting,

    > and you'll probably want to learn from them; the one I can recall

    > offhand is "Enchilada" and its author's next language "SPREAD", the

    > latter at http://oercode.blogspot.nl/. (I don't remember where

    > Enchilada lives.)

    >

    > However, rewriting lambdas is a little different. iepos wrote a paper

    > that includes discussion of that at http://tunes.org/~iepos/joy.html.

    > It's fairly simple compared to general concatenative rewriting.

    >

    > -Wm

    >

    > Cyrille Duret <cduret@...> wrote:

    >>

    >>

    >>

    >> hello,

    >> I have good interest in postfix concatenative languages for some years now, I discover the postfix notation with forth and saw the beauty of joy and now I try to experiment the benefit of a concatenative language for distributed application, user interface ( I am thinking of a visual touch based programming environment a bit like hopscotch https://www.gethopscotch.com/) , etc..

    >>

    >> My language of prototyping is javascript and my language of choice for implementation is ATS2 (http://www.ats-lang.org/)

    >>

    >> I have already done a conventional implementation of a very basic language here https://github.com/cduret/stk.js , but I want to go further.

    >> At the time I read this paper (http://mitarbeiter.hs-heilbronn.de/~herzberg/Publications/ICSOFT.2009.pdf), I saw the power and simplicity of a concatenative language based on a rewriting system.

    >>

    >> So I began my implementation of a basic rewrite system :

    >> The words can be defined with pattern matching as follow :

    >>

    >> x dup => x x.

    >> x y swap => y x.

    >> [x_] call => x_.

    >> ...

    >>

    >> Rewriting system is powerful and can compute symbolic expression as well but the explosion of rewriting steps can lead to slow execution time.

    >> That's why I try to think about a compiler that would transform the rule-based program into a stack oriented bytecode.

    >>

    >> My first problem is to find a way of rewriting a rule with named parameters into a point-free word (in a forth or factor meaning).

    >>

    >> How I could compile the rule :

    >>

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

    >>

    >> into

    >>

    >> toto => 3 * swap dup * +.

    >>

    >>

    >> I am looking for such an algorithm if you have some advices..

    >>

    >> thank you very much ;-)

    >>

    >>

    >>

## John Cowan — 2014-04-30 18:23:36

    Jon Purdy scripsit:

     > I think it is possible to produce a fast implementation of a

    > concatenative system based on pure rewriting.

     You should look at Pure, which is not concatenative but is based on

    eager bottom-up term rewriting.

    --

    John Cowan          http://www.ccil.org/~cowan        cowan@...

    "Why yes, I'm ten percent Jewish on my manager's side."

            --Connie Francis

## Cyrille Duret — 2014-05-01 08:09:38

    @williamThanks for the references, indeed enchilada and SPREAD are the closest to my implementation and I will look carefully at their code.
    For the lambda reduction I will try this simple algorithm first but I think a lot of optimizations are required after reducing the amazing number of combinator words produced

    if you think simple lambda expression as  A\ B A [C A] is reduced to
    [B] dip dup [i] dip [[C] dip i] cons
    you can suspect that the generated code will be way too fat to be efficient.

    @jon
    I would be interested to see ur implementation.The heart of my implementation is the match and rewrite functions of this amazing book about term rewriting
    http://www.amazon.com/Term-Rewriting-That-Franz-Baader/dp/0521779200
    I adapted it to concatenative needs

    My ultimate goal would be to have a very simple rewriting core and doing all with it : type-checking, optimization, compilation/code generation.I don't know if it is possible but I have the feeling that the combination of rewriting and concatenative paradigm is so powerful.

    @john
    thanks for the reference I got the book http://www.amazon.com/Functional-Programming-Parallel-Rewriting-International/dp/0201416638 that describe the underlying implementation of the Clean (now Pure) programming language.
    I don't know if the high level part is suitable for my case of postfix, concatenative language, but the VM bytecode generation and the type check system and the IO implementation is amazing ;-)

## William Tanksley, Jr — 2014-05-01 13:10:32

    Cyrille Duret <cduret@...> wrote:

     > For the lambda reduction I will try this simple algorithm first but I think a lot of optimizations are required after reducing the amazing number of combinator words produced

    > if you think simple lambda expression as

    >  A\ B A [C A] is reduced to

    > [B] dip dup [i] dip [[C] dip i] cons

    > you can suspect that the generated code will be way too fat to be efficient.

     That's completely correct. This is a purely textual algorithm, which

    has advantages for reasoning on paper but disadvantages otherwise. If

    you lift the phrase into a dataflow graph you'll be able to perform

    translation and optimization with the same step -- but it's a more

    complicated step.

     > The heart of my implementation is the match and rewrite functions of this amazing book about term rewriting

    > http://www.amazon.com/Term-Rewriting-That-Franz-Baader/dp/0521779200

    > I adapted it to concatenative needs

     I'm delighted to hear it.

    Check out the back history of this group for talk about static

    typechecking. It's not a simple issue, but several people have done

    the basics.

    -Wm