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)