tomstuart / computationbook Goto Github PK

Example code for Understanding Computation

License: Other

Ruby 100.00%

computationbook's Introduction

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
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
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 -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:

$ 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.

computationbook's People

Contributors

Stargazers

Watchers

Forkers

mudge inglesp howto-ruby pragnesh blackerby jgwhite mocoso qicst23 laoxu djnesmith imclab chqing pablojimeno xp7551 rwaldron sibirtsev ngpestelos cmdev8 drblinken zhuangzhuang masaki-sato slideclick kawasaki2013 dekexu killme2008 alex-learn guidealexis alixedi mengbo jserv intermezzo-fr saraba2monkey francisco-rojas chuanyo felixzhang00 hothat staskoval kissmeta yunge008 judasnow andyglick zhiruchen tavpritesh sprzhing rubyist-liu allsea9 nanguage mattbee supermanever iuliandumitru binape ekct00 weimingtom nielsabels guzishiwo szewa-polyu paulthomas publictestgit crazyrainman freudshow githubyangjunyi efeng1st jlollis ufo124 vsanna zhuyoujun0513 0x4fca uxlsl roachsinai rsj217 tonyyz mcgain beyonddream-productions startproge jhaoc riansyahtohamba johnvenn knrm knrm720 jayteesf as85207 maricaya codesimurg bearerpipelinetest markmckeown liyuray lizarb iq-scm nloadholtes mawuva chyyuu zerokay sv99 belinwu

computationbook's Issues

the_meaning_of_programs: LoadError on execjs/json

the_meaning_of_programs can not work because of LoadError on execjs/json .

The way to reproduce on Ubuntu Linux 14.04 by using Koding:

$ git clone https://github.com/tomstuart/computationbook.git && cd computationbook
$ sudo gem install execjs
$ sudo gem install rspec
$ sudo gem install treetop
$ irb -I. --simple-prompt
>> require 'the_meaning_of_programs'
LoadError: cannot load such file -- execjs/json

If I remove require 'execjs/json' from each Ruby file, the operation of require works:

$ find . -name "*.rb" | xargs sed -i "s#require 'execjs/json'##g"

But to_javascript is not really functioned and always complains:

NameError: uninitialized constant ExecJS::JSON

no need two kind of machine in small-step.

Add class as example

change

class Add
  def reduce(environment)
    if left.reducible?
      Add.new(left.reduce(environment), right)
    elsif right.reducible?
      Add.new(left, right.reduce(environment))
    else
      Number.new(left.value + right.value)
    end
  end
end

class Add < Struct.new(:left, :right)
   def reduce(environment)
    if left.reducible?
      left_reduce,  environment = left.reduce(environment)
      [Add.new(left_reduce, right), environment]
    elsif right.reducible?
      right_reduce, environment = right.reduce(environment)
      [Add.new(left, right_reduce), environment]
    else
      [Number.new(left.value + right.value), environment]
    end
  end
end

parallel assignment in small_step/machine.rb

Hello,
This may be a pebkac as my ruby is essentially non-existent, but when working through 'The Meaning of Programs' examples I notice that the parallel assignment in small_step/machine.rb step method:

self.statement, self.environment = statement.reduce(environment)

sets self.environment to nil after the first reduce:

?> Machine.new(
?> Add.new(Variable.new(:x), Variable.new(:y)),
?> {x: Number.new(3), y:Number.new(4)}).run
x + y, {:x=>«3», :y=>«4»}
3 + y,
NoMethodError: undefined method []' for nil:NilClass from /Users/rob/dev/ruby/computationbook/the_meaning_of_programs/small_step/variable.rb:9:inreduce'
from /Users/rob/dev/ruby/computationbook/the_meaning_of_programs/small_step/add.rb:13:in reduce' from /Users/rob/dev/ruby/computationbook/the_meaning_of_programs/small_step/machine.rb:3:instep'
from /Users/rob/dev/ruby/computationbook/the_meaning_of_programs/small_step/machine.rb:9:in run' from (irb):12 from /usr/local/bin/irb:12:in

I suppose reduce() should be returning the environment as well as the Number.
Hope this is useful feedback as I'm enjoying the book.

Need to reduce denotational statements?

In the book, when you introduce denotational statements, specifically the if statement, it doesn't appear to reduce the statements. For example, the following statement works when the environment has x as the Ruby value of false.

I loaded this code with irb and require './the_meaning_of_programs', then ran the following:

statement = If.new(
  Variable.new(:x),
  Assign.new(:y, Number.new(1)),
  Assign.new(:y, Number.new(2))
)
puts eval(statement.to_ruby).call({x: false})

Here y is assigned 2 as expected. However, when using a Boolean, it seems to be considered truthy and so y is assigned 1.

statement = If.new(
  Variable.new(:x),
  Assign.new(:y, Number.new(1)),
  Assign.new(:y, Number.new(2))
)
puts eval(statement.to_ruby).call({x: Boolean.new(false)})

Is there a missing step here? Should the Boolean be reduced to it's value?

Using evaluate works as expected

statement = If.new(
  Variable.new(:x),
  Assign.new(:y, Number.new(1)),
  Assign.new(:y, Number.new(2))
)
statement.evaluate({x: Boolean.new(false)})

tomstuart / computationbook Goto Github PK

computationbook's Introduction

Understanding Computation example code

computationbook's People

Contributors

Stargazers

Watchers

Forkers

computationbook's Issues

the_meaning_of_programs: LoadError on execjs/json

no need two kind of machine in small-step.

parallel assignment in small_step/machine.rb

Need to reduce denotational statements?

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent