Coursera Programming Languages, Part A 华盛顿大学 Week 2

本文主要是介绍Coursera Programming Languages, Part A 华盛顿大学 Week 2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

第一周介绍了 ML 语言的一些表达与基本的 Language pieces
第二周主要关注 ML 语言中的各种类型 (type)

Conceptual ways to build new types

任何一门编程语言都包含有两种类型，基础类型 (base type) 与复合类型 (compound type)。
其中，基础类型包括 int, bool, string 这种单一的类型，而复合类型的定义里可以包括不止一种基础类型。
我们可以简单的将复合类型分为三类：

• Each-of type (Product type) : 积类型。积复合类型 t 可以包括 t1, t2, ..., tn 基本类型中的 每一种 (Each of)
  一个典型的例子是 Tuple 类型。 a = (3, true) : int * bool
• One-of type (Sum type | tagged union) : 和类型 / 标签联合类型。和复合类型 t 可以包括 t1, t2, ..., tn 基本类型中的 任一种 (One of)
  可以看作是把不同的类型，通过携带标签 (tag field) 的方式放在了一起。在 ML 语言中，值构造器 (value constructor) 就可以看作是标签。
  一个典型的例子是 Option 类型。(int option -> int / NONE)
• Recursive type : 递归类型。递归类型的定义中通常包含自我引用 (self-reference) 。其定义也经常结合和类型与积类型，这使得定义递归数据结构成为了可能。
  一个典型的例子是 list 类型。(hd a int list -> int; tl a int list -> int list / [])
  不同的类型之间可以互相嵌套。 (Nested)

Records : Another approach to build each-of type

ML 语言中的 Record type 是一种每一个成员是一个命名域 (named field) 的 each-of type。我们使用 Record expression 来创建一个 Record value。

e = {foo = (3, true), bar = ("hi", 4)} : {bar : string*int, foo : int*bool}
#foo e = (3, true), #bar e = ("hi", 4) (* 通过 # 取出值 *)

foo, bar 都是这个 Record 的命名域。在 REPL 中命名域会按照字典序排序。
{f1 = e1, f2 = e2, ..., fn = en} 是一个 Record expression 的标准形式，其中每个 f 都是命名域的名称，e 是表达。我们无需声明 e 的类型，type-checker会自动帮我们检测类型。

Syntactic sugar : the truth about tuples

我们发现 tuples 和 records 有很多相似之处，都是 each-of 类型，允许任意多不同类型的复合。
不同的是，tuple 是通过组分的位置 (By position) 来调用各种组分的，而 records 则是通过组分对应的命名域 (By name) 来调用的。
不难发现，tuple 实际上是一种特殊的 record ： 其 field name 均为 1 到 n 中的任意整数，即

(e1, e2, ..., en) = {1 = e1, 2 = e2, ..., n = en}

且

t1*t2*...*tn = {1 : t1, 2 : t2, ..., n : tn}

ML 语言使用 record 定义了 tuple。问题来了，tuple 的功能用 record 完全可以实现，为什么 ML 语言还要提供这么一种写法 (semantics) 呢？
这就要引出 语法糖 (syntactic sugar) 的定义了：

计算机语言中添加的某种语法，这种语法对语言的功能并没有影响，但是更方便程序员使用。通常来说使用语法糖能够增加程序的可读性，从而减少程序代码出错的机会。

因此，tuple 就是一种语法糖：即使去掉这个 feature，我们仍然可以利用 record 来实现；然而有了这个feature，我们的代码更简洁，更利于理解。

Datatype bindings: Build our own "one-of" types

接下来我们介绍 datatype binding，这是目前我们学到的第三种 binding 类型。它能够帮我们构建标签联合类型。
下面是一个例子：

datatype mytype = TwoInts of int*int
                | Str of string
                | Pizza

以上的例子定义了一个类型 mytype，其值 (value) 可以是 int*int 或者 string 或者 nothing。
任何值都会被标记 (tagged) 来让我们知道它的种类：而这些“标签” (tags) 就是所谓的构造器 （constructors），在我们的例子里体现为 TwoInts, Str, 与 Pizza。这些构造器的名字是自定义的，并且不同的构造器可以标记相同的数据类型。
例子中的 datatype binding 向环境中添加了：

• 一个新的类型 mytype
• 三个构造器 TwoInts, Str, Pizza
  构造器实际上是一种将指定的类型转换为自定义类型的函数。在我们的例子中，TwoInts : int*int -> mytype, Str : string -> mytype, Pizza : mytype。注意到 Pizza 本身就是 mytype 类型的值。
  通过 constructor 我们可以构造 mytype 类型的值。如 TwoInts(1, 2), Str"hi", Pizza。
  对于同样是 one-of type 的 option 来说，通过 isSome : option -> bool 函数可以判断 variant 类型 (NONE or SOME)，valOf : t option -> t 可以取出 SOME 中的值。而如果是自己定义的 datatype ML 语言并不提供这些函数，只能自己手写。我们接下来会学到一种更好的方式: Case expressions

How ML provides access to datatype values : Case Expressions

fun f x = (* f has the type mytype -> int*)
  case x of
    Pizza => 3
  | TwoInts(i1, i2) => i1 + i2
  | Str s => String.size s

在 case expression 中，每一个 branch 都是 p => e 的形式，其中 p 成为 pattern。
注意每一个 branch 的 e 必须是相同的类型，在上述例子中为 int。
pattern 看起来像是 expression，但实际上它并不会被 evaluate。真正被 evaluate 的是其后的 expression 。pattern 存在的意义是为了与之后的 expression 进行匹配 (match)。因此对一个 case expression 进行 evaluate 的过程被称为 pattern-matching 。
通过 case expression 与函数递归性质的结合，我们可以实现一下操作：

datatype exp = Constant of int
             | Negate of exp
             | Add of exp*exp
             | Multiply of exp*exp
fun eval x = 
  case x of
    Constant e => e
  | Negate e => ~ (eval e)
  | Add (e1, e2) => eval e1 + eval e2
  | Multiply (e1, e2) => (eval e1) * (eval e2)

eval(Add(Constant 3, Negate (Constant 3))) (* 这个表达式的结果是 0，这实际上是一个树形结构*)

Datatype bindings and Case expressions so far, precisely

Datatype bindings:

datatype t = C1 of t1 | C2 of t2 | ... | Cn of tn

向环境中添加 t 与 C1, C2, ..., Cn
(of tn) 可以省略如果 Cn carries nothing ，Cn 本身的类型即为 t
Case expressions:

case e of p1 => e1 | p2 => e2 | ... | pn => en

Case expressions 将 e evaluate 为 v，然后找到第一个与 v 匹配 (matches) 的 pi，然后 evaluate 对应的 ei 作为整个 case expression 的结果
形如 Ci(x1, x2, ..., xn) 的 pattern， Ci 为类型为 (t1t2...tn -> t) 的构造器（或者类型为 t, Ci carries nothing）。这样的 pattern 匹配 (match) 一个形如 Ci(v1, v2, ..., vn) 的值并且 将每一个 xi 与 vi 做 binding 来 evaluate 对应的 ei，。

这篇关于Coursera Programming Languages, Part A 华盛顿大学 Week 2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！