ALGORITHMIC INFORMATION THEORY - CHAPTER 4

The LISP Interpreter EVAL Trong chương này, chúng tôi chuyển đổi nition de LISP trong LISP được đưa ra trong mục 3,6 vào một chương trình máy đăng ký. Sau đó, chúng tôi biên dịch chương trình máy tính đăng ký vào một phương trình Diophantine theo cấp số nhân. 4,1 Đăng ký Máy Pseudo-Hướng dẫn Bước rẽ để chương trình thông dịch viên cho phiên bản của chúng ta về tinh khiết LISP là viết chương trình con để phá vỡ S-biểu thức ngoài (SPLIT) và đưa chúng trở lại với nhau một lần nữa (JOIN). Bước tiếp theo là. | Chapter 4 The LISP Interpreter EVAL In this chapter we convert the definition of LISP in LISP given in Section into a register machine program. Then we compile this register machine program into an exponential diophantine equation. Register Machine Pseudo-Instructions The first step to program an interpreter for our version of pure LISP is to write subroutines for breaking S-expressions apart SPLIT and for putting them back together again JOIN . The next step is to use SPLIT and JOIN to write routines that push and pop the interpreter stack. Then we can raise the level of discourse by defining register machine pseudo-instructions which are expanded by the assembler into calls to these routines . we extend register machine language with pseudo-machine instructions which expand into several real machine instructions. Thus we have four microcode subroutines SPLIT JOIN PUSH and POP. SPLIT and JOIN are leaf routines and PUSH and POP call SPLIT and JOIN. Figure is a table giving the twelve register machine pseudoinstructions. Now a few words about register usage there are only 19 registers First of all the S-expression to be evaluated is input in EXPRESSION and the value of this S-expression is output in VALUE. There are three 103 104 CHAPTER 4. THE LISP INTERPRETER EVAL Comment Comment is ignored for documentation only R REGISTER Declare the name of a machine register. L LABEL Declare the name of the next instruction. SPLIT T1 T2 S Put the head and tail of s into T1 and T2. HD T s Put the head of s into T. TL T s Put the tail of s into T. EMPTY T Set T to be the empty list . ATOM S L Branch to L if s contains an atom. JN T S1 S2 Join SI to S2 and put the result into T. PUSH s Push s into the STACK. This is equivalent to JN STACK s STACK. POP T Pop T from the STACK. This is equivalent to PŨPL T STACK. PŨPL T s Pop T from the list S T and then put the head of s into replace s by its tail. Figure Register Machine Pseudo-Instructions. In the table above .