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]
On 22/4/06 10:57 PM, "stevan apter" <sa@...> wrote:
> an expression in the combinators S, K, I:This is just from memory: Turner introduced some variants of the
>
> 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
>
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.
>Again, from memory: the unoptimised translations grew exponentially
> 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))
>
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.
>and if so, where to look?
> 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?
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]
>
> [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/> .
>
>
>
>
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]