1. How to construct λ-terms, which are associative with respect to application?

E.g., how to construct f and g, such that for any x:

f (g x) = (f g) x

(i.e. f g x)

  1. How to construct some closed set of such terms such that the above holds for any two pairs and the application x y for any two terms also belongs to the set?

  2. Is there a basis of such λ-terms, which would allow us to express any computable function by using mere application of the terms (as in combinatory logic)? I.e., would the resulting "programming language" be Turing-complete? If not, now limited it would be?

I am asking because I have an idea for a programming language. The associativity with respect to application may be tremendously useful for optimization. If we have two transformations f and g, then instead of doing f (g x) at "run-time" (in two steps), we perform (f g) x, where f g is performed at "compile-time". Think, for example, about apllying XSLT (in its pure, "functional", form, without "scripts") directly to another XSLT style sheet...

  • 2
    $\begingroup$ I am afraid this is not a research-level question. It's fairly easy to show that there aren't many such interesting functions. And for a practical application you would have to have some types somwhere, but such f and g cannot be typed in a reasonable way. If would make more sense if you observed $f (g x) = (f \circ g) x$ and asked how to efficiently compile $f \circ g$. $\endgroup$ – Andrej Bauer Aug 21 at 9:53
  • 2
    $\begingroup$ In any case, I think you're attacking your problem in the wrong way. You should look at partial evaluation, which is a standard compiler and optimization technique for doing precisely what you want. This tutorial does a good job of demonstrating the technique. $\endgroup$ – Andrej Bauer Aug 21 at 9:53
  • $\begingroup$ I can't think of anything interesting other than $\mathrm{id}$... $\endgroup$ – xrq Aug 23 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.