[SICP-ch4] Metalinguistic Abstraction

[SICP-ch4] Metalinguistic Abstraction

establishing new languages and implement these languages by constructing evaluators.

(极简版)


evaluators ( interpreter )

  • a procedure that, when applied to an expression of the language, performs the actions required to evaluate that expression.

4.1 The Metacircular Evaluator

metacircular

  • An evaluator that is written in the same language that it evaluates

Recall environment model

  • To evaluate a compound procedure, evaluate the subexpressions and then apply the
    value
  • To apply a compound procedure, evaluate the body of the procedure in a new environment.

Data Abstraction

  • make the evaluator independent of the representation of the language.

4.1.1 The Core of the Evaluator

eval and apply

(define (eval exp env)
    	;primitive
   (cond ((self-evaluating? exp) exp)
		((variable? exp) (lookup-variable-value exp env))
       	;special form
		((quoted? exp) (text-of-quotation exp))
		((assignment? exp) (eval-assignment exp env))
		((definition? exp) (eval-definition exp env))
		((if? exp) (eval-if exp env))
		((lambda? exp) (make-procedure (lambda-parameters exp)
									(lambda-body exp)
									env))
		((begin? exp)
		     (eval-sequence (begin-actions exp) env))
		((cond? exp) (eval (cond->if exp) env))
       		;combinations
		((application? exp)
         	;apply
			(apply (eval (operator exp) env)
				   (list-of-values (operands exp) env)))
		(else
		      (error "Unknown expression type: EVAL" exp))))

(define (apply procedure arguments)
    		;primitive
	(cond ((primitive-procedure? procedure)
		   (apply-primitive-procedure procedure arguments))
        	;compound
		  ((compound-procedure? procedure)
           ;eval
		   (eval-sequence
				(procedure-body procedure)
				(extend-environment
					(procedure-parameters procedure)
					arguments
					(procedure-environment procedure))))
		(else
			(error
				"Unknown procedure type: APPLY" procedure))))

Conditionals eval-if

Sequences eval-sequence

Assignments eval-assignment

Definitions eval-definition


4.1.2 Representing Expressions

building constructor, selector and predeicate of our language


  • The only self-evaluating items are numbers and strings
  • Variables are represented by symbols
  • Quotations have the form (quote ⟨text-of-quotation⟩)
  • Assignments have the form (set! ⟨var⟩ ⟨value⟩)
  • Definitions have the form (define ⟨var⟩ ⟨value⟩)
  • lambda expressions are lists that begin with the symbol lambda
  • Conditionals begin with if and have a predicate, a consequent, and an (optional) alternative.
  • begin packages a sequence of expressions into a single expression.
  • An application is any compound expression with operator in car and operands in cdr

Derived expressions

  • cond

4.1.3 Evaluator Data Structures

representation of

  • true and false

  • procedures

  • environments (a sequence of frams and each frame is a table of bindings)


4.1.4 Running the Evaluator as a Program

  • model the application of primitive procedures.
  • set up a global environment
  • provide a driver loop that models the read-eval-print loop
(define (driver-loop)
	(prompt-for-input input-prompt)
    ;input
	(let ((input (read)))
         ;evaluate output
		(let ((output (eval input the-global-environment)))
			(announce-output output-prompt)
			(user-print output)))
(driver-loop))

4.1.5 Data as Programs

One operational view of the meaning of a program is that a program is a description of an abstract (perhaps infinitely large) machine.


Evaluator as a bridge between the data objects and the language

  • From the perspective of the user, (* x x) is an expression in the programming language
  • From the perspective of the evaluator, (* x x) is simply a list to be manipulated.

4.1.6 Internal Definitions

evaluator execute definitions in sequence, resulting different scope for internal definition

Ways providing simultaneous scope

  • scan all definitions and create, and then set to their values by assignment.

4.1.7 Separating Syntactic Analysis from Execution

separate eval into analysis and execution

(define (eval exp env) ((analyze exp) env))

syntactic of analysis procedure

  • returns an execution procedure that ignores its environment argument
(define (analyze-self-evaluating exp)
	(lambda (env) exp))

analyze-quoted, analyze-variable, analyze-assignment, analyze-definition, analyze-if

analyze-lambda, analyze-sequence, analyze-application


4.2 Variations on a Scheme — Lazy Evaluation

4.2.1 Normal Order and Applicative Order

applicative-order

  • evaluate arguments than apply
  • strict procedure

normal-order

  • enter body procedure than evaluate arguments
  • non-strict procedure

4.2.2 An Interpreter with Lazy Evaluation

implement a normal-order language


thunk

  • delayed arguments
  • contain the information for applying when needed
  • forcing : evaluating expression in thunk

Modifying the evaluator

primitive: strict

compound: non-strict

change eval into actual-value

(define (actual-value exp env)
	(force-it (eval exp env)))

Representing thunks


4.2.3 Streams as Lazy Lists

With lazy evaluation, streams and lists can be identical, so there is no need for special forms or for separate list and stream operations.

Represent car, cdr and cons as non-strict procedure

List lazier than previous stream

  • The car of the list, as well as the cdr , is delayed.
  • won’t need explicit delay anymore ( ch-3 )

4.3 Variations on a Scheme — Nondeterministic Computing

nondeterministic computing

  • support automatic search
  • expressions have more than one possible value

Our approach

  • generate the sequence of all possible pairs and filter

4.3.1 Amb and Search

amb

(list (amb 1 2 3) (amb 'a 'b))

can have six possible values:

(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)

require

(define (require p) (if (not p) (amb)))

evaluate amb causes time to split into branches

  • machine with sufficient number of processors: parallel executions of choices
  • machine with only one processor: dfs

4.3.2 Examples of Nondeterministic Programs

Logical puzzles

Parsing natural language


4.3.3 Implementing the amb Evaluator

Nondeterministic evaluation

  • result in the discovery of a dead end, must backtrack to a previous choice point

Base on 4.1.7: analyzing evalutor ( analyze + execute )

Difference

  • entirely in the execution procedures

Execution procedures and continuations

the execution procedures in the amb evaluator take three arguments

  • Original: environment
  • Additional: success continuation & failure continuation

success continuation

  • Arguments: value & failure continuation
  • recieve value and proceed with the computation
  • call faliure continuation when value leads to a dead end

failure continuation

  • try another branch of the nondeterministic process

In summary, failure continuations are constructed by

  • amb expressions—to provide a mechanism to make alternative choices if the current choice leads to a dead end;
  • the top-level driver—to provide a mechanism to report failure when the choices are exhausted;
  • assignments—to intercept failures and undo assignments during backtracking.

Failures are initiated only when encountered a dead end. This occurs if

  • user program executes (amb) ( no choice any more )
  • user types try-again at the top-level driver

Failure continuations are also called during processing of a failure

in order to propagate failure back to the choice point or to the top level:

  • When failure continuation created by an assignment finish undoing, it calls the failure continuation it intercepted,
  • When failure continuation for an amb runs out of choices, it calls the failure continuation that was originally given to the amb

Structure of the evaluator

amb evaluator

(define (ambeval exp env succeed fail)
	((analyze exp) env succeed fail))

general form of an execution procedure

(lambda (env succeed fail)
	;; succeed is (lambda (value fail) . . . )
	;; fail is (lambda () . . . )
	. . . )

example: amb

neo analyze ( return execution procedure )

(define (analyze-amb exp)
	(let ((cprocs (map analyze (amb-choices exp))))
		(lambda (env succeed fail)
			(define (try-next choices)
				(if (null? choices)
					(fail)
					((car choices)
					  env
                     ;success continuation
					  succeed
                     ;failure continuation
					  (lambda () (try-next (cdr choices))))))
			(try-next cprocs))))

Driver loop

either calls try-again in response to the user typing try-again at the driver loop

or else starts a new evaluation by calling ambeval.


4.4 Logic Programming

computer science deals with imperative (how to) knowledge, whereas

mathematics deals with declarative (what is) knowledge.


Bias

  • programming is about constructing algorithms for computing unidirectional functions (computations with well-defined inputs and outputs)

Example of logical programming

(define (append x y)
	(if (null? x) y (cons (car x) (append (cdr x) y))))

append procedure can be regard as two rules translate into lisp

y = y append '()
( cons u v ) append y = ( cons u z ) IF v appedn y = z

In a logic programming language, the programmer writes an append
“procedure” by stating the two rules ( What is append ) about append given above.

“How to” knowledge is provided automatically by the interpreter


query language

  • our logic programming language
  • primitive: pattern ?x
  • compound: and, or, not
  • means of abstraction: rules

4.4.1 Deductive Information Retrieval

Simple queries

;;; Query input:
(job ?x (computer programmer))
;;; Query results:
(job (Hacker Alyssa P) (computer programmer))
(job (Fect Cy D) (computer programmer))

Compound queries

(and (job ?person (computer programmer))
	(address ?person ?where))

Rules

;⟨ conclusion ⟩ is a pattern and ⟨ body ⟩ is any query.
; ?first satisfy conclusion than apply body
(rule ⟨ conclusion ⟩ ⟨ body ⟩ )

Logic as programs ( implement our append in logical language )

(rule (append-to-form () ?y ?y))
(rule (append-to-form (?u . ?v) ?y (?u . ?z))
	  (append-to-form ?v ?y ?z))

4.4.2 How the Query System Works

Implement query evaluator

  • must perform some kind of search in order to match queries against facts and rules in the data base.

Approaches

  • nondeterministic program
  • Search with the aid of streams

Pattern matching

  • evaluate primitive and compound

Pattern Matcher Input

  • a pattern
  • a datum
  • a frame that specifies bindings for various pattern variables.

Pattern Matcher Output

  • returns the given frame augmented by any bindings that may have been determined by the match.

Compound queries

Unification

  • evaluate rules
  • a generalization of pattern matching
  • which both the “pattern” and the “datum” may contain variables.

Applying rules

similar to applying a procedure in the eval / apply


4.4.3 Is Logic Programming Mathematical Logic?

No

Query language provides a control structure that interprets the logical statements procedurally.


Differences

  • Take advantage in efficiency
;while less supervisor than programmers
(and (job ?x (computer programmer)) (supervisor ?x ?y))
(and (supervisor ?x ?y) (job ?x (computer programmer)))

  • Infinite loops

whether the system will find the simple answer (married Minnie Mickey) before it goes into the loop depends on implementation details concerning the order in which the system checks the items in the data base.

;assert rules
(assert! (rule (married ?x ?y) (married ?y ?x)))
;query
(married Mickey ?who)

  • Problems with not

not

;input empty frame where x unbound, \not filters out frames, return empty stream 
(and (not (job ?x (computer programmer)))
	 (supervisor ?x ?y))

not of logic programming languages reflects the so-called closed world assumption that all relevant information has been included in the data base.(见脚注)


4.4.4 Implementing the Query System

4.4.4.1 The Driver Loop and Instantiation

4.4.4.2 The Evaluator

4.4.4.3 Finding Assertions by Pattern Matching

4.4.4.4 Rules and Unification

4.4.4.5 Maintaining the Data Base

4.4.4.6 Stream Operations

4.4.4.7 Query Syntax Procedures

4.4.4.8 Frames and Bindings


もう…続けない…なわけないだろ!