|
require 'continuation'
|
|
|
|
# The idea of the code is to run '[0].map &f'
|
|
# with '&f' stopping the execution of 'map'
|
|
# (by aborting the computation (calling k0))
|
|
# and storing the continuation in 'x' (to
|
|
# resume it later). Calling 'x' with a value
|
|
# 'y' should resume the continuation with the
|
|
# value 'y' which will send it the the map
|
|
# ('[0].map { |x| y } and thus returning [y].
|
|
# This is the idea of making a Zipper.
|
|
|
|
|
|
def runtest
|
|
x = callcc { |k0| r0 = [0].map { |x| callcc { |k1| print "\nCaptured!\n"
|
|
k0.call k1
|
|
} }
|
|
@savecont.call r0
|
|
}
|
|
# x = k1
|
|
# = the continuation pointing to where
|
|
# callcc { |k1| .... } was called
|
|
|
|
|
|
puts "\n=> x"
|
|
print " x = ", x.to_s, "\n"
|
|
|
|
# We call 'x' two times with values 1 and 2
|
|
# The resulting values should be respectively
|
|
# [1] and [2]
|
|
|
|
|
|
print "\nBegin of x1\n============\n"
|
|
|
|
x1 = callcc { |k2| @savecont = k2
|
|
x.call 1
|
|
}
|
|
|
|
|
|
print "\n x1 = ", x1.to_s
|
|
puts ""
|
|
|
|
# x1 = { r = [0].map { |x| 1 }
|
|
# @savecont.call r
|
|
# }
|
|
# = k2 [1]
|
|
# = [1]
|
|
|
|
|
|
print "\n\nBegin of x2\n============\n"
|
|
|
|
# Now doing the same with '2' instead of '1'
|
|
# We should get [2]
|
|
|
|
x2 = callcc { |k2| @savecont = k2
|
|
x.call 2
|
|
}
|
|
|
|
print "\n x2 = ", x2.to_s, "\n"
|
|
print " x1 = ", x1.to_s, "\n"
|
|
end
|
|
|
|
|
|
|
|
# The code is run with 5 versions of map
|
|
# - The first one is the actual map implemented
|
|
# in ruby (see array.c in the sources)
|
|
# - The second one is a version having the same
|
|
# effects as the actual map
|
|
# - The thrid one is a sligly modified version of
|
|
# the third one computing the tail last
|
|
# - The fourth one is a version using only persisent
|
|
# arrays with tail computed first
|
|
# - The last one is another version using only persistent
|
|
# arrays but with tail computed last
|
|
|
|
|
|
|
|
|
|
print "\n\
|
|
################\n\
|
|
# THE RUBY MAP #\n\
|
|
################\n\n"
|
|
|
|
|
|
# The code of Array.map can be found in array.c
|
|
# (line 1895 of the current version) :
|
|
#
|
|
# /*
|
|
# * call-seq:
|
|
# * array.collect {|item| block } -> an_array
|
|
# * array.map {|item| block } -> an_array
|
|
# *
|
|
# * Invokes <i>block</i> once for each element of <i>self</i>. Creates a
|
|
# * new array containing the values returned by the block.
|
|
# * See also <code>Enumerable#collect</code>.
|
|
# *
|
|
# * a = [ "a", "b", "c", "d" ]
|
|
# * a.collect {|x| x + "!" } #=> ["a!", "b!", "c!", "d!"]
|
|
# * a #=> ["a", "b", "c", "d"]
|
|
# */
|
|
#
|
|
#
|
|
# static VALUE
|
|
# rb_ary_collect(VALUE ary)
|
|
# {
|
|
# long i;
|
|
# VALUE collect;
|
|
#
|
|
# RETURN_ENUMERATOR(ary, 0, 0);
|
|
# collect = rb_ary_new2(RARRAY_LEN(ary));
|
|
# for (i = 0; i < RARRAY_LEN(ary); i++) {
|
|
# rb_ary_push(collect, rb_yield(RARRAY_PTR(ary)[i]));
|
|
# }
|
|
# return collect;
|
|
# }
|
|
|
|
|
|
runtest
|
|
|
|
|
|
# When computing x1 :
|
|
# Indeed when '1' is sent to 'x', the 'map'
|
|
# receive the value '1' and finishes. All is
|
|
# as expected. 'x1' the array [1]
|
|
# 'x' is still the same procedure.
|
|
#
|
|
# When computing x2 :
|
|
# we get [1,2] instead of [2] and 'x1' changed.
|
|
|
|
|
|
|
|
|
|
print "\n\n\
|
|
###################################\n\
|
|
# NON PERSISTANT MAP : TAIL FIRST #\n\
|
|
###################################\n\n"
|
|
|
|
# This map has the same effect as the actual one
|
|
# when computing arr.map &f
|
|
# we compute q = arr[0..-2].map &f
|
|
# then t = f.call arr[-1]
|
|
# and then push t in q (q << t)
|
|
# this operation does changes q
|
|
|
|
class Array
|
|
def map &f
|
|
if self.empty?
|
|
[]
|
|
else
|
|
print "\nComputing q ... "
|
|
q = self[0..-2].map &f
|
|
print "q = ", q.to_s
|
|
|
|
print "\nCalling f ... "
|
|
t = f.call self[-1]
|
|
print "\nOut of f ... q = ", q.to_s
|
|
|
|
q << t
|
|
print "\nPush ... q = ", q.to_s
|
|
q
|
|
end
|
|
end
|
|
end
|
|
|
|
|
|
runtest
|
|
|
|
# When computing x1 :
|
|
# Indeed when '1' is sent to 'x', the 'map'
|
|
# receive the value '1' and finishes. All is
|
|
# as expected. 'x1' the array [1]
|
|
#
|
|
# When computing x2 :
|
|
# 'x2' should be [2] but is [1,2]
|
|
# Because we pushed t into q when computing x1,
|
|
# when we call x again, q is not empty any more
|
|
# but has its previous value ([1]). Then we push
|
|
# 2 into q, modifing it again.
|
|
# x1 being pointing to q, it is modified too.
|
|
|
|
|
|
print "\n\
|
|
###################################\n\
|
|
# NON PERSISTANT MAP : HEAD FIRST #\n\
|
|
###################################\n\n"
|
|
|
|
|
|
# This map have the correct behavior IN THIS EXAMPLE
|
|
# It is a sligly modified version of the previous one
|
|
# where instead of compyting q = arr[0..-2].map &f
|
|
# before t = f.call arr[-1]
|
|
# we start by computing t = f.call arr[-1]
|
|
# and then q = arr[0..-2].map &f
|
|
# then we push t in q (q << t)
|
|
# this operation does also change q
|
|
|
|
|
|
class Array
|
|
def map &f
|
|
if self.empty?
|
|
[]
|
|
else
|
|
print "\nCalling f ... "
|
|
t = f.call self[-1]
|
|
print "\nOut of f"
|
|
|
|
print "\nComputing q ... "
|
|
q = self[0..-2].map &f
|
|
print "q = ", q.to_s
|
|
|
|
q << t
|
|
print "\nPush ... q = ", q.to_s
|
|
q
|
|
end
|
|
end
|
|
end
|
|
|
|
|
|
runtest
|
|
|
|
# On the contrary to the previous map, here we
|
|
# stop the execution before computing q so
|
|
# when we call the continuation, we re-compute
|
|
# q every time. Thus there is no interference between
|
|
# the two calls.
|
|
|
|
|
|
|
|
print "\n\
|
|
###############################\n\
|
|
# PERSISTANT MAP : TAIL FIRST #\n\
|
|
###############################\n\n"
|
|
|
|
|
|
# This map should always be correct. It does not use
|
|
# imperative features. Instead of pushing t into q
|
|
# (by q << x), we make a new array (q + [t]) so that
|
|
# q will never be modified.
|
|
|
|
|
|
class Array
|
|
def map &f
|
|
if self.empty?
|
|
[]
|
|
else
|
|
print "\nComputing q ... "
|
|
q = self[0..-2].map &f
|
|
print "q = ", q.to_s
|
|
|
|
print "\nCalling f ... "
|
|
t = f.call self[-1]
|
|
print "\nOut of f ... q = ", q.to_s
|
|
|
|
r = q + [t]
|
|
print "\nAppending ... q = ", q.to_s, ", r = ", r.to_s
|
|
r
|
|
end
|
|
end
|
|
end
|
|
|
|
runtest
|
|
|
|
# This map does not modify q so there is no
|
|
# interferences between the instances of the
|
|
# computation
|
|
|
|
|
|
print "\n\
|
|
###############################\n\
|
|
# PERSISTANT MAP : HEAD FIRST #\n\
|
|
###############################\n\n"
|
|
|
|
|
|
# This map should always be correct. It does not use
|
|
# imperative features. Instead of pushing t into q
|
|
# (by q << x), we make a new array (q + [t]) so that
|
|
# q will never be modified.
|
|
|
|
|
|
class Array
|
|
def map &f
|
|
if self.empty?
|
|
[]
|
|
else
|
|
print "\nCalling f ... "
|
|
t = f.call self[-1]
|
|
print "\nOut of f"
|
|
|
|
print "\nComputing q ... "
|
|
q = self[0..-2].map &f
|
|
print "q = ", q.to_s
|
|
|
|
r = q + [t]
|
|
print "\nAppending ... q = ", q.to_s, ", r = ", r.to_s
|
|
r
|
|
end
|
|
end
|
|
end
|
|
|
|
runtest
|
|
|
|
# This map does not modify q so there is no
|
|
# interferences between the instances of the
|
|
# computation.
|
|
|
|
puts ""
|