# Are combinatory logic terms always larger?

So there is an algorithm to convert lambda calculus terms to combinatory logic using SK combinators. It produces things that explode in size. I would like to know more about this explosion in size. I can't seem to think of a better algorithm however. I have heard of functional languages being practically compiled to combinators so it seems that a better algorithm must exist. I looked up David Turner's paper on the topic and he basically just says to apply a few optimizations and that they cause a "considerable improvement".

Does "considerable improvement" mean that the size drops to only a polynomial increase? Is there a known way to convert lambda terms to combinatory logic with only a polynomial (or less?) increase in size? If such an algorithm exists is it practical?

• the paper is from 1979. there is much more modern/ recent thinking/ technology on how to translate code into logic eg with FPGAs & GPUs & generally wouldnt be based on functional languages....
– vzn
Commented Jul 10, 2015 at 22:39
• Can you point me to them?
– Jake
Commented Jul 11, 2015 at 0:25
• the research you cite is more theoretical "proof of principle"... it would be better if you cite the concept/ section about "polynomial increase in size" which seems to be the focus of your question... are you interested in the general theory of converting code into logic/ circuits, on the theoretical or applied side, or the theory of doing it efficiently, or both? the question is very crosscutting in its different aspects... maybe can figure out more in Computer Science Chat
– vzn
Commented Jul 11, 2015 at 2:44
• 1) is there a way to import this to a chat? I can't seem to figure that out. 2) There is no section about polynomial increase in size and that is my problem. It doesn't actually say anything substantial (nor can I find any such references) about how much the increase in size is.
– Jake
Commented Jul 11, 2015 at 3:02
• the comments can be imported to chat after a threshhold of separate posted comments. that is not necessary to start a chat. re polynomial increase it could be a "rumor" or "folklore" concept about this line of research, not sure. but where did you hear stuff like "it produces things that explode in size"; it would be helpful to be more specific etc...
– vzn
Commented Jul 11, 2015 at 16:05

Furthermore, we show that implementations based upon Turner Combinators or Hughes Super-combinators have complexities $$2^{Ω(ν)}$$, i.e. an exponential lower bound. It is open whether any implementation of polynomial complexity, $$ν^{O(1)}$$, exists, although some implementations have been implicitly claimed to have this complexity.