Simulating Perl6 Meta/Hyper operators with pure Functional Programming

LanX has asked for the wisdom of the Perl Monks concerning the following question:

Introduction

I'm doing a case study to simulate Perl6 -Meta-Operators in Perl5 and I'm stuck with a special when restricting myself to pure FP.

See for instance the Cross operator X

    <a b> X 1,2 X <x y>

#produces

    ('a', 1, 'x'),
    ('a', 1, 'y'),
    ('a', 2, 'x'),
    ('a', 2, 'y'),
    ('b', 1, 'x'),
    ('b', 1, 'y'),
    ('b', 2, 'x'),
    ('b', 2, 'y')
[download]

can be simulated with

pp X {"a".."d"};
pp X {"a".."b"} X {1..2} X {'x','y'};

my $iter = X {"a","b"} X {1..2} X {'x','y'};

while ( my ($aref)= $iter->() ) {
  pp $aref;
}
__DATA__
(["a"], ["b"], ["c"], ["d"])
(
  ["a", 1, "x"],
  ["a", 1, "y"],
  ["a", 2, "x"],
  ["a", 2, "y"],
  ["b", 1, "x"],
  ["b", 1, "y"],
  ["b", 2, "x"],
  ["b", 2, "y"],
)
["a", 1, "x"]
["a", 1, "y"]
["a", 2, "x"]
["a", 2, "y"]
["b", 1, "x"]
["b", 1, "y"]
["b", 2, "x"]
["b", 2, "y"]
[download]

Where X is a function with signature (&;$) which accepts an iterator as second argument and returns an iterator.

So in LIST context it produces the whole array in scalar context it just returns a lazy iterator. (i.e. allowing infinite lists)

This functions (and similar others) can be nested and produce nice syntactic sugar, for instance the above has the following precedence

X {"a","b"} ( X {1..2} ( X {"x","y"} ) )

Here my purely functional implementation so far.

(Please note that this is a case study for the API and not optimized for speed. A well designed and tested set of such operators could be optimized and/or reimplemented in XS later, w/o messing with the P5's parser while being as closs as possible to P6 semantics.)

use strict;
use warnings;
use feature qw/say/;
use Data::Dump qw/pp/;


sub gen_listiter {
  my @init=@_;
  my @list=@init;
  
  sub {
    if (@list) {
      return shift @list
    } else {
      @list=@init;
      return ()
    }
  }
}

sub get_array {
  my $iter=shift;
  my @res;
  while ( my ($res)= $iter->() ) {
    push @res,$res;
  }
  return @res;
}

  
my %operations =(
                 '+' => sub { defined $_[1] ? $_[0] + $_[1]->[0] : $_[
+0] },
                );


sub X (&;$) {
  my ($cr,$tail_itr)=@_;
#  my $op = $operations{$tail_itr} if defined $tail_itr;
#  undef $tail_itr if $op;
  

  $tail_itr //= gen_listiter([]);

  
  my $head_itr = gen_listiter($cr->());

  

  my $state='INIT';
  my $head;
  my $tail;
  my $op //= sub { [ $_[0],@{$_[1]} ] };
  
    
  my $cross_itr =
    sub {
      goto $state;
    INIT:
      $state="RESUME";
      while ( ($head) = $head_itr->() ) {
        while ( ($tail) = $tail_itr->() ) {
          return $op->($head,$tail);
        RESUME:
        }
      }
      $state='INIT';
      return;
    };

  if (wantarray) {
    return get_array($cross_itr);
  } else {
    return $cross_itr;
  }
  
}



pp X {"a".."d"};
pp X {"a".."b"} X {1..2} X {'x','y'};

my $iter = X {"a","b"} X {1..2} X {'x','y'};

while ( my ($aref)= $iter->() ) {
  pp $aref;
}
[download]

Extension

Perl6 also allows to use sub-operators which are applied to each combination, like:

my @a = 1, 2;
my @b = 3, 4;
my @c = @a X+ @b; # 1+3, 1+4, 2+3, 2+4
[download]

this could be simulated by passing a string or a anonymous sub in the last parameter slot.

my @a = 1, 2;
my @b = 3, 4;
my @c = X{@a} X{@b} '+'
[download]

An operator symbol like '+' would just be looked up and produce something like 'sub {$a+$b}' to be applied.

Problem

Only the rightmost X has the information about the operation and there is only one slot free to pass an iterator.

Is it possible to write the intermediate (and final) iterators in a purely functional way that the operation (here plus) is incapsulated within the logic of the passed iterators?

Of course there are ways to cheat with OOP by blessing/tying the iterator-ref and returning the operation with something like $op = $iter->get_op()

Another (ugly) way is to check the passed parameters within the iterator $op = $iter->("get_op")

One functional solution could be that all nested iterators just call the next one and append the values so far, and the lowest nested iterator encapsulates the operation and adds over all values reduce {$a+$b} @_ and returns the result thru all levels.

This approach is less optimal, since it inhibits any benefit from memoization, cause sum($a,$b,$c) = sum($a, sum($b,$c)), so many intermediate results from subtrees could be cached. Memoization would result in an extreme performance boost.

I hope my intention is clear now, I don't know there is a solution but it helped talking about it. =)

So there are work arounds but I wonder if a purely functional approach with just one passed function is possible...

Cheers Rolf

( addicted to the Perl Programming Language)

update

PS: If you are wondering about the title ... I was in a hurry and my brain entered a German word so s/mit/with/. :)

Comment on Simulating Perl6 Meta/Hyper operators with pure Functional Programming Select or Download Code

Replies are listed 'Best First'.
Re: Simulating Perl6 Meta/Hyper operators with pure Functional Programming by moritz (Cardinal) on Oct 01, 2013 at 18:54 UTC
I'm not an authority on pure functional programming, and I don't have any working code, so takes this with a grain of salt. But this: Only the rightmost X has the information about the operation and there is only one slot free to pass an iterator. Is it possible to write the intermediate (and final) iterators in a purely functional way that the operation (here plus) is incapsulated within the logic of the passed iterators? sounds an awful lot like you solve the "only one free slot" problem by returning a more complicated object, like an array ref of `[$operator, $iterator]`. Of course that changes the calling convention of the subsequent operations, and you'll likely want to write a `lift` function that deals with the changed calling convention for you. And congratulations, you have invented monads. Which is, of course, the way to solve problems in purely functional languages which you'd solve with state in impure languages. Perl 6 - the future is here, just unevenly distributed	[reply] [d/l] [select]
Re^2: Simulating Perl6 Meta/Hyper operators with pure Functional Programming by LanX (Saint) on Oct 01, 2013 at 22:17 UTC
> you'll likely want to write a lift function An important part of the concept is to return an iterator to the LHS in scalar context for the laziness an array-ref wouldn't help. And there is no context info which tells me if an X {} is nested or already at the RHS of an assignment. (OK I could use metamagic like Damian's Contextual::Return which I never really understood, I'm still suspicious that it might be a April's fool joke) > you have invented monads. kind of ... already in 2011 ... see YAPC talk (well even earlier if you count in Frankfurt Perl Workshop) > the way to solve problems in purely functional languages OK ... needs disambiguation. I don't really care here about side effects, which is the motivation for monads in Haskell. But solutions which "only" work with code-references and closures (i.e. w/o blessing or other magic) have many benefits ... like portability. Cheers Rolf ( addicted to the Perl Programming Language)	[reply]
Re: Simulating Perl6 Meta/Hyper operators mit pure Functional Programming by tobyink (Canon) on Oct 01, 2013 at 18:58 UTC
Nice. Re the syntax, you might be interested in Sub::Infix - it would enable syntax along the lines of: `my $iter = [@list1] \|X\| [@list2];` [download] `use Moops; class Cow :rw { has name => (default => 'Ermintrude') }; say Cow->new->name`	[reply] [d/l]
Re^2: Simulating Perl6 Meta/Hyper operators with pure Functional Programming by LanX (Saint) on Oct 01, 2013 at 22:41 UTC
Sub::Infix is indeed nice, really clever idea ... thanks! :) My problem with overloading so far was that I couldn't use wantarray, i.e. an overloaded '+' always has to return a scalar. But you don't have this problem, right? Anyway ATM I try to find solutions which work w/o overloading to avoid potential side effects. List::Gen for instance globally overloads the typeglob operator... 8-\| > `my $iter = [@list1] \|X\| [@list2];` yep but the problem here is that the array are evaluated (i.e. listified) before being passed to the operator. I'd like to be able to inspect the code block before evaluating it. Cheers Rolf ( addicted to the Perl Programming Language)	[reply] [d/l]
Re: Simulating Perl6 Meta/Hyper operators mit pure Functional Programming by BrowserUk (Patriarch) on Oct 01, 2013 at 19:39 UTC
Seems like a complicated way of doing something very simple: `#! perl -slw use strict; sub X { return map[ $_ ], @{ $_[0] } unless @_ > 1; map { my $item = $_; map { unshift @$_, $item; $_; } X( @_ ); } @{ shift() } } print @$_ for X [ 'a','b' ], [ 1,2 ], ['x','y' ]; __END__ C:\test>FP-X a1x a1y a2x a2y b1x b1y b2x b2y` [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^2: Simulating Perl6 Meta/Hyper operators with pure Functional Programming by LanX (Saint) on Oct 01, 2013 at 22:00 UTC
> Seems like a complicated way of doing ... ... lazy iterators! :) Cheers Rolf ( addicted to the Perl Programming Language)	[reply]
Re: Simulating Perl6 Meta/Hyper operators mit pure Functional Programming by Laurent_R (Canon) on Oct 01, 2013 at 19:01 UTC
Hmm, I find your post very interesting and very stimulating, Rolf. I believe that there must be some solution, but it is only a pure guts feeling, I have nothing to offer right now. It takes a bit of time to fully understand and to test these types of things. I'm keen in trying things out, but have little time for that (late in the evening), so I may not be able to really try things out before the weekend. But, anyway, thank you for these precious thoughts. I hope to be able to have more useful comments next time.	[reply]


Don't ask to ask, just ask
	PerlMonks