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

My Most Important Project Was a Bytecode Interpreter

gpfault.net

Post reply on HN
Print view View original

51–60 of 154 posts

Re: My Most Important Project Was a Bytecode Interpreter

#51

Post by zodiac »

c-smile wrote: post #49
sillysaurus3 wrote: post #3

Also: a software rasterizer. Most people refuse to write one because it's so easy not to. Why bother? It will make you a better coder for the rest of your life. Let's make a list of "power projects" like this. A bytecode interpreter, a software rasterizer... What else?

Hmm, rasterizer was just a starting point for me on the way to understand "how browser works". Having just a rasterizer is like naked VM without bytecode compiler. So I decided to add HTML/CSS engines to it. But if you have HTML/CSS then why not to add scripting to it? So added VM executing bytecodes, GC and compiler producing those bytecodes. Having VM I thought that it would be cool to have built-in persistence in…

I think they meant rasterization as in http://www.scratchapixel.com/lessons/3d-basic-rendering/rast... instead of in the context of browsers...it's not a very precise term

Re: My Most Important Project Was a Bytecode Interpreter

#52

Post by khedoros »

voltagex_ wrote: post #16
zeta0134 wrote: post #9

Earlier quoted context omitted.

I really recommend a raytracer, especially to anyone interested in graphics. It's straightforward, powerful, infinitely expandable with optional features, and opens up a ton of discussion about performance, code complexity, and general organization. Plus it's fun, in an instant gratification kind of way.

Every now and then I get interested in demoscene programming. I've never even been able to get a triangle to render on the screen - except with something like XNA. Do you think there's any value in going back to say, DOS based VGA programming? People in #osdev thought I was a bit strange for wanting to write a bootable kernel that only put pixels on the screen, but I really enjoy the idea of starting with plotting pi…

Are you more interested in actually writing to PC VGA registers, or just the idea of writing a pixel-by-pixel renderer? There are bindings for SDL and SFML in a lot of languages, and the web technology option mentioned by the sibling comment.

If you like the idea of "DOS-based VGA programming" (taken literally), you could also find a DOS compiler or assembler and run it in DosBox. All of IBM's hardware-level documentation can still be found online: http://www.mcamafia.de/pdf/pdfref.htm

Re: My Most Important Project Was a Bytecode Interpreter

#53

Post by adrianratnapala »

chrisseaton wrote: post #33
ender7 wrote: post #22

Earlier quoted context omitted.

The first step in compilation is lexing -- converting a character stream to a stream of semantic "tokens", where a token might be "a number literal" or "the 'while' keyword" or a single character token like "{". This process is usually done via regexs.

I didn't think of lexer rules as regular expressions but I suppose they are of course. But I can't imagine a lexer would ever be the performance bottleneck in a compiler.

According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process).

I am not sure if this is true any more. It probably depends on the language.

Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and difficult languages like C++ will shift the bottlenecks to later stages.

Re: My Most Important Project Was a Bytecode Interpreter

#54

Post by adrianratnapala »

wyager wrote: post #38
robertelder wrote: post #13

One of the moments where I really started to feel like I was starting to 'see the matrix' was when I was working on a regex engine to try to make my compiler faster (it didn't, but that's another story). The asymptotically fast way to approach regex processing actually involves writing a parser to process the regex, so in order to write a fast compiler, you need to write another fast compiler to process the regexes t…

I mean, the whole point of regexes (not to be confused with PCREs) is that any given regex is isomorphic to some canonical finite state machine. It is, specifically speaking, a tiny description of an FSM over the alphabet of ASCII characters (or whatever charset you're using). Interestingly, regexes/FSMs are (IIRC) the most powerful class of machines for which equivalence is decidable. So if you give me any two regex…

Presumably that means "this is not true for any more powerful class of grammars".

Any particular pair grammars from that class. I mean if you showed me a yacc grammar for Pascal and another one for Java, I am sure I could prove they were ineqivelent.

More tricky, if you gave someone clever a hand written Pascal parser and that same yacc grammar she could probably prove equivilency with some effort. But there is no guarantee that this is always possible.

Re: My Most Important Project Was a Bytecode Interpreter

#55

Post by wyager »

adrianratnapala wrote: post #54
wyager wrote: post #38

Earlier quoted context omitted.

I mean, the whole point of regexes (not to be confused with PCREs) is that any given regex is isomorphic to some canonical finite state machine. It is, specifically speaking, a tiny description of an FSM over the alphabet of ASCII characters (or whatever charset you're using). Interestingly, regexes/FSMs are (IIRC) the most powerful class of machines for which equivalence is decidable. So if you give me any two regex…

Presumably that means "this is not true for any more powerful class of grammars ". Any particular pair grammars from that class. I mean if you showed me a yacc grammar for Pascal and another one for Java, I am sure I could prove they were ineqivelent. More tricky, if you gave someone clever a hand written Pascal parser and that same yacc grammar she could probably prove equivilency with some effort. But there is no g…

Yes, that is what I meant.

> I mean if you showed me a yacc grammar for Pascal and another one for Java,

This is why I said "any", and not "all". In most practical cases, you can tell if two grammars are different, but it's easy to construct cases where you can't.

Re: My Most Important Project Was a Bytecode Interpreter

#56

Post by kjax »

chrisseaton wrote: post #33
ender7 wrote: post #22

Earlier quoted context omitted.

The first step in compilation is lexing -- converting a character stream to a stream of semantic "tokens", where a token might be "a number literal" or "the 'while' keyword" or a single character token like "{". This process is usually done via regexs.

I didn't think of lexer rules as regular expressions but I suppose they are of course. But I can't imagine a lexer would ever be the performance bottleneck in a compiler.

Lexer generators typically allow describing rules with regular expressions, but through Thompson's construction, subset construction, and DFA minimization, you can end up with a blazing fast/optimized DFA that processes your input at maximum speed.

Re: My Most Important Project Was a Bytecode Interpreter

#57

Post by linkregister »

wahern wrote: post #47
linkregister wrote: post #34

Earlier quoted context omitted.

Yes, can you describe your SPF library? I'd love to learn more about how using a VM / state machine paradigm could help me approach CS problems.

You can find it here: https://github.com/wahern/dns/blob/master/src/spf.rl (The Ragel stuff is for parsing the SPF records and is a rather small detail. I always intended to remove it--it's a dependency that turns alot of people off--but never got around to it. But, FWIW, Ragel is awesome when you don't mind the build-time dependency.) Basically what happened was that when I set out to write an async SPF library I fo…

Thanks for responding. Great explanation! I agree that adhering to the SPF standard has diminishing returns as support is added for the more esoteric macros. Support for every single macro in the standard is almost certainly unnecessary.

I've seen a simple recursive descent parser to process SPF records, but never considered it could be done with a VM or a stack-based machine. Even with the DNS Lookup Limit, it appears you made the right choice to avoid the call stack for a fully async I/O interface.

Your coding style is simple but since I have never studied a VM before, I have trouble telling what's going on. You've inspired me to learn more!

Re: My Most Important Project Was a Bytecode Interpreter

#58

Post by wahern »

_RPM wrote: post #44
gopalv wrote: post #4

The project that affected my thinking the most was a bytecode interpreter[1]. I've had use for that knowledge, nearly fifteen years later - most of the interesting learnings about building one has been about the inner loop. The way you build a good interpreter is upside-down in tech - the system which is simpler often works faster than anything more complicated. Because of working on that, then writing my final paper…

Interesting. One thing that I still haven't solved yet is the "break" and "continue" statement inside loops. For a break statement, it seems like it would just be the same a JMP with an address as the operand, but there would need to be some sort of registration of "The VM is in the loop now, and the break address is X", and continue would also be a JMP with an address to the top of the code for the loop. I haven't i…

You can implement those as part of a linking phase during bytecode generation: emit a placeholder value (e.g. 0) for the jump address and when you've finished compiling the block go back and fill-in the placeholder with the correct address/offset.

That's relatively easy when implementing an assembler for your opcodes. Just keep track of symbolic labels and their associated jump points (as a simple array or linked list) and process (i.e. finalize or "link") the jump points when the label address becomes known. My "assemblers" often have constructs like:

  L0
  ...
  J1
  ...
  J0
  ...
  L1
where L? registers a symbolic jump destination (i.e. x.label[0].offset = label_offset) and J? emits an unconditional jump and registers a link request (i.e. push(x.label[1].from, jump_opcode_offset)). When a block is finished all the offsets are known; you just process things like

  for (i = 0; i
Knowing when to emit symbolic label and jump instructions from the AST is a little more involved, but no more than analyzing the AST for anything else.

Supporting computed gotos would require much more bookkeeping, I'd imagine, and I'm not surprised few languages support that construct. Or maybe not... I haven't really thought it through.

One cool thing about this whole exercise is that it helps to demonstrate why generating some intermediate representation can be easier (conceptually and mechanically) than directly generating runnable code in a single pass. It seems more complex but it really makes things easier.

Re: My Most Important Project Was a Bytecode Interpreter

#59

Post by hvidgaard »

wyager wrote: post #38
robertelder wrote: post #13

One of the moments where I really started to feel like I was starting to 'see the matrix' was when I was working on a regex engine to try to make my compiler faster (it didn't, but that's another story). The asymptotically fast way to approach regex processing actually involves writing a parser to process the regex, so in order to write a fast compiler, you need to write another fast compiler to process the regexes t…

I mean, the whole point of regexes (not to be confused with PCREs) is that any given regex is isomorphic to some canonical finite state machine. It is, specifically speaking, a tiny description of an FSM over the alphabet of ASCII characters (or whatever charset you're using). Interestingly, regexes/FSMs are (IIRC) the most powerful class of machines for which equivalence is decidable. So if you give me any two regex…

While it is true for Regular Languages (FSM) strict RegExs, it's hardly true for any contemporary implementation of RegExs. They have back references and other constructs that make them more powerful than a Regular Language, and thereby make it impossible to decide equivalence in the general case.

Re: My Most Important Project Was a Bytecode Interpreter

#60

Post by signa11 »

robertelder wrote: post #13

One of the moments where I really started to feel like I was starting to 'see the matrix' was when I was working on a regex engine to try to make my compiler faster (it didn't, but that's another story). The asymptotically fast way to approach regex processing actually involves writing a parser to process the regex, so in order to write a fast compiler, you need to write another fast compiler to process the regexes t…

> When you think more about regexes this way, you realize that a regex is just a tiny description of a virtual machine (or emulator) that can process the simplest of instructions (check for 'a', accept '0-9', etc.). Each step in the regex is just a piece of bytecode that can execute, and if you turn a regex on its side you can visualize it as just a simple assembly program.

which is _exactly_ what bpf does :)

Post reply on HN