X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938-2号

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


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

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

  1. (Page:1)交互式 Ruby Shell(REPL):irb
  2. (Page:2)Ruby 基本语法:
# 局部变量与并行赋值;
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)
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 章 - 程序和机器

  1. (Page:18)“语义学(Semantics)”研究的是单词和它们含义之间的关系。语义不止关注抽象含义本身的基本性质,还关注具体的记号如何与它们的抽象含义关联起来;
  2. (Page:18)三种描述编程语言的方法:
  1. (Page:20)操作语义 - 小步语义:假想一台机器,用这台机器直接按照某种语言的语法进行操作,一小步一小步地对其进行反复规约,从而对一个程序求值。如何进行规约的过程(推理规则)通常使用元语言(数学符号)编写;

- 定义表达式语义

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

- 表达式

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) })
  1. (Page:45)操作语义(Operational Semantic):通过描述一个解析器来说明一种语言的含义;其中,“小步语义”设定了一台能执行小操作的简单抽象机器,它包含了关于如何产生有用中间结果的详尽细节;而“大步语义”(参考 ML 语言)把汇编整个计算的重担交给了机器或执行它的人,在仅通过一步操作就把整个程序转换成一个最终结果的过程中,要求它跟踪许多中间子目标;
  2. (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 })
  1. (Page:52)形式化语义:用数学化的方法表达和分析语义。
  1. (Page:54)实现语法解析器:基于 Treetop


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)