README.md

Understanding Computation example code in Rust

The example code of Understanding Computation, an O’Reilly book about computation theory. Re-implement by language Rust.

Build:

Use

cargo build

to build the code.

Table of Content:

• Chapter 2: The Meaning of Programs
  • syntax
  • small-step operational semantics
  • big-step operational semantics
  • denotational semantics
  • simple-parser
• Chapter 3: The Simplest Computers
  • deterministic and nondeterministic finite automata
  • regular expressions
  • regex parser
• Chapter 4: Just Add Power
  • deterministic and non-deterministic pushdown automata
• Chapter 5: The Ultimate Machine
  • deterministic Turing machines
• Chapter 6: Programming with Nothing
  • FizzBuzz with Closures
  • the lambda calculus
  • lambda parser
• Chapter 7: Universality is Everywhere
  • partial recursive function
  • ski calculus
  • iota calculus
  • tag systems
  • cyclic tag systems
• Chapter 8: Not planning to implement this chapter.
• Chapter 9: Programming in Toyland
  • abstract interpretation: arithmetic with signs
  • type systems

Reading guide:

Most of the example code is implemented in testing form, you can find them in mod.rs. To view the test result, use following command:

RUST_TEST_THREADS=1 cargo test -- --nocapture

You can specify keyword in testing name in the command line.

For example:

$ RUST_TEST_THREADS=1 cargo test -- --nocapture ski_swap
running 1 test
test universality_is_everywhere::ski_calculus::tests::test_ski_swap ... swap: S[K[S[I]]][K]
S[K[S[I]]][K][x][y]
K[S[I]][x][K[x]][y]
S[I][K[x]][y]
I[y][K[x][y]]
y[K[x][y]]
y[x]
ok

If you find any bugs or other programs with the code, please open an issue.