5.5 Compilation (biên dịch)

Bộ explicit-control evaluator (bộ đánh giá điều khiển tường minh) của mục 5.4 là một register machine (máy thanh ghi) mà controller (bộ điều khiển) của nó thực thi các chương trình Scheme. Trong phần này, chúng ta sẽ xem cách chạy các chương trình Scheme trên một register machine mà controller của nó không phải là một Scheme interpreter (bộ thông dịch Scheme).

Máy explicit-control evaluator là một máy tính phổ dụng — nó có thể thực hiện bất kỳ quá trình tính toán nào có thể được mô tả trong Scheme. Controller của evaluator điều phối việc sử dụng các data paths (đường dữ liệu) của nó để thực hiện phép tính mong muốn. Do đó, các data paths của evaluator là phổ dụng: Chúng đủ để thực hiện bất kỳ phép tính nào chúng ta muốn, miễn là có một controller thích hợp.¹

Các máy tính thương mại đa dụng (commercial general-purpose computers) là các register machine được tổ chức xoay quanh một tập hợp các register và các operation tạo thành một tập hợp data paths phổ dụng, hiệu quả và tiện lợi. Controller cho một máy đa dụng là một interpreter cho một register-machine language (ngôn ngữ máy thanh ghi) giống như loại chúng ta đã sử dụng. Ngôn ngữ này được gọi là native language (ngôn ngữ gốc) của máy, hoặc đơn giản là machine language (ngôn ngữ máy). Các chương trình viết bằng machine language là các dãy lệnh sử dụng data paths của máy. Ví dụ, dãy lệnh của explicit-control evaluator có thể được xem như một chương trình machine language cho một máy tính đa dụng, thay vì là controller cho một máy thông dịch chuyên biệt.

Có hai chiến lược phổ biến để thu hẹp khoảng cách giữa các ngôn ngữ bậc cao và register-machine language. Explicit-control evaluator minh họa chiến lược interpretation (thông dịch). Một interpreter viết bằng native language của một máy sẽ cấu hình máy đó để thực thi các chương trình viết bằng một ngôn ngữ (gọi là source language — ngôn ngữ nguồn) có thể khác với native language của máy thực hiện việc đánh giá. Các primitive procedure (thủ tục nguyên thủy) của source language được cài đặt như một thư viện các subroutine viết bằng native language của máy đó. Một chương trình cần được thông dịch (gọi là source program — chương trình nguồn) được biểu diễn như một cấu trúc dữ liệu. Interpreter sẽ duyệt qua cấu trúc dữ liệu này, phân tích source program. Khi làm vậy, nó mô phỏng hành vi dự kiến của source program bằng cách gọi các primitive subroutine thích hợp từ thư viện.

Trong phần này, chúng ta sẽ khám phá chiến lược thay thế là compilation (biên dịch). Một compiler (trình biên dịch) cho một source language và một máy nhất định sẽ dịch một source program thành một chương trình tương đương (gọi là object program — chương trình đích) viết bằng native language của máy đó. Compiler mà chúng ta triển khai trong phần này sẽ dịch các chương trình viết bằng Scheme thành các dãy lệnh được thực thi bằng data paths của máy explicit-control evaluator.²

So với interpretation, compilation có thể mang lại sự gia tăng đáng kể về hiệu suất thực thi chương trình, như chúng ta sẽ giải thích bên dưới trong phần tổng quan về compiler. Mặt khác, một interpreter cung cấp một môi trường mạnh mẽ hơn cho việc phát triển và gỡ lỗi chương trình tương tác, vì source program đang được thực thi có sẵn tại thời điểm chạy để kiểm tra và chỉnh sửa. Ngoài ra, vì toàn bộ thư viện primitive có sẵn, các chương trình mới có thể được xây dựng và thêm vào hệ thống trong quá trình gỡ lỗi.

Xét đến các ưu điểm bổ sung của compilation và interpretation, các môi trường phát triển chương trình hiện đại thường áp dụng chiến lược kết hợp. Các Lisp interpreter thường được tổ chức sao cho các interpreted procedure và compiled procedure có thể gọi lẫn nhau. Điều này cho phép lập trình viên biên dịch những phần của chương trình được cho là đã gỡ lỗi xong, từ đó tận dụng lợi thế hiệu suất của compilation, đồng thời giữ chế độ thực thi thông dịch cho những phần của chương trình vẫn đang trong quá trình phát triển và gỡ lỗi tương tác. Trong mục 5.5.7, sau khi chúng ta đã triển khai compiler, chúng ta sẽ chỉ ra cách kết nối nó với interpreter của mình để tạo ra một hệ thống phát triển tích hợp interpreter-compiler.

An overview of the compiler (Tổng quan về compiler)

Compiler (trình biên dịch) của chúng ta rất giống với interpreter (bộ thông dịch), cả về cấu trúc lẫn chức năng mà nó thực hiện. Do đó, các cơ chế mà compiler sử dụng để phân tích expression (biểu thức) sẽ tương tự như những gì interpreter sử dụng. Hơn nữa, để dễ dàng kết nối giữa mã đã biên dịch và mã thông dịch, chúng ta sẽ thiết kế compiler để sinh ra mã tuân theo cùng một quy ước sử dụng register (thanh ghi) như interpreter: Environment sẽ được giữ trong register env, danh sách đối số sẽ được tích lũy trong argl, một procedure (thủ tục) cần áp dụng sẽ nằm trong proc, các procedure sẽ trả kết quả vào val, và vị trí mà một procedure cần trả về sẽ được giữ trong continue. Nói chung, compiler dịch một source program (chương trình nguồn) thành một object program (chương trình đích) thực hiện về cơ bản cùng các thao tác trên register như interpreter khi đánh giá cùng một source program.

Mô tả này gợi ý một chiến lược để triển khai một compiler sơ khai: Chúng ta duyệt qua expression theo cùng cách mà interpreter làm. Khi gặp một lệnh trên register mà interpreter sẽ thực hiện khi đánh giá expression, chúng ta không thực thi lệnh đó mà thay vào đó tích lũy nó vào một dãy lệnh. Dãy lệnh thu được sẽ là object code (mã đích). Hãy lưu ý lợi thế về hiệu suất của compilation (biên dịch) so với interpretation (thông dịch). Mỗi lần interpreter đánh giá một expression — ví dụ (f 84 96) — nó thực hiện công việc phân loại expression (phát hiện đây là một procedure application — lời gọi thủ tục) và kiểm tra kết thúc danh sách toán hạng (phát hiện rằng có hai toán hạng). Với compiler, expression chỉ được phân tích một lần, khi dãy lệnh được sinh ra tại thời điểm biên dịch. Object code do compiler tạo ra chỉ chứa các lệnh đánh giá operator và hai toán hạng, lắp ráp danh sách đối số, và áp dụng procedure (trong proc) cho các đối số (trong argl).

Đây là cùng loại tối ưu hóa mà chúng ta đã triển khai trong analyzing evaluator (bộ đánh giá phân tích) ở mục 4.1.7. Nhưng vẫn còn nhiều cơ hội khác để tăng hiệu suất trong mã đã biên dịch. Khi interpreter chạy, nó tuân theo một quy trình phải áp dụng được cho bất kỳ expression nào trong ngôn ngữ. Ngược lại, một đoạn mã đã biên dịch cụ thể được tạo ra để thực thi một expression nhất định. Điều này có thể tạo ra sự khác biệt lớn, ví dụ trong việc sử dụng stack (ngăn xếp) để lưu register. Khi interpreter đánh giá một expression, nó phải chuẩn bị cho mọi tình huống. Trước khi đánh giá một subexpression (biểu thức con), interpreter lưu tất cả các register sẽ cần sau này, vì subexpression có thể yêu cầu một quá trình đánh giá bất kỳ. Compiler, ngược lại, có thể tận dụng cấu trúc của expression cụ thể mà nó đang xử lý để sinh ra mã tránh các thao tác stack không cần thiết.

Ví dụ, xét combination (f 84 96). Trước khi interpreter đánh giá operator của combination, nó chuẩn bị cho việc đánh giá này bằng cách lưu các register chứa các toán hạng và environment, những giá trị sẽ cần sau đó. Interpreter sau đó đánh giá operator để thu kết quả vào val, khôi phục các register đã lưu, và cuối cùng chuyển kết quả từ val sang proc. Tuy nhiên, trong expression cụ thể này, operator là ký hiệu f, việc đánh giá nó được thực hiện bởi machine operation (thao tác máy) lookup-variable-value, vốn không thay đổi bất kỳ register nào. Compiler mà chúng ta triển khai trong phần này sẽ tận dụng điều này và sinh ra mã đánh giá operator bằng lệnh:

(assign proc 
        (op lookup-variable-value)
        (const f)
        (reg env))

Đoạn mã này không chỉ tránh việc lưu và khôi phục không cần thiết mà còn gán trực tiếp giá trị tra cứu vào proc, trong khi interpreter sẽ lấy kết quả vào val rồi mới chuyển sang proc.

Một compiler cũng có thể tối ưu hóa việc truy cập environment. Sau khi phân tích mã, compiler trong nhiều trường hợp có thể biết biến cụ thể nằm ở frame (khung) nào và truy cập trực tiếp frame đó, thay vì thực hiện tìm kiếm lookup-variable-value. Chúng ta sẽ thảo luận cách triển khai việc truy cập biến như vậy ở mục 5.5.6. Cho đến lúc đó, chúng ta sẽ tập trung vào loại tối ưu hóa register và stack như đã mô tả ở trên. Có nhiều tối ưu hóa khác mà compiler có thể thực hiện, chẳng hạn như mã hóa các primitive operation (thao tác nguyên thủy) “in line” thay vì sử dụng cơ chế apply tổng quát (xem Bài tập 5.38); nhưng chúng ta sẽ không nhấn mạnh vào chúng ở đây. Mục tiêu chính của chúng ta trong phần này là minh họa quá trình compilation trong một bối cảnh đơn giản hóa (nhưng vẫn thú vị).

5.5.1 Structure of the Compiler (Cấu trúc của compiler)

Trong mục 4.1.7, chúng ta đã chỉnh sửa metacircular interpreter (bộ thông dịch siêu vòng) ban đầu để tách biệt phân tích và thực thi. Chúng ta phân tích từng expression để tạo ra một execution procedure (thủ tục thực thi) nhận environment làm đối số và thực hiện các thao tác cần thiết. Trong compiler, chúng ta về cơ bản sẽ thực hiện cùng một phân tích. Tuy nhiên, thay vì tạo ra các execution procedure, chúng ta sẽ sinh ra các dãy lệnh để chạy trên register machine của mình.

Procedure compile là bộ phân phối (dispatch) cấp cao nhất trong compiler. Nó tương ứng với procedure eval ở mục 4.1.1, procedure analyze ở mục 4.1.7, và điểm vào eval-dispatch của explicit-control-evaluator (bộ đánh giá điều khiển tường minh) ở mục 5.4.1. Compiler, giống như các interpreter, sử dụng các expression-syntax procedure (thủ tục cú pháp biểu thức) được định nghĩa ở mục 4.1.2.³ Compile thực hiện phân tích theo từng trường hợp dựa trên loại cú pháp của expression cần biên dịch. Với mỗi loại expression, nó sẽ phân phối đến một code generator (bộ sinh mã) chuyên biệt:

(define (compile exp target linkage)
  (cond ((self-evaluating? exp)
         (compile-self-evaluating 
          exp target linkage))
        ((quoted? exp) 
         (compile-quoted exp target linkage))
        ((variable? exp)
         (compile-variable 
          exp target linkage))
        ((assignment? exp)
         (compile-assignment
          exp target linkage))
        ((definition? exp)
         (compile-definition
          exp target linkage))
        ((if? exp)
         (compile-if exp target linkage))
        ((lambda? exp)
         (compile-lambda exp target linkage))
        ((begin? exp)
         (compile-sequence 
          (begin-actions exp) target linkage))
        ((cond? exp) 
         (compile 
          (cond->if exp) target linkage))
        ((application? exp)
         (compile-application 
          exp target linkage))
        (else
         (error "Unknown expression type: 
                 COMPILE" 
                exp))))

Targets and linkages (Mục tiêu và liên kết)

Compile và các code generator (bộ sinh mã) mà nó gọi nhận hai đối số bổ sung ngoài expression (biểu thức) cần biên dịch. Có một target (mục tiêu), chỉ định register (thanh ghi) mà mã đã biên dịch sẽ trả về giá trị của expression. Ngoài ra còn có một linkage descriptor (bộ mô tả liên kết), mô tả cách mà mã thu được từ việc biên dịch expression sẽ tiếp tục khi nó đã hoàn tất việc thực thi. Linkage descriptor có thể yêu cầu mã thực hiện một trong ba việc sau:

• tiếp tục tại lệnh kế tiếp trong chuỗi (điều này được chỉ định bởi linkage descriptor next),
• trả về từ procedure (thủ tục) đang được biên dịch (điều này được chỉ định bởi linkage descriptor return), hoặc
• nhảy đến một entry point (điểm vào) được đặt tên (điều này được chỉ định bằng cách sử dụng label được chỉ định làm linkage descriptor).

Ví dụ, biên dịch expression 5 (là self-evaluating — tự đánh giá) với target là register val và linkage là next sẽ tạo ra lệnh:

(assign val (const 5))

Biên dịch cùng expression đó với linkage là return sẽ tạo ra các lệnh:

(assign val (const 5))
(goto (reg continue))

Trong trường hợp đầu tiên, việc thực thi sẽ tiếp tục với lệnh kế tiếp trong chuỗi. Trong trường hợp thứ hai, chúng ta sẽ trả về từ một lời gọi procedure. Trong cả hai trường hợp, giá trị của expression sẽ được đặt vào target register val.

Instruction sequences and stack usage (Chuỗi lệnh và việc sử dụng stack)

Mỗi code generator trả về một instruction sequence (chuỗi lệnh) chứa object code (mã đích) mà nó đã sinh ra cho expression. Việc sinh mã cho một compound expression (biểu thức phức hợp) được thực hiện bằng cách kết hợp đầu ra từ các code generator đơn giản hơn cho các component expression (biểu thức thành phần), tương tự như việc đánh giá một compound expression được thực hiện bằng cách đánh giá các component expression.

Phương pháp đơn giản nhất để kết hợp các instruction sequence là một procedure gọi là append-instruction-sequences. Nó nhận làm đối số bất kỳ số lượng instruction sequence nào cần được thực thi tuần tự; nó nối chúng lại và trả về chuỗi đã kết hợp. Nghĩa là, nếu $\langle\mspace{2mu} seq_{1}\rangle$ và $\langle\mspace{2mu} seq_{2}\rangle$ là các chuỗi lệnh, thì việc đánh giá

(append-instruction-sequences ⟨seq₁⟩ ⟨seq₂⟩)

sẽ tạo ra chuỗi:

⟨seq₁⟩
⟨seq₂⟩

Bất cứ khi nào các register có thể cần được lưu, các code generator của compiler sẽ sử dụng preserving, đây là một phương pháp tinh vi hơn để kết hợp các instruction sequence. Preserving nhận ba đối số: một tập hợp register và hai instruction sequence cần được thực thi tuần tự. Nó nối các chuỗi theo cách mà nội dung của mỗi register trong tập hợp được bảo toàn trong suốt quá trình thực thi chuỗi thứ nhất, nếu điều này là cần thiết cho việc thực thi chuỗi thứ hai. Nghĩa là, nếu chuỗi thứ nhất thay đổi register và chuỗi thứ hai thực sự cần giá trị ban đầu của register, thì preserving sẽ bao bọc một lệnh save và một lệnh restore cho register đó xung quanh chuỗi thứ nhất trước khi nối các chuỗi. Nếu không, preserving chỉ đơn giản trả về các instruction sequence đã được nối. Do đó, ví dụ (preserving (list ⟨reg₁⟩ ⟨reg₂⟩) ⟨seg₁⟩ ⟨seg₂⟩) sẽ tạo ra một trong bốn chuỗi lệnh sau, tùy thuộc vào cách $\langle\mspace{2mu} seq_{1}\rangle$ và $\langle\mspace{2mu} seq_{2}\rangle$ sử dụng $\langle\mspace{2mu} reg_{1}\rangle$ và $\langle\mspace{2mu} reg_{2}\rangle$:

....

Bằng cách sử dụng preserving để kết hợp các instruction sequence, compiler tránh được các thao tác stack không cần thiết. Điều này cũng tách biệt chi tiết về việc có sinh ra lệnh save và restore hay không trong procedure preserving, tách chúng khỏi các vấn đề phát sinh khi viết từng code generator riêng lẻ. Thực tế, không có lệnh save hoặc restore nào được sinh ra một cách tường minh bởi các code generator.

Về nguyên tắc, chúng ta có thể biểu diễn một instruction sequence đơn giản như một danh sách các lệnh. Append-instruction-sequences khi đó có thể kết hợp các instruction sequence bằng cách thực hiện phép nối (append) danh sách thông thường. Tuy nhiên, preserving khi đó sẽ là một thao tác phức tạp, vì nó sẽ phải phân tích từng instruction sequence để xác định cách chuỗi đó sử dụng các register. Preserving sẽ vừa kém hiệu quả vừa phức tạp, vì nó sẽ phải phân tích từng đối số instruction sequence của mình, ngay cả khi các chuỗi này có thể đã được tạo ra bởi các lời gọi preserving, trong trường hợp đó các phần của chúng đã được phân tích rồi. Để tránh việc phân tích lặp lại như vậy, chúng ta sẽ gắn kèm với mỗi instruction sequence một số thông tin về cách nó sử dụng register. Khi chúng ta tạo một instruction sequence cơ bản, chúng ta sẽ cung cấp thông tin này một cách tường minh, và các procedure kết hợp instruction sequence sẽ suy ra thông tin sử dụng register cho chuỗi kết hợp từ thông tin gắn với các chuỗi thành phần.

Một instruction sequence sẽ chứa ba loại thông tin:

• tập hợp các register phải được khởi tạo trước khi các lệnh trong chuỗi được thực thi (các register này được gọi là needed — cần thiết — bởi chuỗi),
• tập hợp các register có giá trị bị thay đổi bởi các lệnh trong chuỗi, và
• các lệnh thực tế (cũng gọi là statement) trong chuỗi.

Chúng ta sẽ biểu diễn một instruction sequence như một danh sách gồm ba phần này. Constructor (hàm tạo) cho instruction sequence như sau:

(define (make-instruction-sequence 
         needs modifies statements)
  (list needs modifies statements))

For example, the two-instruction sequence that looks up the value of the variable x in the current environment, assigns the result to val, and then returns, requires registers env and continue to have been initialized, and modifies register val. This sequence would therefore be constructed as

(make-instruction-sequence
 '(env continue)
 '(val)
 '((assign val
           (op lookup-variable-value)
           (const x)
           (reg env))
   (goto (reg continue))))

We sometimes need to construct an instruction sequence with no statements:

(define (empty-instruction-sequence)
  (make-instruction-sequence '() '() '()))

5.5.2 Compiling Expressions (Biên dịch các biểu thức)

Trong phần này và phần tiếp theo, chúng ta sẽ triển khai các code generator (bộ sinh mã) mà procedure (thủ tục) compile sẽ phân phối đến.

Compiling linkage code (Biên dịch mã liên kết)

Nói chung, đầu ra của mỗi code generator sẽ kết thúc bằng các lệnh — được sinh ra bởi procedure compile-linkage — để thực hiện linkage (liên kết) yêu cầu. Nếu linkage là return thì chúng ta phải sinh ra lệnh (goto (reg continue)). Lệnh này cần register continue và không thay đổi bất kỳ register nào. Nếu linkage là next, thì chúng ta không cần thêm bất kỳ lệnh nào khác. Ngược lại, nếu linkage là một label (nhãn), chúng ta sẽ sinh ra một lệnh goto đến label đó, đây là một lệnh không cần hoặc thay đổi bất kỳ register nào.⁴

(define (compile-linkage linkage)
  (cond ((eq? linkage 'return)
         (make-instruction-sequence 
          '(continue)
          '()
          '((goto (reg continue)))))
        ((eq? linkage 'next)
         (empty-instruction-sequence))
        (else
         (make-instruction-sequence '() '()
          `((goto (label ,linkage)))))))

Mã liên kết được nối vào một instruction sequence (chuỗi lệnh) bằng cách preserving register continue, vì một linkage kiểu return sẽ yêu cầu register continue: Nếu instruction sequence đã cho thay đổi continue và mã liên kết cần nó, continue sẽ được lưu và khôi phục.

(define (end-with-linkage 
         linkage instruction-sequence)
  (preserving '(continue)
   instruction-sequence
   (compile-linkage linkage)))

Compiling simple expressions (Biên dịch các biểu thức đơn giản)

Các code generator cho self-evaluating expression (biểu thức tự đánh giá), quotation (trích dẫn), và variable (biến) sẽ tạo ra các instruction sequence gán giá trị cần thiết vào target register (thanh ghi đích) và sau đó tiếp tục như được chỉ định bởi linkage descriptor (bộ mô tả liên kết).

(define (compile-self-evaluating 
         exp target linkage)
  (end-with-linkage
   linkage (make-instruction-sequence 
            '()
            (list target)
            `((assign ,target (const ,exp))))))

(define (compile-quoted exp target linkage)
  (end-with-linkage
   linkage
   (make-instruction-sequence
    '()
    (list target)
    `((assign 
       ,target
       (const ,(text-of-quotation exp)))))))

(define (compile-variable
         exp target linkage)
  (end-with-linkage 
   linkage
   (make-instruction-sequence 
    '(env)
    (list target)
    `((assign ,target
              (op lookup-variable-value)
              (const ,exp)
              (reg env))))))

Tất cả các lệnh gán này đều thay đổi target register, và lệnh tra cứu một biến cần register env.

Assignment (gán) và definition (định nghĩa) được xử lý gần giống như trong interpreter. Chúng ta đệ quy sinh mã tính giá trị sẽ được gán cho biến, và nối vào đó một instruction sequence gồm hai lệnh thực sự đặt hoặc định nghĩa biến và gán giá trị của toàn bộ expression (ký hiệu ok) vào target register. Việc biên dịch đệ quy này có target là val và linkage là next để mã sẽ đặt kết quả vào val và tiếp tục với mã được nối sau nó. Việc nối này được thực hiện với preserving env, vì environment (môi trường) là cần thiết để đặt hoặc định nghĩa biến, và mã cho giá trị biến có thể là kết quả biên dịch của một expression phức tạp có thể thay đổi các register theo nhiều cách khác nhau.

(define (compile-assignment 
         exp target linkage)
  (let ((var (assignment-variable exp))
        (get-value-code
         (compile (assignment-value exp) 
                  'val
                  'next)))
    (end-with-linkage 
     linkage
     (preserving 
      '(env)
      get-value-code
      (make-instruction-sequence
       '(env val)
       (list target)
       `((perform (op set-variable-value!)
                  (const ,var)
                  (reg val)
                  (reg env))
         (assign ,target (const ok))))))))

(define (compile-definition 
         exp target linkage)
  (let ((var (definition-variable exp))
        (get-value-code
         (compile (definition-value exp)
                  'val
                  'next)))
    (end-with-linkage
     linkage
     (preserving 
      '(env)
      get-value-code
      (make-instruction-sequence
       '(env val)
       (list target)
       `((perform (op define-variable!)
                  (const ,var)
                  (reg val)
                  (reg env))
         (assign ,target (const ok))))))))

Instruction sequence gồm hai lệnh được nối thêm này yêu cầu env và val và thay đổi target. Lưu ý rằng mặc dù chúng ta bảo toàn env cho chuỗi này, nhưng chúng ta không bảo toàn val, vì get-value-code được thiết kế để đặt kết quả của nó vào val một cách tường minh để chuỗi này sử dụng. (Thực tế, nếu chúng ta bảo toàn val, chúng ta sẽ gặp lỗi, vì điều này sẽ khiến nội dung trước đó của val được khôi phục ngay sau khi get-value-code chạy.)

Compiling conditional expressions (Biên dịch các biểu thức điều kiện)

Mã cho một if expression (biểu thức if) được biên dịch với một target và linkage cho trước có dạng:

⟨compilation of predicate, 
 target val, linkage next⟩
 (test (op false?) (reg val))
 (branch (label false-branch))
true-branch
 ⟨compilation of consequent with given 
  target and given linkage or after-if⟩
false-branch
 ⟨compilation of alternative 
  with given target and linkage⟩
after-if

Để sinh ra mã này, chúng ta biên dịch predicate (mệnh đề điều kiện), consequent (nhánh đúng), và alternative (nhánh sai), và kết hợp mã thu được với các lệnh để kiểm tra kết quả của predicate cùng với các label mới được tạo để đánh dấu các nhánh đúng và sai, cũng như điểm kết thúc của câu lệnh điều kiện.⁵ Trong cách sắp xếp mã này, chúng ta phải rẽ nhánh bỏ qua nhánh đúng nếu phép kiểm tra là sai. Chỉ có một chút phức tạp ở cách xử lý linkage cho nhánh đúng. Nếu linkage cho câu điều kiện là return hoặc một label, thì cả nhánh đúng và nhánh sai sẽ cùng sử dụng linkage này. Nếu linkage là next, nhánh đúng sẽ kết thúc bằng một lệnh nhảy qua mã của nhánh sai đến label ở cuối câu điều kiện.

(define (compile-if exp target linkage)
  (let ((t-branch (make-label 'true-branch))
        (f-branch (make-label 'false-branch))
        (after-if (make-label 'after-if)))
    (let ((consequent-linkage
           (if (eq? linkage 'next) 
               after-if
               linkage)))
      (let ((p-code 
             (compile (if-predicate exp)
                      'val
                      'next))
            (c-code
             (compile (if-consequent exp) 
                      target 
                      consequent-linkage))
            (a-code
             (compile (if-alternative exp)
                      target
                      linkage)))
        (preserving 
         '(env continue)
         p-code
         (append-instruction-sequences
          (make-instruction-sequence 
           '(val) 
           '()
           `((test (op false?) (reg val))
             (branch (label ,f-branch))))
          (parallel-instruction-sequences
           (append-instruction-sequences 
            t-branch c-code)
           (append-instruction-sequences
            f-branch a-code))
          after-if))))))

Env được bảo toàn xung quanh mã predicate (mệnh đề điều kiện) vì nó có thể cần được sử dụng bởi cả nhánh đúng và nhánh sai, và continue được bảo toàn vì nó có thể cần cho mã linkage (liên kết) trong các nhánh đó. Mã cho các nhánh đúng và sai (không được thực thi tuần tự) được nối lại bằng một bộ kết hợp đặc biệt parallel-instruction-sequences được mô tả trong mục 5.5.4.

Lưu ý rằng cond là một derived expression (biểu thức dẫn xuất), vì vậy tất cả những gì compiler (trình biên dịch) cần làm để xử lý nó là áp dụng transformer cond->if (từ mục 4.1.2) và biên dịch if expression (biểu thức if) thu được.

Compiling sequences (Biên dịch các chuỗi lệnh)

Việc biên dịch các sequence (chuỗi lệnh) — từ phần thân procedure (thủ tục) hoặc các begin tường minh — tương tự như quá trình đánh giá chúng. Mỗi expression (biểu thức) trong chuỗi được biên dịch — expression cuối cùng với linkage được chỉ định cho chuỗi, và các expression khác với linkage là next (để thực thi phần còn lại của chuỗi). Các instruction sequence (chuỗi lệnh) cho từng expression riêng lẻ được nối lại để tạo thành một instruction sequence duy nhất, sao cho env (cần cho phần còn lại của chuỗi) và continue (có thể cần cho linkage ở cuối chuỗi) được bảo toàn.

(define (compile-sequence seq target linkage)
  (if (last-exp? seq)
      (compile (first-exp seq) target linkage)
      (preserving '(env continue)
       (compile (first-exp seq) target 'next)
       (compile-sequence (rest-exps seq)
                         target
                         linkage))))

Compiling lambda expressions (Biên dịch các biểu thức lambda)

Các lambda expression (biểu thức lambda) tạo ra procedure. Object code (mã đích) cho một lambda expression phải có dạng:

⟨construct procedure object 
 and assign it to target register⟩
⟨linkage⟩

Khi chúng ta biên dịch lambda expression, chúng ta cũng sinh ra mã cho phần thân procedure. Mặc dù phần thân sẽ không được thực thi tại thời điểm tạo procedure, nhưng việc chèn nó vào object code ngay sau mã cho lambda là thuận tiện. Nếu linkage cho lambda expression là một label hoặc return, điều này là ổn. Nhưng nếu linkage là next, chúng ta sẽ cần bỏ qua mã cho phần thân procedure bằng cách sử dụng một linkage nhảy đến một label được chèn sau phần thân. Object code do đó sẽ có dạng:

⟨construct procedure object 
 and assign it to target register⟩
 ⟨code for given linkage⟩ or 
  (goto (label after-lambda))
 ⟨compilation of procedure body⟩
after-lambda

Compile-lambda sinh ra mã để tạo procedure object (đối tượng thủ tục) theo sau là mã cho phần thân procedure. Procedure object sẽ được tạo tại thời gian chạy bằng cách kết hợp environment hiện tại (môi trường tại thời điểm định nghĩa) với entry point (điểm vào) của phần thân procedure đã biên dịch (một label mới được tạo ra)⁶.

(define (compile-lambda exp target linkage)
  (let ((proc-entry 
         (make-label 'entry))
        (after-lambda 
         (make-label 'after-lambda)))
    (let ((lambda-linkage
           (if (eq? linkage 'next)
               after-lambda
               linkage)))
      (append-instruction-sequences
       (tack-on-instruction-sequence
        (end-with-linkage 
         lambda-linkage
         (make-instruction-sequence 
          '(env)
          (list target)
          `((assign 
             ,target
             (op make-compiled-procedure)
             (label ,proc-entry)
             (reg env)))))
        (compile-lambda-body exp proc-entry))
       after-lambda))))

Compile-lambda sử dụng bộ kết hợp đặc biệt tack-on-instruction-sequence thay vì append-instruction-sequences (5.5.4) để nối phần thân procedure (thủ tục) vào mã của lambda expression (biểu thức lambda), bởi vì phần thân không phải là một phần của chuỗi lệnh sẽ được thực thi khi chuỗi kết hợp được bắt đầu; thay vào đó, nó nằm trong chuỗi chỉ vì đó là một vị trí thuận tiện để đặt nó.

Compile-lambda-body tạo mã cho phần thân của procedure. Mã này bắt đầu bằng một label (nhãn) cho entry point (điểm vào). Tiếp theo là các lệnh sẽ khiến run-time evaluation environment (môi trường đánh giá tại thời gian chạy) chuyển sang environment (môi trường) thích hợp để đánh giá phần thân procedure — cụ thể là definition environment (môi trường định nghĩa) của procedure, được mở rộng để bao gồm các binding (ràng buộc) của các formal parameter (tham số hình thức) với các đối số mà procedure được gọi. Sau đó là mã cho chuỗi các expression (biểu thức) tạo thành phần thân procedure. Chuỗi này được biên dịch với linkage là return và target là val để nó sẽ kết thúc bằng việc trả về từ procedure với kết quả nằm trong val.

(define (compile-lambda-body exp proc-entry)
  (let ((formals (lambda-parameters exp)))
    (append-instruction-sequences
     (make-instruction-sequence 
      '(env proc argl)
      '(env)
      `(,proc-entry
        (assign env 
                (op compiled-procedure-env)
                (reg proc))
        (assign env
                (op extend-environment)
                (const ,formals)
                (reg argl)
                (reg env))))
     (compile-sequence (lambda-body exp)
                       'val
                       'return))))

5.5.3 Compiling Combinations (Biên dịch các tổ hợp)

Cốt lõi của quá trình compilation (biên dịch) là biên dịch các procedure application (lời gọi thủ tục). Mã cho một combination (tổ hợp) được biên dịch với một target và linkage cho trước có dạng:

⟨compilation of operator, 
 target proc, linkage next⟩
⟨evaluate operands and construct 
 argument list in argl⟩
⟨compilation of procedure call 
 with given target and linkage⟩

Các register env, proc, và argl có thể cần được lưu và khôi phục trong quá trình đánh giá operator và operand. Lưu ý rằng đây là nơi duy nhất trong compiler (trình biên dịch) mà một target khác val được chỉ định.

Mã cần thiết được sinh ra bởi compile-application. Thủ tục này đệ quy biên dịch operator để tạo mã đưa procedure cần áp dụng vào proc, và biên dịch các operand để tạo mã đánh giá từng operand riêng lẻ của application. Các instruction sequence (chuỗi lệnh) cho các operand được kết hợp (bởi construct-arglist) với mã tạo danh sách đối số trong argl, và mã danh sách đối số thu được được kết hợp với mã procedure và mã thực hiện lời gọi procedure (được sinh ra bởi compile-procedure-call). Khi nối các chuỗi mã, register env phải được bảo toàn xung quanh việc đánh giá operator (vì việc đánh giá operator có thể thay đổi env, vốn sẽ cần để đánh giá các operand), và register proc phải được bảo toàn xung quanh việc tạo danh sách đối số (vì việc đánh giá các operand có thể thay đổi proc, vốn sẽ cần cho việc áp dụng procedure thực tế). Continue cũng phải được bảo toàn trong suốt quá trình, vì nó cần cho linkage trong lời gọi procedure.

(define (compile-application 
         exp target linkage)
  (let ((proc-code 
         (compile (operator exp) 'proc 'next))
        (operand-codes
         (map (lambda (operand)
                (compile operand 'val 'next))
              (operands exp))))
    (preserving 
     '(env continue)
     proc-code
     (preserving 
      '(proc continue)
      (construct-arglist operand-codes)
      (compile-procedure-call 
       target
       linkage)))))

Mã để tạo danh sách đối số sẽ đánh giá từng operand vào val và sau đó cons giá trị đó vào danh sách đối số đang được tích lũy trong argl. Vì chúng ta cons các đối số vào argl theo thứ tự, chúng ta phải bắt đầu với đối số cuối cùng và kết thúc với đối số đầu tiên, để các đối số xuất hiện theo thứ tự từ đầu đến cuối trong danh sách kết quả. Thay vì lãng phí một lệnh để khởi tạo argl thành danh sách rỗng nhằm chuẩn bị cho chuỗi đánh giá này, chúng ta để chuỗi mã đầu tiên tạo argl ban đầu. Dạng tổng quát của việc tạo danh sách đối số như sau:

⟨compilation of last operand, targeted to val⟩
(assign argl (op list) (reg val))
⟨compilation of next operand, targeted to val⟩
(assign argl (op cons) (reg val) (reg argl))
…
⟨compilation of first operand, targeted to val⟩
(assign argl (op cons) (reg val) (reg argl))

Argl phải được bảo toàn xung quanh mỗi lần đánh giá operand ngoại trừ lần đầu tiên (để các đối số đã tích lũy không bị mất), và env phải được bảo toàn xung quanh mỗi lần đánh giá operand ngoại trừ lần cuối (để sử dụng cho các lần đánh giá operand tiếp theo).

Việc biên dịch mã đối số này hơi phức tạp, vì cách xử lý đặc biệt đối với operand đầu tiên được đánh giá và nhu cầu bảo toàn argl và env ở các vị trí khác nhau. Procedure construct-arglist nhận làm đối số mã đánh giá từng operand riêng lẻ. Nếu không có operand nào, nó chỉ đơn giản phát ra lệnh:

(assign argl (const ()))

Ngược lại, construct-arglist tạo mã khởi tạo argl với đối số cuối cùng, và nối thêm mã đánh giá các đối số còn lại và gắn chúng vào argl lần lượt. Để xử lý các đối số từ cuối đến đầu, chúng ta phải đảo ngược danh sách các chuỗi mã operand từ thứ tự được cung cấp bởi compile-application.

(define (construct-arglist operand-codes)
  (let ((operand-codes 
         (reverse operand-codes)))
    (if (null? operand-codes)
        (make-instruction-sequence 
         '() 
         '(argl)
         '((assign argl (const ()))))
        (let ((code-to-get-last-arg
               (append-instruction-sequences
                (car operand-codes)
                (make-instruction-sequence 
                 '(val)
                 '(argl)
                 '((assign argl
                           (op list)
                           (reg val)))))))
          (if (null? (cdr operand-codes))
              code-to-get-last-arg
              (preserving 
               '(env)
               code-to-get-last-arg
               (code-to-get-rest-args
                (cdr operand-codes))))))))

(define (code-to-get-rest-args operand-codes)
  (let ((code-for-next-arg
         (preserving 
          '(argl)
          (car operand-codes)
          (make-instruction-sequence 
           '(val argl)
           '(argl)
           '((assign argl
                     (op cons)
                     (reg val)
                     (reg argl)))))))
    (if (null? (cdr operand-codes))
        code-for-next-arg
        (preserving 
         '(env)
         code-for-next-arg
         (code-to-get-rest-args 
          (cdr operand-codes))))))

Applying procedures (Áp dụng các thủ tục)

Sau khi đánh giá các thành phần của một combination, mã đã biên dịch phải áp dụng procedure trong proc cho các đối số trong argl. Mã này thực hiện về cơ bản cùng một dispatch (phân phối) như procedure apply trong metacircular evaluator (bộ đánh giá siêu vòng) ở mục 4.1.1 hoặc entry point apply-dispatch trong explicit-control evaluator (bộ đánh giá điều khiển tường minh) ở mục 5.4.1. Nó kiểm tra xem procedure cần áp dụng là primitive procedure (thủ tục nguyên thủy) hay compiled procedure (thủ tục đã biên dịch). Với primitive procedure, nó sử dụng apply-primitive-procedure; chúng ta sẽ sớm thấy cách nó xử lý compiled procedure. Mã áp dụng procedure có dạng sau:

(test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch))
compiled-branch
 ⟨code to apply compiled procedure 
  with given target and appropriate linkage⟩
primitive-branch
 (assign ⟨target⟩
         (op apply-primitive-procedure)
         (reg proc)
         (reg argl))
 ⟨linkage⟩
after-call

Lưu ý rằng nhánh compiled phải bỏ qua nhánh primitive. Do đó, nếu linkage cho lời gọi procedure ban đầu là next, nhánh hợp này phải sử dụng một linkage nhảy đến một label được chèn sau nhánh primitive. (Điều này tương tự như linkage được sử dụng cho nhánh đúng trong compile-if.)

(define (compile-procedure-call
         target linkage)
  (let ((primitive-branch 
         (make-label 'primitive-branch))
        (compiled-branch 
         (make-label 'compiled-branch))
        (after-call
         (make-label 'after-call)))
    (let ((compiled-linkage
           (if (eq? linkage 'next)
               after-call
               linkage)))
      (append-instruction-sequences
       (make-instruction-sequence 
        '(proc)
        '()
        `((test 
           (op primitive-procedure?)
           (reg proc))
          (branch 
           (label ,primitive-branch))))
       (parallel-instruction-sequences
        (append-instruction-sequences
         compiled-branch
         (compile-proc-appl 
          target
          compiled-linkage))
        (append-instruction-sequences
         primitive-branch
         (end-with-linkage
          linkage
          (make-instruction-sequence
           '(proc argl)
           (list target)
           `((assign 
              ,target
              (op apply-primitive-procedure)
              (reg proc)
              (reg argl)))))))
       after-call))))

Các nhánh primitive (nguyên thủy) và compound (hợp), giống như các nhánh true và false trong compile-if, được nối bằng parallel-instruction-sequences thay vì append-instruction-sequences thông thường, vì chúng sẽ không được thực thi tuần tự.

Applying compiled procedures (Áp dụng các thủ tục đã biên dịch)

Mã xử lý procedure application (lời gọi thủ tục) là phần tinh vi nhất của compiler (trình biên dịch), mặc dù các instruction sequence (chuỗi lệnh) mà nó sinh ra rất ngắn. Một compiled procedure (thủ tục đã biên dịch) — như được tạo bởi compile-lambda — có một entry point (điểm vào), là một label (nhãn) chỉ định nơi mã của procedure bắt đầu. Mã tại entry point này tính toán một kết quả trong val và trả về bằng cách thực thi lệnh (goto (reg continue)). Do đó, chúng ta có thể kỳ vọng mã cho một compiled-procedure application (được sinh ra bởi compile-proc-appl) với một target và linkage cho trước sẽ trông như sau nếu linkage là một label:

(assign continue 
        (label proc-return))
 (assign val
         (op compiled-procedure-entry)
         (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨target⟩ 
         (reg val))   ; included if target is not val
 (goto (label ⟨linkage⟩))   ; linkage code

hoặc như sau nếu linkage là return:

(save continue)
 (assign continue 
         (label proc-return))
 (assign val 
         (op compiled-procedure-entry)
         (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨target⟩
         (reg val))   ; included if target is not val
 (restore continue)
 (goto (reg continue))   ; linkage code

Đoạn mã này thiết lập continue để procedure sẽ trả về một label proc-return và nhảy đến entry point của procedure. Mã tại proc-return sẽ chuyển kết quả của procedure từ val sang target register (nếu cần) và sau đó nhảy đến vị trí được chỉ định bởi linkage. (Linkage luôn là return hoặc một label, vì compile-procedure-call thay thế một linkage next cho nhánh compound-procedure bằng một label after-call.)

Thực tế, nếu target không phải là val, đó chính xác là mã mà compiler của chúng ta sẽ sinh ra. Tuy nhiên, thông thường target là val (thời điểm duy nhất compiler chỉ định một register khác là khi nhắm mục tiêu đánh giá một operator vào proc), vì vậy kết quả của procedure được đưa trực tiếp vào target register và không cần quay lại một vị trí đặc biệt để sao chép nó. Thay vào đó, chúng ta đơn giản hóa mã bằng cách thiết lập continue để procedure sẽ “trả về” trực tiếp đến vị trí được chỉ định bởi linkage của lời gọi:

⟨set up continue for linkage⟩
(assign val 
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Nếu linkage là một label, chúng ta thiết lập continue để procedure sẽ trả về label đó. (Tức là, (goto (reg continue)) mà procedure kết thúc sẽ tương đương với (goto (label ⟨linkage⟩)) tại proc-return ở trên.)

(assign continue 
        (label ⟨linkage⟩))
(assign val
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Nếu linkage là return, chúng ta không cần thiết lập continue nữa: Nó đã chứa sẵn vị trí mong muốn. (Tức là, (goto (reg continue)) mà procedure kết thúc sẽ đi thẳng đến nơi mà (goto (reg continue)) tại proc-return sẽ đi tới.)

(assign val
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Với cách triển khai linkage return này, compiler sinh ra mã tail-recursive (đệ quy đuôi). Gọi một procedure như bước cuối cùng trong phần thân procedure sẽ thực hiện một chuyển giao trực tiếp, không lưu bất kỳ thông tin nào trên stack.

Giả sử thay vào đó, chúng ta xử lý trường hợp gọi procedure với linkage return và target là val như đã trình bày ở trên cho target khác val. Điều này sẽ phá vỡ tail recursion (đệ quy đuôi). Hệ thống của chúng ta vẫn sẽ cho cùng một giá trị cho bất kỳ expression nào. Nhưng mỗi lần gọi procedure, chúng ta sẽ lưu continue và trả về sau lời gọi để hoàn tác việc lưu (vô ích) đó. Các lần lưu thừa này sẽ tích tụ trong một chuỗi lồng nhau của các lời gọi procedure⁸.

Compile-proc-appl sinh ra mã procedure-application ở trên bằng cách xét bốn trường hợp, tùy thuộc vào việc target cho lời gọi có phải là val hay không và linkage có phải là return hay không. Lưu ý rằng các instruction sequence được khai báo là thay đổi tất cả các register, vì việc thực thi phần thân procedure có thể thay đổi các register theo nhiều cách tùy ý. Cũng lưu ý rằng chuỗi mã cho trường hợp target là val và linkage là return được khai báo là cần continue: Mặc dù continue không được sử dụng tường minh trong chuỗi lệnh gồm hai câu lệnh này, chúng ta phải đảm bảo rằng continue sẽ có giá trị chính xác khi chúng ta vào compiled procedure.

(define (compile-proc-appl target linkage)
  (cond ((and (eq? target 'val)
              (not (eq? linkage 'return)))
         (make-instruction-sequence 
          '(proc)
          all-regs
          `((assign continue (label ,linkage))
            (assign 
             val 
             (op compiled-procedure-entry)
             (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val))
              (not (eq? linkage 'return)))
         (let ((proc-return 
                (make-label 'proc-return)))
           (make-instruction-sequence 
            '(proc)
            all-regs
            `((assign continue 
                      (label ,proc-return))
              (assign 
               val 
               (op compiled-procedure-entry)
               (reg proc))
              (goto (reg val))
              ,proc-return
              (assign ,target (reg val))
              (goto (label ,linkage))))))
        ((and (eq? target 'val)
              (eq? linkage 'return))
         (make-instruction-sequence 
          '(proc continue) 
          all-regs
          '((assign 
             val 
             (op compiled-procedure-entry)
             (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val))
              (eq? linkage 'return))
         (error "return linkage, 
                 target not val: COMPILE"
                target))))

5.5.4 Combining Instruction Sequences (Kết hợp các chuỗi lệnh)

Phần này mô tả chi tiết cách các instruction sequence (chuỗi lệnh) được biểu diễn và kết hợp. Nhắc lại từ mục 5.5.1 rằng một instruction sequence được biểu diễn như một danh sách gồm các register (thanh ghi) cần thiết, các register bị thay đổi, và các lệnh thực tế. Chúng ta cũng sẽ coi một label (nhãn, ký hiệu) là một trường hợp suy biến của instruction sequence, vốn không cần hoặc thay đổi bất kỳ register nào. Vì vậy, để xác định các register cần và bị thay đổi bởi các instruction sequence, chúng ta sử dụng các selector (bộ chọn):

(define (registers-needed s)
  (if (symbol? s) '() (car s)))
(define (registers-modified s)
  (if (symbol? s) '() (cadr s)))
(define (statements s)
  (if (symbol? s) (list s) (caddr s)))

và để xác định xem một chuỗi cho trước có cần hoặc thay đổi một register cho trước hay không, chúng ta sử dụng các predicate (hàm điều kiện):

(define (needs-register? seq reg)
  (memq reg (registers-needed seq)))
(define (modifies-register? seq reg)
  (memq reg (registers-modified seq)))

Dựa trên các predicate và selector này, chúng ta có thể triển khai các bộ kết hợp instruction sequence khác nhau được sử dụng trong toàn bộ compiler (trình biên dịch).

Bộ kết hợp cơ bản là append-instruction-sequences. Nó nhận một số lượng tùy ý các instruction sequence cần được thực thi tuần tự và trả về một instruction sequence có các statement (câu lệnh) là sự nối tiếp của tất cả các chuỗi. Điểm tinh tế là xác định các register cần và bị thay đổi bởi chuỗi kết quả. Nó thay đổi những register bị thay đổi bởi bất kỳ chuỗi nào; nó cần những register phải được khởi tạo trước khi chuỗi đầu tiên có thể chạy (các register cần bởi chuỗi đầu tiên), cùng với những register cần bởi bất kỳ chuỗi nào khác mà không được khởi tạo (bị thay đổi) bởi các chuỗi trước đó.

Các chuỗi được nối từng cặp một bởi append-2-sequences. Thủ tục này nhận hai instruction sequence seq1 và seq2 và trả về một instruction sequence có các statement là các statement của seq1 theo sau bởi các statement của seq2, có các register bị thay đổi là hợp của các register bị thay đổi bởi seq1 hoặc seq2, và có các register cần là hợp của các register cần bởi seq1 với hiệu của các register cần bởi seq2 và các register bị thay đổi bởi seq1. (Xét theo phép toán tập hợp, tập register cần mới là hợp của tập register cần bởi seq1 với hiệu của tập register cần bởi seq2 và tập register bị thay đổi bởi seq1.) Do đó, append-instruction-sequences được triển khai như sau:

(define (append-instruction-sequences . seqs)
  (define (append-2-sequences seq1 seq2)
    (make-instruction-sequence
     (list-union 
      (registers-needed seq1)
      (list-difference 
       (registers-needed seq2)
       (registers-modified seq1)))
     (list-union
      (registers-modified seq1)
      (registers-modified seq2))
     (append (statements seq1)
             (statements seq2))))
  (define (append-seq-list seqs)
    (if (null? seqs)
        (empty-instruction-sequence)
        (append-2-sequences 
         (car seqs)
         (append-seq-list (cdr seqs)))))
  (append-seq-list seqs))

Thủ tục này sử dụng một số phép toán đơn giản để thao tác các tập hợp được biểu diễn dưới dạng danh sách, tương tự như biểu diễn tập hợp (không có thứ tự) được mô tả trong mục 2.3.3:

(define (list-union s1 s2)
  (cond ((null? s1) s2)
        ((memq (car s1) s2)
         (list-union (cdr s1) s2))
        (else
         (cons (car s1)
               (list-union (cdr s1) s2)))))

(define (list-difference s1 s2)
  (cond ((null? s1) '())
        ((memq (car s1) s2)
         (list-difference (cdr s1) s2))
        (else 
         (cons (car s1)
               (list-difference (cdr s1)
                                s2)))))

Preserving, bộ kết hợp instruction sequence quan trọng thứ hai, nhận một danh sách register regs và hai instruction sequence seq1 và seq2 cần được thực thi tuần tự. Nó trả về một instruction sequence có các statement là các statement của seq1 theo sau bởi các statement của seq2, với các lệnh save và restore thích hợp bao quanh seq1 để bảo vệ các register trong regs bị thay đổi bởi seq1 nhưng cần bởi seq2. Để thực hiện điều này, preserving trước tiên tạo một chuỗi có các lệnh save cần thiết theo sau bởi các statement của seq1 và tiếp đó là các lệnh restore cần thiết. Chuỗi này cần các register đang được lưu và khôi phục ngoài các register cần bởi seq1, và thay đổi các register bị thay đổi bởi seq1 ngoại trừ những register đang được lưu và khôi phục. Chuỗi đã được bổ sung này và seq2 sau đó được nối theo cách thông thường. Thủ tục sau triển khai chiến lược này một cách đệ quy, duyệt xuống danh sách các register cần bảo toàn:¹⁰

(define (preserving regs seq1 seq2)
  (if (null? regs)
      (append-instruction-sequences seq1 seq2)
      (let ((first-reg (car regs)))
        (if (and 
             (needs-register? seq2 first-reg)
             (modifies-register? seq1 
                                 first-reg))
            (preserving 
             (cdr regs)
             (make-instruction-sequence
              (list-union 
               (list first-reg)
               (registers-needed seq1))
              (list-difference
               (registers-modified seq1)
               (list first-reg))
              (append `((save ,first-reg))
                      (statements seq1)
                      `((restore ,first-reg))))
             seq2)
            (preserving 
             (cdr regs)
             seq1
             seq2)))))

Một bộ kết hợp chuỗi khác, tack-on-instruction-sequence, được compile-lambda sử dụng để nối phần thân procedure vào một chuỗi khác. Bởi vì phần thân procedure không được thực thi “in line” như một phần của chuỗi kết hợp, việc sử dụng register của nó không ảnh hưởng đến việc sử dụng register của chuỗi mà nó được nhúng vào. Do đó, chúng ta bỏ qua các tập register cần và bị thay đổi của phần thân procedure khi nối nó vào chuỗi khác.

(define (tack-on-instruction-sequence 
         seq body-seq)
  (make-instruction-sequence
   (registers-needed seq)
   (registers-modified seq)
   (append (statements seq)
           (statements body-seq))))

Compile-if và compile-procedure-call sử dụng một bộ kết hợp đặc biệt gọi là parallel-instruction-sequences để nối hai nhánh thay thế theo sau một phép kiểm tra. Hai nhánh này sẽ không bao giờ được thực thi tuần tự; với mỗi lần đánh giá phép kiểm tra, chỉ một trong hai nhánh được thực thi. Vì lý do này, các register cần bởi nhánh thứ hai vẫn cần cho chuỗi kết hợp, ngay cả khi chúng bị thay đổi bởi nhánh thứ nhất.

(define (parallel-instruction-sequences 
         seq1 seq2)
  (make-instruction-sequence
   (list-union (registers-needed seq1)
               (registers-needed seq2))
   (list-union (registers-modified seq1)
               (registers-modified seq2))
   (append (statements seq1)
           (statements seq2))))

5.5.5 Một ví dụ về mã đã biên dịch

Bây giờ khi chúng ta đã thấy tất cả các thành phần của compiler (trình biên dịch), hãy xem xét một ví dụ về mã đã biên dịch để thấy cách mọi thứ kết hợp với nhau. Chúng ta sẽ biên dịch định nghĩa của một procedure (thủ tục) đệ quy factorial bằng cách gọi compile:

(compile
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))
 'val
 'next)

Chúng ta đã chỉ định rằng giá trị của expression define sẽ được đặt vào register val. Chúng ta không quan tâm mã đã biên dịch sẽ làm gì sau khi thực thi define, vì vậy việc chọn next làm linkage descriptor (bộ mô tả liên kết) là tùy ý.

Compile xác định rằng expression là một definition (định nghĩa), vì vậy nó gọi compile-definition để biên dịch mã tính giá trị sẽ được gán (với target là val), tiếp theo là mã cài đặt định nghĩa, tiếp theo là mã đặt giá trị của define (là ký hiệu ok) vào target register, và cuối cùng là mã linkage. Env được bảo toàn xung quanh quá trình tính giá trị, vì nó cần thiết để cài đặt định nghĩa. Vì linkage là next, nên trong trường hợp này không có mã linkage. Khung của mã đã biên dịch do đó là:

⟨save env if modified by code to compute value⟩
  ⟨compilation of definition value, 
   target val, linkage next⟩
  ⟨restore env if saved above⟩
  (perform (op define-variable!)
           (const factorial)
           (reg val)
           (reg env))
  (assign val (const ok))

Expression sẽ được biên dịch để tạo giá trị cho biến factorial là một lambda expression (biểu thức lambda) mà giá trị của nó là procedure tính giai thừa. Compile xử lý điều này bằng cách gọi compile-lambda, biên dịch phần thân procedure, gán nhãn nó như một entry point (điểm vào) mới, và sinh ra lệnh sẽ kết hợp phần thân procedure tại entry point mới với run-time environment (môi trường tại thời gian chạy) và gán kết quả vào val. Chuỗi lệnh sau đó bỏ qua mã procedure đã biên dịch, vốn được chèn vào tại điểm này. Mã procedure bắt đầu bằng việc mở rộng definition environment (môi trường định nghĩa) của procedure bằng một frame (khung) ràng buộc formal parameter (tham số hình thức) n với đối số của procedure. Sau đó là phần thân procedure thực tế. Vì mã này cho giá trị của biến không thay đổi register env, nên các lệnh save và restore tùy chọn được hiển thị ở trên sẽ không được sinh ra. (Mã procedure tại entry2 không được thực thi tại thời điểm này, nên việc nó sử dụng env là không liên quan.) Do đó, khung của mã đã biên dịch trở thành:

  (assign val (op make-compiled-procedure)
              (label entry2)
              (reg env))
  (goto (label after-lambda1))
entry2
  (assign env (op compiled-procedure-env)
              (reg proc))
  (assign env (op extend-environment)
              (const (n))
              (reg argl)
              (reg env))
  ⟨compilation of procedure body⟩
after-lambda1
  (perform (op define-variable!)
           (const factorial)
           (reg val) (reg env))
  (assign val (const ok))

Phần thân procedure luôn được biên dịch (bởi compile-lambda-body) như một sequence (chuỗi) với target là val và linkage là return. Chuỗi trong trường hợp này bao gồm một if expression (biểu thức if) duy nhất:

(if (= n 1)
    1
    (* (factorial (- n 1)) n))

Compile-if sinh ra mã đầu tiên tính predicate (mệnh đề điều kiện) (với target là val), sau đó kiểm tra kết quả và rẽ nhánh bỏ qua nhánh đúng nếu predicate là sai. Env và continue được bảo toàn xung quanh mã predicate, vì chúng có thể cần cho phần còn lại của if expression. Vì if expression là expression cuối cùng (và duy nhất) trong sequence tạo thành phần thân procedure, target của nó là val và linkage là return, nên cả nhánh đúng và nhánh sai đều được biên dịch với target là val và linkage là return. (Tức là, giá trị của câu điều kiện — giá trị được tính bởi một trong hai nhánh — chính là giá trị của procedure.)

⟨save continue, env if modified by 
 predicate and needed by branches⟩
  ⟨compilation of predicate, 
   target val, linkage next⟩
  ⟨restore continue, env if saved above⟩
  (test (op false?) (reg val))
  (branch (label false-branch4))
true-branch5
  ⟨compilation of true branch, 
   target val, linkage return⟩
false-branch4
  ⟨compilation of false branch, 
   target val, linkage return⟩
after-if3

Predicate (= n 1) là một procedure call (lời gọi thủ tục). Điều này tra cứu operator (toán tử) (ký hiệu =) và đặt giá trị này vào proc. Sau đó nó lắp ráp các đối số 1 và giá trị của n vào argl. Tiếp theo, nó kiểm tra xem proc chứa một primitive procedure (thủ tục nguyên thủy) hay một compound procedure (thủ tục hợp), và phân nhánh đến nhánh primitive hoặc compound tương ứng. Cả hai nhánh đều tiếp tục tại label after-call. Yêu cầu bảo toàn register xung quanh việc đánh giá operator và operand không dẫn đến việc lưu register nào, vì trong trường hợp này các phép đánh giá đó không thay đổi các register liên quan.

  (assign proc (op lookup-variable-value)
               (const =) 
               (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value)
              (const n)
              (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch17))
compiled-branch16
  (assign continue (label after-call15))
  (assign val (op compiled-procedure-entry)
              (reg proc))
  (goto (reg val))
primitive-branch17
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
after-call15

Nhánh đúng, là hằng số 1, được biên dịch (với target là val và linkage là return) thành:

(assign val (const 1))
(goto (reg continue))

Mã cho nhánh sai là một procedure call khác, trong đó procedure là giá trị của ký hiệu *, và các đối số là n và kết quả của một procedure call khác (gọi đến factorial). Mỗi lời gọi này thiết lập proc và argl và có các nhánh primitive và compound riêng. Hình 5.17 cho thấy toàn bộ quá trình biên dịch định nghĩa của procedure factorial. Lưu ý rằng các lệnh save và restore có thể có của continue và env xung quanh predicate, như đã hiển thị ở trên, thực tế được sinh ra, vì các register này bị thay đổi bởi lời gọi procedure trong predicate và cần cho lời gọi procedure và linkage return trong các nhánh.

5.5.6 Lexical Addressing (Địa chỉ từ vựng)

Một trong những tối ưu hóa phổ biến nhất được thực hiện bởi compiler (trình biên dịch) là tối ưu hóa việc tra cứu biến. Compiler của chúng ta, như đã triển khai cho đến nay, sinh ra mã sử dụng thao tác lookup-variable-value của evaluator machine (máy đánh giá). Thao tác này tìm kiếm một biến bằng cách so sánh nó với từng biến hiện đang được ràng buộc, làm việc từng frame (khung) từ trong ra ngoài thông qua run-time environment (môi trường tại thời gian chạy). Việc tìm kiếm này có thể tốn kém nếu các frame lồng nhau sâu hoặc nếu có nhiều biến. Ví dụ, hãy xem xét vấn đề tra cứu giá trị của x khi đánh giá expression (biểu thức) (* x y z) trong một lần áp dụng procedure (thủ tục) được trả về bởi:

(let ((x 3) (y 4))
  (lambda (a b c d e)
    (let ((y (* a b x))
          (z (+ c d x)))
      (* x y z))))

Vì một let expression (biểu thức let) chỉ là cú pháp rút gọn của một lambda combination (tổ hợp lambda), nên biểu thức này tương đương với:

((lambda (x y)
   (lambda (a b c d e)
     ((lambda (y z) (* x y z))
      (* a b x)
      (+ c d x))))
 3
 4)

Mỗi lần lookup-variable-value tìm kiếm x, nó phải xác định rằng ký hiệu x không eq? với y hoặc z (trong frame đầu tiên), cũng không với a, b, c, d, hoặc e (trong frame thứ hai). Chúng ta sẽ giả định, tạm thời, rằng các chương trình của chúng ta không sử dụng define — rằng các biến chỉ được ràng buộc bằng lambda. Bởi vì ngôn ngữ của chúng ta là lexically scoped (phạm vi từ vựng), run-time environment cho bất kỳ expression nào sẽ có cấu trúc song song với cấu trúc từ vựng của chương trình trong đó expression xuất hiện.¹¹ Do đó, compiler có thể biết, khi phân tích biểu thức trên, rằng mỗi lần procedure được áp dụng, biến x trong (* x y z) sẽ được tìm thấy ở hai frame bên ngoài frame hiện tại và sẽ là biến đầu tiên trong frame đó.

Chúng ta có thể khai thác điều này bằng cách tạo ra một loại thao tác tra cứu biến mới, lexical-address-lookup, nhận đối số là một environment và một lexical address (địa chỉ từ vựng) gồm hai số: một frame number (số khung), chỉ định cần bỏ qua bao nhiêu frame, và một displacement number (số dịch chuyển), chỉ định cần bỏ qua bao nhiêu biến trong frame đó. Lexical-address-lookup sẽ trả về giá trị của biến được lưu tại lexical address đó so với environment hiện tại. Nếu chúng ta thêm thao tác lexical-address-lookup vào máy, chúng ta có thể làm cho compiler sinh ra mã tham chiếu biến bằng thao tác này, thay vì lookup-variable-value. Tương tự, mã đã biên dịch của chúng ta có thể sử dụng thao tác mới lexical-address-set! thay cho set-variable-value!.

Để sinh ra mã như vậy, compiler phải có khả năng xác định lexical address của một biến mà nó sắp biên dịch tham chiếu đến. Lexical address của một biến trong chương trình phụ thuộc vào vị trí trong mã. Ví dụ, trong chương trình sau, địa chỉ của x trong expression ⟨e1⟩ là (2, 0) — lùi hai frame và là biến đầu tiên trong frame. Tại thời điểm đó, y ở địa chỉ (0, 0) và c ở địa chỉ (1, 2). Trong expression ⟨e2⟩, x ở (1, 0), y ở (1, 1), và c ở (0, 2).

((lambda (x y)
   (lambda (a b c d e)
     ((lambda (y z) ⟨e1⟩)
      ⟨e2⟩
      (+ c d x))))
 3
 4)

Một cách để compiler sinh ra mã sử dụng lexical addressing là duy trì một cấu trúc dữ liệu gọi là compile-time environment (môi trường tại thời gian biên dịch). Cấu trúc này theo dõi biến nào sẽ ở vị trí nào trong frame nào của run-time environment khi một thao tác truy cập biến cụ thể được thực thi. Compile-time environment là một danh sách các frame, mỗi frame chứa một danh sách các biến. (Tất nhiên sẽ không có giá trị nào được ràng buộc với các biến, vì giá trị không được tính tại thời gian biên dịch.) Compile-time environment trở thành một đối số bổ sung cho compile và được truyền đến mỗi code generator (bộ sinh mã). Lời gọi compile ở cấp cao nhất sử dụng một compile-time environment rỗng. Khi một phần thân lambda được biên dịch, compile-lambda-body mở rộng compile-time environment bằng một frame chứa các tham số của procedure, để chuỗi tạo thành phần thân được biên dịch với environment đã mở rộng đó. Tại mỗi điểm trong quá trình biên dịch, compile-variable và compile-assignment sử dụng compile-time environment để sinh ra các lexical address thích hợp.

5.5.7 Interfacing Compiled Code to the Evaluator (Kết nối mã đã biên dịch với evaluator)

Chúng ta vẫn chưa giải thích cách nạp mã đã biên dịch vào evaluator machine hoặc cách chạy nó. Chúng ta sẽ giả định rằng explicit-control-evaluator machine (máy đánh giá điều khiển tường minh) đã được định nghĩa như trong mục 5.4.4, với các thao tác bổ sung được chỉ định trong Chú thích 323. Chúng ta sẽ triển khai một procedure compile-and-go để biên dịch một Scheme expression, nạp object code (mã đối tượng) thu được vào evaluator machine, và khiến máy chạy mã đó trong evaluator global environment (môi trường toàn cục của bộ đánh giá), in kết quả, và vào vòng lặp điều khiển của evaluator. Chúng ta cũng sẽ sửa đổi evaluator để các expression thông dịch có thể gọi các compiled procedure cũng như các interpreted procedure. Khi đó, chúng ta có thể đưa một compiled procedure vào máy và sử dụng evaluator để gọi nó:

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)

;;; EC-Eval value:
120

Để cho phép evaluator xử lý compiled procedure (ví dụ, để đánh giá lời gọi đến factorial ở trên), chúng ta cần thay đổi mã tại apply-dispatch (5.4.1) để nó nhận diện compiled procedure (phân biệt với compound procedure hoặc primitive procedure) và chuyển điều khiển trực tiếp đến entry point của mã đã biên dịch:¹²

apply-dispatch
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-apply))
  (test (op compound-procedure?) (reg proc))
  (branch (label compound-apply))
  (test (op compiled-procedure?) (reg proc))
  (branch (label compiled-apply))
  (goto (label unknown-procedure-type))

compiled-apply
  (restore continue)
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))

Lưu ý việc khôi phục continue tại compiled-apply. Hãy nhớ rằng evaluator được sắp xếp sao cho tại apply-dispatch, continuation sẽ ở trên đỉnh stack. Entry point của mã đã biên dịch, ngược lại, mong đợi continuation nằm trong continue, vì vậy continue phải được khôi phục trước khi mã đã biên dịch được thực thi.

Để cho phép chúng ta chạy một số mã đã biên dịch khi khởi động evaluator machine (máy đánh giá), chúng ta thêm một lệnh branch vào đầu evaluator machine, lệnh này sẽ khiến máy chuyển đến một entry point (điểm vào) mới nếu register flag được thiết lập.¹³

;; branches if flag is set:
(branch (label external-entry)) 
read-eval-print-loop
  (perform (op initialize-stack))
  …

External-entry giả định rằng máy được khởi động với val chứa vị trí của một instruction sequence (chuỗi lệnh) đặt một kết quả vào val và kết thúc bằng (goto (reg continue)). Bắt đầu tại entry point này sẽ nhảy đến vị trí được chỉ định bởi val, nhưng trước tiên gán continue để việc thực thi sẽ quay lại print-result, nơi in giá trị trong val và sau đó quay lại đầu vòng lặp read-eval-print của evaluator.¹⁴

external-entry
  (perform (op initialize-stack))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (reg val))

Bây giờ chúng ta có thể sử dụng procedure (thủ tục) sau để biên dịch một định nghĩa procedure, thực thi mã đã biên dịch, và chạy vòng lặp read-eval-print để thử procedure. Bởi vì chúng ta muốn mã đã biên dịch trả về vị trí trong continue với kết quả trong val, chúng ta biên dịch expression với target là val và linkage là return. Để biến object code (mã đối tượng) do compiler sinh ra thành các lệnh thực thi cho evaluator register machine (máy thanh ghi của bộ đánh giá), chúng ta sử dụng procedure assemble từ register-machine simulator (trình mô phỏng máy thanh ghi) (5.2.2). Sau đó, chúng ta khởi tạo register val để trỏ đến danh sách các lệnh, thiết lập flag để evaluator sẽ chuyển đến external-entry, và khởi động evaluator.

(define (compile-and-go expression)
  (let ((instructions
         (assemble 
          (statements
           (compile 
            expression 'val 'return))
          eceval)))
    (set! the-global-environment
          (setup-environment))
    (set-register-contents! 
     eceval 'val instructions)
    (set-register-contents! 
     eceval 'flag true)
    (start eceval)))

Nếu chúng ta đã thiết lập giám sát stack (ngăn xếp), như ở cuối mục 5.4.4, chúng ta có thể kiểm tra mức sử dụng stack của mã đã biên dịch:

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))
(total-pushes = 0, maximum-depth = 0)

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)
(total-pushes = 31, maximum-depth = 14)

;;; EC-Eval value:
120

So sánh ví dụ này với việc đánh giá (factorial 5) bằng phiên bản thông dịch của cùng procedure, được hiển thị ở cuối mục 5.4.4. Phiên bản thông dịch yêu cầu 144 lần push và độ sâu stack tối đa là 28. Điều này minh họa sự tối ưu hóa đạt được từ chiến lược biên dịch của chúng ta.

Interpretation and compilation (Thông dịch và biên dịch)

Với các chương trình trong phần này, chúng ta bây giờ có thể thử nghiệm các chiến lược thực thi thay thế là interpretation (thông dịch) và compilation (biên dịch).¹⁵ Một interpreter (bộ thông dịch) nâng cấp máy lên mức của chương trình người dùng; một compiler hạ chương trình người dùng xuống mức của machine language (ngôn ngữ máy). Chúng ta có thể coi ngôn ngữ Scheme (hoặc bất kỳ ngôn ngữ lập trình nào) như một hệ thống các trừu tượng được xây dựng trên machine language. Interpreter thích hợp cho việc phát triển và gỡ lỗi chương trình tương tác vì các bước thực thi chương trình được tổ chức theo các trừu tượng này, do đó dễ hiểu hơn đối với lập trình viên. Mã đã biên dịch có thể thực thi nhanh hơn, vì các bước thực thi chương trình được tổ chức theo machine language, và compiler có thể tự do thực hiện các tối ưu hóa vượt qua các trừu tượng cấp cao hơn.¹⁶

Các lựa chọn giữa interpretation và compilation cũng dẫn đến các chiến lược khác nhau để porting (chuyển đổi) ngôn ngữ sang các máy tính mới. Giả sử chúng ta muốn triển khai Lisp cho một máy mới. Một chiến lược là bắt đầu với explicit-control evaluator (bộ đánh giá điều khiển tường minh) ở mục 5.4 và dịch các lệnh của nó sang các lệnh cho máy mới. Một chiến lược khác là bắt đầu với compiler và thay đổi các code generator (bộ sinh mã) để chúng sinh ra mã cho máy mới. Chiến lược thứ hai cho phép chúng ta chạy bất kỳ chương trình Lisp nào trên máy mới bằng cách biên dịch nó trước với compiler chạy trên hệ thống Lisp gốc của chúng ta, và liên kết nó với một phiên bản đã biên dịch của run-time library (thư viện thời gian chạy).¹⁷ Tốt hơn nữa, chúng ta có thể biên dịch chính compiler, và chạy nó trên máy mới để biên dịch các chương trình Lisp khác.¹⁸ Hoặc chúng ta có thể biên dịch một trong các interpreter của mục 4.1 để tạo ra một interpreter chạy trên máy mới.