thoughts on programming language

所谓编程语言要素就是说，一旦我们对于这些编程语言的要素掌握之后，我们就可以用这个语言做一些事情了。编程语言要素必须是基本的(atomic)， 然后我们在学习语言的时候，首先学习这些基本的内容之后，就可以开动了。不要使用形式的东西来概括，必须是一些可以put into practice的东西

• 基本类型 // 比如字符串如何表示等
• 复合结构 // 如何将基本类型复合出来
• 内存管理 // 如何进行内存分配释放
• 程序结构 // 变量作用域，变量声明，类的访问权限，程序结构
• 语言特有特性 // 反射，动态代码生成，continuation
• 工程组织性 // 如何组织一个大的项目，如何服用代码比如库
• 文件系统 // 如何操作文件，读取特定字节等
• 并发控制 // 比如进程，线程，锁
• 网络通信 // 通讯设施
• C/C++扩展 // 如何使用C/C++来编写扩展提高效率

一种语言并不会因为拥有其他语言所没有的特征，就比其他的语言更好。重要的问题并不在于语言有多少特征，而在于它所拥有的特征是否足以在某个希望的应用领域支持某种所希望的程序设计风格

• 所有特征必须清晰优雅地集成在语言中
• 能够组合这些特征得到一个解决方案
• 减少荒谬和专用的特征
• 任何特征的实现都不应该给未使用该特征的程序强加上明显的额外开销
• 用户只需要了解自己在编写程序时所明确使用的那个语言子集

https://class.coursera.org/proglang-003/lecture

Now that we have learned enough ML to write some simple functions and programs with it, we can list the essential “pieces” necessary for defining and learning any programming language:

• 句法 Syntax: How do you write the various parts of the language?
• 语义 Semantics: What do the various language features mean? For example, how are expressions evaluated?
• 惯用方法 Idioms: What are the common approaches to using the language features to express computations?
• 库函数 Libraries: What has already been written for you? How do you do things you could not do without library support (like access files)?
• 工具 Tools: What is available for manipulating programs in the language (compilers, read-eval-print loops, debuggers, …)

lua-applicaiton-programming.html

用Lua开发应用程序不仅仅要学习语言本身，包括运行环境，开发工具和部署工具等等。

A lot goes into writing an application:

• The language itself. Which version of Lua? (Does it matter?)
• The language environment. Platforms? Libraries? Frameworks?
• The development tools.Editors? Static checkers? Testing? CI?
• The deployment. How will users install and run your program?

整个clojure生态系统中，需要你能够灵活运用的东西有很多，语言知识仅仅是一个部分而已，你会遇到下面的问题：

• 我应该使用什么工具来组织项目和依赖项？
• 什么才是良好的代码编写流程？
  • 对问题进行分解，识别出纯函数。
  • 学习标准库，这样你就能发现那些已经写好的功能。
  • 不要让实体泛滥，数据就得当做数据来用。（我的理解是尽量使用序列而不是class, 这样数据一览无余并且并且clojure有强大的序列操作库）
  • 在repl中做彻底的测试。
• 如何才能确保自己的代码是正确的？
• 我怎样才能保持代码灵活且易于维护？
• 我需要什么样的库？
• 我如何才能把clojure放到万维网上？

强类型和弱类型，决定操作两个不同类型的值是否会出错：如果是1 + "string", 如果是强类型，那么报错；如果是弱类型，那么会提供相应的语义。在Python里面调用 1 + "string" 会出错，但是在Javascript里面 1 + "string" = "1string"。

静态和动态类型，强调一个值所持的类型是否可以动态变化，通常动态类型不需要在声明/定义变量的时候写类型，而静态类型需要（使用类型推导的辅助可能不需要）。在Python里面 x = "hello" 之后可以调用 x = 1, 而在 C++/Java/ML里面则没有办法之后将x绑定到其他类型的值上。

许多语言都有点对弱类型的支持。比如Python在 1.0 + 2这样的表达式会允许通过，但是SML在写 1.0 + 2 则会出现类型错误。所以其实强类型和弱类型这个区分不是特别明显，或者说也不是特别重要，完全看语言的语义设计。

这门课程 对于 weak typing 的解释则是这样的：如果一段程序通过了类型检查，不管是在编译期还是运行期，但是程序运行期间还出现未定义错误的话，比如造成运行环境崩溃或者是操作系统崩溃，那么这门语言就是弱类型的。 对于C/C++就是绝好的例子，我们编写的C语言程序通过了C编译器的检查并且生成了可执行代码，但是在编译器和运行期都不会对内存越界访问进行检查。所以弱类型并不是一个特别合适的名字。

这门课程 对静态类型和动态类型语言的优劣，从下面这几个方面进行了比较： pdf0 pdf1

1. Convenience 哪种语言方便
2. Not preventing useful programs 是否会拒绝某些有意义的程序
3. Catching bugs early 是否有助于发现Bugs
4. Performance 性能差异
5. Code reuse 代码复用性
6. Prototyping 是否适合原型开发
7. Evolution 是否适合迭代升级

https://philosophy.stackexchange.com/questions/6992/the-difference-between-soundness-and-completeness

Soundness is the property of only being able to prove "true" things.

Completeness is the property of being able to prove all true things.

Soundness强调某件事物的正确性/稳定性(no false negative)，Completeness强调某件事物的完备性(no false positive)。 它们代表了事物的两面，所以没有办法兼顾，同时满足soundness和completeness.

如果以类型系统为例，

• 如果通过类型检查，并且程序运行期间在类型上是绝对没有问题的，那么它就是符合soundness的。
• 如果程序运行期间不会出现类型错误的话，并且类型检查也可以通过的话，那么它就是符合completeness的。

通常静态类型语言的类型系统是正确的，但几乎都是不完备的。以下面这些SML程序为例，如果要达到完备性的话， 那么类似 `4 div "hi"` 这样的代码，如果在程序运行期间不执行的话，应该是可以通过的。

fun f1 x = 4 div "hi" (* but f1 never called *)

fun f2 x = if true then 0 else 4 div "hi"

fun f3 x = if x then 0 else 4 div "hi"
val x = f3 true

fun f4 x = if x <= abs x then 0 else 4 div "hi"

fun f5 x = 4 div x
val y = f5 (if true then 1 else "hi")

Why incompleteness

Almost anything you might like to check statically is undecidable:

• Any static checker cannot do all of: (1) always terminate, (2) be sound, (3) be complete
• This is a mathematical theorem!

Examples:

• Will this function terminate on some input?
• Will this function ever use a variable not in the environment?
• Will this function treat a string as a function?
• Will this function divide by zero?

Undecidability is an essential concept at the core of computing

• The inherent approximation of static checking is probably its most important ramification

动态语言的类型系统则是偏向completeness, 而在soundness方面通过运行时添加类型检查代码来满足。所以我的理解是， 就类型系统这个特性而言，动态语言的能力要比静态语言能力要广，代价则是运行时的类型检查开销。

大部分OOP都实现了动态分派，以python代码为例，在 `A::m` 代码里面调用 `m2` 方法，而这个m2方法是在类型B里面定义的

class A:
    def __init__(self):
        pass

    def m(self):
        print("A::m")
        self.m2()


class B(A):
    def __init__(self):
        super()

    def m2(self):
        print("B::m")

b = B()
b.m()

动态分派是OOP的一个杀手锏，有点类似闭包对FP的意思。如何手动实现动态分派呢？最关键的一点就是方法绑定是运行时才知道的， 也就是具体调用哪个方法，必须在运行时去查找。同理字段方法也是运行时才知道的，这个也必须分离。

使用racket来实现的话，一个对象里面包含 `fields` 和 `methods` 两个属性，每个属性都是一个查找表。在访问字段和方法的时候， 都需要去对应的查找表里面查找。

;; Our "objects" will have:
;;  * an immutable list of mutable "fields" (symbols and contents)
;;  * an immutable list of immutable "methods" (symbols and functions taking self)
(struct obj (fields methods))

; like assoc but for an immutable list of mutable pairs
(define (assoc-m v xs)
  (cond [(null? xs) #f]
        [(equal? v (mcar (car xs))) (car xs)]
        [#t (assoc-m v (cdr xs))]))

(define (get obj fld)
  (let ([pr (assoc-m fld (obj-fields obj))])
    (if pr
        (mcdr pr)
        (error "field not found"))))

(define (set obj fld v)
  (let ([pr (assoc-m fld (obj-fields obj))])
    (if pr
        (set-mcdr! pr v)
        (error "field not found"))))

(define (send obj msg . args) ; convenience: multi-argument functions (2+ arguments)
  (let ([pr (assoc msg (obj-methods obj))])
    (if pr
        ((cdr pr) obj args) ; do the call
        (error "method not found" msg))))

https://en.wikipedia.org/wiki/Multiple_dispatch

按照维基百科的解释是，多重分派可以根据参数实际运行类型，或者是参数的某些属性，匹配到相同名字的多个函数下面的某一个。 我本来希望以下面Java代码为例，写一个clojure的实现（因为clojure支持multimethod），但是奈何水平不行只能作罢，只能写个其他的分派函数意思一下。

(defmulti foo (fn [x] (do (println "dispatch-fn") (:type x))))

(defmethod foo :string [x]
  (println (str "this is string value => " (:value x))))

(defmethod foo :integer [x]
  (println (str "this is intteger value => " (:value x))))

(foo {:type :string :value "world"})
(foo {:type :integer :value 2000})

分派函数可以任意的，并且允许含有side-effect（但是最好不要这样做，因为不知道会调用多少次）。

user=> (load-file "test.clj")
dispatch-fn
this is string value => world
dispatch-fn
this is intteger value => 2000
nil

多重方法和Java/C++里面的静态重载还有点不同。静态重载函数也可以通过参数类型进行区分同名函数，但是和多重方法的差别在于，这种类型匹配是静态的。 以下面代码为例子，虽然代码里面 `inst` 创建对象实际是类型B，但是因为在字面上类型是A，所以匹配上了 `call_m (A inst)` 这个实现。不过因为OOP的方法调用 都是动态指派，最终调用的还是 `B::m`.

class A {
    public void m() {
        System.out.println("A::m");
    }
}
class B extends A {
    public void m() {
        System.out.println("B::m");
    }
}
class Test {
    public void call_m(A inst) {
        System.out.println("call_m(A)");
        inst.m();
    }
    public void call_m(B inst) {
        System.out.println("call_m(B)");
        inst.m();
    }
    public static void main(String [] args) {
        Test t = new Test();
        A inst = new B();
        t.call_m(inst);
    }
}

➜  playbook javac Test.java && java Test
call_m(A)
B::m

https://zh.wikipedia.org/wiki/%E5%AD%90%E7%B1%BB%E5%9E%8B

通常我们在OOP里面接触到的子类(subclass)，是子类型的一种实现方式。这种实现方式是名义子类型，也就是在名字上确定了类型之间的关系。

另外一种子类型实现是结构子类型，有点类似于duck-typing这个意思。只要在结构上，父类里面所有的字段和方法，在子类里面都都有，那么就满足子类型关系。

书写上 `t1 :< t2` 表示t1是t2的子类型。通常子类型有下面几个特性：

1. “Width” subtyping: A supertype can have a subset of fields with the same types （字段可以更多）
2. “Permutation” subtyping: A supertype can have the same set of fields with the same types in a different order（字段顺序没有关系）
3. Transitivity: If t1 <: t2 and t2 <: t3, then t1 <: t3（具有传递性）
4. Reflexivity: Every type is a subtype of itself（具有反身性）

子类型还有另外一个特性是深度子类型化(depth subtyping). 这个特性是可选的，就是嵌套字段类型是否也需要满足子类型。这个特性特别重要，如果满足这个特性并且要求类型检查是sound的， 那么必须要求数据不能修改（或者是类似Java实现方式，在运行时增加类型检查）。我们用下面这个例子说明depth subtyping的问题。

If ta <: tb, then {f1:t1, …, f:ta, …, fn:tn} <: {f1:t1, …, f:tb, …, fn:tn}

fun setToOrigin (c:{center:{x:real,y:real}, r:real})=
c.center = {x=0.0, y=0.0}

val sphere: {center:{x:real,y:real,z:real}, r:real} = {center={x=3.0, y=4.0, z=0.0}, r=1.0}
val _ = setToOrigin(sphere)
val _ = sphere.center.z (* kaboom! (no z field) *)

Java是如何处理深度子类型化的呢？可以看看下面这个数组例子。这段代码是可以通过编译的，但是在运行时出现Exception， 异常出现在 `xs[0] = new A();` 这个代码上。 Java在这里增加了类型判断，先判断出xs元素的真实类型，然后确保赋值对象是子类。Java对数组做了单独处理，可能因为数组是Java里面原始类型的原因，但是对List这类容器就直接不允许了。

import java.util.ArrayList;

class A {
}
class B extends A {
    public int foo = 0;
}
class Test {
    public static void reset(A[] xs) {
        xs[0] = new A(); // exception happened.
    }
    public static void main(String [] args) {
        B[] xs = new B[10];
        reset(xs);
        System.out.println(xs[0].foo);
    }
}

/* Compile Error
class Test {
    public static void reset(ArrayList<A> xs) {
        xs.set(0, new A());
    }
    public static void main(String [] args) {
        ArrayList<B> xs = new ArrayList<B>(10);
        reset(xs);
        System.out.println(xs.get(0).foo);
    }
}
*/

➜  playbook javac Test.java && java Test
Exception in thread "main" java.lang.ArrayStoreException: A
	at Test.reset(Test.java:8)
	at Test.main(Test.java:12)

Java在处理深度子类型上另外一个case就比较常见了，就是处理null. 在类型上，null是所有类型的子类，因为你可以创建类型类型A然后 `A a = null`. 所有这些代码在编译期都可以通过类型检查，但是需要增加代码在运行期进行Null判断。

协变(covariance)和逆变(contravariance)是subtyping应用在容器,函数以及其他构造器上的产生的概念。假设我们的构造器用函数f表示：

• if ta <: tb, and f(ta) <: f(tb), 那么就是f要求类型协变
• if ta <: tb, and f(tb) <: f(ta), 那么就是f要求类型逆变

我们以下面的函数来解释什么时候要求协变，什么时候要求逆变

fun bar (fx : {a : int, b: int} -> { c: int, d: int}) (x: {a:int, b:int}) : {c:int, d:int} = fx x

fun foo (p: { a: int, b: int}) : { c: int, d: int } =
    {c = 10, d = 20}

fun foo2 (p: {a : int }) : {c : int, d: int, e: int} = { c = 10, d = 20, e = 30}

val _ = bar foo {a = 3, b = 4}

假设我们这里需要把foo2替换foo的话，如果ML支持subtyping的话，那么要求：

1. foo2 接受的参数必须比 foo 接受的参数要少，更抽象。ta <: tb, fun-arg(tb) <: fun-arg(ta), 所以在函数参数上，要求类型是逆变的。
2. foo2 返回的值一定 foo 返回的值更多，更具体。ta <: tb, fun-ret(ta) <: fun-ret(tb), 所以在函数返回值上，要求类型是协变的。

更形式化的 `t1 <: t2, t3 <: t4 => t2->t3 <: t1->t4`

泛型和具体类型有点像类型光谱的两端：一个是可以匹配任意类型，一个则是只能匹配单一的类型。泛型的完全的多态，具体类型则没有任何多态的意思。

是否有部分多态呢？这种多态有泛型的含义，但是同时也可以通过子类型进行约束，这就是约束性的多态。Java里面就实现了这套东西，比如我们可以在 泛型之前添加 `<T extends A>`, 就要求T是个泛型，但是必须是A的子类(子类型), 而 `<T super A>` 则表示T是个泛型，但是必须是A的父类型。

TODO: examples