Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

15 Apr 2021

The Racket Reference阅读笔记【一】Language Model相关

The Racket Reference 阅读笔记。

1 Language Model

1.2 Syntax Model

racket的语法解析分为两个阶段,一是read阶段,作用将文件中的字符解析成语法对象。而是expand阶段,作用是将语法对象进行必要的处理以便于下一阶段的进行。

expand阶段主要的工作是根据binding格式将语法树进行扩展。

1.2.1 Identifiers, Binding, and Scopes

标识符可以用来指向很多东西,比如变量,语法形式,宏转换器,升格的符号名亦或是语法对象。

绑定用来表示同一个标识符与其出现位置的关系。此处的标识符指向变量或者语法形式。在下面的例子中,第一个x绑定到第二个,第二个x是对第一x的引用:

(let ([x 5]) x)

绑定和引用取决于作用域集合。很多情况下可以产生新的作用域,每个作用域有自己的独特记号。

一个语法形式代表一个代码片段,比如一个标识符或者一个函数调用。其表示形式是一个语法对象。每个语法对象关联一个作用域集合。

当一个语法形式被解析为一个特定标识符,它的符号名、作用域集合所对应的含义(比如变量、语法形式、宏转换器)会被更新到一个去全局表中。一个标识符指向特定的绑定的时候,引用的符号名和标识符的符号名相同,且引用的作用域集合是绑定的超集。这种情况下,标识符指向的绑定的作用域集合是所有其他的超集。如果此绑定不存在,那么引用是有起义的。一个绑定遮蔽其他相同符号名但是作用域为子集的绑定。

下面的例子:

(let ([x 5])
  (let ([x 6])
    x)

第一个x绑定到第二个x,第二个x绑定到第三个x。第二个绑定的作用域集合是第一个绑定的超集,所以第三个x引用第二个绑定。

绑定有顶层绑定,模块绑定,局部绑定之分。模块内不允许引用顶层绑定。一个不受绑定的标识符是无绑定的。每个绑定附带一个通常表示为整数的阶段值。阶段值0表示运行阶段,此阶段的绑定构成基础环境。阶段值1对应外裹模块的展开阶段,此阶段的绑定构成转换环境。阶段值-1表示其他以阶段值1导入的模块的运行阶段。阶段值-1的绑定构成模板环境。标签阶段值是其他概念,不代表任何运行阶段。

同一标识符在不同阶段可以有不同的绑定,也就是不同阶段同一形式所关联的作用域集合可以不同。顶层或者模块环境谕示在每个阶段有不同的作用域。宏展开或者其他语法形式中的作用域则被统一添加到形式的所有阶段的作用域集合。

1.2.2 Syntax Objects

语法对象在单纯的Racket值之上增加了文法信息,源码位置,语法辖属以及tamper状态。文法信息构成作用域集合,每个阶段一个。特别地,一个标识符表示为一个包含符号名的语法对象,它的文法信息可以合并到全局绑定表,用以决定它在每个阶段的绑定。

当一个语法对象表示的表达式不止单个标识符以及简单常量的时候,可以解析其内容。可以用free-identifier=?以及bound-identifier=?来对比两个标识符。

对于下面的语法对象:

(let ([x 5]) (+ x 6))

可以解出两个x。free-identifier=?以及bound-identifier=?会告诉你两个x相同。

一个语法对象的文法信息可以移植到另一个语法对象,所以判断一个语法对象的时候,其符号名以及文法信息均会被考虑。

quote-syntax形式在程序的执行和表示之前搭起一座桥。比如(quote-syntax datum #:local)产生一个语法对象,它具有datum在解析时所具有的所有文法信息。类似的(quote-syntax datum)则移除了datum的某些作用域。

1.2.3 Expansion (Parsing)

展开过程则是以递归方式对语法对象在某个执行阶段的处理。这个过程是从阶段0开始的。语法对象附带的文本信息中的绑定则驱动了这个展开过程,处理子表达式的过程中会导致新的绑定产生。一些情况下,子表达式在更深入阶段展开。

1.2.3.1 Fully Expanded Programs

完全展开后的语法在文中有记述。

完全展开后的程序也就是解析了的程序。

1.2.3.2 Expansion Steps
  • 对于标识符,其绑定由其文法信息决定。如果绑定存在,则使用之。如不存在,那么会在同等文法信息下插入了一个符号名为'#%top的语法对象以替代之。插入的语法对象会具有implicit-made-explicit properties信息。如果#%top标识符无绑定,那么会以exn:fail:syntax异常报错。如果#%top存在绑定,那么会以#%top的绑定继续解析过程。
  • 如果语法对象对子的第一个元素是标识符且绑定于非顶层变量,那么后续解析会使用此绑定。
  • 对子是上述之外的语法对象之外的情况,会以对子的文法信息插入符号名#%app。插入的语法对象会具有implicit-made-explicit properties信息。如果插入的#%app没有绑定信息,那么会以exn:fail:syntax异常报错。否则会以#%app的绑定来继续解析过程。
  • 如果是其他语法对象,则会以同等文法信息插入符号名'#%datum。插入的语法对象会具有implicit-made-explicit properties信息。如果插入的#%datum没有绑定信息,那么会以exn:fail:syntax异常报错。否则,会以#%datum的绑定继续解析。

解读:首先对标识符和对子结进行区分。对于标识符,如果未绑定,则交给#%top处理。对于对子结,排除层顶绑定之后看是否绑定,如果非绑定则交给#%app处理。剩下其他情况交给#%datum处理。

implicit-made-explicit包含额外的信息,比如syntax-original?

标识符的绑定有几种:

  • 转换器,用于宏展开。返回的结果是语法对象,而且会被重新解析。展开的时候会对current-namespace进行参数化,确保他们处于合适的阶段。但是如果基本阶段在值上如果比目标阶段大一个值得时候,不会进行参数化。
  • 变量绑定,比如通过define或者let引入的。
  • 核心语法形式,可能有一些特定规则。
1.2.3.3 Expansion Context

每次展开都是在特定的上下文环境中进行的。核心语法形式以及宏转换器在不同的上下文会展示出不行的行为。比如说,module语法形式只在顶层上下文中是有效的,在其他上下文中无效。

有以下几种上下文:

  • 顶层上下文
  • 模块首级上下文
  • 模块上下文
  • 内部定义上下文,内嵌于其他上下文中,可同时允许定义式和表达式
  • 表达式上下文,内嵌于其他上下文中,只允许表达式

不同的核心语法形式以不同的上下文来解析子形式。例如,一个let形式在解析右边值得时候始终使用表达式上下文,而解析躯体部分的时候则使用内部定义上下文。

1.2.3.4 Introducing Bindings
  • 在顶层以及模块级别的require形式,可以在当前的作用域集合中导入新的。如果没有特别指定,绑定会在原模块定义的位阶导出。可以使用for-meta来修改导出位阶。for-label则是在标签位阶导入绑定。
  • 顶层或者模块级别的define, define-values, define-syntax, define-syntaxes,会在位阶0(也就是基础环境)为标识符添加新的绑定。
  • 顶层或者模块级别的begin-for-syntax可以在位阶1(也就是变换环境)中为标识符添加绑定。叠加多个begin-for-syntax可以添加绑定的位阶。
  • let-values形式会开始一个新的作用域。这个作用域会添加到标识符的作用域集合。所以形式中的标识符和完全展开的形态下的同一标识符bound-identifier=?成立。新的绑定和let-values具有相同的位阶。
  • letrec-values以及letrec-syntaxes+values和let-values类似,不过新的作用域也会拓展到右手边的表达式。
  • 内部定义上下文会为其中的标识符创建新的作用域。
1.2.3.5 Transformer Bindings

如果绑定是一个转换器(使用define-synatxes定义),那么绑定的值存在于展开的时候,而不是运行的时候,即便这个绑定本身时在位阶0定义的。

此时,绑定的值是通过对绑定对应的形式进行求值决定的。而为了求值,必须先对形式进行展开。展开时候的位阶是1。如果展开后获取的值是单参过程,或者是make-set!-transformer的结果,那么会被用作是一个语法转换器。

在展开过程把语法对象传给转换器之前,语法对象被置于一个新的宏作用域(应用于所有子语法对象)以区别宏的定义处和使用处的语法对象。转换器运行结束后,作用域会被重置。但是如果转换器的使用和绑定的定义在同一个定义上下文,那么使用处的语法对象会加一层新的使用处作用域,在转换器运行结束时不会重置。

make-set!-transformer以及prop:set!-transformer允许赋值型的转换器。

make-rename-transformer以及prop:rename-transformer生成重命名型的转换器。

展开器可以通过诸如’origin的语法属性来对展开历史进行跟踪。另外展开器还使用操弄状态来控制未导出或者受保护的模块绑定。

展开器对letrec-syntaxes+values的处理和define-syntaxes类似,都可以达到n+1位阶。begin-for-syntax和define-syntaxes有点类似,不过前者中定义的绑定在1位阶而不是0位阶。

1.2.3.6 Local Binding Context

即便一个标识符的绑定可以从其文法信息以及全局绑定表中推导而来,展开器依然维持一个本地的绑定上下文用以记录局部绑定。

非局部上下文的标识符通常无法引用一个局部绑定。但是宏可以使用编译时期的状态来暂存绑定的标识符,或者使用local-expand来提供标识符。

局部绑定上下文同样跟宋局部的转换器绑定(也就是由let-syntax生成的绑定)

1.2.3.7 Partial Expansion

特定上下文,比如内部定义上下文以及模块上下文,通过局部展开可以决定形式是否是定义,表达式还是其他声明形式。

1.2.3.8 Internal Definitions

内部定义上下文允许混合局部定义和表达式。局部定义其实相当于通过letrec-syntaxes+values生成的绑定。

部分展开伊始,内部定义上下文会引入一个外沿作用域。此外还会产生一个内沿作用域。

1.2.3.9 Module Expansion, Phases, and Visits

模块的展开和内部定义的展开类似。都有外沿和内沿作用域。

require形式不仅在展开时导入绑定,而且访问受引用的模块。也就是说,展开器会实例化在begin-for-syntax中定义的任意变量,并且会运算define-syntaxes转换器的绑定。

受require的模块被访问时的效果和模块实例化是一致的。

编译过程中,模块顶层上下文会被访问到。因此,当展开器遇到(require (for-syntax ...))的时候,会立马在位阶1实例化其绑定。同样地,展开器会立马执行遇到的任何begin-for-syntax。

0以外的位阶按需访问。在哪一级位阶展开就在哪一级对模块进行访问。

1.2.3.10 Macro-Introduced Bindings

对于一个顶层的定义,如果标识符在定义前使用,那么只在当前绑定条件下进行求解。为了让标识符能够在定义前使用,define-syntaxes形式会避免绑定一个标识符,如果define-syntaxes的声明没有产生结果。

宏生成的require和provide子句也会引入并引用特定生成的绑定,造成和定义相关的效果。

1.2.4 Compilation

扩展之后的代码在运算之前会经历一个编译阶段。编译阶段会丢失一些信息。与此同时,好处是编译后的代码可以序列化保存,然后可以重新加载。

虽然读取,展开,编译,运算这些操作可以单独进行。但他们通常是合并执行的。比如eval会获取syntax object然后对其进行展开,编译并执行。

1.2.5 Namespaces

名字空间即使解析的起始点,也是运行编译代码的起始点。名字空间带有模块注册表,可以将模块名字映射到模块声明。这个注册表在所有位阶皆可访问,作用域代码的解析和编译过程。

作为解析起始点,名字空间为每个位阶提供一个作用域,且提供一个所有位阶皆可访问的作用域。namespace-require创建初始绑定,后续的展开和运行创建额外的绑定。名字空间内对一个形式进行运算,会将名字空间内对应位阶的作用域赋予形式本身以及形式的展开结果。所以每个绑定了的标识符至少有一个作用域。名字空间内的全位阶作用域只在特定情况下被使用(比如使用eval而不是eval-syntax)。除了模块生成的名字空间(module->namespace),只有单一的全位阶名字空间,以及各异的位阶特定的作用域。

作为运算的起始点,每个名字空间除了为不同的位阶封装不用的顶层变量,还为每个位阶维护潜在的的模块实例。也就是说,虽然模块声明在各位阶可见,但是模块实例在各个位阶却是隔离开来的。每个名字空间都有一个基本位阶,eval或者dynamic-require都执行在此位阶下。也就是说使用eval来运行一个require形式会在当前名字空间的基本位阶实例化对应的模块。

名字空间创建后,既有名字空间内的模块实例会被附着到新的名字空间。从运算模型的角度,来自不同名字空间的顶层变量的定义会以不同的前缀区分。但是附着模块的时候会采用和目标名字空间相同的前缀。运算编译后的表达式所需的第一步是把对顶层变量以及模块级别的变量的引用放置到当前的名字空间内。

运算过程中,始终有一个名字空间会被当做当前的名字空间。改变此名字空间不会影响被运算的表达式所引用的变量,只是会影响用于代码展开以及随后的运行所涉及的反射性操作的行为。

如果一个标识符被绑定到一个语法或者一个导出,那么将此标识符定义成变量会这笔此语法或者此导出。反之亦然,如果一个标识符被绑定到一个顶层变量,那么绑定标识符到语法或者导出会遮蔽变量。

跟名字空间的情况类似,每个模块会有一个跨各个位阶的作用域,以及针对每个位阶的特定作用域。后者会被添加到每个形式,不管是代码中的还是通过局部宏展开出现的。模块的作用域们可以通过module->namespace合成到一个名字空间。与此同时,解析模块会从删除所有外围的顶层或者模块(module或者module*)的作用域们开始。

1.2.6 Inferred Value Names

为了帮助错误报告,编译期间会对某些值的名字进行推断,比如对于执行诀的名字的推断会用于施行时参数错误报告中。

使用procedure-rename可以遮盖一个执行诀的推断名。

只要可以,就会将执行诀的名字推断出来。越靠近表达式的名字优先级越高。下面的例子中,执行诀推断名为。

(define my-f
  (let ([f (lambda () 0)]) f))

如果’inferred-name被附着到语法对象,那么会被用于命名对应的表达式,并且会遮盖从表达式上下文推断出的名字。 如果’inferred-name设置为#<void>,则会隐藏从上下文推断出的名字。

为了支持属性一致性的传播和合并,‘inferred-name属性可以是cons生成的树,并且其所有的叶子都相同,比如(cons 'name 'name)等同于’name,以及(cons (void) (void))等同于#

如果推断名不可得,但是源坐标可得时,名字会从源坐标信息中生成。推断名和辖属分配名对语法转换器可得,看syntax-local-name。

1.2.7 Cross-Phase Persistent Module Declarations

一个模块在满足下面语法的情况下,可以跨位阶存续。这个模块使用从完全展开程序的非端节点,如果它包含#declare #:cross-phase-persisten,并且不适用quote-syntax或者#%variable-reference,并且模块级别绑定没有被set!

本语法应用与展开之后,但是跨位阶存续模块只从其他跨位阶存续模块导入符号。唯一相关的展开步骤只有隐式引入#%plain-module-begin,隐式引入#%plain-app,隐式导入#%datum

Beau­tiful Racket

Beau­tiful Racket / explainers / Identifiers

一个变量的含义由其绑定的所决定。一个变量可以绑定一个特定值,一个函数,一个宏,甚至另一个标识符。已绑标识符也叫做变量。

这些字符( ) [ ] { } " , ' ; # | \`不能用来命名标识符。

标识符绑定可以通过下列方式生成

  • 通过define,let或者lambda创建
  • 导入其他模块创建的标识符
  • 宏展开的时候增加额外的标识符

每个标识符都关联着作用域。常见的作用域情形:

  • 表达式作用域,绑定在表达式中创建
  • 模块作用域,在模块顶层创建的,可以导入其他模块
  • 宏作用域,不同展开阶段时定义的变量不可混用

Beau­tiful Racket / explainers / Hygiene

Hygiene是Racket宏的组织策略,对应的问题是:此处定义的宏在别处展开的时候,如何处理标识符的绑定。

本身上有两种选择:

  • 根据宏定义的时候的文法信息来处理绑定
  • 根据宏展开的时候的文法信息来处理绑定

第二个选择容易带来意想不到的后果,所以racket采用了第一种选择,这样定义宏的时候就不怎么需要考虑其使用环境。

四条黄金规则:

  • 定义宏的时候,尽量使用本地的文法信息
  • 宏展开的时候定义的绑定会遮蔽原有信息
  • 宏展开时候定义的绑定只在该宏中可见
  • 每个标识符会保留原有的文法信息

由于有这些限制在,所以想破坏Hygiene,只能从外部传入标识符这个办法了。

(本篇完)

Categories

Tags