# combinator optimization

## stevan apter — 2006-04-22 12:57:08

    an expression in the combinators S, K, I:

    Ix -> x

    Kxy -> x

    Sxyz -> xz(yz)

    can be optimized (shortened) by systematically replacing certain

    patterns with the combinators discovered by david turner:

    S(Kf)(Kg) -> K(fg)

    S(Kf)I -> f

    S(Kf)(Bgh) -> B*fgh

    S(Kf)g-> Bfg

    S(Bfg)(Kh) -> C'fgh

    Sf(Kg)-> Cfg

    S(Bfg)h -> S'fgh

    for example, the unoptimized translation into combinators of the

    functional expression

        f 3 where f x is x+1

    is

        S(S(K S)(S(K K)I))(S(K K)(K(3)))(S(S(K +)I)(K(1)))

    after optimization we get:

        C I(3)(C +(1))

    i've been hunting around for research into the general problem of

    combinator optimization, but have come up dry.  does anyone here

    know whether this area is still the subject of active investigation?

    and if so, where to look?

    [Non-text portions of this message have been removed]

## Manfred Von Thun — 2006-04-26 08:27:32

    On 22/4/06 10:57 PM, "stevan apter" <sa@...> wrote:

     > an expression in the combinators S, K, I:

    >

    > Ix -> x

    > Kxy -> x

    > Sxyz -> xz(yz)

    >

    > can be optimized (shortened) by systematically replacing certain

    > patterns with the combinators discovered by david turner:

    >

    > S(Kf)(Kg) -> K(fg)

    > S(Kf)I -> f

    > S(Kf)(Bgh) -> B*fgh

    > S(Kf)g-> Bfg

    > S(Bfg)(Kh) -> C'fgh

    > Sf(Kg)-> Cfg

    > S(Bfg)h -> S'fgh

    >

     This is just from memory: Turner introduced some variants of the

    classical combinators by others which do what in concatenative

    terminology might be expresses as ³doing something not on the

    top of the stack, but one below the top², where ³something² means

    concatenatively: shuffle the stack and then call a quotation. When

    I designed Joy, I also thought of having similar variants (working

    below the top) for all the combinators that I had conceived of by

    then. Doing this systematically would have doubled the number

    needed, possibly by using a postfix single quote or prime symbol to

    indicate the variant intended, just as C¹ and S¹ above are variants

    of the standard C and S. But eventually I settled on the dip combinator

    which could do all the variant tricks but could also take arbitrarily

    complex quoted expressions as argument.

     >

    > for example, the unoptimized translation into combinators of the

    > functional expression

    >

    >     f 3 where f x is x+1

    >

    > is

    >

    >     S(S(K S)(S(K K)I))(S(K K)(K(3)))(S(S(K +)I)(K(1)))

    >

    > after optimization we get:

    >

    >     C I(3)(C +(1))

    >

     Again, from memory: the unoptimised translations grew exponentially

    in the number of combinators of the original expression, then some

    better translation were found which only grew quadratically. Only when

    Turner discovered his optimised translation which grows linearly did

    the implementation of a lambda calculus language in terms of combinators

    become feasible: KRC (Kent Recursive Calculator, an untyped Lisp-like

    language), then Miranda (typed) and now Haskell. All three are non-strict,

    being implemented via combinators which give call by need, also

    known as laziness.

     >

    > i've been hunting around for research into the general problem of

    > combinator optimization, but have come up dry.  does anyone here

    > know whether this area is still the subject of active investigation?

            and if so, where to look?

    What little I knew about the field came from the book by Peyton-Jones

    ³The Implementation of Functional Programming Languages² in Prentice

    Hall. It deals with the implementation of Miranda, and as far as I can tell

    the core of the implementation of Haskell would be very similar. I do not

    know what details are freely available. But if you add ³Miranda² or

    ³Haskell²

    to your search list, you might be lucky. There are also a few Haskell

    mailing

    groups that might be able advise on whether there is still active

    investigation.

    It might well be that the area was already so well developed a few years

    back

    that the topic is no longer active.

      - Manfred

     >

    >

    > [Non-text portions of this message have been removed]

    >

    >

    >

    >

    >

    >  YAHOO! GROUPS LINKS

    >

    > *  Visit your group "concatenative

    > <http://groups.yahoo.com/group/concatenative> " on the web.

    > *

    > *  To unsubscribe from this group, send an email to:

    > *  concatenative-unsubscribe@yahoogroups.com

    > <mailto:concatenative-unsubscribe@yahoogroups.com?subject=Unsubscribe>

    > *

    > *  Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service

    > <http://docs.yahoo.com/info/terms/> .

    >

    >

    >

    >

     [Non-text portions of this message have been removed]

## stevan apter — 2006-04-26 10:59:48

    chapter 16 of p-j has what i'm looking for, and googling

    "director strings" turns up some interesting research material.

    thanks manfred.

       ----- Original Message -----

      From: Manfred Von Thun

      To: concatenative@yahoogroups.com

      Sent: Wednesday, April 26, 2006 4:27 AM

      Subject: Re: [stack] combinator optimization

      On 22/4/06 10:57 PM, "stevan apter" <sa@...> wrote:

      > an expression in the combinators S, K, I:

      >

      > Ix -> x

      > Kxy -> x

      > Sxyz -> xz(yz)

      >

      > can be optimized (shortened) by systematically replacing certain

      > patterns with the combinators discovered by david turner:

      >

      > S(Kf)(Kg) -> K(fg)

      > S(Kf)I -> f

      > S(Kf)(Bgh) -> B*fgh

      > S(Kf)g-> Bfg

      > S(Bfg)(Kh) -> C'fgh

      > Sf(Kg)-> Cfg

      > S(Bfg)h -> S'fgh

      >

      This is just from memory: Turner introduced some variants of the

      classical combinators by others which do what in concatenative

      terminology might be expresses as ³doing something not on the

      top of the stack, but one below the top², where ³something² means

      concatenatively: shuffle the stack and then call a quotation. When

      I designed Joy, I also thought of having similar variants (working

      below the top) for all the combinators that I had conceived of by

      then. Doing this systematically would have doubled the number

      needed, possibly by using a postfix single quote or prime symbol to

      indicate the variant intended, just as C¹ and S¹ above are variants

      of the standard C and S. But eventually I settled on the dip combinator

      which could do all the variant tricks but could also take arbitrarily

      complex quoted expressions as argument.

      >

      > for example, the unoptimized translation into combinators of the

      > functional expression

      >

      >     f 3 where f x is x+1

      >

      > is

      >

      >     S(S(K S)(S(K K)I))(S(K K)(K(3)))(S(S(K +)I)(K(1)))

      >

      > after optimization we get:

      >

      >     C I(3)(C +(1))

      >

      Again, from memory: the unoptimised translations grew exponentially

      in the number of combinators of the original expression, then some

      better translation were found which only grew quadratically. Only when

      Turner discovered his optimised translation which grows linearly did

      the implementation of a lambda calculus language in terms of combinators

      become feasible: KRC (Kent Recursive Calculator, an untyped Lisp-like

      language), then Miranda (typed) and now Haskell. All three are non-strict,

      being implemented via combinators which give call by need, also

      known as laziness.

      >

      > i've been hunting around for research into the general problem of

      > combinator optimization, but have come up dry.  does anyone here

      > know whether this area is still the subject of active investigation?

             and if so, where to look?

      What little I knew about the field came from the book by Peyton-Jones

      ³The Implementation of Functional Programming Languages² in Prentice

      Hall. It deals with the implementation of Miranda, and as far as I can tell

      the core of the implementation of Haskell would be very similar. I do not

      know what details are freely available. But if you add ³Miranda² or

      ³Haskell²

      to your search list, you might be lucky. There are also a few Haskell

      mailing

      groups that might be able advise on whether there is still active

      investigation.

      It might well be that the area was already so well developed a few years

      back

      that the topic is no longer active.

        - Manfred

      >

      >

      > [Non-text portions of this message have been removed]

      >

      >

      >

      >

      >

      >  YAHOO! GROUPS LINKS

      >

      > *  Visit your group "concatenative

      > <http://groups.yahoo.com/group/concatenative> " on the web.

      > *

      > *  To unsubscribe from this group, send an email to:

      > *  concatenative-unsubscribe@yahoogroups.com

      > <mailto:concatenative-unsubscribe@yahoogroups.com?subject=Unsubscribe>

      > *

      > *  Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service

      > <http://docs.yahoo.com/info/terms/> .

      >

      >

      >

      >

      [Non-text portions of this message have been removed]

      Yahoo! Groups Links

    [Non-text portions of this message have been removed]