An Exhaustive Todo List

Here is a list of things that I want to learn and build(not necessarily over the next year).

• Learning about Executables and Linkers: My primary interest is in operating systems and low level software and thus executables and linkers are some of the most common pieces of software I have to interact with.

  • Writing a userspace exec: A userspace program that takes in an object file(*.o) and executes it.
  • A debugger for C executables: Understanding the ptrace system call in more detail. Maintaining an in-memory-stack for backtraces, parsing through debugging stubs etc (Optional) Using DAP so that editors like VSCode and Neovim can use their debugger frontends to interact with it

• Pet Compilers: Last year I wrote a couple of pet compilers, almost all of them are incomplete feature wise. Currently there is no support for some extremely common language features and does zero optimizations. Some improvements that I want to make :

  • Converting interpreter backend to a bytecode VM and support for JIT:

    Relatively simple, need to change the eval function currently implemented into a bytecode codegen and construct a stack based VM for evaluation. Create wrappers for basic IO and OS interfacing. Support for JIT compilation?(Unsure about this feature)

  • Implementing optimizations for the compilers:

    The lisp compiler currently doesn’t support tail-call elimination. Its relatively straightforward to implement since llvm supports tail call elimination. I have zero clue about compiler optimizations, and before implementing the rest,I need to read about them. A bunch of resources that I am thinking of reading and implementing prototypes (Reading list)

  • Type systems:

    Implementing Bidirectional type checking and Hindley Milner type inference. The LLVM compiler syntax is awfully close to JavaScript so implement bidirectional type checking for that(since llvm ir requires typing). A bit academic so have to read some papers and a lot of code for this (Reading list)

  • Classes, Inheritance and Lambdas:

    For the LLVM compiler. Relatively easier to implement compared to others in this list: add the vtable as the first member of structs(implicit). Support for functors and lambdas as well.

  • An async runtime:

    Unsure about the implementation as of now, but looks doable with a bit of thought. I might live to regret saying this, xkcd predicting the future: 1425

• Web Server from scratch(Non blocking, single thread variety): A TCP Server, event loop and implementing the relevant parts of the HTTP protocol. If I get some more time implementing websockets ono top of it. Primarily to familiarize myself with calling linux syscalls with Rust, particularly epoll. A middleware based API to setup routes (like Gin or Express)

• Functional programming: I spent a couple of months last year learning haskell and now I kind of have an idea about the functional programming jargon people talk about: like functors, monads and applicatives. Apply them to write a:

  • Monadic Parser Combinator: First in haskell and then maybe port it to Rust(Can use this instead of nom for Advent of Code)

• Databases:

  • Mini key value store: Implement a key value store based on the bitcask paper, something like avinash’s CaskDB. Eventually implement an sql layer on top of it: Lexing, Parsing, Storage(mapping sql entities to bytes) and Execution(running parsed AST on storage)

  • CMU Bustub assignments: Every year I plan to watch the CMU database lectures, this year is no different. But I really want to attempt solving the bustub assignments because they use idiomatic C++. The only C++ project that I wrote involved just slapping shared pointers on top of everything. This works for smaller projects, but the overall the code looks incredibly ugly. Also personally I think having a clear idea about your object lifetimes helps rewthe programmer to reason about the overall architecture and performance of the code. Hopefully by the end of 2024, I can finally understand the infamous Rule Of Five.

• Tensor library, Autograd Engine and a native backend: Approximately a month ago, I decided to read through Geohotz’s tinygrad. I had no clue what it did, but I knew that it was an extension on top of Karpathy’s Micrograd which was inspired by pytorch’s autograd engine. Tinygrad houses a tensor library and an autograd engine, but also houses multiple backends. Thus your neural networks can now run on any backend of your choice. The idea is to build something similar(maybe a DSL for neural networks?) with lesser features in a different language.

• Extending RiscV VM: Currently my RiscV virtual machine supports the RV32I instruction set. I need to implement the MAF instructions to support XV6 and extend it to 64 bit(:%s/u64/u32). Also need to add support for different privilege levels, CSR registers, Virtual Memory, UART, CLINT, PLIC and VirtIO.

• RiscV Softcore An extension of the VM project. Write it in bluespec and synthesize on an FPGA(most probably a PYNQ Z2). Reading the bluespec riscv book (Reading list) + toying around with Vivado(not a very fun exercise tbh).

Reading List

Non exhaustive as of know, will add more later. ^ Denotes currently reading.

Literature

• Fall by Camus : Listened to the audiobook during a harsh afternoon last semester, one of the books that I want to read once every year.
• Stranger by Camus : Haven’t read this, but reddit warns that no young person should read this and so obviously I want to read this a couple of times
• Crime and Punishment by FD : Reading Dostoevsky is not my cup of tea, but there is no book that has made me feel disgust and guilt like parts of this novel.
• Brothers Karmazov by FD : A book recommended by my philosophy professor as a must read. He said he would pay the money back if it didn’t change my view of the world.
• God of Small Things : I haven’t read a piece of Malayalam Literature in a long time. God of small things is a book that I read when I was very young(12-13 ish probably) and I remember having an excerpt as a part of my malayalam literature class.
• Old Man and the Sea: Had to read parts of this for my literature class, loved it and want to gorge on the whole thing.
• Randamoozham: I remember reading a critical character analysis of Mahabharat when I was in school. This book is the story of Kurukshetra but from the eyes of Bheema.

Computers

• RiscV processor in Bluespec
• Bitcask Paper and CaskDB
• ^ Tinygrad
• Cornell CS6120: Really good implementation assignments
• Green threads: Understanding how golang does userspace threads
• Insane Metaprogramming : This is one of the craziest things I have seen on the internet, want to learn scheme just for this.
• Engineering a compiler: Heavily recommended book to read after crafting interpreters
• Cwerg: A compiler heavily focussed on the backend , want to gorge through this to understand optimizations
• Bidirectional type checking: Cause typescript
• Hindley Milner: Cause haskell