Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

02 May 2021

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

The Racket Reference 阅读笔记。

1 Language Model

1.1 Evaluation Model

Racket的求值运算(evaluation,简称求值,或者运算)可以看作是对运算表达式(简称表达式)进行精简,以获取其结果(姑且把运算的结果叫做量值value)。

(+ 1 1) → 2

1.1.1 Sub-expression Evaluation and Continuations

精简表达式的过程需要分步进行,例如:

(- 4 (+ 1 1)) → (- 4 2) → 2

如果我们把量值当作表达式的最精简形式,那么意味着非量值的表达式可以被继续精简。为了确定下一步可精简的部分,可以把表达式分为两部分,redex(reducible expression,姑且翻译为首发式)以及continuation(姑且翻译为待发式)。上面例子中(- 4 (+ 1 1))的首发式是(+ 1 1),待发式是(- 4 [])。对首发式进行求值运算,将获得的结果装入待发式,即对表达式进行乐一步精简。表达式的动态范围(dynmaic extent)是指其精简过程中含有首发式的一众步骤。

1.1.2 Tail Position

如果表达式expr1和expr2的待发式相同,但是expr1是expr2的首发式,那么可以说expr1处于尾随expr2的姿态。例如 (if (zero? 0) (+ 1 1) 3)中的(+ 1 1)处于尾随姿态,因为:

C[(if (zero? 0) (+ 1 1) 3)] → C[(if #t (+ 1 1) 3)] → C[(+ 1 1)]

1.1.3 Multiple Return Values

从前面的描述可以观察到,待发式需要靠量值的输入来推动其继续精简。大部分待发式只需要单个量值来推动,可是有些待发式需要多个量值推动:

  • (+ [] 1),需要一个量值
  • (let-values ([(x y) []]) expr),需要两个量值
  • (begin [] (+ 1 2)),可以接受任意数目的量值,因为begin会忽略这些量值

1.1.4 Top-Level Variables

给定x = 10,则有x + 1 = 10 + 1 = 11

此处x可以看成是一个变量(variable),是在运算过程中可以替换,从而变成量值的标识符(类似于代数上的x, y, z)。

Top-Level Variable即顶层变量,即在代码顶层定义的变量。下面的define构造定义了一个顶层变量x:

(define x 10)

define构造将左手边的标识符绑定到右手边的表达式运算得出的量值。左手边的标识符处于定义上下文,而不是运算上下文,所以不会被当作一个变量,而只是当作一个单纯的标识符。在运算上下文中,标识符会被赋予具体的含义,要么被当作一个变量,要么被当作一个阔集(macro),等等。

在运算过程中,Racket会维护一张定义表,用于记录已定义的变量。随着运算过程中不断加入新的变量定义,定义表会随之扩展。

set!可以用来变更顶层变量所对应的量值。

1.1.5 Objects and Imperative Update

除了set!之外,像vector-set!等操作也能对复合数据结构中的元素进行修改。为了解释这些个修改,需要对量值进行深入剖析。量值表示的是表达式的运算结果,但量值又是由什么来表示的呢?这里要引入一个概念,叫做标的(object)。标的持有的是被量值引用的数据。

少数标的可以直接当作量值使用,比如布尔型,(void),还有小整型数。(因为这些标的的数据量很小,不需要通过引用跳转,而是可以直接嵌套到引用中)。大部分的量值都是通过引用来关联标的的。多个量值可以关联到同一标的,这个标的内容变更会对所有引用它的量值可见。所以大部分类型的量值都是标的引用。

运算过程中,也会有一张表用来记录现有的标的。也会有新创建的标的加入到这个表中。

回到顶层变量的话题,顶层变量本身不是量值,必须对顶层变量进行运算才能确定其量值。运算的时候意味着从定义表中找到顶层变量标识符对应的量值。而对标的的引用则可以被看作一个量值,因此不需要通过运算来确定。

标的引用无法直接以文本的形式在源代码中出现。但是可以通过datum->syntax等方式创建。

1.1.6 Garbage Collection

没有被引用的标的会被当作垃圾回收。

上面这句话不完全正确。值得注意的是,一些复合数据类型中使用了弱性引用来指向标的。如果一个标的只有弱性引用,那么也会被当作垃圾回收。弱性引用则被替换成了#f。

其他的特例,fixnum不会被当作垃圾回收;Latin1字符集范围内的字符也不会被回收,它们的equal?和eq?返回相同的值,所有的Latin1字符都被内部模块引用。像null, #t, #f eof, 以及#<void>也是不会被回收的。quote产生的量值在quote表达式还存在式便不会被回收。

1.1.7 Procedure Applications and Local Variables

给定f(x) = x + 10,则有f(7) = 7 + 10 = 17

执行诀在使用上跟变量大体类似,但有一点不同,就是执行诀的参量需要额外处理。应用执行诀的时候,传入的参量会被对应到新的落点(location),执行诀正文内的使用的参量会被替换成从对应的落点。因此,执行诀内部对参量的修改不会对传入的参量造成影响。参量传入执行诀时,就在执行诀内部产生的局部变量。

如果传入执行诀的是表达式,那么要先对这个表达式运算,然后将所得的量值作为参量传入。也就是说,Racket是传值型的语言。

(let ([x (+ 1 2)]) expr)这些构造,其原理跟应用执行诀的原理一致。

1.1.8 Variables and Locations

变量是量值的替代,初始程序中的表达式会指向变量。顶层变量既是变量又是落点。其他变量则必须在运行的时候被替换成落点;表达式运算的时候其实只关心落点。单个局部变量(非顶层变量,非模块变量),可以在不同的应用过程中,可以应对不同的落点。

将落点从量值区分开来,正好实现了Racket的文法作用域(lexical scoping)。

(未完待续)

2021-05-07更新

1.1.9 Modules and Module-Level Variables

Racket中可以按照模块来组织代码。在模块内部也可以有顶层的变量,称为独部级别的变量(部级变量)。从运算的角度,这些变量和顶层级别的变量(顶级变量)类似,不过这些变量会以模块为前缀,所以看起来是属于某个独部的。

不过有一点差别就是,顶级变量在定义的时候就例现化了,而部级变量未必。因为独部需要通过require来例现化,在未例现化之前,独部变量不会例现化。

1.1.9.1 Phases

位阶是用来区分执行阶段和展开阶段的名字定义。

一个独部可以在不同位阶例现化。这些个位阶被表示成整数。位阶中定义的变量也会以位阶未前缀,所起看起来也是属于某个位阶的。

独部有一个基本位阶,通常为0。顶层的require可以在指定的位阶导入其他独部。比如使用(require (for-syantx ...))在升一位阶导入目标独部。使用(require (for-template ...))在降一位阶导入目标独部。

独部内部也可以在不同的位阶定义变量,比如可以使用begin-for-syntax来让位阶升一。

被求访(require)的独部,求访所在的位阶会称为该独部的基本位阶。求访位阶不同的独部彼此隔绝。

顶级变量也可以在不同的位阶存在。begin-for-syntax下的define处于升一位阶。像make-base-namespace以及eval这些探视性(reflective)操作可以提供到高位阶的顶级变量的访问,只要它们所在的独部是在高位阶例现化的。

1.1.9.2 The Separate Compilation Guarantee

当一个独部受编译时,其升一位阶会随之例现化,随之而来的其他位阶上的独部也会例现化。拔出萝卜带出泥,一个独部的例现化会连锁例现化一堆其他独部。这些独部可以像根系一样庞杂,但一个基本的规则:独部之间不能存在循环引用。

此外Racket提供一个保证,叫做:“The Separate Compilation Guarantee”:

升一位阶的独部例现化在Racket运行系统上的效果会被抛弃。

如果一个独部被求访多次,只有在第一次的时候会例现化,但是有这个保证在,每次求访看到的这个独部的现例都是一致的,因为例现化产生的效果是被抛弃了的。这样,一个独部的求访顺序也就变得无所谓了。

但是也不尽然。效果如果是在Racket运行系统上的,则是内部效果,可以被抛弃;但是效果如果在外部,比如写入共享内存或者外部磁盘,那么效果就可以被外界观察到, 抛弃了也没用。总的来说,抛弃的大都是对变量的变更而已。

Racket中的thread虽然看起来具有外部性,但其实现并没有依赖于操作系统的线程,所以产生的效果还是内部的。

文中给出了一个具体的例子说明内部性效果是如何被丢弃的。

更多参考:

  • “Composable and Compilable Macros” [Flatt02][http://www.cs.utah.edu/plt/publications/gpce13-f-color.pdf]
  • “Advanced Macrology and the implementation of Typed Scheme” [Culpepper07][https://www2.ccs.neu.edu/racket/pubs/scheme2007-ctf.pdf]
1.1.9.3 Cross-Phase Persistent Modules

跨位阶的独部也是存在的,比如:

> (module cross '#%kernel
    (#%declare #:cross-phase-persistent)
    (#%provide x)
    (define-values (x) (gensym)))

跨位阶的独部声明中必须包含(#%declare #:cross-phase-persistent)。跨位阶的独部依然需要在不同的位阶例现化。但是第一次例现化所产生的定义,在后续的例现中都可见。

下面的:

> (define (same-instence? mod)
    (namespace-require mod)
    (define a
      (parameterize ([current-namespace (make-base-namespace)])
        (namespace-attach-module-declaration ns mod)
        (namespace-require mod)
        (namespace-variable-value 'x)))
    (define b
      (parameterize ([current-namespace (make-base-namespace)])
        (namespace-attach-module-declaration ns mod)
        (namespace-require mod)
        (namespace-variable-value 'x)))
    (eq? a b))

> (same-instence? ''cross)
#t

一个使用案例是让语句错误exn:fail:syntax在各位阶可见。

跨位阶的独部有一些使用上的限制:

  • 只能导入其他跨位阶的独部
  • 只能下面这些类型的变量定义
    • 对应函数的变量
    • 对应结构类型,或者相关函数的变量
    • 对应结构类型辖属,或者相关函数的变量
  • 不能包含语句字面体(经由quote-syntax产生的)
  • 不能包含变量引用 (经由#%variable-reference产生)

默认情况下谈到的独部均非跨位阶。

1.1.9.4 Module Redeclarations

独部是可以重定义的。

为了避免麻烦,还是不要这么做吧,这节不看了

1.1.9.5 Submodules

使用module或者module*可以创建无限制嵌套的下级独部。下级独部相对独立,即便和上级独部在同一文法单元中,也需要单独求访。

但是嵌套的独部也要遵循无循环引用的规则,可能也是因为这一点,所以有以下规则:

  • module定义的下级独部不能求访外围的上级独部,但是可以被后者求访
  • 与之相反,module*定义的下级独部可以求访外围的上级独部,但是不可以被后者求访。以(module* name #f ...)形式(name后面为#f)定义的独部,自动可以求访外围独部,并且可以披露外围独部的捆束项。

(更新完)

2021-05-08更新

1.1.10 Continuation Frames and Marks

如果将单个续发式继续细化,可以得到一系列续发式帧元。这些帧元是最小化的不可再细分的续发式。运算过程中会对这些帧元进行增增减减,但通常每次操作一个帧元。

每个帧元都标注着一个续发记号的集合。每个记号由一堆键值构成。其键可以是任意值,只能对应一个续发记号。有许多操作会设置或者抽除续发记号。也就是说通过记号可以将额外的信息附着于动态范畴。

一个例子,记号可以在异常抛出时用于添加栈回溯信息,或者用于实现动态作用域。

1.1.11 Prompts, Delimited Continuations, and Barriers

一个闪现(prompt)是特殊类别的续发式帧元,带有闪现标签。许多操作允许捕获从首发位置到闪现之间的那些帧元。此类续发式有时叫做有界续发式(delimited continuation)。其他一些操作允许用捕获的续发式(composable continuation)来扩展将当前的续发式。还有其他一些操作允许中断当前运算并退回最近的闪现。当一个有界续发式被捕获时,其关系的闪现也会被捕获。

续发式屏障也是一众特殊的续发式帧元,用以组织特定的续发式替换行为。只有在替换没有引入屏障的时候,才能成功。屏障可以用于组织续发式向下跳转。有一些操作会安装屏障,比如异常处理器被调用时,会安置一个屏障以组织捕获续发式在异常点之前的部分。

一个逃逸续发式是一个衍生的概念。它包含了一个闪现用于逃逸。

(更新完)

2021-05-11更新

1.1.12 Threads

Racket支持并发运行的多线绪运算(也是以thread表示)。不同的线绪之间可以互相抢占(不需要被抢占方的协作)。但是这些线绪并不能并行运行,因为这些线绪运行在同一处理器上(即单个操作系统进程内的单个线程)。

通过thread可以创建一条线绪。就运算模型而言,一步运算可能涉及多个并发的表达式(不同的线绪只能贡献一个表达式)。这些表达式共享相同的标的以及顶级变量。也就是说,线绪间可以通过状态共享的方式来通信,并且他们的运行序列一致性会得到保证[Lamport79]。虽说如此,大部分运算步骤只涉及某线绪的一个表达式;特定的同步原语才需要多个线绪共同参与(例如在channel传递一个量值)。

若非特别指出,常量时间的执行决和运算操作具有原子性,所以是线绪安全的。例如,使用set!更改一个变量的时候在所有运算线绪看来是一个原子动作。但是注意,set!更改变量之前可能需要对将设的值进行求值操作,这个操作可能不具有原子性。

有些操作不是原子性的,比如hash-set!,它操作的过程中需要上锁;端口操作也大都不是原子的,但是他们是线绪安全的,因为给被线绪一读取的字节不会被线绪二读取。此外port-commit-peeked以及write-bytes-avail提供额外的并发保证。

除了共享的状态,每条线绪也可以有私有状态,只能通过线绪进行访问,使用线绪格牢表示。在创建新线绪的时候可以留用老线绪中的格牢。

待归(Futures)和场站(places)用来表示不同的并发和并行机制,它们对共享状态的保证较弱。场站可以通过make-shared-bytes来共享数据。待归和场站中的运算受一致性约束,因为其他待归和场站可能会访问所属数据。对共享状态的读与写最终发生在虚拟内存级别,在此级别的读写操作有同步性约束,但是此级别及以下的操作不受racket的一致性约束,除非在代码层面显示指明约束。

[Lamport79]: https://www.microsoft.com/en-us/research/uploads/prod/2016/12/How-to-Make-a-Multiprocessor-Computer-That-Correctly-Executes-Multiprocess-Programs.pdf

1.1.13 Parameters

动参(活动参数,Parameters)是一个衍生的概念。它们是按照续发式记号以及线绪格牢定义的。有一些原语执行决也内驻对动态的使用,比如默认的输出流可以通过东参来修改。

动参是针对特定线绪和特定续发式的设定。在空续发式中,每个动参对应一个受留用的线绪格牢。

对于非空续发式,动参的量值根据动态定值(parameterization)来确定。动参定值在最近的外层续发式帧元上添加一个续发式记号。动参定值会将该动参映射到一个可留用的线绪格牢。一个动参执行决可以变更或者访问相应的格牢。

若干操作,比如parameterize或者call-with-parameterization可以安插一个动参定值记号到续发式帧元。

1.1.14 Exceptions

异常也是一个衍生的概念,定义于续发式,即刻,以及续发式记号之上。此外,异常也是“内驻”的,许多初始构造和执行决也会产生异常。

续发式记号上可以关联异常处理器,用于捕获异常。当异常发生时,会根据当前的续发式记号来确定一系列相关的异常处理器,看哪个能处理此异常。对于未处理的异常,会由一个内驻的动参处理。

异常处理器可以潜在的行为是退出当前续发式,并回溯到外围即刻。默认的异常处理器会回溯的线绪的默认即刻。

1.1.15 Custodians

一个监理管理着一众线绪,文件流端口,TCP端口,TCP侦听器,UDP套接字,字节转化器,以及场站。当一个线绪被创建时,会为其指派由current-custodian动参对应的监理。

除了总监理以外,其他的监理都被另一个监理所管理者。所以监理的体系成层级状。每个下级监理所负责的标的同时也可以看作受本级监理负责。

通过custodian-shutdown-all来关闭一个监理时,其所负责的资源都会被释放,相关线绪会挂起。被关闭的监理无法用于管理新标的,否则会抛出异常exn:fail:contract。

一个线绪可以归多个监理负责,通过thread/suspend-to-kill挂起的线绪则不可以有监理。额外的监理可以通过thread-resume来添加。关联有多个监理的线绪的资源不会随某个监理的custodian-shutdown-all而释放,需要所有监理皆关闭才会释放。

监理对其管辖的资源具有弱引用。受监管的值可以执行遗嘱。同样,一个监理对下级监理采用的也是弱引用。被释放的监理如果有下级监理,那么这些下级监理会变成本级监理的上级监理的直属下级。

通过make-custodian-box所创建的监理盒子可以含有到一个值的强引用。但是监理盒子本身是被弱引用的。

Racket支持监理级别的内存审计(参考custodian-memory-accounting-available?),current-memory-use可以汇报当前监理负责的所有标的。如果一个标的归两个监理负责,那么其划归是任意的,而且动态变化的。但是如果这两个监理有上下级关系,那么会划归到上级监理,除非上级监理只能通过下级监理访问该资源。监理的内存审计不会计入弱引用,或者其他监理所负责的线绪,或者其他监理,或者其他监理的监理盒子。

(更新完)

Categories