长风破浪会有时 直挂云帆济沧海

也許我這一生 始終在追逐那顆九號球

Programming Language Part B 课程笔记

本文是学习Coursera Programming Language课程的学习笔记,文章内容及代码均取自课程材料。

Interpreter or Compiler

实现编程语言的 workflow 如下图:

Parser 读取程序文本,检查 syntax,如果语法正确则输出 AST(abstract syntax tree)。如果该编程语言有 type checker,则将 AST 丢给 type checker 检查,通过 type check 后,就由 interpreter 或 compile 来运行程序并输出结果。

在实现编程语言 B 通常有下面两种办法:

  • 使用另一种编程语言 A 来实现 interpreter(命名为 evaluator 或 executor 更恰当),输入 B 语言写的代码,输出结果
  • 使用另一种编程语言 A 实现 compiler(命名为 translator 更恰当),将 B 翻译成第三种编程语言 C

Skipping Parsing

如果基于编程语言 A 来实现编程语言 B,就可以跳过 parsing 阶段:Have B programmers write ASTs directly in PL A

ML from a Racket perspective

ML is like a well-defined subset of Racket

Racket from an ML Perspective

One way to describe Racket is that it has “one big datatype”:all values have this type.

我的理解由于 Racket 是 dynamic typing,所以 ML 程序员看来 Racket 只有一个类型(这样 static type check 都能成功)

  • Constructors are applied implicitly (values are tagged)

    42 is really like Int 42

  • Primitives implicitly check tags and extract data, raising errors for wrong constructors

      fun car v = case v of Pair(a,b) => a | _ => raise …
      fun pair? v = case v of Pair _ => true | _ => false

Weak Typing

There exist programs that, by definition, must pass static checking but then when run can “set the computer on fire”?

  • Ease of language implementation: Checks left to the programmer
  • Performance: Dynamic checks take time
  • Lower level: Compiler does not insert information like array sizes, so it cannot do the checks

Racket is not weakly typed

  • It just checks most things dynamically*
  • Dynamic checking is the definition – if the implementation can analyze the code to ensure some checks are not needed, then it can optimize them away

The Part-Time Parliament 论文笔记

背景Paxos 岛兼职议会类似容错式分布式系统面对的问题:议员对应分布式系统中的进程,议员缺席对应进程挂掉。Paxos 设计的议会协议在议员经常缺席的情况下可以保证法令的一致性。The Single-Decree Synod单一法令的神会协议的演化如下: 首先由几个能保证一致性和允许进展性的约束推导出初级协议(preliminary protocol) preliminary protocol的约束版本得到基本协议(basic protocol),其满足一致性但不保证进展性 进一步约...…