Example code for Understanding Computation
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:
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 -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 installto install Treetop, you can try out the parsers:
$ bundle exec irb -I. >> require 'treetop' => true >> Treetop.load('the_meaning_of_programs/parser/simple') => SimpleParser >> require 'the_meaning_of_programs' => true >> program = SimpleParser.new.parse('while (x < 5) { x = x * 3 }').to_ast => «while (x < 5) { x = x * 3 }» >> program.reduce(x: Number.new(3)) => [«if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } } else { do-nothing }», {:x=>«3»}] >> program.evaluate(x: Number.new(3)) => {:x=>«9»} >> program.to_ruby => "-> e { while (-> e { (-> e { e[:x] }).call(e) < (-> e { 5 }).call(e) }).call(e); e = (-> e { e.merge({ :x => (-> e { (-> e { e[:x] }).call(e) * (-> e { 3 }).call(e) }).call(e) }) }).call(e); end; e }" >> eval(program.to_ruby).call(x: 3) => {:x=>9}
$ bundle exec irb -I. >> require 'treetop' => true >> Treetop.load('programming_with_nothing/lambda_calculus/lambda_calculus') => LambdaCalculusParser >> require 'programming_with_nothing' => true >> two = LambdaCalculusParser.new.parse('-> p { -> x { p[p[x]] } }').to_ast => -> p { -> x { p[p[x]] } } >> require 'universality_is_everywhere' => true >> two.to_ski => S[S[K[S]][S[K[K]][I]]][S[S[K[S]][S[K[K]][I]]][K[I]]] >> two.to_ski.to_iota => ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ]]]]][ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ]]]]][ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ]]]] >> inc, zero = SKISymbol.new(:inc), SKISymbol.new(:zero) => [inc, zero] >> expression = SKICall.new(SKICall.new(two.to_ski.to_iota, inc), zero) => ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ]]]]][ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]]]][ɩ[ɩ[ɩ[ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ[ɩ[ɩ]]]]][ɩ[ɩ]]]][ɩ[ɩ[ɩ[ɩ]]][ɩ[ɩ]]]][inc][zero] >> expression = expression.reduce while expression.reducible? => nil >> expression => inc[inc[zero]]
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.