On 13 October 2010 21:56, Eliot Miranda <eliot.miranda at gmail.com> wrote:
>
>
> On Wed, Oct 13, 2010 at 11:37 AM, Igor Stasenko <siguctua at gmail.com> wrote:
>>
>> On 13 October 2010 21:06, Eliot Miranda <eliot.miranda at gmail.com> wrote:
>> >
>> >
>> > On Wed, Oct 13, 2010 at 9:41 AM, Tom Rushworth <tom_rushworth at mac.com>
>> > wrote:
>> >>
>> >> Hi Igor, Eliot,
>> >>
>> >> Eliot, I'm not sure I understood your comment:
>> >>
>> >> On 2010-Oct-13, at 08:55, Eliot Miranda wrote:
>> >>
>> >> > Right.  And because Smalltak can't reify variables and CAS is an
>> >> > operation on a variable CAS can't be implemented as a primitive on
>> >> > variables.  There's no way to express "pass a variable to a
>> >> > primitive",
>> >> > only "pass an expression (which may be the value of a variable)" to a
>> >> > primitive".  One could do it with a primitive on an object, e.g.
>> >> > thisContext at: tempIndex compareWith: match andSetTo: expr, or
>> >> > anObject
>> >> > instVarAt: varIndex compareWith: match andSetTo: expr but that's
>> >> > soooo
>> >> > ugly.  Hence I think it is better done using a special assignment
>> >> > operator.
>> >
>> > I mean one can't write
>> >     | t |
>> >     self compare: t andSwap: expr
>> > because in the above the rvalue of t is passed, not it's lvalue, and cas
>> > needs to operate on an lvalue (rvalue == read value, or value of a
>> > variable;
>> > lvalue = location value, or address of a variable).  Clearly cas needs
>> > to
>> > apply to a variable, not the value in the variable.  The variable's
>> > value is
>> > compared and the variable is set to a new value if it matches.  Look at
>> > Igor's example and you'll see his primitive on Arrays passes an lvalue
>> > since
>> > the primitive takes the index of an array element.
>> > e.g. if you implemented CAS in C using functions instead of macros you'd
>> > know that you couldn't do it with int cas(int var, int match, int new)
>> > but
>> > you'd know that you can do it with int cas(int *var, int match, int new)
>> > and
>> > ... int v; ... cas(&v, match, new)
>> >
>> >>
>> >> Doesn't this apply to Igor's proposed atomic swap as well?  The target
>> >> in
>> >> Igor's example was a variable "locked" which was clearly meant to be
>> >> visible
>> >> to other threads.
>> >
>> > Yes.  First time I read Igor's post I on;y saw the initial
>> > "| var1 var2 temp |
>> > temp := var1.
>> > var1 := var2.
>> > var2 := temp."
>> > which I rejected and didn't read further.  Now I see the :=:.  I don't
>> > like
>> > this because it doesn't map as nicely to CAS which I like using.  I like
>> > the
>> > boolean result one gets fro CAS that says the assignment either happened
>> > or
>> > it didn't.  Atomic swap is more low-level.  I then have to inspect the
>> > value
>> > the variable used to have and undo the swap if it wasn't what was
>> > expected.
>> >  So
>> >         | var |
>> >         var ?= expr : match
>> > is equivalent to
>> >         [| var scratch |
>> >         scratch := expr.
>> >         var :=: scratch.
>> >         scratch == match
>> >             ifTrue: [true]
>> >             ifFalse: [var :=: scratch. false]] valueUninterruptibly
>> > Hence I think :=: is too low-level.
>> >
>>
>> well, once you start using valueUninterruptibly, there is no much
>> reason to use/introduce atomic swap nor cas :)
>
> Right :)
>
>>
>> moreover, i see no trivial way to implement CAS using atomic swap,
>> while reverse is trivial.
>
> Is it, or does it also rely on uninterruptbility?  Is this right?
>     v1 :=: v2
> is equivalent to
>     [ | scratch |
>      scratch := v1.
>      v1 ?= v2 : scratch] whileFalse.
>      v2 := scratch.
>

Nope! Not in all cases.

If v1 and v2 having equal significance in algorithm, not just v1,
then it won't work.
I mean, if the above will be interrupted after leaving the loop but
before you assign to v2 (v2 := scratch)
and your code expects that not only v1 swapped correctly, but v2 as well,
then you're in trouble.

Swap is symmetric, i.e. v1 :=: v2 should be semantically equal to v2 :=: v1.
But its not achievable unless its also atomic.

So, i must confess (again), that CAS cannot serve as a complete
replacement for atomic swap.


>
>> >From this point of view, CAS is better.
>>
>> >>
>> >> If that's the case, then they both need to be implemented with a
>> >> special
>> >> assignment operator, and Igor and I can get back to arguing the merits
>> >> of
>> >> the atomic swap versus the atomic compare and swap :).  If not, then
>> >> Igor's
>> >> swap has a clear advantage and I guess you can both ignore the rest of
>> >> this
>> >> email...
>> >
>> > Um, mine /does/ use a special assignment operator, "?= :" :)
>> >
>>
>> var ?= match : expression
>>
>> could mean a lot of hacking in compiler. how about:
>>
>> var ?= { match . expression }
>>
>> so, you just need to introduce a new binary operator ?= "CAS
>> assignment" or "conditional assignment"
>> which is much simpler to hack comparing to trinary one.
>
> That's a good suggestion, bit let's see.  Personally I find  var ?= { match
> . expression } ok but a little flowery :)
>

Yes. But it looks more conformant to traditional ST syntax.  :)

>> And you can also force compiler to expect only '{' after ?=, so no
>>
>> var ?= foo
>> var ?= #( foo )
>> var ?= self bar
>>
>> will be allowed.
>
> But ?= : is no more difficult than parsing expressions within keywords.  I
> guess it'll look something like
>     conditionalAssignment: varNode
> " var '?=' expression ':' match => ConditionalAssignmentNode."
> | loc start valueNode |
> (loc := varNode assignmentCheck: encoder at: prevMark + requestorOffset) >=
> 0 ifTrue:
> [^self notify: 'Cannot store into' at: loc].
> start := self startOfNextToken.
> self advance.
> self expression ifFalse: [^self expected: 'Expression'].
> newValueNode := parseNode.
> (self match: #colon) ifFalse: [^self expected: 'colon'].
> self advance.
> self expression ifFalse: [^self expected: 'Expression'].
> parseNode := ConditionAssignmentNode new
> variable: varNode
> value: valueNode
> match: valueNode
> from: encoder
> sourceRange: (start to: self endOfLastToken).
> varNode nowHasDef.
> ^true

Okay, if you think its easy. No problem.
But i am a bit worrying about parsing & clearly reading following:

boo ?= #foo:bar: : #baz: .

colon seems not a good choice here.

>>
>>
>> >>


-- 
Best regards,
Igor Stasenko AKA sig.