From: axs@cs.bham.ac.uk (Aaron Sloman)
Newsgroups: comp.lang.pop
Subject: Re: dlocals etc. (and shallow binding)
Date: 24 Jan 93 03:55:37 GMT
Organization: School of Computer Science, University of Birmingham, UK

pop@cs.umass.edu ( Robin Popplestone ) writes:

> Date: 20 Jan 93 13:51:04 GMT
> Organization: University of Massachusetts, Amherst
>
> Shallow binding of POP-2 variables arose because the 4130 only had one
> index register which we needed to use as a stack pointer, since that
> provided a general low-space-overhead way of calling functions in what was
> a modified functional language. This always appeared as the wrong way of
> doing things, since the lambda calculus calls for lexical binding, but was
> justified on the grounds that existing lexical binding techniques (as
> embodied in Algol) were also wrong, since they didn't provide the
> possibility of returning a function as a result of a function. We were of
> course aware of the debugging advantages of having part of the environment
> available for very little cost.

It is interesting that Pop-2 and Maclisp both used incremental
compilers rather than interpreters, and both used shallow binding
for dynamically scoped identifiers rather than deep binding. By
contrast Interlisp was interpreted and used deep binding, which
required searching up a list of variable value pairs to get the
value of a variable that was last declared local in some calling
procedure.

It turned out that shallow binding, in which all occurrences of a
particular variable pointed to the same memory location, whose value
had to be saved somewhere on entry to a procedure in which the
variable was local and then copied back on exit had a very nice
property, and I believe this happened entirely by accident rather
than by design.

A really "clean" implementation would have required all local
variables to have their values initialised to some safe default on
procedure entry, e.g. to "undef". Instead, for the sake of
efficiency all the implementations of Pop that I have used employed
shallow binding and always left the old value in the variable on
procedure entry, which speeded up procedure entry, and could
occasionally cause obscure bugs, when people forgot to assign to
local variables and they inherited values from the preceding
procedure activation.

But it also had a very nice side effect, namely that shallow-bound
dynamic variables could be used to produce an "incremented context"
mechanism that was automatically reset on procedure exit.

For example, the Pop-11 pattern matcher keeps a list of variables
whose values have been set in the dynamic variable popmatchvars,
which is local to the matcher and also has the empty list as its
global value. This means that inside a recursive call of the
matcher the previously bound variables are already available, and if
new bindings are set, they can be "pushed" onto the front of the
list, e.g. using

    [^word ^^popmatchvars] -> popmatchvars;

However on exit from the recursive call, popmatchvars will
automatically be re-set to its original value, and this is
guaranteed to happen whether the exit is normal or caused by an
interrupt, or a use of "exitfrom", or suspension of a process, etc.

Similarly, printing routines often need to keep count of the level
of recursion to prevent infinite printing. So it is quite common to
use a variable like

    vars
        printlevel = 0,
        max_printlevel = 5;


    define print_procedure( ..... );
        dlocal printlevel = printlevel + 1;

        if printlevel >= max_printlevel then
            ... print closing bracket and return ....
        else
            print suitable opening bracket
            call print_procedure recursively on the components
                of the structure being printed.

        endif
    enddefine;

Because of the way dynamic locals, declared using dlocal or vars,
work, it is guaranteed that the top level value of the variable will
always be reset when the procedure exits, normally or otherwise.

The alternative to these dynamically scoped uses of printlevel and
popmatchvars (and similar things, like interrupt, cucharout,
prmishap, etc.) would have been to require all these values to be
passed explicitly as extra arguments in any procedure that might
call a procedure that used these values, or else to do what Robin
does, namely:

> My own practice these days is to avoid any dlocals in code I actually
> write, by using an extra argument to any function (usually called "Env")
> which is a data-structure that bundles up any kind of style switch.

But of course, you have to keep changing the definition of the
structure Env for different purposes, which can makes reuse of code
difficult. Also when the environment changes you either have to use
dlocal anyway, to ensure that it is automatically reset whenever
procedure exit occurs, or else you have to copy the structure on
entry to any procedure that can change it.

I think dynamic local expressions, of which dynamic local variables
are a special case, handle this rather elegantly, and I see no
reason for avoiding them, provided that their use is disciplined.

It's interesting that these extra mechanisms to ensure automatic
resetting of context are needed only because procedures can exit
abormally. If a simpler control regime were used, and only ordinary
procedure exit were available, then all tidying up and resetting of
context could be done by explicit code at the end of a procedure
definition, and there would be no need for dynamically scoped local
variables.

In relation to some of the earlier discussion in this newsgroup, it
is interesting to note that the dlocal mechanism in pop-11 can be
used with global lexically scoped variables, i.e. file-local
lexicals. This undermined the supposed contrast between dynamic and
lexical scoping, and instead caused John Gibson to introduce the
term "permanent" in contrast with "lexical".

I'll return to that topic in a later posting.

Aaron
-- 
Aaron Sloman,
School of Computer Science, The University of Birmingham, B15 2TT, England
EMAIL   A.Sloman@cs.bham.ac.uk  OR A.Sloman@bham.ac.uk
Phone: +44-(0)21-414-3711       Fax:   +44-(0)21-414-4281
From: sfk@otter.hpl.hp.com (Steve Knight)
Date: Sun, 24 Jan 1993 16:47:27 GMT
Subject: VED's future
Organization: Hewlett-Packard Laboratories, Bristol, UK.