Local variable in loop affects callcc

[Pinku Surana]

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 = x

# This produces the CORRECT output
a = interval
end

puts a.inspect

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

 

[David A. Black]

Hi --

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 = x

# This produces the CORRECT output
a = 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. If you do this:

a = 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.rubypal.com for details and updates!

 

[Pinku Surana]

Hi --

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 = x

# This produces the CORRECT output
   a = 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. If you do this:

   a = 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.rubypal.comfor details and updates!

"a = x = interval" probably gets translated into "a = 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]

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 = x

# This produces the CORRECT output
a = 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]

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

 

[Pit Capitain]

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 << "/#{@seq += 1}:#{x}"

# This produces the CORRECT output
a << ( 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]

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 << "/#{@seq += 1}:#{x}"

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

 

[Pit Capitain]

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