《计算的本质：深入剖析程序和计算机》读书笔记（第 1-2 章）

Created on 2020 / 12 / 25, 16:50:23#编程语言

旧书清理系列。“可计算理论”基础。

第 1 章 - 刚好够用的 Ruby 基础

Page 1交互式 Ruby Shell（REPL）：irb；
Page 2Ruby 基本语法：

# 局部变量与并行赋值；
greeting = 'hello'
width, height, depth = [1000, 2250, 250]  # 数组字面量；

# 双引号字符串插值；
"hello #{'dlrow'.reverse}"  # 无参信号传递可以省略括号；
o = Object.new
def o.to_s
  'a new object'
end
"here is #{o}"

# 检查对象（当 IRB 需要显示对象时调用）；
o = Object.new
def o.inspect
  '[my object]'
end
o

# 可变参数方法（“*” 运算符）；
def join_with_commas(before, *words, after)
  before + words.join(', ') + after
end
join_with_commas('Testing: ', 'two', 'three', 'four', '.')
arguments = ['one', 'two', 'three']
join_with_commas('Testing: ', *arguments, '.')  # 展开数组；
before, *words, after = ['Testing: ', 'one', 'two', 'three', '.']

# 代码块；
def numbers_names
  [yield('one'), yield('two'), yield('three')].join(', ')
end
numbers_names { |name| name.upcase.reverse }

# 枚举类型；
# def count(arr)
#   accumator = 0
#   for i in arr
#     accumator += 1 if yield(i)
#   end
#   puts accumator
# end
# count([1, 2, 3, 4, 5]) { |number| number > 2 }

(1..10).count { |number| number.even? }
(1..10).select { |number| number.even? }
(1..10).select(&:even?)  # 向代码块参数发送一个无参的 even? 消息；
(1..10).any? { |number| number < 8 }
(1..10).all? { |number| number < 8 }
(1..5).each do |number|
  if number.even?
    puts "#{number} is even"
  else
    puts "#{number} is odd"
  end
end
(1..10).map { |number| number * 3 }
(1..10).inject(0) { |result, number| result + number }  # 类似 ECMAScript 中的 reduce 方法；

# 结构体（用于生成其他类）；
class Point < Struct.new(:x, :y)  # Point 类拥有两个属性 x，y；
  def +(other_point)
    Point.new(x + other_point.x, y + other_point.y)
  end
  def inspect
    "#<Point (#{x}, #{y})>"
  end
end
a = Point.new(2, 3)
b = Point.new(10, 20)
a + b

# Monkey Patching（可以随时给类型或模块添加方法）；
class Point
  def -(other_point)
    Point.new(x - other_point.x, y - other_point.y)
  end
end

# 定义常量（任何以大写字母开头的变量，包括类和模块）；
NUMBERS = [4, 5, 6, 7]

# 删除常量；
Object.send(:remove_const, :NUMBERS)  # 给符号 “NUMBERS” 发送删除消息；

# 符号（常用做字典的键）；
:my_symbol

# 数组；
numbers = ['zero', 'one', 'two']
numbers.push('three', 'four')
numbers.drop(2)

# 范围；
ages = 18..30
ages.entries
ages.include?(25)  # “?” 表明函数会返回一个布尔值（函数名的一部分）；

# 字典；
fruit = { 'a' => 'apple', 'b' => 'banana', 'c' => 'coconut' }
dimensions = { width: 1000, height: 2250, depth: 250 }
dimensions[:depth]

# Lambda；
multiply = -> x, y { x * y }  # #<Proc (lambda)>；
multiply.call(6, 9)
multiply[6, 9]  # 调用方式与“函数”不同；

# 函数；
def add(x, y)
  x + y
end
add(10, 10)

# 类；
class Calculator
  def divide(x, y)
    x / y
  end
end
c = Calculator.new
c.class
c.divide(10, 2)

class MultiplyingCalculator < Calculator  # 继承；
  def multiply(x, y)
    # super(x, y)  # 可以用 super 调用父类的同名方法；
    x * y
  end
end
mc = MultiplyingCalculator.new
mc.class
mc.class.superclass
mc.multiply(10, 2)
mc.divide(10, 2)

# 模块（可以被任意包含的代码段封装）；
module Addition
  def add(x, y)
    x + y
  end
end
class AddingCalculator
  include Addition
end
ac = AddingCalculator.new
ac.add(10, 2)

Ruby 中的每一个值都是一个对象，对象之间彼此靠“发送消息”进行通信（风格来源于 Smalltalk）。表达式 “1 + 2” 可以理解为：使用参数 2 给对象 1 发送一个叫做 “+” 的消息，而对象 1 上则有一个可以处理该消息的方法（#+）；

o = Object.new  # 新建对象（给 Object 对象发送了 “new” 消息）；
def o.add(x, y)
  x + y
end
o.add(2, 3)
def o.add_twice(x, y)
  # 在方法定义内部，当前对象总是接受消息并执行此方法的对象；
  add(x, y) + add(x, y)
end
o.add_twice(2, 3)

第 2 章 - 程序和机器

Page 18“语义学（Semantics）”研究的是单词和它们含义之间的关系。语义不止关注抽象含义本身的基本性质，还关注具体的记号如何与它们的抽象含义关联起来；
Page 18三种描述编程语言的方法：

靠实现规范：直接以语言运行时的实现作为标准，如：Ruby、PHP、Perl 5；
靠文档规范：使用书面化的官方文档进行描述，如：C++、Java、ECMAScript；
靠数学方法：使用形式语义学中的数学方法准确描述编程语言的含义。

Page 20操作语义 - 小步语义：假想一台机器，用这台机器直接按照某种语言的语法进行操作，一小步一小步地对其进行反复规约，从而对一个程序求值。如何进行规约的过程（推理规则）通常使用元语言（数学符号）编写；

明确定义了操作应该发生的顺序；
大部分需要通过以“迭代”的方式来求值。

- 定义表达式语义：

每一个“可规约”的表达式都需要满足“自约束”，即：向外暴露同样的规约接口，具体实现向内部约束；
“普通表达式（+-*/）”规约：可以通过“小步语义”来实现；
“变量”规约，抽象机器不仅需要存储当前表达式，还需要存储从变量名到它们的值的映射 — 上下文环境（env）。这部分可以用“散列表”进行存储；
“语句（“赋值”、“调用”、“回传”等）”规约：可以通过求值来生成另一个表达式（如：x = x + 1）。一个语句能够通过求值改变抽象机器的状态，而规约一个表达式则不会（两者的区别）；

- 1. 语句：

# 语句的最终规约结果（表示语句已执行成功）；
class DoNothing
  def to_s
    'do-noting'
  end
  def inspect
    "<<#{self}>>"
  end
  def ==(other_statement)
    other_statement.instance_of?(DoNothing)
  end
  def reducible?
    false
  end
end
# 循环语句；
# 1. 把 <<while (条件) {主体}>>；规约为 <<if (条件) {主体;while (条件) {主体}} else { do-noting }>> 和一个没有改变的环境。
class While < Struct.new(:condition, :body)
  def to_s
    "while (#{condition}) { #{body} }"
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    true
  end
  def reduce(env)
    [If.new(condition, Sequence.new(body, self), DoNothing.new), env]
  end
end
# 序列语句；
# 1. 如果第一条语句是 <<do-nothing>>，就规约成第二条语句和原始的环境；
# 2. 否则，就对第一条语句规约，得到一个新的序列和一个规约后的环境。
class Sequence < Struct.new(:first, :second)
  def to_s
    "#{first}; #{second}" 
  end
  def inspect 
    "«#{self}»"
  end
  def reducible?
    true
  end
  def reduce(env)
    case first
    when DoNothing.new
      [second, env]
    else
      reduced_first, reduced_env = first.reduce(env)
      [Sequence.new(reduced_first, second), reduced_env]
    end
  end
end
# 赋值语句；
# 1. 如果赋值操作符右侧表达式可以规约，则得到一个规约了的赋值语句以及一个没有改变的上下文环境；
# 2. 否则，更新上下文环境，得到一个 DoNothing 语句及一个更新后的上下文环境。
class Assign < Struct.new(:name, :expr)
  def to_s
    "#{name} = #{expr}"
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    true
  end
  def reduce(env)
    if expr.reducible?
      [Assign.new(name, expr.reduce(env)), env]
    else
      [DoNothing.new, env.merge({ name => expr })]
    end
  end
end
# 条件语句；
# 1. 如果条件能规约，就对其规约，得到一个规约了的条件语句和一个没有改变的环境；
# 2. 如果条件是 true，就规约成结果语句和一个没有改变的环境；
# 3. 如果条件是 false，就规约成替代语句和一个没有改变的环境。
class If < Struct.new(:condition, :consequence, :alternative)
  def to_s
    "if (#{condition}) { #{consequence} } else { #{alternative} }"
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    true
  end
  def reduce(env)
    if condition.reducible?
      [If.new(condition.reduce(env), consequence, alternative), env]
    else
      case condition
      when Boolean.new(true)
        [consequence, env]
      when Boolean.new(false)
        [alternative, env]
      end
    end
  end
end

- 2. 独立表达式：

# Number 终结符；
class Number < Struct.new(:value)
  def to_s
    value.to_s
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    false
  end
end
# Boolean 终结符；
class Boolean < Struct.new(:value)
  def to_s
    value.to_s
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    false
  end
end
# LessThan 非终结符（可以规约）；
class LessThan < Struct.new(:left, :right)
  def to_s
    "#{left} < #{right}"
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    true
  end
  def reduce(env)
    if left.reducible?
      LessThan.new(left.reduce(env), right)
    elsif right.reducible?
      LessThan.new(left, right.reduce(env))
    else
      Boolean.new(left.value < right.value)
    end
  end
end
# Variable 非终结符（可以规约）；
class Variable < Struct.new(:name)
  def to_s
    name.to_s
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    true
  end
  def reduce(env)
    env[name]  # 从环境中返回变量的值；
  end
end
# Add 非终结符（可以规约）；
class Add < Struct.new(:left, :right)
  def to_s
    "#{left} + #{right}"
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    true
  end
  def reduce(env)  # 规约方法；
    if left.reducible?
      Add.new(left.reduce(env), right)
    elsif right.reducible?
      Add.new(left, right.reduce(env))
    else
      Number.new(left.value + right.value)
    end
  end
end
# Multiply 非终结符（可以规约）；
class Multiply < Struct.new(:left, :right)
  def to_s
    "#{left} * #{right}"
  end
  def inspect
    "<<#{self}>>"
  end
  def reducible?
    true
  end
  def reduce(env)  # 规约方法；
    if left.reducible?
      Multiply.new(left.reduce(env), right)
    elsif right.reducible?
      Multiply.new(left, right.reduce(env))
    else
      Number.new(left.value * right.value)
    end
  end
end

- 定义抽象机器：

# 机器运行时接受一个表达式，和一个上下文环境（保存变量信息）；
class Machine < Struct.new(:stat, :env)
  def step
    self.stat, self.env = stat.reduce(env)
  end
  def run
    while stat.reducible?
      puts "#{stat}, #{env}"
      step
    end
    puts "#{stat}, #{env}"
  end
end
# 使用抽象机器运行一个表达式；
Machine.new(
  Assign.new(:x, Add.new(Variable.new(:x), Number.new(1))),
  { x: Number.new(3) }
).run
Machine.new(
  If.new(Variable.new(:x), 
    Assign.new(:y, Number.new(1)), 
    Assign.new(:y, Number.new(2))),
  { x: Boolean.new(true) }
).run

# x = 1 + 1; y = x + 3, {}
# x = 2; y = x + 3, {}
# do-noting; y = x + 3, {:x=><<2>>}
# y = x + 3, {:x=><<2>>}
# y = 2 + 3, {:x=><<2>>}
# y = 5, {:x=><<2>>}
# do-noting, {:x=><<2>>, :y=><<5>>}
Machine.new(
  Sequence.new(
    Assign.new(:x, Add.new(Number.new(1), Number.new(1))),
    Assign.new(:y, Add.new(Variable.new(:x), Number.new(3)))), {}
).run

# while (x < 3) { x = x * 3 }, {:x=><<1>>}
# if (x < 3) { x = x * 3; while (x < 3) { x = x * 3 } } else { do-noting }, {:x=><<1>>}
# if (1 < 3) { x = x * 3; while (x < 3) { x = x * 3 } } else { do-noting }, {:x=><<1>>}
# if (true) { x = x * 3; while (x < 3) { x = x * 3 } } else { do-noting }, {:x=><<1>>}
# x = x * 3; while (x < 3) { x = x * 3 }, {:x=><<1>>}
# x = 1 * 3; while (x < 3) { x = x * 3 }, {:x=><<1>>}
# x = 3; while (x < 3) { x = x * 3 }, {:x=><<1>>}
# do-noting; while (x < 3) { x = x * 3 }, {:x=><<3>>}
# while (x < 3) { x = x * 3 }, {:x=><<3>>}
# if (x < 3) { x = x * 3; while (x < 3) { x = x * 3 } } else { do-noting }, {:x=><<3>>}
# if (3 < 3) { x = x * 3; while (x < 3) { x = x * 3 } } else { do-noting }, {:x=><<3>>}
# if (false) { x = x * 3; while (x < 3) { x = x * 3 } } else { do-noting }, {:x=><<3>>}
# do-noting, {:x=><<3>>}
Machine.new( 
  While.new(
    LessThan.new(Variable.new(:x), Number.new(3)),
    Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3)))),
    { x: Number.new(1) } 
).run

Page 40操作语义 - 大步语义：定义如何从一个表达式或语句直接得到它的结果。需要将程序执行当成一个“递归”而不是迭代，为了对一个更大的表达式求值，需要对所有比它小的子表达式求值，然后把结果结合起来得到最终答案；

更为松散，只说明哪些子计算会执行，而不会指明它们按照什么顺序执行。会执行较小规模的计算，并将其作为更大规模计算的一部分；
更多地使用“递归”的方式来进行，依赖栈来记住当前处理在整个计算中的位置；
不需要 Machine 类来反复执行规约和存储中间状态，而是只对程序的 AST 访问一次就计算出整个程序的结果。

- 表达式：

class Number
  def evaluate(env)
    self
  end
end
class Boolean
  def evaluate(env)
    self
  end
end
class Variable
  def evaluate(env)
    env[name]
  end
end
class Add
  def evaluate(env)
    Number.new(left.evaluate(env).value + right.evaluate(env).value)
  end
end
class Multiply
  def evaluate(env)
    Number.new(left.evaluate(env).value * right.evaluate(env).value)
  end
end
class LessThan
  def evaluate(env)
    Boolean.new(left.evaluate(env).value < right.evaluate(env).value)
  end
end
# 避免了类似“小步语义”产生的中间处理过程，只会得到一个包含最终结果的新环境；
class Assign
  def evaluate(env)
    env.merge({ name => expr.evaluate(env) })
  end
end
class DoNoting
  def evaluate(env)
    env
  end
end
class If
  def evaluate(env)
    case condition.evaluate(env)
    when Boolean.new(true)
      consequence.evaluate(env)
    when Boolean.new(false)
      alternative.evaluate(env)
    end
  end
end
# 初始环境需要“穿过”这两个求值过程；
class Sequence
  def evaluate(env)
    second.evaluate(first.evaluate(env))
  end
end
class While
  def evaluate(env)
    case condition.evaluate(env)
    when Boolean.new(true)
      evaluate(body.evaluate(env))  # body 必须是能够返回新 env 的语句；
    when Boolean.new(false)
      env
    end
  end
end

puts Number.new(23).evaluate({})
puts Variable.new(:x).evaluate({ x: Number.new(23) })
puts LessThan.new(Add.new(Variable.new(:x), Number.new(2)), Variable.new(:y)).evaluate({ x: Number.new(2), y: Number.new(5) })

# statement = Sequence.new(Assign.new(:x, Add.new(Number.new(1), Number.new(1))),Assign.new(:y, Add.new(Variable.new(:x), Number.new(3))) )
# puts statement.evaluate({})

statement = While.new(LessThan.new(Variable.new(:x), Number.new(5)),Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3))) )
puts statement.evaluate({ x: Number.new(1) })

Page 45操作语义（Operational Semantic）：通过描述一个解析器来说明一种语言的含义；其中，“小步语义”设定了一台能执行小操作的简单抽象机器，它包含了关于如何产生有用中间结果的详尽细节；而“大步语义”（参考 ML 语言）把汇编整个计算的重担交给了机器或执行它的人，在仅通过一步操作就把整个程序转换成一个最终结果的过程中，要求它跟踪许多中间子目标；
Page 46指称语义（Denotational Semantic）：关心从程序本来的语言到其他表示的转换（指语义上的描述，而非语言特征/语法结构的一一对应，因此并不是“转译”）。关注如何借助另一种语言的已有含义 — 一种低级的、更形式化的或者至少比正在描述的语言更好理解的语言 — 解释一个新的语言。通常用于把程序转成数学化的对象；

class Number
  def to_ruby
    "-> e { #{value.inspect} }"  # 返回 Proc 代码，带有名为 “e” 的环境变量参数；
  end
end
class Boolean
  def to_ruby
    "-> e { #{value.inspect} }"
  end
end
class Variable
  def to_ruby
    "-> e { e[#{name.inspect}] }"
  end
end
# 指称的组合（每一个子表达式都是一个 Proc 源代码）；
class Add
  def to_ruby
    "-> e { (#{left.to_ruby}).call(e) + (#{right.to_ruby}).call(e) }"
  end
end
class Multiply
  def to_ruby
    "-> e { (#{left.to_ruby}).call(e) * (#{right.to_ruby}).call(e) }"
  end
end
class LessThan
  def to_ruby
    "-> e { (#{left.to_ruby}).call(e) < (#{right.to_ruby}).call(e) }"
  end
end
# 语句的指称语义（对语句的求值会产生一个新的环境）；
class Assign
  def to_ruby
    "-> e { e.merge({ #{name.inspect} => (#{expr.to_ruby}).call(e) }) }"
  end
end
class DoNothing
  def to_ruby
    '-> e { e }'  # 直接返回当前环境；
  end
end
class If
  def to_ruby
    "-> e { if (#{condition.to_ruby}).call(e)" + 
    " then (#{consequence.to_ruby}).call(e)" + 
    " else (#{alternative.to_ruby}).call(e)" + 
    " end }"
  end
end
# 对第一个语句求值的结果会作为对第二个语句求值时的环境；
class Sequence
  def to_ruby
    "-> e { (#{second.to_ruby}).call((#{first.to_ruby}).call(e)) }"
  end
end
class While
  def to_ruby
    "-> e {" +
    " while (#{condition.to_ruby}).call(e); e = (#{body.to_ruby}).call(e); end;" + 
    " e" +
    " }"
  end
end
statement = While.new(
  LessThan.new(Variable.new(:x), Number.new(5)),
  Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3))))
# -> 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 }
puts statement.to_ruby
proc = eval(statement.to_ruby)
puts proc.call({ x: 1 })

Page 52形式化语义：用数学化的方法表达和分析语义。

形式化的“指称语义”关注的是：通过把程序转换成定义良好的数学对象（通常是函数）以获得程序的核心含义；
“形式化语义”的一个重要应用是：为一种编程语言的含义给出一个无歧义的定义，而不是让其依赖于自然语言规范文档和“由实现规范”这样更加随意的方法；
“指称语义”比“操作语义”抽象层次更高，它忽略了程序如何执行的细节。

Page 54实现语法解析器：基于 Treetop。

Last built on 2023 / 10 / 26, 11:37:10

曜彤.手记

《计算的本质：深入剖析程序和计算机》读书笔记（第 1-2 章）

第 1 章 - 刚好够用的 Ruby 基础

第 2 章 - 程序和机器

评论 | Comments