- 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)
How to construct some closed set of such terms such that the above holds for any two pairs and the application
x yfor any two terms also belongs to the set?
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
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...