8 ms·
My Most Important Project Was a Bytecode Interpreter
- Chanyow 10y agohello, you are right.
- sillysaurus3 10y agoAlso: 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?
- kovrik 10y agoYour own Lisp-like language (or Scheme implementation). Really recommend it.
- zeveb 10y agoSeconded. One of my plethora of hobby projects has been an interpreter or compiler (it changes from month to month) for Common Lisp, for an esoteric platform. It's a huge amount of fun, and I have learnt so much about software from it.
- zeta0134 10y agoI 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.
- voltagex_ 10y agoEvery 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 pixels, then moving on to more complex effects.
- chrisseaton 10y agoYou can write raw pixels to the screen with a HTML canvas and JS - no need to do it with low level code and making your own OS.
- corysama 10y agoI bet you could go from main() to displayBufferOnScreen(unsigned char *buffer) in a couple dozen lines of C using SDL.
- voltagex_ 10y agoThis is a good idea, as is the Javascript one above.
- vram22 10y agoOr with different desktop GUI toolkits for different languages: C++ w/Qt, C++ w/ wxWidgets, wxPython, Perl/Tk, Python +Tkinter, Delphi, Lazarus, or many other lang/toolkit combos. Even many BASICs have that ability built-in (from the early days of personal computers).
- nice_byte 10y agoYou could skip writing a bootable kernel, and try that with microcontrollers :) It's possible to hook up a tiny lcd screen to an arduino
- errozero 10y agoYou can even wire up an arduino into a vga monitor. There are a few vids on youtube showing simple games displayed this way.
- khedoros 10y agoAre 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 http://www.mcamafia.de/pdf/pdfref.htm
- signa11 10y agohaving 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. write the hot-spots in c++/c, and interface that with python. or go with lua all the way ? or maybe try a hybrid approach (which would allow you to see how embeddable the language really is) possibilities are endless, and as you so rightly said, gratification is instantaneous :)
- Marazan 10y agoSimply 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.
- signa11 10y ago> 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. thank you for your insight! this is very useful indeed.
- Marazan 10y ago
- voltagex_ 10y agoI've messed around with a DNS client and DNS server for the same reasons, but I don't think they quite meet the bar for a "power" project.
- spotman 10y agoA distributed database. Same category of probably not a great idea to use and claim is better than what's out there ( it won't be ) but boy howdy will it teach you about distributed systems and pitfalls that will absolutely help you when you are working on one at your day job.
- tptacek 10y agoStrong agree on emulator and particularly stack vm. Would add: TCP/IP stack.
- nialo 10y agomostly curiosity: why a stack vm in particular? (is it because you then need to write the compiler for it?)
- tptacek 10y agoBecause if you're familiar with conventional real register architectures, the stack VM forces you to rethink it, in a much simpler way. It's a useful simplifying abstraction.
- vram22 10y agoThere used to be a lot of interest in, and articles about, stack machines (real ones, not VMs) back in the days of mags like BYTE and PC Mag. Good reading.
- vram22 10y agoI once corresponded with someone who wrote his own working TCP/IP stack for his own home PC, an IBM PC Jr. See Mike's PCJr page near end of this post: http://jugad2.blogspot.in/2012/09/lissajous-hippo.html http://jugad2.blogspot.in/2012/09/lissajous-hippo.html
- vram22 10y agoUpdate: Visited his page again. He has now even created a web server for the PCJr and ran his site on it for a while.
- keithnz 10y agoYour own multi tasking OS. Very common to roll your own everything on embedded systems. Especially back in the early 80s/90s
- Jasper_ 10y agoTracks 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, move onto reverse engineering simple formats for e.g. games) * Understanding the difference between RAM and address spaces (e.g. understanding virtual memory, mmap, memory-mapped IO, dynamic linking, the VDSO, page faulting, shared memory) * Device drivers (easier on Linux, understanding userspace/kernel interaction, ioctls, how hardware and registers work, how to read spec sheets and hardware manuals) * Graphics (modern software rasterizer that's not scanline-based, understanding 3D and projective transforms, GPU programming and shaders, basic lighting (reflection and illumination) models, what "GPU memory" is, what scanout is, how full scenes are accumulated all along the stack) I could go heavily into depth for any one of these. Ask me questions if you're interested! They're all fun and I always have more to learn. Also, the longer you get into any given track, the more you realize they all connect in the end.
- kirang1989 10y agoThis is an awesome list. Thanks!
- Rexxar 10y agoConcerning last point, do you know nice example of non-scanline-based 2D renderers ?
- nadam 10y agoA very informative tutorial on high performance edge-function based rasterization: https://fgiesen.wordpress.com/2013/02/17/optimizing-sw-occlusion-culling-index/ 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.
- 10y ago
- skybrian 10y agoA web server. Use a subset of HTTP 1.0 and make the browser serve pages.
- skybrian 10y agoA simple search engine for a directory of documents. Create the index yourself.
- skybrian 10y agoA chat server. One chat room. Make sure you can handle fast and slow clients, and disconnects.
- fernly 10y agoOMG, memories... at once point in the pleistocene era, I was tasked with writing a manual for what was then Informix 4GL[1], and to get comfortable with the language, I spent a week writing a user forum app, with topics and message threads, messages stored as "blobs" in the SQL DB. Tried to get my co-workers in the pubs group to use it. They thought it was cute but all said hahaha no. [1] https://en.wikipedia.org/wiki/IBM_Informix-4GL https://en.wikipedia.org/wiki/IBM_Informix-4GL -- I am flabbergasted to see 4GL is still in use 30 years on.
- shermanyo 10y agoA basic game engine! I was exposed to so many concepts over time, building on a code base I understood from the ground up. It was the first time my code (c++ no less!) felt completely deterministic, that I understood every piece of data down to the byte level, heap/stack/gpu locality at any point of execution, and especially the lifecycle and memory management. If anyone is interested in creating an indie/hobby game engine, I'd recommend the following: - game loop with independent render FPS and a constant simulation tick delta (otherwise it runs non-deterministic due to floating point) - "entities, components, systems" architecture (ECS) - data-driven content (load level and game object data from JSON or similar, and programmatically build your scene) - basic event or messaging system Honestly, I can't think of a field that covers as wide a range of CS topics at the depth I've seen in lower level game development. If you focus on understanding and implementing the popular patterns and algorithms recommended by the indie community, its not the most daunting of projects. There's so much great information, and a few good books that break down and walk through a working implementation you can build on once you understand it from the ground up.
- pooktrain 10y agoThis seems like lots of fun - mind sharing the books that you alluded to?
- shermanyo 10y agoSure, the main book I had in mind is "SFML Game Development" https://www.packtpub.com/game-development/sfml-game-development https://www.packtpub.com/game-development/sfml-game-developm... SFML is a C++ library that handles window management, input, sound, etc... For reference, a friend and I went through the book chapter by chapter a couple years ago. He was new to programming, and I'd made a few simple games and read scattered info in the past. The book had a good pace and filled in a lot of the gaps I had. Another great book is "Game Engine Architecture" https://www.crcpress.com/Game-Engine-Architecture-Second-Edition/Gregory/p/book/9781466560017 https://www.crcpress.com/Game-Engine-Architecture-Second-Edi... This book is a lot deeper, but I found it a great reference. I probably spent more time reading this book and going back over my engine code to refactor based on what I learned (rather than use it as a direct example implementation. At that stage, there were a few good articles online that were focused on the ECS pattern. Here's a couple, but try to find something that matches your language, there's plenty of info out there. http://www.dataorienteddesign.com/dodmain/node5.html http://www.dataorienteddesign.com/dodmain/node5.html https://eliasdaler.wordpress.com/2015/08/10/using-lua-and-cpp-in-practice/ https://eliasdaler.wordpress.com/2015/08/10/using-lua-and-cp... https://github.com/junkdog/artemis-odb/wiki/Introduction-to-Entity-Systems https://github.com/junkdog/artemis-odb/wiki/Introduction-to-... Good luck and have fun!
- c-smile 10y agoHmm, 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 it - you need to persist UI state somehow, right? So it got integrated NoSQL database on board. That's pretty much how http://sciter.com http://sciter.com was born.
- zodiac 10y agoI think they meant rasterization as in http://www.scratchapixel.com/lessons/3d-basic-rendering/rasterization-practical-implementation http://www.scratchapixel.com/lessons/3d-basic-rendering/rast... instead of in the context of browsers...it's not a very precise term
- richdougherty 10y ago* 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 structures: futures/promises, queues, etc. * A simple roguelike game.
- mamcx 10y agoI 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).
- doozy 10y agoWhile 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.
- mamcx 10y agoThis area is one where it look more impenetrable. You find good info about compilers and even build "computers" from scratch but databases is black magic. Specially, because RDBMS look like are at all or nothing. I wonder if is possible to pick "only" the transactional/storage and made by myself the query/optimizer/api on top. I will be happy if is possible to build on top of something like sqlite, unfortunately, I don't know C at all (work with F#,C#, Delphi, Python). In the other hand, know the basic steps could be good enough...
- 10y ago
- bonoboTP 10y ago* Implementing Internet protocols (TCP, IP, SMTP etc) * Floating point manipulation and numerical computation * Rolling some own crypto (strictly for fun use)
- loup-vaillant 10y agoActually, 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 API is flexible or complex. And of course good old exploitable bugs.
- bonoboTP 10y agoNo. 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.
- loup-vaillant 10y agoDogma, 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.
- usrusr 10y agoReading from a raw filesystem dump was both interesting and rewarding as it works on a problem domain that exists in reality, not just on some simplified playground. If you target something as primitive as FAT, the challenge isn't terribly high.
- titzer 10y agoA virtual memory system for a kernel.
- 0xcde4c3db 10y agoA screen-oriented text editor with undo and search/replace. Can you make it handle a 10MB file without "simple" operations having annoying delays? How about 100MB? 1GB? 100GB? With no line breaks in the file?
- mynewtb 10y agoIs there any such editor?
- criddell 10y agoI don't think so. Can a text editor do search and replace on a 100 GB file without a delay? You could construct an index, but that's not going to happen instantaneously either.
- 0xcde4c3db 10y ago> Can a text editor do search and replace on a 100 GB file without a delay? I meant that things like simply scrolling through a few pages or inserting/deleting a single character in the middle of the file shouldn't cause noticeable delays. Doing an operation that spans the entire file is different.
- hawski 10y agoWith both emacs and vim you can certainly edit 500MB file. I concatenated all sources of recent Linux kernel 4.6.3 once. From what I remember it was all .c, .h and .S files. Resulting file has 542MB and 19'726'498 lines. I did it to test the text editor I am working on. Some stats: $ time vim -c 'edit kernel-total' -c q real 0m8.162s user 0m7.687s sys 0m0.398s $ vim kernel-total ^Z $ ps aux | awk "/kernel-total$/ || NR == 1" USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND hawski 10467 2.7 17.1 805120 670988 pts/2 T 17:41 0:07 vim kernel-total $ time emacs kernel-total -f kill-emacs real 0m7.155s user 0m6.869s sys 0m0.237s $ emacs kernel-total ^Z $ ps aux | awk "/kernel-total$/ || NR == 1" USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND hawski 10825 43.8 14.8 857484 581152 pts/2 T 17:47 0:07 emacs kernel-total With vim editing is quite smooth and with emacs it feels laggy. I only edited a bit, like entering a new line here and there, moving few pages down, going to the end of the file and to the top again. Saving is sluggish.
- Johnny_Brahms 10y agoBy far the project that teaches me the most was writing an inliner for a toy language we developed as a part of a course at uni. Most people don't really realise that the more complex an inliner gets, the more similarities it gets to a rabid animal you can just barely restrain on a leash. My prof said he had laughed at my "how hard can it be?"-attitude . I worked my ass off and ended up being asked whether he could use the inliner in a language often mentioned on HN today :) The inliner was superseded by a much better one in 2003 written by a much smarter person than I, though.
- Johnny_Brahms 10y agoBy far the project that teaches me the most was writing an inliner for a toy language we developed as a part of a course at uni. Most people don't really realise that the more complex an inliner gets, the more similarities it gets to a rabid animal you can just barely restrain on a leash. My prof said he had laughed at my "how hard can it be?"-attitude . I worked my ass off and ended up being asked whether he could use the inliner in a language often mentioned on HN today :) The inliner was superseded by a much better one in 2003 written by a much smarter person than I, though.
- prirun 10y agoAn emulator for a real chip, like a 68000. I wrote one for a Prime minicomputer (Prime died in the early 90's). Telnet to em.prirun.com on port 8001 to try it out! The advantage of emulating a real system/chip is that if you can find old software for it, you avoid the step of having to invent your own programs: real, running programs already exist.
- gopalv 10y agoThe 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 about the JVM, contributing to Perl6/Parrot and then moving onto working on the PHP bytecode with APC, my career went down a particular funnel (still with the JVM now, but a logical level above it). Building interpreters makes you an under-techtitect, if that's a word. It creates systems from the inner loop outwards rather than leaving the innards of the system for someone else to build - it produces a sort of double-vision between the details and the actual goals of the user. [1] - "Design of the Portable.net interpreter"
- _RPM 10y agoInteresting. 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 implemented those in my system yet, and also have no idea how Python or PHP does it. Is PHP's VM a stack based one? I do read the Zend/ directory of PHP's source, but it is really hard to follow and there is virtually no documentation on the VM
- wahern 10y agoYou 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 < x.nlabel; i++) { for (j = 0; j < x.label[i].nfrom; j++) { patch_in_offset(x.label[i].from[j], x.label[i].offset) } } 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.
- briansteffens 10y agoNice post! I really enjoy playing around with things like this. It's amazing how little is needed to make a language/interpreter capable of doing virtually anything, even if not elegantly or safely. As long as you can perform calculations, jump around, and implement some kind of stack your language can do just about anything. I recently threw something together sort of like this, just for fun (I like your interpreter's name better though): https://github.com/briansteffens/bemu https://github.com/briansteffens/bemu It's crazy how much these little projects can clarify your understanding of concepts that seem more complicated or magical than they really are.
- curtfoo 10y agoYes I wrote a parser/compiler and interpreter for a custom domain specific language and it had a similar effect on my career. Lots of fun! Okay I guess technically I used a parser generator that I then modified to build an AST and convert it into assembly-like code that fed the interpreter.
- tominous 10y agoI love the author's meta-idea of refusing to accept that unfamiliar things are black boxes full of magic that can't be touched. A great example of this mindset is the guy who bought a mainframe. [1] Refuse to be placed in a silo. Work your way up and down the stack and you'll be much better placed to solve problems and learn from the patterns that repeat at all levels. [1] https://news.ycombinator.com/item?id=11376711 https://news.ycombinator.com/item?id=11376711
- stephengillie 10y agoEverything is made from smaller components. Understand each of those components better and you'll understand the entire system better. Sometimes, you can use end-errors to tell which component has the issue. For instance, if a web site gives a 502 error, the problem is likely with the load balancer or lower network stack on the web server. 404 would often be a file system level issue on the web server. 500 is frequently a network issue between web server and database server. 400 is a problem with the site presentation code, or maybe database malforming addresses.
- dspillett 10y ago> Everything is made from smaller components. Understand each of those components better and you'll understand the entire system better. This. No matter how specialised you are (or want to be) always strive to have at least a basic understanding of the full stack and everything else that your work touches through a couple of levels of indirection (including the wetware such as, in commercial contexts, having a good understanding of your client's business even if you aren't even close to being client-facing) because it will help you produce much more useful/optimal output and can be a lot more helpful when your colleagues/compatriots/partners/what-ever his a technical problem. Heck, at the logical extreme a little cross discipline understanding could even lead you to discovering a better method of doing X that strips out the need for Y altogether, revolutionising how we do Z. Of course don't go overboard unless you are truly a genius... Trying to keep up with everything in detail is a sure-fire route to mental burn-out!
- dpratt 10y agoI'd add a driver for a non trivial binary protocol - I ended up implementing a JVM driver for Cassandra a few years ago, and it was a blast.
- voltagex_ 10y agoWorking with data as binary is a good test of a high level language skills. When I was playing around with DNS, I wrote terrible code like https://github.com/voltagex/junkcode/blob/master/CSharp/DNS/BaxterWorks.DNS.Parsers/Query.cs https://github.com/voltagex/junkcode/blob/master/CSharp/DNS/.... A better way to do it is https://github.com/kapetan/dns/blob/master/DNS/Protocol/Header.cs https://github.com/kapetan/dns/blob/master/DNS/Protocol/Head... - structs, of course. I'd add reading and implementing a protocol from RFC - it's a great way to start thinking about design, especially if you read the original RFCs and work forward through the revisions and see what was kept vs deprecated.
- robertelder 10y agoOne 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 that will process the actual programs that you write. But, if your regexes get complex, you should really write a parser to parse the regexes that will parse the actual program. This is where you realize that it's parsers all the way down. 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.
- chrisseaton 10y agoI don't get it - what do regexps have to do with compilers and how do they make compilers faster?
- ender7 10y agoThe 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.
- duaneb 10y agoA lot of optimizations on arbitrary byte code often look for patterns in byte streams (or in reified assembly) in similar ways to regexes.
- teraflop 10y agoFor many years, an important stage of the GHC Haskell compiler consisted of a giant Perl script full of regexes. http://code.haskell.org/ghc-scp/ghc/docs/comm/the-beast/mangler.html http://code.haskell.org/ghc-scp/ghc/docs/comm/the-beast/mang...
- rosstex 10y agoIn this same vein, I recommend coding an emulator! It can be an excellent experience. http://www.multigesture.net/articles/how-to-write-an-emulator-chip-8-interpreter/ http://www.multigesture.net/articles/how-to-write-an-emulato...
- anaccountwow 10y agoThis is a required hw assignment for a freshmen class @ cmu. https://www.cs.cmu.edu/~fp/courses/15122-s11/lectures/23-c0vm.pdf https://www.cs.cmu.edu/~fp/courses/15122-s11/lectures/23-c0v... Given it has some parts already written in the interest of time...
- _RPM 10y agoI am jealous of those students. I would love to take that class.
- Arcten 10y agoWhat'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.
- wahern 10y agoTwo 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). A DSL or VM doesn't need to be complex; it could be incredibly simple but still be immensely more powerful than coding a solution directly in an existing language using its constructs and APIs. Case in point: the BSD hexdump(1) utility. POSIX defines the od(1) utility for formatting binary data as text, and it takes a long list of complex command-line arguments. The hexdump utility, by contrast, uses a simple DSL to specify how to format output. hexdump can implement almost every conceivable output format of od and then some using its DSL. The DSL is basically printf format specifiers combined with looping declarations. I got bored one day and decided to implement hexdump as a library (i.e. "one hexdump to rule them all"), with a thin command-line wrapper that emulates the BSD utility version. Unlike BSD hexdump(1) or POSIX od(1), which implement everything in C in the typical manner, I decided to translate the hexdump DSL into bytecode for a simple virtual machine. http://25thandclement.com/~william/projects/hexdump.c.html The end result was that my implementation was about the same size as either of those, but 1) could built as a shared library, command-line utility, or Lua module, 2) is more performant (formats almost 30% faster for the common outputs, thanks to a couple of obvious, easy, single-line optimizations the approach opened up) than either of the others, and 3) is arguably easier to read and hack on. Granted, my little hexdump utility doesn't have much value. I still tend to rewrite a simple dumper in a couple dozen lines of code for different projects (I'm big on avoiding dependencies), and not many other people use it. But I really liked the experience and the end result. I've used simple DSLs, VMs, and especially explicit state machines many times before and after, but this one was one of the largest and most satisfying. The only more complex VM I've written was for an asynchronous I/O SPF C library, but that one is more difficult to explain and justify, though I will if pressed.
- linkregister 10y agoYes, 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.
- loeg 10y agoI like implementing emulators, because the toolchain and architecture specification are all there already. You get to implement what is basically a little embedded CPU.
- _RPM 10y agoI saw the matrix after I first implemented a virtual machine. I recommend everyone does it because it will teach you a lot about how code is executed and transformed from the syntax to the actual assembly/bytecode. A stack based virtual machine is so simple it takes a lot of thinking to understand how they work. (or maybe I'm just not that smart). It's interesting that he implemented function calls via a jump. In my VM a function is just mapped to a name (variable), so functions are first class. When the VM gets to a CALL instruction, it loads the bytecode from the hash table (via a lookup of the name). Since this is a procedural language where statements can be executed outside of a function, implementing the functions as a jump would be difficult because there would need to be multiple jumps between the function definition and statements that aren't in a function. I really wish my CS program had a compilers class, but unfortunately they don't, so I had to learn everything on my own.
- chii 10y agoA CS education is incomplete without a semester on writing a simple compiler, and a corresponding emulator for the output for said compiler.
- philippeback 10y agoSoulmate of yours here: https://clementbera.wordpress.com https://clementbera.wordpress.com Lots of optimizations going on for OpenVM. https://github.com/OpenSmalltalk/opensmalltalk-vm https://github.com/OpenSmalltalk/opensmalltalk-vm Interesting bit: VM is written in Slang and transformed into C then compiled. So you can livecode your VM. In the VM simulator.
- philippeback 10y agoParsers made easy and pretty much interactive: http://www.lukas-renggli.ch/blog/petitparser-1 http://www.lukas-renggli.ch/blog/petitparser-1 http://www.themoosebook.org/book/internals/petit-parser http://www.themoosebook.org/book/internals/petit-parser This include the dynamic generation of blocks and arrows style things...
- foobarge 10y agoI've done something similar 21 years ago: a C interpreter targeting a virtual machine. The runtime had a dynamic equivalent of libffi to call into native code and use existing native libraries. I added extensions to run code blocks in threads so that the dinning philosopher problem solution was very elegant. Back in the days, not having libffi meant generating assembly on the fly for Sparc, MIPS, PA-Risc, i386. Fun times. That C interpreter was used to extend a CAD package.
- reacweb 10y agoBill gates also started with an interpreter (basic interpreter). Many parts of early windows applications were developed in p-code and visual basic is an important part of Microsoft success.
- reidrac 10y agoI wrote a VM for the 6502 for fun and it was one of most interesting and satisfying projects I've ever made in my free time. It is very close to a bytecode interpreter, only that it comes with a specification that is actually the opcode list for the MOS 6502 (and few details you need to take into account when implementing that CPU). Besides there are cross-compilers that allows you to generate 6502 code from C for your specific VM (see cc65).
- elcct 10y agoI did something similar in the distant past, that is I wrote subset of C compiler (functions, standard types, pointers) to imaginary assembler and then bytecode interpreter. It was awesome fun, but also I got so into it my - then - girlfriend started to question my commitment to the relationship. So be careful, this is really interesting thing to do :)
- memsom 10y agoI did this in C#. It was a lunch time project at work a couple of years ago. It was fun. I still want to do a V2 and remove all of the shortcuts I put in because I didn't want to write code for the stack and stuff like that. At the end of the day, my solution was spookily similar to this - the 32bit instructions - well, yeah, I was the same! It was just simpler. I did have a few general purpose registers (V1, V2 and V3 I think) and I did have routines to handle bytes, words and such like. So stuff like this (as a random example I pulled from the source): ORG START START: ST_B 10 LOOP: ST_B 10 ADD_B ;;value will go back on stack LD_B V1 SM_B V1 ;;value we use next loop SM_B V1 ;;value we compare SM_B V1 ;;value we echo to console TRP 21 ;;writes to the console ST_S '',13,10,$ TRP 21 ;;writes to the console CMP_B 50 ;;compares stack to the constant JNE LOOP ST_S 'The End',13,10,$ TRP 21 ;;writes to the console END
- pka 10y agoI'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 http://www.stephendiehl.com/llvm
- TazeTSchnitzel 10y ago> 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.
- oops 10y agoNice read! Reminds me of nand2tetris that was posted not too long ago https://news.ycombinator.com/item?id=12333508 https://news.ycombinator.com/item?id=12333508 (You basically implement every layer starting with the CPU and finishing with a working Tetris game)
- douche 10y agoThis reminds me a little bit of my computer architecture class. We started at logic gates in a simulator[1], and worked our way up from there to flip-flops and adders, memory chips, a simple ALU, and eventually a whole 8-bit CPU in the simulator. I want to think that we were even writing assembly for it, loading the programs into the simulated memory, and executing it. It was a great way to get a sense of how everything works, and I think it's when C-style pointers really clicked for me. [1] this one, IIRC https://sourceforge.net/projects/circuit/ https://sourceforge.net/projects/circuit/