HN Theater @HNTheaterMonth

An explanation by Gerald Sussman himself: https://www.youtube.com/watch?v=0m6hoOelZH8#t=1h12m30s

If you prefer video, here is an explanation of the Y combinator from Gerald Sussman himself: https://www.youtube.com/watch?v=0m6hoOelZH8#t=1h12m30s

⬐ selimthegrim

The kabbalah joke at 4:48 is priceless

The self-definition comment is a reference to the common LISP exercise of writing a "meta-circular evaluator"[1] - that is, writing a LISP interpreter in LISP. This is famously done[3] in "Structure and Interpretation of Computer Programs", which is a very popular textbook and MIT course which uses LISP as a teaching language[2]. This can be found for example, in lecture 7 of the SICP lecture series on Youtube[4].

Dijkstra's comment on this is quite acerbic, isn't it? Here is the full quote for easy reference:

> [LISP's] promotion of the idea that a programming language should be able to formulate its own interpreter (which then could be used as the language’s definition) has caused a lot of confusion because the incestuous idea of self-definition was fundamentally flawed.

I agree to the extent that the exercise of writing a LISP interpreter in LISP is indeed often a very confusing exercise for beginner, partly because writing any interpreter (or compiler) is fairly arcane for a beginner, and partly because keeping track of which parts are in implementation and which parts are in the target language can be made more difficult; also because it's easy to "cheat" and rely on outside language in inappropriate ways. I would recommend using a language you already know well and implementing a moderately simple language as a first exercise to a student. But on the whole the exercise of writing an interpreter in its own language - or alternatively writing a self-hosting compiler[5] - is rewarding and does teach you a great deal about how programs work.

I also can't agree the so-called "incestuous idea of self-definition" is "fundamentally flawed:" it is in fact fairly interesting and related to important meta-mathematical concepts like Godel numbering[6], reductions[7], and the Church-Turing thesis[8]. Writing a meta-circular evaluator seems like a reasonably concrete way to start building intuition towards these important ideas. Perhaps Dijkstra has in mind such problems as Curry's Paradox[9] or Russel's Paradox[10], both of which are paradoxes arising from self-reference? In my view a meta-circular evaluator is much closer in spirit to Godel numbering (which is valid and useful) than these paradoxes.

[1]: https://en.wikipedia.org/wiki/Meta-circular_evaluator

[2]: https://en.wikipedia.org/wiki/Structure_and_Interpretation_o...

[3]: http://www.sicpdistilled.com/section/4.1/

[4]: https://www.youtube.com/watch?v=0m6hoOelZH8

[5]: https://en.wikipedia.org/wiki/Self-hosting_(compilers)

[6]: https://en.wikipedia.org/wiki/G%C3%B6del_numbering

[7]: https://en.wikipedia.org/wiki/Reduction_(complexity)

[8]: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

[9]: https://en.wikipedia.org/wiki/Curry%27s_paradox

[10]: https://en.wikipedia.org/wiki/Russell%27s_paradox

⬐ kazinator

Dijkstra is very famous for his opinions, somewhat famous for a handful of mostly obvious algorithms like graph traversal that programmers keep reinventing while coding, and a pair of awful process synchronization primitives. Actual software, not so much, just some thing called "THE" and some role in an Algol 60 compiler.

My favorite is the FLAC algorithm. It's fairly simple to explain - take a signal input, pattern match a generative signal that closely matches the original or part of it, and the output is a combination of that generative code and the difference between it and it and the input.

Second favorite is the LISP REPL. Specifically the Eval function, thanks to this classic video of Sussman https://www.youtube.com/watch?v=0m6hoOelZH8

⬐ teddyh

That video, appropriately enough, also contains a definition and explanation of what the Y Combinator is.

⬐ nayuki

The actual algorithm you are describing is called https://en.wikipedia.org/wiki/Linear_prediction .

http://www.youtube.com/watch?feature=player_detailpage&v=0m6... A great little moment from this class.

⬐ ANTSANTS

No, no, don't spoil the best part!

⬐ None

None

⬐ bsaul

Thanks for the link. Last time someone posted about those courses i started watching them, but i didn't went up to there.

My problem now is that this really made me want to start coding my own Lisp.

⬐ JackMorgan

Thankfully chapter 4 demonstrates how to do just that! Want to make it lazy like Haskell? Syntax different from Scheme? You are limited only by your imagination. Round that off with the last chapter from Let Over Lambda and you can add in "or make it like Forth"!

⬐ bsaul

One thing i wonder though: i first wanted to code that lisp in haskell (learning two languages in one), but i'm not quite sure it's such a good idea, now that i've learned about homoiconicity.

Any advice ?

⬐ eru

You are one courageous individual. But you are not the only one. https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_... has got you covered.

⬐ bsaul

absolutely fantastic ! Thanks

(I like _why and I don't have any problem with the attention he receives or anything. But I did kind of agree with some of the "that's rubbish" responses to the "first" stuff.)

I'm reasonably sure I won't agree with you on any definition of art. But, uh, here's some stuff. I may-or-may-not think of some of it as art. I do think it's stuff that keeps the coding world from being some dreadful place of "craftsmanship" and "professionalism" and things.

The miniKanren presentations are wonderful. They're all "and now let's run this stuff backwards. Because because." http://www.infoq.com/presentations/miniKanren

Meta-circular evaluators. Page 13 of http://www.softwarepreservation.org/projects/LISP/book/LISP%... http://www.youtube.com/watch?v=0m6hoOelZH8&list=ECE18841... http://www.scheme.com/tspl4/examples.html#./examples:h7 ("After completing the preceding exercise, use the interpreter to run a copy of the interpreter, and use the copy to run another copy of the interpreter. Repeat this process to see how many levels deep it will go before the system grinds to a halt." :D)

SICP opens with this: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-3.html I think it's lovely.

http://en.wikipedia.org/wiki/Edsger_W._Dijkstra "One of Dijkstra's sidelines was serving as Chairman of the Board of the fictional Mathematics Inc., a company that he imagined having commercialized the production of mathematical theorems in the same way that software companies had commercialized the production of computer programs. He invented a number of activities and challenges of Mathematics Inc. and documented them in several papers in the EWD series."

Also obfuscated code and some esolang stuff, I guess.

I remember some competition that was about creating and hiding some bug that did some particular thing in code that appeared to do something else, in a way that seemed (if discovered) like it was a mistake. That was cute.

Oh, and maybe http://sigbovik.org/ Maybe not.