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

101–110 of 154 posts

Re: My Most Important Project Was a Bytecode Interpreter

#101

Post by kefka »

halter73 wrote: post #68
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…

Isn't it possible to decide the equivalence of deterministic pushdown automata? Wouldn't DPDAs be considered more powerful than FSMs due to the addition of a stack? Wikipedia [1] shows there's a paper called "The equivalence problem for deterministic pushdown automata is decidable" that won the Gödel Prize is 2002. I haven't read the paper nor do I currently have access to it though. [1] https://en.wikipedia.org/wiki…

Here you go!

http://link.springer.com.sci-hub.cc/chapter/10.1007/3-540-63...

It was initially published in 1997.

Re: My Most Important Project Was a Bytecode Interpreter

#102

Post by Rexxar »

Jasper_ wrote: post #21
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?

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…

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

Re: My Most Important Project Was a Bytecode Interpreter

#103

Post by bonoboTP »

loup-vaillant wrote: post #98
bonoboTP wrote: post #77

Earlier quoted context omitted.

* Implementing Internet protocols (TCP, IP, SMTP etc) * Floating point manipulation and numerical computation * Rolling some own crypto (strictly for fun use)

Actually, implementing your own crypto for real is not so crazy. The best algorithms are surprisingly simple, and easy to make side-channel resistant. The only real difficulty I have so far is with modulo arithmetic on big numbers (for elliptic curves and one time authentication). With proper test vectors and some code review, crypto is in fact quite easy. More dangers lie un the use of crypto, especially when the AP…

No. Never roll your own crypto for production. If you only know one thing about security as a programmer, then it has to be this.

But you are right that crypto algorithms aren't specifically hard to implement compared with, say, computer graphics, image processing, gui programming or whatever.

But! The big difference is that crypto is attacked by other smart people. The bugs and design flaws in your scientific computing library are not hunted down by intelligent agents to purposefully break it. If people attacked your Paint clone to the same extent they attack computer security programs, then it would become just as hard to write them correctly as it is with crypto.

There are so many kinds of ways to get it wrong that beginners don't even know about. It's an "unknown unknowns" situation.

Re: My Most Important Project Was a Bytecode Interpreter

#104

Post by pka »

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, a nightmare in C.

That leaves codegen, but using the right abstractions it turns into a very manageable task as well.

Here's a compiler written in Haskell for LLVM [0].

[0] http://www.stephendiehl.com/llvm

Re: My Most Important Project Was a Bytecode Interpreter

#105

Post by loup-vaillant »

bonoboTP wrote: post #103
loup-vaillant wrote: post #98

Earlier quoted context omitted.

Actually, implementing your own crypto for real is not so crazy. The best algorithms are surprisingly simple, and easy to make side-channel resistant. The only real difficulty I have so far is with modulo arithmetic on big numbers (for elliptic curves and one time authentication). With proper test vectors and some code review, crypto is in fact quite easy. More dangers lie un the use of crypto, especially when the AP…

No. Never roll your own crypto for production. If you only know one thing about security as a programmer, then it has to be this. But you are right that crypto algorithms aren't specifically hard to implement compared with, say, computer graphics, image processing, gui programming or whatever. But! The big difference is that crypto is attacked by other smart people. The bugs and design flaws in your scientific comput…

Dogma, Dogma, Dogma.

Have you seen the size of the reference implementations for chacha20, blake2b, or poly1305? Those are tiny, a couple hundred lines for all three! There is very little room for errors to sneak in. Between test vectors, compiler warnings, and Valgrind, we can be pretty sure all bugs have been shaked out. Add in good old code review and the safety of this stuff is pretty much guaranteed.

Of course, I would never make the mistake of rolling my own OpenSSL clone (too big, bad API, some bad primitives), or even my own AES implementation (slow or prone to timing attacks).

Of course, I don't make the mistake of going blind. I read the literature before making any choice. If I don't know why some construction is considered safe, I don't use it. Due diligence first. And I certainly don't implement the first primitive that my search engine gets its hands on. I go for the most vetted alternatives.

Re: My Most Important Project Was a Bytecode Interpreter

#107

Post by Arcten »

anaccountwow wrote: post #45

This is a required hw assignment for a freshmen class @ cmu. https://www.cs.cmu.edu/~fp/courses/15122-s11/lectures/23-c0v... Given it has some parts already written in the interest of time...

What's even cooler, is that after building this VM (for the C0 language) as a freshman, you can come back as a junior/senior and write a compiler for that language in 15-411. It's a very cool way of going full circle.

Re: My Most Important Project Was a Bytecode Interpreter

#108

Post by bonoboTP »

loup-vaillant wrote: post #105
bonoboTP wrote: post #103

Earlier quoted context omitted.

No. Never roll your own crypto for production. If you only know one thing about security as a programmer, then it has to be this. But you are right that crypto algorithms aren't specifically hard to implement compared with, say, computer graphics, image processing, gui programming or whatever. But! The big difference is that crypto is attacked by other smart people. The bugs and design flaws in your scientific comput…

Dogma, Dogma, Dogma. Have you seen the size of the reference implementations for chacha20, blake2b, or poly1305? Those are tiny , a couple hundred lines for all three! There is very little room for errors to sneak in. Between test vectors, compiler warnings, and Valgrind, we can be pretty sure all bugs have been shaked out. Add in good old code review and the safety of this stuff is pretty much guaranteed. Of course,…

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 that in computer security defense is a lot harder than offense. If you make just one mistake, it can often lead to a compromised system.

Anyway, there's a lot of discussion on this topic around security.stackexchange, quora, reddit etc. The consensus is that it's a terrible idea.

Re: My Most Important Project Was a Bytecode Interpreter

#109

Post by Marazan »

signa11 wrote: post #61
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.

having written one as a slightly larger python thingy, i can fully attest to that. now that it is kind of done, i want to make it faster :) for example, having a home-grown vector_3d class kind of sucks (performance wise). it might be better to have vector_3d be actually based on, say, numpy.array ? once that is done, and i start seeing some real improvement, it might be possible to go the other route as well i.e. wr…

Simply replacing your own vector_3d class with numpy.array() won't actually speed you up that much as the overhead of creating all the tiny 3 element arrays kills you (I think I got only a 2x speed up from going from a pure python vector_3d to numpy arrays). Numpy is optimised for the creation of a small number of big arrays.

The massive enormous speed ups come from creating massive arrays and implicitly working on them in parallel. So instead of iterating through every pixel and creating a origin and direction vector for each one you create a Total_number_of_pixels X 3 numpy array and pass that to your ray tracing function. Due to the way numpy broadcasts arrays the amount of rewriting you need to do is incredibly minimal and the speed ups over pure python are astronomical.

Re: My Most Important Project Was a Bytecode Interpreter

#110

Post by errozero »

nice_byte wrote: post #50
voltagex_ wrote: post #16

Earlier quoted context omitted.

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…

You could skip writing a bootable kernel, and try that with microcontrollers :) It's possible to hook up a tiny lcd screen to an arduino

You can even wire up an arduino into a vga monitor. There are a few vids on youtube showing simple games displayed this way.
Post reply on HN