Type checkers can be very enlightening. Somewhere on my hard drive an implementation of all corners of the lambda cube lurks. At some point I’ll write about this.
I also happen to like interpreters/compilers. I’d argue that writing a compiler is a much better experience than a interpreter since you learn a lot more about manipulating code as data and data as code.
Also I’m not sure if it’s what you’re looking for, but I’ve learned a ton through blogging. Way more than any single project. Shameless link to my blog
In the readme I state that the project is basically abandoned due to memory limitations on the AVR chip I was using, but I’ve got a branch where it’s running happily on ARM, though the keyboard-specific parts still have a way to go.
On a Teensy 2 the interpreter runs and accepts input; I can load about 10-20 lines of code into it before I run out of RAM. Enough for a proof-of-concept or toy but not much more. This is with a lot of care taken to do as little as possible in a self-hosted manner, which is contrary to the traditions of Forth. (Functions implemented in C are stored in flash and aren’t subject to the same harsh memory constraints.)
I bet a seasoned Forth pro could make it work within 2.5kb, but I wimped out and upgraded to a board with 16kb.
Besides simple Lisp-ish interpreters, I like doing a markov chain-based text generator to feel out languages – it can be pretty tightly scoped (maybe a page of code), but usually involves both file IO and graph data structures.
So I should preface this by saying that I’m very much an amateur and self-taught. These definitely put the toy in toy implementation:
btree: A kind-of, sort-of drop-in replacement for tree in shell. (Twice actually: once taking advantage of bashisms and once using POSIX shell syntax only.)
toy-core: Minimal C implementation of a few basic utilities (cat, tail, head, and echo). I wanted to understand ring buffers better, so I was mostly interested in tail, but the whole thing was useful for practicing C.
llisp: This was inspired by reading Mary Rose Cook’s Little Lisp interpreter. I started a mini-Lisp in Lua. I lost steam after getting the most basic functionality, but would like to go back to it someday.
A mandelbrot fractal view. Exercises math and recursion, plus actually displaying or emitting graphics.
A parser for a simple language. Exercises recursion or function call overhead, and puts you up against a language and library’s ability to deal with character and string data, and its ability to allocate memory.
Taking something by a master and not reading their code until after a whack at the problem myself. http://norvig.com/ is a good source. Another was Thompson’s regex search paper – I did read it first, but the IBM 709 code was obscure enough to avoid spoilers. I’ve put this one up as a kind of problem set: https://github.com/darius/regexercise
If it’s a problem you’re interested in, you can’t really lose: you either get schooled or you find a wrinkle that your chosen master didn’t.
I worked through Little Schemer like this. I would cover their answers and try on my own, then check, compare etc. It was a great experience: humbling in a good way.
Another book this works well for is K&R on C. There are tons of solutions to their exercises on Github, Bitbucket and personal websites. Try to solve first, then read around. Problem there, of course, is that the solutions are off very varied quality, and you don’t know in advance which are good, great, meh, terrible. Of course, you can think of that as training for reading real code: You never know what you’ll get.
The book, Paradigms of AI Programming, starts with an implementation of most of cool early ideas in AI (Eliza, Goal Directed Solvers, symbolic math, game solving). What makes these learning projects is the clarity of the descriptions of how to solve these problems. Although the book is all about Lisp, I found it a really great programming book in general and I’ve learnt from implementing them in Clojure / Haskell.
As far as “tooting my own horn” goes, I wrote a readable emulator for the MOS 6502 in Common Lisp. My original goals included writing a full NES emulator on top of it, then tools for the reverse engineering, observation, and runtime modification of Nintendo ROMs. Probably including a compiler for a lisp-like language targeting the emulator.
I got a new job I find much more challenging though, so this isn’t likely to happen ‘til I retire. :P For a decent NES emulator, sprocketnes is actually quite clear even without knowing Rust.
Interesting projects I’ve been meaning to read include the following:
goya, a browser-based Pixel Art editor in 1000 lines of Clojurescript/Om
snabbswitch, a readable userspace networking stack in LuaJIT
xv6, a modern reimplementation of Sixth Edition Unix in ANSI C used in courses at MIT
jonesforth, duh, of course, I’m sure you’re aware, etc.
I don’t have a fixed set, it depends on what else I’m interested in at the time. Right now I’m making a strong push to learn Common Lisp, so I’m implementing graph algorithms from a book I’m reading, and using it for other small projects that come up. Been using it to query our mongodb, for example.
One thing I have done a few times is a utility to download and install the latest development build of Chromium. I have it in c, c++, Python, Go, ocaml, and I think a couple others.
The Matasano crypto challenges got some good press, and seem nicely structured (I stalled after the first set: we had our first baby). Now online: http://cryptopals.com/
I don’t subscribe to the idea that you should reimplement known ground in a new language. In fact, I get bored quickly if I try to implement something twice. This is just my personal way of doing things, I love people having their pet idea that they iterate and iterate over and over again in different languages.
So, I come up with new things that I try out and drop along the way when I’m losing interest. I am currently learning Rust and my collection of attempts can be found here. (possibly currently very broken, due to the development speed of Rust)
Type checkers can be very enlightening. Somewhere on my hard drive an implementation of all corners of the lambda cube lurks. At some point I’ll write about this.
I also happen to like interpreters/compilers. I’d argue that writing a compiler is a much better experience than a interpreter since you learn a lot more about manipulating code as data and data as code.
Also I’m not sure if it’s what you’re looking for, but I’ve learned a ton through blogging. Way more than any single project. Shameless link to my blog
Eagerly awaiting the type checker posts. Love your blog.
Thanks :) I’ll be sure to post it here when I write it up :)
I wrote a Forth implementation for microcontrollers, and then wrote a keyboard firmware in that Forth.
Turns out that’s a pretty good way to teach yourself C!
https://github.com/technomancy/orestes
This is awesome!
(“the ultimate yak shave” ha!)
Thanks!
In the readme I state that the project is basically abandoned due to memory limitations on the AVR chip I was using, but I’ve got a branch where it’s running happily on ARM, though the keyboard-specific parts still have a way to go.
Curious: how close did you come to getting your Forth to run within the memory constraints you have?
On a Teensy 2 the interpreter runs and accepts input; I can load about 10-20 lines of code into it before I run out of RAM. Enough for a proof-of-concept or toy but not much more. This is with a lot of care taken to do as little as possible in a self-hosted manner, which is contrary to the traditions of Forth. (Functions implemented in C are stored in flash and aren’t subject to the same harsh memory constraints.)
I bet a seasoned Forth pro could make it work within 2.5kb, but I wimped out and upgraded to a board with 16kb.
Great question!
Great ideas! Thanks!
Pretty pictures! Because pretty pictures!
You’re a coder of Magellan?! Huge thumbs up, one of our all time favourites at CMUCC. :)
Oh no, none of these are mine. My knockoffs are these are much less impressive! :d
Besides simple Lisp-ish interpreters, I like doing a markov chain-based text generator to feel out languages – it can be pretty tightly scoped (maybe a page of code), but usually involves both file IO and graph data structures.
Not an implementation, but I used it to generate this scrambled version of the GPL.
So I should preface this by saying that I’m very much an amateur and self-taught. These definitely put the toy in toy implementation:
btree: A kind-of, sort-of drop-in replacement fortreein shell. (Twice actually: once taking advantage of bashisms and once using POSIX shell syntax only.)cat,tail,head, andecho). I wanted to understand ring buffers better, so I was mostly interested intail, but the whole thing was useful for practicing C.A mandelbrot fractal view. Exercises math and recursion, plus actually displaying or emitting graphics.
A parser for a simple language. Exercises recursion or function call overhead, and puts you up against a language and library’s ability to deal with character and string data, and its ability to allocate memory.
Taking something by a master and not reading their code until after a whack at the problem myself. http://norvig.com/ is a good source. Another was Thompson’s regex search paper – I did read it first, but the IBM 709 code was obscure enough to avoid spoilers. I’ve put this one up as a kind of problem set: https://github.com/darius/regexercise
If it’s a problem you’re interested in, you can’t really lose: you either get schooled or you find a wrinkle that your chosen master didn’t.
I worked through Little Schemer like this. I would cover their answers and try on my own, then check, compare etc. It was a great experience: humbling in a good way.
Another book this works well for is K&R on C. There are tons of solutions to their exercises on Github, Bitbucket and personal websites. Try to solve first, then read around. Problem there, of course, is that the solutions are off very varied quality, and you don’t know in advance which are good, great, meh, terrible. Of course, you can think of that as training for reading real code: You never know what you’ll get.
There’s an old book, The C Answer Book, for just this. (I haven’t read it.)
Links to your own toy implementations appreciated, too! Toot your own horn! :)
Some of these are a bit too involved to call toys, though.
The book, Paradigms of AI Programming, starts with an implementation of most of cool early ideas in AI (Eliza, Goal Directed Solvers, symbolic math, game solving). What makes these learning projects is the clarity of the descriptions of how to solve these problems. Although the book is all about Lisp, I found it a really great programming book in general and I’ve learnt from implementing them in Clojure / Haskell.
As far as “tooting my own horn” goes, I wrote a readable emulator for the MOS 6502 in Common Lisp. My original goals included writing a full NES emulator on top of it, then tools for the reverse engineering, observation, and runtime modification of Nintendo ROMs. Probably including a compiler for a lisp-like language targeting the emulator.
I got a new job I find much more challenging though, so this isn’t likely to happen ‘til I retire. :P For a decent NES emulator, sprocketnes is actually quite clear even without knowing Rust.
Interesting projects I’ve been meaning to read include the following:
I like http://www.windley.com/archives/2007/03/applied_web_heresies_etech_2007.shtml as a toy/learning project.
I don’t have a fixed set, it depends on what else I’m interested in at the time. Right now I’m making a strong push to learn Common Lisp, so I’m implementing graph algorithms from a book I’m reading, and using it for other small projects that come up. Been using it to query our mongodb, for example.
One thing I have done a few times is a utility to download and install the latest development build of Chromium. I have it in c, c++, Python, Go, ocaml, and I think a couple others.
The Matasano crypto challenges got some good press, and seem nicely structured (I stalled after the first set: we had our first baby). Now online: http://cryptopals.com/
I don’t subscribe to the idea that you should reimplement known ground in a new language. In fact, I get bored quickly if I try to implement something twice. This is just my personal way of doing things, I love people having their pet idea that they iterate and iterate over and over again in different languages.
So, I come up with new things that I try out and drop along the way when I’m losing interest. I am currently learning Rust and my collection of attempts can be found here. (possibly currently very broken, due to the development speed of Rust)
https://github.com/search?utf8=%E2%9C%93&q=user%3Askade&type=Repositories&ref=advsearch&l=Rust
This one has some good ideas -> http://blog.fogus.me/2009/05/29/pet-projects/