Re: Exceptions as objects (was Re: What is wrong with OO ?)

[fjh@murlibobo.cs.mu.OZ.AU (Fergus Henderson)]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:

>I wrote:
>>>In fact, the programmer can _not_ implement dynamic scoping easily by
>>>hand in Ada and thanks to the arcane scope rules of C++ (from time to
>>>time I reread the draft C++ standard trying to find out what the scope
>>>rules _are_, does _anyone_ know?) it is even less true there.
>
>fjh@murlibobo.cs.mu.OZ.AU (Fergus Henderson) replied fliply:
>>To answer your parenthetical question, the scope rules are defined in
>>sections 3.3 [basic.scope] and 3.4 [basic.lookup] of the draft.
>
>Get real!

OK, that _was_ a bit flip.  You're right that the scope rules of C++
can be rather arcane.

>fjh proposes the following sketch of implementing a dynamically
>scoped variable in C++:
>
>>	#include "dynamic_scope.h"
>>	
>>	dynamically_scoped<int> x;
>
>>	void foo() {
>>		rebind<x> local_x;	// or something like that
>>	}
>
>Close, but not quite.  (This approach is also applicable in Ada 95.)
>
>What's wrong with it?  x has the wrong type.

You can give `x' an implicit conversion to type "reference to int".

	operator int & ();

Now, due to C++'s arcane overloading rules ;-), this is not
exactly the same in all circumstances, but it usually does
the trick.  Sometimes you may have to insert a few additional
explicit conversions.

(My compiler seems to think that you need an assignment operator
as well.  Maybe it's right.)

>In languages that have them, dynamically scoped variables follow different
>_scope_ rules from other variables, but there is nothing special about
>their _contents_.  It would be necessary to do something like
>
>	int x;
>
>	void foo() {
>	    rebind< &x > preserved_x;
>	    ...
>	}

You could do that too, and it would work fine in the case of `int'.
However, for other types that has some disadvantages.
It won't work if type of `x' doesn't allow copying.
Even if `x' can be copied, you will most likely have to do a deep copy,
which may be slow.  That's why I went for the approach with
the implicit conversion-to-reference instead.

>An "implementation" of
>dynamically scoped variables which depends on giving them the wrong
>type (your approach) _does_ impose a heavy burden on the programmer,
>because then every reference that would have been a reference to x
>has to become x.contents() or whatever you want to call it.

No, that's not correct, because you can use an implicit conversion.

>>>It is also likely to be
>>>seriously less efficient than a reasonable mechanism implemented by the
>>>compiler.
>
>>I'm not convinced.
>
>Why not.  Do you actually know any C++ compilers which make your approach
>run as fast as a good Lisp system (Harlequin, Franz, CMUCL)?  The obvious
>mechanism is essentially a Prolog-style trail.

Well, with the implementation I was thinking of, block entry and block
exit are likely to quite cheap.  The main cost of my C++ implementation
is that you have an extra indirection for each access to the variable.
But I think it will be at least competitive.

	template <class T> class dynamically_scoped;

	template <class T, dynamically_scoped<T> & ds_var> class rebind;

	template <class T>
	class dynamically_scoped {
		template <dynamically_scoped<T> & ds_var>
		friend class rebind<T, ds_var>;
		T* current_var;
		T original_var;
	public:
		dynamically_scoped() {
			current_var = &original_var;
		}
		dynamically_scoped<T>& operator = (const T &val) {
			*current_var = val;
			return *this;
		}
		operator T& () {
			return *current_var;
		}
	};

	template <class T, dynamically_scoped<T> & ds_var>
	class rebind {
		T new_var;
		T* prev_var;
	public:
		rebind() {
			prev_var = ds_var.current_var;
			ds_var.current_var = &new_var;
		}
		~rebind() {
			ds_var.current_var = prev_var;
		}
	private:
		// prevent copying
		rebind(const rebind<T, ds_var>&);
		void operator =(const rebind<T, ds_var>&);
	};

If you're willing to assume that the variable can be cheaply copied,
you can do better.  Here's an alternate implementation that has
performance characteristics that are more similar to your suggested
implementation:

	template <class T> class dynamically_scoped;

	template <class T, dynamically_scoped<T> & ds_var> class rebind;

	template <class T>
	class dynamically_scoped {
		template <dynamically_scoped<T> & ds_var>
		friend class rebind<T, ds_var>;

		T current_value;
	public:
		dynamically_scoped<T>& operator = (const T & x) {
			current_value = x;
			return *this;
		}
		operator T& () {
			return current_value;
		}
	};

	template <class T, dynamically_scoped<T> & ds_var>
	class rebind {
		T old_value;
	public:
		rebind() {
			old_value = ds_var.current_value;
		}
		~rebind() {
			ds_var.current_value = old_value;
		}
	private:
		// prevent copying
		rebind(const rebind<T, ds_var>&);
		void operator =(const rebind<T, ds_var>&);
	};

>Block entry:
>	for each dynamic variable x
>	    push contents of x onto Trail
>	push block descriptor onto Trail
>
>Block exit:
>	discard block descriptor from Trail
>	for each dynamic variable x in reverse order
>	    pop contents of x from Trail

With the second implementation above, block entry and exit are
in fact slightly cheaper:

  Block entry:
	for each dynamic variable x
	   copy (not push) contents of x onto stack

  Block exit:
	for each dynamic variable x
	   copy (not push) contents of x from stack

I tried a simple test of dynamically_scoped<int>.  My compiler (SGI
C++) generated one instruction to put the address of x in a register,
and then a load/store pair for block entry and a load/store pair for
block exit.

By storing the trail on the stack, you save having to increment the
trail pointer (the stack pointer increment is usually free, since you
normally have to increment it anyway).  You also reduce the danger
of cache collisions, although that's probably not a noticable effect.
Furthermore, unlike say Prolog, you pay the cost of trailing and
untrailing only when you're actually using it (you don't have
any untrail loops).  The downside is that you can't get tail recursion
optimization.

Most modern Unix C++ implementations use separate code address tables for
exception handling, so there's no need to push any descriptors.
(PC implementations are another matter, though -- they do normally
push and pop stuff.  I think that's mostly Microsoft's fault.)

>There are three things to be said about this:
>
>(1) it is hard to see how to do _substantially_ better than this.

Yes, but as shown above you can do slightly better, and in any case all
you really need is to not do substantially worse.

>(2) the exception unwinder uses block descriptors, it is hard to
>    see how such a _global_ mechanism can be efficiently simulated
>    by _local_ classes.

Well, the local C++ classes are making use of the underlying C++
exception handling mechanism, which could use a global block descriptor
stack or separate code address tables or some other global mechanism.

>(3) Lisp systems enforce certain _global_ restrictions on the use
>    of dynamic binding.  fjh's mechanism can simulate to some degree
>    what Lisp _allows_ but not what it _forbids_.

Could you be more specific about the restrictions that Lisp systems
enforce?

You can enforce quite a bit in C++.

>None of this should be taken as endorsing the addition of dynamic binding
>to any specific language.

Yes, and the fact that you *can* implement dynamically scoped variables
in C++ does not mean that you necessarily *should* ;-)

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.