Archive for April, 2011

Perl 6 resources

April 30, 2011

I’m writing this post in as a reference for the Perl 6 lecture I’m giving today at Penguicon, but of course it may prove generally useful as well.

Official Perl 6 website
#perl6 IRC
STD.pm6 (official Perl 6 grammar)
Perl 6 Spec
Rakudo website
Rakudo repository on github
masak’s History of Perl 6 (Only up to mid-2010, but still very interesting.)
ABC module (used as an example, interesting real-world grammar usage)
jnthn’s Perl 6 talks

An infinite stream of “Pi”

April 27, 2011

So, after TimToady’s help with my last problem, finishing this is trivial. You just convert the Haskell code without worrying about type safety.

type LFT = (Integer, Integer, Integer, Integer) 
extr :: LFT -> Integer -> Rational 
extr (q,r,s,t) x = ((fromInteger q) * x + (fromInteger r)) / 
                           ((fromInteger s) * x + (fromInteger t)) 
unit :: LFT 
unit = (1,0,0,1) 
comp :: LFT -> LFT -> LFT 
comp (q,r,s,t) (u,v,w,x) = (q*u+r*w,q*v+r*x,s*u+t*w,s*v+t*x) 

becomes

sub extr([$q, $r, $s, $t], $x) { 
    ($q * $x + $r) / ($s * $x + $t); 
}

my $unit = [1, 0, 0, 1];

sub comp([$q,$r,$s,$t], [$u,$v,$w,$x]) {
    [$q * $u + $r * $w, 
     $q * $v + $r * $x, 
     $s * $u + $t * $w, 
     $s * $v + $t * $x];
}

And then the final piece in the puzzle,

pi = stream next safe prod cons init lfts where 
  init = unit 
  lfts = [(k, 4*k+2, 0, 2*k+1) | k<-[1..]] 
  next z = floor (extr z 3) 
  safe z n = (n == floor (extr z 4)) 
  prod z n = comp (10, -10*n, 0, 1) z 
  cons z z’ = comp z z’ 

becomes

sub pi-stream() {
    stream(-> $z { extr($z, 3).floor; },
           -> $z, $n { $n == extr($z, 4).floor; },
           -> $z, $n { comp([10, -10*$n, 0, 1], $z); },
           &comp,
           $unit, 
           (1..*).map({ [$_, 4 * $_ + 2, 0, 2 * $_ + 1] }));
}

It’s a very direct translation.

Does it work?

> my @pi := pi-stream;
> say @pi[^40].join('');
3141592653589793238468163213056056860170

Yay!

Except, according to the Joy of Pi, the first 40 digits of pi are

3.1415926535 8979323846 2643383279 502884197 # pi
3.1415926535 8979323846 8163213056 056860170 # ours

What’s going wrong? I haven’t empirically verified it yet, but I’m pretty sure the issue is Rakudo’s Ints and Rats overflowing. Which means our next post is going to have to dive back into Math::BigInt and Math::FatRat…

More Pi

April 26, 2011

So, in my previous post I started converting a spigot algorithm for calculating pi from Haskell to Perl 6. I apologize for being away for so long, but I’m back at it now.

Interestingly, while I thought the previous stream function was much clearer in p6, this time out I think I have to give the edge to Haskell.

convert :: (Integer,Integer) -> [Integer] -> [Integer] 
convert (m,n) xs = stream next safe prod cons init xs 
  where 
    init = (0%1, 1%1) 
    next (u,v) = floor (u*v*n’) 
    safe (u,v) y = (y == floor ((u+1)*v*n’)) 
    prod (u,v) y = (u - fromInteger y/(v*n’), v*n’) 
    cons (u,v) x = (fromInteger x + u*m’, v/m’) 
    (m’,n’) = (fromInteger m, fromInteger n) 

The difference comes from Haskell’s extremely elegant on-the-fly pair notation. When I translate that to p6, I get

sub convert($m, $n, @x) {
    stream(-> $u { floor($u.key * $u.value * $n); },
           -> $u, $y { $y == floor(($u.key + 1) * $u.value * $n); },
           -> $u, $y { $u.key - $y / ($u.value * $n) => $u.value * $n; },
           -> $u, $x { $x + $u.key * $m => $u.value / $m; },
           0/1 => 1/1,
           @x);
}

Even with p6′s big advantage in not having to explicitly convert integers to rationals, the pair thing makes this round a win for Haskell, IMO.

Perhaps one of the other p6 programmers out there can think of a more elegant way of handling this…

Update: They sure can! The esteemed TimToady pointed out Perl 6 can do something almost identical to the Haskell approach, skipping Pairs altogether:

sub convert($m, $n, @x) {
    stream(-> [$u, $v] { floor($u * $v * $n); },
           -> [$u, $v], $y { $y == floor(($u + 1) * $v * $n); },
           -> [$u, $v], $y { [$u - $y / ($v * $n), $v * $n]; },
           -> [$u, $v], $x { [$x + $u * $m, $v / $m]; },
           [0/1, 1/1],
           @x);
}

This version compares very well with the Haskell version, IMO!


Follow

Get every new post delivered to your Inbox.