Re: let-fluid problem

[Lars Thomas Hansen <lth@xxxxxxxxxxx>]

(Second followup, different subtopic)

Olin writes (in an earlier message, sorry for lengthy quote):

>I would like to argue against any DYNAMIC-WIND + SET! sort of
>"fluid variable" system. The problem is threads. If you have a
>thread model, then any thread switch involves unwinding up the
>stack to the common ancestor continuation, then winding down into
>the activated continuation. This seems unacceptably expensive; thread
>switch should be a low-overhead operation.
>
>Because of this issue, I strongly prefer making fluid variables
>a primitive construct. Scheme48's system is a pretty canonical example
>of this genre. "Fluid variables" are data structures. So you have the
>following primitive procedures:
>   (MAKE-FLUID value) -> fluid
>   (LET-FLUID fluid value thunk)
>   (LET-FLUIDS fluid1 value1 ... fluidn valuen thunk)
>   (FLUID fluid) -> value
>   (SET-FLUID! fluid value)
>There are no primitive syntax forms. This design is not unique to S48;
>I believe it was proposed by someone other than Kelsey & Rees, and
>is used elsewhere (but I can't recall who or where).
>
>Fluid values are cells that have dynamic scope, as provided by LET-FLUID.
>You typically bind them to global vars, e.g.
>    (define $cwd (make-fluid #f))
>    (define (with-cwd dir thunk) (let-fluid $cwd dir thunk))
>Throwing in or out of LET-FLUID scope does the right thing, as you'd want.
>
>Single-threaded implementations can provide fluids using DYNAMIC-WIND,
>*but* multithreaded implementatins can implement fluids using deep
>binding techniques, providing fast thread switch. This is not possible
>with a system that actually effects variables.

Remarkably, it _is_ possible.

The specification only says that valuables are stored in the dynamically
bound variables, but specifies nothing about the mechanism.  All we need
is a mechanism that (a) allows code inside the scope of the FLUID-LET to
get and set the dynamically bound values, (b) allows code outside the
scope of a FLUID-LET to get and set the original value, and (c) gets rid
of the unwind/wind problem.

For the sake of argument, take the case where the dynamically bound
variable is a global.  In Larceny, a global has a single value slot, and
reading a global is implemented using the following code sequence:

get() =
	get constant-vector from procedure
	get global-cell from constant-vector
	get global-cell.value
	if value is #!undefined, then TRAP
	return value

and writing a global is implemented using the following sequence:

store(object) =
	get constant-vector from procedure
	get global-cell from constant-vector
	store object in global-cell.value

This mechanism can be changed as follows.  The idea is to use the
undefined-checking as a fast check for fluidness and handle dynamically
bound variables out-of-line.  

A global cell is given a second value word, whose initial value is #f.
If its value is #f then the global is not dynamically bound by any part
of the program; if its value is #t, then some part of the program has a
FLUID-LET in effect on the variable.

The code for reading the global is modified as follows:

	[get cell as before]
	get global-cell.value1
	if value1 is #!undefined, then			[ fluid or undefined ]
		get global-cell.value2
		if value2 is #f, then 
			TRAP				[ undefined variable ]
		return lookup-fluid(global-cell)	[ fluid ]
	else return value1				[ normal ]

The code for writing the global is modified as follows:

	[get cell as before]
	get global-cell.value1
	if value1 is #!undefined, then			[ maybe fluid? ]
		get global-cell.value2
		if value2 is #f, then			[ undefined ]
			store object in global-cell.value1
		else					[ fluid ]
			store-fluid(global-cell,object)
	else store object in global-cell.value1

The functions lookup-fluid and store-fluid can use whatever storage
mechanism they like to map variables to values (notably thread-local
storage and deep binding).  

One piece remains: FLUID-LET would do something like this on entry:

	if global is already dynamically bound then
		save current value 
		store new value for lookup-fluid to find
	else
		save current value for lookup-fluid to find; this is
			the value outside any FLUID-LET
		set global.value1 to #!undefined
		set global.value2 to #t
		store new value for lookup-fluid to find

and the opposite on exit, except that it takes a little effort to make
sure that the last thread to undo a fluid binding on the global restores
the global to a "normal" value.

The cost to code that reads globals is 0 for globals that are not
dynamically bound, and a call-out of some sort for globals that are
dynamically bound.  The cost in code size is effectively 0 because the
code that checks value2 can be moved into the trap handler.

The cost to code that writes globals is a compare and statically
predictable branch for globals that are not dynamically bound, and in
addition a call-out for globals that are dynamically bound.

The space cost is one _bit_ per global, which in some implementations
will probably need to be rounded up to one or two words.

In addition, the mechanism requires that global-variable checking is
never turned off in programs that use fluid variables implemented
with this technique.

For lexically scoped variables (I find I use fluid-let with these more
than with globals) the problem is a little thornier because they are not
usually checked for definedness; however, if FLUID-LET is known to the
compiler then the compiler can insert the necessary checks on access
to variables that are fluidly bound in the lexical scope.

(For multiprocessors -- well, I don't know.  I didn't say I was
advocating this implementation, only that the SRFI-15 spec does not
necessarily imply the unwind/wind cost on a thread switch.)

--lars