Nils M Holm's Bits and Pieces

Who am I? | No, really! | What's new? | Privacy Statement | ~nmh

LISP SYSTEM IMPLEMENTATION

[CS and math] [programming] [retro computing] [other stuff] [attic]

Books I've Written

NMH's Incomplete Dictionary of Statistics

Computer Science and Math

LISP System Implementation: A rather massive volume about the design and implementation of an interactive LISP environment in C and LISP. Focusing on compilation to abstract machine code, but covers all aspects of LISP implementation, including garbage collection, syntax analysis, code generation, semantics, tail call elimination, non-local exits, error handling, I/O, image files, and much, much more... The source code contained in the book is in the public domain.
Write Your Own Compiler: The tiniest compiler book I have ever written. It covers all steps in the compilation process from high level language (T3X) to executable (ELF). Lots of diagrams, lots of code, zero theory. The tour through the compiler itself spans less than 100 pages. All code in the book is provided under the CC0 license (public domain). It can be downloaded below.
An Introduction to Array Programming in Klong: This book introduces you to the world of solving problems with array operators, adverbs, idioms, and functions. Using examples of varying complexity, from a mundane matrix formatter to a complete Gaussian elimination solver, it takes you on an entertaining tour through the Klong language.
Practical Compiler Construction: This book offers a tour through the full compiler for a clean and sane subset of the C programming language (C89), covering lexical analysis, parsing, semantics, code generation, optimization, and runtime support, including lots of clarifying annotations and diagrams. The SubC compiler discussed in the book is in the public domain and can be downloaded below.
Prolog Control in Six Slides: The design and implementation of a pure PROLOG interpreter plus cuts in R4RS Scheme, based on a set of slides explaining the control algorithm behind depth-first resolution with negation as failure (SLDNF).
Scheme 9 from Empty Space (get the interpreter, play the game): S9fES is both a book and an interpreter for the R4RS Scheme programming language. The book offers a guided tour through every single line of the interpreter with lots of annotations and diagrams. It covers even the gory details, such as macro expansion, call/cc, and tail-call elimination.
An Introduction to Statistics with Klong: An introduction to the statistics library of the Klong programming language, covering data representation, visualization, basic statistical functions, probability distributions, χ² tests, and linear and non-linear regression.
NMH's Incomplete Dictionary of Statistics: A dictionary of statistics and probability that focuses on application and comprehensibility rather than completeness, hence an incomplete dictionary. Topics covered include probability, inference, modelling, regression, hypothesis testing. Contains lots of beautiful illustrations. All pages freely available, so you can take your own sample.
Compiling Lambda Calculus: An introduction to lambda calculus and the compilation of functional languages. Covers reduction, convertiblity, fixed points, representation of closures, and compilation of Scheme to C. The text is completely self-contained, but basic understanding of formal logic and programming will be helpful. Code is in Scheme und provided under the CC0 license.
Statistics, a short and painless introduction: A small book that covers the most fundamental principles of probability and statistics in simple and straight-forward prose, but without dumbing it down. Intended for students of natural and social sciences as well as everybody else who always wanted to know how statistics work.
Sketchy Scheme, 4.5^th Edition: A beginner-friendly introduction to functional programming in Scheme. This is a step-by-step guide to problem-solving in the functional way. The book contains lots of example, from trivial to advanced, as well as Scheme definitions of many standard procedures, an informal explanation of continuations, and a digression dealing with lambda calculus.
Logic Programming in Scheme: An introduction to the principles of logic programming in MicroKANREN, covering predicates, goals, negation, cutting, and the translation of functional code into declarative code. Chapter two uses logic programming to solve the well-known Zebra puzzle, and chapter three contains the complete and annotated implementation of MicroKANREN in portable Scheme.

Programming Languages

Scheme 9 from Empty Space (get the book, play the game): S9fES is both a book and an interpreter for the R4RS Scheme programming language. The interpreter is a very mature, portable and easily extendable implementation of the language. It provides an interface to some common Unix system calls, a large library, and compiles natively on Plan 9.
LISP9, an experimental LISP system: A LISP system that is intended to be hackable and comprehensible. The language is a cross between R4RS Scheme and ancient LISP with terse keywords, low-level macros, and simple semantics. The implementation is in C and LISP9. There is a comprehensive book describing the implementation.
Klong, a simple array language: Klong is an array language, like K or APL. Its programs use operators to manipulate lists (vectors) and (multi-dimensional) arrays. Klong is a mathematical notation rather than a programming language. It uses the ASCII alphabet and has simpler semantics than K. Its interpreter is based on S9core and should run on all systems providing a C89 compiler as well as on Plan 9.
Kilo LISP, a kilo byte-sized LISP system: Kilo LISP is a purely symbolic LISP system that runs in 64K bytes of memory. It is written in C89 and compiles fine using SubC (below), Turbo C, or any modern C compiler. The code is about 25K bytes of comprehensible C and LISP.
The SubC Compiler: SubC is a clean, fast, and simple compiler for a subset of C89 that can compile itself on various BSDs, Linux, Windows, and other systems. It also cross-compiles to DOS. Its code is in the public domain.
The T3X Compilers: T3X is a small, portable, procedural, block-structured, recursive, almost typeless, and to some degree object-oriented programming language. It targets the Tcode machine, the 8086 under DOS, and the 386 and Alpha processors under Unix.; T3X9 is a tiny, block-structured, procedural language. Its compiler can compile itself in the blink of an eye (0.05s on a 750MHz notebook). It currently generates ELF executables for FreeBSD-x86. T3X9 is a subset of T3X.
The XT3X Compiler and Virtual Machine: A T3X9 compiler and Tcode machine extended with functions for X11 graphics and OSS sound. Intended for writing simple video games as they were ubiquituos in the 1970's and 80's.
mLite, a lightweight, dynamic functional language: mLite is a general-purpose, functional, lightweight, dynamic programming language. It borrows ideas from both the Scheme and Standard ML languages, taking most of its syntax from ML and its dynamic nature from Scheme. It extends ML-style pattern matching by adding guarded patterns and also introduces the principle of "implicit guards".

Retro Computing

CP/NC – A Control Program for the NC100: CP/NC is a CP/M-compatible operating system for the Amstrad NC100 Notepad Computer. It is based on Russell Marks's ZCN operating system, but aims to feel more like an old-fashioned CP/M system.
–––==[The DOS Vault]==–––: Some DOS programs from the 1980's and 1990's, most of them written by me, quite a few of them never published before. Includes a few games, the T3X compiler, a small database program, etc.
LISPy things you can do in 64K bytes of core: Some of the first machines that ran LISP had less than 64K bytes of memory, and yet there are lots of fun things that you can do on such a machine. An exploration of purely symbolic LISP in limited memory.
VE, a visual editor for CP/M: This is a small (20KB) editor for Z80-based CP/M machines. It implements a subset of VI and is optimized for slow serial lines. Requires a 4MHz CPU and a VT52 terminal. Also works on the CP/NC console. Source code (in T3X) included.
BTN11: BTN11 is a two-pass assembler that generates absolute binaries for various models of the PDP-11. It is written in K&R (pre-ANSI) C.
unproto 1.7: This is a slightly modified version of Wietse Venema's unproto program (also via http) that works more cooperatively with the Mark Williams C compiler on Coherent 3.x. Here are the essential differences between the last official version (1.6) and this one.

Odds & Ends

More or less random things that keep me busy.

Science Fiction, Baby!: A gallery of science fiction stuff that I have created in the past decades.
Raja Yoga Revisited: A guide to systematic self-exploration based on ancient yoga scriptures, like the Upanishads, the Bhagavad Gita, etc. An attempt to view meditation in a scientific light. From 2009 but, hey, the sources are much older! ;)
Attention in the Digital Age: How does the ubiquitous fight for attention form our habits? A statistical analysis and opinionated essay based on data from the web server logs of this site.
Sensitivity as a Handicap: A short essay explaining sensitivity, why high sensitivity is a disadvantage in our society, and why this is a loss for all of us.
Love, Impending Doom, and the Drake Equation: Why we are doomed as a civilization, and why this is both inevitable and prefectly OK. An essay about a possible explanation of the Fermi Paradox.
~~Depressing IQ fact generator~~: Calculating the number of people in your "window of comprehension", based on your IQ. Warning: things get really depressing beyond 150. Removed due to the General Data Protection Regulation (GDPR). The code is in the Klong archive, in case you are interested.
What to do with a high IQ?: Most people think that a high IQ will make you successful, attractive, socially respected, etc, but many people actually suffer from being highly intelligent. This paper investigates the seeming paradox. Basic statistics required.
Where Do The Failed 0.1% Go? (PDF): An article about two highly intelligent people who fell through the social safety net. Including suggestions on how not to fail such people in the future. Published in Vidya #324/325 in 2015. Erratum: on the bottom of page 3, "window of 30 IQ points" should be "window of 15 IQ points".
~~Klong function plotter~~: Using the "plot.kg" module from the Klong library. Removed due to the General Data Protection Regulation (GDPR). The code is in the Klong archive, in case you are interested.
Lambda Calculator: A set of functions and a REPL for the λKβη-calculus, providing normal-order and applicative-order reduction, tracing, pretty-printing, various transformations, Church numerals, etc.
Minimal quasiquote expander using syntax-rules: Simple quasi-quotation in seven lines of Scheme, for your enjoyment or as a quick-and-dirty solution for Schemes that have syntax-rules, but not quasiquote.

The Attic

There used to be a link to free PDF copies of some draft versions and obsolete books here. The page is gone, but a copy can be found in the Internet Archive:

https://web.archive.org/web/20180403032702/www.bcl.hamilton.ie/~nmh/t3x.org/zzz/

Books

Lightweight Compiler Techniques (PDF): A discussion of techniques for implementing simple yet efficient compilers for procedural languages. Covers all phases of compilation: scanning, parsing, optimization, code synthesis. Little theory, lots of code. The T3X compiler described in this book can be found below.
Zen-Style Programming (PDF): An introduction to various aspects of computer science at break-neck speed: functional programming, arbitrary-precision arithmetics, meta-circular evaluation, searching and sorting, the limits of computability, streams and generators, formal grammars, syntax analysis, regular expressions, logic programming, design and implementation of programming languages, and much more...
Code: Zen Lisp
Die Anatomie einer Programmiersprache (PDF): An early precursor to Lightweight Compiler Techniques in German.
Code: BSL Compiler Kit

The Rest

FOOGOL IV, V5: Lindberg's FOOGOL IV compiler hacked up to emit 386 assembly language. Also converted to modern (ANSI 89) C. Compiles fine with SubC.
MINBASIC: An interpreter and compiler for an obscure BASIC dialect that I have created back in the early 1990's. Includes some simple games as example programs. The compiler is written in MINBASIC.
Mini Scheme v.3: An extended but still tiny version of Moriwaki and Kida's Mini Scheme interpreter, featuring string operations, type checking, file operations, improved macro syntax, and more complete error checking.
PD Korn Shell: A slightly patched version of pdksh, compiles on most modern BSD's and has a clear-screen function that you can bind to a key. This was the one tcsh feature I was missing most in pdksh. And: yes, I actually use this shell. :)
S9fES Interpreter, 2007 (1st ed.) version: The original version of the Scheme 9 interpreter from the first edition of the book, including fixes to the errata from 2009.
S9fES Interpreter, 2014 (3rd ed.) version: The Scheme 9 interpreter from the third edition of the book.
S9fES Interpreter, 2018 version: The last version of the original (pre-Reimagined) Scheme 9 interpreter.
SOL Operating System: SOL is a tiny, FORTH-based operating systems for the PDP-11 (sol-11.zip) and the IBM PC (sol-86.zip, hyperlinked sources). There is also a generic version (sol3.zip) running on a virtual stack machine. You need BTN11 (above) to compile the PDP-11 version. Bootstrapping the other versions requires a working T3X compiler. Good luck!
T3X Compiler, version 8.1.7b: T3X is a lightweight procedural language with backends for the 8086 (EXE), 386, Alpha, and the Tcode Machine. It features modules, objects, a full optimizing compiler, and a set of tools for manipulating Tcode. The Tcode port of the 8.1.7b compiler works fine on 64-bit systems. Development of T3X ceased in 2004. Version 6.8 of the compiler is described in the book "Lightweight Compiler Techniques" (above).
USELESS: An interpreter, compiler, and editor for a super-terse dialect of FORTH. Brevity = expressiveness? You decide. Lots of funny sample programs included.

contact | privacy