On Wed, Oct 13, 2010 at 12:58 PM, Igor Stasenko <siguctua at gmail.com> wrote:

> 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.
>

OK, how about
    boo ?= #foo:bar: ? #baz
?


The main problem we have now is finding space in the bytecode.  At least for
me, the remaining bytecodes have all been taken by Newspeak (and I'm eager
to get Newspeak running on Cog).  So my plan is new object representation,
new bytecode set, then cas.


> >>
> >>
> >> >>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20101013/2e8d17dc/attachment.htm