Baike.dev
All toolsOnline toolsAI codingTrendingOpen sourceNewsSubmit
Log in
< Back to tools
C

computationbook

> 编程语言
Open source

Example code for Understanding Computation

506 stars0 likes0 views
WebsiteGitHub

About

Example code for Understanding Computation

Understanding Computation example code

This is the example code for Understanding Computation, an O’Reilly book about computation theory. (Here’s a sample chapter.) Ruby 1.9 or 2.0 is required.

Right now it’s a pretty rough dump of code from the book. Each chapter has its own directory:

  • Chapter 2: The Meaning of Programs
    • syntax
    • parser
    • small-step operational semantics
    • big-step operational semantics
    • denotational semantics
  • Chapter 3: The Simplest Computers
    • deterministic and nondeterministic finite automata
    • regular expressions
  • Chapter 4: Just Add Power
    • deterministic and nondeterministic pushdown automata
  • Chapter 5: The Ultimate Machine
    • deterministic Turing machines
  • Chapter 6: Programming with Nothing
    • FizzBuzz with procs
    • the lambda calculus
  • Chapter 7: Universality is Everywhere
    • partial recursive functions
    • the SKI combinator calculus
    • Iota
    • tag systems
    • cyclic tag systems
  • Chapter 8: Impossible Programs
  • Chapter 9: Programming in Toyland
    • abstract interpretation: arithmetic with signs
    • type systems

Each directory contains definitions of the classes implemented in that chapter. There’s also a file named after each chapter (e.g. just_add_power.rb) that can be required to load all the code for that chapter.

For example:

irb
$ irb -I.
>> require 'universality_is_everywhere'
=> true
>> identity = SKICall.new(SKICall.new(S, K), SKICall.new(K, K))
=> S[K][K[K]]
>> x = SKISymbol.new(:x)
=> x
>> expression = SKICall.new(identity, x)
=> S[K][K[K]][x]
>> while expression.reducible?; puts expression; expression = expression.reduce; end; puts expression
S[K][K[K]][x]
K[x][K[K][x]]
K[x][K]
x
=> nil

If you run bundle install to install Treetop, you can try out the parsers:

…
…

If you have any questions, please get in touch via Twitter or email. If you find any bugs or other programs with the code, please open an issue.

Issues· 2 open

View all issuesOpen on GitHub

No open issues yet, or sync has not completed.

> Tags

Ruby

No comments yet. Be the first to share.

> Details

PublishedAug 1, 2026
UpdatedSep 17, 2026
Category编程语言
PricingOpen source

> Related tools

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言