百科.dev
全部条目在线工具AI 编程趋势榜开源项目技术资讯提交条目
登录
< 返回工具列表
C

computationbook

> 编程语言
开源

理解计算的示例代码

506 stars0 点赞0 次浏览
访问官网GitHub

工具介绍

理解计算的示例代码

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 开放

查看全部 Issues在 GitHub 打开

暂无开放 Issues,或尚未同步最近议题。

> 标签

Ruby

暂无评论,来聊聊你的看法吧

> 工具信息

发布日期2026年8月1日
最后更新2026年9月17日
分类编程语言
定价开源

> 相关工具

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