Bottoms Scheme implementation project
history | edit |

Possibly interesting reading

This is a list of possibly fitting material. Not everything is interesting for the same stages in the project (in fact the typing, math and proofs topics are probably just for what might come after the current curriculum). We definitely won't have time to explore everything on this list, but perhaps you find something that you want to read. If you do, why not tell us about the ideas afterwards (if any)? (Could be anything from an informal recount to a real presentation, however you feel about it.)

Feel free to make your own suggestions. If you do so, why not put your name behind it in parens so that others could chat to you about it? (The initial items without names are from Christian.)

I've put suggestions that I haven't studied myself yet (but still think they might be interesting) in italics. Christian.

(There's also the More links page with less relevant links.)

Various

To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction

Lambda Diagrams

How Steve Wozniak Wrote BASIC for the Original Apple From Scratch

Code is not literature

Land of Lisp (HN)

(Nand2Tetris - Building a Modern Computer from First Principles (the Cambridge Programmer's Study Group is working through this course))

* [Build a Modern Computer from First Principles: Nand to Tetris Part II](https://www.coursera.org/learn/nand2tetris2) ([HN](https://news.ycombinator.com/item?id=14526344))

Testing

How to Prevent the next Heartbleed

QuickCheck / (Introduction to QuickCheck) / An introduction to QuickCheck with number theory and red-black trees (HN)

(FreeSWITCH RaspberryPi GCC Compiler Bug: users pay if the compiler developers don't invest the time to 'certify' their product.)

Concurrency

CHESS

(A (brief) retrospective on transactional memory: good or bad article? STM.NET versus Clojure STM (stackoverflow). STM.NET Released!)

(Occam / Occam-pi; Matt Jadud's research (1, 2))

"Currently trying to extend blame semantics to concurrent systems"

Distribution

Kali Scheme

Input/output, sequencing

Programming with Managed Time (HN, LtU); Programming with Managed Time (essay + videos) (HN)

(Functional reactive programming, The introduction to Reactive Programming you've been missing (HN, HN))

Actor model

(Communicating sequential processes; HN search)

(The Transactional Memory / Garbage Collection Analogy)

A Gentle Introduction to Monad Transformers (HN), also see Extensible Effects: an alternative to Monad Transformers

(Option Monads in Rust (HN))

(Monoids, Functors, Applicatives, and Monads: Main Ideas (HN))

C

How Should You Write a Fast Integer Overflow Check? / Testing for Integer Overflow in C and C++ / (IOC, Clang manual: -fsanitize=signed-integer-overflow, -fsanitize=unsigned-integer-overflow, also see -ftrapv; LLVM has Arithmetic with Overflow Intrinsics) / Fast integer overflow detection, libo (HN) (see also 2 followup articles, and hint for GCC 5's __builtin_add_overflow etc.) / (The Performance Cost of Integer Overflow Checking (HN))

Integer overflow discussion in Rust: 0560-integer-overflow. Also, Myths and Legends about Integer Overflow in Rust (HN).

Understanding Integer Overflow in C/C++ (pdf, 2012) (HN)

Vulnerabilities Induced by Migrating to 64-Bit Platforms (PDF) (HN)

(C-Reduce)

(rr (HN))

(‘C and C++ in critical systems’: various articles)

Tis-interpreter – find subtle bugs in programs written in standard C (HN)

Programming languages

Rust, ATS, PreScheme(paper, other papers): VM implementation language candidates.

VLISP for an old implementation in ASM, then its own variant of PreScheme. HN post mentioning it.

Idris Agda Cryptol Mezzo Nim (formerly Nimrod) Shen1 Io Erlang (Julia) (Clojure) (Slate (HN)) (atomo) (Atomy) (Forth: see 'Virtual machines')

(1 successor of Qi, after Mark Tarver, creator of Qi, gives up and then resumes.)

I could put all of the above in italics, as I have studied none deeply (although I know enough about their concepts to think they may be relevant in some ways). Christian.

(BitC: abandoned. Possibly interesting 'Retrospective Thoughts on BitC' mailing list posts.)

COGENT: Certified Compilation for a Functional Systems Language (lobsters)

(Rust for C++ programmers)

(Agda vs. Coq)

(Coq: The world's best macro assembler? (HN))

(Differences between Agda and Idris)

Learn You an Agda (HN)

Arc

Kernel, klisp

Programming Language Development: The Past 5 Years

Formal semantics

Reflection

interactive scientific computing #2 of 2, goldilocks languages (historical overview with some interesting pointers)

Shen: A Sufficiently Advanced Lisp [video] (2014)

Kicking the tires of Shen Prolog (from A gentle introduction to Prolog (HN))

For S3C

Genie: idea of explicit ownership transfer (could that be useful statically?) (is that present in Vala, too?)

Mathematics

Linear logic

Predicate logic

Categories from scratch (HN)

Extensional Higher Order Prolog (HN)

Types

Algebraic Data Types (HN)

(What is type safety? (HN))

Dependent type

Irken Language – A Scheme with parametric polymorphism

(Grow Your Own Type System (Ocaml))

(Curry-Howard, the Ontological Ultimate, HN)

(Type systems and logic (hackerschool) (HN))

So you want to learn type theory (HN)

Types (Gist) (HN)

Runtime types

Schema (blog post, HN)

Theorem proving

Expressing formal proofs in a computer language: Y Scheme (okmij.org) (Would this be related perhaps?: Propositions as Types (HN))

Software Foundations

Reflex DSL: Automating Formal Proofs for Reactive Systems (HN)

Proof-carrying code

Wikipedia

Denotational semantics

An Executable Implementation of the Denotational Semantics for Scheme

ATS

Articles by Chris Double

Idris

(2048: Idris example)

Virtual machines

Forth(/Factor/J2): concatenative, stack based language; ancestor of stack based VMs like the JVM?, alternative to register based machines / variable based languages.

2 Functional Programming and the J Programming Language (HN); unlike Forth, J is functional.

Not virtual, but real stack based CPU: ZPU architecture document (ZPU docs)

Scorth, a Scheme (also by Matt Jadud) that compiled to Forth on the LEGO Mindstorm: paper, traces of a talk, sources?

(List of Forth implementations)

SECD machine

(Warren Abstract Machine)

Announcing Potential: x86-64 assembler as a Haskell EDSL / The Potential Programming Language (status?)

(BPF: The Forgotten Bytecode)

Dis virtual machine from Inferno

Papers and memos on the Interlisp-D VM in the Xerox Alto source code archive

UCB CS294: Virtual Machines and Managed Runtimes (HN)

LuaJIT 2.0 intellectual property disclosure (HN)

Secure operating systems

seL4 (Wikipedia, recent paper: Comprehensive formal verification of an OS microkernel)

Compilation

A-normal form (how is this really different from CPS and SSA (static single assignment) form?: see discussion on HN, re Compiling with Continuations, Continued (2007) [pdf])

a continuation-passing style intermediate language for guile

Introducing the WebKit FTL JIT (HN)

(The Implementation of Functional Programming Languages: Simon Peyton Jones on how to compile Haskell. Different: lazy, pure.)

Partial evaluation

The Three Projections of Doctor Futamura (Mike)

Partial Evaluation Tutorial; Racket code

(Partial Evaluation and Immutable Servers HN)

Macros

We're planning to implement non-hygienic macros, so these aren't really relevant, but anyway..:

(Understanding syntactic closures and environments during macro expansion.)

(Ask Christian for more.)

Continuations

guile and delimited continuations

Parsing

S-expressions are so easy to parse that there is probably no need to study parsing literature. But maybe that's not completely right? (Does anyone have some good pointers?)

Top-down, Bottom-up, Shift-reduce parsing

Object orientation

Flavors

CLOS

Other lisp-implementation-for-learning projects

Note that many of these are much more simplified (relying heavily on features of the host language, or not implementing features that are essential to write some classes of functional programs, not implementing error handling, no security ambitions).

Learn C and build your own Lisp (HN) (no GC, some odd language design decisions; more complete alternatives mentioned in the HN discussion)

How to Write a Lisp Interpreter in Python (norvig.com) (HN), mentions Project 4: A Scheme Interpreter

EarlGray's SECD machine

zozotez, a tail call optimizing LISP interpreter that runs on BrainFuck, bootstrapped with EBF (extended BrainFuck)

Scheme from Scratch; Royal Scheme

(Lisp in QBASIC)

7 lines of code, 3 minutes (HN) (not really so much from scratch?)

Building a LISP from scratch with Swift (HN)

Mal – Make a Lisp, in 68 languages (github.com) (HN)

* [Guide - The Make-A-Lisp Process](https://github.com/kanaka/mal/blob/master/process/guide.md)
* [Mal for TempleOS](https://github.com/bagnalla/holyc_mal)

Lisp in less than 200 lines of C (carld.github.io) (HN)

Other Scheme implementations

Heist (in Ruby)

klisp

Chibi-Scheme (with a VM in C)

femtolisp (with a VM in C)

Fargo (in JavaScript; "Instead of call/cc, Fargo supports Ruby-style fibers for pausing and resuming async work.")

Outlet

Husk Scheme (in Haskell)

(Egison (derivative of Husk))

Picobit (with a VM in C, and a custom C compiler)

Bones (minimalistic, batch compiler to x86_64 asm)

SIOD, part of Scheme In A Grid (SIAG) (download) (HN)

The more well-known (and bigger) implementations: Racket, Chicken, Larceny, Gambit, Scheme-48/SCSH, MIT-Scheme, Guile, SCM, Gauche, Ikarus, Stalin, Kawa, SISC, Bigloo, Chez Scheme.

There are also elk, oaklisp, scheme2c, tinyscheme in Debian.

Between death and revival: Rscheme, T.

Category:Scheme_implementations (Wikipedia)

List on schemewiki.org

Other resources

Readscheme

Lambda the Ultimate