Live data from Hacker News

My Most Important Project Was a Bytecode Interpreter

gpfault.net

131–140 of 154 posts

Re: My Most Important Project Was a Bytecode Interpreter

#131
post #21

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?

Tracks I've done and suggested to friends and colleagues as learning experiences: * Compression (lossless, lossy, image, audio, texture, video) * Languages (bytecode interpreter, AST interpreter, parser/lexer for a simple language, simple JIT, understanding instruction scheduling) * DSP programming (writing programs for fast, branchless math) * Comfort with binary and binary formats (start with packfiles .zip/.tar, m…

A blog post detailing resources etc would be heaven.

Re: My Most Important Project Was a Bytecode Interpreter

#132
post #65

Earlier quoted context omitted.

Hence "not to be confused with PCREs", which most pseudo-regex implementations are based off of.

Did you edit the comment? I cannot recall reading that at all, but I may have been in a hurry.

Nope, didn't change it!

Re: My Most Important Project Was a Bytecode Interpreter

#133

Earlier quoted context omitted.

Even experts wouldn't do this on their own. It takes teams and a lot of time. A lot of thought can go into a few hundred lines of code. It needs math oriented people, it needs OS-oriented people, people who are experienced with exploiting systems. As I said, it's good to do it for fun and to learn, but there's no reason to do it for production. It's almost always a case of ignorance and overconfidence. The problem is…

> Even experts wouldn't do this on their own Did you miss the part where I mentioned code review? And the one where I said I would never invent my own primitives? > A lot of thought can go into a few hundred lines of code. I can attest to that. I can also confirm that most such though went in the design of the primitive itself. Most implementations in pure C are pretty straightforward, almost naive. Seriously, take a…

I'm not saying it's impossible to do. It depends on how "deep" you want to go. "Rolling your own crypto" can have different meanings. It can mean designing a new hash algorithm or encryption algorithm, or opening up a crypto book and reading some pseudocodes and formulas and then implementing them, or it can mean something more high level.

The higher you go the less error-prone it becomes.

Anyway, if you think you can realistically estimate the risks involved and you have the skills to do it, then perhaps you can. You'd definitely be in the top 0.1% of developers or even better. For the vast vast majority (the rest of us), it's not worth doing. It's very likely that we'd do something where we don't even know that we don't even know we should pay attention to. Again, unknown unknowns. When I read about bugs and exploits in security code, I always realize how difficult it is to get it right.

By the way, why do you think that the consensus is the way it is? Is it spread by security and crypto developers so that there's less competition?

Re: My Most Important Project Was a Bytecode Interpreter

#134
post #104

I'm thinking a lot of the complexity of writing a compiler stems from the usage of inappropriate tools. I.e. I would rather kill myself than write a lexer in C (without yacc / bison), but using parser combinators it's a rather trivial task. Similarly, annotating, transforming, folding, pattern matching on, CPS transforming etc. the produced AST is pretty trivial in a language that supports these constructs. And again…

> I would rather kill myself than write a lexer in C

I've written several lexers in C-like languages, it's not that painful. I wouldn't dare write a parser though.

Re: My Most Important Project Was a Bytecode Interpreter

#135
post #102

Earlier quoted context omitted.

Concerning last point, do you know nice example of non-scanline-based 2D renderers ?

2D renderers? Do you mean rendering 2D shapes? In that case, scanline is probably the most efficient thing you can do, but most renderers are not scanline. The only modern 2D scanline renderer I know of is in the Flash Player code. For a 3D renderer, I recommend fgiesen's series as linked above, and the older series by Nicolas Capens: http://forum.devmaster.net/t/advanced-rasterization/6145

Yes, 2d shapes. I'm writing vector drawing software and I use agg as backend (which use scanlines). In the long term it could be a good think to use or implement a more modern back-end.

Re: My Most Important Project Was a Bytecode Interpreter

#136
post #111
post #102

Earlier quoted context omitted.

Concerning last point, do you know nice example of non-scanline-based 2D renderers ?

A very informative tutorial on high performance edge-function based rasterization: https://fgiesen.wordpress.com/2013/02/17/optimizing-sw-occlu... (articles 6, 7, 8, others are not closely related) As far as I know modern hardware has been non-scanline-based for ages btw.

Thanks, looks very interesting. But it seems more 3D-oriented than 2D oriented.

Re: My Most Important Project Was a Bytecode Interpreter

#137
post #126

Earlier quoted context omitted.

* A database (transaction, lock managers, buffer/IO management, etc). * An MVC web framework. * A GUI validation library. * A JavaScript UI library. * An iteratee implementation. * An Erlang-style actors library in another language. * Implementing for-yield, async-await, etc on top of delimited continuations. * Interpreters, typecheckers, code generators. * Some of an ECMAScript implementation. * Concurrent data stru…

I haven't find a good introductory yet complete resource about build a complete database. I'm on the hunt for it (building also a relational language).

While not exactly what you're looking for, The Definitive Guide to SQLite takes you from writing a SELECT statement all the way to an overview of SQLite internals. O'Reilly also published a booklet called Inside SQLite that goes a bit deeper into the subject. I suggest SQLite because the source code is superb (seriously, some of the most readable, most logically organized and best commented C code you'll ever see) and it's a fairly small codebase with a huge community.

And then there is Database Systems, The Complete Book where the second half of the book offers in deep coverage of the implementation of database systems.

Re: My Most Important Project Was a Bytecode Interpreter

#138

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…

A regular expression is by definition a regular grammar, the least mighty language in the chomsky hierarchy and realizable by finite state automaton. You can get something similar to a virtual equivalent of a turing complete language, due to the fact that the tape of the turing machine is, contrary to the hypothetical theory, practically limit by recourses. CPUs are finite state automatons, yet we use them to solve p…

Real computers are much closer to linear bounded automata than full Turing machines.

https://en.m.wikipedia.org/wiki/Linear_bounded_automaton

Re: My Most Important Project Was a Bytecode Interpreter

#139
post #27

Two approaches are severely underused in the software world: 1) Domain-specific languages (DSLs) 2) Virtual machines (or just explicit state machines more generally) What I mean is, alot of problems could be solved cleanly, elegantly, more safely, and more powerfully by using one (or both) of the above. The problem is that when people think DSL or VM, they think big (Scheme or JVM) instead of thinking small (printf).…

Yes, absolutely agree. In LISP its obvious. 1. Every function is a tiny VM already. Every macro is a layer on top of a "compiler" to let you redesign a language. LISP gives much more power, precisely because every program is its own DSL, and all power of the language within that DSL is available. http://www.paulgraham.com/avg.html 2. In SICP they show how to build anything from LISP constructs. The elegant thing is t…

I whole-heartedly agree with your points. The ability to transform programs programmatically is extremely powerful. But, FWIW, I tend to see that as a form of generic programming.

When I think DSL I think regular expressions (especially PCREs) or SQL, where the syntax is tailored-designed for the specific task at hand.

The problem with in-program transformations is that you're still largely bound to the syntax of the host language. That's particularly the case with s-expression. That binding has amazing benefits (e.g. when auto-transforming programs into resumable state machines) but also puts constraints on the language syntax you can employ. That's not a problem when you're dealing with experienced engineers and devising technical solutions, but people tend to stay away from DSLs generally because they fear the burden imposed on others (including their future selves) having to learn a new language, how to use it, and how it integrates within a larger framework. You minimize that burden and make DSLs more cost-effective by maximizing the expressiveness of the DSL in the context of its purpose, and minimize switching costs by making the delineation between the host language and the DSL clear and obvious.

So, for example, in concrete terms you'd generally implement arithmetic expressions using infix notation. You can sorta implement infix notation in LISP, but you still have the s-expression baggage (such as it is; it's obviously not baggage from the expert's standpoint), which among other things makes it difficult to know where the host language ends and the DSL begins.

Lua had a head start on most popular languages with its LPeg PEG parser, which makes it trivial to parse custom DSLs into ASTs. For all the limitations of PEGs[1], they're just amazingly powerful. But to drive home my previous point, while expert LPeg users use the Snowball-inspired pattern where you instantiate PEG terms as Lua objects and build grammars using Lua's arithmetic operators (with operator overloading "a * b" means concatenation instead of multiplication, and "a^1" means repeat 1 or more times), newbies tends to prefer the specialized syntax which uses a notation similar to the original PEG paper and to typical regular expression syntax. (LPeg includes a small module to parse and compile that notation.)

Converting the AST into useable code is another matter, and that's an area where LISP shines for sure. And now that I think about it, the best of both worlds might be a PEG parser in LISP. But I'm completely ashamed to say I haven't use LISP or LISP derivatives.

[1] Yes, implementing left-recursion can be taxing using a PEG. But the syntax is so intuitive and powerful that the alternatives just can't replace it. Regular expressions are limited, too, but they'll never replace PEGs (or anything more sophisticated) because their expressiveness is just too powerful and cost-effective within certain domains. Instead we supplement regular expressions rather than replace them; and if PEGs continue catching on I expect PEGs to be supplemented rather than replaced.

Re: My Most Important Project Was a Bytecode Interpreter

#140
post #135

Earlier quoted context omitted.

2D renderers? Do you mean rendering 2D shapes? In that case, scanline is probably the most efficient thing you can do, but most renderers are not scanline. The only modern 2D scanline renderer I know of is in the Flash Player code. For a 3D renderer, I recommend fgiesen's series as linked above, and the older series by Nicolas Capens: http://forum.devmaster.net/t/advanced-rasterization/6145

Yes, 2d shapes. I'm writing vector drawing software and I use agg as backend (which use scanlines). In the long term it could be a good think to use or implement a more modern back-end.

Modern, fast 2D rasterization is a really hard problem, one which I'm currently writing a long-form article on. The classic Red Book stencil trick + Loop-Blinn from 2005 is the current state of the art, I think. I'd love to do more research there.

In terms of a software rasterizer, which can often be faster, it's just a matter of elbow grease and engineering. Use SIMD. Implement tons of special cases.

Write a simple polygon plotter to get you started -- just fill a triangle with white with simple edge functions. Then work your way up to arbitrary polygons. And then look into the theory behind antialiasing and such.

Post reply on HN