Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

craftinginterpreters.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#11

Post by justinpombrio »

ASipos wrote: post #4

A bit of nitpicking: "the function to compute the truth value of a given proof" should be "the function that returns the truth value of a given statement" (1st change because it is confusing to use the word compute in two different ways, 2nd change is simply an error correction) "equivalent in power" should not link to the Church-Turing thesis, as the former is a mathematical statement, proved in any introductory cou…

More nitpicking:

> You can prove that by writing a simulator for a Turing machine in your language. Since Turing proved his machine can compute any computable function, by induction, that means your language can too.

That's not by induction, that's by composition or something.

> We almost have the third too. You can create and concatenate strings of arbitrary size, so you can store unbounded memory.

That's not true! Eventually you'll run out of memory & disk space. Turing machine tapes are infinite, you can't fit one in this puny universe.

EDIT:

> Syntactic sugar has a bad rap among the PL intelligentsia.

Um, what? I presume the author isn't aware of the large PLT group at Northeastern that continuously writes papers about macros, i.e. user-defined syntactic sugar, and develops Racket, a language built almost entirely out of syntactic sugar. Or maybe they're defining "syntactic sugar" to not include macros: if so, they should be more clear about that.

Also, I'm doing a PhD focusing on syntactic sugar, so I probably have authority to say: syntactic sugar has a very good rap among the PL intelligentsia. Languages with a needlessly complicated semantics have a bad rap, but that's different from having a large grammar. PL researchers are a lot more concerned about semantics than syntax.

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#12

Post by munificent »

DanPristupov wrote: post #7

I just want to thank Bob for the amazing "Game Programming Patterns" book. I can't recommend it highly enough. And since I'm also interested in compilers, I will buy "Crafting Interpreters” without a hesitation.

Thank you!

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#13

Post by munificent »

dang wrote: post #9
TekMol wrote: post #6

Earlier quoted context omitted.

Is the posting of a book chapter different from a blog post? The Show HN rules say blog posts can't be Show HNs. And the reason given is they "can't be tried out".

Yes, it's different. A book (assuming it's a real book and not something slapdash) is a major piece of work. Obviously some of the finer distinctions (e.g. what counts as a book chapter vs. an article) can get pretty arbitrary. But the broader lines aren't. The intent of Show HN is for people to share what they're working on. If we applied the strictest definition, the only thing anyone could easily 'try out' would b…

> A book (assuming it's a real book and not something slapdash) is a major piece of work.

It is, I hope. But if you're prefer I post these without "Show HN", I'm happy to. I thought it was worth doing it to make it more obvious that I was self-posting, but I can not do that if that's what others would prefer.

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#14

Post by munificent »

ASipos wrote: post #4

A bit of nitpicking: "the function to compute the truth value of a given proof" should be "the function that returns the truth value of a given statement" (1st change because it is confusing to use the word compute in two different ways, 2nd change is simply an error correction) "equivalent in power" should not link to the Church-Turing thesis, as the former is a mathematical statement, proved in any introductory cou…

Thanks for this! When I get home this evening, I'll tweak this. You're right on all accounts.

Except for the Neil Gaiman quote. I like Gaiman's wording better than Chesterton's and I think it's different enough that it makes sense to attribute it to him.

Also, man, what was up that Petêr guy? Who peed in his Cheerios?

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#15

Post by munificent »

justinpombrio wrote: post #11
ASipos wrote: post #4

A bit of nitpicking: "the function to compute the truth value of a given proof" should be "the function that returns the truth value of a given statement" (1st change because it is confusing to use the word compute in two different ways, 2nd change is simply an error correction) "equivalent in power" should not link to the Church-Turing thesis, as the former is a mathematical statement, proved in any introductory cou…

More nitpicking: > You can prove that by writing a simulator for a Turing machine in your language. Since Turing proved his machine can compute any computable function, by induction, that means your language can too. That's not by induction, that's by composition or something. > We almost have the third too. You can create and concatenate strings of arbitrary size, so you can store unbounded memory. That's not true!…

> That's not by induction, that's by composition or something.

Good point. I'll fix that.

> That's not true! Eventually you'll run out of memory & disk space. Turing machine tapes are infinite, you can't fit one in this puny universe.

Sure, but in practice, most people loosen that requirement. Otherwise, no implemented language is Turing-complete.

> Um, what? I presume the author isn't aware of the large PLT group at Northeastern that continuously writes papers about macros, i.e. user-defined syntactic sugar, and develops Racket, a language built almost entirely out of syntactic sugar.

The mini-essay is about what syntactic sugar the language designer chooses to add to the language. Language features that let users extend the syntax are outside of the scope of that.

I do note:

> Lispers famously claim their language “has no syntax”, while Smalltalkers proudly show that you can fit the entire grammar on an index card. This tribe has the philosophy that the language doesn’t need syntactic sugar. Instead, the minimal syntax and semantics it provides are powerful enough to let library code be as expressive as if it were part of the language itself.

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#16

Post by justinpombrio »

munificent wrote: post #15
justinpombrio wrote: post #11

Earlier quoted context omitted.

More nitpicking: > You can prove that by writing a simulator for a Turing machine in your language. Since Turing proved his machine can compute any computable function, by induction, that means your language can too. That's not by induction, that's by composition or something. > We almost have the third too. You can create and concatenate strings of arbitrary size, so you can store unbounded memory. That's not true!…

> That's not by induction, that's by composition or something. Good point. I'll fix that. > That's not true! Eventually you'll run out of memory & disk space. Turing machine tapes are infinite, you can't fit one in this puny universe. Sure, but in practice, most people loosen that requirement. Otherwise, no implemented language is Turing-complete. > Um, what? I presume the author isn't aware of the large PLT group at…

> The mini-essay is about what syntactic sugar the language designer chooses to add to the language. Language features that let users extend the syntax are outside of the scope of that.

What counts as part of the language? If you've coded in a lisp, you've used `and`, `or`, `cond`, `let*`, `letrec`, etc. All of those are defined by macros, but I don't think it's realistic to exclude them from being considered part of the language.

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#17

Post by sn9 »

munificent wrote: post #14
ASipos wrote: post #4

A bit of nitpicking: "the function to compute the truth value of a given proof" should be "the function that returns the truth value of a given statement" (1st change because it is confusing to use the word compute in two different ways, 2nd change is simply an error correction) "equivalent in power" should not link to the Church-Turing thesis, as the former is a mathematical statement, proved in any introductory cou…

Thanks for this! When I get home this evening, I'll tweak this. You're right on all accounts. Except for the Neil Gaiman quote. I like Gaiman's wording better than Chesterton's and I think it's different enough that it makes sense to attribute it to him. Also, man, what was up that Petêr guy? Who peed in his Cheerios?

> "It turns out that the answer to both is “no” and, in astonishingly, the two questions are deeply intertwined."

Did you forget a word here?

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#18

Post by kazinator »

justinpombrio wrote: post #16
munificent wrote: post #15

Earlier quoted context omitted.

> That's not by induction, that's by composition or something. Good point. I'll fix that. > That's not true! Eventually you'll run out of memory & disk space. Turing machine tapes are infinite, you can't fit one in this puny universe. Sure, but in practice, most people loosen that requirement. Otherwise, no implemented language is Turing-complete. > Um, what? I presume the author isn't aware of the large PLT group at…

> The mini-essay is about what syntactic sugar the language designer chooses to add to the language. Language features that let users extend the syntax are outside of the scope of that. What counts as part of the language? If you've coded in a lisp, you've used `and`, `or`, `cond`, `let*`, `letrec`, etc. All of those are defined by macros, but I don't think it's realistic to exclude them from being considered part of…

> What counts as part of the language?

Very simple: the arbitrary set of requirements documented in the reference manual for the language and (consequently) provided in the implementation.

Re: Show HN: “Crafting Interpreters” chapter, control flow and Turing-completeness

#19

Post by munificent »

sn9 wrote: post #17
munificent wrote: post #14

Earlier quoted context omitted.

Thanks for this! When I get home this evening, I'll tweak this. You're right on all accounts. Except for the Neil Gaiman quote. I like Gaiman's wording better than Chesterton's and I think it's different enough that it makes sense to attribute it to him. Also, man, what was up that Petêr guy? Who peed in his Cheerios?

> "It turns out that the answer to both is “no” and, in astonishingly , the two questions are deeply intertwined." Did you forget a word here?

Yes, yes I did. Would you believe I did three drafts of this?

I'll fix it tonight. Thanks!

Post reply on HN