Lambda the Ultimate

In Haskell, \f -> \g -> (((f.).).) g is equivalent to \x y z -> f (g x y z), and more generally, \f -> \g -> (((f.)... .) g with n compositions is equivalent to x1 ... xn -> f (g x1 ... xn) with n arguments.

But what is \f -> \g -> (.(.(.f))) g? Can you generalize?

What about arbitrary left and right compositions, like (.(.((.f).)))? Can a general description be given?

I am interested in your strategies in tackling such questions. I find reasoning about combinators quickly overwhelming. Sure, I can mechanically reduce a lambda term to normal form, but it's usually not that insightful. Is the key once more abstraction, through understanding of combinators at a high operational level?

Any pointers to resources for reasoning about combinators would be appreciated.

Automatically Generating the Back End of a Compiler Using Declarative Machine Descriptions[PDF]
By Joao Dias

Although I have proven that the general problem is undecidable, I show how, for machines of practical interest, to generate the back end of a compiler.
...
The largest machine-dependent component in a back end is the instruction
selector. Previous work has shown that it is difficult to generate a highquality
instruction selector. But by adopting the compiler architecture developed
by Davidson and Fraser (1984), I can generate a na¨ıve instruction
selector and rely upon a machine-independent optimizer to improve the machine
instructions. Unlike previous work, my generated back ends produce
code that is as good as the code produced by hand-written back ends.

The Code Generation 2009 Call for Speakers closes on Friday January 16th 2009. Accepted speakers have their conference fees waived.

Session proposals are sought covering topics such as:

• Tool and technology adoption
• Code Generation and Model Transformation tools and approaches
• Defining and implementing modelling languages
• Domain Analysis and Domain Engineering
• Language evolution and modularization
• Meta Modelling
• Runtime virtual machines versus direct code generation
• Software Product Lines and Software Factories

Visit the Code Generation 2009 web site for more information and to make a speaking submission.

Code Generation 2009 is sponsored by SoftFluent, itemis & NT/e and supported by OMG, IASA & ACCU.