Lambda the Ultimate

Systematic search for lambda expressions by Susumu Katayama

This paper presents a system for searching for desired small functional programs by just generating a sequence of type-correct programs in a systematic and exhaustive manner and evaluating them. The main goal of this line of research is to ease functional programming, along with the subgoal to provide an axis to evaluate heuristic approaches to program synthesis such as genetic programming by telling the best performance possible by exhaustive search algorithms. While our previous approach to that goal used combinatory expressions in order to simplify the synthesis process, which led to redundant combinator expressions with complex types, this time we use de Bruijn lambda expressions and enjoy improved results.

Although the algorithm is slow and only works on small expressions, it looks helpful. Perhaps there could be some synthesis with Hoogλe, or whatever the name is after Google makes them change it.

I have a bunch of ideas for my own programming language (like every other CS undergraduate with an appropriate degree of hubris) and I'm starting to fiddle with writing my own compiler for it, but I'm having trouble understanding a lot of technical material out there. Most of the programming language papers and tutorials I'm finding on the net assume that I already know lambda calculus and other advanced mathematics.

What's some good easy to understand stuff I can read to get the mathematical basis I need to understand all the jargon, or understand some if it without the math? (i.e. I'd like to understand dependent typing, but the papers I've found turn my brain into knots)