From: Nils M Holm
Subject: Implementing closures using local-class environments in LAMBDA
Date:
Message-ID: <cje9ag$ojg$1@online.de>
While thinking about a simple method to add closures and
lexical scoping to a dynamically scoped pure LISP interpreter,
I had the following idea. Maybe somebody else has played with
this idea before, but anyway here it is:
- attach a first class environment to LAMBDA:
(LAMBDA (Y) (CONS X Y) ((X.VALUE)))
- automatically add all bindings of free variables to such
an environment whenever a lambda function escapes the
context of LAMBDA or LABEL:
((LAMBDA (X) (LAMBDA (Y) (CONS X Y))) 'VALUE)
=> (LAMBDA (Y) (CONS X Y) ((X.VALUE)))
- when LAMBDA has an environment attached, its bindings
will take effect while evaluating its term:
((LAMBDA (Y) (CONS X Y) ((X.HEAD))) 'TAIL)
; Y is bound to 'TAIL
; X is bound to 'HEAD
; (CONS X Y) is evaluated
; X and Y are unbound
=> '(HEAD.TAIL)
I already have implemented this method. You can try it online
at
http://www.t3x.org/LISP/OL/
Thanks for your interest.
Nils
F'up to: comp.lang.lisp
--
Nils M Holm <···@despammed.com> -- http://www.t3x.org/nmh/
Nils M Holm <···@despammed.com> wrote in message news:<············@online.de>...
> While thinking about a simple method to add closures and
> lexical scoping to a dynamically scoped pure LISP interpreter,
> I had the following idea. Maybe somebody else has played with
> this idea before, but anyway here it is:
I recently implemented scoping in a really dumb way. Nested dynamic
scopes give rise to evaluation frames that hold bindings. These are
normally on the stack (the interpreter's own stack). When a variable
is accessed---get this---a search takes place! If we don't find it in
the innermost frame, we look to the next enclosing one and so on. All
variables have a default local binding stored in the symbol, so if the
search fails, that place is fetched. Talk about grossly inefficient. A
closure can be readily created; I do this by actually making a copy
the stack of frames into one big vector-like object, and setting up
their links to mirror those of the original stack. That copied stack
is the closure's environment.
In this manner, you can capture the entire dynamic environment easily.
Doing so, however, is a problem, because then callers of the closure
cannot override variables that have bindings in that captured
environment. E.g. if you had some *print-base* overridden to
hexadecimal when you made the closure, you could not make that closure
output in decimal by surrounding the closure call with an override. To
solve that, I added a boolean property to each frame which is true
when that frame's dynamic parent does not lexically contain it: in
other words, the frame is the root of a lexical scope. The copying
algorithm stops when it encounters such a frame, and so the closures
are de facto lexical.
The big difference between this and CL is that there are no special
declarations. Variables are essentially lexical, except that free
references are dynamically resolved (potentially to lexical bindings
in dynamically surrounding environments). If you override a variable
that behaves like a dynamic one, like *random-state* or whatever, the
override is both lexical, in the sense that it's lexically captured by
closures, but it's also dynamic, in the sense that when you call
things, they access and modify your overridden value.
Of course, this fluffy naivete comes at a significant run-time cost.
:)
From: Matthew Danish
Subject: Re: Implementing closures using local-class environments in LAMBDA
Date:
Message-ID: <87llet2h83.fsf@mapcar.org>
Nils M Holm <···@despammed.com> writes:
> While thinking about a simple method to add closures and
> lexical scoping to a dynamically scoped pure LISP interpreter,
> I had the following idea. Maybe somebody else has played with
> this idea before, but anyway here it is:
>
> - attach a first class environment to LAMBDA:
Congratulations. This is how closures are usually implemented.
> (LAMBDA (Y) (CONS X Y) ((X.VALUE)))
Well, ok, not like that. At first, I didn't realize you meant
(LAMBDA (Y) (CONS X Y) ((X . VALUE)))
> - automatically add all bindings of free variables to such
> an environment whenever a lambda function escapes the
> context of LAMBDA or LABEL:
>
> ((LAMBDA (X) (LAMBDA (Y) (CONS X Y))) 'VALUE)
> => (LAMBDA (Y) (CONS X Y) ((X.VALUE)))
Rather than make it complicated by referring to ``escape'' why don't
you just make this evaluation rule for LAMBDA:
(defstruct closure params body env)
;; expr is an s-expr, env is an assoc-list of bindings
(defun evaluate (expr env)
(cond
((symbolp expr) (or (cdr (assoc expr env))
(error "Unbound variable ~A" expr)))
((atom expr) expr)
((eql (first expr) 'progn)
(let (result)
(dolist (e (rest expr) result)
(setf result (evaluate e env)))))
;; ...
;; Evaluation rule for LAMBDA
((eql (first expr) 'lambda)
(make-closure :params (second expr)
:body (cons 'progn (cddr expr))
:env env))
(t
;; ...
;; Evaluation rule for function call
(let* ((vals (mapcar (lambda (e) (evaluate e env))
expr))
(closure (first vals)))
(assert (closure-p closure))
(evaluate (closure-body closure)
(nconc (mapcar 'cons
(closure-params closure)
(rest vals))
(closure-env closure)))))))
--
;; Matthew Danish -- user: mrd domain: cmu.edu
;; OpenPGP public key: C24B6010 on keyring.debian.org
From: Nils M Holm
Subject: Re: Implementing closures using first-class environments in LAMBDA
Date:
Message-ID: <cjgao2$vd4$1@online.de>
Matthew Danish <··········@cmu.edu> wrote:
> Congratulations. This is how closures are usually implemented.
Thanks.
> Well, ok, not like that. At first, I didn't realize you meant
>
> (LAMBDA (Y) (CONS X Y) ((X . VALUE)))
In what way are closures implemented usually? Since you emphasize
the dot: using lists of lists rather than lists of pairs? That would
not make a big difference, would it?
> Rather than make it complicated by referring to ``escape'' why don't
> you just make this evaluation rule for LAMBDA:
I had thought about implementing it this way, but this method
would attempt to create closures in a lot of situations where
it is not really neccessary. In particular, functions of the form
(LABEL ((F (LAMBDA ...))
(G (LAMBDA ...))
...
EXPR))
would involve a lot of superflous computations when none of its
functions actually escapes.
And then, detecting an escaping function is not that hard. When
unbinding function arguments, you check whether the result
expression is a lambda function and if it is, you create a
closure.
In my implementation, these are two lines of code and save a
lot of unneccessary calls to the routine that creates closures.
Nils
--
Nils M Holm <···@despammed.com> -- http://www.t3x.org/nmh/