最近有一些想法,想出一个系列来和大家聊聊编程语言和它的实现。初步想法是通过实现一门或多门语言来和大家探讨编程语言的本质,我希望通过这一系列,我可以给大家带来不同的视角去看待自己手中的编程语言。

除此之外,还有另外一些原因。我断断续续学习编程语言已有一些日子,主要是一些函数式的编程语言,像是 lisp 或是 ML 系的,也看过一些实现编程语言的书,像是一开始误入歧途看的《龙书》,慢慢发现的 《sicp》、《eopl》,还有一些正在看的 《tapl》、《Compiling with Continuations》等等。我想通过这个系列,看看自己到底学进去了多少,是走马观花,还是真的学有所获。另外,在这写作的过程中,我相信也能理清一些似懂非懂的概念和知识。于是,便有了这个计划。

具体说些什么?

以写解释器/编译器为主,在实现的过程中,讲述一些语言的特性和编译原理,目前计划中的有包括但不限于:

  • 闭包的本质
  • 类型检查
  • 类型推导
  • 模式匹配
  • 尾调用优化
  • continuation 和 cps
  • 编译到 native / js
  • 编译优化
  • gc

下期预告

下一期,我会发布一篇如何从零开始实现一门语言的解释器的文章,在此之前,让我们先看看我们要实现的语言长什么样子:

感兴趣的同学可以到 playground 试玩 = =

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
// **注意**,这不是 JavaScript,这里只是用了它的语法高亮

// 数字运算
let n = 1 + 2 * 3 - 4
print(n)  // => 3

// 字符串
let s = "hello " + "world"
print(s)  // => hello world

// 布尔值
print(true)   // => true
print(false)  // => false

// 列表
let l = [1,2,3,4,5]
print(head(l))  // => 1
print(tail(l))  // => [2,3,4,5]
print(cons(1, [2, 3]))  // => [1,2,3]
print(length(l))  // => 5

// 关系运算
print(1 > 2)   // => false
print(1 >= 2)  // => false
print(1 < 2)   // => true
print(1 <= 2)  // => true
print(1 == 2)  // => false
print(1 != 2)  // => true

// 逻辑运算
print(!true)  // => false
print(!false) // => true
print(true && false)  // => false
print(true || false)  // => true

// 条件分支
let x = if (1 > 2) {
  1
} else {
  2
}
print(x)  // => 2

// first class function, 闭包
let compose = func(f, g) {
  func(x) {
    f(g(x))
  }
}

let add1 = func(x) {
  x + 1
}

let double = func(x) {
  x * 2
}

print(compose(add1, double)(2))  // => 5

// 递归函数
letrec fact = func(n) {
  if (n == 0) {
    1
  } else {
    n * fact(n-1)
  }
}
print(fact(5))  // => 120


letrec fib = func(n) {
  if (n < 2) {
    n
  } else {
    fib(n-1) + fib(n-2)
  }
}
print(fib(9))  // => 34


letrec is_even = func(n) {
  if (n == 0) {
    true
  } else {
    is_odd(n-1)
  }
}
and is_odd = func(n) {
  if (n == 0) {
    false
  } else {
    is_even(n-1)
  }
}

print(is_even(13))  // => false
print(is_odd(13))   // => true

// 更复杂的一些例子
letrec map = func(f, list) {
  if (length(list) > 0) {
    let hd = head(list)
    let tl = tail(list)
    cons(f(hd), map(f, tl))
  } else {
    list
  }
}

letrec filter = func(f, list) {
  if (length(list) > 0) {
    let hd = head(list)
    let tl = tail(list)
    if (f(hd)) {
      cons(hd, filter(f, tl))
    } else {
      filter(f, tl)
    }
  } else {
    list
  }
}

letrec reduce = func(f, list, init) {
  if (length(list) > 0) {
    let hd = head(list)
    let tl = tail(list)
    reduce(f, tl, f(init, hd))
  } else {
    init
  }
}

print(map(func(x){ x + 1 }, [1,2,3,4,5]))      // => [2,3,4,5,6]

print(filter(func(x){ x > 3 }, [1,2,3,4,5]))   // => [4,5]

print(reduce(func(acc, e){ acc * e }, [1,2,3,4,5], 1))  // => 120

print(reduce(func(acc, e){ acc + e }, ["w", "o", "r", "l", "d"], "hello "))  // => hello world

值得注意的是 ,这里没有 return 关键字,默认 body 的最后一个表达式的值作为返回值。

对了,我会用世界上最流行的语言 JavaScript 来实现我们的语言。

敬请期待…