How I finally understood the Y Combinator | Hacker News Reader

How I finally understood the Y Combinator

noeit.wordpress.com

34 pointsdragonquest8 comments

This is what made it click for me: http://nex-3.com/posts/43-fun-with-the-y-combinator-in-ruby

The computer science part of my brain says "hmm, that's neat" (admittedly, it's likely that it's not fully clicking for me yet).

The engineering part of my brain says "OK, so what does that let me build that is much harder without it?"

I'm with you so far. As an (originally) low-level programmer, I learned to deal first with state machines and performance, so functional programming looks sort of ivory tower and meaningless.

However, trying to get things to work efficiently in parallel on clusters of multicore machines, working mostly in Python, the issues I think FP tries to address are starting to come into focus.

I once sat through a 2 hour seminar just to hear Guido Van Rossum talk about parallelization in Python. When it came time for him to speak, he said something like "I don't know why I was invited -- I neither care nor think very much about parallelism". This was sort of amusing. Note his comments on tail recursion elsehwere on YC.

I come from the opposite end of the spectrum. Only recently have I begone to worry about implementation in the real world.

Have you had a look at http://users.bigpond.net.au/d.keenan/Lambda/index.htm ? It give an introduction into the more general theory of combinatorial logic instead of just focusing on the y-combinator.

My engineering side agrees with yours, but programming side has been tainted by it too. My programming side just thinks "think of all the cool stuff I could learn and use in the time it would take to wrap my head around something I can see no use for".

Same as I could learn enough of a foreign language to get by with in a fraction of the time it would take me to learn Klingon, which has no purpose other than novelty.

Can one of you Klingon-speakers please tell me why I should care about the Y-combinator and how mind-numbingly cool it is?

Y combinator is not something that makes your daily engineering life easier. Its main point in CS is that it allows to construct a Turing machine equivalent solely by lambdas---hence it allows reasoning of computation process based on very few axioms. But that's not something programmers do every day.

I think what's important is knowing about the thinking process of Y combinators and alike. That is, thinking about something that can be applied to itself, and taking advantage of it.

A "first-order" thinking is something like thinking about a function that works on values, or about a program that takes input data stream and emits output data stream. In this mode, you tend to think the operator and what the operator works on are separate things. Values aren't functions, or data isn't a program.

A "higher-order" thinking is like thinking about functions work on functions, or programs work on programs. This mode of thinking opens up new source of ideas. For example, I did one thing for to improve program X, and another thing to improve program Y; can I write a program Z that does the same kind of improvement for X, Y, and other future programs? If I feed Z itself to Z then, can I improve Z itself? You have an interpreter P. Can you write a program Q on P that, when interpreted, takes a source S and produce a program S' that's more efficient than S? If you can, what if you feed Q itself to the program Q running on P? Will that process converge? If so, it's a sort of fixed point. What will it be like?

I work as a programmer and frequently encounter this "program generating programs" pattern. It is not some kind of tips that can be applied directly into everyday coding, but it allows me to climb one step higher in the abstraction ladder, giving wider vision on the program I'm working on.

I'll copy the response here:

What blew my mind is how it forces an appreciation for the nature and power of thinking functionally. Getting a feel for function composition, combinators and lambda calculus opens the door to a very different approach for creating programs.

This link (from the comments on the OP) is actually a very interesting yet simple explaination of the Y-Combinator.

http://mvanier.livejournal.com/2897.html

Reply on news.ycombinator.com