This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Computer Science / Programming Resource Guide

General Topics

Game Development

See also the general topics below: especially computer graphics, data structures, and algorithms.

• Game Programming Patterns (free book on some design patterns possibly useful in games)

• Invent Your Own Computer Games with Python, Making Games with Python & Pygame (free books)

• Entity Component Systems

  • A simple high-level explanation
  • Evolve Your Hierarchy (one of the earlier mainstream ECS papers)

• Fix Your Timestep! (or, how to do timesteps right. Read it.)

• Game Networking

• Red Blob Games (good visual resource on algorithms like A*, hexagonal grids, etc.)

• Catmull-Rom splines (splines that pass through all control points; good for games)

• Game AI

  • Behavior Trees
  • Boids (flocking behavior)

• Collision / Physics

  • 2D collision detection (especially Separating Axis Theorem, aka SAT)
  • Integration Basics
  • Real-Time Collision Detection (commercial book; basically the definitive resource on collision)

Computer Graphics

• Graphics Pipeline (overview of how computer graphics works)

• Metaballs

  • Metaballs and WebGL
  • Metaballs and Marching Squares

• What Every Coder Should Know About Gamma

• Constructive Solid Geometry (CSG -- boolean operations on meshes)

• Fast Inverse Square Root (famous algorithm for calculating 1 / sqrt(x), used heavily for vector normalization (originally for lighting in Quake III Arena))

• How OpenGL works: software rendering in 500 lines of code (lessons on creating a software rasterizer)

• Sutherland-Hodgman algorithm for polygon clipping

• Clip Space Approach – Extracting the Planes (frustum culling in clip space)

• Inigo Quilez' blog

• Signed Distance Fields

  • Modeling with Distance Functions (and the ShaderToy example/code)
  • nvscene 2008 - Rendering Worlds With Two Triangles
  • Volumetric Rendering: Signed Distance Functions
  • Ray Marching and Signed Distance Functions

• Rasterization

  • Rasterization: a Practical Implementation
  • Triangle rasterization in practice

Programming Language Theory and Compilers/Interpreters

• The Programming Languages Zoo

• (How to Write a (Lisp) Interpreter (in Python)) (follow-up: (An ((Even Better) Lisp) Interpreter (in Python)))

• Build Your Own Lisp

• The Implementation of Functional Programming Languages

• Hindley-Milner explanation

• Modern Compiler Implementation in ML (commercial book; variants in C and Java are available, but aren't as good)

• Compilers: Principles, Techniques, and Tools (aka The Dragon Book)

• Compiling with Continuations

• Write You A Haskell (currently unfinished)

• Official LLVM Tutorial (implements a compiler for a tiny toy language called Kaleidoscope); Haskell and OCaml versions also available.

• Control Flow Graphs/Analysis

• Data Flow Graphs/Analysis

• Pointer Tagging (storing information in unused bits of pointers)

• NaN boxing (using bits of IEEE 754 floats for tagging, similar to pointer tagging)

• Turbofan wiki (contains technical design docs of V8's new TurboFan compiler)

• Continuations

  • Continuation-Passing Style (aka CPS)
  • Exceptional Continuations in JavaScript (pdf; implementing continuations/call-cc in JavaScript using transpilation and exceptions)
  • What’s in a Continuation (and related project unwinder)
  • How to compile with continuations (CPS transforms)

• Intermediate Representations

  • Three Address Code
  • Static Single Assignment (aka SSA; registers are only assigned once, makes analyses such as CFG/DFA generation easier)
  • FIRM (graph-based IR; related paper)

• Optimization

  • Constant Folding (basic optimization by statically evaluating constants)
  • Automatic Vectorization (automatically convert scalar code to vectorized (SIMD) code)
  • Deforestation
  • Dead Code Elimination (via control flow analysis)

• Talks

  • Growing A Language (by Guy Steele Jr. of Scheme fame, on the challenges of designing languages that can scale)

Decompilation

• Reverse Compilation Techniques (Cristina Cifuentes' rather in-depth thesis on decompilation)
• decomp

Parsing

• Chomsky Hierarchy (hierarchy of types of grammars)
• Pratt parsers (Recursive Descent + Top Down operator precedence parsing = Pratt parsers)
• PEG grammars, Packrat parsers
• The Packrat Parsing and Parsing Expression Grammars Page (collection of resources on PEGs and Packrat parsers)
• Top-Down operator precedence parsing
• Earley parsers (can parse any context-free grammar)
• Shunting-yard algorithm (Dijkstra's algorithm for easy infix expression parsing (infix to tree/prefix/postfix))
• Reverse Polish Notation (aka postfix notation)
• Monadic Parsing in Haskell (parsing with monadic combinators)
• Sexy Lexing with Python

Algorithms

• Introduction to Algorithms (also known as CLRS, a famous algorithms book)
• Big O in Plain English
• Boyer–Moore–Horspool algorithm (fast substring search; the related Boyer-Moore is used notably in grep -- see why GNU grep is fast)
• Burrows–Wheeler transform (decreases entropy in data reversibly, used notably in bzip2)
• Huffman coding (tree for generating optimal prefix codes, used a lot in compression)
• Bucket Sort, Tree Sort, Radix Sort
• Pathfinding / Graph Searching
  • Dijkstra's Algorithm (general shortest-path pathfinding / graph traversal)
  • A* (Dijkstra's algorithm with heuristics, very commonly used)
  • D* Lite
  • Jump Point Search
  • Understanding Goal-Based Vector Field Pathfinding (fast pathfinding using vector fields for large numbers of entities)
• Topological sorting (for ordering nodes in a graph based on dependents)
• Neural Networks and Deep Learning (free book)
• Creating A Genetic Algorithm For Beginners
• Shor's algorithm (quantum computer algorithm for integer factorization in polynomial time)
• Bit Twiddling Hacks (little black book of hacks using bitwise ops)

Data Structures

• Bloom Filter

• van Laarhoven lenses (see the Haskell section on lens)

• Purely Functional Data Structures (commercial book; extended from freely available thesis)

• Free Monads

  • Purify Code Using Free Monads
  • You Could Have Invented Free Monads

• Spatial partitioning

  • Quadtrees (2D), Octrees (3D)
  • Bounding Volume Hierarchies
  • Binary Space Partitioning (BSP)

• Tries

• Interval trees / Segment trees

• Blockchain 101 (a good video tutorial and demonstration of blockchains)

• Distributed Hash Table (self-explanatory; notably used in BitTorrent)

• XOR linked list (more space-efficient doubly linked list implementation by XORing the previous and next pointers)

• Memory Allocation

  • Free Lists
  • Buddy memory allocation
  • Dynamic Memory Allocation: Advanced Concepts (slides; includes Segregated Free Lists)
  • Reference Counting (a simple form of garbage collection)

Regular Expressions (Regex)

• Regular-Expressions.info (tutorial and reference)
• refiddle, regex101, regexpal (online regex testers)
• Implementing Regular Expressions
  • Regular Expression Matching Can Be Simple And Fast in particular is well worth a read
• Matching regular expressions with derivatives
• The true power of regular expressions (on non-regular regular expression matchers, e.g. PCRE)

IEEE 754 Floating Point

• What Every Computer Scientist Should Know About Floating-Point Arithmetic HTML reprint / PDF
• http://0.30000000000000004.com
• http://floating-point-gui.de
• Unit in Last Place (measure of floating point precision)

Cryptography

• Lifetimes of cryptographic hash functions
• Public-key cryptography
• Diffie–Hellman key exchange (method of secure public key exchange)
• Elliptic curve cryptography

Common Ciphers

• Caesar cipher (alphabet rotation by a key; ROT-13 is a special case)
• Vigenère cipher
• XOR cipher (XORing plaintext with a key)

Emulation

• How To Write a Computer Emulator (older Emulation FAQ)
• GameBoy Emulation in JavaScript (a tutorial)
• Statically Recompiling NES Games into Native Executables with LLVM and Go (an attempt at statically recompiling NES binaries)
• Accuracy takes power: one man’s 3GHz quest to build a perfect SNES emulator (why emulators require fast computers)

Interesting Operating Systems

• NixOS (see also Nix, its more portable package manager) -- an OS built around Nix, a referentially transparent package manager. Allows you to build an entire OS setup around a single config file, with multiple profiles and no package dependency hell.
• MenuetOS (a fairly modern OS written in x86_64 assembly)
• MINIX (a popular teaching OS)

Computer Architectures

General Concepts

• Harvard architecture, Modified Harvard architecture
• Stack machines (useful in programming language VMs or concatenative languages)
• Register machines
• Delay slots
• Branch Prediction

Lisp Machines

Pong Story

x86 / x86_64

• x86 Assembly Wikibook
• x86 Instruction Set Reference
• [xchg rax,rax] -- interesting/clever x86_64 snippets
• x86_64 AMD Programmer's Manual (Volume 2, System Programming)
• x86_64 AMD Programmer's Manual (Volume 3, Instruction Reference)
• x86_64 System V ABI
• x86_64 ELF File Format

MIPS

• SPIM (MIPS simulator; unfortunately no macros/pseudo-instructions)
• MARS (another MIPS simulator, more featureful but requires Java)

Language Specific

General / Multi-Language

• Learn X in Y Minutes (short intros/walkthroughs of languages via demonstration code with comments)

Python

• Automate the Boring Stuff with Python (free book)
• Documentation
  • GUIs
    • Qt
      • PyQt (note that the free version is licensed under the GPL, act accordingly)
      • PySide (LGPL but currently Qt 4 only)
      • Tutorials: PyQt4, PyQt5, PySide
    • Tkinter
      • Tkinter tutorial
      • Graphical User Interfaces with Tk

JavaScript

• Eloquent Javascript (free book)

• You Don't Know JS (series of free books)

• You Might Not Need jQuery (jQuery -> Vanilla JS)

• this

• Fetch API

• Typed Arrays for manipulating binary data / compact native arrays

• Web Storage, IndexedDB -- offline in-browser databases

• TextEncoder/TextDecoder APIs for text codecs

• asm.js (a subset of JavaScript (statically type inferrable, no GC) targetted at efficient machine translation/compilation)

• Web Assembly (a text (S-expression based) and binary IR with goals similar to asm.js)

• SIMD.js

• Emscripten, Cheerp -- C/C++/LLVM to JavaScript/asm.js/webasm compilers

• Ramda (a library for functional programming in JavaScript; includes lenses, immutable data structures, etc. and is generally better than lodash)

• proxy-fun (list of resources related to the ES6 Proxy interface)

• Transferable Objects: Lightning Fast! (shows new interface for movable zero-copy buffers across Web Workers)

TypeScript

• Tutorial
• Handbook
• Compiler Options Reference
• TypeSearch (searches for type definitions)

CSS

• A Complete Guide to Flexbox, A Complete Guide to Grid

Java

• Interface Pollution in the JDK 8

Lua

• LuaJIT (fast JITed Lua interpreter)
• New Garbage Collector (design doc for LuaJIT 3's future GC)
• Love (a standalone game framework in Lua using LuaJit)

Haskell

• Learn You a Haskell for Great Good! (free book)
• Haskell Programming from First Principles (free book)
• Real World Haskell (free book)
• What I Wish I Knew When Learning Haskell (very useful rundown of the ecosystem, common and useful packages/types/etc)
• Introduction to Haskell
• Documentation for Prelude
• Stack (Package manager with stable package tree snapshots and sandboxing)
• Lenses
  • lens library
  • History of Lenses
  • Lenses in Pictures (nice visual explanation)
• Functors, Applicatives, And Monads In Pictures (visual explanation of functors/applicative functors/monads)
• A History of Haskell: Being Lazy With Class (a history of Haskell)
• Philip Wadler's monad papers
  • Monads For Functional Programming
• See the Purely Functional Data Structures and Free Monads sections in Data Structures above

LISP

• Recursive Functions of Symbolic Expressions and Their Computation by Machine (seminal LISP paper by McCarthy)
• Structure and Interpretation of Computer Programs (also known as The Wizard Book)
• The Art of the Metaobject Protocol (commercial book on the CLOS metaobject protocol for metaprogramming)
• Lambda Papers

Racket

• Racket Guide
• Realm of Racket (commercial book)

Erlang

• Learn You Some Erlang for Great Good! (free book)
• Documentation

OCaml

• Real World OCaml (free book)
• Documentation
• OPAM (Package Manager)

Rust

• Rust By Example (free book)
• Manual
• Documentation
• docs.rs (Third-party package documentation)

D

• Programming in D (free book / tutorial / reference)
• Language Reference
• Library Reference

Fortran

• Fortran on the IBM 704 (manual for the original Fortran for the IBM 704, from 1957)
• The History of FORTRAN

Web

HTTP

• HTTP Made Really Easy (simple introduction/guide to HTTP 1.0 and 1.1)

Optimization

• High Performance Browser Networking (free book)

Browser Engines

• How Browsers Work: Behind the scenes of modern web browsers (original)

• How browsers work internally (video talk)

• Let's build a browser engine!

• How Browser Works (slides)

• Faster HTML and CSS: Layout Engine Internals for Web Developers (video talk)

• How browser engines work? (video talk + slides)

• How Browsers Work - Part 1 - Architecture (archived)

• Gecko

  • Mozilla's Layout Engine (slides)
  • Gecko Overview

• WebKit

  • WebCore Rendering I – The Basics
  • WebCore Rendering II – Blocks and Inlines
  • WebCore Rendering III – Layout Basics
  • WebCore Rendering IV – Absolute/Fixed and Relative Positioning
  • WebCore Rendering V – Floats
  • Getting Started With the WebKit Layout Code (archived)
  • How WebKit Loads a Web Page (archived)
  • How WebKit Works (slides)
  • Rendering in WebKit (video talk)
  • WebKit For Developers

Layout

• Learn CSS Layout
• Everything You Never Knew About CSS Floats
• Rendering: repaint, reflow/relayout, restyle

Tools

Git

• git - the simple guide (simple intro to git)
• Pro Git (free book)
• Oh shit, git! (for when you inevitably mess up)

Make

• Make files not war (tutorial on make)

Design

• Dark Patterns (sets of subversive and potentially malicious design patterns)
• Motherfucking Website -> Better Motherfucking Website -> Best Motherfucking Website

Culture

• How To Ask Questions The Smart Way
• The XY Problem
• On The Cruelty Of Really Teaching Computing Science (famous Dijkstra essay)
• Grace Hopper on Letterman
• The Cathedral and the Bazaar (free book/essay by Eric Raymond)
• The Jargon File
• Execution in the Kingdom of Nouns (essay on Java-style OOP by Steve Yegge)
• Kill -9 by Monzy (a very dense CS-laden nerdrap song performed live at Stanford)
• Land of Lisp - The Music Video
• Sorting algorithms demonstrated with Hungarian folk dances