The Inbox: Collections-ul.564.mcz

> On 3 February 2014 13:48,  <[hidden email]> wrote:
>> A new version of Collections was added to project The Inbox:
>> http://source.squeak.org/inbox/Collections-ul.564.mcz
>>
>> ==================== Summary ====================
>>
>> Name: Collections-ul.564
>> Author: ul
>> Time: 3 February 2014, 2:35:36.802 pm
>> UUID: 4b9a37ef-df86-40a0-a0dd-8e8b2c04d4ed
>> Ancestors: Collections-ul.563
>>
>> Make sure that Array >> #isLiteral won't get into an infinite recursion, even if the receiver has an recursive structure.
>>
>> =============== Diff against Collections-ul.563 ===============
>>
>> Item was changed:
>>  ----- Method: Array>>isLiteral (in category 'testing') -----
>>  isLiteral
>> +
>> +       ^self class == Array and: [
>> +               self isLiteralIfContainedBy: IdentitySet new ]!
>> -       ^self class == Array and: [self allSatisfy: [:each | each isLiteral]]!
>>
>> Item was added:
>> + ----- Method: Array>>isLiteralIfContainedBy: (in category 'testing') -----
>> + isLiteralIfContainedBy: parents
>> +       " Answer whether the receiver has a literal text form recognized by the compiler. Precondition: the receiver is an instance of Array. "
>> +
>> +       (parents includes: self) ifTrue: [ ^false ].
>> +       parents add: self.
>> +       1 to: self size do: [ :index |
>> +               | element |
>> +               element := self at: index.
>> +               (element class == Array
>> +                       ifTrue: [ element isLiteralIfContainedBy: parents ]
>> +                       ifFalse: [ element isLiteral ]) ifFalse: [ ^false ] ].
>> +       parents remove: self.
>> +       ^true!
>
> 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?)

> On 3 February 2014 14:49, Tobias Pape <[hidden email]> wrote:
>> On 03.02.2014, at 15:28, Frank Shearar <[hidden email]> wrote:
>>
>>> On 3 February 2014 13:48,  <[hidden email]> wrote:
>>>> A new version of Collections was added to project The Inbox:
>>>> http://source.squeak.org/inbox/Collections-ul.564.mcz
>>>>
>>>> ==================== Summary ====================
>>>>
>>>> Name: Collections-ul.564
>>>> Author: ul
>>>> Time: 3 February 2014, 2:35:36.802 pm
>>>> UUID: 4b9a37ef-df86-40a0-a0dd-8e8b2c04d4ed
>>>> Ancestors: Collections-ul.563
>>>>
>>>> Make sure that Array >> #isLiteral won't get into an infinite recursion, even if the receiver has an recursive structure.
>>>>
>>>> =============== Diff against Collections-ul.563 ===============
>>>>
>>>> Item was changed:
>>>> ----- Method: Array>>isLiteral (in category 'testing') -----
>>>> isLiteral
>>>> +
>>>> +       ^self class == Array and: [
>>>> +               self isLiteralIfContainedBy: IdentitySet new ]!
>>>> -       ^self class == Array and: [self allSatisfy: [:each | each isLiteral]]!
>>>>
>>>> Item was added:
>>>> + ----- Method: Array>>isLiteralIfContainedBy: (in category 'testing') -----
>>>> + isLiteralIfContainedBy: parents
>>>> +       " Answer whether the receiver has a literal text form recognized by the compiler. Precondition: the receiver is an instance of Array. "
>>>> +
>>>> +       (parents includes: self) ifTrue: [ ^false ].
>>>> +       parents add: self.
>>>> +       1 to: self size do: [ :index |
>>>> +               | element |
>>>> +               element := self at: index.
>>>> +               (element class == Array
>>>> +                       ifTrue: [ element isLiteralIfContainedBy: parents ]
>>>> +                       ifFalse: [ element isLiteral ]) ifFalse: [ ^false ] ].
>>>> +       parents remove: self.
>>>> +       ^true!
>>>
>>> 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.

> On 3 February 2014 15:06, Tobias Pape <[hidden email]> wrote:
>> On 03.02.2014, at 16:01, Frank Shearar <[hidden email]> wrote:
>>
>>> On 3 February 2014 14:49, Tobias Pape <[hidden email]> wrote:
>>>> On 03.02.2014, at 15:28, Frank Shearar <[hidden email]> wrote:
>>>>
>>>>> On 3 February 2014 13:48,  <[hidden email]> 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!

>> (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 [1] 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:.
> [1] http://www.cs.indiana.edu/~sabry/papers/delim-dyn-bind.pdf

> On 3 February 2014 16:08, Tobias Pape <[hidden email]> wrote:
>> On 03.02.2014, at 16:14, Frank Shearar <[hidden email]> wrote:
>>
>>> On 3 February 2014 15:06, Tobias Pape <[hidden email]> wrote:
>>>> On 03.02.2014, at 16:01, Frank Shearar <[hidden email]> wrote:
>>>>
>>>>> On 3 February 2014 14:49, Tobias Pape <[hidden email]> wrote:
>>>>>
>>>>> 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 [1] 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:.
>>> [1] 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!