留学生考试辅导 FB 150,

Comp 524: Lisp Implementation
Function Expressions/Closures
Instructor: (FB 150,

Copyright By PowCoder代写 加微信 powcoder

Free Variable Interpretation
(setq y 5)
(setq f (lambda (x) (* x y)))
(funcall f 2)
(setq y 6)
(setq f (lambda (x) (* x y)))
(funcall f 2)
(setq f (lambda (x) (* x y)))
(funcall f 2)
Results of the three (funcall f 2) expressions in the lisp implementation studied so far?
(setq y 5)
Variable referenced but not defined in a function definition is a free variable

Free Variable Intereprtation (Q/A)
(setq y 5)
(setq f (lambda (x) (* x y)))
(funcall f 2)
(setq y 6)
(setq f (lambda (x) (* x y)))
(funcall f 2)
(setq f (lambda (x) (* x y)))
(funcall f 2)
Results of the three (funcall f 2) expressions in the lisp implementation studies so far?
(setq y 5)
Variable referenced but not defined in a function definition is a free variable

Free Variables: Value available at Definition and Call Time
(setq y 5)
(setq f (lambda (x) (* x y)))
(funcall f 2)
Variable referenced but not defined in a function definition is a free variable
===============
=== Values ====
===============
=== Values ====
{F=LAMBDA (X) (* x y), Y=5}
===============
===============
===============

Free Variable: Value Available at Definition and Call Time
(setq y 6)
(setq f (lambda (x) (* x y)))
(funcall f 2)
===============
=== Values ====
===============
=== Values ====
{F=LAMBDA (X) (* x y), Y=6}
===============
===============
===============
(setq y 5)

Free Variables: Value Not available
(setq f (lambda (x) (* x y)))
(funcall f 2)
Unbound variable
===============
=== Values ====
===============
=== Values ====
{F=LAMBDA (X) (* x y)}
===============
===============
===============

Free Variable: Value Available at Call Time
(setq g (lambda (y) (funcall f y)))
(setq f (lambda (x) (* x y)))
(funcall g 2)
Result of (funcall g 2) in current implementation?

Free Variable: Value Available at Call Time (Q/A)
(setq g (lambda (y) (funcall f y)))
(setq f (lambda (x) (* x y)))
(funcall g 2)
Result of (funcall g 2) in current implementation?

Free Variable: Value Available at Call Time
(setq g (lambda (y) (funcall f y)))
(setq f (lambda (x) (* x y)))
(funcall g 2)
===============
=== Values ====
===============
=== Values ====
===============
=== Values ====
{F=LAMBDA (X) (* x y), G=LAMBDA (Y) (FUNCALL F Y)}
===============
===============
===============
===============
Dynamic Scoping: Free variables looked up in calling ancestor scopes, which is caller’s environment rather than environment of definition

Free Variable: Value Not Available at Call Time
(setq g (lambda (x) (funcall f x)))
(setq f (lambda (x) (* x y)))
(funcall g 2)
===============
=== Values ====
===============
=== Values ====
===============
=== Values ====
{F=LAMBDA (X) (* x y), G=LAMBDA (Y) (FUNCALL F Y)}
===============
===============
===============
===============

Returning Functions
(setq x 5)
(setq timesGenerator
(lambda (x)
(lambda (y) (* x y))
(setq twice (funcall timesGenerator 2))
(funcall twice 3)
What is the intended result of the last funcall?
What will the actual result given our implementation of lambda so far?

Returning Functions (Q/A)
(setq x 5)
(setq timesGenerator
(lambda (x)
(lambda (y) (* x y))
(setq twice (funcall timesGenerator 2))
(funcall twice 3)
What is the intended result of the last funcall?
What will the actual result given our implementation of lambda so far?

Tracing Abbreviated Version
Final result is application of returned second lambda
(setq x 5)
(lambda (x)
(lambda (y) (* x y))

Create Outer Lambda
I*** New lambda:
argNames:[X]
body:((LAMBDA (Y) (* x y)))
I***Eval: (LAMBDA (X) (LAMBDA (Y) (* x y))) –> LAMBDA (X) (LAMBDA (Y) (* x y))
(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)

Eval Outer Lambda arguments
I***(IntegerAtom) Eval: 2 –> 2
(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)

Initialize
I***(BasicEnvironmentFrame) Variable ‘X’ set to ‘2’ in environment:
===============
=== Values ====
===============
===============
(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)

Evaluate Body of Main Lambda, return Inner Lambda
I***New lambda:
argNames:[Y]
body:((* x y))
I*** Eval: (LAMBDA (Y) (* x y)) –> LAMBDA (Y) (* x y)
(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)
Value of X not used!

Start Evaluate Funcall of Returned Lambda application
I***(IntegerAtom) Eval: 3 –> 3
(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)

Bind Y in Created for Returned Lambda
***(BasicScope) Variable ‘Y’ set to ‘3’ in environment:
===============
=== Values ====
===============
===============

(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)

(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)
=== Values ====
===============
===============
===============
=== Values ====
==============
Global scope used, retrrn value is 15! Defining scope exists our tree-based implementation, but we have no reference to it when evaluating returned function.

What if no Global X
(FUNCALL ((LAMBDA (X) (LAMBDA (Y) (* x y))) 2) 3)
=== Values ====
===============
===============
===============
=== Values ====
==============
(lambda (x)
(lambda (y) (* x y))

No Global Value
(lambda (x)
(lambda (y) (* x y))

Gives error when we may not expect it to
Exception in thread “main” java.lang.IllegalStateException: Variable ‘X’ has no value
at main.lisp.parser.terms.IdentifierAtomWithLookup.eval(IdentifierAtomWithLookup.java:35)
at main.lisp.evaluator.basic.SumEvaluator.eval(SumEvaluator.java:22)

Non Intuitive!
Gives error when we may not expect it to
(lambda (x)
(lambda (y) (* x y))

(setq g (lambda (y) (funcall f y)))
(setq f (lambda (x) (* x y)))
(funcall g 2)
Does not give error when we may expect it to
What is difference in the rules for intuitive vs unintuitive? More formal terms for the two cases based on the terminology used so far?

Non Intuitive(Q/A)
Gives error when we may not expect it to
(lambda (x)
(lambda (y) (* x y))

(setq g (lambda (y) (funcall f y)))
(setq f (lambda (x) (* x y)))
(funcall g 2)
Does not give error when we may expect it to
What is difference in the rules for intuitive vs unintuitive? More formal terms for the two cases based on the terminology used so far?

Static (Lexical) vs Dynamic Scope
Dynamic Scoping: Free variables looked up in calling parent’s environment
Static (Lexical) Scoping: Free variables looked up in defining parent’s environment
In PL-Lisp we will add rather than replace (C-Lisp) dynamic scoping
New abstraction and syntax?

Function Operator
(lambda (x)
(lambda (y) (* x y))

(setq g (lambda (y) (funcall f y)))
(setq f (lambda (x) (* x y)))
(funcall g 2)
(setq f (function
(lambda (x) (* x y))))
(lambda (x)
(lambda (y) (* x y)))

Can optionally enclose lambda with free variables in function for static scoping

Lambda vs Function: Free Variable in Call and Defining Environment
(setq y 5)
(lambda (x) (* x y)))
(funcall f 2)
(setq y 5)
(setq f (function
(lambda (x) (* x y))))
(funcall f 2)
Outputs of calls to f?

Lambda vs Function: Free Variable in Call and Defining Environment (Q/A)
(setq y 5)
(lambda (x) (* x y)))
(funcall f 2)
(setq y 5)
(setq f (function
(lambda (x) (* x y))))
(funcall f 2)
Outputs of calls to f?

Lambda vs Function: Free Variable in Call and Defining Environment
(setq y 5)
(lambda (x) (* x y)))
(funcall f 2)
(setq y 5)
(setq f (function
(lambda (x) (* x y))))
(funcall f 2)
Which environment to choose is decided at definition time, not the entries in it. Consistent with compiler resolution of scopes vs runtime use of variables in scope

Lambda vs Function: Free Variable in Call But Not Defining Ancestor Environment
(lambda (y) (funcall f y)))
(lambda (x) (* x y)))
(funcall g 2)
(lambda (y) (funcall f y)))
(setq f (function
(lambda (x) (* x y))))
(funcall g 2)
Unbound y error

Lambda vs Function: Free Variable in Defining but not Call Ancestor Environment
(lambda (x)
(lambda (y) (* x y))

(lambda (x)
(lambda (y) (* x y)))
Unbound y error

Static Scoping: Inner Lambda Definition Environment
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)
=== Values ====
===============
===============
===============
=== Values ====
==============
Difference in implementation of dynamic and static scoping?

Lambda  Function Evaluators
S= (F E1 E2 … EN) F is an IdentifierAtom
S.eval(Environment) {return BasicOperationManagerSingleton.get().
getEvaluator (S.getHead().toString)}.
eval(S, Environment)
S= (F … ) F is an IdentifierAtom
Register Lambda Evaluator
(lambda (X Y) (* x y))
Register a Function Evaluator
Change Funcall Evaluator
(lambda (X Y) (* x y))
Register Funcall Evaluator

Lambda  Function Application
S.eval(Environment) {return BasicOperationManagerSingleton.get().
getEvaluator (S.getHead().toString)}.
eval(S, Environment)
S= (F … ) F is Lambda, Function or IdentifierAtom
S= (F … ) F is a lambda expression
Must change Composite S-Expression Evaluation to Detect and Handle New Case
> ((lambda (X Y) (print X) (* x y)) 3 4)
S= (F … ) F is a function expression
> ( (function (lambda (X Y) (print X) (* x y))) 3 4)
Inconsistent with Clisp

Lambda  Function Evaluator
{P1, P2, … ,PN },
LambdaFactory.newInstance(
S. eval (Environment)
(lambda (P1 P2 … PN) OE1 … EM RE)
return Lambda
Fundamental difference if any?

Lambda  Function Evaluator (Q/A)
{P1, P2, … ,PN },
LambdaFactory.newInstance(
S. eval (Environment)
(lambda (P1 P2 … PN) OE1 … EM RE)
return Lambda
Fundamental difference if any?

{P1, P2, … ,PN },
LambdaFactory.newInstance(
S. eval (Environment)
(lambda (P1 P2 … PN) OE1 … EM RE)
return Lambda
Associate the body and arg names (lambda) with the static environment The environment existed when lambda was returned, we never had a reference to it.
=== Values ====
===============
===============
===============
=== Values ====
==============
Closure = method + defining environment = lambda body + environment + arg names

Lambda  Function EVALUATOR
{P1, P2, … ,PN },
LambdaFactory.newInstance(
S. eval (Environment)
(lambda (P1 P2 … PN) OE1 … EM RE)
return FunctionFactory.newInstance(
Lambda, Environment
{P1, P2, … ,PN },
LambdaFactory.newInstance(
S. eval (Environment)
(lambda (P1 P2 … PN) OE1 … EM RE)
return Lambda

Lambda  Function Helper
eval (Function, {E1 .. EN) }, Environment)
ChildEnvironment =
Environment
return Lambda.eval(
Environment))
P1, P2, … PN =
Enviroment.store(P1..PN, E1..EN)
eval (Lambda, {E1 .. EN) }, Environment)
Enviroment.store(P1..PN, E1.eval(Environment)..EN.eval(Environment))
.newChild()
Lambda.getArgNames()
Change how?

Lambda  Function Helper (Q/A)
eval (Function, {E1 .. EN) }, Environment)
ChildEnvironment =
Environment
return Lambda.eval(
Environment))
P1, P2, … PN =
Enviroment.store(P1..PN, E1..EN)
eval (Lambda, {E1 .. EN) }, Environment)
Enviroment.store(P1..PN, E1.eval(Environment)..EN.eval(Environment))
.newChild()
Lambda.getArgNames()
Change how?

Lambda  Function Helper
ChildEnvironment =
Environment
return Lambda.eval(
Environment))
P1, P2, … PN =
eval (Function, {E1 .. EN) }, Environment)
Enviroment.store(P1..PN, E1.eval(Environment)..EN.eval(Environment))
.newChild()
Function.getEnvironment()
getLambda().getArgNames()
StaticEnvironment =
ChildEnvironment =
Environment
return Lambda.eval(
Environment))
P1, P2, … PN =
Enviroment.store(P1..PN, E1..EN)
eval (Lambda, {E1 .. EN) }, Environment)
Enviroment.store(P1..PN, E1.eval(Environment)..EN.eval(Environment))
.newChild()
Lambda.getArgNames()

Reusing Function Helper
eval (Function, {E1 .. EN) }, Environment)
LambdaHelper.eval(
ChildEnvironment =
Environment
return Lambda.eval(
Environment))
P1, P2, … PN =
Enviroment.store(P1..PN, E1..EN)
eval (Lambda, {E1 .. EN) }, Environment)
Enviroment.store(P1..PN, E1.eval(Environment)..EN.eval(Environment))
.newChild()
Lambda.getArgNames()
Function.getLambda(),
{E1 .. EN) },
Function.getEnviroment()

Lambda  Function Application Evaluation
eval(Function, {E1, … EN}, Environment)
Function = FuncInput.eval()
S = (FuncInput E1 .. EN )
S.eval (Environment)
eval(Lambda, {E1, … EN}, Environment)
Lambda = LambdaInput.eval()
S = (LambdaInput E1 .. EN )
S.eval (Environment)
LambdaHelper.
FunctionHelper.

Funcall of Lambda or Function Evaluator
.eval(Lambda, {E1, … EN}, Environment)
Lambda = F.eval()
S = (Funcall F E1 .. EN )
S.eval (Environment)
S = (Funcall F E1 .. EN )
S.eval (Environment)
LambdaHelper
Change how?

Funcall of Lambda or Function Evaluator
.eval(Lambda, {E1, … EN}, Environment)
Lambda = F.eval()
S = (Funcall F E1 .. EN )
S.eval (Environment)
S = (Funcall F E1 .. EN )
S.eval (Environment)
LambdaHelper
Change how?

Funcall of Lambda or Function Evaluator
.eval(Lambda, {E1, … EN}, Environment)
Lambda = F.eval()
S = (Funcall F E1 .. EN )
S.eval (Environment)
S = (Funcall F E1 .. EN )
LambdaOrFunction instanceof Lambda?
S.eval (Environment)
LambdaHelper
. {E1, … EN}, Environment):
LambdaHelper.eval (LambdaOrFunction,
. {E1, … EN}, Environment)
FuncionHelper.eval (LambdaOrFunction,
LambdaOrFunction = F.eval()

Static (Lexical) vs Dynamic Scope
Dynamic Scoping: Free variables looked up in calling parent’s environment
Static (Lexical) Scoping: Free variables looked up in defining parent’s environment
Free Variable: Variable referenced but not defined in a lambda expression is a free variable

Tracing Input Returning Function
(lambda (x)
(function (lambda (y) (* x y)))

Input Returning Function
I*** New s-expression: (FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Create Outer Lambda
I***New lambda:
argNames:[X]
body:((FUNCTION (LAMBDA (Y) (* x y))))
I***Eval: (LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) –> LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Eval Outer Lambda arguments
*** Eval: 2 –> 2
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Create and Initialize for Its Parameters
I*** Variable ‘X’ set to ‘2’ in environment:
===============
=== Values ====
===============
===============
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Evaluate Body of Main Lambda Compute Inner Lambda
I*** New lambda:
argNames:[Y]
body:((* x y))
I***(FunctionCallingExpression) Eval: (LAMBDA (Y) (* x y)) –> LAMBDA (Y) (* x y)
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Evaluate Body of Main Lambda Compute Inner Function (Lambda + Environment)
I*** New function:
lambda:LAMBDA (Y) (* x y)
environment:
===============
=== Values ====
===============
===============
I*** Eval: (FUNCTION (LAMBDA (Y) (* x y))) –> #
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Evaluate its Arguments
I*** Eval: 3 –> 3
(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Bind Y in On Top of Stored Environment
***(BasicScope) Variable ‘Y’ set to ‘3’ in environment:
===============
=== Values ====
===============
=== Values ====
===============
===============

(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)

Evaluate Inner Body
I*** New ‘INTEGER’ token: number: 5
I*** IntegerAtom(number: 5)
I*** Eval: (* x y) –> 5
I*** Eval: LAMBDA (Y) (* x y) –> 5
I*** Eval: (FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3) –> 5

(FUNCALL ((LAMBDA (X) (FUNCTION (LAMBDA (Y) (* x y)))) 2) 3)