Asp Forum - Local variable in loop affects callcc

Pinku Surana

9/9/2008 4:54:00 PM

I was trying to do some simple backtracking, but it kept failing for
some reason. In the simplified version below, I use continuations to
return either a 1 or 2 from interval. testcc assigns a value to the
array, prints it out, then calls the next continuation on the stack
(@next_cc) to jump back into interval and return the other number. The
output should be:
[1, 1]
[1, 2]
[2, 1]
[2, 2]

But if I introduce a temporary local variable, I get this instead:
[1, 1]
[1, 2]
[1, 1] # WRONG
[1, 2] # WRONG

The local variable seems to cause the continuations to jump only to
the point where i=1, not where i=0 where it should go. How does a
local variable effect continuations like that?

I'm using "ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]" built
for Ubuntu. Thanks for your help.

def interval
return callcc { |ret|
callcc { |k|
@next_cc.push(k)
ret.call(1)
}
ret.call(2)
}
end

def testcc
@next_cc = []
a = Array.new(2)
for i in 0...2
# This produces the WRONG output
# x = interval
# a[i] = x

# This produces the CORRECT output
a[i] = interval
end

puts a.inspect

while (not @next_cc.empty?) do
@next_cc.pop.call
end
end

7 Answers

David A. Black

9/9/2008 5:31:00 PM

Hi --

On Wed, 10 Sep 2008, Pinku Surana wrote:

> I was trying to do some simple backtracking, but it kept failing for
> some reason. In the simplified version below, I use continuations to
> return either a 1 or 2 from interval. testcc assigns a value to the
> array, prints it out, then calls the next continuation on the stack
> (@next_cc) to jump back into interval and return the other number. The
> output should be:
> [1, 1]
> [1, 2]
> [2, 1]
> [2, 2]
>
> But if I introduce a temporary local variable, I get this instead:
> [1, 1]
> [1, 2]
> [1, 1] # WRONG
> [1, 2] # WRONG
>
> The local variable seems to cause the continuations to jump only to
> the point where i=1, not where i=0 where it should go. How does a
> local variable effect continuations like that?
>
> I'm using "ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]" built
> for Ubuntu. Thanks for your help.
>
>
>
> def interval
> return callcc { |ret|
> callcc { |k|
> @next_cc.push(k)
> ret.call(1)
> }
> ret.call(2)
> }
> end
>
> def testcc
> @next_cc = []
> a = Array.new(2)
> for i in 0...2
> # This produces the WRONG output
> # x = interval
> # a[i] = x
>
> # This produces the CORRECT output
> a[i] = interval
> end
>
> puts a.inspect
>
> while (not @next_cc.empty?) do
> @next_cc.pop.call
> end
> end

I haven't unraveled it entirely but I believe it's not about the local
variable itself; it's about the fact that the interval method gets
called before the assignment to a[i]. If you do this:

a[i] = x = interval

you'll get the result you want.

David

--
Rails training from David A. Black and Ruby Power and Light:
Intro to Ruby on Rails January 12-15 Fort Lauderdale, FL
Advancing with Rails January 19-22 Fort Lauderdale, FL *
* Co-taught with Patrick Ewing!
See http://www.r... for details and updates!

Pinku Surana

9/9/2008 6:46:00 PM

On Sep 9, 1:30 pm, "David A. Black" <dbl...@rubypal.com> wrote:
> Hi --
>
>
>
> On Wed, 10 Sep 2008, Pinku Surana wrote:
> > I was trying to do some simple backtracking, but it kept failing for
> > some reason. In the simplified version below, I use continuations to
> > return either a 1 or 2 from interval. testcc assigns a value to the
> > array, prints it out, then calls the next continuation on the stack
> > (@next_cc) to jump back into interval and return the other number. The
> > output should be:
> > [1, 1]
> > [1, 2]
> > [2, 1]
> > [2, 2]
>
> > But if I introduce a temporary local variable, I get this instead:
> > [1, 1]
> > [1, 2]
> > [1, 1] # WRONG
> > [1, 2] # WRONG
>
> > The local variable seems to cause the continuations to jump only to
> > the point where i=1, not where i=0 where it should go. How does a
> > local variable effect continuations like that?
>
> > I'm using "ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]" built
> > for Ubuntu. Thanks for your help.
>
> > def interval
> > return callcc { |ret|
> > callcc { |k|
> > @next_cc.push(k)
> > ret.call(1)
> > }
> > ret.call(2)
> > }
> > end
>
> > def testcc
> > @next_cc = []
> > a = Array.new(2)
> > for i in 0...2
> > # This produces the WRONG output
> > # x = interval
> > # a[i] = x
>
> > # This produces the CORRECT output
> > a[i] = interval
> > end
>
> > puts a.inspect
>
> > while (not @next_cc.empty?) do
> > @next_cc.pop.call
> > end
> > end
>
> I haven't unraveled it entirely but I believe it's not about the local
> variable itself; it's about the fact that the interval method gets
> called before the assignment to a[i]. If you do this:
>
> a[i] = x = interval
>
> you'll get the result you want.
>
> David
>
> --
> Rails training from David A. Black and Ruby Power and Light:
> Intro to Ruby on Rails January 12-15 Fort Lauderdale, FL
> Advancing with Rails January 19-22 Fort Lauderdale, FL *
> * Co-taught with Patrick Ewing!
> Seehttp://www.ruby... details and updates!

"a[i] = x = interval" probably gets translated into "a[i] = interval"
anyway because x is not used. I want to do something with the value of
x before I assign it to the array. The sample code I posted is just a
simplified version of my code that still exhibits the bug.

Sean O'Halpin

9/10/2008 6:27:00 PM

On Tue, Sep 9, 2008 at 5:48 PM, Pinku Surana <suranap@gmail.com> wrote:
> I was trying to do some simple backtracking, but it kept failing for
> some reason. In the simplified version below, I use continuations to
> return either a 1 or 2 from interval. testcc assigns a value to the
> array, prints it out, then calls the next continuation on the stack
> (@next_cc) to jump back into interval and return the other number. The
> output should be:
> [1, 1]
> [1, 2]
> [2, 1]
> [2, 2]
>
> But if I introduce a temporary local variable, I get this instead:
> [1, 1]
> [1, 2]
> [1, 1] # WRONG
> [1, 2] # WRONG
>
> The local variable seems to cause the continuations to jump only to
> the point where i=1, not where i=0 where it should go. How does a
> local variable effect continuations like that?
>
> I'm using "ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]" built
> for Ubuntu. Thanks for your help.
>
>
>
> def interval
> return callcc { |ret|
> callcc { |k|
> @next_cc.push(k)
> ret.call(1)
> }
> ret.call(2)
> }
> end
>
> def testcc
> @next_cc = []
> a = Array.new(2)
> for i in 0...2
> # This produces the WRONG output
> # x = interval
> # a[i] = x
>
> # This produces the CORRECT output
> a[i] = interval
> end
>
> puts a.inspect
>
> while (not @next_cc.empty?) do
> @next_cc.pop.call
> end
> end
>
>

Like David, I haven't fully unravelled this myself, however it appears
to be a scoping issue. If you replace the

for i in 0..2

with

(0..2).each do |i|

you get the correct result in both cases.

Regards,
Sean

Jim Weirich

9/11/2008 5:24:00 AM

Sean O'halpin wrote:
> On Tue, Sep 9, 2008 at 5:48 PM, Pinku Surana <suranap@gmail.com> wrote:
>>
>> I'm using "ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]" built
>> ret.call(2)
>>
>>
>>
>
> Like David, I haven't fully unravelled this myself, however it appears
> to be a scoping issue. If you replace the
>
> for i in 0..2
>
> with
>
> (0..2).each do |i|
>
> you get the correct result in both cases.
>
> Regards,
> Sean

Ko1 once showed me a trick with continuations and local variables.
Local variables in the Ruby stack are not restored to their values when
the continuation is reentered. However, variables stored in the C-stack
(by the implementation) are restored (since the C-stack is copied and
restored when calling a continuation). (NOTE: I may have this
backwards, it is too late at night).

I suspect this may be the essential difference between for and each.

-- Jim Weirich
--
Posted via http://www.ruby-....

Pit Capitain

9/12/2008 10:01:00 AM

Hi Pinku, I like continuations, so I tried to understand your problem.
If you change the #testcc method a little bit, you can see what's
going on:

def testcc
@seq = 0
@next_cc = []
a = ["", ""]
for i in 0...2
# This produces the WRONG output
# x = interval
# a[i] << "/#{@seq += 1}:#{x}"

# This produces the CORRECT output
a[i] << ( x = interval
"/#{@seq += 1}:#{x}" )
end

I changed the array "a" to contain two strings and then append the
results of the method #interval plus a sequence number to those
strings. The version with the output you desire yields the following
output:

["/1:1", "/2:1"]
["/1:1", "/2:1/3:2"]
["/1:1/4:2", "/2:1/3:2/5:1"]
["/1:1/4:2", "/2:1/3:2/5:1/6:2"]

The other version yields

["/1:1", "/2:1"]
["/1:1", "/2:1/3:2"]
["/1:1", "/2:1/3:2/4:2/5:1"]
["/1:1", "/2:1/3:2/4:2/5:1/6:2"]

As you can see, in both cases the method #interval is called in the
same sequence with the same results:

1:1
2:1
3:2
4:2
5:1
6:2

The only difference is that the result of the fourth invocation (4:2)
is stored into different locations of the array "a". The outcome
depends on the time when the array index "i" is evaluated: in the
"correct" version the index is evaluated *before* calling the
#interval method and creating the continuations, in the "wrong"
version the index is evaluated *after* the call. It has nothing to do
with introducing a local variable, as you can see in the code above,
where the "correct" version also uses a local variable.

Regards,
Pit

Pinku Surana

9/12/2008 3:09:00 PM

On Sep 12, 6:00 am, Pit Capitain <pit.capit...@gmail.com> wrote:

> The only difference is that the result of the fourth invocation (4:2)
> is stored into different locations of the array "a". The outcome
> depends on the time when the array index "i" is evaluated: in the
> "correct" version the index is evaluated *before* calling the
> #interval method and creating the continuations, in the "wrong"
> version the index is evaluated *after* the call. It has nothing to do
> with introducing a local variable, as you can see in the code above,
> where the "correct" version also uses a local variable.

I modified your code to verify that the continuation is jumping back
to the correct place in the stack, but the value of i is not being
saved correctly. Somehow, your "correct" version causes the runtime to
preserve i on the stack. It also works if I convert the FOR loop to an
EACH method. But somehow the FOR loop doesn't save i correctly. I
suspect Jim's post is closer to the truth. I hope someone familiar
with the runtime can explain why local variables are sometimes not
stored correctly. Your "correct" code works, but FOR loops don't.

inside i==0, but i is really 0
inside i==1, but i is really 1
["/1:1", "/2:1"]
inside i==1, but i is really 1
["/1:1", "/2:1/3:2"]
inside i==0, but i is really 1 ### Here's where "i" did not get
restored correctly
inside i==1, but i is really 1
["/1:1", "/2:1/3:2/4:2/5:1"]
inside i==1, but i is really 1
["/1:1", "/2:1/3:2/4:2/5:1/6:2"]

Modified code:
for i in 0...2
# This produces the WRONG output
if (i==0)
x = interval
puts "inside i==0, but i is really #{i}"
else
x = interval
puts "inside i==1, but i is really #(i}"
end
a[i] << "/#{@seq += 1}:#{x}"

# This produces the CORRECT output
# a[i] << ( x = interval
# "/#{@seq += 1}:#{x}" )
end

Pit Capitain

9/13/2008 8:54:00 AM

2008/9/12 Pinku Surana <suranap@gmail.com>:
> I hope someone familiar
> with the runtime can explain why local variables are sometimes not
> stored correctly.

What I wanted to show with the modified example is that AFAIK local
(Ruby) variables aren't restored at all. Here's another simple
example:

i = 0
cc = callcc { |cc| cc }
puts "i is #{i}"
exit if i > 0
i = 1
cc.call

The output is:

i is 0
i is 1

Regards,
Pit

comp.lang.ruby

Local variable in loop affects callcc

Pinku Surana

David A. Black

Pinku Surana

Sean O'Halpin

Jim Weirich

Pit Capitain

Pinku Surana

Pit Capitain

x Login to ForumsZone