Last updated at 7:21 pm UTC on 29 September 2016
Notes about dynamic variables
[squeak-dev] The Inbox: Collections-ul.564.mcz
Frank Shearar frank.shearar at gmail.com
Mon Feb 3 16:27:49 UTC 2014
Previous message: [squeak-dev] The Inbox: Collections-ul.564.mcz
Next message: [squeak-dev] The Inbox: Collections-ul.564.mcz
On 3 February 2014 16:08, Tobias Pape wrote:
> On 03.02.2014, at 16:14, Frank Shearar wrote:
>> On 3 February 2014 15:06, Tobias Pape wrote:
>>> On 03.02.2014, at 16:01, Frank Shearar wrote:
>>>> On 3 February 2014 14:49, Tobias Pape wrote:
>>>>> On 03.02.2014, at 15:28, Frank Shearar wrote:
>>>>>> On 3 February 2014 13:48, wrote:
>>>>>> So this is a basic depth first traversal with cycle protection, yes?
>>>>>> (This pattern seems to crop up _a lot_. Maybe it's worth pulling out
>>>>>> as a separate algorithm?)
>>>>> Well, there are two such applications:
>>>>> One with an explicit down-handling of a variable (like this)
>>>>> and one with an implicit variable (semi-global)
>>>>> (Dynamic variable, probably, at least thread-local)
>>>>> I would like to have both.
>>>>> I propose the (seaside-inspired) #use:during: message for the second.
>>>> Except that DynamicVariable's #use:during: is incompatible with
>>>> stack-slicing, because those kinds of dynamic variables aren't
>>>> delimited. (Unlike resumable exceptions, for instance.
>>> Sorry, I (currently) donít know what you mean by stack-slicing.
>>> Are we speaking of Martin von LŲwisí DynamicVariables currently in 4.5/trunk
>>> that are based on Thread-local storage
>>> or the Seaside ones based on Exceptions?
>> Ah! I thought that the Seaside ones were the same the DynamicVariable in trunk!
> No; the trunk ones should be better, performance-wise, since they donít
> have to walk the stack on #value
Absolutely they're more efficient. O(1) lookup versus O(n) in the call
stack. And they're also broken when considered with delimited
continuations :) I haven't pushed hard on the issue because I don't
know yet how to make them efficient. (Other languages do things like
"shallow binding", in Henry Baker's terminology. We could possibly get
the same thing with VM modifications.)
>>> (I just see that DV is using #value:during: rather than #use:during:
>>> the former is consistent while the latter IMHO speaks better)
>> Right. So if Seaside's version uses resumable exceptions, there's no trouble.
>> By "stack-slicing" I mean tricks like using delimited continuations.
>> Oleg Kiselyov demonstrated  how, since there are multiple
>> reasonable ways of using delimited control and dynamic bindings
>> (trunk's DynamicVariable) together, that there were therefore _no_
>> reasonable ways of combining them. Dynamic bindings either capture too
>> much or too little of the environment. The answer is to _delimit_ the
>> dynamic bindings. Handily, that's exactly what we have with resumable
>> exceptions + #on:do:.
>>  http://www.cs.indiana.edu/~sabry/papers/delim-dyn-bind.pdf
> Yes, but I think that is more of concern for continuations than for
> dynamically scoped variables, no? Arenít those by definition delimitted?
No, DynamicVariable style dynamic variables are not delimited, because
their keep-the-old-value-around and their restore-old-value logic
isn't on the call stack. But that's an implementation detail. The
point of the referenced paper is that _no matter what_ implementation
of dynamic variables you have, unless they're delimited they're broken
when considered with delimited continuations. (Or delimited
continuations are broken with them. Point is, their semantics cannot
be sensibly combined.) And delimited continuations are baked into the
bedrock of the language!
See also http://www.lshift.net/blog/2012/06/27/resumable-exceptions-can-macro-express-delimited-dynamic-variables/