計算機科学のブログ

Building Abstractions with Functions - Functions and the Processes They Generate - Greatest Common Divisors - evaluation, normal-order, applicative-order

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.2(Functions and the Processes They Generate)、1.2.5(Greatest Common Divisors)、Exercise 1.20の解答を求めてみる。

normal-orderの場合。

  • gcd(206, 40)
  • 40 === 0 ? 206 : gcd(40, 206 % 40)
  • gcd(40, 206 % 40)
  • 206 % 40 === 0 ? 40 : gcd(206 % 40, 40 % (206 % 40))
  • 6 === 0 ? 40 : gcd(206 % 40, 40 % (206 % 40))
  • gcd(206 % 40, 40 % (206 % 40))
  • 40 % (206 % 40) === 0 ? 206 % 40 : gcd(40 % (206 % 40), (206 % 40) % (40 % (206 % 40)))
  • 4 === 0 ? 206 % 40 : gcd(40 % (206 % 40), (206 % 40) % (40 % (206 % 40)))
  • gcd(40 % (206 % 40), (206 % 40) % (40 % (206 % 40)))
  • (206 % 40) % (40 % (206 % 40)) === 0 ? 40 % (206 % 40) : gcd((206 % 40) % (40 % (206 % 40)), (40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))))
  • 2 === 0 ? 40 % (206 % 40) : gcd((206 % 40) % (40 % (206 % 40)), (40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))))
  • gcd((206 % 40) % (40 % (206 % 40)), (40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))))
  • (40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))) === 0 ? (206 % 40) % (40 % (206 % 40)) : gcd((40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))), ((206 % 40) % (40 % (206 % 40))) % (40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))))
  • 0 === 0 ? (206 % 40) % (40 % (206 % 40)) : gcd((40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))), ((206 % 40) % (40 % (206 % 40))) % (40 % (206 % 40)) % ((206 % 40) % (40 % (206 % 40))))
  • (206 % 40) % (40 % (206 % 40))
  • 2

よって、剰余演算子は18回計算することになる。

applicative-orderの場合。

  • gcd(206, 40)
  • 40 === 0 ? 206 : gcd(40, 206 % 40)
  • gcd(40, 206 % 40)
  • gcd(40, 6)
  • 6 === 0 ? 40 : gcd(6, 40 % 6)
  • gcd(6, 40 % 6)
  • gcd(6, 4)
  • 4 === 0 ? 6 : gcd(4, 6 % 4)
  • gcd(4, 6 % 4)
  • gcd(4, 2)
  • 2 === 0 ? 4 : gcd(2, 4 % 2)
  • gcd(2, 4 % 2)
  • gcd(2, 0)
  • 0 === 0 ? 2 : gcd(0, 2 % 0)
  • 2

よって、剰余演算子は4回計算することになる。