fadmmatt's comments

This is a great article. Continuations are rarely understood, which is unfortunate, given their power.

I wrote an article for my compilers class that gives examples of how to use continuations (in Scheme):

http://matt.might.net/articles/programming-with-continuation...

It covers basic stuff like exceptions and back-tracking search, and more advanced topics like threads, generators and coroutines.

The role the YC plays in this case is hiding the memoization.

The memoizing Y combinator is the same as the Y combinator, except it doesn't re-compute inputs it's already seen.

Writing recursive functions in "Y-combinator style" is a way to expose internal recursive call sites to external inspection and manipulation.

The Y combinator version still grows the stack.

Stay tuned: I'll be giving another crazy lambda talk at PLDI 2010 this summer.

Thanks! Will fix.

Re-post: http://news.ycombinator.com/item?id=1136998

Nifty.

I wrote up an alternate derivation based on fixed points for my compilers students:

http://matt.might.net/articles/implementation-of-recursive-f...

It also shows how to exploit the Y combinator to get speed-ups from memoization in JavaScript.

Yes.[1]

I do research in programming languages, but until yesterday, I never posted much about my research area.

I use my blog to post on topics related to courses I teach. (Mostly advanced compilers and static analysis.)

I also post on new ideas from others that I don't have time to do original research in, but that I find useful or interesting.

I'm also using my blog to recruit students for our Ph.D. program. It worked pretty well for that this year.

[1] http://matt.might.net/articles/

If you're interested in more Church, here's the blog post I wrote for my compilers students (with code) on Church encodings:

http://matt.might.net/articles/church-encodings-demo-in-sche...

When building a compiler, I have my students use Church encodings to eliminate many constructs at first. As we learn how to handle each construct, we steadily drop the Church encodings and performance improves.

Just curious where you got the number $500,000

I've heard ballpark estimates that the total wealth of the U.S., the sum of all assets (bridges, buildings, companies, cars) minus debts is roughly $80-$90 trillion. Wikipedia seems to think it's nearer to $60 trillion.

Assuming $90 trillion and 300mil people, if we divided up the wealth of everyone (not just the top 1%) and redstributed, we'd only get to $300,000 per person. If the top 1% hold a third of all wealth, you've got at most $100,000 per person.

No studies?

http://www.dvorak-keyboards.com/Dvorak_vs_qwerty_keyboard_te...

Remember: A study need not be published in a journal and well-typeset to be scientific.

In my experience, yes.

I switched to Dvorak a couple years ago, and I've been glad I did. I used to have terrible pain in my wrists and forearms. For eliminating pain, switching to Dvorak was as effective as switching to an expensive ergonomic keyboard.

I went cold turkey, so I felt like a stroke patient for the first four days. It was a very awkward and frustrating feeling. Within a week, I could type fast enough to code. (Coding doesn't require a fast typing speed.) It took about two weeks to get back to email/IM speed.

I'm probably not as fast as I was at QWERTY (110 wpm -> 90 wpm), but I'm certainly fast enough. If I do 15 years on Dvorak, I'll probably reach 110 wpm again.

I'd recommend doing an hour of typing exercises each day, and napping after each exercise to let it sink in. Each time I woke up from a nap, I was much better at the exercise from before the nap.

I wrote up my experience on my blog if you're interested:

http://matt.might.net/articles/preventing-and-managing-rsi/

For implementing languages, I highly recommend Scheme, Haskell and Scala.

These languages are hell-on-wheels for tearing apart and transforming syntax trees.

I teach a compilers class, and I encourage my students to use a mixture of Scala and Scheme. If you're thinking about implementing a language, you might want to look at some of the blog posts I wrote for my students:

* A Scheme interpreter in Scala: http://matt.might.net/articles/denotational-interpreter-for-...

* A meta-circular Scheme interpreter: http://matt.might.net/articles/metacircular-evaluation-and-f...

* Compiling Scheme to C: http://matt.might.net/articles/compiling-scheme-to-c/

* Compiling Scheme to Java: http://matt.might.net/articles/compiling-to-java/

* Architectures for interpreters: http://matt.might.net/articles/writing-an-interpreter-substi...

SICP and HtDP are good for starting out.

I often use Scheme when I teach compilers, and I've got a few Scheme-related blog posts designed for the curious student:

* Church encodings: http://matt.might.net/articles/church-encodings-demo-in-sche...

* Macro-generating macros: http://matt.might.net/articles/implementation-of-scheme-vect...

* Programming with continuations: http://matt.might.net/articles/programming-with-continuation...

Here's a short implementation (with explanation) in Scheme:

http://matt.might.net/articles/implementation-of-regular-exp...

Hold the amusement--the third project for the class is (of course) a Scheme -> CPS -> C compiler:

http://matt.might.net/teaching/fall-2009-advanced-compilatio...

Naturally, students are required to implement call/cc.

And, in my static analysis class last spring, project 2 was CPS conversion + 0CFA:

http://matt.might.net/teaching/spring-2009-programming-langu...

-Matt

Don't forget that Java already has anonymous classes, which can be used to mimic closures.

I taught my advanced compilers class how to compile Scheme directly to Java by using them to implement lambda:

http://matt.might.net/articles/compiling-to-java/

In fact, as the link above points out, anonymous classes are flexible enough to express the Y combinator, allowing "recursion-less recursion" in Java.

I think the coolest way to write a lexer is to use the derivative of regular expressions:

http://matt.might.net/articles/implementation-of-regular-exp...

It's surprisingly easy to implement, as the prior example demonstrates in Scheme.

This is the technique I recommend to my advanced compilers class.

Don't forget the Y combinator and the memoizing Y combinator:

http://matt.might.net/articles/implementation-of-recursive-f...

The lambda calculus is Turing-complete, so the following language is sufficient to encode any computable function:

exp ::= var | (lambda (var) exp) | (exp exp)

Check out

http://matt.might.net/articles/church-encodings-demo-in-sche...

To see how to build numbers, booleans, lists, conditionals and recursion out of pure lambdas.

Even cooler is that these tricks work in languages like JavaScript too:

http://matt.might.net/articles/implementation-of-recursive-f...

Thanks for pointing that out.

I don't remember why I did it that way.

I changed them to more sensible variable names.