庄周梦蝶

生活、程序、未来

声明:本博客所有文章,未经允许,禁止转载。谢谢。

Clojure Under a Microscope(1): Clojure 如何理解代码(上)

| Comments

开篇

最近在读《Ruby Under a Microscope》(已经有中文版《Ruby 原理剖析》)。我很喜欢这本书介绍 Ruby 语言实现的方式,图文并茂,娓娓道来,不是特别深入,但是给你一个可以开始学习 Ruby 源码的框架和概念。

我大概在 2-3 年前开始阅读 Clojure Java 实现的源码,陆陆续续也有一些心得,想着可以在读 Ruby 这本书的时候,按照这本书的思路梳理一遍。因此就有了这第一篇: Clojure 如何理解代码。

目录:

IO Reader

我们抛开 leiningen 等构建工具,Clojure 唯一需要的是 JVM 和它的 jar 包,运行一段简单的 clojure 代码,可以这样:

1
2
$ java -cp clojure.jar  clojure.main -e "(println (+ 2 2))"
4

clojure.main 是所有 clojure 程序的启动入口,关于启动过程,后续会有单独一篇博客来介绍。-e 用来直接执行一段传入的 clojure 代码。

当 clojure 读到 (println (+ 2 2)) 这么一行代码的时候,它看到的是一个字符串。接下来它会将这段字符串拆成一个一个字符来读入,也就是

1
( p r i n t l n   ( +   2   2 ) )

这么一个字符列表。这是通过 java.io.PushBackReader 来完成。 Clojure 内部封装了一个 LineNumberingPushbackReader 的类继承了 PushbackReader ,并且内部封装了 Java 标准库的 LineNumberReader 来支持记录代码行列号(为了调试、报错、记录元信息等目的),并且最重要的是支持字符的回退(unread),它可以将读出来的字符『吐』回去,留待下次再读。内部其实就是一个回退字符缓冲区。

我们来试试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(def r
  (-> "(println (+ 2 2))"
      (java.io.StringReader.)
      (clojure.lang.LineNumberingPushbackReader.)))

(.read r)            ; => 40  '('
(.read r)            ; => 112 'p'
(.read r)            ; => 114 'r'
(.unread r 114)      ; 『吐』回 'r' 
(.read r)            ; => 114 'r'   
(.read r)            ; => 105 'i' 
(.getLineNumber r)   ;  获取行号,从 1 开始
(.getColumnNumber r) ;  获取列号,从 0 开始
......

read 返回的的是字符串的整数编码(0 – 65535),Clojure 默认使用的是 UTF-8 编码。查看一个字符的整数编码可以 int 强制转换:

1
2
(int \()  ; => 40
(int \你) ; => 20320

上面的例子中我们 unread 了 114(也就是字符 ‘r’),然后下次调用 read,返回的仍然是 114。Clojure 的词法解析需要依赖这个回退功能。

此外还可以通过 getLineNumbergetColumnNumber 获取代码的行号和列号。这个行列信息最终会在 Clojure 对象的 metadata 里,比如我们看下 + 这个函数的行列信息:

1
2
user=> (select-keys (meta #'clojure.core/+) [:column :line :file])
{:column 1, :line 965, :file "clojure/core.clj"}

LispReader

单个字符是没有意义,接下来,Clojure 需要理解这些字符组成的字符串是个什么东西,理解了之后才能去执行求值。

这个『东西』,在 Clojure 里定义为 form。form 其实不是 clojure 特有的概念,而应该说是 lisp 系的语言都有一个概念。form 该怎么理解呢? 粗糙地理解,它是 Clojure 的对象,对应了一种 clojure 数据类型。更精确地说,form 是一个可以被正常求值的『程序单元』。

form 可以是:

  • Literals 字面量,比如字符、字符串、数字、nil、true/false 布尔值等等。
  • Symbol 符号,可以先简单地理解成类似 Java 的变量名称 identifier。
  • Lists 括号括起来的列表,如 (a b c)
  • Vectors 这是 clojure 有别于其他 lisp 方言的地方,中括号括起来的列表 [1 2 3]
  • Maps 散列表 {:a 1 :b 2}
  • Sets/Map namespace(1.9 新增)、deftype、defrecord 等其他类型。

那么 Clojure 是怎么将上面 reader 读到的字符流理解成 form 的呢?这是通过 LispReader 来完成,他负责将字符流解析成 form。我们尝试调用它的 read 方法来读取下 "(println (+ 2 2))",看看结果是什么:

1
2
3
4
5
 (def r
  (-> "(println (+ 2 2))"
      (java.io.StringReader.)
      (clojure.lang.LineNumberingPushbackReader.)))
 (def form (clojure.lang.LispReader/read r nil))

查看下 form:

1
2
3
4
user=> form
(println (+ 2 2))
user=> (class form)
clojure.lang.PersistentList

这个 form 的『样子』和它的文本字符串是一模一样的 (println (+ 2 2)),可是它不是字符串了,而是一个 List —— Clojure 的数据结构也是最重要的数据结构。这个一模一样就是所谓的同像性,也就是 Homoiconicity。因为 form 其实就是 AST,(println (+ 2 2)) 是一个层次的嵌套结构,转换成树形如下:

image

对应的刚好也是语法树,那么同像性就赋予我们操作这棵语法树的能力,因为它本质上就是一个普通的 Clojure 『对象』,也就是 form。我们可以随心所欲的操作这个 form,这也是 Clojure 强大的元编程能力的基础。

如果对应到编译原理, LispReader 不仅是 Lexer,同时也是 Parser。除了读取解析出词法单元之外,还会检查读取的结果是否是一个合法的可以被求值的 form,比如我们故意少一个括号:

1
2
user=> (read-string  "(+ 1 2")
RuntimeException EOF while reading  clojure.lang.Util.runtimeException (Util.java:221)

read-string 和另一个函数 read 最终调用的还是 LispReader,因为少了个括号,它会报错,这不是一个合法的 form。

Clojure 的编译器是 one-pass 还是 two-pass?

编译器可以多遍扫描源码,做分词、解析、优化等等工作。那么 Clojure 编译器是几遍?

严格来讲, Clojure 的编译器是 two-pass 的,但是很多情况下都是 one-pass 的。

但是 pass 这个概念在 clojure 里不是特别合适,按照 Rich Hickey 的答复,Clojure 的编译器更多是按照一个一个编译单元来描述更合适。每个单元是一个顶层(toplevel) form。

比如你有一个 clojure 代码文件:

1
2
3
(def a 1)
(def b 2)
(println (+ 1 2))

clojure 编译器会认为这里有三个顶层编译单元,分别是 (def a 1)(def b 2)(println (+ 1 2)),这三个编译单元都是最顶层的 form,它们会按照在文件中的出现顺序一一编译。

正因为编译单元要按照这个顺序,因此其实 clojure 不支持循环引用,或者前向查找(但是特别提供了 declare):

1
2
(def b 2)
(println (+ a b))

第二个 form 将报错,因为找不到 a:

1
 Unable to resolve symbol: a in this context

请注意,前向查找跟多少遍扫描没有关系,一遍扫描也可以实现前向查找。Clojure 这里的选择是基于两个理由:编译性能和名称冲突考虑。参见这个 YC 上的回复

LispReader 实现

LispReader 的实现是一个典型的递归下推机,往前读一个字符,根据这个字符的类型通过一系列 if 语句判断要执行哪一段解析,完整代码在 github,核心的循环代码精简如下,并加上注释:

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
for(; ;){
           //读取到一个 List,返回。
          if(pendingForms instanceof List && !((List)pendingForms).isEmpty())
              return ((List)pendingForms).remove(0);

          //读一个字符
          int ch = read1(r);

          //跳过空白,注意,逗号也被认为是空白
          while(isWhitespace(ch))
              ch = read1(r);

          //读到末尾
          if(ch == -1)
              {
              if(eofIsError)
                  throw Util.runtimeException("EOF while reading");
              return eofValue;
              }

          //读到设定的返回字符,提前返回。
          if(returnOn != null && (returnOn.charValue() == ch)) {
              return returnOnValue;
          }

          //可能是数字
          if(Character.isDigit(ch))
              {
              Object n = readNumber(r, (char) ch);
              return n;
              }

          //根据字符,查找 reader 表,走入更具体的解析
          IFn macroFn = getMacro(ch);
          if(macroFn != null)
              {
              Object ret = macroFn.invoke(r, (char) ch, opts, pendingForms);
              //no op macros return the reader
              if(ret == r)
                  continue;
              return ret;
              }
          //如果是正负符号,进一步判断可能是数字
          if(ch == '+' || ch == '-')
              {
              //再读一个字符
              int ch2 = read1(r);
              //如果是数字
              if(Character.isDigit(ch2))
                  {
                  //先回退 ch2 ,继续调用 readNumber 读出数字。
                  unread(r, ch2);
                  Object n = readNumber(r, (char) ch);
                  return n;
                  }
              //不是数字,回退 ch2
              unread(r, ch2);
              }
          //读取 token,并解析
          String token = readToken(r, (char) ch);
          return interpretToken(token);
          }
}

LispReader 维护了一个字符到 reader 的映射,专门用于读取特定的 form,也就是上面 getMacro 用到的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   static IFn[] macros = new IFn[256]; //特殊宏字符到 Reader 函数的映射
  macros['"'] = new StringReader();  // 双引号开头的使用字符串Reader
  macros[';'] = new CommentReader();  // 注释
  macros['\''] = new WrappingReader(QUOTE); // quote 
  macros['@'] = new WrappingReader(DEREF);// deref符号 @
  macros['^'] = new MetaReader();   //元数据
  macros['`'] = new SyntaxQuoteReader(); // syntax quote
  macros['~'] = new UnquoteReader();   // unquote
  macros['('] = new ListReader();      //list 
  macros[')'] = new UnmatchedDelimiterReader();  //括号不匹配
  macros['['] = new VectorReader();   //vector
  macros[']'] = new UnmatchedDelimiterReader();  // 中括号不匹配
  macros['{'] = new MapReader();     // map
  macros['}'] = new UnmatchedDelimiterReader();  // 大括号不匹配
  macros['\\'] = new CharacterReader();   //字符,如\a
  macros['%'] = new ArgReader();   // 匿名函数便捷记法里的参数,如%, %1
  macros['#'] = new DispatchReader();  // #下面将提到的 dispatch macro
  
  static private IFn getMacro(int ch){
    if(ch < macros.length)
        return macros[ch];
    return null;
   }

ListReader 实现解析

我们先看下 ListReader,它是一个普通的 Clojure 函数,继承 AFn,并实现了 invoke 调用方法,关于 Clojure 的对象或者说运行时模型,我们后文再谈,ListReader 核心的代码如下:

1
2
3
List list = readDelimitedList(')', r, true);
IObj s = (IObj) PersistentList.create(list);
return s;

调用了 readDelimitedList 获取了一个 List 列表,然后转换成 Clojure 的 PersistentList 返回。readDelimitedList 的处理也很容易理解:

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
//收集结果
ArrayList a = new ArrayList();

for(; ;)
  {
  int ch = read1(r);
  //忽略空白
  while(isWhitespace(ch))
      ch = read1(r);
  //非法终止
  if(ch == -1)
      {
      if(firstline < 0)
          throw Util.runtimeException("EOF while reading");
      else
          throw Util.runtimeException("EOF while reading, starting at line " + firstline);
      }
  //读到终止符号,也就是右括号),停止
  if(ch == delim)
      break;
  //可能是macro fn
  IFn macroFn = getMacro(ch);
  if(macroFn != null)
      {
      Object mret = macroFn.invoke(r, (char) ch);
      //no op macros return the reader
      
      //macro fn 如果是no op,返回reader本身
      if(mret != r)
          //非no op,加入结果集合
          a.add(mret);
      }
  else
      {
      //非macro,回退ch
      unread(r, ch);
      //读取object并加入结果集合
      Object o = read(r, true, null, isRecursive);
      //同样,根据约定,如果返回是r,表示null
      if(o != r)
          a.add(o);
      }
  }
//返回收集的结果集合

return a;

再举一个例子,MetaReader,用于读取 form 的元信息。

MetaReader 解析

Clojure 可以为每个 form 附加上元信息,例如:

1
2
user=> (meta (read-string "^:private (+ 2 2)"))
{:private true}

通过 ^:private,我们给 (+ 2 2) 这个 form 设置了元信息 private=true。当 LispReader 读到 ^ 字符的时候,它从 macros 表找到 MetaReader,然后使用它来继续读取元信息:

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
   //meta对象,可能是map,可能是symbol,也可能是字符串,例如(defn t [^"[B" bs] (String. bs))
   Object meta = read(r, true, null, true);
  //symbol 或者 字符串,就是简单的type hint tag
  if(meta instanceof Symbol || meta instanceof String)
      meta = RT.map(RT.TAG_KEY, meta);
  //如果是keyword,证明是布尔值的开关变量,如 ^:dynamic ^:private
  else if (meta instanceof Keyword)
      meta = RT.map(meta, RT.T);
  //如果连 map 都不是,那很抱歉,非法的meta数据
  else if(!(meta instanceof IPersistentMap))
      throw new IllegalArgumentException("Metadata must be Symbol,Keyword,String or Map");

  //读取要附加元数据的目标对象
  Object o = read(r, true, null, true);
  if(o instanceof IMeta)
      //如果可以附加,那么继续走下去
      {
      if(line != -1 && o instanceof ISeq)
          {
          //如果是ISeq,加入行号,列号
          meta = ((IPersistentMap) meta).assoc(RT.LINE_KEY, line).assoc(RT.COLUMN_KEY, column);
          }
      if(o instanceof IReference)
          {
          //如果是 ref,重设 meta
          ((IReference)o).resetMeta((IPersistentMap) meta);
          return o;
          }
      //增加 meta 到原有的 ometa
      Object ometa = RT.meta(o);
      for(ISeq s = RT.seq(meta); s != null; s = s.next()) {
      IMapEntry kv = (IMapEntry) s.first();
      ometa = RT.assoc(ometa, kv.getKey(), kv.getValue());
      }
      //关联到o
      return ((IObj) o).withMeta((IPersistentMap) ometa);
      }
  else
      //不可附加元素,抱歉,直接抛出异常
      throw new IllegalArgumentException("Metadata can only be applied to IMetas");

从代码里可以看到,不是所有 form 都可以添加元信息的,只有实现 IMeta 接口的 IObj 才可以,否则将抛出异常:

1
2
user=> ^:private 3
IllegalArgumentException Metadata can only be applied to IMetas  clojure.lang.LispReader$MetaReader.invoke (LispReader.java:820)

Dispatch Macros

Clojure 同时还支持 # 字符开始的所谓 dispatch macros,比如正则表达式 #"abc" 或者忽略解析的 #_(form)。这部分的解析也是查表法:

1
2
3
4
5
6
7
8
9
dispatchMacros['^'] = new MetaReader();  //元数据,老的形式 #^
dispatchMacros['\''] = new VarReader();   //读取var,#'a,所谓var-quote
dispatchMacros['"'] = new RegexReader();  //正则,#"[a-b]"
dispatchMacros['('] = new FnReader();    //匿名函数快速记法 #(println 3)
dispatchMacros['{'] = new SetReader();   // #{1} 集合
dispatchMacros['='] = new EvalReader();  // eval reader,支持 var 和 list的eval
dispatchMacros['!'] = new CommentReader();  //注释宏, #!开头的行将被忽略
dispatchMacros['<'] = new UnreadableReader();   // #< 不可读
dispatchMacros['_'] = new DiscardReader();   //#_ 丢弃

LispReader 读到 # 字符的时候,会从 macros 表找到 DispatchReader,然后在 DispatchReader 内部继续读取一个字符,去 dispatchMacros 找到相应的 reader 进行下一步解析。

更多 Reader 源码解析,可以参考我的注解,或者自行研读。

本篇总结

一张图来总结本篇所介绍的内容:

reader

Clojure 在从文件或者其他地方读取到代码文本后,交给 IO Reader 拆分成字符,然后 LispReader 将字符流解析成可以被求值的 form。

我们前面提到 LispReader 同时是 Lexer 和 Parser,但是它并不是完整意义上的 Parser,比如它不会去检查 if 的使用是否合法:

1
2
3
4
user=> (read-string "(read-string "(if 1 2 3 4)")")
(if 1 2 3 4)
user=> (if 1 2 3 4)
CompilerException java.lang.RuntimeException: Too many arguments to if, compiling:(NO_SOURCE_PATH:93:1)

LispReader 只会检查它是否是一个合法的 form,而不会去检查它的语义是否正确,更进一步的检查需要 clojure.lang.Compiler 介入了,它会执行一个 analyze 解析过程来检查,这是下一篇要讲的内容。

声明:本博客所有文章,未经允许,禁止转载。谢谢。

Clojure Under a Microscope, clojure

« Clojure 并发实践:使用 pmap 加速程序 微信 phxpaxos 源码解读:fsync 和 fdatasync »

Comments