Post by luserdroog Post by Kaz Kylheku Post by luserdroog
I have a partly written Lisp interpreter that uses straight-ahead
There's a single global env association list, and executing a
lambda involves prepending the new assoc pairs in front of the
env before recursing to evaluate the body.
How does lexical scoping work? Does it need stuff like Weizenbaum
environments? Doing it right means closures somewhere, right?
What's the simplest strategy for modifying a dynamic scoping lisp
to a lexically scoping one?
If you have a dynamically scoped list where there is a global env
association list, that means that you are not passing that list around.
It's held in some global variable, and you're saving, modifying and
restoring that global variable to do the dynamic binding.
To achieve lexical scope, you must, instead of using a global variable,
pass the environment as an argument. There is no need to save and
restore anything then, because there is no global. But every function of
the evaluator needs the environment parameter.
Ok. I'm partly doing this. But currently the global env is modified by
SET, SETQ, and DEFUN. So I guess these functions and functions that call
If you're interpreting a dynamically scoped Lisp using an interpreter
in Common Lisp, you might as well do one of two things. Given a form
;; save and restore dynamic environment
1. Use unwind-protect to guard the restoration of the dynamic
environment, so the expansion is like this:
(let ((#:g025 %dyn-env%))
(progn (bind-dynamic-var ...)
(setf %dyn-env% #:g025))
2. Just use a special variable for the environment, so
we bootstrap the dynamic scope in the interpreted language
from that of the host language.
(let ((*dyn-env* *dyn-env*)) ;; save and restore
Dynamic scope has the virtue that it's easy for the host language's
dynamic scope to be used by the hosted language. You can just directly
use host language variables for the dynamic variables of the hosted
Common Lisp has a special operator progv for binding dynamic variables,
which basically exists in supports of writing dynamically scoped
interpreters and related techniques.
Post by luserdroog
them will need modification to pass the env and return a modified one.
So I suppose getting rid of the global env is the first step.
Yes, and no.
Let me now describe a different implementation strategy.
Dynamnic scope can be made to behave like lexical scope, yet
retain the dynamism.
Firstly, let me say that even if you pass the environment around
everywhere and avoid the global variable, you can still have dynamic
scope. You can do that by making closures dumb (no environment stored in
them) and by passing the envrionment even into the function application
machinery, so that function bodies are evaluated in a scope which
includes the passed-down environment extended with the parameter
bindings (and not any closed environment).
About 17 years ago I wrote a dialect called VoqLisp (in C++) which
passed the environment around, but passed it into the function calling
machinery also. Functions could see the values of parent variables:
(let ((*foo* 42))
(fun)) ;; fun could see *foo*
Yet, lexical closures worked in this dialect.
How that worked was: each environment frame carried a "is-top-level"
flag. Whenever a function was called, the brand new environment
frame which was created for it, and pushed onto the environment
stack, had this flag set to true.
The lambda operator created a closure by taking a delimited slice of the
environment, up to and including the closest frame marked is-top-level.
It made a copy of this environment and stuck it into the closure.
The invocation of a lambda spliced the captured environment
onto the environment. So that is to say, a function would see its
parameter bindings first, the captured environment slice second,
and after that, the current dynamic scope.
(In retrospect, all of this is eerily similar to one of the possible
strategies of implementing delimited closures. My implementation was
doing with variable bindings what delimited closures do with the entire
This scoping strategy came in quite handy in the application,
which was API testing on an embedded device.
Tests could be written which were governed by multiple parameters
represented as special variables.
Specific test cases could customize some of those variables
and then produce a closure, for instance:
(let ((*foo-param* foo-var)
(make-thread (lambda () (frobozz-test))))
The above overrides two parameters. These overrides are captured
by the lambda, which is then the thread function for a new thread.
The thread runs (frobozz-test) which uses those values of
*foo-param* and *bar-param*, and the pervasive dynamic defaults
of all other parameters (which could be numerous).
When the lambda is invoked, the captured dynamic environment
slice containing the *foo-param* and *bar-param* bindings
is pushed on top of whatever dynamic environment is current.
Then the parameters are pushed (there aren't any in this case),
and then the body is evaluated.
You can't do this in exactly the above way with either lexical scope or
dynamic scope. With lexical + dynamic scope can do it like this:
(make-thread (lambda ()
(let ((*foo-param* foo-var)
So though it may not look like a big deal, it's still neat how
you could host that binding outside of the lambda, and still
have it work.
For one thing, how it this was practically useful useful is that
multiple tests could share the parameters:
(let ((*foo-param* foo-var)
(make-thread (lambda () (frobozz-test)))
(make-thread (lambda () (scrotelytest)))
I.e. by being able to move the binding out of the lambda, we can share
it among multiple lambdas easily. This gave the code an intuitive
structure: the code could have a section where parameters are
established with let, wrapped around code that farms multiple tests
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1