本页使用了标题或全文手工转换

Scheme

维基百科,自由的百科全书
跳到导航 跳到搜索

Scheme
Lambda lc.svg
编程范型多范型函数式, 指令式, 元编程
语言家族Lisp
設計者小蓋伊·史提爾傑拉德·傑伊·薩斯曼
发行时间1975年,​47年前​(1975
穩定版本
R7RS-small[1]
(2013年7月6日,​9年前​(2013-07-06[2]
型態系統强类型动态类型
作用域词法
文件扩展名.scm   .ss
網站www.scheme-reports.org 編輯維基數據鏈接
主要實作產品
Bigloo英语Bigloo, BONES[3], Chez, Chibi[4], Chicken, Cyclone[5], Foment[6], Gambit, Gauche英语Gauche (Scheme implementation), Guile, IronScheme英语IronScheme, Kawa英语Kawa (Scheme implementation), Larceny英语Larceny (Scheme implementation), Loko[7], MIT/GNU Scheme, Mosh[8], Picrin[9], Rapid[10], s7[11], S9fES[12], Sagittarius[13], Scheme 48, SCM, STklos英语STklos, TinyScheme
衍生副語言
femtolisp[14], Husk[15], Racket, SIOD, Swift LispKit[16], T英语T (programming language)
啟發語言
ALGOL, Lisp, MDL英语MDL (programming language)
影響語言
Clojure, Common Lisp, Dylan, EuLisp英语EuLisp, Haskell, Hop英语Hop (software), ISLISP, JavaScript, Julia, Lua, R, Racket, Ruby, Rust, S, Scala

Scheme是一种函数式编程语言,是Lisp的两种主要方言之一,不同于与之并列的Common Lisp,Scheme遵循極簡主義英语Minimalism (computing)哲学,以一个小型语言核心作为标准,加上各种强力语言工具(语法糖)来扩展语言本身[17]。Scheme是第一個使用靜態作用域的Lisp方言,也是第一个引入头等续体和“干净宏”的编程语言。

简介[编辑]

在1975年,麻省理工學院傑拉德·傑伊·薩斯曼蓋伊·史提爾二世,開發出了Scheme語言最初版本,隨後兩人通過發表「λ論文集」而不斷對它進行完善和推廣。Scheme與λ演算關係十分密切,故將小寫字母「λ」用作標誌

麻省理工學院與其他一些院校,曾采用Scheme教授计算机科学入門課程。著名的入門教材《计算机程序的构造和解释》(SICP),利用Scheme來詮釋程序設計[18]。Scheme有眾多實現可視為一個主要優勢[19],然而不同實現之間的差異成為了它的一個劣勢,Scheme掌控委员会声称,它是“世上最不可移植的编程语言”,并且是一个“编程语言家族”而非一个单一的语言[20]

歷史[编辑]

起源[编辑]

Scheme起源於1958年由約翰·麥卡錫提出的Lisp語言。麥卡錫通過Lisp證明了,經由幾個簡單的算子,與用作匿名函數的借鑒自阿隆佐·邱奇的λ表示法[21],就可以構建出圖靈完備的系統。麥卡錫提出的S-表达式,可以将程序与数据用相同的结构存储,这被称为同像性。Scheme的語法即來自S-表达式,這一特性使得在Scheme中實現自循環直譯器變得非常簡單[22]

在1973年,麻省理工學院Carl Hewitt英语Carl Hewitt提出的一種叫做演員模型計算模型[23],并用Lisp开发当时叫做Planner英语Planner (programming language)-73的新语言来实现它[24]。傑拉德·薩斯曼與蓋伊·史提爾为了理解演员模型,決定在Maclisp工作环境中實現一個微型Lisp解释器,并接着增加创建演员和发送消息的机制[25]。兩人很快發現了演員模型與λ演算之間的相似性,所謂「演員」就是彼得·兰丁提出的閉包[26],而Joel Moses英语Joel Moses在1970年已将它介入Lisp用来解决函数参数问题英语funarg problem[27];實現演員的關鍵,是將詞法作用域介入到Lisp中[28]

在1975年,基於对λ演算表达能力的理解[29],傑拉德·薩斯曼與蓋伊·史提爾開發出了新型Lisp解释器[30],并将在其上完成的微缩版的演员实现命名為「Schemer」,後因ITS英语Incompatible Timesharing System作業系統文件名的字符數限制而改為Scheme[31]。儘管Hewitt指出了Scheme不能表达特定类型的原语演员[32],Scheme解释器本身采用的簡約的語法和语义,很快贏得廣泛接受。

在1978年,蓋伊·史提爾二世傑拉德·傑伊·薩斯曼发表了《修订的Scheme报告:一种LISP方言》[33],从而完善了Scheme的功能,并正式将其确立为Lisp的一种主要方言。在1998年,二人在总结Scheme历史时指出,簡單而強大的λ演算,使得Scheme最終得以實現極度的精簡化[34]

λ論文集[编辑]

「λ論文集」是傑拉德·薩斯曼與蓋伊·史提爾撰寫的關於Scheme的一系列論文,最早作為麻省理工學院的內部備忘錄發表[35]。通常認定λ論文集包括:

  • 1975年: Scheme: An Interpreter for Extended Lambda Calculus.[36]
  • 1976年: Lambda: The Ultimate Imperative.[37]
  • 1976年: Lambda: The Ultimate Declarative.[38]
  • 1977年: Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO.[39]
  • 1978年: The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two).[40]
  • 1978年: RABBIT: A Compiler for SCHEME.[41]
  • 1979年: Design of LISP-based Processors, or SCHEME: A Dialect of LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode.[42]
  • 1980年: Compiler Optimization Based on Viewing LAMBDA as RENAME + GOTO. AI: An MIT Perspective.
  • 1980年: Design of a Lisp-based Processor. CACM. 23. 11.[43]

標準化[编辑]

Scheme的業界標準,是由專門的掌控委員會發表的《第n次修訂的演算法語言Scheme報告》(Revisedn Report on the Algorithmic Language Scheme),这种标题形式参照了ALGOL 60标准文档的标题[44]。Scheme曾經由IEEE標準化為IEEE 1178–1990,它于2019年11月07日停用[45]

1998年通过的R5RS是現在被普遍接受的標準[46]。2007年通過的R6RS[47],做出了很大的變動[48],Scheme社區中有使用者指責它在堆積華而不實的功能[49][50]。Scheme掌控委員會決定在R7RS中,將Scheme分化為兩個獨立而兼容的語言[51]:一個是2013年通過的R7RS-small[52],它為教學場合提供对IEEE/R5RS標準的及时更新,R7RS-small目前已经有了一些实现支持[53];而另一個是作为标准合集的R7RS-Large[54],它包含了各种提议被接纳并进入冻结状态的Scheme实现要求英语Scheme Requests for Implementation(SRFI),以此為實際編程場合提供对R6RS標準的继续完善,Larceny英语Larceny (Scheme implementation)和Chibi[4]提供了R7RS-Large过渡草案红色版(即数据结构部份)的全部SRFI的实现。

命名法[编辑]

在正式场合比如Scheme标准的命名法英语Nomenclature中,提及一个λ表达式或原始过程时,偏好使用词语“过程”而非“函数”。在一般使用中,词语“过程”和“函数”是可互换使用的。过程应用有时被正式称呼为“组合”(combination)。

同其他Lisp一样,在Scheme中使用术语“thunk英语thunk”,来提及没有实际参数的过程。术语“适当”(proper)尾递归,称谓所有Scheme实现的一个性质,它们都进行尾递归优化,从而支持无限数目的活跃尾递归

基础特征[编辑]

Scheme大体上是一個函數式程式語言,並支援其他编程范型。它同其他Lisp编程语言家族语言共享了很多特征。它的非常简单的語法基於LispS-表达式:即圆括号包围的列表,其中的前缀是算符,而随后那些的是实际参数。故而Scheme程序由嵌套的列表的序列构成。列表也是Scheme中的主要数据结构,这导致了在源代码和数据格式之间的紧密等价性,即同像性。Scheme程序可以轻易的动态建立和求值Scheme代码片段。

Scheme與其他Lisp方言的列表,都是基於最基礎的數據結構有序對(pair)。Scheme从它的Lisp先辈继承了一组丰富的列表处理原始运算,比如conscar英语CAR and CDRcdr英语CAR and CDR。Scheme的變數都使用動態強型別系統,Scheme中的过程都是頭等物件,即头等函数,因此过程可以作为值赋值给变量,或作为实际参数传递给过程。

本章主要集中于语言的创新特征,它们使得Scheme区别于其他Lisp方言。除非专门指出,这里描述的特征都有关于R5RS标准。在本章例子中使用“===> 结果”表示法,来指示求值在紧前行上的表达式的结果。这同于R5RS中使用的约定。本章节描述的特征使得Scheme不同于在它之前的其他编程语言。Scheme的这些方面强烈的影响了Scheme语言的所有产品,并共通于始自1975年最初的λ论文,特别是自从R2RS以来[55],所有版本的Scheme编程语言。

極簡主義[编辑]

Scheme的簡約性,使它成為具備同級別功能的程式語言中最易於實現的語言,这得益于使用λ演算来从更原始的形式导出多数的语言语法[56]。例如在R5RS标准中,定义了23个基于S-表达式的语法构造,其中14个被归类为派生形式或库形式,它们可以被写为涉及原则上为lambdad的更基础形式的宏。正如R5RS(§3.1)所说:“最基础的变量绑定构造是lambda表达式,因为所有其他的变量绑定构造,都可以依据lambda表达式来做出解释”[46]

基础形式definelambdaquoteifdefine-syntaxlet-syntaxletrec-syntaxsyntax-rulesset!
派生形式doletlet*letreccondcaseandorbegin、命名letdelayunquoteunquote-splicingquasiquote

下面是一个宏的例子,它将let实现为使用lambda来进行变量绑定的一个表达式:

(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))))

使用上述定义的let,一个Scheme实现可以将(let ((a 1)(b 2)) (+ b a)),重写为((lambda (a b) (+ b a)) 1 2),这将实现任务缩减为编码过程实例化的工作。

词法作用域[编辑]

像多数现代语言而不像更早期的Lisp比如Maclisp,Scheme是词法作用域的[57]:在一个程序单元中所有可能的变量绑定,都可以通过阅读这个程序单元来分析出来,而不需要考虑到它可能在其中被调用的那些上下文。这对比于动态作用域,它是早期Lisp方言的特征,因为在当时的编译器和解释器中,用来实现词法作用域算法的原始的文字替换方法,关联着处理代价。在那些Lisp中,对一个过程内的自由变量的引用,依赖于这个调用的上下文,完全有可能引用到这个过程外部的相当不同的绑定。

λ演算[编辑]

邱奇λ演算的数学表示法,启发了Lisp使用lambda作为介入一个过程的关键字,并影响了Lisp中涉及到使用高阶函数函数式编程技术的发展。但是早期的Lisp由于对自由变量的处理方式[58],而不适合表达λ演算[29]

一个正式的λ系统,拥有一些公理和一个完备的推理规则。这有助于使用数理逻辑和工具来进行分析。在这个系统中,演算可以被看作直接的演绎。λ演算的语法,来自用x, y, z, ...、圆括号、空格、点号和符号λ形成的递归表达式[59]。λ演算的功能包括:首先,充当强力的数理逻辑的起点。其次,它可以缩减编程者在考虑实现细节上的要求,因为它可以用于模拟机器求值。最后,λ演算建立了一个坚实的元理论[60]

在Scheme中,lambda關鍵字被用於定義匿名过程,并且使用define基础形式来定义命名过程,即将一个lambda过程绑定到指名的全局变量[61]。在Scheme中,(define (foo x) (+ x 1))(define foo (lambda (x) (+ x 1))) ,在語法上是等同的。例如有序對可以表示為[62]

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

這樣定義出來的conscarcdr,滿足恆等式(car (cons x y))等於x,和(cdr (cons x y))等於y。甚至递归也可以表示为利用λ演算的Y组合子[63]

词法作用域的介入[57],通过在某些形式的λ表示法,和在工作编程语言中它们的实际表达之间做出等价,解决了早期Lisp的有关问题。Sussman和Steele展示了,通过将λ表达式用作“控制结构和环境修改器”,而非简单的过程实例化,可以用这个新语言优雅的导出其他编程语言包括ALGOLFortran的,所有指令式和声明式语义,和其他Lisp的动态作用域[64]。他们在第一篇λ论文中,与对Scheme的首次描述一起,介入了续体传递风格英语continuation-passing style[65],并在后续的论文中,他们推进演示了在这种实际使用中体现出的λ演算的原生能力。

过程应用中的求值次序[编辑]

Scheme采用了传值调用,但不同于多数Lisp规定了过程实际参数的求值次序,Scheme不规定求值次序。对比于其他Lisp,Scheme表达式在算符位置(第一个项目)上可以是一个表达式,只要在算符位置上的表达式的结果是一个过程,这种表示就是完全合法的[66]

在Scheme中,在算符和实际参数位置上的这些表达式的求值次序,可以在逐个调用的基础上由实现来选择,而唯一的约束是:“运算符和运算数表达式的任何并发求值的效果,被约束为一致于某种顺序次序的求值。”(R5RS sec. 4.1.3)[46]

(let
  ((ev 
     (lambda(n)
       (display "Evaluating ")
       (display (if (procedure? n) "procedure" n))
       (newline) n)))
  ((ev +) (ev 1) (ev 2)))
===> 3

ev是一个过程,它描述传递给它的实际参数,接着返回这个实际参数的值。在调用过程+来加12之中,表达式(ev +)(ev 1)(ev 2)可以按任何次序求值,只要效果上它们不像是并行求值的。因此在上述例子被执行的时候,下列三行可以被标准Scheme按任何次序来显示,然而一行的文本不可以同另一行的文本产生交错,因为这会违反顺序求值约束。

Evaluating 1
Evaluating 2
Evaluating procedure

塊結構[编辑]

Scheme的代碼塊結構,不同于早先Lisp的語言構造[67]。自从R2RS开始[55],Scheme中的块,是通过三个“绑定构造”来实现的:let英语Let expressionlet*letrec。例如,下列构造建立一个,其中叫做var的符号被绑定到数10

(define var "goose")
;; 这里任何到var的引用都会被绑定到"goose"
(let ((var 10))
  ;; 语句走到这里时,任何到var的引用都会绑定到10
  )
;; 这里任何到var的引用都会绑定到"goose"

依据编程者的需要,块可以嵌套英语Nesting (computing)来建立任意复杂的块结构。使用块结构来建立局部绑定,减轻了不然可能发生的命名空间冲突英语Naming collision

let的变体之一let*,允许绑定引用在前面相同构造中定义的变量,例如:

(let* 
  ((var1 10)
   (var2 (+ var1 12)))
  ;; 但是var1的定义不可以引用var2
  )

let的另一个变体letrec,被设计用来确使互递归过程可绑定彼此。

下面的例子是侯世达雌雄序列英语Hofstadter sequence#Hofstadter Female and Male sequences

;; 将侯世达雌雄序列计算为有序对的列表
(hofstadter-male-female 8)
===> ((1 . 0) (1 . 0) (2 . 1) (2 . 2) (3 . 2) (3 . 3) (4 . 4) (5 . 4) (5 . 5))

在一个单一的letrec中的所有过程,可以通过名字引用其他的过程,还有在相同的letrec中此前定义的变量的值,但是它们不可以引用在相同的letrec中此后定义的变量的值。

let的变体“命名let”形式,在let关键字之后有一个标识符。它将这些let变量绑定到一个过程的实际参数,这个过程的名字由这个标识符给出,它的过程体是let形式的主体。这个过程体可以通过调用这个过程达成想要的重复。命名let被广泛用于实现迭代。

一个简单的计数器例子:

(let loop ((n 1))
  (if (> n 10)
    '()
    (cons n
	  (loop (+ n 1)))))
===> (1 2 3 4 5 6 7 8 9 10)

就像Scheme中的任何过程一样,在命名let中建立的这个过程是头等对象

适当尾递归[编辑]

Scheme拥有一个迭代构造do[68],但是在Scheme中更推崇的惯用法英语Programming idiom,是使用尾递归来表达迭代[69]。遵循标准的Scheme实现被要求优化尾递归,从而支持无限数量的活跃尾递归(R5RS sec. 3.5[46]),这个性质被Scheme报告描述为“适当”(proper)尾递归,它使得Scheme编程者可以安全的使用递归结构来书写迭代算法,这在很多时候是更符合直觉的。尾递归过程和命名let形式,提供对使用尾递归的迭代的支持。

;; 建造从0到9的平方的列表:
;; 注意:loop简单的就是用作标签的一个任意符号。任何符号都行。
(define (list-of-squares n)
  (let loop ((i n) (res '()))
    (if (< i 0)
      res
      (loop (- i 1) (cons (* i i) res)))))

(list-of-squares 9)
===> (0 1 4 9 16 25 36 49 64 81)

头等续体[编辑]

在Scheme中续体头等对象[70]。自从R2RS开始[55],Scheme提供了过程call-with-current-continuation英语call-with-current-continuation (简写为call/cc),通过把当前续体包装成脱离(escape)过程来捕获它,并把它绑定到编程者提供的一个过程的一个形式参数(R5RS sec. 6.4)[46]。头等续体使得编程者能够建立非局部控制结构比如迭代协程回溯

续体可以被用来模拟指令式编程语言中return语句的行为。下列函数find-first接受函数func和列表lst,返回lst中的第一个元素x,它使得(func x)返回真。

(define (find-first func lst)
  (call-with-current-continuation
    (lambda (return-immediately)
      (for-each
        (lambda (x)
          (if (func x)
    	    (return-immediately x)))
        lst)
      #f)))

(find-first integer? '(1/2 3/4 5.6 7 8/9 10 11))
===> 7
(find-first zero? '(1 2 3 4))
===> #f

David Madore在1999年提出的阴阳谜题[71],展示了Scheme可以将续体当作头等对象处理,绑定它们到变量,和把它们作为给过程的实际参数来传递[72]

统一的命名空间[编辑]

对比于Common Lisp,在Scheme中所有的数据和过程共享一个共同的命名空间,而Common Lisp中有函数和数据分离的命名空间,使得一个函数和一个变量可以有相同的名字,并且将一个函数作为值引用时要求特殊的表示法。这有时叫做“Lisp1与Lisp2”差异,二者分别称谓Scheme的统一的命名空间,和Common Lisp的分立的命名空间[73]

在Scheme中, 可以使用操纵和绑定数据的原始运算来绑定过程。没有等价于Common Lisp的defun#'的原始运算。

;; 变量绑定到一个数:
(define f 10)
f
===> 10
;; 变化(改变绑定值)
(set! f (+ f f 6))
f
===> 26
;; 将一个过程赋值给相同的变量:
(set! f (lambda (n) (+ n 12)))
(f 6)
===> 18
;; 将一个表达式的结果赋值给相同的变量:
(set! f (f 1))
f
===> 13
;; 函数式编程:
(apply + '(1 2 3 4 5 6))
===> 21
(set! f (lambda (n) (+ n 100)))
(map f '(1 2 3))
===> (101 102 103)

实现标准[编辑]

本章归档多年来做出的给与Scheme特定特征的设计决定,它们不是最初设计的直接产物。

注释[编辑]

直到R5RS标准,在Scheme中的标准注释是分号,它使得这行余下部份对Scheme不可见。许多实现支持可替代的约定,允许注释扩展为多于一行,而R6RS标准允许其中的两种:一个完整的S-表达式,可以通过前导#; 而变成一个注释(介入于SRFI 62[74]),和通过用#||#围绕文本,产生的“多行注释”或“块注释”。

在布尔表达式中非布尔值的处理[编辑]

在多数Lisp方言包括Common Lisp中,布尔表达式中的值NIL按照惯例被求值为值假。在Scheme中,自从1991年的IEEE标准[45],除了#f的所有的值,包括在Scheme中写为'()NIL的等价者,在布尔表达式中求值为值真(R5RS sec. 6.3.1)[46]

在多数Lisp中表示布尔值真的常量是T,而在Scheme中它是#t

干净宏[编辑]

Scheme的语法可以轻易的通过宏系统来扩展[75]。R5RS标准介入了强力的干净宏系统[76],它允许编程者使用一种简单的模式匹配子语言,向语言增加的新的语法构造(R5RS sec 4.3)[46]。在此前的R4RS标准中,干净宏系统已经作为“高级”系统,和“低级”宏系统一起被编排入标准的附录中[77],二者都被当作对Scheme的扩展而非语言的本质部份。

干净宏的实现,也叫做syntax-rules, 被要求遵守语言的其余部份的词法作用域。这是通过针对宏展开的特殊命名和作用域规则来确保的,从而避免在其他编程语言的宏系统中可能出现的常见编程错误。R6RS规定了更加复杂的变换系统syntax-case,它已经作为对R5RS Scheme的一个语言扩展而能够获得到有一段时间了。例如:

;; 定义一个宏来实现“if”的具有多个表达式的变体
;; 有真分支而无假分支
(define-syntax when
  (syntax-rules ()
    ((when pred exp exps ...)
      (if pred (begin exp exps ...)))))

宏和过程的调用看起来非常相似,二者都是S-表达式,但是它们被不同的对待。在编译器遇到程序中的一个S-表达式的时候,它首先查看这个符号是否被定义为在当前词法范围内的语法关键字。如果是这样,它接着尝试展开这个宏,将在这个S-表达式尾部的项目当作实际参数,而不用编译代码来求值它们,递归的重复这个处理过程直到没有余留的宏调用。如果它不是一个语法关键字,编译器编译代码来求值在这个S-表达式尾部的实际参数,并接着求值在这个S-表达式头部的符号所表示的变量,把它作为过程来调用,并把最终的尾部表达式作为实际参数传递给它。

多数Scheme实现还提供额外的宏系统。其中最流行是语法闭包显式重命名宏define-macro,它是类似于Common Lisp中提供的defmacro系统的非干净宏。

不能指定一个宏是否为干净的,是宏系统的一个缺点。可作为替代的展开模型比如作用域集合,提供一种潜在的解决方案[78]

延迟求值[编辑]

自从R2RS开始[55],Scheme通过delay形式和过程force支持延迟求值。

(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(set! a 20)
(force eval-aplus2)
===> 22
(define eval-aplus50 (delay (+ a 50)))
(let ((a 8))
  (force eval-aplus50))
===> 70
(set! a 100)
(force eval-aplus2)
===> 22

这些原始运算,产生或处理叫做promise的值,promise的原本定义的文字内容被留存了,并且在第一次使用force之后它的值也被留存了。promise永远只求值一次。它们可以被用来实现高级的惰性求值构造比如串流[79]

在R5RS中,给出了delayforce的推荐实现,将promise实现为没有实际参数的一个过程(thunk英语thunk),并使用记忆化来确保它永远只求值一次,与调用force的次数无关(R5RS sec. 6.4)[46]。在R6RS标准中,它们不再是原始运算,转而作为R5RS兼容库的一部份提供(rnrs r5rs (6))。

SRFI 41确使有限和无限序列能够具有非凡经济性的表达。例如,这是使用在SRFI 41中的函数定义的一个斐波那契数列[79]

;; 定义斐波那契序列
(define fibs
  (stream-cons 0
    (stream-cons 1
      (stream-map +
        fibs
        (stream-cdr fibs)))))

;; 计算这个序列的第一百个数
(stream-ref fibs 99)
===>  218922995834555169026

eval及其运行环境[编辑]

R5RS标准之前,在其他Lisp中无处不在的eval过程,在Scheme中没有等价者。在第一篇λ论文中,曾经将evaluate描述为“类似于LISP函数EVAL”[80],但在具有词法作用域的Scheme中,对这个表达式在哪个环境中求值存在困惑。例如,不明确求值下列表达式的结果应当是5还是6[81]

(let ((name '+))
  (let ((+ *))
    (evaluate (list name 2 3))))

在求值实际参数name的时候,在外层环境中找到了它的定义;在求值结果表达式(+ 2 3)的时候,如果在外层环境中求值,结果是两个运算数的总和;如果在内层环境中求值,这里符号+已经被绑定到过程*的值,结果是两个运算数的乘积。为此在1978年的最初修订报告中,将evaluate替代为enclose,它接受分别为代码和运行环境的两个实际参数[82]。由于各种技术和实际原因,第二次、第三次和第四次修订报告省略了任何eval的等价者[81]

R5RS通过规定三个返回环境的过程,并提供接受一个S-表达式和一个环境的过程eval,它在提供的这个环境内求值这个表达式(R5RS sec. 6.5)[46],解决了这个困惑。R6RS通过提供叫做environment的一个过程进行了扩展,编程者通过它可以精确的指定将哪个对象导入到求值环境之内。

通过现代Scheme(通常兼容于R5RS)来求值表达式expr,你需要定义如下这样的一个函数evaluate

(define (evaluate expr)
  (eval expr (interaction-environment)))

interaction-environment是解释器的全局环境。

数值塔[编辑]

Scheme规定了数值数据类型的相较完全的集合,包括复数有理数类型,这在Scheme中叫做“数值塔”(R5RS sec. 6.2[46])。标准对它们作抽象处理,而不委以任何特定的内部表示。

数可以有精确性品质。一个精确数只能从涉及其他精确数的精确运算产生,不精确是传染的。标准规定任何两个实现对产生精确数的所有运算都必须产生等价的结果。

R5RS标准规定了过程exact->inexactinexact->exact,它们可以用于改变一个数的精确性。inexact->exact产生“在数值上最接近实际参数的精确数”。exact->inexact产生“在数值上最接近实际参数的不精确数”。R6RS标准在主报告中省略了这些过程,而是在标准库中将它们规定为R5RS兼容过程(rnrs r5rs (6))。

在R5RS标准中,不要求Scheme实现去实现整个数值塔,而是它们必须实现“符合实现用途和Scheme语言精神二者的连贯子集”(R5RS sec. 6.2.3)[46]。新的R6RS标准要求实现整个数值塔,并且“精确整数对象和精确有理数对象实际上有无限的大小和精度,并且对于实现特定过程...所以它们在得到精确实际参数时总是返回精确结果”(R6RS sec. 3.4, sec. 11.7.1)[47]

在支持精确有理复数的实现中的精确算术例子:

;; 三个有理实数和两个有理复数的总和
(define x (+ 1/3 1/4 -1/5 -1/3i 405/50+2/3i))
x
===> 509/60+1/3i
;; 检查精确性
(exact? x)
===> #t

在既不支持精确有理数也不支持复数却接受有理数表示法的实数的实现中相同算术的例子:

;; 四个有理实数的总和
(define xr (+ 1/3 1/4 -1/5 405/50))
;; 两个有理实数的总和
(define xi (+ -1/3 2/3))
xr
===> 8.48333333333333
xi
===> 0.333333333333333
;; 检查精确性
(exact? xr)
===> #f
(exact? xi)
===> #f

二者实现都符合R5RS标准,但是第二个实现不符合R6RS,因为它没有实现完整的数值塔。

原始数据类型不相交[编辑]

在Scheme中原始数据类型是不相交的。对于任何Scheme对象,下列谓词中只有一个可以为真:boolean?pair?symbol?number?char?、>string?vector?port?procedure?(R5RS sec 3.2)[46]

作为对比,在数值数据类型之内,对数值值是可以有交叠的。例如,一个整数值可以同时满足如下谓词:integer?rational?real?complex?number?(R5RS sec 6.2)[46]

等价谓词[编辑]

Scheme在任意对象之间有三种不同类型的等价,它们通过三种不同的“等价谓词”来指示,即测试等式的关系算符eq?eqv?equal?

  • eq?求值为#f,除非它的实际参数表示在内存中相同的对象;
  • eqv?大体上同于eq?,但是特殊处理原始对象(比如字符和数),使得表示相同值的数eqv?为真,即使它们不引用相同的对象;
  • equal?比较数据结构比如列表、向量和字符串,来确定它们是否有全等的结构并且其内容eqv?为真(R5RS sec. 6.1)[46]

在Scheme中还存在依赖于类型的等价运算:string=?string-ci=?比较两个字符串(后者进行不依赖大小写比较);char=?char-ci=?比较字符;=比较数[46]

输入/输出[编辑]

Scheme的输入和输出基于了“端口”数据类型(R5RS sec 6.6)[46]。R5RS定义了两个缺省端口,可通过过程current-input-portcurrent-output-port来访问,它们对应于Unix概念的标准输入和标准输出。多数实现还提供current-error-port。标准通过标准过程比如with-input-from-filewith-output-to-file,支持输入和标准输出的重定向。多数实现提供有重定向能力的字符串端口,使用在SRFI 6中描述的过程[83],确使很多常规的输入-输出运算能在字符串缓冲区上进行而非在文件上。R6RS标准规定了更多复杂和有能力的端口过程和很多新的端口类型。

下面的例子是使用严格的R5RS Scheme书写的。

例子1,缺省输出到current-output-port

(let ((hello0 (lambda() (display "Hello world") (newline))))
  (hello0))

例子2,类似例子1但对输出过程使用可选的端口参数的例子:

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (hello1 (current-output-port)))

类似例子1,但是输出被重定向到一个新建文件:

;; NB: with-output-to-file is an optional procedure in R5RS
(let ((hello0 (lambda () (display "Hello world") (newline))))
  (with-output-to-file "helloworldoutputfile" hello0))

类似例子2,但是具有显式的文件打开和端口关闭来发送输出到文件:

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p)))
      (output-port (open-output-file "helloworldoutputfile")))
  (hello1 output-port)
  (close-output-port output-port))

类似例子2,但是使用call-with-output-file来发送输出到一个文件:

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (call-with-output-file "helloworldoutputfile" hello1))

对输入提供了类似的过程。R5RS Scheme提供了谓词input-port?output-port?。对于字符输入和输出提供了write-charread-charpeek-charchar-ready?。为了书写和阅读Scheme表达式,Scheme提供了readwrite。在读运算时,如果输入端口到达了文件的结束处,则返回的结果是end-of-file对象,并且这可以使用谓词eof-object?来测试。

除了标准之外,SRFI 28定义了一个基本的格式化过程,类似Common Lisp的format并以此命名[84]

标准过程的重定义[编辑]

在Scheme中,过程被绑定到变量[61]。在R5RS中语言标准正式的授权编程者可以变更内建过程的变量绑定,在效果上重定义它们(R5RS "Language changes")[46]。例如,通过重定义+可以将它扩展为同接受数一样接受字符串:

(set! +
  (let ((original+ +))
    (lambda args
      (apply
        (if (or (null? args) (string? (car args)))
          string-append
          original+)
        args))))

(+ 1 2 3)
===> 6
(+ "1" "2" "3")
===> "123"

在R6RS中所有绑定,包括标准过程,都属于某个库,并且所有导出的绑定都是不可变的(R6RS sec 7.1)[47]。因此,禁止通过变更进行标准过程的重定义。转而,可以在标准过程的名字下导入不同的过程,这在效果上类似于重定义。

标准形式和过程概述[编辑]

Scheme语言正式定义于1998年的R5RS和2007年R6RS标准之中。它们描述了标准“形式”,即关键字和随同的语法,它们提供语言的控制结构,和执行通常任务的标准过程。

在标准Scheme中,从一个数据类型转换到另一个数据类型的过程,在它们的名字中包含字符串->,谓词结束于一个?,而改变已经分配了数据的值的过程结束于一个!。Scheme编程者通常跟从这些命名约定

标准形式[编辑]

本表格描述Scheme中的标准形式。某些形式出现在不止一行之中,因为它们不能被轻易的归类入语言中的一个单一功能。

在表格中标记了“L”的形式被归类为标准中的派生的“库”形式,并且在实践中通常被实现为使用了更基础形式的宏,这使得实现任务比在其他语言中要容易许多。

R5RS Scheme语言中的标准形式
用途 形式
定义 define
绑定构造 lambda, do (L), let (L), let* (L), letrec (L)
条件求值 if, cond (L), case (L), and (L), or (L)
顺序求值 begin (*)
迭代 lambda, do (L), 命名let (L)
语法扩展 define-syntax, let-syntax, letrec-syntax, syntax-rules (R5RS), syntax-case (R6RS)
引述 quote('), unquote(,), quasiquote(`), unquote-splicing(,@)
赋值 set!
延迟求值 delay (L)

注意begin在R5RS中被定义为库语法,但是展开者需要知道它来完成分片功能。在R6RS中它不再是库语法。

标准过程[编辑]

下面两个表格描述在R5RS Scheme中的标准过程。R6RS更加具有可扩展性而如此总结是不实际的。

某些过程出现在不止一行之中,因为它们不能轻易的分类入语言的一个单一功能。

R5RS Scheme语言中的标准过程
用途 过程
构造 vector, make-vector, make-string, list
等价谓词 eq?, eqv?, equal?, string=?, string-ci=?, char=?, char-ci=?
类型转换 vector->list, list->vector, number->string, string->number, symbol->string, string->symbol, char->integer, integer->char, string->list, list->string
数值 参见独立表格
字符串 string?, make-string, string, string-length, string-ref, string-set!, string=?, string-ci=?, string<? string-ci<?, string<=? string-ci<=?, string>? string-ci>?, string>=? string-ci>=?, substring, string-append, string->list, list->string, string-copy, string-fill!
字符 char?, char=?, char-ci=?, char<? char-ci<?, char<=? char-ci<=?, char>? char-ci>?, char>=? char-ci>=?, char-alphabetic?, char-numeric?, char-whitespace?, char-upper-case?, char-lower-case?, char->integer, integer->char, char-upcase, char-downcase
向量 make-vector, vector, vector?, vector-length, vector-ref, vector-set!, vector->list, list->vector, vector-fill!
符号 symbol->string, string->symbol, symbol?
有序对和列表 pair?, cons, car, cdr, set-car!, set-cdr!, null?, list?, list, length, append, reverse, list-tail, list-ref, memq. memv. member, assq, assv, assoc, list->vector, vector->list, list->string, string->list
识别谓词 boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?
续体 call-with-current-continuation (call/cc), values, call-with-values, dynamic-wind
环境 eval, scheme-report-environment, null-environment, interaction-environment (可选)
输入/输出 display, newline, read, write, read-char, write-char, peek-char, char-ready?, eof-object? open-input-file, open-output-file, close-input-port, close-output-port, input-port?, output-port?, current-input-port, current-output-port, call-with-input-file, call-with-output-file, with-input-from-file(可选), with-output-to-file(可选)
系统接口 load (可选), transcript-on (可选), transcript-off (可选)
延迟求值 force
函数式编程 procedure?, apply, map, for-each
布尔逻辑 boolean? not

在其名字中包含-ci的字符串和字符过程,在它们的实际参数之间进行不依赖大小写的比较:相同字符的大写和小写版本被认为是相等的。

R5RS Scheme语言中的标准数值过程
用途 过程
基本算术算符 +, -, *, /, abs, quotient, remainder, modulo, gcd, lcm, expt, sqrt
有理数 numerator, denominator, rational?, rationalize
近似 floor, ceiling, truncate, round
精确性 inexact->exact, exact->inexact, exact?, inexact?
不等式 <, <= , >, >=, =
杂项谓词 zero?, negative?, positive? odd? even?
极大和极小 max, min
三角 sin, cos, tan, asin, acos, atan
指数 exp, log
复数 make-rectangular, make-polar, real-part, imag-part, magnitude, angle, complex?
输入-输出 number->string, string->number
类型谓词 integer?, rational?, real?, complex?, number?

接受多于一个实际参数的-/在R5RS中被定义了但留作为可选的。

Scheme实现要求[编辑]

由于Scheme的极简主义,很多常见过程和语法形式不是由标准定义的。 为了保持核心语言很小并促进扩展的标准化,Scheme社群拥有“Scheme实现要求”(SRFI)流程,通过对扩展提案的仔细研讨来定义扩展库。这提升了代码可移植性。很多SRFI被几乎所有Scheme实现支持。

在不同的实现中具有相当广泛支持的SRFI包括[85]

  • 0: 基于特征的条件展开构造
  • 1: 列表库
  • 4: 同构数值向量数据类型
  • 6: 基本字符串端口
  • 8: 接收、绑定到多个值
  • 9: 定义记录类型
  • 13: 字符串库
  • 14: 字符集库
  • 16: 可变元数过程的语法
  • 17: 广义set!
  • 18: 多线程支持
  • 19: 时间数据类型和过程
  • 25: 多维数组原语
  • 26: 不用柯里化的特殊化形式参数的表示法
  • 27: 随机数位的来源
  • 28: 基本格式化字符串
  • 29: 本地化
  • 30: 嵌套的多行注释
  • 31: 递归求值的特殊形式
  • 37: args-fold:程序实际参数处理器
  • 39: 形式参数对象
  • 41: 串流
  • 42: 及早推导式
  • 43: 向量库
  • 45: 表达迭代式惰性算法的原语
  • 60: 作为位元的整数
  • 61: 更一般性的cond子句
  • 66: 八位组向量
  • 67: 比较过程

實作[编辑]

Scheme的精簡設計,使得程式語言設計人士與愛好者,特別鍾愛研究它,故而它有不斷湧現的新實作,而活躍開發的實作也在持續跟進語言標準更新[86]。儘管Scheme有眾多實現是它的一個主要長處[19],但是由于Scheme没有库函数标准,造成了很多不可互通的實作互相競爭,试图使用Scheme编写既复杂又便于移植的程序,往往比较困难[20]。R6RS和R7RS-Large,在核心语言之外制定了库函数标准,使得编译器开发者和贡献者可以实现Scheme的可移植库。

幾乎所有Scheme實作都有传承自Lisp的「讀取﹣求值﹣輸出循環」交互模式,一些Scheme實作亦可作為編譯器。很多用C语言及衍生语言寫成的軟體,都利用Scheme作為腳本語言,很多嵌入式系統語言即是基於Scheme。Chez SchemeLarceny英语Larceny (Scheme implementation)等实现,可以將Scheme程式編譯為本機二進制碼。GambitChicken等实现,可將Scheme程式編譯為C代码,Bigloo英语Bigloo还能编译成JVM字节码或者.Net字节码。

一些实现支持额外的特征。比如Kawa英语Kawa (Scheme implementation)提供与Java类的集成,而Scheme到C编译器通常易于使用C写成的外部库,甚至允许将实际C代码嵌入到Scheme源代码中。另一个例子是用java书写的Pvts英语Pvts,它提供了支持Scheme学习的一组可视工具。

教科書[编辑]

實際用處[编辑]

很多著名的電腦科學院校都利用Scheme來教授入門級課程。以下為一些最為著名的教授Scheme的學校:

自由軟體影像處理程式GIMP利用Scheme為嵌入式脚本語言[92]GNOME中有到核心库的一个GNU的扩展語言Guile包装器[93]

参见[编辑]

註釋[编辑]

  1. ^ Alex Shinn, John Cowan英语John W. Cowan, Arthur A. Gleckler; et al. The Revised7 Report on the Algorithmic Language Scheme (PDF). 2022-09-06. 
  2. ^ R7RS-small archive. 
  3. ^ BONES - A simple Scheme compiler for x86_64 systems. 
  4. ^ 4.0 4.1 Alex Shinn. Chibi-Scheme is a very small library intended for use as an extension and scripting language in C programs. 
  5. ^ Cyclone Scheme is a brand-new compiler that allows real-world application development using the R7RS Scheme Language standard. 
  6. ^ Foment is an implementation of R7RS Scheme. 
  7. ^ Loko Scheme, an optimizing Scheme compiler. 
  8. ^ Mosh is a free and fast interpreter for Scheme as specified in the R7RS & R6RS. 
  9. ^ Picrin is a lightweight R7RS scheme implementation written in pure C89. 
  10. ^ Rapid Scheme expands and evaluates a Scheme program as described by the R7RS. 
  11. ^ s7 is a Scheme interpreter intended as an extension language for other applications. 
  12. ^ S9fES is a mature, portable, and comprehensible interpreter for R4RS Scheme. 
  13. ^ Sagittarius Scheme - R6RS/R7RS Scheme system. 
  14. ^ femtolisp - a lightweight, robust, scheme-like lisp implementation. 
  15. ^ Husk is a dialect of Scheme written in Haskell that implements a superset of the R5RS standard and a large portion of the R7RS-small language. 
  16. ^ Swift LispKit is a framework for building Lisp-based extension and scripting languages for macOS and iOS applications. 
  17. ^ The Scheme Programming Language. MIT. [2022-05-04]. (原始内容存档于2022-04-12). 
  18. ^ Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press. 1996 [2011]. ISBN 0-262-01153-0. (原始内容存档于2018-03-09) (英语). 
  19. ^ 19.0 19.1 scheme-faq-standards - What Scheme implementations are there?. Community Scheme Wiki. 
  20. ^ 20.0 20.1 Will Clinger, Marc Feeley, Chris Hanson, Jonathan Rees and Olin Shivers. Scheme Steering Committee Position Statement. Scheme Steering Committee. 2009-08-20 [2011-12-19]. (原始内容存档于2009-08-26). Scheme has the unhappy distinction of being the world's most unportable programming language. It is almost misleading to call Scheme a "programming language;" it would be more accurate to characterise Scheme as a family of dialects, all loosely related by the common features of lexical scope, dynamic typing, list structure, higher-order functions, proper tail-recursion, garbage collection, macros, and (some form of) s-expression based lexical syntax. 
  21. ^ John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979. To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions. Church used higher order functionals instead of using conditional expressions. Conditional expressions are much more readily implemented on computers. 
    David Turner英语David Turner (computer scientist). Some History of Functional Programming Languages (PDF). [2021-11-10]. (原始内容 (PDF)存档于2020-04-15). LISP was not based on the lambda calculus, despite using the word “LAMBDA” to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene’s theory of first order recursive functions. (McCarthy made these statements, or very similar ones, in a contribution from the floor at the 1982 ACM symposium on LISP and functional programming in Pittsburgh. No written version of this exists, as far as know.) 
  22. ^ A meta-circular interpreter of a subset of Scheme. 
  23. ^ Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998. At about this time, Carl Hewitt was developing his theory of actors as a model of computation. This model was object-oriented and strongly influenced by Smalltalk. Every object was a computationally active entity capable of receiving and reacting to messages. The objects were called actors, and the messages themselves were also actors. Every computational entity was an actor and message-passing was the only means of interaction. An actor could have arbitrarily many acquaintances; that is, it could “know about” other actors and send them messages or send acquaintances as (parts of) messages. Hewitt then went on to model many traditional control structures as patterns of message-passing among actors. Functional interactions were modeled with the use of continuations; one might send the actor named “factorial” a message containing two other actors: the number 5 and another actor to which to send the eventually computed value (presumably 120). While Conniver made control points into first-class data, the actors model went to the logical extreme by making everything be first-class data. 
  24. ^ Carl Hewitt, Peter Bishop, Irene Greif, Brian Smith, Todd Matson, Richard Steiger. Actor induction and meta-evaluation. 1973. 
    Irene Greif, Carl Hewitt. Actor semantics of PLANNER-73. 1975. 
  25. ^ Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998 [2021-11-07]. (原始内容存档于2022-04-06). Hewitt and his students developed and implemented in Lisp a new language to make concrete the actor model of computation. This language was first called Planner-73 but the name was later changed to PLASMA (PLAnner-like System Modeled on Actors).
    It was at this point that we (Sussman and Steele) put our heads together. (Steele had just become a graduate student at MIT, but he had been following this progression of language designs because he had had a part-time job at MIT Project MAC as one of the maintainers of MacLisp.) We wanted to better understand Hewitt’s actors model but were having trouble relating the actors model and its unusual terminology to familiar programming notions. We decided to construct a toy implementation of an actor language so that we could play with it. Using MacLisp as a working environment, we wrote a tiny Lisp interpreter and then added mechanisms for creating actors and sending messages. We wanted to better understand Hewitt’s actors model but were having trouble relating the actors model and its unusual terminology to familiar programming notions. We decided to construct a toy implementation of an actor language so that we could play with it. Using MacLisp as a working environment, we wrote a tiny Lisp interpreter and then added mechanisms for creating actors and sending messages.
     
  26. ^ 彼得·兰丁. The mechanical evaluation of expressions (PDF). 1964. 
  27. ^ Joel Moses英语Joel Moses. The Function of FUNCTION in LISP, or Why the FUNARG Problem Should Be Called the Environment Problem (pdf). June 1970 [2009-10-27]. AI Memo 199. (原始内容存档于2010-05-23). The use of free variables is a very powerful computational idea. In many situations it is possible to avoid using free variables by supplying a function with additional arguments. This can be quite cumbersome. ……
    When a function uses free variables or when it calls functions which use them, then the value of this function is not completely determined by its arguments, since the value might depend on the values of the free variables. Thus in order to completely specify a computation, one has to specify a function and its arguments in addition to an environment in which the values of the free variables can be determined. ……
    An important point which must be realized about functional arguments (abbreviated FUNARGs) is that two different environments are involved in such cases. The first environment is the one which is in effect when then FUNARG is bound as an argument. We shall call this the binding environment. The second environment is the one that is in effect when the FUNARG is activated as a function. We shall call this the activation environment. ……
    Consider now what it would require for the system to restore the binding environment for functional arguments. It would require knowing where in the stack or "alist" the binding environment exists through some pointer to it. Supplying such pointer is a function FUNCTION in LISP. That is when one transmits a functional argument f which is to be evaluated in its binding environment, then one uses FUNCTION(f). FUNCTION will prevent its argument f from being evaluated, just as QUOTE would. The result of FUNCTION will be a structure which not only contains a reference to the function f, but also contains a pointer to the binding environment. Thus at the FUNARG's activation time we will be able to use the current place in the stack up to the point where the binding environment exists, thus skipping over any values in the activation environment which differ from those in the binding environment. ……
    The points we have made so far are:
    1) Free variables in function definitions require that one must have an environment in order to be able to evaluate a function.
    2) When one uses functional arguments, the the question arises as to which environment one chooses in order to evaluate the function, the binding environment or the activation environment.
    3) When one returns functions (which require the values of free variables for their evaluation) then one must, in general, save the binding environment and thus create a stack which is, in fact, a tree. ……
    LISP allows the user to choose between the binding environment and the activation environment by allowing a function to be bound with FUNCTION or with QUOTE. QUOTE will force the activation environment to be used in evaluating the function. A useful metaphor for the difference between FUNCTION and QUOTE in LISP is to think of QUOTE as a porous or an open covering of the function since free variables escape to the current environment. FUNCTION acts as a closed or nonporous covering (hence the term "closure" used by Landin). Thus we talk of "open" Lambda expressions (functions in LISP are usually Lambda expressions) and "closed" Lambda expressions. ……
    My interest in the environment problem began while Landin, who had a deep understanding of the problem, visited MIT during 1966-67. I then realized the correspondence between the FUNARG lists which are the results of the evaluation of "closed" Lambda expressions in LISP and ISWIM's Lambda Closures.
     
  28. ^ Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998 [2021-11-07]. (原始内容存档于2022-04-06). Sussman had just been studying Algol. He suggested starting with a lexically scoped dialect of Lisp, because that seemed necessary to model the way names could refer to acquaintances in PLASMA. Lexical scoping would allow actors and functions to be created by almost identical mechanisms. Evaluating a form beginning with the word lambda would capture the current variable-lookup environment and create a closure; evaluating a form beginning with the word alpha would also capture the current environment but create an actor. Message passing could be expressed syntactically in the same way as function invocation. The difference between an actor and a function would be detected in the part of the interpreter traditionally known as apply. A function would return a value, but an actor would never return; instead, it would typically invoke a continuation, another actor that it knew about. Our interpreter also provided the necessary primitives for implementing the internal behavior of primitive actors, such as an addition operator that could accept two numbers and a continuation actor. 
  29. ^ 29.0 29.1 Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998. This led us to three important ideas:
    • First, we realized that all the patterns of control structure that Hewitt had described in terms of actors could equally well be described by the λ-calculus. ……
    • Second, we realized that the λ-calculus — a small, simple formalism — could serve as the core of a powerful and expressive programming language. (Lisp had adopted the λ-notation for functions but had failed to support the appropriate behavior for free variables. The original theoretical core of Lisp was recursion equations, not the λ-calculus.) ……
    • Third, we realized that in our quest for the “ultimate AI language” we had come full circle. As the MIT school had struggled to find more and more powerful ways to express and manipulate control structure to support heuristic search, we had progressed from Lisp to CONVERT to Planner to Conniver to PLASMA to a simple variation of Lisp!
     
  30. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). Inspired by ACTORS [Greif and Hewitt][Smith and Hewitt], we have implemented an interpreter for a LISP-like language, SCHEME, based on the lambda calculus [Church], but extended for side effects, multiprocessing, and process synchronization. The purpose of this implementation is tutorial. We wish to:
    ⑴ alleviate the confusion caused by Micro-PLANNER英语Planner (programming language), CONNIVER, etc. by clarifying the embedding of non-recursive control structures in a recursive host language like LISP.
    ⑵ explain how to use these control structures, independent of such issues as pattern matching and data base manipulation.
    ⑶ have a simple concrete experimental domain for certain issues of programming semantics and style.
     
    LISP code for the SCHEME interpreter by Gerald Jay Sussman and Guy Lewis Steele, Jr. 
  31. ^ Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998. We were very pleased with this toy actor implementation and named it “Schemer” because we thought it might become another AI language in the tradition of Planner and Conniver. However, the ITS operating system had a 6-character limitation on file names and so the name was truncated to simply SCHEME and that name stuck. 
  32. ^ Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998 [2021-11-07]. (原始内容存档于2022-04-06). We concluded that actors and closures were effectively the same concept. (Hewitt later agreed with this, but noted that two types of primitive actors in his theory, namely cells (which have modifiable state) and synchronizers (which enforce exclusive access), cannot be expressed as closures in a lexically scoped pure Lisp without adding equivalent primitive extensions.) 
    Carl Hewitt英语Carl Hewitt. ActorScript: Industrial strength integration of local and nonlocal concurrency for Client-cloud Computing. 2009. arXiv:0907.3330可免费查阅 [cs.PL]. In summary, Sussman and Steele [1975] mistakenly concluded “we discovered that the 'Actors' and the lambda expressions were identical in implementation.” The actual situation is that the λ-calculus is capable of expressing some kinds of sequential and parallel control structures but, in general, not the concurrency expressed in the Actor model. On the other hand, the Actor model is capable of expressing everything in the λ-calculus and more [Hewitt 2008f]. 
  33. ^ Guy L. Steele Jr., Gerald J. Sussman. The Revised Report on SCHEME: A Dialect of LISP (PDF). 1978. SCHEME is a dialect of LISP. It is an expression-oriented, applicative order, interpreter-based language which allows one to manipulate programs as data. It differs from most current dialects of LISP in that it closes all lambda-expressions in the environment of their definition or declaration, rather than in the execution environment. This has the consequence that variables are normally lexically scoped, as in ALGOL. However, in contrast with ALGOL, SCHEME treats procedures as a first-class data type. They can be the values of variables, the returned values of procedures, and components of data structures. Another difference from LISP is that SCHEME is implemented in such a way that tail-recursions execute without net growth of the interpreter stack. The effect of this is that a procedure call behaves like a GOTO and thus procedure calls can be used to implement iterations, as in PLASMA. 
  34. ^ Gerald J. Sussman, Guy L. Steele Jr. The First Report on Scheme Revisited. 1998 [2021-11-07]. (原始内容存档于2022-04-06). We were actually trying to build something complicated and discovered, serendipitously, that we had accidentally designed something that met all our goals but was much simpler than we had intended.
    We thought that Scheme would turn out to be the next in a long series of programming languages that had been designed at MIT over the course of 17 years. ……
    In this process we learned some great lessons. The λ-calculus can be seen as a universal glue by which compound constructs can be built inductively from simpler ones and a set of primitives. …… The essence of the matter is that the λ-calculus provides a way of abstracting entities of any particular type and then combining such abstractions with other entities to make new entities of that same type, which are instances of the abstractions. …… Given the right primitives, the λ-calculus can serve as a foundation for the abstraction and instantiation of virtually any kind of complex conceptual structure.
    We also were struck by the great importance of names as a means of reference. …… Naming seems to correspond to some important cognitive mechanism that is, if not innate, then at least extremely well-developed in our culture. The λ-calculus embodies a provably coherent theory of naming.
     
  35. ^ The Original 'Lambda Papers' by Guy Steele and Gerald Sussman. [2021-11-07]. (原始内容存档于2022-01-12). 
  36. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). 
  37. ^ Gerald J. Sussman, Guy L. Steele Jr. Lambda: The Ultimate Imperative. 1976 [2021-11-11]. (原始内容存档于2022-04-10). 
  38. ^ Guy L. Steele Jr. LAMBDA: The Ultimate Declarative. 1976 [2021-11-10]. (原始内容存档于2022-04-09). 
  39. ^ Guy L. Steele Jr. Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO. 1977 [2021-11-07]. (原始内容存档于2022-05-09). 
  40. ^ Gerald J. Sussman, Guy L. Steele Jr. The Art of the Interpreter of the Modularity Complex (Parts Zero, One, and Two). 1978 [2021-11-07]. (原始内容存档于2021-11-07). 
  41. ^ Guy L. Steele Jr. RABBIT: A Compiler for SCHEME. 1978 [2021-11-07]. (原始内容存档于2021-11-08). 
    Rabbit Scheme: Old Scheme implementation in InterLisp. 
  42. ^ Gerald J. Sussman, Guy L. Steele Jr. Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode. 1979 [2021-11-07]. (原始内容存档于2021-11-07). 
  43. ^ Gerald J. Sussman, Guy L. Steele Jr. Design of a LISP-based microprocessor. 1980 [2021-11-07]. (原始内容存档于2021-11-08). 
  44. ^ J.W. Backus; F.L. Bauer; J.Green; C. Katz; J. McCarthy P. Naur; et al. Revised Report on the Algorithmic Language Algol 60. Numerische Mathematik, Communications of the ACM, and Journal of the British Computer Society. January–April 1960 [2012-08-09]. (原始内容存档于2007-06-25). 
  45. ^ 45.0 45.1 IEEE 1178-1990 - IEEE Standard for the Scheme Programming Language. [2022-01-14]. (原始内容存档于2021-03-04). 
  46. ^ 46.00 46.01 46.02 46.03 46.04 46.05 46.06 46.07 46.08 46.09 46.10 46.11 46.12 46.13 46.14 46.15 46.16 Richard Kelsey, William Clinger英语William Clinger (computer scientist), Jonathan Rees; et al. Revised5 Report on the Algorithmic Language Scheme. Higher-Order and Symbolic Computation. August 1998, 11 (1): 7–105 [2007-01-04]. doi:10.1023/A:1010051815785. (原始内容存档于2007-01-05) (英语). Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have an exceptionally clear and simple semantics and few different ways to form expressions. A wide variety of programming paradigms, including imperative, functional, and message passing styles, find convenient expression in Scheme. 
  47. ^ 47.0 47.1 47.2 Michael Sperber, R. Kent Dybvig, Matthew Flatt英语Matthew Flatt, Anton Van Straaten; et al. Revised6 Report on the Algorithmic Language Scheme. Scheme Steering Committee. August 2007 [2009-10-20]. (原始内容存档于2013-06-25). This report is accompanied by a report describing standard libraries; references to this document are identified by designations such as “library section” or “library chapter”. It is also accompanied by a report containing non-normative appendices. A fourth report gives some historical background and rationales for many aspects of the language and its libraries. 
  48. ^ Revised6 Report on the Algorithmic Language Scheme, Appendix E: language changes. Scheme Steering Committee. 2007-09-26 [2011-12-19]. (原始内容存档于2010-04-09). 
  49. ^ R6RS Electorate. Scheme Steering Committee. 2007 [2009-10-20]. (原始内容存档于2008-12-04). 
  50. ^ Marc Feeley (compilation). Implementors' intentions concerning R6RS. Scheme Steering Committee, r6rs-discuss mailing list. 2007-10-26 [2009-10-20]. (原始内容存档于2008-08-20). 
  51. ^ R7RS Home Page. 
  52. ^ R7RS-small archive. 
  53. ^ Implementations support all or part of R7RS-small. 
  54. ^ R7RS-Large Interim Red Edition. 2020-03-17. The Revised7 Report on the Algorithmic Language Scheme (“R7RS”) intentionally describes a small language, suitable for implementing on reduced hardware, or for experiments in programming language design and implementation.
    However, Scheme is used for practical programming, and there a minimal language is not a help. Additional data structures and programming idioms make the programmer’s job easier (if they are well-designed!). Therefore, as part of the R7RS design process, it was agreed that a subsequent report would appear on “R7RS-Large”, a collection of Scheme libraries that are useful across a wide variety of problems.
    The decision of what was to appear in R7RS-Large was left to the community, and a strategy was adopted: proposals were published as SRFIs (Scheme Requests For Implementation, http://srfi.schemers.org), and the community would then vote on which would be adopted.
    As a result, R7RS-Large will be developed in several stages, depending upon the support from the community for each proposal. At each stage, several SRFIs are frozen, and implementers and users may then rely upon those libraries being in the final product. (In a few cases, a library might be revisited, with a subsequent stage adopting a completely backward-compatible new version of that library; this has already happened with generators.)
    When this process has completed, the resulting interim reports will be collated and reorganized into a final document.
     
  55. ^ 55.0 55.1 55.2 55.3 William Clinger英语William Clinger (computer scientist). The Revised Revised Report on Scheme or An Uncommon Lisp (PDF). 1985. Data and procedures and the values they amass, Higher-order functions to combine and mix and match, Objects with their local state, the message they pass, A property, a package, the control of point for a catch - In the Lambda Order they are all first-class. One thing to name them all, one things to define them, one thing to place them in environments and bind them, in the Lambda Order they are all first-class. ……
    Scheme shares with Common Lisp the goal of a core language common to several implementations. Scheme differs from Common Lisp in its emphasis upon simplicity and function over compatibility with older dialects of Lisp.
     
  56. ^ Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978. System-Provided Extensions - Some standard syntactic extension are provided by convenience in ordinary programming. They are distinguished from other magic words in that they are semantically defined in terms of others rather then being primitive {Note FEXPR英语fexprs Are Okay by Us}. For expository purposes they are described here pattern-matching/production-rules kind of language. takes advantage of the definition of list notation: (A B C) = (A . (B . (C . NIL))). Thus the pattern (x . r) matches (A B C), with x = A and r = (B C). the ordering of the "productions" is significant; the first one which matches is to be used. 
  57. ^ 57.0 57.1 Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). There are several important consequences of closing every lambda expression in the environment from which it is passed (i.e., in its "lexical" or "static" environment).
    First, the axioms of lambda calculus are automatically preserved. Thus, referential transparency英语referential transparency is enforced. This in turn implies that there are no "fluid" variable bindings (as there are in standard stack implementations of LISP such as MacLISP).
    Second, the upward funarg problem英语funarg problem [Moses] requires that the environment structure be potentially tree-like.
    Finally, the environment at any point in a computation can never be deeper than the lexical depth of the expression being evaluated at that time; i.e., the environment contains bindings only for variables bound in lambdas lexically surrounding the expression being evaluated. This is true even if recursive functions are involved. ……Furthermore, it is not even necessary to scan the environment for the variable, since its value must be in a known position relative to the top of the environment structure; this position can be computed by a compiler at compile time on the basis of lexical scope.
     
  58. ^ John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. LISP 1.5 Programmer's Manual (PDF) 2nd. MIT Press. 1985 [1962] [2021-11-10]. ISBN 0-262-13011-4. (原始内容 (PDF)存档于2021-03-02). The variables in a lambda expression are dummy or bound variables because systematically changing them does not alter the meaning of the expression. Thus λ[[u;v];v2+u] means the same thing as λ[[x;y];y2+x].
    We shall sometimes use expressions in which a variable is not bound by a lambda. For example, in the function of two variables λ[[x;y];xn+yn] the variable n is not bound. This is called a free variable. It may be regarded as a parameter. Unless n has been given a value before trying to compute with this function, the value of the function must be undefined. ……
    Free Variables - A variable is bound in a particular function when it occurs in a list of bound variables following the word LAMBDA or PROG. Any variable that is not bound is free. ……
    When a variable is used free, it must have been bound by a higher level function. If a program is being run interpretively, and a free variable is used without having bee bound on a higher level, error diagnostic *A 8* will occur.
    If the program is being run complied, the diagnostic may not occur, and the variable may have value NIL.
     
  59. ^ van Tonder, André. A Lambda Calculus for Quantum Computation. SIAM Journal on Computing. 1 January 2004, 33 (5): 1109–1135. S2CID 613571. arXiv:quant-ph/0307150可免费查阅. doi:10.1137/S0097539703432165. 
  60. ^ Niehren, J.; Schwinghammer, J.; Smolka, G. A concurrent lambda calculus with futures (PDF). Theoretical Computer Science. November 2006, 364 (3): 338–356 [2021-11-07]. doi:10.1016/j.tcs.2006.08.016. (原始内容 (PDF)存档于2022-04-08). 
  61. ^ 61.0 61.1 Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). DEFINE - This is analogous to the MacLISP DEFUN primitive (but note that the LAMBDA must appear explicitly!). It is used for defining a function in the "global environment" permanently, as opposed to LABELS (see below), which is used for temporary definitions in a local environment. DEFINE takes a name and a lambda expression; it closes the lambda expression in the global environment and stores the closure in the LISP value cell of the name (which is a LISP atom). 
    Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978 [2021-11-07]. (原始内容存档于2022-04-06). Atoms which are not atomic symbols (identifiers) evaluate to themselves. Typical examples of such atoms are numbers, arrays, and strings (character arrays). Symbols are treated as identifiers or variables. They may be lexically bound by lambda-expressions. There is a global environment containing values initially have as their values primitive operations such as, for example, CAR, CONS, and PLUS. SCHEME differs from most LISP systems in that the atom CAR is not itself an operation (in the sense of being an invocable object, e.g. a valid first argument to APPLY), but only has one as a value when considered as an identifier. 
  62. ^ Structure and Interpretation of Computer Programs - 2.1.3 What Is Meant by Data?. [2021-11-04]. (原始内容存档于2022-04-25). 
  63. ^ Y-Combinator, Based on work by Jim Marshall. [2021-12-24]. (原始内容存档于2021-12-24). 
  64. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Lambda: The Ultimate Imperative. 维基文库. 1976 (英文). Lambda calculus (and related languages, such as "pure LISP") is often used for modelling the applicative constructs of programming languages. However, they are generally thought of as inappropriate for modelling imperative constructs. …… we show how imperative constructs may be modelled by applicative SCHEME constructs. ……
    Up to now we have thought of SCHEME’s LAMBDA expressions as functions, and of a combination such as (G (F X Y)) as meaning “apply the function F to the values of X and Y, and return a value so that the function G can be applied and return a value ...” But notice that we have seldom used LAMBDA expressions as functions. Rather, we have used them as control structures and environment modifiers. For example, consider the expression:
      (BLOCK (PRINT 3) (PRINT 4))
    This is defined to be an abbreviation for:
      ((LAMBDA (DUMMY) (PRINT 4)) (PRINT 3))
    We do not care about the value of this BLOCK expression; it follows that we do not care about the value of the (LAMBDA (DUMMY) ...). We are not using LAMBDA as a function at all.
    It is possible to write useful programs in terms of LAMBDA expressions in which we never care about the value of any lambda expression. We have already demonstrated how one could represent any “FORTRAN” program in these terms: all one needs is PROG (with GO and SETQ), and PRINT to get the answers out. The ultimate generalization of this imperative programming style is continuation-passing. ……
    …… we will consider the problem of dynamically scoped, or "fluid", variables. These do not exist in ALGOL, but are typical of many LISP implementations, ECL, and APL. We will see that fluid variables may be modelled in more than one way, and that one of these is closely related to continuation-passing.
     
  65. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). It is always possible, ……to perform any calculation in this way: rather than reducing to its value, it reduces to an application of a continuation to its value (cf. [Fischer]). That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function. 
  66. ^ Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978. Non-atomic forms are divided by the evaluator into two classes: combinations and "magic (special) forms". …… Magic forms are recognized by then presence of a "magic (reserved) word" in the car position of the form. All non-atomic forms which are not magic forms are considered to be combinations. The system has a small initial set of magic words; there is also a mechanism for creating new ones {Note FUNCALL is a Pain}.
    A combination is considered to be a list of subforms. These subforms are all evaluated. The first value mub be a procedure; it is applied to the other values to get the value of the combination. There are four important points here:
    (1) the procedure Position is always evaluated just like any other position. (This is why the primitive operators are the values of global identifiers.)
    (2) the procedure is never "re-evaluated"; if the first subform fails to evaluate to a applicable procedure, it is an error. Thus, unlike most LISP systems, SCHEME always evaluates the first subform of a combination exactly once.
    (3) the arguments are all completely evaluated before the procedure is applied; that is, SCHEME, like most LISP systems, is an applicative-order language. Many SCHEME programs exploit this fact.
    (4) the argument forms (and procedure form) may in principle be evaluated in any order. This is unlike the usual LISP left-to-right order. (All SCHEME interpreters implemented so far have in fact performed left-to-right evaluation, but we do not wish programs to depend on this fact. Indeed, there are some reasons why a clever interpreter might want to evaluate them right-to-left, e.g. to get things on a stack in the correct order.)
     
  67. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). LABELS - We have decided not to use the traditional LABEL primitive in this interpreter because it is difficult to define several mutually recursive functions using only LABEL. The solution, which Hewitt [Smith and Hewitt] also uses, is to adopt an ALGOL-esque block syntax:
      (LABELS <function definition list> <expression>)
    This has the effect of evaluating the expression in an environment where all the functions are defined as specified by the definitions list. Furthermore, the functions are themselves closed in that environment, and not in the outer environment; this allows the functions to call themselves and each other recursively. ……
    BLOCK - This is like the MacLISP PROGN, but arranges to evaluate its last argument without an extra net control frame (explained later), so that the last argument may involved in an iteration. Note that in SCHEME, unlike MacLISP, the body of a LAMBDA expression is not an implicit PROGN.
     
    Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Lambda: The Ultimate Imperative. 维基文库. 1976 (英文). At this point we are almost in a position to model the most general form of compound statement. In LISP, this is called the "PROG feature". In addition to statement sequencing and GO TO statements, one can return a value from a PROG by using the RETURN statement.
    Let us first consider the simplest compound statement, which in SCHEME we call BLOCK. Recall that
        (BLOCK S1 S2) is defined to be ((LAMBDA (DUMMY) S2) S1)
    Notice that this not only performs S1 before S2, but also returns the value of S2. Furthermore, we defined (BLOCK S1 S2 ... Sn) so that it returns the value of Sn. Thus BLOCK may be used as a compound expression, and models a LISP PROGN, which is a PROG with no GO TO statements and an implicit RETURN of the last "statement" (really an expression).
     
    Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978.
    (BLOCK x1 x2 ... xn)
        (BLOCK x) → x
        (BLOCK x . r) → ((LAMBDA (A B) (B)) x (LAMBDA () (BLOCK . r)))

    BLOCK sequentially evaluates the subforms xi from left to right. For example:
        (BLOCK (ASET' X 43) (PRINT X) (+ X 1))
    returns 44 after setting x to 43 and then printing it {Note BLOCK Exploits Applicative Order}.
    (LET ((v1 x1) (v2 x2) ... (vn xn)) . body)
        → ((LAMBDA (v1 v2 ... vn) (BLOCK . body)) x1 x2 ... xn)

    LET provides a convenient syntax for binding several variables to corresponding quantities. It allows the forms for the quantities to appear textually adjacent to their corresponding variables. Notice that the variables are all bound simultaneously, not sequentially, and that the initialization form xi may be evaluated in any order. For convenience, LET also supplies a BLOCK around the forms constituting its body.
     
  68. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). DO - This is like the MacLISP "new-style" DO; old-style DO is not supported. 
  69. ^ Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978 [2021-11-07]. (原始内容存档于2022-04-06). Another difference from LISP is that SCHEME is implemented in such a way that tail-recursions execute without net growth of the interpreter stack. The effect of this is that a procedure call behaves like a GOTO and thus procedure calls can be used to implement iterations, as in PLASMA. 
  70. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). CATCH - This is the "escape operator" which gives the user a handle on the control structure of the interpreter. The expression:
      (CATCH <identifier> <expression>)
    evaluates <expression> in an environment where <identifier> is bound to a continuation which is "just about to return from the CATCH"; that is, if the continuation is called as a function of one argument, then control proceeds as if the CATCH expression had returned with the supplied (evaluated) argument as its value. ……
    As another example, we can define a THROW function, which may then be used with CATCH much as they are in LISP:
      (DEFINE THROW (LAMBDA (TAG RESULT) (TAG RESULT)))
     
  71. ^ David Madore, "call/cc mind-boggler" Portuguese Web Archive的存檔,存档日期2011-01-22
  72. ^ Yin Wang, "Understanding the Yin-Yang Puzzle"
  73. ^ Richard P. Gabriel英语Richard P. Gabriel; Kent M. Pitman英语Kent M. Pitman. Technical Issues of Separation in Function Cells and Value Cells. Lisp and Symbolic Computation. June 1988, 1 (1): 81–101 [2021-11-08]. S2CID 26716515. doi:10.1007/bf01806178. (原始内容存档于2006-11-13). 
  74. ^ Taylor Campbell. SRFI 62: S-expression comments. The SRFI Editors, schemers.org. 2005-07-21 [2012-08-09]. (原始内容存档于2022-04-11). 
  75. ^ Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978 [2021-11-07]. (原始内容存档于2022-04-06). Syntactic Extensions - SCHEME has a syntactic extension mechanism which provides a way to define an identifier to be a magic word, and to associate a function with that word. The function accepts the magic form as an argument, and produces a new form; this new form is then evaluated in place of the original (magic) form. This is precisely the same as the MacLISP macro facility. 
  76. ^ Kohlbecker, E.; Friedman, D. P.; Felleisen, M.; Duba, B. Hygienic Macro Expansion (PDF). ACM conference on LISP and functional programming. 1986 [2021-11-10]. (原始内容 (PDF)存档于2017-08-29). In most current Lisp systems the expander's task is confined to the process of finding syntactic extensions and replacing them by their expansions. This implies, in particular, the each macro function is responsible for the integrity of the program. For Lisp systems (and other languages with similar macro facilities) this means specifically that variable binding must not be corrupted. This, however, is not as simple a task as it sounds. ……
    The real danger of these erroneous macros is that they are treacherous. They work in all cases but one: when the user - or some other macro writer - inadvertently picks the wrong identifier name.
    Various techniques have been proposed to circumvent this capturing problem, but they rely on the individual macro writer. if even one of many macro writers is negligent, the macro system becomes unsafe. We claim that the task of safely renaming macro-generated identifier is mechanical. It is essentially an α-conversion, which is knowledgeable about the origin of the identifiers. For these reasons we propose a change to the navïe macro expansion algorithm which automatically maintains hygienic conditions during expansion time.
     
    Kohlbecker, E; Wand, M. Macro-by-example: Deriving syntactic transformations from their specifications (PDF). Symposium on Principles of Programming Languages. 1987 [2021-11-10]. (原始内容 (PDF)存档于2022-04-12). 
  77. ^ William Clinger and Jonathan Rees, editors. Revised4 Report on the Algorithmic Language Scheme. ACM Lisp Pointers. 1991, 4 (3): 1–55 [2012-08-09]. (原始内容存档于2022-01-22). 
  78. ^ Flatt, Matthew. Binding as sets of scopes. Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2016: 705–717. ISBN 978-1-4503-3549-2. S2CID 15401805. doi:10.1145/2837614.2837620. 
  79. ^ 79.0 79.1 Philip L. Bewig. SRFI 41: Streams. The SRFI Editors, schemers.org. 2008-01-24 [2012-08-09]. (原始内容存档于2021-03-07). 
  80. ^ Gerald J. Sussman, Guy L. Steele Jr.. 链接至维基文库 Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 (英文). EVALUATE - This is similar to the LISP function EVAL. It evaluates its argument, and then evaluates the resulting s-expression as SCHEME code. 
  81. ^ 81.0 81.1 The Scheme of Things: The June 1992 Meeting - Evaluating computed expressions. ACM SIGPLAN, Lisp Pointers, Volume V, Issue 4. 1992 [2021-11-12]. (原始内容存档于2022-04-04). 
  82. ^ Gerald J. Sussman, Guy L. Steele Jr. The Revised Report on SCHEME: A Dialect of LISP. 1978 [2021-11-07]. (原始内容存档于2022-04-06).
      (ENCLOSE fnrep envrep)
    ENCLOSE takes two s-expressions, one representing the code for a procedure, and the other representing the (lexical) environment in which is to run. ENCLOSE returns a (closed) procedure which can be invoked.
    The representation of the code is the standard s-expression description (a lambda-expression). the representation of the environment is an association list (a-list) of the traditional kind:
      ((var1 . value1) (var2 . value2) ...)
    NIL represents the global lexical environment. ……
    The EVALUATE primitive described in [SCHEME] has been removed from the language. We discovered (the hard way) that the straightforward implementation of EVALUATE (evaluate the given expression in the current environment) destroys referential transparency英语referential transparency. We then altered it to evaluate the expression in the top-level environment, but were still disturbed by the extent to which one is tied to a particular representation of a procedure to be executed.
     
  83. ^ William D Clinger. SRFI 6: Basic String Ports. The SRFI Editors, schemers.org. 1999-07-01 [2012-08-09]. (原始内容存档于2021-10-21). 
  84. ^ Scott G. Miller. SRFI 28: Basic Format Strings. The SRFI Editors, schemers.org. 2002-06-25 [2012-08-09]. (原始内容存档于2022-05-08). 
  85. ^ Scheme Systems Supporting SRFIs. The SRFI Editors, schemers.org. 2009-08-30 [2012-08-09]. (原始内容存档于2021-06-20). 
  86. ^ Scheme Benchmarks. 
  87. ^ Brian Harvey, Matthew Wright. Simply Scheme: Introducing Computer Science. 1999 [2021-11-07]. (原始内容存档于2022-05-04). 
  88. ^ Eric Grimson. 6.001 Structure and Interpretation of Computer Programs. MIT Open Courseware. Spring 2005 [2009-10-20]. (原始内容存档于2009-10-01). 
  89. ^ Alex Vandiver, Nelson Elhage; et al. 6.184 - Zombies drink caffeinated 6.001. MIT CSAIL. January 2009 [2009-10-20]. (原始内容存档于2009-08-28). 
  90. ^ Brian Harvey. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley Webcasts. Spring 2011 [2011-12-18]. (原始内容存档于2016-03-16). 
  91. ^ John DeNero. CS 61A Structure and Interpretation of Computer Programs. UC Berkeley. Fall 2011 [2011-12-18]. (原始内容存档于2011-12-29). 
  92. ^ Dov Grobgeld. The GIMP Basic Scheme Tutorial. The GIMP Team. 2002 [2009-10-20]. (原始内容存档于2010-01-24). 
  93. ^ guile-gnome. Free Software Foundation. [2009-10-20]. (原始内容存档于2016-03-04). 

延伸阅读[编辑]

外部链接[编辑]