kdr@doc.ic.ac.uk (K D Rigotti) (11/24/90)
I'm looking for a *very* small program to show shallow binding in action. Any suggestions? Ideally it should work for all versions of lisp including GNU Emacs lisp (if that has shallow binding??) Thanks in advance. Kevin ---------------------------- "Information makes the world go around, money just oils the bearings"
simon@gmdtub (Simon Leinen) (11/27/90)
>>>>> On 23 Nov 90 18:15:33 GMT, kdr@doc.ic.ac.uk (K D Rigotti) said: Kevin> I'm looking for a *very* small program to show shallow binding Kevin> in action. Any suggestions? I don't wonder that no-one posted a reply yet. `Shallow binding' and `deep binding' are different implementations of special binding, but they are supposed to be semantically equivalent. If you want to decide whether your particular Lisp implementation uses shallow or deep binding, you have to look at special variable access speeds. The following little benchmark compares the access to a (special) variable on top of the binding stack vs. to one `covered' by many later bindings. In a deep binding implementation, the access to the covered binding should be slower. Unfortunately, all our Lisps use shallow binding (KCL, Allegro, and Lucid Lisp). Lisp implementations that are designed for multiprocessing may use deep binding (I think QLisp does) because context switching is faster. There may be mysterious hashing techniques for deep binding implementations that could defeat this test. The program follows on the next page. -- Simon. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; File Name: binding.cl ;;; Description: Check whether shallow or deep binding is used. ;;; Author: Simon Leinen (simon@lisp5) ;;; Date Created: 26-Nov-90 ;;; RCS $Header$ ;;; RCS $Log$ ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; #| Use this in Emacs Lisp: (defmacro time (&rest forms) (` (let ((-start-time- (the-time))) (prog1 (progn (,@ forms)) (let ((-end-time- (the-time))) (princ (format "Real time: %s" (- -end-time- -start-time-)))))))) |# (defvar *a* 1) (defvar *b* 2) (defun with-many-bindings-for-*b* (fn n-bindings n-calls) (with-many-bindings-for-*b*-aux fn n-bindings n-calls)) (defun with-many-bindings-for-*b*-aux (fn n-bindings n-calls) (if (= n-bindings 0) (dotimes (i n-calls) (funcall fn)) (let ((*b* n-bindings)) (with-many-bindings-for-*b*-aux fn (- n-bindings 1) n-calls)))) (defun special-ref-*a* () *a*) (defun special-ref-*b* () *b*) (princ "Bottom of binding stack: ") (time (with-many-bindings-for-*b* (function special-ref-*a*) 50 100000)) (princ "Top of binding stack: ") (time (with-many-bindings-for-*b* (function special-ref-*b*) 50 100000)) (princ "If the two timings differ SIGNIFICANTLY, your machine seems to use deep binding.")
pcg@cs.aber.ac.uk (Piercarlo Grandi) (11/28/90)
On 23 Nov 90 18:15:33 GMT, kdr@doc.ic.ac.uk (K D Rigotti) said: kdr> I'm looking for a *very* small program to show shallow binding in kdr> action. Any suggestions? Ideally it should work for all versions kdr> of lisp including GNU Emacs lisp (if that has shallow binding??) Shallow binding is an implementation technique. It cannot be observed or demonstrated at the language level, as it just influences the execution time of variable references in deeply nested lambda calls; it *might* be possible to concoct a very contrived example that recurses many levels deep and then makes repeated references to a fluid variable up in the environment tree; with shallow binding the recursion would take more time than with deep binding, but references to the fluid variable would take less time than with deep binding. I doubt that one can actually create a simple example in which the difference is observable (the levels of recursion must be many). Shallow binding and other implementation techniques are deep binding and cached binding. All these are discussed in Baker's CACM article (1975) "Shallow binding in Lisp 1.5". There is a possibility that you are instead interested in the difference between dynamic and static scoping, which is instead a language level feature. Any good book on Lisp will explain the difference between the binding and the scoping problems. Virtually the only Lisp dialects that have static scoping by default are Common Lisp and Scheme; all others support dynamic scoping by default, including GNU Emacs lisp. For full background and details on both the binding and the scoping issue read John Allen's book, "The Anatomy of Lisp", published by Academic Press. -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk
kdr@doc.ic.ac.uk (K D Rigotti) (11/28/90)
Aaaah! I see! Sorry folks, it was a very badly worded request, mostly because I wasn't really sure what it was I wanted to know if you know what I mean... hohum Many thanks to Simon for the program and to those who sent mail (I can't mail outside the uk so don't feel miffed if you didn't get a reply ). Kevin ---------------------------- "Information makes the world go around, money just oils the bearings"
rar (Bob Riemenschneider) (11/29/90)
=> From: pcg@cs.aber.ac.uk (Piercarlo Grandi) => Newsgroups: comp.lang.lisp => => For full background and details on both the binding and the scoping => issue read John Allen's book, "The Anatomy of Lisp", published by => Academic Press. Excellent recommendation, but it's McGraw-Hill (ISBN 0-07-001115-X). -- rar