Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lazy assignation to Seq and Array #1651

Closed
p6rt opened this issue Apr 2, 2010 · 5 comments
Closed

Lazy assignation to Seq and Array #1651

p6rt opened this issue Apr 2, 2010 · 5 comments
Labels

Comments

@p6rt
Copy link

p6rt commented Apr 2, 2010

Migrated from rt.perl.org#74008 (status was 'resolved')

Searchable as RT74008$

@p6rt
Copy link
Author

p6rt commented Apr 2, 2010

From jaume.martif@gmail.com

This patch implements lazy assignation to Seq and Array objects.

Some things that don't work yet​:
* for statements are eager, so a for iterating an infinite set can't be used
on a gather.
* Circular side-effects.
* Either class IO or test io.rakudo need changes, because they don't have
the same semantics when gathers are assigned lazily to Arrays.

The test below can be used to evaluate the patch​:

# Ranges

my @​range_a=1..*;

is @​range_a[0..5].join(','), '1,2,3,4,5,6', 'An infinite range on an
C<Array>';

my @​range_b=2,4,6..*;

is @​range_b[0..5].join(','), '2,4,6,7,8,9', 'An infinite range on an
C<Array> with initial values';

# Series

my @​series_a=2,4,6...*;

is @​series_a[0..5].join(','), '2,4,6,8,10,12', 'Infinite series
2,4,6,8,10,12... on an C<Array>';

my @​series_b=2,4,8...*;

is @​series_b[0..5].join(','), '2,4,8,16,32,64', 'Infinite series
2,4,8,16,32,64... on an C<Array>';

my @​series_c=0,1,{ $^a + $^b }...*;

is @​series_c[0..5].join(','), '0,1,1,2,3,5', 'All fibonacci numbers on an
C<Array>';

# Gather

my @​gather_a = gather { my $n=1; loop { take $n++; } };

is @​gather_a[0..5].join(','), '1,2,3,4,5,6', 'Infinite C<gather/take> on an
C<Array>';

# Side-effects

my $i=0;

my @​side_1 = gather { loop { take $i++ } };

my @​side_2 = @​side_1;

my @​side_3 = @​side_2;

is @​side_1[0..5].join(','),'0,1,2,3,4,5','Assigning C<Gather> with
side-effects';

is @​side_2[0..5].join(','),'0,1,2,3,4,5',''Assigning C<Gather> with
side-effects';

is @​side_3[0..5].join(','),'0,1,2,3,4,5',''Assigning C<Gather> with
side-effects';

# Parcels with multiple potentially infinite sets.

my @​pinf_1 = gather { for 2..5 { take $_ } };
my @​pinf_2 = 8...*;
my @​pinf_3 = 0...*;

my @​parcel_1 = (1,@​pinf_1,6,7,@​pinf_2);
my @​parcel_2 = (1,@​pinf_3,6,7,@​pinf_2);

is @​parcel_1[0..9].join(','),'1,2,3,4,5,6,7,8,9,10';

is @​parcel_2[0..9].join(','),'1,0,1,2,3,4,5,6,7,8','';

my @​map_1=1,2..*;
@​map_1.=map({$_*2});

is @​map_1[0..5].join(','),'2,4,6,8,10,12','Lazy map';

my @​grep_1=1,2..*;
@​grep_1.=grep({$_>2});

is @​grep_1[0..5].join(','),'3,4,5,6,7,8','Lazy grep';

@p6rt
Copy link
Author

p6rt commented Apr 2, 2010

From jaume.martif@gmail.com

0001-Implementation-of-lazy-Seq-and-Array.patch
From b73c5f9bfff9eb20230e0b11116a9e064ef8f7b1 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Jaume=20Mart=C3=AD?= <jaume.martif@gmail.com>
Date: Thu, 1 Apr 2010 23:08:25 -0700
Subject: [PATCH] Implementation of lazy Seq and Array

---
 src/builtins/Iterator.pir     |    6 +++
 src/builtins/List.pir         |   43 ++++++++++++++++++++++
 src/builtins/Seq.pir          |   11 +++---
 src/builtins/SeqIter.pir      |   36 ++++++++++++++++++
 src/cheats/gatheriterator.pir |   80 ++++++++++++++++++++++++++++++++++++++--
 src/cheats/mapiterator.pir    |    7 +++-
 src/core/Any-list.pm          |   58 +++++++++++++++++++-----------
 src/core/RangeIter.pm         |   18 +++++++++
 8 files changed, 228 insertions(+), 31 deletions(-)

diff --git a/src/builtins/Iterator.pir b/src/builtins/Iterator.pir
index 8c4e306..172173a 100644
--- a/src/builtins/Iterator.pir
+++ b/src/builtins/Iterator.pir
@@ -50,6 +50,12 @@ continue until memory is exhausted.
     .return (parcel)
 .end
 
+.sub '!mostly_eager' :method
+    .local pmc items, rest
+    items = self.'eager'()
+    null rest
+    .return (rest,items)
+.end
 
 .namespace ['Iterator']
 .sub 'batch' :method
diff --git a/src/builtins/List.pir b/src/builtins/List.pir
index c989dec..b8c716e 100644
--- a/src/builtins/List.pir
+++ b/src/builtins/List.pir
@@ -70,6 +70,49 @@ Returns the next element of the list.
     .return (value)
 .end
     
+.sub '!mostly_eager' :method
+    .local pmc iter, rpa, value, result, lazy
+    rpa  = getattribute self, '$!rpa'
+    result = new ['Parcel']
+
+  rpa_get:
+    unless rpa goto get_done
+    value = shift rpa
+    $P0 = getprop 'scalar', value
+    if null $P0 goto not_scalar
+    push result, value
+    goto rpa_get
+  not_scalar:
+    $I0 = isa value, ['ResizablePMCArray']
+    if $I0 goto rpa_flatten
+    $I0 = isa value, ['Iterable']
+    if $I0 goto is_iterable
+    push result, value
+    goto rpa_get
+  is_iterable:
+    iter = value.'iterator'()
+    null value
+    null lazy
+    (lazy,value) = iter.'!mostly_eager'()
+    unless null lazy goto is_not_eager
+    if null value goto rpa_get
+  rpa_flatten:
+    splice rpa, value, 0, 0
+    goto rpa_get
+
+  is_not_eager:
+   .local pmc temp
+   unshift rpa, lazy
+   if null value goto all_lazy
+   splice result, value, 0, 0
+ all_lazy:
+   temp = new ['Parcel']
+   splice temp, rpa, 0, 0
+   lazy = temp.'iterator'()
+  get_done:
+    .return (lazy,result)
+.end
+
 =back
 
 =head2 Functions
diff --git a/src/builtins/Seq.pir b/src/builtins/Seq.pir
index 9992e66..a33d062 100644
--- a/src/builtins/Seq.pir
+++ b/src/builtins/Seq.pir
@@ -172,7 +172,8 @@ Performs list assignment using the values from C<source>.
 .sub '!STORE' :method
     .param pmc source
 
-    .local pmc items, rest
+    .local pmc items, rest, values
+    values = new ['Parcel']
     items = new ['Parcel']
     null rest
 
@@ -181,11 +182,11 @@ Performs list assignment using the values from C<source>.
     $I0 = isa source, ['Iterable']
     unless $I0 goto source_item
     $P0 = source.'iterator'()
-    source = $P0.'eager'()
-
+    (rest,values) = $P0.'!mostly_eager'()
   source_loop:
-    unless source goto source_done
-    $P0 = shift source
+    if null values goto done
+    unless values goto source_done
+    $P0 = shift values
     $P1 = self.'!elem'($P0)
     push items, $P1
     goto source_loop
diff --git a/src/builtins/SeqIter.pir b/src/builtins/SeqIter.pir
index 447ff17..c4d37f3 100644
--- a/src/builtins/SeqIter.pir
+++ b/src/builtins/SeqIter.pir
@@ -22,6 +22,42 @@ item to be retrieved.
     proto = p6meta.'new_class'('SeqIter', 'parent'=>'Iterator', 'attr'=>'$!seq $!index')
 .end
 
+=item mostly_eager()
+
+=cut
+
+.sub '!mostly_eager' :method
+    .local pmc items, rest, seq
+    seq   = getattribute self,  '$!seq'
+    # index = getattribute self, '$!index'
+    .local pmc items_parent
+    items = new ['Parcel']
+    items_parent = getattribute seq, '@!items'
+    if null items_parent goto end_loop
+    $I0 = elements items_parent
+    .local int n
+    .local pmc elem
+    n = 0
+  beg_loop:
+    if n == $I0 goto end_loop
+    elem = items_parent[n]
+    unless null elem goto lookup_done
+    elem = seq.'postcircumfix:<[ ]>'(n)
+  lookup_done:
+    push items, elem
+    inc n
+    goto beg_loop
+  end_loop:
+    .local pmc items_lazy
+    rest = getattribute seq, '$!rest'
+    if null rest goto end
+    (rest,items_lazy) = rest.'!mostly_eager'()
+    if null items_lazy goto end
+    splice items, items_lazy, 0, 0
+  end:
+    .return (rest,items)
+.end
+
 
 =item get()
 
diff --git a/src/cheats/gatheriterator.pir b/src/cheats/gatheriterator.pir
index 921bcf6..ffa3bf3 100644
--- a/src/cheats/gatheriterator.pir
+++ b/src/cheats/gatheriterator.pir
@@ -16,7 +16,7 @@ GatherIterator is used to handle gather/take.
 .sub 'onload' :anon :init :load
     .local pmc p6meta, proto
     p6meta = get_hll_global ['Mu'], '$!P6META'
-    proto = p6meta.'new_class'('GatherIterator', 'parent'=>'Iterator', 'attr'=>'$!coro $!block')
+    proto = p6meta.'new_class'('GatherIterator', 'parent'=>'Iterator', 'attr'=>'$!coro $!block $!buffer $!others $!pos')
 .end
 
 =item get()
@@ -27,12 +27,21 @@ Returns the next element of the list.
 
 .include 'except_types.pasm'
 .sub 'get' :method
-    .local pmc coro, i
+    .local pmc coro, i, buffer
+
+    buffer = getattribute self, '$!buffer'
+    if buffer goto buffered
     coro = getattribute self, '$!coro'
     i = self.coro()
+    i = descalarref i
+    i = new ['ObjectRef'], i
+    self.'!spread'(i)
+  buffered:
+    i = shift buffer
     .return (i)
 .end
 
+
 .sub '' :method :subid('!gather_coroutine')
     .local pmc block, eh, ex, i, res
     block = getattribute self, '$!block'
@@ -55,15 +64,78 @@ Returns the next element of the list.
     res()
 .end
 
+
+.sub '!spread' :method
+    .param pmc elem
+    .local pmc other, others, it
+    .local int n
+    others = getattribute self, '$!others'
+    $I0 = elements others
+    n = 0
+  beg:
+    if n == $I0 goto end
+    other = others[n]
+    $P0 = elem
+    push other, $P0
+    inc n
+    goto beg
+  end:
+.end
+
+
+.sub '!mostly_eager' :method
+    .local pmc buffer, others, block, gi, pos, eager, coro
+
+    buffer = getattribute self, '$!buffer'
+    others = getattribute self, '$!others'
+    block = getattribute self, '$!block'
+    coro = getattribute self, '$!coro'
+    $I0 = elements others
+    pos = box $I0
+
+    gi = new ['GatherIterator']
+    setattribute gi, '$!block', block
+    setattribute gi, '$!coro', coro
+    eager = clone buffer
+    $P0 = root_new ['parrot';'ResizablePMCArray']
+    push others, $P0
+    setattribute gi, '$!buffer', $P0
+    setattribute gi, '$!others', others
+    setattribute gi, '$!pos', pos
+
+    .return (gi,eager)
+.end
+
+
+.sub destroy :method :vtable
+    .local pmc others
+    .local pmc pos
+
+    pos = getattribute self, '$!pos'
+    others = getattribute self, '$!others'
+    $P0 = new ['ResizablePMCArray']
+    $I0 = pos
+    splice others, $P0, $I0, 1
+.end
+
+
 .namespace []
 .sub '!GATHER'
     .param pmc block
-    .local pmc gi
+    .local pmc gi, others, buffer
     gi = new ['GatherIterator']
-    setattribute gi, '$!block', block
+    $P0 = clone block
+    setattribute gi, '$!block', $P0
     .const 'Sub' coro = '!gather_coroutine'
     $P0 = clone coro
     setattribute gi, '$!coro', $P0
+    others = root_new ['parrot';'ResizablePMCArray']
+    buffer = root_new ['parrot';'ResizablePMCArray']
+    push others, buffer
+    setattribute gi, '$!buffer', buffer
+    setattribute gi, '$!others', others
+    $P0 = box 0
+    setattribute gi, '$!pos', $P0
     .return (gi)
 .end
 
diff --git a/src/cheats/mapiterator.pir b/src/cheats/mapiterator.pir
index 20d24c9..9b844ab 100644
--- a/src/cheats/mapiterator.pir
+++ b/src/cheats/mapiterator.pir
@@ -51,7 +51,12 @@ Returns the next element of the list.
   done:
     .return (parcel)
 .end
-    
+
+
+.sub '!mostly_eager' :method
+    .return(self)
+.end
+
 =back
 
 =cut
diff --git a/src/core/Any-list.pm b/src/core/Any-list.pm
index 2d5385e..d6f6686 100644
--- a/src/core/Any-list.pm
+++ b/src/core/Any-list.pm
@@ -5,17 +5,16 @@ augment class Any {
     }
 
     our multi method map(&block) {
-        Q:PIR {
-            .local pmc self, block, map
-            self = find_lex 'self'
-            block = find_lex '&block'
-            $P0 = self.'list'()
-            $P0 = $P0.'iterator'()
-            map = new ['MapIterator']
-            setattribute map, '$!iter', $P0
-            setattribute map, '&!block', block
-            %r = map
-        };
+        my @temp = @.list;
+        my $it   = @temp.iterator;
+
+        gather {
+            loop {
+                my $parcel = $it.batch(&block.count());
+                last if ($parcel ~~ ::EMPTY);
+                take &block(|$parcel);
+            }
+        }
     }
 
     multi method first($test) {
@@ -29,9 +28,13 @@ augment class Any {
     }
 
     our multi method grep($test) {
-        gather {
-            for @.list {
-                take $_ if $_ ~~ $test;
+        my @temp = @.list;
+        my $it   = @temp.iterator;
+        gather {
+            loop {
+                my $elem = $it.get;
+                last if ($elem ~~ ::EMPTY);
+                take $elem if $elem ~~ $test;
             }
         }
     }
@@ -155,17 +158,22 @@ augment class Any {
     # other than the stringification of the objects.
     multi method uniq() {
         my %seen;
-        gather for @.list {
-             unless %seen{$_} {
-                 take $_;
-                 %seen{$_} = 1;
+        my @temp = @.list;
+        my $it   = @temp.iterator;
+        gather loop {
+             my $elem = $it.get;
+             last if ($elem ~~ ::EMPTY);
+             unless %seen{$elem} {
+                 take $elem;
+                 %seen{$elem} = 1;
              }
         }
     }
 
     multi method kv() {
         my $i = 0;
-        gather for $.list -> $value {
+        my @temp = @.list;
+        gather for @temp -> $value {
             my $key = $i++;
             take $key;
             take $value;
@@ -174,14 +182,22 @@ augment class Any {
 
     multi method keys() {
         my $i = 0;
-        gather for $.list -> $value {
+        my @temp = @.list;
+        my $it   = @temp.iterator;
+        gather loop {
+            my $value = $it.get;
+            last if ($value ~~ ::EMPTY);
             my $key = $i++;
             take $key;
         }
     }
 
     multi method values() {
-        gather for $.list -> $value {
+        my @temp = @.list;
+        my $it   = @temp.iterator;
+        gather loop {
+            my $value = $it.get;
+            last if ($value ~~ ::EMPTY);
             take $value;
         }
     }
diff --git a/src/core/RangeIter.pm b/src/core/RangeIter.pm
index fe96972..e5ceecd 100644
--- a/src/core/RangeIter.pm
+++ b/src/core/RangeIter.pm
@@ -29,4 +29,22 @@ class RangeIter is Iterator {
         $!value .= succ;
         $current;
     }
+
+    method !mostly_eager() {
+        Q:PIR {
+            .local pmc lazy, eager, max, self
+            self  = find_lex 'self'
+            max = getattribute self, '$!max'
+
+            $I0 = isa max, ['Whatever']
+            if $I0 goto inf_range
+            eager = self.'eager'()
+            goto end
+          inf_range:
+            lazy = self
+          end:
+            .return (lazy, eager)
+        }
+    }
+
 }
-- 
1.6.4.4

@p6rt
Copy link
Author

p6rt commented Sep 30, 2011

From @coke

On Fri Apr 02 14​:20​:38 2010, jmarti wrote​:

This patch implements lazy assignation to Seq and Array objects.

Sorry about the delay in responding. While the patch no longer cleanly
applies, it looks like this feature does exist in current rakudo​:

19​:58 < [Coke]> nom​: my @​range_a = 1..*; say "alive"; print
@​range_a[2344];
19​:58 <+p6eval> nom ebd4d8​: OUTPUT«alive␤2345»

Thanks for the patch, and again, sorry about the delay in responding!

--
Will "Coke" Coleda

@p6rt
Copy link
Author

p6rt commented Sep 30, 2011

The RT System itself - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

p6rt commented Sep 30, 2011

@coke - Status changed from 'open' to 'resolved'

@p6rt p6rt closed this as completed Sep 30, 2011
@p6rt p6rt added the patch label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant