Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!unido!opal!tub!gmdtub!simon!simon
From: simon@gmdtub (Simon Leinen)
Newsgroups: comp.lang.lisp
Subject: Re: Shallow Binding
Message-ID: <SIMON.90Nov26185913@lisp5.first.gmd.de>
Date: 26 Nov 90 17:59:13 GMT
References: <KDR.90Nov23181533@pelican.doc.ic.ac.uk>
Sender: news@bigfoot.first.gmd.de
Reply-To: simon@opal.CS.TU-Berlin.DE
Distribution: comp
Organization: GMD-FIRST, Berlin
Lines: 67
In-reply-to: kdr@doc.ic.ac.uk's message of 23 Nov 90 18:15:33 GMT

>>>>> 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.")