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.
- 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
- To apply a compound procedure, evaluate the body of the procedure in a new environment.
- make the evaluator independent of the representation of the language.
4.1.1 The Core of the Evaluator
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
(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))))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
(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))))
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
- 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
4.1.3 Evaluator Data Structures
true and false
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
1 2 3 4 5 6 7 8 9
(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
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))
4.2.1 Normal Order and Applicative Order
- evaluate arguments than apply
- strict procedure
- enter body procedure than evaluate arguments
- non-strict procedure
4.2.2 An Interpreter with Lazy Evaluation
implement a normal-order language
- delayed arguments
- contain the information for applying when needed
- forcing : evaluating expression in thunk
Modifying the evaluator
(define (actual-value exp env) (force-it (eval exp env)))
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.
cons as non-strict procedure
List lazier than previous stream
carof the list, as well as the
cdr, is delayed.
- won’t need explicit
delayanymore ( ch-3 )
- support automatic search
- expressions have more than one possible value
- generate the sequence of all possible pairs and filter
4.3.1 Amb and Search
1 2 3 4 5
(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)
(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
Parsing natural language
4.3.3 Implementing the amb Evaluator
- result in the discovery of a dead end, must backtrack to a previous choice point
Base on 4.1.7: analyzing evalutor ( analyze + execute )
- 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
- Arguments: value & failure continuation
- recieve value and proceed with the computation
- call faliure continuation when value leads to a dead end
- try another branch of the nondeterministic process
In summary, failure continuations are constructed by
ambexpressions—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-againat 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
(define (ambeval exp env succeed fail) ((analyze exp) env succeed fail))
general form of an execution procedure
1 2 3 4
(lambda (env succeed fail) ;; succeed is (lambda (value fail) . . . ) ;; fail is (lambda () . . . ) . . . )
neo analyze ( return execution procedure )
1 2 3 4 5 6 7 8 9 10 11 12 13
(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))))
try-again in response to the user typing try-again at the driver loop
or else starts a new evaluation by calling
computer science deals with imperative (how to) knowledge, whereas
mathematics deals with declarative (what is) knowledge.
- 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
- our logic programming language
- primitive: pattern ?x
- compound: and, or, not
- means of abstraction: rules
4.4.1 Deductive Information Retrieval
1 2 3 4 5
;;; Query input: (job ?x (computer programmer)) ;;; Query results: (job (Hacker Alyssa P) (computer programmer)) (job (Fect Cy D) (computer programmer))
(and (job ?person (computer programmer)) (address ?person ?where))
1 2 3
;⟨ 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 )
1 2 3
(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.
- nondeterministic program
- Search with the aid of streams
- 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.
- evaluate rules
- a generalization of pattern matching
- which both the “pattern” and the “datum” may contain variables.
similar to applying a procedure in the eval / apply
4.4.3 Is Logic Programming Mathematical Logic?
Query language provides a control structure that interprets the logical statements procedurally.
- Take advantage in efficiency
1 2 3
;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.
1 2 3 4
;assert rules (assert! (rule (married ?x ?y) (married ?y ?x))) ;query (married Mickey ?who)
- Problems with not
1 2 3
;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
22.214.171.124 The Driver Loop and Instantiation
126.96.36.199 The Evaluator
188.8.131.52 Finding Assertions by Pattern Matching
184.108.40.206 Rules and Unification
220.127.116.11 Maintaining the Data Base
18.104.22.168 Stream Operations
22.214.171.124 Query Syntax Procedures
126.96.36.199 Frames and Bindings