最近在跟着C站上面的Programming Language这课,感觉还是挺不错的,开个坑整理一下…

Programming Language这一系列课是UW的CSE341公开课版本,内容基本一致(最新的spring2018版加了Haskell),作业有autograder评分,对白嫖党真是重大利好. 这门课并不是一个编程入门级课程,而是从更general的角度讲解一些编程语言的概念,比如抽象,类型系统,作用域,编程范型(fp, oop)之类的东西. 感觉这门课比较注重讲函数式,课上讲了standard ml, racket, ruby三种语言,这里的Part A专注于Standard ml. 感觉课程note讲得很系统了,这里抓一些我认为重要的东西记录一下.

About ML

一个ML程序包含了一系列的bindings, 每一个binding需要通过类型检查,之后进行evaluate. binding的类型基于static environment, binding evaluation基于dynamic environment.

对于一个binding来说, 我们一般考虑三个方面:

  • syntax (how you write something)
  • type-checking rules
  • evaluation rules

其实对这三个方面的关注对于学习一个新的语言特性的时候都是通用的.

variable binding

ML里面有多种binding, 拿variable binding做例子.

syntax:

val x = e

  • val: 关键字
  • x: 任意变量
  • e: 任意表达式.

type-check: 先从当前的static environment中对e进行type-check, 得到e的类型t -> x的类型也为t, 之后将x: type t加入static environment中.

evaluation: 和type-check 差不多, 只是这时是对dynamic environment进行操作

至于各种expression的具体定义…用到的时候去翻文档吧

ml里的binding都是不可变的(immutable), 例如给定一个variable bindingval x = 1+2, 在ml里面并不能用赋值的方式改变x, 只能创建一个新的dynamic environment来覆盖(shadow)这里的值.

function binding

同样考虑那三个方面

syntax:

fun x0 (x1: t1, ..., xn: tn) = e

  • fun: 关键字
  • x0: 函数名
  • 参数x1, …, xn, 类型分别为t1, …, tn
  • e: 函数主题,为任意表达式

type-check:

对e进行type-check, 此时的static environment中 x1 : t1, …, xn : tn, 若e的类型为t, 我们将x0 : t1 * … * tn -> t加入top-level static environment中. 注意这里的x1~xn参数仅存在函数里的static environment, 不加入top-level static environment. e的类型由类型推导系统推出,之后章节再介绍

evaluation:

ml中的函数本质上也是一个值, 我们将x0加入dynamic environment中,直到我们调用它的时候才真正进行evaluate

function call

前面提到只有调用函数的时候才会进行evaluate, ml中的function call也是一种表达式,syntax为 e0 (e1, ..., en), e0的类型为t1*...*tn -> t, 这时候的dynamic environment中e0->v0, e1->v1 …en->vn. v0是一个函数, 我们这个时候在这个dynamic environment中对v0的主体进行evaluation.

注意这里的dynamic environment是函数定义时的环境, 而不是调用时的环境.

举个例子:

1
2
3
4

y = 2
fun add2(x) = x + y
y = 1
add2(1)

这里执行的结果为3

Nested functions

我们可以在函数中用let…in…end表达式来实现nested function

在以下情况使用nested function定义一个helper function比较好:

  • 这个helper function仅在一个函数中使用
  • 如果它在别处使用, 容易被误用
  • 它之后比较可能被改变或者删除

在程序设计中, 可复用的代码省时省力, 但也意味着在之后更不方便修改

immutable data vs mutable data

immutable的好处简单来说就是: because it is impossible to mutate, we can create alias without thinking.

前面说到,ml里面并没有改变一个binding的内容的方法,一个binding在一个环境中永远都是一个值, 那些看起来像是赋值的操作实际上是创建了一个新环境去覆盖旧环境. 所以没办法赋值有什么好处呢?

我们来看一个ml中的例子:

1
2
3
4
5
6
7
8
9

fun sort_pair1 (pr: int * int) = 
    if #1 pr < #2 pr
    then pr
    else (#2 pr, #1 pr)

fun sort_pair2 (pr: int * int) = 
    if #1 pr < #2 pr
    then (#1 pr, #2 pr)
    else (#2 pr, #1 pr)

由于ml中数据的不可变性,以上两个函数是可以等价的,并不用关心返回的结果是一个新的变量还是旧变量的引用. 这样的话用第一种就比较好了,因为它省去了创建一个新tuple的空间. 但如果是在数据可变的情况下,这两种实现不能等价! 若对sort_pair1返回的结果再进行赋值操作,有可能会改变输入的pr的值

再举个例子:

1
2
3
4
5
6
7
8

fun append (xs: int list, ys: int list) = 
    if null xs
    then ys
    else hd (xs) :: append(tl(xs), ys)

val x = [2, 4]
val y = [5, 3, 0]
val z = append(x, y)

由于数据不可变,对以上代码的底层实现,下图两种实现方式是等价的,所以ml底层代码可以用第一种实现方式省空间.

接下来我们来看一下mutable data带来的一些问题, 考虑以下的java代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class ProtectedResource {
    private Resource theResource = ...;
    private String[] allowedUsers = ...;
    public String[] getAllowedUsers() {
        return allowedUsers;
    }
    public String currentUser() { ... }
    public void useTheResource() {
        for(int i=0; i < allowedUsers.length; i++) {
            if(currentUser().equals(allowedUsers[i])) {
                ... // access allowed: use it
                return;
            }
        }
    throw new IllegalAccessException();
    }
}

这样的代码是存在安全隐患的, 由于getAllowedUsers()返回的是allowedUsers的引用,我们是可以用这种方式给当前的user添加权限:

1

getAllowedUsers()[0] = currentUser()

为了避免这样的操作,getAllowedUsers返回的应该是a copy of allowedUsers:

1
2
3
4
5
6

public String[] getAllowedUsers() {
    String[] copy = new String[allowedUsers.length];
    for(int i=0; i < allowedUsers.length; i++)
        copy[i] = allowedUsers[i];
    return copy;
}

The pieces of a Programming Language

In a general way, 当学习一种新的编程语言时,我们可以重点关注以下几个方面:

  • 语法 Syntax: 语言具体怎么写
  • 语意 Semantics: 语言特性具体是怎样的,表达式怎么进行evaluate的
  • 风格 Idioms: 每种语言都有各自的coding style
  • 库 Libraries: 在工作中我们不需要重复造轮子,了解一些该语言下常用的库有助于提高生产力
  • 工具 Tools: 开发,调试这种语言的一些工具(编译器, REPL, debugger等)

第一周的笔记整理完了,我感觉这门课笔记还是拆成几篇blog来记比较好…