🔬65. The EVAL routine in Perl 6, part 2

Welcome back! As you might notice, there was a small gap in the daily post flow.

Before we are back to the Rakudo internals, a couple of words about some changes here. First of all, every post is now marked with either 🦋 or 🔬 (or with indistinguishable rectangles □ if your browser cannot display an emoji :-). These characters mean two categories of posts here: a butterfly stands for Perl 6 syntax, while a microscope is for Perl 6 internals. In the first category, only user-level aspects or Perl 6 are discussed. In the second, we dig into the source codes of Rakudo. All the past post are updated accordingly.

The second change is that I will occasionally post more articles in the Perl 6 syntax category because I found out that non-Russian speakers often like my Russian blog posts. Those posts are mostly short texts explaining interesting features of Perl 6, such as the =~= operator or promises.

* * *

OK, now we have to talk about the EVAL routine. It is defined in the src/core/ForeignCode.pm file as a multi-function. Let us see at their signatures:

proto sub EVAL($code is copy where Blob|Cool, 
               Str() :$lang = 'perl6',
               PseudoStash :$context, *%n)

multi sub EVAL($code, 
               Str :$lang where { ($lang // '') eq 'Perl5' },
               PseudoStash :$context)

Notice that one of the function is a proto, while another is the only multi-candidate. Unlike many other cases that you can see in the sources of Rakudo, this proto routine contains code. Refer to one of the recent blog posts to see how it works.

We start with an example from the first part of the article.

EVAL('say 123');

Here, the passed value is Str, and it is caught by the proto sub, as its first argument can be Cool.

The sub creates a compiler for the given language (which is Perl 6 by default).

my $compiler := nqp::getcomp($lang);

The next step in the sub is to make a string out of $code. In this first example, this task is trivial.

$code = nqp::istype($code,Blob) ?? $code.decode(
    $compiler.cli-options<encoding> // 'utf8'
) !! $code.Str;

Finally, the string is compiled:

my $compiled := $compiler.compile:
    $code,
    :outer_ctx($eval_ctx),
    :global(GLOBAL),
    :mast_frames(mast_frames),
    |(:optimize($_) with nqp::getcomp('perl6').cli-options<optimize>),
    |(%(:grammar($LANG<MAIN>), :actions($LANG<MAIN-actions>)) if $LANG);

After compilation, you get an object of the ForeignCode type. This class is a child class of Callable, so the object can be called and returned (actually, it’s not quite clear how it happens):

$compiled();

Now you can understand that single quotes in the second example with curly braces still create an executable code:

EVAL('say {456}');

Here, the whole string is compiled as it was a Perl 6 code, and the code block there is a code block, which Perl should execute, and thus say gets a code block, so it calls its gist method to prepare the output:

> {456}.gist
-> ;; $_? is raw { #`(Block|140388575216888) ... }

 

🔬61. Declared in BOOTSTRAP

First of all, a new release of the Rakudo Perl 6 compiler was announced today: 2018.02. There are many fixes and speed improvements there, including one proposed by me. Let me not go through the changes, as most of them require quite in-depth knowledge of the Rakudo internals.

Instead, let us take a low-hanging fruit and look at the feature that you may see almost immediately when you start reading Rakudo sources.

Ideologically, Perl 6 can (and should) be written in Perl 6. Currently, some parts are written in NQP but still, the vast number of data types—located in the src/core directory—are implemented in Perl 6.

The thing is that some classes are not fully defined there. Or their relation to other classes is not explicit. For example, here’s the whole definition of the Sub class:

my class Sub { # declared in BOOTSTRAP
    # class Sub is Routine

}

Not only you don’t see any methods here, but also its hierarchy is defined ‘via comments.’ Of course, Perl 6 is not that smart to read comments saying ‘make this code great and cool,’ so let’s see what’s going on here.

In the source tree, there is the following file: src/Perl6/Metamodel/BOOTSTRAP.nqp, where the above-mentioned relation is built.

The class itself (the Sub name) is declared as a so-called stub in the very beginning of the file:

my stub Sub metaclass Perl6::Metamodel::ClassHOW { ... };

Now, the name is known but the definition is not yet ready. We have seen a few examples earlier. Here is the part of the Sub class:

# class Sub is Routine {
Sub.HOW.add_parent(Sub, Routine);
Sub.HOW.compose_repr(Sub);
Sub.HOW.compose_invocation(Sub);

This code lets the user think that the class definition is the following, as the documentation says:

class Sub is Routine {
}

Other examples of Routine children are Method, Submethod, and Macro. The first two are also defined in BOOTSTRAP:

# class Method is Routine {
Method.HOW.add_parent(Method, Routine);
Method.HOW.compose_repr(Method);
Method.HOW.compose_invocation(Method);

# class Submethod is Routine {
Submethod.HOW.add_parent(Submethod, Routine);
Submethod.HOW.compose_repr(Submethod);
Submethod.HOW.compose_invocation(Submethod);

The classes themselves are defined in their corresponding files src/core/Method.pm and src/core/Submethod.pm:

my class Method { # declared in BOOTSTRAP
    # class Method is Routine

    multi method gist(Method:D:) { self.name }
}
my class Submethod { # declared in BOOTSTRAP
    # class Submethod is Routine

    multi method gist(Submethod:D:) { self.name }
}

Unlike them, the Marco type’s hierarchy is explicitly announced in src/core/Macro.pm:

my class Macro is Routine {
}

As you may see, the classes basically introduce their namespaces and do not add many methods to their Routine parent.

The Routine class in its turn is also defined in two places: in src/core/Routine.pm and in BOOTSTRAP.pm.

my class Routine { # declared in BOOTSTRAP
    # class Routine is Block
    # has @!dispatchees;
    # has Mu $!dispatcher_cache;
    # has Mu $!dispatcher;
    # has int $!rw;
    # has Mu $!inline_info;
    # has int $!yada;
    # has Mu $!package;
    # has int $!onlystar;
    # has @!dispatch_order;
    # has Mu $!dispatch_cache;

This time, there are many methods, some of which are added in src/core/Routine.pm using regular Perl 6 syntax, and some are added through BOOTSTRAP in NQP:

In Perl 6:

method candidates() {
    self.is_dispatcher ??
        nqp::hllize(@!dispatchees) !!
        (self,)
}

In NQP:

Routine.HOW.add_method(Routine, 'dispatcher', nqp::getstaticcode(sub ($self) {
    nqp::getattr(nqp::decont($self),
        Routine, '$!dispatcher')
    }));

Similarly, the attributes from comments are created in NQP:

Routine.HOW.add_attribute(Routine, Attribute.new(:name<@!dispatchees>, :type(List), :package(Routine)));
Routine.HOW.add_attribute(Routine, Attribute.new(:name<$!dispatcher_cache>, :type(Mu), :package(Routine)));

As far as I understand, such bootstrapping is needed because Rakudo requires some Perl 6 defined before it can compile itself. For example, if you declare Sub’s relation to Routine completely in src/core/Sub.pm, then you get an error when compiling Rakudo:

Representation for Sub must be composed before it can be serialized

🔬60. Examining the Real role of Perl 6, part 3

As promised yesterday, let us take a look at the two methods of the Real role: polymod and base.

polymod

I already devoted a post to the Int.polymod method, but the method also exists in the Real role. Let us see if it is different.

method polymod(Real:D: +@mods) {
    my $more = self;
    my $lazy = @mods.is-lazy;
    fail X::OutOfRange.new(
        :what('invocant to polymod'), :got($more), :range<0..Inf>
    ) if $more < 0; 
    gather { 
        for @mods -> $mod {
            last if $lazy and not $more;
            Failure.new(X::Numeric::DivideByZero.new:
                using => 'polymod', numerator => $more
            ) unless $mod;
            take my $rem = $more % $mod;
            $more -= $rem;
            $more /= $mod;
        }
        take $more if ($lazy and $more) or not $lazy;
    }
}

It looks familiar. Comparing to the method of Int, the separation of lazy and non-lazy lists is incorporated in the main loop. In the rest, it is again the mod operation (in the form of %) and a division (and some additional subtraction).

Try the method on the same 120 (but as a Numeric value):

> say 120.polymod(10,10)
(0 2 1)

> say 120e0.polymod(10,10)
(0 2 1)

The first method is a call of Int.polymod, while the second one is Real.polymod. The results are the same.

A final note on the method. Just notice that it also works with non-integer values:

> 120.34.polymod(3.3, 4.4)
(1.54 0.8 8)

Indeed, 1.54 + 0.8 * 3.3 + 8 * 3.3 * 4.4 = 120.34.

base

The base method converts a number to its representation in a different system, e. g., hexadecimal, octal, or in a system with 5 or 35 digits. Extrapolating hexadecimal system, you may guess that if there are 36 digits, then the digits are 0 to 9 and A to Z.

A few examples with the numbers with a floating point (actually, Rat numbers here):

> 120.34.base(10)
120.34
> 120.34.base(36)
3C.C8N1FU
> 120.34.base(3)
11110.100012
> 120.34.base(5)
440.132223

The fractional part is converted separately. The second argument of the method limits the number of digits in it. Compare:

> 120.34.base(5)
440.132223
> 120.34.base(5, 2)
440.14

I will skip the details of the method internals and will only show the most interesting parts.

The signature of the method in the src/core/Real.pm file is the following:

 method base(Int:D $base, $digits? is copy)

The documentation interprets that quite differently (although correct semantically):

method base(Real:D: Int:D $base where 2..36, $digits? --> Str:D)

The possible digits are listed explicitly (not in ranges):

my @conversion := <0 1 2 3 4 5 6 7 8 9
                   A B C D E F G H I J
                   K L M N O P Q R S T
                   U V W X Y Z>;

Finally, the last gathering of the separate digits into a resulting string is done like that, using a call to the Int.base method:

my Str $r = $int_part.base($base);
$r ~= '.' ~ @conversion[@frac_digits].join if @frac_digits;
# if $int_part is 0, $int_part.base doesn't see the sign of self
$int_part == 0 && self < 0 ?? '-' ~ $r !! $r;

The method also does some heuristics to determine the number of digits after the floating point:

my $prec = $digits // 1e8.log($base.Num).Int;
. . .
for ^$prec {
    last unless $digits // $frac;
    $frac = $frac * $base;
    push @frac_digits, $frac.Int;
    $frac = $frac - $frac.Int;
}

Compare now the method with the same method from the Int class:

multi method base(Int:D: Int:D $base) {
    2 <= $base <= 36
        ?? nqp::p6box_s(nqp::base_I(self,nqp::unbox_i($base)))
        !! Failure.new(X::OutOfRange.new(
            what => "base argument to base", :got($base), :range<2..36>))
}

In this case, all the hard work is delegated to the base_I function of NQP.

And that’s more or less all that I wanted to cover from the Real role internals.

🔬59. Examining the Real role of Perl 6, part 2

Today, we continue our initial exploration of the Real role, that was started a couple of days ago.

Together with its methods, the role contains a number of subroutines (placed outside the role) that define the infix operators with the objects of the Real type. The list is not that long, so let me copy it here:

multi sub infix:<+>(Real \a, Real \b) { a.Bridge + b.Bridge }
multi sub infix:<->(Real \a, Real \b) { a.Bridge - b.Bridge }
multi sub infix:<*>(Real \a, Real \b) { a.Bridge * b.Bridge }
multi sub infix:</>(Real \a, Real \b) { a.Bridge / b.Bridge }
multi sub infix:<%>(Real \a, Real \b) { a.Bridge % b.Bridge }
multi sub infix:<**>(Real \a, Real \b) { a.Bridge ** b.Bridge }
multi sub infix:«<=>»(Real \a, Real \b) { a.Bridge <=> b.Bridge }
multi sub infix:<==>(Real \a, Real \b) { a.Bridge == b.Bridge }
multi sub infix:«<»(Real \a, Real \b) { a.Bridge < b.Bridge }
multi sub infix:«<=»(Real \a, Real \b) { a.Bridge <= b.Bridge }
multi sub infix:«≤» (Real \a, Real \b) { a.Bridge ≤ b.Bridge }
multi sub infix:«>»(Real \a, Real \b) { a.Bridge > b.Bridge }
multi sub infix:«>=»(Real \a, Real \b) { a.Bridge >= b.Bridge }
multi sub infix:«≥» (Real \a, Real \b) { a.Bridge ≥ b.Bridge }

proto sub infix:<mod>($, $) is pure {*}
multi sub infix:<mod>(Real $a, Real $b) {
    $a - ($a div $b) * $b;
}

As you see, most of the operators are using the Bridge method, which allows using the same code in derived classes that may redefine the bridge.

There’s also one prefix operation for negation:

multi sub prefix:<->(Real:D \a) { -a.Bridge }

The cis function works as a type converter returning a complex number:

roto sub cis($) {*}
multi sub cis(Real $a) { $a.cis }

Try it out:

> cis(pi)
-1+1.22464679914735e-16i

> cis(pi).WHAT
(Complex)

A bit outstanding, there is a function for atan2:

proto sub atan2($, $?) {*}
multi sub atan2(Real \a, Real \b = 1e0) { a.Bridge.atan2(b.Bridge) }
# should really be (Cool, Cool), and then (Cool, Real) and (Real, Cool)
# candidates, but since Int both conforms to Cool and Real, we'd get lots
# of ambiguous dispatches. So just go with (Any, Any) for now.
multi sub atan2( \a, \b = 1e0) { a.Numeric.atan2(b.Numeric) }

It is a bit strange as it does not follow the manner in which other trigonometric functions are implemented. The atan2 routine is also defined as a method:

proto method atan2(|) {*}
multi method atan2(Real $x = 1e0) { self.Bridge.atan2($x.Bridge) }
multi method atan2(Cool $x = 1e0) { self.Bridge.atan2($x.Numeric.Bridge) }

All other trigonometric functions only exist as Real methods. The rest is defined inside the src/core/Numeric.pm file as self-standing subroutines, for example:

proto sub cos($) is pure {*}
multi sub cos(Numeric \x) { x.cos }
multi sub cos(Cool \x) { x.Numeric.cos }

. . .

proto sub atan($) is pure {*}
multi sub atan(Numeric \x) { x.atan }
multi sub atan(Cool \x) { x.Numeric.atan }

There are a few more routines but let us skip them, as they are quite straightforward and clear.

In the next part, we will explore the two methods of the Real role: polymod and base. Stay tuned!

🔬58. A word on polymod in Perl 6

Before moving to the second part of the Real role, let us stop on the polymod method of the Int class.

The method takes a number and a list of arbitrary numbers (units) and returns the corresponding multipliers. So that you can easily say that 550 seconds, for example, is 9 minutes and 10 seconds:

> 550.polymod(60)
(10 9)

In the method call, the value of 60 is the number of seconds in a minute. In the result, 9 is a number of minutes, and 10 is a remainder, which is a number of seconds. So, 550 seconds = 10 second + 9 minutes.

If you want more details, add more units. For example, what is it 32768 seconds?

> 32768.polymod(60, 60, 24)
(8 6 9 0)

It is 8 seconds, 6 minutes, 9 hours, and 0 days.

Similarly, 132768 seconds are 1 day, 12 hours, 52 minutes, and 48 seconds:

> 132768.polymod(60, 60, 24)
(48 52 12 1)

Honestly, it was quite difficult for me to understand how it works and how to read the result.

Another example from the documentation was even harder:

> 120.polymod(1, 10, 100)
(0 0 12 0)

What does 12 mean? It is, obviously, 12 times 10. OK, But I asked to give me some information about the number of hundreds. My expectation is to have it like that: 120 is 2 times 10 and 1 time 100.

Try 121:

> 121.polymod(1, 10)
(0 1 12)

Erm, why zero? Zero plus 1 times 1 plus 12 times 10? Brr. Ah! You don’t need to specify an explicit 1 in the arguments:

> 121.polymod(10)
(1 12)

That makes more sense. Except the fact that I still don’t know how many hundreds are there in 121:

> 121.polymod(10, 100)
(1 12 0)
> 121.polymod(100, 10)
(21 1 0)

It’s time to take a look at the source code (src/core/Int.pm):

method polymod(Int:D: +@mods) {
    fail X::OutOfRange.new(
        :what('invocant to polymod'), :got(self), :range<0..^Inf>
    ) if self < 0; 

    gather { 
         my $more = self; 
         if @mods.is-lazy { 
             for @mods -> $mod {
                $more
                    ?? $mod
                    ?? take $more mod $mod
                    !! Failure.new(X::Numeric::DivideByZero.new:
                            using => 'polymod', numerator => $more)
                    !! last;
                $more = $more div $mod;
            }
            take $more if $more;
        }
        else {
            for @mods -> $mod {
                $mod
                    ?? take $more mod $mod
                    !! Failure.new(X::Numeric::DivideByZero.new:
                        using => 'polymod', numerator => $more);
                $more = $more div $mod;
            }
            take $more;
        }
    }
}

The method has two branches, one for lazy lists, and another one for non-lazy lists. Let us only focus on the second branch for now:

for @mods -> $mod {
    $mod
        ?? take $more mod $mod
        !! Failure.new(X::Numeric::DivideByZero.new:
                       using => 'polymod', numerator => $more);
    $more = $more div $mod;
}

take $more;

OK, the last take takes the remainder, that’s easy. In the loop, you divide the number by the next unit and then ‘count’ the intermediate reminder.

I would say I would implement it differently and switch the operators:

  for @mods -> $mod {
      $mod
-           ?? take $more mod $mod
+           ?? take $more div $div
          !! Failure.new(X::Numeric::DivideByZero.new:
                         using => 'polymod', numerator => $more);
-      $more = $more div $mod;
+      $more = $more mod $mod;
  }

  take $more;

With this code, I can get the number of hundreds, tens, and ones in 121:

> 121.polymod(100, 10, 1)
(1 2 1 0)

OK, let’s avoid two 1s:

> 1234.polymod(1000, 100, 10, 1)
(1 2 3 4 0)

Also works fine with the earlier example with seconds:

> 132768.polymod(86400, 3600, 60)
(1 12 52 48)

It is 1 day, 12 hours, 52 minutes, and 48 seconds.

As you see, now you have to use explicit units (8600 instead of 24) and you have to sort them in descending order, but now I can understand and explain the result, which I could hardly do for the original method.

 

🔬57. Examining the Real role of Perl 6, part 1

During the last few days, we talked a lot about the Real role. Lets us then look at it more precisely. The code is located in the src/core/Real.pm file.

It contains the role itself and a few subroutines implementing different infixes. The Real role in its turn implements the Numeric role:

my role Real does Numeric {
    . . .
}

It is interesting that the class definition also needs some knowledge about the Complex class, that’s why there is a forward class declaration in the first line of the file:

my class Complex { ... }

The Real role defines many trigonometrical functions as methods, and as we already saw, they are using the Bridge method:

method sqrt() { self.Bridge.sqrt }
method rand() { self.Bridge.rand }
method sin() { self.Bridge.sin }
method asin() { self.Bridge.asin }
method cos() { self.Bridge.cos }
method acos() { self.Bridge.acos }
method tan() { self.Bridge.tan }
method atan() { self.Bridge.atan }

Another set of methods include generic methods that manipulate the value directly:

method abs() { self < 0 ?? -self !! self }
proto method round(|) {*}
multi method round(Real:D:) {
    (self + 1/2).floor; # Rat NYI here, so no .5
}
multi method round(Real:D: Real() $scale) {
    (self / $scale + 1/2).floor * $scale;
}
method truncate(Real:D:) {
    self == 0 ?? 0 !! self < 0 ?? self.ceiling !! self.floor
}

There’s a really interesting and useful variant of the round method, which allows you to align the number to the grid you need:

> 11.5.round(3)
12
> 10.1.round(3)
9

Another set of methods are used to convert a number to different data types:

method Rat(Real:D: Real $epsilon = 1.0e-6) { self.Bridge.Rat($epsilon) }
method Complex() { Complex.new(self.Num, 0e0) }
multi method Real(Real:D:) { self }
multi method Real(Real:U:) {
    self.Mu::Real; # issue a warning;
    self.new
}
method Bridge(Real:D:) { self.Num }
method Int(Real:D:) { self.Bridge.Int }
method Num(Real:D:) { self.Bridge.Num }
multi method Str(Real:D:) { self.Bridge.Str }

And here we have a problem in the matrix. The Bridge method is defined in such a way that it calls the Num method. In its turn, Num is calling Bridge, which calls Num.

Run one of the following lines of code, and Rakudo will hang:

Real.new.say;
Real.new.Str;

 

🔬56. A bit more on Rat vs FatRat in Perl 6

Yesterday, we were digging into Rakudo Perl 6 to understand when a Rat value becomes a Num value. It turned out that if the value becomes too small, which means its denominator gets bigger and bigger, Rakudo starts using a Num value instead of Rat.

We found the place where it happened. Today, let us make an exercise and see if it is possible that Perl 6 behaves differently, namely, it expands the data type instead of switching it to a floating point and losing accuracy.

The change is simple. All you need is to update the ifs inside the DIVIDE_N routine:

--- a/src/core/Rat.pm
+++ b/src/core/Rat.pm
@@ -48,16 +48,14 @@ sub DIVIDE_NUMBERS(Int:D \nu, Int:D \de, \t1, \t2) {
           ($numerator   := -$numerator),
           ($denominator := -$denominator))),
       nqp::if(
-        nqp::istype(t1, FatRat) || nqp::istype(t2, FatRat),
+        nqp::istype(t1, FatRat) || nqp::istype(t2, FatRat) || $denominator >= UINT64_UPPER,
         nqp::p6bindattrinvres(
           nqp::p6bindattrinvres(nqp::create(FatRat),FatRat,'$!numerator',$numerator),
           FatRat,'$!denominator',$denominator),
-        nqp::if(
-          $denominator < UINT64_UPPER,
           nqp::p6bindattrinvres(
             nqp::p6bindattrinvres(nqp::create(Rat),Rat,'$!numerator',$numerator),
-            Rat,'$!denominator',$denominator),
-          nqp::p6box_n(nqp::div_In($numerator, $denominator)))))
+            Rat,'$!denominator',$denominator)
+        ))
 }

Now, there are two outcomes: either the routine generates a Rat value or a FatRat. The latter happens when the sub arguments were already FatRats or when the current Rat gets too close to zero.

Compile and test our modified perl6 executable with Newton’s algorithm from yesterday’s post:

my $N = 25;
my @x = 
    Rat.new(1, 1), 
    -> $x { 
        $x - ($x ** 2 - $N) / (2 * $x)
    } ... *;

.WHAT.say for @x[0..10];
.say for @x[1..10];

As expected, the first elements of the sequence are Rats, while the tail is made of FatRats:

(Rat)
(Rat)
(Rat)
(Rat)
(Rat)
(Rat)
(FatRat)
(FatRat)
(FatRat)
(FatRat)
(FatRat)

Also, you can easily see it if you print the values:

13
7.461538
5.406027
5.01524760
5.0000231782539490
5.0000000000537228965718724535111
5.00000000000000000000028861496160410945540567902983713732806515
5.000000000000000000000000000000000000000000008329859606174157518822601061625174583303232554885171687075417887439374231515823
5.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000693865610585718905982734693675309615913812411108046914931948226816763601320201386971350204028084660605790650314446568089428143916887535905115787146371799888
5.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004814494855534925123195523522159753005055993378092336823010386671077751892080269126953923957066141452855241262256569975702944214065988292758274535222239622977104185030432093986146346015004230914044314506580063758070896734658461687838556535528402765772220596451598003813021305355635793333485373058987453787504731

* * *

I don’t know what is better — to have two different types for a rational number (not counting the Rational role) or one type that can hold both ‘narrow’ and ‘wide’ values, or a mechanism that switches to a wider data type when there is not enough capacity. I feel the best is the last option (in the case that FatRat and Rat are using different types for storing numerators and denominators, of course).

As far as I understand, that was exactly the original thought:

For values that do not already do the Numeric role, the narrowest appropriate type of IntRatNum, or Complex will be returned; however, string containing two integers separated by a /will be returned as a Rat (or a FatRat if the denominator overflows an int64).

Also it feels more natural to silently add more space for more digits instead of breaking the idea of having the Rat type. Anyway, there are different opinions on this, but that should not stop Perl 6 from being widespread.