計算機プログラムの構造と解釈 第二版（第二章）

計算機プログラムの構造と解釈 第2版

http://sicp.iijlab.net/
　
Scheme でなく Ruby でやるのだ。

lispy.rb

class Cell
  def initialize(a, b)
    @car = a
    @cdr = b
  end
  attr_accessor :car, :cdr

  def inspect
    "(#{@car.inspect}, #{@cdr.inspect})"
  end
  alias :to_s :inspect
end

class Array
  def list
    iter = ->(a, b) {
      if a.empty?
        b
      else
        iter[a[0...-1], Cell.new(a[-1], b)]
      end
    }
    iter[slice(0...-1), Cell.new(slice(-1), nil)]
  end
  alias :~ :list
end

Cons = ->(a, b) {Cell.new(a, b)}
List = ->(ar) {ar.list}
Car = ->(ar) {ar.car}
Cdr = ->(ar) {ar.cdr}

if __FILE__ == $0
  p List[[1, 2, 3]]    #=>(1, (2, (3, nil)))
  p ~[:a, :b, :c]      #=>(:a, (:b, (:c, nil)))
  
  p Cons[Cons[1, 2], Cons[3, 4]]    #=>((1, 2), (3, 4))
  p Cons[Cons[1, Cons[2, 3]], 4]    #=>((1, (2, 3)), 4)
end

　
有理数の実装。

require_relative 'lispy'

make_rat = ->(n, d) {Cons[n, d]}
numer = ->(x) {Car[x]}
denom = ->(x) {Cdr[x]}
p_rat = ->(x) {puts "#{numer[x]}/#{denom[x]}"}

gcd = ->(a, b) { b.zero? ? a : gcd[b, a % b] }

make_rat = ->(n, d) {
  g = gcd[n, d]
  n1, d1 = n / g, d / g
  n1, d1 = -n1, -d1 if d1 < 0
  Cons[n1, d1]
}

add_rat = ->(x, y) {
  make_rat[numer[x] * denom[y] + numer[y] * denom[x], denom[x] * denom[y]]
}
sub_rat = ->(x, y) {
  make_rat[numer[x] * denom[y] - numer[y] * denom[x], denom[x] * denom[y]]
}
mul_rat = ->(x, y) {
  make_rat[numer[x] * numer[y], denom[x] * denom[y]]
}
div_rat = ->(x, y) {
  make_rat[numer[x] * denom[y], denom[x] * numer[y]]
}
is_equal_rat = ->(x, y) {
  numer[x] * denom[y] == numer[y] * denom[x]
}


one_half = make_rat[1, 2]
p_rat[one_half]    #=>1/2

one_third = make_rat[1, 3]
p_rat[add_rat[one_half, one_third]]    #=>5/6
p_rat[mul_rat[one_half, one_third]]    #=>1/6
p_rat[div_rat[one_half, one_third]]    #=>3/2
p is_equal_rat[one_half, one_half]     #=>true

問題2.2。

make_point = ->(a, b) {Cons[a, b]}
x_point = ->(point) {Car[point]}
y_point = ->(point) {Cdr[point]}
p_point = ->(point) {puts "(#{x_point[point]}, #{y_point[point]})"}

make_segment = ->(start_po, end_po) {Cons[start_po, end_po]}
start_segment = ->(segment) {Car[segment]}
end_segment   = ->(segment) {Cdr[segment]}

midpoint_segment = ->(seg) {
  s, e = start_segment[seg], end_segment[seg]
  make_point[(x_point[s] + x_point[e]) / 2, (y_point[s] + y_point[e]) / 2]
}

p1 = make_point[1, 2]
p2 = make_point[7, 12]
seg = make_segment[p1, p2]
p_point[midpoint_segment[seg]]    #=>(4, 7)

問題2.3。

make_rectangle = ->(a, b) {
  a, b = b, a if x_point[a] > x_point[b]
  Cons[a, b]
}
width  = ->(rect) {x_point[Cdr[rect]] - x_point[Car[rect]]}
height = ->(rect) {(y_point[Cdr[rect]] - y_point[Car[rect]]).abs}
perimeter = ->(rect) {(width[rect] + height[rect]) * 2}
area = ->(rect) {width[rect] * height[rect]}

p rect1 = make_rectangle[p2, p1]    #=>((1, 2), (7, 12))
p perimeter[rect1]    #=>32
p area[rect1]         #=>60

データとは何か

cons = ->(x, y) {
  dispatch = ->(m) {
    if m.zero?
      x
    elsif m == 1
      y
    else
      raise "Argument not 0 or 1 -- CONS #{m}"
    end
  }
}

car = ->(z) {z[0]}
cdr = ->(z) {z[1]}

p car[cons[2, 3]]    #=>2
p cdr[cons[2, 3]]    #=>3

問題2.4。これはややこしい。

cons = ->(x, y) {->(m) {m[x, y]}}
car = ->(z) {z[->(p, q) {p}]}
cdr = ->(z) {z[->(p, q) {q}]}

p car[cons[2, 3]]    #=>2
p cdr[cons[2, 3]]    #=>3

問題2.5。

cons = ->(a, b) {2 ** a * 3 ** b}

count = ->(x, a) {
  iter = ->(i, n) {
    (i % a != 0) ? n : iter[i / a, n + 1]
  }
  iter[x, 0]
}

car = ->(z) {count[z, 2]}
cdr = ->(z) {count[z, 3]}

p car[cons[2, 3]]    #=>2
p cdr[cons[2, 3]]    #=>3