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

Building a Lox Interpreter in Julia

lukemerrick.com

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Building a Lox Interpreter in Julia

#11

Post by adgjlsfhk1 »

kwertzzz wrote: post #7
lukemerrick wrote: post #2

Disclaimer: I wrote this blog post. If this were an "Ask HN" post, though, the question would be "What next after reading Crafting Interpreters?" I have only done the tree-walk interpreter half of the book, but I'm already excited to move beyond Lox, and I'm curious to hear what others have done in this situation.

I am wondering why the julia lox interpreter is so slow. Could it be that there is a lot of type unstable code or could it be an issue with julia's garbage collector? (I can relate to the comment that it is quite hard to find usable information from julia's profiler).

I'm pretty sure it is type instability. The faster way to do this would be with something like https://github.com/YingboMa/Unityper.jl which would fix that. The problem with profiling unstable code in Julia is that it makes everything slow so the profiler will just show a big mess of everything being slow. We do need better resources, but I have no idea what they would like like.

Re: Building a Lox Interpreter in Julia

#13

Post by TwentyPosts »

lukemerrick wrote: post #2

Disclaimer: I wrote this blog post. If this were an "Ask HN" post, though, the question would be "What next after reading Crafting Interpreters?" I have only done the tree-walk interpreter half of the book, but I'm already excited to move beyond Lox, and I'm curious to hear what others have done in this situation.

Personally, I found "Writing an Interpreter in Go" better than "Crafting Interpreters". It has a follow-up book titled "Writing a Compiler in Go", which (similar to Crafting Interpreter's second half) implements a virtual machine. The books take a lot of inspiration from Crafting Interpreters.

If this sounds at all appealing to you, I would check it out. I found Monkey so far somewhat more compelling than Lox (might be personal preference, though), and I thought the exposition (and code quality) was overall better. Go is also very easy to pick up.

Re: Building a Lox Interpreter in Julia

#14

Post by nsajko »

adgjlsfhk1 wrote: post #11
kwertzzz wrote: post #7

Earlier quoted context omitted.

I am wondering why the julia lox interpreter is so slow. Could it be that there is a lot of type unstable code or could it be an issue with julia's garbage collector? (I can relate to the comment that it is quite hard to find usable information from julia's profiler).

I'm pretty sure it is type instability. The faster way to do this would be with something like https://github.com/YingboMa/Unityper.jl which would fix that. The problem with profiling unstable code in Julia is that it makes everything slow so the profiler will just show a big mess of everything being slow. We do need better resources, but I have no idea what they would like like.

What do you mean by "We do need better resources"?

Re: Building a Lox Interpreter in Julia

#15

Post by cdcarter »

erichocean wrote: post #9
lukemerrick wrote: post #2

Disclaimer: I wrote this blog post. If this were an "Ask HN" post, though, the question would be "What next after reading Crafting Interpreters?" I have only done the tree-walk interpreter half of the book, but I'm already excited to move beyond Lox, and I'm curious to hear what others have done in this situation.

I'd do the second half of the book, it's got plenty of important techniques that aren't taught in the first half. Once you've done that, you can see how it's done "for real" in a production setting by reading the source code to Wren (by the same author). [0] Wren's implementation maps very closely to the C implementation of Lox. At that point, you're ready to do your own language. As far as compilation techniques go,…

I agree on the suggestion to do part two, it's where things get really fun!

One thing you can do with the finished Lox (or Monkey, if you prefer WACIG) before going into the world of intermediate representations is implementing a peephole optimizer. You look for reducible patterns in the bytecode, and replace them with optimized bytecode. You can also look for certain patterns and replace naive implementations with native builtins/intrinsics. You can work with the raw bytes of the bytecode, so you don't need to introduce an IR just yet.

The Apex compiler at Salesforce does a vast majority of its optimizations as peeps.

EDIT: I _just_ wrote another comment to someone asking similar questions a few days ago. Here's a link to the parent question, check out my thoughts as well as others in the thread. https://news.ycombinator.com/item?id=36119915

Re: Building a Lox Interpreter in Julia

#16

Post by adgjlsfhk1 »

nsajko wrote: post #14
adgjlsfhk1 wrote: post #11

Earlier quoted context omitted.

I'm pretty sure it is type instability. The faster way to do this would be with something like https://github.com/YingboMa/Unityper.jl which would fix that. The problem with profiling unstable code in Julia is that it makes everything slow so the profiler will just show a big mess of everything being slow. We do need better resources, but I have no idea what they would like like.

What do you mean by "We do need better resources"?

There currently don't exist great tools to figure out why type unstable code is slow. @code_warntype and Cthulhu can help find type stability problems, but they're pretty hard to use for newer users (or big functions)

Re: Building a Lox Interpreter in Julia

#17

Post by mollerhoj »

lukemerrick wrote: post #2

Disclaimer: I wrote this blog post. If this were an "Ask HN" post, though, the question would be "What next after reading Crafting Interpreters?" I have only done the tree-walk interpreter half of the book, but I'm already excited to move beyond Lox, and I'm curious to hear what others have done in this situation.

I really wish Bob would write a “Crafting Type Checkers” sequel.

Re: Building a Lox Interpreter in Julia

#18

Post by xgdgsc »

lukemerrick wrote: post #2

Disclaimer: I wrote this blog post. If this were an "Ask HN" post, though, the question would be "What next after reading Crafting Interpreters?" I have only done the tree-walk interpreter half of the book, but I'm already excited to move beyond Lox, and I'm curious to hear what others have done in this situation.

https://github.com/tshort/StaticCompiler.jl/issues/59 Would working on this feasible?

Re: Building a Lox Interpreter in Julia

#19

Post by nextaccountic »

mollerhoj wrote: post #17
lukemerrick wrote: post #2

Disclaimer: I wrote this blog post. If this were an "Ask HN" post, though, the question would be "What next after reading Crafting Interpreters?" I have only done the tree-walk interpreter half of the book, but I'm already excited to move beyond Lox, and I'm curious to hear what others have done in this situation.

I really wish Bob would write a “Crafting Type Checkers” sequel.

There's Types and Programming Languages by Benjamin Pierce

Re: Building a Lox Interpreter in Julia

#20

Post by lukemerrick »

adgjlsfhk1 wrote: post #11
kwertzzz wrote: post #7

Earlier quoted context omitted.

I am wondering why the julia lox interpreter is so slow. Could it be that there is a lot of type unstable code or could it be an issue with julia's garbage collector? (I can relate to the comment that it is quite hard to find usable information from julia's profiler).

I'm pretty sure it is type instability. The faster way to do this would be with something like https://github.com/YingboMa/Unityper.jl which would fix that. The problem with profiling unstable code in Julia is that it makes everything slow so the profiler will just show a big mess of everything being slow. We do need better resources, but I have no idea what they would like like.

I actually played with Unityper.jl and SumTypes.jl, but my conclusion was that if I was going to depart from dispatch on Julia types in my code, I might as well just stick to an untyped tree, since either way I'd have to have a single `evaluate` function for interpreting any kind of node.

Reconsidering now, it seems that there might be benefits beyond type dispatch to having a typed syntax tree, so maybe I'll give that a shot as a next step!

Post reply on HN