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

31–40 of 44 posts

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

#31

Post by pacaro »

oconnor0 wrote: post #8
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`

That doesn't explain why they would need a different precedence. `a + b - c` is not the same as `a - b + c` even through the precedence's of + and - are the same (in most syntaxes).

Granted, the intersection of precedence and associativity is a great source of confusion (and any number of annoying Facebook memes)

I'm not a formally trained mathematician, but one way to rationalize + and - having the same precedence, is to consider them as inverses of each other, so your two examples can be written as

a + -b + c

And

a + b + -c

At which point precedence and associativity no longer matter. The same can be done with multiplication and division

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

#32

Post by EamonnMR »

khedoros1 wrote: post #27
munificent wrote: post #12

Earlier quoted context omitted.

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.

Which game?

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

#33

Post by munificent »

yorwba wrote: post #30
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?

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

Oh, God, you're right. Thank you! You wouldn't know I actually edited this chapter twice.

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

#34

Post by dom0 »

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…

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

The common hand-wave for this is to assume that (1) the machine has big enough storage for the problem, otherwise you could not have the problem in the first place and (2) the algorithm can have an arbitrary time/space trade-off, so if it needed more memory than the physical bound, you could just have it run longer. Note that (1) is a non-sequitur, since the input tape is usually not included in the machine memory in the first place.

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

#35

Post by khedoros1 »

EamonnMR wrote: post #32
khedoros1 wrote: post #27

Earlier quoted context omitted.

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.

Which game?

Ultima Underworld. About 5 birds with one stone: game dev, reverse engineering, real mode X86 assembly (covered a subset of ARM in college), technical details of DOS, OpenGL graphics, and a dip into writing software renderers too.

I consider it a long-term hobby; it's not exactly a quick solo project.

I'm also looking at another one called Solar Winds. It came out at a similar time, but the whole game is smaller than just UW's binary, with a lot more of the game's content encoded directly in the binary. UW tends toward deep call stacks, and significant portions are written in C. SW is pretty flat with very few function calls, and I think that about 1/3 of the code is made of Sound Blaster drivers linked into the binary.

I took a look at Lemmings, but that was going to be kind of annoying. Most of the binary was encrypted and would be decrypted on the fly, sometimes in a 2-step operation, where it would be decrypted then copied backwards into a new location. There are already engine implementations for that, so it didn't seem worth the effort.

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

#36

Post by agumonkey »

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

May I ask your team website if there's one ? I'm curious about your research

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

#37

Post by agumonkey »

DonaldPShimoda wrote: post #28
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!…

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

The colored sets ?

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

#38

Post by agumonkey »

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.

Has anyone ever found a link between boolean (F2) and "normal" base (F[n], or N) arithmetics ?

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

#40

Post by DonaldPShimoda »

agumonkey wrote: post #37
DonaldPShimoda wrote: post #28

Earlier quoted context omitted.

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

The colored sets ?

I think you mean Flatt's "Binding as Sets of Scopes" [1]. Yeah, that's definitely something he's working on. There are a couple PhD candidates in his group who are also working on macros and hygiene, but I don't follow their research directly (we're just often in the same room so I hear about it).

[1] http://www.cs.utah.edu/plt/publications/popl16-f.pdf

Post reply on HN