Scheme: An Interpreter for Extended Lambda Calculus

Gerald Jay Sussman, Guy L. Steele Jr., 1975, MIT AI Memo 349

About this paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

SCHEME

扩展 Lambda 演算的解释器

Gerald Jay Sussman 和 Guy Lewis Steele Jr.

摘要：

受 ACTORS [Greif and Hewitt] [Smith and Hewitt] 启发，我们实现了一个类似 LISP 的编程语言 SCHEME 的解释器。该编程语言基于 Lambda 演算 [Church]，但扩展了副作用、多进程以及进程同步机制。该实现的目的在于教学。我们希望：

(1) 通过澄清像 LISP 这样的递归宿主语言中非递归控制结构的嵌入方式，减轻由 Micro-PLANNER、CONNIVER 等造成的困惑。

(2) 解释如何使用这些控制结构，而不涉及模式匹配和数据库操作等问题。

(3) 为编程语义和风格中的某些问题提供一个简单具体的实验领域。

本文组织为若干部分。第一部分是一个简短的“参考手册”，包含 SCHEME 所有特殊特性的规范。接下来，我们给出一系列程序示例，用以说明各种程序设计风格以及如何使用它们。这将引出一些语义问题，我们将在第三部分尝试用 Lambda 演算对其进行澄清。在第四部分，我们将对基于 Lambda 演算的编程语言的解释器实现者所面临的问题进行总体讨论。最后，我们将给出一个完全注释的 SCHEME 解释器，该解释器使用 MacLISP [Moon] 编写，以使程序员了解在类似 LISP 这样的递归语言中实现非递归控制结构的技巧。

References

  1. [Bobrow and Wegbreit] Bobrow, Daniel G. and Wegbreit, Ben. "A Model and Stack Implementation of Multiple Environments." CACM 16, 10 (October 1973) pp. 591-603.
  2. [Church] Church, Alonzo: The Calculi of Lambda Conversion. Annals of Mathematics Studies Number 6. Princeton University Press (Princeton, 1941). Reprinted by Klaus Reprint Corp. (New York, 1965).
  3. [Dijkstra] Dijkstra, Edsger W. "Solution of a Problem in Concurrent Programming Control." CACM 8,9 (September 1965) p. 569.
  4. [Fischer] Fischer, Michael J. "Lambda Calculus Schemata." Proceedings of ACM Conference on Proving Assertions about Programs. SIGPLAN Notices (January 1972).
  5. [Galley and Pfister] Galley, S.W. and Pfister, Greg. The MDL Language. Programming Technology Division Document SYS.11.01. Project MAC, MIT (Cambridge, November 1975).
  6. [Greif] Greif, Irene: Semantics of Communicating Parallel Processes. Ph.D. thesis. MAC-TR-154, Project MAC, MIT (Cambrudge, September 1975).
  7. [Greif and Hewitt] Greif, Irene and Hewitt, Carl. Actor Semantics of Planner-73. Working Paper 81, MIT AI Lab (Cambridge, 1975).
  8. [Ingerman] Ingerman, P. Z. "Thunks -- A Way of Compiling Procedure Statements with Some Comments on Procedure Declarations." CACM 4,1 (January 1961) pp. 55-58.
  9. [Knuth] Knuth, Donald E. "Additional Comments on a Problem in Concurrent Programming Control." CACM 9,5 (May 1966) pp. 321-322.
  10. [Lamport] Lamport, Leslie. "A New Solution of Dijkstra's Concurrent Programming Problem." CACM 17,8 (August 1974) pp. 453-455.
  11. [MAC] Project MAC Progress Report XI (July 1973 - July 1974). Project MAC, MIT (Cambridge, 1974).
  12. [McCarthy] McCarthy, John, et al. LISP 1.5 Programmer's Manual. The MIT Press (Cambridge, 1965).
  13. [McDermott and Sussman] McDermott, Drew V. and Sussman, Gerald Jay. The CONNIVER Reference Manual. AI Memo 295a. MIT AI Lab (Cambridge, January 1974).
  14. [Moon] Moon, David A. MACLISP Reference Manual, Revision 0. Project MAC, MIT (Cambridge, April 1974).
  15. [Moses] Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT AI Lab (Cambridge, June 1970).
  16. [Reynolds] Reynolds, John C. "Definitional Interpreters for Higher Order Programming Languages." ACM Conference Proceedings 1972.
  17. [Smith and Hewitt] Smith, Brian C. and Hewitt, Carl. A PLASMA Primer (draft). MIT AI Lab (Cambridge, October 1975).
  18. [Sussman] Sussman, Gerald Jay, Winograd, Terry, and Charniak, Eugene. Micro-PLANNER Reference Manual. AI Memo 203A. MIT AI Lab (Cambridge, December 1971).

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 中文 by gpt-5, against glossary version 6. Translated from the English.