Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!sri-spam!parcvax!hplabs!tektronix!teklds!dadla!tekla!kend
From: kend@tekla.UUCP (Ken Dickey)
Newsgroups: net.lang.lisp
Subject: Re: Common Lisp
Message-ID: <654@tekla.UUCP>
Date: Mon, 7-Jul-86 15:27:57 EDT
Article-I.D.: tekla.654
Posted: Mon Jul  7 15:27:57 1986
Date-Received: Thu, 10-Jul-86 01:24:42 EDT
References: <1023@h.cs.cmu.edu>
Reply-To: kend@tekla.UUCP (Ken Dickey)
Followup-To: net.lang.lisp
Distribution: net
Organization: Tektronix, Inc., Beaverton, OR.
Lines: 50
Keywords: lexical-lookup
Summary: lexical variable references cheap

In article <1023@h.cs.cmu.edu> shivers@h.cs.cmu.edu (Olin Shivers) writes:
>
>It isn't true that lexical variable references are slow in the interpreter.
>The trick is to allow the interpreter to do a pre-execution pass over the
>code and resolve variable references. In a lexically scoped lisp, you can
>always tell which binding a given reference refers to just by examining the
>code; that's the reason why it's called "lexical" scoping. This variable
>resolution technique is known to all Algol wizards, not just lisp folks.
>

There is another way to make lexical variable references (typically)
cheaper in interpreters.  That is to do the lookup as
	V:Id->(Env->Val) 
rather than 
	V:Env->(Id->Val) 
as in deep binding.  The gist of this is to keep an "Env-list" for
each symbol.  Lookup is then essentially a 'getprop' on the env-list.
[Ie if (getenv envN Id) is non-empty, you have found the value, else
(empty) look with a key of the next env, until found or the global
env is reached, then fail].

The cost here for failure is 
   (* number-of-environments  number-of-envlist-bindings)
which is typically (much) less than
   (* number-of-environments  number-of-ribcage-bindings)
as in deep binding.

The trick with this (ahem) scheme is in the garbage collection.  When
the ob-vec (oblist) is collected, the env-lists of the symbols are
not collected (the symbols are themselves valid only if they have a
non-null property-list).  When the environments (frames) are
collected, then the (env val) pairs are valid and so is the symbol
[so you need the vars rib of the frame, but not the values rib].

[Note that this strategy differs from that presented by Padget &
Fitch in "Closurize and Concentrate", 12th POPL].



-Ken Dickey
---------------------------------------------------
UUCP:           HOST!tektronix!tekla!kend
   Where HOST is any one of:
	masscomp,decvax,allegra,uf-cgrl,mit-eddie,mit-ems,
	uoregon,psu-cs,orstcs,zehntel,ucbcad,ucbvax,purdue,
	uw-beaver,reed, ogcvax,ihnp4,tekred,minn-ua,cbosg

CSnet: kend%tekla@tektronix 
ARPAnet: kend%tekla%tektronix@csnet-relay
---------------------------------------------------