[scala] Simulating python yield with scala continuations

[Arnold deVos-3]

I'm interested in the upcoming continuations support so I thought I would try
to build something similar to the python generators with it.  Here is a scrap
of python:

def generate():
    yield "first"
    for i in range(1,4):
        yield str(i)
    yield "last"

In python this function returns an iterator over the values passed to the
yield statements. The nice thing is: it is lazy and can be used as a
coroutine.  Anyway, if we iterate like this:

for r in generate():
    print r

It prints this:

first
1
2
3
last

Here is a scala version in which a produce() method serves the same role as
python's yield:

object Generator {
    def generate = {
        val g = new Generator[String]
        reset {
            g produce "first"
            g produce 1.toString
            g produce 2.toString
            g produce 3.toString
            g produce "last"
        }
        g
    }

    def main(args: Array[String]) {
        for( a <- generate ) println(a)
    }
}

This also prints

first
1
2
3
last

The Generator class is defined in terms of shift() as follows:

class Generator[A] extends Iterator[A] {
    private var a: A = _                
    private var k: (Unit => Unit) = null
                                       
    def next = {                        
        val a0 = a                      
        val k0 = k                      
        k = null                        
        k0()                            
        a0                              
    }                                  
                                       
    def hasNext = k != null            
                                       
    def produce(a0: A): Unit @ suspendable = {
        a = a0                                
        shift { k0: (Unit => Unit) => k = k0 }
    }
}

But the example is not quite the same as the python because that had a loop in
the generate function.  Lets try that in the scala version, replacing the
generate method with:

    def generate = {
        val g = new Generator[String]
        reset {
            g produce "first"
            for( i <- 1 to 4) { g produce i.toString }
            g produce "last"
        }
        g
    }

But this does not compile:

generator.scala:28: error: type mismatch;
 found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
 required: (Int) => Unit
            for( i <- 1 to 4) { g produce i.toString }
                 ^
one error found

Substituting a while loop produces a different compile error. Do any
continuation experts/experimenters out there know what the problem is?  

The example was compiled with scala r17271 plus the latest continuations
plugin from trunk as of r18035 for reasons explained in the previous post.  
This may be the problem, I don't know.

- Arnold

[Jorge Ortiz-3]

Scala has lazy collections, which, AFAIK, can do whatever generators can without needing the continuations plugin.

  val generate =
    (
      Array("first").projection append
      (1 to 4).map(_.toString) append
      Array("last").projection
    ).elements

  for (r <- generate) println(r)

The code is, admittedly, a little ugly, but could be made a little cleaner with 2.8 collections.

(Note this won't work in the interpreter, as the interpreter calls toString on "generate", which forces its evaluation. If you suppress the call to toString, it works as specified.)

--j

On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <adv-list-scala@...> wrote:

I'm interested in the upcoming continuations support so I thought I would try
to build something similar to the python generators with it.  Here is a scrap
of python:

def generate():
   yield "first"
   for i in range(1,4):
       yield str(i)
   yield "last"

In python this function returns an iterator over the values passed to the
yield statements. The nice thing is: it is lazy and can be used as a
coroutine.  Anyway, if we iterate like this:

for r in generate():
   print r

It prints this:

first
1
2
3
last

Here is a scala version in which a produce() method serves the same role as
python's yield:

object Generator {
   def generate = {
       val g = new Generator[String]
       reset {
           g produce "first"
           g produce 1.toString
           g produce 2.toString
           g produce 3.toString
           g produce "last"
       }
       g
   }

   def main(args: Array[String]) {
       for( a <- generate ) println(a)
   }
}

This also prints

first
1
2
3
last

The Generator class is defined in terms of shift() as follows:

class Generator[A] extends Iterator[A] {
   private var a: A = _
   private var k: (Unit => Unit) = null

   def next = {
       val a0 = a
       val k0 = k
       k = null
       k0()
       a0
   }

   def hasNext = k != null

   def produce(a0: A): Unit @ suspendable = {
       a = a0
       shift { k0: (Unit => Unit) => k = k0 }
   }
}

But the example is not quite the same as the python because that had a loop in
the generate function.  Lets try that in the scala version, replacing the
generate method with:

   def generate = {
       val g = new Generator[String]
       reset {
           g produce "first"
           for( i <- 1 to 4) { g produce i.toString }
           g produce "last"
       }
       g
   }

But this does not compile:

generator.scala:28: error: type mismatch;
 found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
 required: (Int) => Unit
           for( i <- 1 to 4) { g produce i.toString }
                ^
one error found

Substituting a while loop produces a different compile error. Do any
continuation experts/experimenters out there know what the problem is?

The example was compiled with scala r17271 plus the latest continuations
plugin from trunk as of r18035 for reasons explained in the previous post.
This may be the problem, I don't know.

- Arnold

[Arnold deVos-3]

Well yes, you can always string together pieces with append, andThen and so on
but continuations are all about coding this sort of thing in direct-style.  
The benefit is not so clear with a simple example like mine.

But the point of the post is not to motivate continuations.  I am wanting
exchange knowledge with others that already do want to continuations and tease
out bugs in the implementation.

-- Arnold


On Thu, 18 Jun 2009 01:33:57 pm Jorge Ortiz wrote:

> Scala has lazy collections, which, AFAIK, can do whatever generators can
> without needing the continuations plugin.
>
>   val generate =
>     (
>       Array("first").projection append
>       (1 to 4).map(_.toString) append
>       Array("last").projection
>     ).elements
>
>   for (r <- generate) println(r)
>
> The code is, admittedly, a little ugly, but could be made a little cleaner
> with 2.8 collections.
>
> (Note this won't work in the interpreter, as the interpreter calls toString
> on "generate", which forces its evaluation. If you suppress the call to
> toString, it works as specified.)
>
> --j
>
> On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <
>
> adv-list-scala@...> wrote:
> > I'm interested in the upcoming continuations support so I thought I would
> > try
> > to build something similar to the python generators with it.  Here is a
> > scrap
> > of python:
> >
> > def generate():
> >    yield "first"
> >    for i in range(1,4):
> >        yield str(i)
> >    yield "last"
> >
> > In python this function returns an iterator over the values passed to the
> > yield statements. The nice thing is: it is lazy and can be used as a
> > coroutine.  Anyway, if we iterate like this:
> >
> > for r in generate():
> >    print r
> >
> > It prints this:
> >
> > first
> > 1
> > 2
> > 3
> > last
> >
> > Here is a scala version in which a produce() method serves the same role
> > as python's yield:
> >
> > object Generator {
> >    def generate = {
> >        val g = new Generator[String]
> >        reset {
> >            g produce "first"
> >            g produce 1.toString
> >            g produce 2.toString
> >            g produce 3.toString
> >            g produce "last"
> >        }
> >        g
> >    }
> >
> >    def main(args: Array[String]) {
> >        for( a <- generate ) println(a)
> >    }
> > }
> >
> > This also prints
> >
> > first
> > 1
> > 2
> > 3
> > last
> >
> > The Generator class is defined in terms of shift() as follows:
> >
> > class Generator[A] extends Iterator[A] {
> >    private var a: A = _
> >    private var k: (Unit => Unit) = null
> >
> >    def next = {
> >        val a0 = a
> >        val k0 = k
> >        k = null
> >        k0()
> >        a0
> >    }
> >
> >    def hasNext = k != null
> >
> >    def produce(a0: A): Unit @ suspendable = {
> >        a = a0
> >        shift { k0: (Unit => Unit) => k = k0 }
> >    }
> > }
> >
> > But the example is not quite the same as the python because that had a
> > loop in
> > the generate function.  Lets try that in the scala version, replacing the
> > generate method with:
> >
> >    def generate = {
> >        val g = new Generator[String]
> >        reset {
> >            g produce "first"
> >            for( i <- 1 to 4) { g produce i.toString }
> >            g produce "last"
> >        }
> >        g
> >    }
> >
> > But this does not compile:
> >
> > generator.scala:28: error: type mismatch;
> >  found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
> >  required: (Int) => Unit
> >            for( i <- 1 to 4) { g produce i.toString }
> >                 ^
> > one error found
> >
> > Substituting a while loop produces a different compile error. Do any
> > continuation experts/experimenters out there know what the problem is?
> >
> > The example was compiled with scala r17271 plus the latest continuations
> > plugin from trunk as of r18035 for reasons explained in the previous
> > post. This may be the problem, I don't know.
> >
> > - Arnold

[Christos KK Loverdos]

As a side note, I think the point with Python's generators is best  
given with tree traversal:

def inorder(t):
   if t:
     for x in inorder(t.left):
       yield x
     yield t.label
     for x in inorder(t.right):
       yield x

No explicit state management, no result building up. As soon as I have  
a value, I yield it.

On Jun 18, 2009, at 6:56 AM, Arnold deVos wrote:

> Well yes, you can always string together pieces with append, andThen  
> and so on
> but continuations are all about coding this sort of thing in direct-
> style.
> The benefit is not so clear with a simple example like mine.
>
> But the point of the post is not to motivate continuations.  I am  
> wanting
> exchange knowledge with others that already do want to continuations  
> and tease
> out bugs in the implementation.
>
> -- Arnold
>
>
> On Thu, 18 Jun 2009 01:33:57 pm Jorge Ortiz wrote:
>> Scala has lazy collections, which, AFAIK, can do whatever  
>> generators can
>> without needing the continuations plugin.
>>
>>  val generate =
>>    (
>>      Array("first").projection append
>>      (1 to 4).map(_.toString) append
>>      Array("last").projection
>>    ).elements
>>
>>  for (r <- generate) println(r)
>>
>> The code is, admittedly, a little ugly, but could be made a little  
>> cleaner
>> with 2.8 collections.
>>
>> (Note this won't work in the interpreter, as the interpreter calls  
>> toString
>> on "generate", which forces its evaluation. If you suppress the  
>> call to
>> toString, it works as specified.)
>>
>> --j
>>
>> On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <
>>
>> adv-list-scala@...> wrote:
>>> I'm interested in the upcoming continuations support so I thought  
>>> I would
>>> try
>>> to build something similar to the python generators with it.  Here  
>>> is a
>>> scrap
>>> of python:
>>>
>>> def generate():
>>>   yield "first"
>>>   for i in range(1,4):
>>>       yield str(i)
>>>   yield "last"
>>>
>>> In python this function returns an iterator over the values passed  
>>> to the
>>> yield statements. The nice thing is: it is lazy and can be used as a
>>> coroutine.  Anyway, if we iterate like this:
>>>
>>> for r in generate():
>>>   print r
>>>
>>> It prints this:
>>>
>>> first
>>> 1
>>> 2
>>> 3
>>> last
>>>
>>> Here is a scala version in which a produce() method serves the  
>>> same role
>>> as python's yield:
>>>
>>> object Generator {
>>>   def generate = {
>>>       val g = new Generator[String]
>>>       reset {
>>>           g produce "first"
>>>           g produce 1.toString
>>>           g produce 2.toString
>>>           g produce 3.toString
>>>           g produce "last"
>>>       }
>>>       g
>>>   }
>>>
>>>   def main(args: Array[String]) {
>>>       for( a <- generate ) println(a)
>>>   }
>>> }
>>>
>>> This also prints
>>>
>>> first
>>> 1
>>> 2
>>> 3
>>> last
>>>
>>> The Generator class is defined in terms of shift() as follows:
>>>
>>> class Generator[A] extends Iterator[A] {
>>>   private var a: A = _
>>>   private var k: (Unit => Unit) = null
>>>
>>>   def next = {
>>>       val a0 = a
>>>       val k0 = k
>>>       k = null
>>>       k0()
>>>       a0
>>>   }
>>>
>>>   def hasNext = k != null
>>>
>>>   def produce(a0: A): Unit @ suspendable = {
>>>       a = a0
>>>       shift { k0: (Unit => Unit) => k = k0 }
>>>   }
>>> }
>>>
>>> But the example is not quite the same as the python because that  
>>> had a
>>> loop in
>>> the generate function.  Lets try that in the scala version,  
>>> replacing the
>>> generate method with:
>>>
>>>   def generate = {
>>>       val g = new Generator[String]
>>>       reset {
>>>           g produce "first"
>>>           for( i <- 1 to 4) { g produce i.toString }
>>>           g produce "last"
>>>       }
>>>       g
>>>   }
>>>
>>> But this does not compile:
>>>
>>> generator.scala:28: error: type mismatch;
>>> found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
>>> required: (Int) => Unit
>>>           for( i <- 1 to 4) { g produce i.toString }
>>>                ^
>>> one error found
>>>
>>> Substituting a while loop produces a different compile error. Do any
>>> continuation experts/experimenters out there know what the problem  
>>> is?
>>>
>>> The example was compiled with scala r17271 plus the latest  
>>> continuations
>>> plugin from trunk as of r18035 for reasons explained in the previous
>>> post. This may be the problem, I don't know.
>>>
>>> - Arnold
>
>

--
  __~O
-\ <,       Christos KK Loverdos
(*)/ (*)      http://ckkloverdos.com

[Ricky Clarkson]

Bah.  I'd played with C#'s yield and not worked out how to make it
recurse, which you've just showed..

public static IEnumerable<int> Ones() { yield return 1; foreach (var v
in Ones()) yield return v; }

This one's probably most useful as a compiler test case though. :)
The more usual way of writing Ones() would be while (true) yield
return 1;

2009/6/18 Christos KK Loverdos <loverdos@...>:

> As a side note, I think the point with Python's generators is best given
> with tree traversal:
>
> def inorder(t):
>  if t:
>    for x in inorder(t.left):
>      yield x
>    yield t.label
>    for x in inorder(t.right):
>      yield x
>
> No explicit state management, no result building up. As soon as I have a
> value, I yield it.
>
> On Jun 18, 2009, at 6:56 AM, Arnold deVos wrote:
>
>> Well yes, you can always string together pieces with append, andThen and
>> so on
>> but continuations are all about coding this sort of thing in direct-style.
>> The benefit is not so clear with a simple example like mine.
>>
>> But the point of the post is not to motivate continuations.  I am wanting
>> exchange knowledge with others that already do want to continuations and
>> tease
>> out bugs in the implementation.
>>
>> -- Arnold
>>
>> On Thu, 18 Jun 2009 01:33:57 pm Jorge Ortiz wrote:
>>>
>>> Scala has lazy collections, which, AFAIK, can do whatever generators can
>>> without needing the continuations plugin.
>>>
>>>  val generate =
>>>   (
>>>     Array("first").projection append
>>>     (1 to 4).map(_.toString) append
>>>     Array("last").projection
>>>   ).elements
>>>
>>>  for (r <- generate) println(r)
>>>
>>> The code is, admittedly, a little ugly, but could be made a little
>>> cleaner
>>> with 2.8 collections.
>>>
>>> (Note this won't work in the interpreter, as the interpreter calls
>>> toString
>>> on "generate", which forces its evaluation. If you suppress the call to
>>> toString, it works as specified.)
>>>
>>> --j
>>>
>>> On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <
>>>
>>> adv-list-scala@...> wrote:
>>>>
>>>> I'm interested in the upcoming continuations support so I thought I
>>>> would
>>>> try
>>>> to build something similar to the python generators with it.  Here is a
>>>> scrap
>>>> of python:
>>>>
>>>> def generate():
>>>>  yield "first"
>>>>  for i in range(1,4):
>>>>      yield str(i)
>>>>  yield "last"
>>>>
>>>> In python this function returns an iterator over the values passed to
>>>> the
>>>> yield statements. The nice thing is: it is lazy and can be used as a
>>>> coroutine.  Anyway, if we iterate like this:
>>>>
>>>> for r in generate():
>>>>  print r
>>>>
>>>> It prints this:
>>>>
>>>> first
>>>> 1
>>>> 2
>>>> 3
>>>> last
>>>>
>>>> Here is a scala version in which a produce() method serves the same role
>>>> as python's yield:
>>>>
>>>> object Generator {
>>>>  def generate = {
>>>>      val g = new Generator[String]
>>>>      reset {
>>>>          g produce "first"
>>>>          g produce 1.toString
>>>>          g produce 2.toString
>>>>          g produce 3.toString
>>>>          g produce "last"
>>>>      }
>>>>      g
>>>>  }
>>>>
>>>>  def main(args: Array[String]) {
>>>>      for( a <- generate ) println(a)
>>>>  }
>>>> }
>>>>
>>>> This also prints
>>>>
>>>> first
>>>> 1
>>>> 2
>>>> 3
>>>> last
>>>>
>>>> The Generator class is defined in terms of shift() as follows:
>>>>
>>>> class Generator[A] extends Iterator[A] {
>>>>  private var a: A = _
>>>>  private var k: (Unit => Unit) = null
>>>>
>>>>  def next = {
>>>>      val a0 = a
>>>>      val k0 = k
>>>>      k = null
>>>>      k0()
>>>>      a0
>>>>  }
>>>>
>>>>  def hasNext = k != null
>>>>
>>>>  def produce(a0: A): Unit @ suspendable = {
>>>>      a = a0
>>>>      shift { k0: (Unit => Unit) => k = k0 }
>>>>  }
>>>> }
>>>>
>>>> But the example is not quite the same as the python because that had a
>>>> loop in
>>>> the generate function.  Lets try that in the scala version, replacing
>>>> the
>>>> generate method with:
>>>>
>>>>  def generate = {
>>>>      val g = new Generator[String]
>>>>      reset {
>>>>          g produce "first"
>>>>          for( i <- 1 to 4) { g produce i.toString }
>>>>          g produce "last"
>>>>      }
>>>>      g
>>>>  }
>>>>
>>>> But this does not compile:
>>>>
>>>> generator.scala:28: error: type mismatch;
>>>> found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
>>>> required: (Int) => Unit
>>>>          for( i <- 1 to 4) { g produce i.toString }
>>>>               ^
>>>> one error found
>>>>
>>>> Substituting a while loop produces a different compile error. Do any
>>>> continuation experts/experimenters out there know what the problem is?
>>>>
>>>> The example was compiled with scala r17271 plus the latest continuations
>>>> plugin from trunk as of r18035 for reasons explained in the previous
>>>> post. This may be the problem, I don't know.
>>>>
>>>> - Arnold
>>
>>
>
> --
>  __~O
> -\ <,       Christos KK Loverdos
> (*)/ (*)      http://ckkloverdos.com
>
>
>
>
>
>

--
Ricky Clarkson
Java Programmer, AD Holdings
[phone]
Skype: ricky_clarkson
Google Talk: ricky.clarkson@...

[Christos KK Loverdos]

As a side note 2, I just looked up 'Bah' in the dictionary, and it is  
close in meaning to the greek 'Μπα', whose sound can be exactly the  
same :)

On Jun 18, 2009, at 10:20 PM, Ricky Clarkson wrote:

> Bah.  I'd played with C#'s yield and not worked out how to make it
> recurse, which you've just showed..
>
> public static IEnumerable<int> Ones() { yield return 1; foreach (var v
> in Ones()) yield return v; }
>
> This one's probably most useful as a compiler test case though. :)
> The more usual way of writing Ones() would be while (true) yield
> return 1;
>
> 2009/6/18 Christos KK Loverdos <loverdos@...>:
>> As a side note, I think the point with Python's generators is best  
>> given
>> with tree traversal:
>>
>> def inorder(t):
>>  if t:
>>    for x in inorder(t.left):
>>      yield x
>>    yield t.label
>>    for x in inorder(t.right):
>>      yield x
>>
>> No explicit state management, no result building up. As soon as I  
>> have a
>> value, I yield it.
>>
>> On Jun 18, 2009, at 6:56 AM, Arnold deVos wrote:
>>
>>> Well yes, you can always string together pieces with append,  
>>> andThen and
>>> so on
>>> but continuations are all about coding this sort of thing in  
>>> direct-style.
>>> The benefit is not so clear with a simple example like mine.
>>>
>>> But the point of the post is not to motivate continuations.  I am  
>>> wanting
>>> exchange knowledge with others that already do want to  
>>> continuations and
>>> tease
>>> out bugs in the implementation.
>>>
>>> -- Arnold
>>>
>>> On Thu, 18 Jun 2009 01:33:57 pm Jorge Ortiz wrote:
>>>>
>>>> Scala has lazy collections, which, AFAIK, can do whatever  
>>>> generators can
>>>> without needing the continuations plugin.
>>>>
>>>>  val generate =
>>>>   (
>>>>     Array("first").projection append
>>>>     (1 to 4).map(_.toString) append
>>>>     Array("last").projection
>>>>   ).elements
>>>>
>>>>  for (r <- generate) println(r)
>>>>
>>>> The code is, admittedly, a little ugly, but could be made a little
>>>> cleaner
>>>> with 2.8 collections.
>>>>
>>>> (Note this won't work in the interpreter, as the interpreter calls
>>>> toString
>>>> on "generate", which forces its evaluation. If you suppress the  
>>>> call to
>>>> toString, it works as specified.)
>>>>
>>>> --j
>>>>
>>>> On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <
>>>>
>>>> adv-list-scala@...> wrote:
>>>>>
>>>>> I'm interested in the upcoming continuations support so I  
>>>>> thought I
>>>>> would
>>>>> try
>>>>> to build something similar to the python generators with it.  
>>>>> Here is a
>>>>> scrap
>>>>> of python:
>>>>>
>>>>> def generate():
>>>>>  yield "first"
>>>>>  for i in range(1,4):
>>>>>      yield str(i)
>>>>>  yield "last"
>>>>>
>>>>> In python this function returns an iterator over the values  
>>>>> passed to
>>>>> the
>>>>> yield statements. The nice thing is: it is lazy and can be used  
>>>>> as a
>>>>> coroutine.  Anyway, if we iterate like this:
>>>>>
>>>>> for r in generate():
>>>>>  print r
>>>>>
>>>>> It prints this:
>>>>>
>>>>> first
>>>>> 1
>>>>> 2
>>>>> 3
>>>>> last
>>>>>
>>>>> Here is a scala version in which a produce() method serves the  
>>>>> same role
>>>>> as python's yield:
>>>>>
>>>>> object Generator {
>>>>>  def generate = {
>>>>>      val g = new Generator[String]
>>>>>      reset {
>>>>>          g produce "first"
>>>>>          g produce 1.toString
>>>>>          g produce 2.toString
>>>>>          g produce 3.toString
>>>>>          g produce "last"
>>>>>      }
>>>>>      g
>>>>>  }
>>>>>
>>>>>  def main(args: Array[String]) {
>>>>>      for( a <- generate ) println(a)
>>>>>  }
>>>>> }
>>>>>
>>>>> This also prints
>>>>>
>>>>> first
>>>>> 1
>>>>> 2
>>>>> 3
>>>>> last
>>>>>
>>>>> The Generator class is defined in terms of shift() as follows:
>>>>>
>>>>> class Generator[A] extends Iterator[A] {
>>>>>  private var a: A = _
>>>>>  private var k: (Unit => Unit) = null
>>>>>
>>>>>  def next = {
>>>>>      val a0 = a
>>>>>      val k0 = k
>>>>>      k = null
>>>>>      k0()
>>>>>      a0
>>>>>  }
>>>>>
>>>>>  def hasNext = k != null
>>>>>
>>>>>  def produce(a0: A): Unit @ suspendable = {
>>>>>      a = a0
>>>>>      shift { k0: (Unit => Unit) => k = k0 }
>>>>>  }
>>>>> }
>>>>>
>>>>> But the example is not quite the same as the python because that  
>>>>> had a
>>>>> loop in
>>>>> the generate function.  Lets try that in the scala version,  
>>>>> replacing
>>>>> the
>>>>> generate method with:
>>>>>
>>>>>  def generate = {
>>>>>      val g = new Generator[String]
>>>>>      reset {
>>>>>          g produce "first"
>>>>>          for( i <- 1 to 4) { g produce i.toString }
>>>>>          g produce "last"
>>>>>      }
>>>>>      g
>>>>>  }
>>>>>
>>>>> But this does not compile:
>>>>>
>>>>> generator.scala:28: error: type mismatch;
>>>>> found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
>>>>> required: (Int) => Unit
>>>>>          for( i <- 1 to 4) { g produce i.toString }
>>>>>               ^
>>>>> one error found
>>>>>
>>>>> Substituting a while loop produces a different compile error. Do  
>>>>> any
>>>>> continuation experts/experimenters out there know what the  
>>>>> problem is?
>>>>>
>>>>> The example was compiled with scala r17271 plus the latest  
>>>>> continuations
>>>>> plugin from trunk as of r18035 for reasons explained in the  
>>>>> previous
>>>>> post. This may be the problem, I don't know.
>>>>>
>>>>> - Arnold
>>>
>>>
>>
>> --
>>  __~O
>> -\ <,       Christos KK Loverdos
>> (*)/ (*)      http://ckkloverdos.com
>>
>>
>>
>>
>>
>>
>
>
>
> --
> Ricky Clarkson
> Java Programmer, AD Holdings
> [phone]
> Skype: ricky_clarkson
> Google Talk: ricky.clarkson@...

--
  __~O
-\ <,       Christos KK Loverdos
(*)/ (*)      http://ckkloverdos.com

[Arnold deVos-3]

Some parts of this message have been removed. Learn more about Nabble's security policy.

I think the yield statement (at least in python) represents some sort of sweet spot. Granted it is not completely general but it is pretty easy to use in common cases. Pretty typical of the way they do things in the python world.

So it is a good candidate, among others, for a handy scala library function built on shift and reset.

Actually, a scala version might be even easier to use than the python version because, for example, it should be possible to yield directly from a called function. That is a trap when you are innocently refactoring a python generator.

Unfortunately I have not got my attempted implementation to work yet (see bottom of original post). Not sure if I've hit a limitation, bug or what.

- Arnold

On Fri, 19 Jun 2009 05:20:23 Ricky Clarkson wrote:
> Bah. I'd played with C#'s yield and not worked out how to make it
> recurse, which you've just showed..
>
> public static IEnumerable<int> Ones() { yield return 1; foreach (var v
> in Ones()) yield return v; }
>
> This one's probably most useful as a compiler test case though. :)
> The more usual way of writing Ones() would be while (true) yield
> return 1;
>
> 2009/6/18 Christos KK Loverdos <loverdos@...>:
> > As a side note, I think the point with Python's generators is best given
> > with tree traversal:
> >
> > def inorder(t):
> >  if t:
> >    for x in inorder(t.left):
> >      yield x
> >    yield t.label
> >    for x in inorder(t.right):
> >      yield x
> >
> > No explicit state management, no result building up. As soon as I have a
> > value, I yield it.
> >
> > On Jun 18, 2009, at 6:56 AM, Arnold deVos wrote:
> >> Well yes, you can always string together pieces with append, andThen and
> >> so on
> >> but continuations are all about coding this sort of thing in
> >> direct-style. The benefit is not so clear with a simple example like
> >> mine.
> >>
> >> But the point of the post is not to motivate continuations.  I am
> >> wanting exchange knowledge with others that already do want to
> >> continuations and tease
> >> out bugs in the implementation.
> >>
> >> -- Arnold
> >>
> >> On Thu, 18 Jun 2009 01:33:57 pm Jorge Ortiz wrote:
> >>> Scala has lazy collections, which, AFAIK, can do whatever generators
> >>> can without needing the continuations plugin.
> >>>
> >>>  val generate =
> >>>   (
> >>>     Array("first").projection append
> >>>     (1 to 4).map(_.toString) append
> >>>     Array("last").projection
> >>>   ).elements
> >>>
> >>>  for (r <- generate) println(r)
> >>>
> >>> The code is, admittedly, a little ugly, but could be made a little
> >>> cleaner
> >>> with 2.8 collections.
> >>>
> >>> (Note this won't work in the interpreter, as the interpreter calls
> >>> toString
> >>> on "generate", which forces its evaluation. If you suppress the call to
> >>> toString, it works as specified.)
> >>>
> >>> --j
> >>>
> >>> On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <
> >>>
> >>> adv-list-scala@...> wrote:
> >>>> I'm interested in the upcoming continuations support so I thought I
> >>>> would
> >>>> try
> >>>> to build something similar to the python generators with it.  Here is
> >>>> a scrap
> >>>> of python:
> >>>>
> >>>> def generate():
> >>>>  yield "first"
> >>>>  for i in range(1,4):
> >>>>      yield str(i)
> >>>>  yield "last"
> >>>>
> >>>> In python this function returns an iterator over the values passed to
> >>>> the
> >>>> yield statements. The nice thing is: it is lazy and can be used as a
> >>>> coroutine.  Anyway, if we iterate like this:
> >>>>
> >>>> for r in generate():
> >>>>  print r
> >>>>
> >>>> It prints this:
> >>>>
> >>>> first
> >>>> 1
> >>>> 2
> >>>> 3
> >>>> last
> >>>>
> >>>> Here is a scala version in which a produce() method serves the same
> >>>> role as python's yield:
> >>>>
> >>>> object Generator {
> >>>>  def generate = {
> >>>>      val g = new Generator[String]
> >>>>      reset {
> >>>>          g produce "first"
> >>>>          g produce 1.toString
> >>>>          g produce 2.toString
> >>>>          g produce 3.toString
> >>>>          g produce "last"
> >>>>      }
> >>>>      g
> >>>>  }
> >>>>
> >>>>  def main(args: Array[String]) {
> >>>>      for( a <- generate ) println(a)
> >>>>  }
> >>>> }
> >>>>
> >>>> This also prints
> >>>>
> >>>> first
> >>>> 1
> >>>> 2
> >>>> 3
> >>>> last
> >>>>
> >>>> The Generator class is defined in terms of shift() as follows:
> >>>>
> >>>> class Generator[A] extends Iterator[A] {
> >>>>  private var a: A = _
> >>>>  private var k: (Unit => Unit) = null
> >>>>
> >>>>  def next = {
> >>>>      val a0 = a
> >>>>      val k0 = k
> >>>>      k = null
> >>>>      k0()
> >>>>      a0
> >>>>  }
> >>>>
> >>>>  def hasNext = k != null
> >>>>
> >>>>  def produce(a0: A): Unit @ suspendable = {
> >>>>      a = a0
> >>>>      shift { k0: (Unit => Unit) => k = k0 }
> >>>>  }
> >>>> }
> >>>>
> >>>> But the example is not quite the same as the python because that had a
> >>>> loop in
> >>>> the generate function.  Lets try that in the scala version, replacing
> >>>> the
> >>>> generate method with:
> >>>>
> >>>>  def generate = {
> >>>>      val g = new Generator[String]
> >>>>      reset {
> >>>>          g produce "first"
> >>>>          for( i <- 1 to 4) { g produce i.toString }
> >>>>          g produce "last"
> >>>>      }
> >>>>      g
> >>>>  }
> >>>>
> >>>> But this does not compile:
> >>>>
> >>>> generator.scala:28: error: type mismatch;
> >>>> found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
> >>>> required: (Int) => Unit
> >>>>          for( i <- 1 to 4) { g produce i.toString }
> >>>>               ^
> >>>> one error found
> >>>>
> >>>> Substituting a while loop produces a different compile error. Do any
> >>>> continuation experts/experimenters out there know what the problem is?
> >>>>
> >>>> The example was compiled with scala r17271 plus the latest
> >>>> continuations plugin from trunk as of r18035 for reasons explained in
> >>>> the previous post. This may be the problem, I don't know.
> >>>>
> >>>> - Arnold
> >
> > --
> >  __~O
> > -\ <,       Christos KK Loverdos
> > (*)/ (*)      http://ckkloverdos.com

--
Arnold deVos
Langdale Consultants

[Jorge Ortiz-3]

Again, probably not as pretty, but it can be done with lazy collections:

  case class Tree(left: Option[Tree], label: String, right: Option[Tree])

  def inorder(t: Tree): Iterator[String] = {
    t.left.elements.flatMap(inorder) append
    Iterator.single(t.label) append        
    t.right.elements.flatMap(inorder)      
  }

  val t = Tree(Some(Tree(None, "left", None)), "center", Some(Tree(None, "right",  None)))

  for (x <- inorder(t)) println(x)

--j

On Thu, Jun 18, 2009 at 12:48 AM, Christos KK Loverdos <loverdos@...> wrote:

As a side note, I think the point with Python's generators is best given with tree traversal:

def inorder(t):
 if t:
   for x in inorder(t.left):
     yield x
   yield t.label
   for x in inorder(t.right):
     yield x

No explicit state management, no result building up. As soon as I have a value, I yield it.

On Jun 18, 2009, at 6:56 AM, Arnold deVos wrote:

Well yes, you can always string together pieces with append, andThen and so on
but continuations are all about coding this sort of thing in direct-style.
The benefit is not so clear with a simple example like mine.

But the point of the post is not to motivate continuations.  I am wanting
exchange knowledge with others that already do want to continuations and tease
out bugs in the implementation.

-- Arnold

On Thu, 18 Jun 2009 01:33:57 pm Jorge Ortiz wrote:

Scala has lazy collections, which, AFAIK, can do whatever generators can
without needing the continuations plugin.

 val generate =
  (
    Array("first").projection append
    (1 to 4).map(_.toString) append
    Array("last").projection
  ).elements

 for (r <- generate) println(r)

The code is, admittedly, a little ugly, but could be made a little cleaner
with 2.8 collections.

(Note this won't work in the interpreter, as the interpreter calls toString
on "generate", which forces its evaluation. If you suppress the call to
toString, it works as specified.)

--j

On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <

adv-list-scala@...> wrote:

I'm interested in the upcoming continuations support so I thought I would
try
to build something similar to the python generators with it.  Here is a
scrap
of python:

def generate():
 yield "first"
 for i in range(1,4):
     yield str(i)
 yield "last"

In python this function returns an iterator over the values passed to the
yield statements. The nice thing is: it is lazy and can be used as a
coroutine.  Anyway, if we iterate like this:

for r in generate():
 print r

It prints this:

first
1
2
3
last

Here is a scala version in which a produce() method serves the same role
as python's yield:

object Generator {
 def generate = {
     val g = new Generator[String]
     reset {
         g produce "first"
         g produce 1.toString
         g produce 2.toString
         g produce 3.toString
         g produce "last"
     }
     g
 }

 def main(args: Array[String]) {
     for( a <- generate ) println(a)
 }
}

This also prints

first
1
2
3
last

The Generator class is defined in terms of shift() as follows:

class Generator[A] extends Iterator[A] {
 private var a: A = _
 private var k: (Unit => Unit) = null

 def next = {
     val a0 = a
     val k0 = k
     k = null
     k0()
     a0
 }

 def hasNext = k != null

 def produce(a0: A): Unit @ suspendable = {
     a = a0
     shift { k0: (Unit => Unit) => k = k0 }
 }
}

But the example is not quite the same as the python because that had a
loop in
the generate function.  Lets try that in the scala version, replacing the
generate method with:

 def generate = {
     val g = new Generator[String]
     reset {
         g produce "first"
         for( i <- 1 to 4) { g produce i.toString }
         g produce "last"
     }
     g
 }

But this does not compile:

generator.scala:28: error: type mismatch;
found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
required: (Int) => Unit
         for( i <- 1 to 4) { g produce i.toString }
              ^
one error found

Substituting a while loop produces a different compile error. Do any
continuation experts/experimenters out there know what the problem is?

The example was compiled with scala r17271 plus the latest continuations
plugin from trunk as of r18035 for reasons explained in the previous
post. This may be the problem, I don't know.

- Arnold

--
 __~O
-\ <,       Christos KK Loverdos
(*)/ (*)      http://ckkloverdos.com

[Paul Chiusano]

It's a bit nicer separating into Leaf and Branch classes, IMO:

trait Tree {

  def inorder: Stream[Int] = this match {

    case Leaf(a) => Stream(a)

    case Branch(a,l,r) => l.inorder append Stream.cons(a, r.inorder)

  }

}

case class Leaf(a: Int) extends Tree

case class Branch(a: Int, left: Tree, right: Tree) extends Tree

Anyway, I understand the point of the OP was not to debate the merits of generators vs lazy collections. :)

Paul

On Fri, Jun 19, 2009 at 3:11 AM, Jorge Ortiz <jorge.ortiz@...> wrote:

Again, probably not as pretty, but it can be done with lazy collections:

  case class Tree(left: Option[Tree], label: String, right: Option[Tree])

  def inorder(t: Tree): Iterator[String] = {
    t.left.elements.flatMap(inorder) append
    Iterator.single(t.label) append        
    t.right.elements.flatMap(inorder)      
  }

  val t = Tree(Some(Tree(None, "left", None)), "center", Some(Tree(None, "right",  None)))

  for (x <- inorder(t)) println(x)

--j

On Thu, Jun 18, 2009 at 12:48 AM, Christos KK Loverdos <loverdos@...> wrote:

As a side note, I think the point with Python's generators is best given with tree traversal:

def inorder(t):
 if t:
   for x in inorder(t.left):
     yield x
   yield t.label
   for x in inorder(t.right):
     yield x

No explicit state management, no result building up. As soon as I have a value, I yield it.

On Jun 18, 2009, at 6:56 AM, Arnold deVos wrote:

Well yes, you can always string together pieces with append, andThen and so on
but continuations are all about coding this sort of thing in direct-style.
The benefit is not so clear with a simple example like mine.

But the point of the post is not to motivate continuations.  I am wanting
exchange knowledge with others that already do want to continuations and tease
out bugs in the implementation.

-- Arnold

On Thu, 18 Jun 2009 01:33:57 pm Jorge Ortiz wrote:

Scala has lazy collections, which, AFAIK, can do whatever generators can
without needing the continuations plugin.

 val generate =
  (
    Array("first").projection append
    (1 to 4).map(_.toString) append
    Array("last").projection
  ).elements

 for (r <- generate) println(r)

The code is, admittedly, a little ugly, but could be made a little cleaner
with 2.8 collections.

(Note this won't work in the interpreter, as the interpreter calls toString
on "generate", which forces its evaluation. If you suppress the call to
toString, it works as specified.)

--j

On Wed, Jun 17, 2009 at 7:17 PM, Arnold deVos <

adv-list-scala@...> wrote:

I'm interested in the upcoming continuations support so I thought I would
try
to build something similar to the python generators with it.  Here is a
scrap
of python:

def generate():
 yield "first"
 for i in range(1,4):
     yield str(i)
 yield "last"

In python this function returns an iterator over the values passed to the
yield statements. The nice thing is: it is lazy and can be used as a
coroutine.  Anyway, if we iterate like this:

for r in generate():
 print r

It prints this:

first
1
2
3
last

Here is a scala version in which a produce() method serves the same role
as python's yield:

object Generator {
 def generate = {
     val g = new Generator[String]
     reset {
         g produce "first"
         g produce 1.toString
         g produce 2.toString
         g produce 3.toString
         g produce "last"
     }
     g
 }

 def main(args: Array[String]) {
     for( a <- generate ) println(a)
 }
}

This also prints

first
1
2
3
last

The Generator class is defined in terms of shift() as follows:

class Generator[A] extends Iterator[A] {
 private var a: A = _
 private var k: (Unit => Unit) = null

 def next = {
     val a0 = a
     val k0 = k
     k = null
     k0()
     a0
 }

 def hasNext = k != null

 def produce(a0: A): Unit @ suspendable = {
     a = a0
     shift { k0: (Unit => Unit) => k = k0 }
 }
}

But the example is not quite the same as the python because that had a
loop in
the generate function.  Lets try that in the scala version, replacing the
generate method with:

 def generate = {
     val g = new Generator[String]
     reset {
         g produce "first"
         for( i <- 1 to 4) { g produce i.toString }
         g produce "last"
     }
     g
 }

But this does not compile:

generator.scala:28: error: type mismatch;
found   : (Int) => Unit @scala.continuations.cps[Unit,Unit]
required: (Int) => Unit
         for( i <- 1 to 4) { g produce i.toString }
              ^
one error found

Substituting a while loop produces a different compile error. Do any
continuation experts/experimenters out there know what the problem is?

The example was compiled with scala r17271 plus the latest continuations
plugin from trunk as of r18035 for reasons explained in the previous
post. This may be the problem, I don't know.

- Arnold

--
 __~O
-\ <,       Christos KK Loverdos
(*)/ (*)      http://ckkloverdos.com

[Marc Downie]

Unfortunately I have not got my attempted implementation to work yet (see bottom of original post). Not sure if I've hit a limitation, bug or what.

As a sometimes-Scala and oftentimes-Python person I too am interested in this topic and specifically the "limitation, bug or what" part. 

This is going to silly to the Scala-hardcore but if Arnold's original for loop code and everything like it worked, I'd use a lot more Scala. Python's coroutine like generators are extremely useful in my work (animation and music [1]) and while I know you can do anything you want with lazy collections, the resulting code crosses some kind of threshold for collaboration with people in my field (digital art) or my future self.

best,

Marc.

-----------------------------

[1] openendedgroup.com/field --- an IDE for digital art, with a tiny amount of Scala support.