fadmmatt

Yes.

It will look suspiciously similar to the Scripting Language Design and Implementation class that I'll be teaching.

This kind of stuff also showed up in my program analysis and advanced compiler classes, too.

One of the class projects was to implement first-class macros, and we used an interpreter that looked a lot like the one from this article:

http://matt.might.net/articles/metacircular-evaluation-and-f...

(/article author)

Sure, but the article doesn't use eval.

That's a good question, actually.

Lisp macros need knowledge of the structure of the s-expression.

Certainly one can Church encode s-expressions and provide defmacro.

Gensym is trickier. Hygiene might be really challenging.

I might actually try that out.

(/article author)

I was an entrepreneur (failed twice), and I'm now a professor.

Being a pre-tenure professor is way more terrifying than being an entrepreneur was.

And, depending on the field, between 25% and 75% of your salary as a professor will come from being able to procure external funding.

If you can't convince the funding agencies to pay you, then tenure buys you an office, a teaching load and health care.

It's been terrifying for me because my hit rate is about the same as Matt's. I've had very little luck getting funding for my research.

And, at the last funding panel I served on, the funding rate was down to 5%. My own fund-seeking overhead is now at 60% of my time, and I'm still not getting any.

Either we have too many scientists, or not enough science funding. I don't think the current system is sustainable.

You can't do this with #define alone. You can pass these "functions" around arbitrarily, and it still works.

Good question.

In short, you can use the macros to hide the context-switching (yielding).

You could, for instance, force every function to perform a context switch right after its called. Since languages like Scheme encode even loops with function call, you're guaranteed to eventually hit a switch point. (And, if you allow other looping constructs, you could use macros to hide a yield inside them as well.)

When I taught advanced compilers last semester, one of the projects was a Scheme-to-C compiler that implemented first-class continuations via call/cc.

I realized when going over that material, however, that most students didn't know what a continuation was, or how to use them, so I created a "by-example" tutorial:

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

It covers exceptions, backtracking-search, the magic "amb" function, magic sat-solving, generators and cooperative threads.

Neat; but C++0x does this:

[](int x, int y) { return x + y; }

instead of this:

lambda<int> (x,y) --> x + y

Ironically, the template hack could be shorter in many cases.

(Article author here.)

I'd love to use Haskell, but I'm helping out on an exascale DoE project, and C++ is all we're allowed to use. Ugh.

Of course, lambdas don't make C++ more powerful, but that's just reductio ad Turing tar-pit.

You can turn that argument around, too: there's no problem you can solve with C++ that you can't solve with lambdas alone:

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

If programming languages were about computational power, we would have stopped with Fortran.

Programming languages are about the freedom of expressions.

Milner, Robin (1978), "A Theory of Type Polymorphism in Programming", Jcss 17: 348–375

I don't know if there's a free copy online anywhere.

The Damas-Milner paper is the sequel; it presents an alternate algorithm for type inference.

Benjamin Pierce's "Orange Book" is one of the best references now.

For anyone that uses an ML (e.g. OCaml), Haskell or Scala, Milner was responsible for the Hindley-Milner type system and inference algorithm that sits at the foundation of these languages.

It ignited a wave of research into type theory that continues to this day, yet in many ways, Hindley-Milner is still the most significant contribution to the field.

I remember reading his original paper on polymorphic typing for my qualifiers and being struck by the elegance and approachability of his writing.

Well worth a read.

In case anyone needs them, I wrote up Okasaki red-black trees for Scala:

http://matt.might.net/articles/implementation-of-immutable-p...

Back when I took calculus in high school, the instructor asked for a show of hands for first-borns. All hands but one went up--well above 80%. I've wondered why that was so ever since. Why weren't middle and younger children pushing themselves to get into the "advanced" math classes?

My brother in the Army can still see it, so it's apparently not all government.

By the way, he can't get to Hacker News.

Can anyone check to see if http://matt.might.net/ is blocked?

I host it on a linode.

Thanks!

* Does the transfer function not need to take some input other than the state?

It depends on how you're encoding things. You might want to supply the I in I/O as an extra parameter to the transfer function.

Or, you could kick off the execution with the state containing a (possibly infinite) sequence representing all of the I/O events it will encounter during execution.

For the most part, transfer functions operate on just states.

* Can you convert a denotational semantics to an operational semantics (and vice versa)? Is there any value in doing this?

Yes, Olivier Danvy has a strong research program in this area. He has a battery of techniques that allow you to (almost) mechanically calculate one kind of semantics from another.

In many cases, calculating an operational semantics from a denotational semantics is the easiest way to prove their equivalence.

If you're wondering what things like "operational" and "denotational" mean and what they look like in code, I created this article for my compilers students:

http://matt.might.net/articles/writing-an-interpreter-substi...

Short version:

* A denotational semantics is a function M : Program -> (Value -> Value) that maps a program to a mathematical function.

* An operational semantics is a relation (=>) between consecutive machine states. That is, if state => state' holds, then the machine transitions from state to state'.

* The relation in a "big-step" operational semantics need not be decidable. Big-step relations are usually recursive.

* The relation in a "small-step" operational semantics must be decidable.

* When you implement a transition relation, =>, it's usually implemented as a function. That is, if you have a relation R \subseteq State x State, you can encode this as a "transfer function" f : State -> 2^State.

Herb Simon noted the optimal solution is often infeasible a long time ago.

He argued that economic agents rarely finding a satisfying solution to their constraints, and instead choose a "satisficing" or "good-enough" solution.

Simon also noted that the satisficing solution found by humans is often close to the optimal solution.

He got (and deserved) a Nobel prize for these two observations.

I find work of the flavor "X reduces to P = NP, so Nyah!" to be deeply unsatisfying and misleading.

For problems of human importance, good-enough solutions to NP problems can often be found in a reasonable amount of time.

In fact, state-of-the-art SAT solvers are mind-bogglingly fast (on average). They can find solutions in seconds, where the theoretical worst case solution time is many-fold the expected lifetime of the universe.

Generating a hard instance of SAT is actually hard to do. One of the few reliable techniques we know of is to encode prime factorization into a circuit. This is good news for crypto, but bad news for anyone looking to show the real-world intractability of a process by reducing it to P=NP. Few processes in nature actually mimic prime factorization or graph isomorphism.

Enhance!

http://www.youtube.com/watch?v=Vxq9yj2pVWk

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.