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

21–30 of 44 posts

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

#21

Post by [deleted] »

kazinator wrote: post #18
justinpombrio wrote: post #16

Earlier quoted context omitted.

> 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.

[deleted]

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

#22

Post by sigjuice »

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…

Common Lisp has a whole bunch of syntax and syntactic sugar. e.g. ' (quote), #', &rest, &key, &optional and more.

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

#23

Post by sn9 »

munificent wrote: post #19
sn9 wrote: post #17

Earlier quoted context omitted.

> "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!

Haha I wouldn't worry about it.

I've seen more typos in professionally edited articles on major online newspapers.

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

#24

Post by [deleted] »

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!…

[deleted]

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

#25

Post by pvg »

munificent wrote: post #13
dang wrote: post #9

Earlier quoted context omitted.

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.

to make it more obvious that I was self-posting

Not really what Show HN is for, though, so if you skip it for just chapter updates (rather than the whole book) you'll probably get less guff.

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

#26

Post by analognoise »

munificent wrote: post #13
dang wrote: post #9

Earlier quoted context omitted.

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.

I like and appreciate it.

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

#27

Post by khedoros1 »

munificent wrote: post #12
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!

I'm reading it too, bit by bit! I've been writing file importers for an old game that I'd like to recreate, but I've never built a game engine before, and I'm getting to a place where I need to start tying things together to build the cohesive whole.

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

#28

Post by DonaldPShimoda »

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!…

I just wanna add that there is also a dedicated group at Utah working on hygiene and macros for Racket, headed by Matthew Flatt (who's somewhat relevant within the scope of Racket).

(Not contradicting you; just wanna throw my school in where I can!)

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

#29

Post by DonaldPShimoda »

rspeele wrote: post #10
pacaro wrote: post #5

The author asks why && and || need different precedence (Unless I misunderstood). This is because `a && (b || c)` has a different truth table than `(a && b) || c`

&& having higher precedence than || makes sense because && is boolean multiplication and || is boolean addition.

This makes so much sense but I never thought of it this way before so explicitly. Neat!

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

#30

Post by yorwba »

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?

Related to that, the two questions are

> “Can all true statements be proven?”, “Are there functions that we can define but not compute?”

And the answers are "no" and "yes", so to fit with "both answers are 'no'", the second question should be "Can we compute all functions we can define?".

Post reply on HN