自循環直譯器

自循環直譯器(英語:Meta-circular evaluator)是元直譯器(Metainterpreter,或Self-interpreter)的一種。自循環直譯器不僅是在直譯語言中寫成(如Scheme的自循環直譯器是在Scheme中寫成),而且通過底層語言的功能來實現直譯語言的功能。因此,自循環直譯器不需擔心如何具體實現任何功能,而只需處理語言讀入與直譯,所以尤其適合作為教育用途。自循環直譯器一般在同像(即程式與資料為同一格式,如Lisp)的語言中出現。

自循環直譯器最早出現於約翰·麥卡錫Lisp 1.5版定義,其中麥卡錫以Lisp語言的功能來描述Lisp的直譯規則[1]

Eval/Apply循環

著名電腦科學教科書《计算机程序的构造和解释》詳細研究了一個Scheme語言的自循環直譯器[2]。此書中的直譯器包含兩個主要元素:

  • Eval,即將一個表示式轉換為其取值的函數。
  • Apply,即將一個函數呼叫轉換為其返回值的函數。

這兩個元素互相呼叫,並最終將整個程式轉換為其取值。

實例

例如以下簡單的Scheme表示式(假設square是一個內建函數,其返回值為參數的平方):

(+ (square 2) (square 3))

其直譯過程如下:

  • 直譯器首先將整個程式傳入Eval,而Eval辨認出整個程式是一個函數呼叫(被呼叫的函數是「+」,或加法函數)。因此,Eval會呼叫Apply來處理這一呼叫。
  • Apply收到被呼叫函數為「+」,參數分別為(square 2)(square 3)。因此,Apply分別呼叫Eval來處理這兩個參數。
  • Eval收到表示式為(square 2),這是一個函數呼叫。因此Eval調用Apply。
  • Apply收到被呼叫函數為「square」,參數為2(注意:這裡的「2」僅僅是一個符號,而不是數字)。現在Apply會呼叫Eval,將符號「2」轉換為數值2。Apply隨後呼叫square函數,並返回4。同樣地,Eval處理(square 3)並返回9。
  • 現在直譯器回到了Apply函數,處理「+」的呼叫。現在Apply函數有了參數的具體取值(分別為4和9),並呼叫「+」函數而返回13。
  • Eval函數收到返回值13,這個值是整個表示式的取值。注意以上過程中自循環直譯器並沒有關心具體如何實現「+」函數與「square」函數,這些細節都由底層的Scheme來處理。

參見

註釋

  1. ^ EVALQUOTE的定義,原文在 Lisp 1.5 Programmer's Manual页面存档备份,存于互联网档案馆
  2. ^ 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年3月9日) (英语).