Code Contraptions

Like delicate assemblies inside mechanical watches, code can be small enough to see all at once but intricate enough to reward careful study. Code Contraptions highlights these interesting and digestible fragments of code.

[codecontraptions]

Walk the expression tree. At every node, generate fresh type variables for anything you don't know yet. When two things must be the same type, unify them. When unification fails, that's a type error.

Algorithm W in one sentence from the Loon introduction.

[codecontraptions]

in early january 2024, a group of motivated individuals asked arthur whitney to demonstrate the fundamentals of the design, organization and style of his method of writing interpreters in c in the most succinct and approachable way. about a day later, arthur offered a tiny interpreter of a toy vector language, implemented in about 25 lines of c with a small header file. his code is published in this repository under /ref.

—excerpt from the readme of kparc/ksimple, a repo hosting Arthur Whitney's pedagogical implementation of an array language from January 2024. Cheers to reading awc.

[codecontraptions]

Modal is a small language based on pattern-matching to rewrite trees. Superficially it looks a little like Prolog and Datalog, but it works differently. It's not quite a term-rewriting language, but it uses delimited string rewriting to apply the rules defined by the program until no more rules can be applied. Here's a tiny concatenative language in Modal:

<> (?x dup) (?x ?x) <> (?x ?y swap) (?y ?x) <> (?x pop) () .. (1 2 3) (4 5 6) swap pop dup 01 (4 5 6) (1 2 3) pop dup 02 (4 5 6) dup 00 (4 5 6) (4 5 6)

[codecontraptions]

Brian Kernighan demonstrates the composability of UNIX tools by walking you through interactively checking for spelling mistakes in a file.

[codecontraptions]

The making of the ["Highway at Night"](http://js1k.com/2014-dragons/demo/1951) JS1K 2014 submission.

[jdp]

One summer weekend in 1989, Arthur Whitney visited Ken Iverson at Kiln Farm and produced—on one page and in one afternoon—an interpreter fragment on the AT&T 3B1 computer. I studied this interpreter for about a week for its organization and programming style; and on Sunday, August 27, 1989, at about four o’clock in the afternoon, wrote the first line of code that became the implementation described in this document.

Roger Hui, on studying the small program that would inspire the J language interpreter.

[codecontraptions]

McCarthy's 1960 Lisp

The Lisp as designed by McCarthy in 1960. Translated into Common Lisp by Paul Graham. Originally from here.

(defun null. (x) (eq x '())) (defun and. (x y) (cond (x (cond (y 't) ('t '()))) ('t '()))) (defun not. (x) (cond (x '()) ('t 't))) (defun append. (x y) (cond ((null. x) y) ('t (cons (car x) (append. (cdr x) y))))) (defun list. (x y) (cons x (cons y '()))) (defun pair. (x y) (cond ((and. (null. x) (null. y)) '()) ((and. (not. (atom x)) (not. (atom y))) (cons (list. (car x) (car y)) (pair. (cdr x) (cdr y)))))) (defun assoc. (x y) (cond ((eq (caar y) x) (cadar y)) ('t (assoc. x (cdr y))))) (defun eval. (e a) (cond ((atom e) (assoc. e a)) ((atom (car e)) (cond ((eq (car e) 'quote) (cadr e)) ((eq (car e) 'atom) (atom (eval. (cadr e) a))) ((eq (car e) 'eq) (eq (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'car) (car (eval. (cadr e) a))) ((eq (car e) 'cdr) (cdr (eval. (cadr e) a))) ((eq (car e) 'cons) (cons (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'cond) (evcon. (cdr e) a)) ('t (eval. (cons (assoc. (car e) a) (cdr e)) a)))) ((eq (caar e) 'label) (eval. (cons (caddar e) (cdr e)) (cons (list. (cadar e) (car e)) a))) ((eq (caar e) 'lambda) (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))))) (defun evcon. (c a) (cond ((eval. (caar c) a) (eval. (cadar c) a)) ('t (evcon. (cdr c) a)))) (defun evlis. (m a) (cond ((null. m) '()) ('t (cons (eval. (car m) a) (evlis. (cdr m) a)))))

[codecontraptions]

> The program Bentley asked Knuth to write is one that’s become familiar to people who use languages with serious text-handling capabilities: Read a file of text, determine the n most frequently used words, and print out a sorted list of those words along with their frequencies. The story of Don Knuth's approach to a programming task and the follow-up review of his solution by a UNIX adept.

[codecontraptions]

The Smalltalk-71 "One Pager"

[codecontraptions]

> This is a tale of two approaches to regular expression matching.

[codecontraptions]

Ingenious ideas are simple. Ingenious software is simple. Simplicity is the heart of the Unix philosophy. The more code lines you have removed, the more progress you have made. As the number of lines of code in your software shrinks, the more skilled you have become and the less your software sucks.

the suckless manifest

[codecontraptions]

A regular expression matcher implemented in C. > Beautiful code is likely to be simple -- clear and easy to understand. Beautitful code is likely to be compact -- just enough code to do the job and no more -- but not cryptic, to the point where it cannot be understood. Beautiful code may well be general, solving a broad class of problems in a uniform way. One might even describe it as elegant, showing good taste and refinement.

[codecontraptions]

> ii is a minimalist FIFO and filesystem-based IRC client. It creates an irc directory tree with server, channel and nick name directories. In every directory a FIFO in file and a normal out file is created.

[codecontraptions]

The C source of Plan 9's uniq(1) command.

[codecontraptions]

This short Smalltalk fragment contains almost every syntactic element of the language.

[codecontraptions]

UNIX V5, OpenBSD, Plan 9, FreeBSD, and GNU coreutils implementations of echo.c

A comparison of echo(1) implementations.

[codecontraptions]

p8/lithp.rb

A Lisp in about 15 lines of tight Ruby.