Planet Raku

Raku RSS Feeds

Roman Baumer (Freenode: rba #raku or ##raku-infra) / 2023-05-28T09:19:17


Elizabeth Mattijsen: So why is there RakuAST in the first place?

Published by Elizabeth Mattijsen on 2023-05-27T18:43:27

Several people have asked me to explain why RakuAST is such a big thing. And why it was deemed necessary to go down this way. I will try to explain this in this blog post. Without getting too technical I hope.

There are several stages your Raku program goes through before it becomes executable bytecode that can actually be run by a virtual machine such as MoarVM or the JVM.

Before RakuAST

A highly simplified explanation: the first step is to parse your program using a grammar. The grammar determines whether the syntax of your program is correct. For instance: 'say "Hello World";' is syntactically correct and interpreted as a statement (because of the trailing ;) with the argument "Hello World" being passed to something callable called say.

While the parsing of your program is progressing, a data structure is built through the the calling of the associated action methods. That data structure stores the name of the callable say, and its argument "Hello World" in such a way that it can be used for the next step.

Once your Raku program has been parsed completely, the data structures that were built up during parsing, are used to create the bytecode that can actually be run. And then usually execute that bytecode, unless we were pre-compiling a module, in which case the bytecode is saved in a file.

If you really want to look at this, you can find the code in src/Perl6/Grammar.nqp, src/Perl6/Actions.nqp and src/Perl6/World.nqp.

After RakuAST

Until RakuAST, these data structures were just that: data structures that only could be manipulated if you really knew how. And that required knowledge of the way these data-structures were set up, and the methods that you could use to manipulate them. Since these were considered internal information, the format of these data structures could change from one release of Rakudo to the next, rendering any third party modules that used these feaures inoperable.

With RakuAST, these data structures have been replaced by a set of RakuAST:: objects, with a (not yet) documented interface. But an interface that is intended to be stable, like all other Raku Programming Language features. So it has tests that will ultimately be part of roast. To facilitate development with RakuAST, and of RakuAST itself, there already are a number of utility methods such as .raku, .DEPARSE, .literalize, .rakudoc, .grep, .first and of course, the .AST method on strings to have RakuAST objects created for you.

Also with RakuAST, there is now a complete separation of steps: whereas in the old situation sometimes the precursor to bytecode would already be created during parsing, this does not happen with RakuAST. At the end of the parsing stage, there is a single RakuAST::CompUnit object that contains a representation of all of the parsed code, including any documentation and declarator doc blocks.

This representation can then be altered if necessary (think macro, but then better!). Or the representation can be trimmed to only contain documentation, if you just want to create HTML of the documentation.

# create the RakuAST tree of a given source file
my $ast = $filename.IO.slurp.AST;
# show the ASTs of Rakudoc objects in that source file
.say for $ast.rakudoc;

Or it can be used to already do some optimizations, such as constant folding. A very simple example of constant folding:

# fold simple integer addition into a single integer
sub fold-integers($ast) {

    # is it a + operation?
    if $ast ~~ RakuAST::ApplyInfix && $ast.infix.operator eq '+' {
        my $left  = $ast.left;
        my $right = $ast.right;

        # integers on both sides?
        if $left ~~ RakuAST::IntLiteral && $right ~~ RakuAST::IntLiteral {

            # We can calculate the result now, return as a single AST
            return RakuAST::IntLiteral.new(
              $left.compile-time-value + $right.compile-time-value
            )
        }
    }

    # no optimization possible
    $ast
}

# create an example AST
my $ast = "42 + 666".AST.statements.head.expression;
say $ast;
# RakuAST::ApplyInfix.new(
#   left  => RakuAST::IntLiteral.new(42),
#   infix => RakuAST::Infix.new("+"),
#   right => RakuAST::IntLiteral.new(666)
# )

say fold-integers($ast);
# RakuAST::IntLiteral.new(708)

Actually, this logic can be simplified by using the .literalize method, which attempts to reduce a given Rakuast:: object to a literal value (or returns Nil if it cannot do this).

# fold expression into a literal, if possible
sub constant-fold($ast) {
    with $ast.literalize {
        RakuAST::Literal.new($_)
    }
    else {
        $ast
    }
}

Apart from constant-folding, RakuAST can be used to provide run-time optimizers with more information, such as improved escape analysis. All of these that would not be possible (or at least magnitudes of difficulty harder) without RakuAST.

BEGIN

Of course, there is one feature that complicates matters: explicit and implicit BEGIN blocks. Any code in these will be parsed, turned into RakuAST objects, converted to bytecode and executed during parsing of your program.

# explicit BEGIN
BEGIN say "compilation started at " ~ DateTime.now;

# implicit BEGIN
my constant compiled-at = DateTime.now;

It's like a program inside a program, of which the result can be saved for later reference. And yes, you can do an EVAL inside a BEGIN block. So it truly is a program inside a program: all of the features of the Raku Programming Language are available.

But now that we have RakuAST objects, it will actually be technically possible to inspect and possibly alter the RakuAST object tree at that time as well. Which will also open some interesting future capabilities! At the expense of severe headaches for the core developers :-)

Conclusion

This installment gives a little background on why the development of RakuAST is so important for the future development of the Raku Programming Language.

The intended audience are those people willing to be early adopters of these exciting new features in the Raku Programming Language.

Elizabeth Mattijsen: A practical example of RakuAST

Published by Elizabeth Mattijsen on 2023-05-26T10:01:09

A while ago someone asked on #raku if it is possible to create a Raku character class with the valid characters being supplied by a string. This is not possible by default in Raku at the moment. But it is possible using RakuAST!

Let's first see how one can create characters classes with RakuAST by applying the .AST method to an example.

By the way, all of these examples assume that a use experimental :rakuast; or use v6.e.PREVIEW is active.

say 'my token {<[abc]>}'.AST.statements.head.expression;

What this does is

because the .AST returns a statement list, and we're only interested in the expression of the first statement.

The result is:

RakuAST::TokenDeclaration.new(
  body => RakuAST::Regex::Assertion::CharClass.new(
    RakuAST::Regex::CharClassElement::Enumeration.new(
      elements => (
        RakuAST::Regex::CharClassEnumerationElement::Character.new("a"),
        RakuAST::Regex::CharClassEnumerationElement::Character.new("b"),
        RakuAST::Regex::CharClassEnumerationElement::Character.new("c"),
      )
    )
  )
);

So it looks like each character in the charclass is a separate RakuAST::Regex::CharClassEnumerationElement::Character object. With this knowledge, it is pretty easy to make a custom token for the characters in a given string. Let's create a subroutine "chars-matcher" that will create a token with a charclass of the characters for a given string:

sub chars-matcher($string) {
    my @elements = $string.comb.unique.map: {
        RakuAST::Regex::CharClassEnumerationElement::Character.new($_)
    }
    RakuAST::TokenDeclaration.new(
      body => RakuAST::Regex::Assertion::CharClass.new(
        RakuAST::Regex::CharClassElement::Enumeration.new(:@elements)
      )
    ).EVAL
}

First we create an array "@elements" and fill that with an enumeration object for each unique char in the given string ($string.comb.unique). And then we create the TokenDeclaration object as from the example, but with the @elements array as the specification of the characters. And then we convert that into an actual usable token by running .EVAL on it.

An example of its usage:

my $matcher = chars-matcher("Anna Mae Bullock");
say "Tina Turner" ~~ $matcher;       # 「n」
say "Tina Turner" ~~ / $matcher+ /;  # 「na 」

As you can see, you can use the generated token direct in a smart-match. Or you can use it as part of a more complicated regex.

If you're ready to further dabble with RakuAST, it is probably a good idea to know a little bit of how it is currently being implemented. So let's dive a little bit into that, to better understand some of the errors you might encounter when writing Raku Programming Language code to create ASTs.

Prerequisites for RakuAST

It is the intent to have all Raku source code be parsed by the (new) Raku grammar (and associated Actions) in the future, just as it is now with the legacy grammar. Since the Raku core setting (which contains the Raku code for most of the implementation of the Raku Programming Language) must also be parsed by this, it implies that the RakuAST classes must exist before there is any Raku Programming Language.

This is a chicken-and-egg problem that is solved in Rakudo by the so-called "bootstrap". This is quite a sizeable chunk of NQP code that "manually" creates enough functionality to allow the Raku core setting to build itself up to a fully functional implementation of the Raku Programming Language.

When Jonathan Worthington started the RakuAST project, they didn't want to have to implement all of that functionality in NQP yet again. So they devised a neat hack by creating a rather simple parser that would read Raku-like code, and convert that to NQP source code that would create all of the 360+ RakuAST classes when run. Of course, that Raku-like code still does not have the full Raku capabilities, but it does make the implementation task a lot easier than it would have been if it had be all written in NQP.

Example of a RakuAST class' internals

Let's have look a simple example of such a RakuAST class. For instance, the RakuAST::StrLiteral class that we've seen earlier in the first instalment.

class RakuAST::StrLiteral is RakuAST::Literal {
    has Str $.value;

    method new(Str $value) {
        my $obj := nqp::create(self);
        nqp::bindattr($obj, RakuAST::StrLiteral, '$!value', $value);
        $obj
    }

    # other methods

    method IMPL-EXPR-QAST(RakuAST::IMPL::QASTContext $context) {
        my $value := $!value;
        $context.ensure-sc($value);
        my $wval := QAST::WVal.new( :$value );
        QAST::Want.new($wval,'Ss', QAST::SVal.new(:value(nqp::unbox_s($value))))
    }
}

For simplicity's sake, only two methods are shown. The new method, taking a single positional Str $value. Which needs some NQP to create the object and bind the value to the $!value attribute.

And we see an IMPL-EXPR-QAST method. That method will be called whenever that RakuAST object needs to generate QAST (a precursor to actual bytecode) for itself.

If you find this very interesting, you probably want to read the RakuAST README. And the actual source code of the RakuAST classes can be found in the same directory. And if you're really feeling adventurous and you have the Rakudo repository checked out, you can have a look at the generated NQP code in gen/moar/ast.nqp.

What's the point?

So why am I even mentioning this? Because the RakuAST classes look like they're actual Raku classes, but they're really NQP subroutines wrapped up to appear like Raku classes. Which results in unexpected failure modes if there's some error in your calls to RakuAST classes. In other words: the edges are a little bit sharper with RakuAST classes, and LTA error messages can and will happen. It's one of the "benefits" of living on the edge!

Of course, as a user of RakuAST classes, you should only be interested in the new method, and any other non-internal methods. Sadly, it is way too early in the bootstrap to mark internal methods with an is implementation-detail trait, so another heuristic is needed. And that would be: "consider any ALL-CAPS methods to be off-limits".

Conclusion

This installment gives an actual example of how you can use RakuAST in your code today. And gives some technical background on the implementation of RakuAST classes, which still is a little sharp around the edges.

The intended audience are those people willing to be early adopters of these exciting new features in the Raku Programming Language.

Elizabeth Mattijsen: RakuAST for Early Adopters

Published by Elizabeth Mattijsen on 2023-05-24T15:44:04

Originally, I thought I'd name this series of blog posts "RakuAST for Beginners". But since documentation on RakuAST is pretty non-existent at this stage, I felt I would be doing people a service by making clear that they will be at the very front of development in the Raku Programming Language if they start dabbling in RakuAST.

What Is It?

If you're a programmer, you may be aware of the concept of an Abstract Syntax Tree. That's where the "AST" in RakuAST comes from.

Normally, when you write a program in the Raku Programming Language, all of the business of compiling your code into something that can be executed, is done for you under the hood. One of the steps in this process is to create an Abstract Syntax Tree (aka AST from now on) from your code, and convert that to bytecode that an interpreter (or "virtual machine") such as MoarVM can execute.

So where does RakuAST come into this? Well, RakuAST allows you to create an AST (that can be converted to bytecode and run) programmatically without needing to create intermediate source code.

How ready is it for primetime?

Not (yet). Several areas of RakuAST features and semantics are still un(der)developed. But there is enough implemented to allow the new "Raku" grammar to handle Raku source code well enough to make 64% of Raku test files pass completely. A lot of the work that needs to be done with the "Raku" grammar, is to use the already existing RakuAST features, rather than needing new features in RakuAST itself. But that is worth another series of blog posts in itself.

If you want to run your code with the new Raku grammar, you must set the RAKUDO_RAKUAST=1 environment variable before running. Otherwise the default grammar (which is now referred to as the "legacy" grammar) will be used.

In any case, because it is not ready for primetime (yet), and some interfaces and semantics might still change, one will have to put a use experimental :rakuast in the code. Or indicate you want the current development language version, by putting a use v6.e.PREVIEW in the code.

So when should I use this?

When it is handy for you to do so.

To give you an example: sprintf takes a format string to create a string representation of the values given. This is currently implemented with a special "format-string" grammar. Everytime a sprintf is executed (either directly, or by using printf or .fmt), it will parse the format using that grammar. And the associated actions then produce the string representation for the given values.

Needless to say, this is very repetitive and cpu-intensive. Wouldn't it be better to only parse the format once, and then create code for that, and run that code everytime?

Yes, it would. But until there was RakuAST, that was virtually impossible to do because there was no proper API for building ASTs. Nor was there an interface to execute those ASTs. And now that there is RakuAST, it is actually possible to do this. And there is actually already an implementation of that idea in the new Formatter class. Although this is definitely not intended as an entry point into grokking RakuAST.

But maybe a better way to tell whether it is handy for you to use RakuAST, is to use RakuAST whenever you need to resort to using EVAL. Because with RakuAST, you will have a way to not have to worry about incidental code insertion, and you will be able to create semantics for which there is no way in the Raku Programming Language (yet).

Let's start at the beginning

It is common to start with a "Hello World", so let's start with one here as well. This is the syntax to create an AST for saying "Hello World":

use experimental :rakuast;

my $ast = RakuAST::Call::Name.new(
  name => RakuAST::Name.from-identifier("say"),
  args => RakuAST::ArgList.new(
    RakuAST::StrLiteral.new("Hello world")
  )
);

This creates a RakuAST tree and puts that in the $ast variable. There is no output yet, because all that was done here, was to create the RakuAST objects. To actually convert to bytecode and run that, one needs to call the .EVAL method on the RakuAST object:

$ast.EVAL;  # Hello World

Pretty neat, eh? But that's not all. To help in development and debugging, you can say the .raku method on a RakuAST object, and it will create a representation of the object as RakuAST objects in Raku code.

say $ast.raku;
# RakuAST::Call::Name.new(
#   name => RakuAST::Name.from-identifier("say"),
#   args => RakuAST::ArgList.new(
#     RakuAST::StrLiteral.new("Hello world")
#   )
# );

And since most uses of saying RakuAST objects will be to see this representation, you can actually drop the .raku part there, so say $ast will give you the same output.

Of course, sometimes you would like to see how a RakuAST object would look like as Raku source code. And there's a method for that as well: .DEPARSE:

say $ast.DEPARSE;  # say("Hello World")

Of course, the .DEPARSE output will be a little more formal than original. But it will (usually) be legal source code, and round-trippable. And you could argue that this could be used as a (simple) linter. And you'd be right: the way .DEPARSE is implemented, is that it is pluggable (so one could implement their own way of deparsing RakuAST objects). But that in itself is again enough for a series of blog posts.

Finally, sometimes you would have a piece of source code of which you would like to know the RakuAST representation. And for that, there's the .AST method on strings:

my $ast = 'say "Hello World"'.AST;
say $ast;
# RakuAST::StatementList.new(
#   RakuAST::Statement::Expression.new(
#     expression => RakuAST::Call::Name.new(
#       name => RakuAST::Name.from-identifier("say"),
#       args => RakuAST::ArgList.new(
#         RakuAST::QuotedString.new(
#           segments   => (
#             RakuAST::StrLiteral.new("Hello World"),
#           )
#         )
#       )
#     )
#   )
# )

Note that this is slightly more complex than the initial example. But you hopefully see that that's because this is now wrapped as an expression in a statement, which is part of a statement list. And the double quoted string hasn't been flattened yet.

And it should also be noted that this functionality depends on the "Raku" grammar, which does not yet support all Raku Programming Language functionality. So in some cases, it may still not do what you hoped it would do.

Conclusion

This blog post introduces RakuAST, an interface to create Abstract Syntax Trees in the Raku Programming Language. It shows how to build a "Hello World" AST, and shows how to run the AST, how it was created and how it could be represented as Raku source code.

The intended audience are those people willing to be early adopters of these exciting new features in the Raku Programming Language.

Rakudo Weekly News: 2023.21 Maxcinating

Published by Elizabeth Mattijsen on 2023-05-22T13:55:06

Steve Roe was inspired by a fascinating discussion on the #raku-beginner IRC channel about the concept of the maximum and minimum possible values of empty lists, and why the Raku Programming Language handles them the way they are handled. The result was a blog post called “raku to the .max” with some insightful comments on /r/rakulang as well.

Wenzel’s Corner

Wenzel P.P. Peppmeyer was on a roll this week with two blog posts:

Haytham’s Corner

Haytham Elganiny posted an update on the status of the Pakku package handler for the Raku Programming Language.

Anton’s Corner

Anton Antonov published a new module WWW::PaLM and wrote a blog post with an introduction: WWW::PaLM (for Bard and other hallucinators) (/r/rakulang comments).

Weeklies

Weekly Challenge #218 is available for your perusal.

New Problem Solving Issues

Core Developments

RakuAST developments this week:

Meanwhile on Mastodon

Meanwhile still on Twitter

Questions about Raku

Comments

New Raku Modules

Updated Raku Modules

Winding down

Keep Ukraine on your mind! Слава Україні!  Героям слава!

Please keep staying safe, keep staying healthy, and keep up the good work!

If you like what I’m doing, committing to a small sponsorship would mean a great deal!

gfldex: Most trusting

Published by gfldex on 2023-05-21T13:49:56

I was looking for a neat way to specify units when working with numbers. When doing dimensional analysis, many physicists like to put units into square brackets to create an additional namespace. We can do the same.

use v6.d;

class Unit { ... }

class SiInt is Int {
    trusts GLOBAL;
    trusts Unit;

    has Unit $!unit;
    method !unit { return-rw $!unit }

    method new(CORE::Int $new) { nextsame }
    method Str { self.Int::Str ~ $!unit.suffix }

    method ACCEPTS(Unit:U $u) { $!unit === $u }
}

class Unit {
    our $.suffix = '';
    our $.long-name = "unit-less";

    method ACCEPTS(SiInt $si) { $si!SiInt::unit === self }
}

class m is Unit { our $.suffix = 'm'; our $.long-name = 'Meter'; }

multi sub postcircumfix:<[ ]>(SiInt $obj, Unit:U $unit) {
    $obj!SiInt::unit === Unit ?? ($obj!SiInt::unit = $unit)
        !! fail(‘Sorry, units can only be set, not changed.’);

    $obj
}
multi sub postcircumfix:<[ ]>(Int $value, Unit:U $unit) { SiInt.new($value)[$unit] }

constant Int = SiInt; # intentional shadowing of CORE::Int

my $i = 42[m];
put [$i, $i.^name]; # 42m SiInt
my Int() $a = 1;
put [$a, $a.^name]; # 1 SiInt

class s is Unit { our $.suffix = 's'; our $.long-name = 'Seconds'; }
multi sub infix:<+>(SiInt $l, SiInt $r) {
    $l!SiInt::unit === Unit ?? callsame()[$r!SiInt::unit]
    !! $r!SiInt::unit === Unit ?? callsame()[$l!SiInt::unit]
        !! $l!SiInt::unit === $r!SiInt::unit ?? nextsame()
           !! fail(„Unit mismatch between $l and $r“)
}

my $s = 60[s];

say $i + $a; # 43m
say $s + $i; # Unit mismatch between 60s and 42m

The idea is to have a numerical type that is by default unit-less. A unit can be added (but not changed) with square bracket postcircumfix. Since I add type-objects for each unit, I don’t have to mess around with strings and can multi-dispatch if needed. Since I want direct access to the unit, I tell the class to trust the package the operators are defined in. (This could be a module, of course.) What happens to be an ENODOC.

I have to use a forward declaration to get ACCEPTS to get hold of $!unit. Subsequently, multi-dispatch works just fine.

multi sub fancy(Int $value where m) { #`[fancy calculation goes here] }
multi sub fancy(Int) { fail ‘Can only be fancy with Unit "m".’ }
fancy($i);

Since SiInt is just an Int all built-ins will work, so long the unit is restored after using them. Being able to trust operators allows them to access the entire class, without having to cheat with use nqp;.

Because Raku treats types as values, I can calculate a compound unit.

class Meters-per-Second is Unit { our $.suffix = 'm/s'; our $.long-name = 'Meters per Second'; }
multi sub infix:</>(m, s) { Meters-per-Second }

sub speed($d where m, $t where s) { ($d / $t).Int.[m/s] }

my Int $fast = speed(500[m], 1[s]);
say $fast; # 500m/s

I’m quite pleased with being able to extend the type-system so easily without having to invent a complete new DSL. This aids composability greatly.

gfldex: Plucking strings

Published by gfldex on 2023-05-17T12:50:12

This is a correction and follow-up of my previous post. The ever helpful vrurg provided a simplification to my transformative role. I added some evil to it, mostly for nicer looking introspection.

role Trans[::From, ::To, &c] {
    has To $.value;
    method COERCE(From:D $old) {
        self.new(:value($old.&c))
    }

    unless ::?ROLE.^declares_method(my $mname = To.^name) {
        ::?ROLE.^add_method: $mname, ('my method ' ~ $mname ~ '(--> To) { $.value }').EVAL;
    }
}

By checking if the role contains a method already, I don’t need to fool around with the method table any more. I use .EVAL to compose the method name properly. Rakudo doesn’t care, but a human looking at the method name does not need to be confused. Please note the absence of use MONKEY;. The method form of EVAL doesn’t require it. It is safe to assume code not to be safe.

Task 2 can be written as a naive algorithm. Keep the stickers that contain characters that are also in the target word. Check if all letters in the target word are in the kept stickers. If so, show them or complain.

Again, I need a way to turn words into Sets. I shall do so by invoking the coercion-protocol with a new-method.

class Plucked {
    has $.str;
    has @.chars;

    method new(Str:D $s) { callwith  :str($s), :chars($s.comb) }
    method gist { $!str ~ ' ' ~ @!chars.pairs».&{ .key ~ ' ' ~ .value } }
    method Str { $.str }
    method Set { @.chars.Set }
    method AT-POS($pos) { @.chars.AT-POS($pos) }
    method AT-KEY($key) { @.chars.grep( * eq $key ) }
}

constant PC = Plucked(Str:D);

for [
    ('perl','raku','python'), 'peon';
    ('love','hate','angry'), 'goat';
    ('come','nation','delta'), 'accommodation';
    ('come','country','delta'), 'accommodation'
] -> [ @stickers, PC $word ] {
    my @keep;
    for @stickers -> PC $sticker {
        @keep.push($sticker) if $word ∩ $sticker;
    }
    if ([∪] @keep) ⊇ $word {
        put „"$word" can be made with "[email protected]"“;
    } else {
        my $missing = $word ∖ ([∪] @keep);
        put „"$word" can not be made, "$missing" is missing“;
    }
}

The helper class Plucked knows how to dissect Strs and turn them into Sets and Strs. Since laziness is a virtue, I reduce the amount of typing by storing the coercion-type in a constant. Then I write the naive algorithm down.

I didn’t know that I can store coercion-types the same way as other type-objects in a constant. It just DWIMed and that pleases me greatly.

Rakudo Weekly News: 2023.20 SO Survey

Published by Elizabeth Mattijsen on 2023-05-15T15:38:20

The 2023 Stackoverflow Developer Survey is now live. That in itself is not really Raku related, but that the Raku Programming Language is one of the options you can select for your programming language, is! Taking the survey will only take a few minutes of your life, and be your chance to boost the visibility of Raku when the survey results become available (/r/rakulang comments).

Revisited

1 Problem, 5 Programming Languages by code_reports, revisits the Raku solution from the original 1 Problem, 16 Programming Languages video from about a year ago (/r/rakulang comments).

Wenzel’s Corner

Wenzel P.P. Peppmeyer tried out the new coercion features of the Raku Programming Language, and wrote a blog about it: Coercing coercion (/r/rakulang comments).

Weeklies

Weekly Challenge #217 is available for your perusal.

Core Developments

RakuAST developments this week:

Meanwhile still on Twitter

Questions about Raku

Comments

Updated Raku Modules

Winding down

Remember the people of Ukraine are still under attack, every single day. Слава Україні!  Героям слава!

Please keep staying safe, keep staying healthy, and keep up the good work!

If you like what I’m doing, committing to a small sponsorship would mean a great deal!

p6steve: raku to the .max

Published by librasteve on 2023-05-15T11:03:54

This post is inspired by a recent, fascinating discussion on the raku-beginner Discord channel starting with this message. Thanks to the other folks for helping me to get to a better understanding and apologies if my immediate responses were stupid // wrong. This post will hopefully give a bit more space for elaboration.

Before I wrote this post myself, I tried to get ChatGPT to do it for me …

Raku is a programming language that acts as if there was no distinction between numbers and strings, but it’s there behind the scenes internally. Number 2 and string “2” are 99% same, except when they aren’t. There are no “numbers” or “strings”. It’s just scalars, and they convert automatically. But it’s not so simple. 2 and 2.0 are the same thing (as numbers), but “2” and “2.0” are completely different (as strings).

I hope this helps!

ChatGPT – Please write a 2000 word blog post on how raku seamlessly combines numbers and strings

Well that’s a good start, eh? Although not quite 2000 words.

“HUH?”

Our #raku-beginner thread started with a “huh?” moment:

> my Int @i = [];              ... an empty Array of Ints
> say [max] @i;    # -Inf      ... how can a max be minus infinity?

> (-Inf).^name     # Num       ... specifically -Inf is a Num (aka a float)

> my Str @s = [];              ... an empty Array of Strs
> say [max] @s;    # -Inf      ... even worse a Str is now a number

I’ve adjusted this a little for clarity.

We need to explain wtf raku is doing here to incomers from less tolerant languages. If this has got you wondering, read on.

Untyped Context

One helpful clarification coming from our Discord chat:- this post is mainly about raku in untyped context (there will be some words at the end about how this stuff can be gradually controlled with raku types).

Consider this…

> 1 + "2"            #3          ...add an Int to a Str
> 1 ~ "2"            #12         ...concatenate an Int with a Str
> 1 cmp "2"          #Less       ...cmp an Int with a Str
> 1 cmp "a"          #Less       
> (1, "2").sort      #(1,2)      ...sort a List containing Int & Str
> (1, "a").sort      #(1 a)

Raku does its best to do useful things even if you mix types such as numbers and strings. The whole point of untyped context is to do operations between different types.

A typical use case would be reading data in from a .csv file … where number and string format are not well defined and we want to do operations such as sorting on a column.

Some ideas in play here are:

# Arithmetic operations automatically convert strings to numbers...

> "2"            #Str        
> 1 + "2"        #3          ... e.g. +-/* math operators
> + "2"          #Int        ... prefix:<+> is shorthand for .Numerical
# ... and string operations convert numbers to strings

> 1              #Int
> 1 ~ "2"        #"12"       ... string concatenation
> ~ 1            #Str        ... prefix:<~> is shorthand for .Stringy 

Smart Building Blocks

In Raku, where possible, language features reuse lower level building blocks.

Smart comparison, cmp does either <=> or leg, depending on the existing type of its arguments

- leg forces string context for the comparison

- <=> forces numeric context for the comparison

cmp returns a type object Order::Less, Order::Same, Order::More

cmp will first try to compare operands as strings (via coercion to Stringy), and, failing that, will try to compare numerically via the <=> operator or any other type-appropriate comparison operator. 

Raku sort sorts the list, smallest element first. By default infix:<cmp> is used for comparing list elements.

In this spirit, sort is built on cmp, cmp is built on leg and <=> and these are built on type coercion with .Numeric and .Stringy methods. As we will see shortly, min and max also employ the same cmp logic.

This modular design can have some quirks and corner cases – but the basic idea is DRY (Do not Repeat Yourself) a familiar principle of all coding.

Operator Identity

Another idea in play here is operator identity. In general, infix operators can be applied to a single or no element without yielding an error, generally in the context of a reduce operation. Again, Raku is trying it’s best to deliver a valid result.

say [+] ()        #0

The design documents specify that this should return an identity value, and that an identity value must be specified for every operator. In general, the identity element returned should be intuitive. However, here is a table that specifies how it is defined for operator classes in Raku, which corresponds to the table in the above definition in the types and operators defined by the language:

Operator classIdentity value
EqualityTrue
Arithmetic +0
Arithmetic *1
ComparisonTrue
Bitwise0
Stringy
SetsEmpty set or equivalent
Or-like BoolFalse
And-like BoolTrue
https://docs.raku.org/language/operators#Identity

Some real examples bring this to life:

say [+] (2,3);   #5   2 + 3
say [+] (2);     #2   2 + 0
say [+] ();      #0   0 is the identity for '+'
say [*] (2,3);   #6   2 * 3
say [*] (2);     #2   2 * 1
say [*] ();      #1   1 is the identity for '*'

I think of the identity as “what’s the default argument that gives the right answer”

Identity for min & max

Now we can start to see what was going on at the start… from the docs:

max returns the largest of the arguments, as determined by cmp semantics.

say [max] (2,3);  #3   2 max 3 (cmp (<=>) return largest)
say [max] (2);    #2   2 max -Inf
say [max] ();     #0   -Inf is the identity for 'max'

So -Inf (minus infinity) is the identity for the max operator. It is the Raku way to say “what is the smallest possible thing”. That way anything else compared to -Inf will be returned as the largest.

Similarly +Inf is the identity for the min operator.

The Smallest Possible Number

+/-Inf is the Raku way to represent the IEEE 754 floating point standard infinity value. You can also write the ∞ unicode symbol.

IEEE 754 requires infinities to be handled in a reasonable way, such as

https://en.wikipedia.org/wiki/IEEE_754#Infinities

This is implemented by the Floating Point Unit (FPU) part of your CPU and, since it is a hardware concept, it is super fast and is the natural way for a computer to represent the largest possible number (+Inf) or the smallest possible number (-Inf).

I imagine that Larry Wall must have smiled when he realised that this was the perfect choice value for the identity values of min and max operators.

Also, for numbers, in untyped context, Raku already has an automatic and efficient way to walk up the set of built in number types from integers (Ints) to rationals (Rats) to floating point (Nums).

[21:22]librasteve: the idea afaik is that as you get beyond the range of Rats then the efficient way for your machine to handle bigger numbers is Nums so there is graceful degradation of precision, but not of accuracy

[21:23]librasteve: then, if you run out of Nums you get to Inf

So while it is tempting to ask “why don’t we have a special value for the smallest possible Int?” that is asking in principle to have two kinds of infinities – one for Ints and one for Nums. And then raku would need to invent special values and code that repeats what the FPU does anyway – not just for Ints, but for Rats and FatRats and so on. So I think that Larry made a good design choice here and that this mixing of Ints and Nums is one of the neat things you can do in untyped context.

“HUH!” 2.0

Here’s our Huh example again, first the numbers (min is similar to max, of course):

> my Int @i = [];
> say [max] @i;    # -Inf      ... how can a max be minus infinity?

> (-Inf).^name     # Num       ... specifically -Inf is a Num (aka a float)

So, we have a chain of reasonable behaviours:

Some subtle aspects are (i) that max returns a defined value (Num:D) — I think that in general Raku operations should return values and try to avoid returning Type Objects such as (Int) otherwise every piece of code would have to handle Type Object arguments explicitly and (ii) that this design helps functional programming and recursion, like this simple example:

say (().max , "honeybee").max;    #"honeybee"

Legs and Strings

leg is the Raku String three-way comparator. Short for less, equal or greater?. It coerces both arguments to Str and then does a lexicographic comparison.

say 'a' leg 'b';       # Less
say 'a' leg 'a';       # Same
say 'b' leg 'a';       # More

So sort works on Str values via cmp and then leg:

say <b c a>.sort;      # (a b c)

And, following the logic of our building blocks, max and min too:

say max <a b c>;        # c
say min <a b c>;        # a

leg is a very natural way to include a dictionary word sort into the Raku operation set

What happens when you mix numbers and strings in untyped context:

say 1 cmp 'a';          # Less

# under the hood, cmp first tries Numeric comparison <=>
say 1 <=> 'a';          # Cannot convert string to number ... 

# when that fails, cmp switches to String comparison leg
say 1 leg 'a';          # Less

# leg succeeds because it coerces both args to strings

And with max and min:

say 1 max 'a';          # a

So that’s neat … I can use untyped context to sort a mixed set of numbers and strings lexicographically and it will auto convert the numbers to Str as it goes.

The Smallest Possible Thing

When we were dealing only with numbers, the case was clear that -Inf is a good candidate for the smallest possible thing.

Now we have mixed numbers and strings, it is a bit odd to see -Inf come up in our HUH?

Nevertheless, I believe that -Inf is a good design choice for the smallest possible thing, why:

I would agree with critics that say this outcome is “weird” … while it is a natural consequence of the Raku modular approach, it is an odd looking corner case that emerges from a consistent application of the building blocks. Hopefully this post is a start to clarifying, explaining and teaching newcomers.

“HUH!” 3.0

Here’s our Huh example again, now with the strings (min is similar to max, of course):

> my Str @s = [];              ... an empty Array of Strs
> say [max] @s;    # -Inf      ... even worse a Str is now a number

Finally, we have a very similar chain of reasonable behaviours:

I think that this chain is logical and easy to learn and accepting that +/-Inf is a corner case is better overall than special casing largest / smallest values for each type.

Class Act

As mentioned at the beginning, Raku types can be gradually introduced to control the weirdness.

> my Str @s = []; 
> my Str $res = [max] @s;

# Type check failed in assignment to $res; expected Str but got Num (-Inf)

Each degree of string and number specialisation is represented in the raku class diagram – and so you can both gloss over the type differences in untyped context, or you can tighten the types progressively according to your problem domain.

So, you can use the IntStr allomorph here too that will catch just the empty list case:

> my @a = []; 
> my IntStr $res = [max] @a;

# Type check failed in assignment to $res; expected Str but got Num (-Inf)

As ever, comments are welcome!

~librasteve

gfldex: Coercing coercion

Published by gfldex on 2023-05-10T21:35:21

Task 1 of PWC #216 is a Set-operation.

for [('abc', 'abcd', 'bcd'), 'AB1 2CD'; ('job', 'james', 'bjorg'), '007 JB'; ('crack', 'road', 'rac'), 'C7 RA2'] -> [@words, $reg] {
    say @words.grep($reg.lc.comb.grep(/<alpha>/) ⊆ *.comb);
}

The transformation of $reg is a bit unwieldy. I could pull it out and transform it before I use it but then I would have to use is rw. That ain’t neat. What if I could write a type that does the transformation for me? The answer is mildly insane.

role Trans[::From, ::To, &c] {
    has To $.value;
    method COERCE(From:D $old) {
        my \instance = self.new(:value($old.&c));
        my \table = instance.^method_table;
        table{To.^name} = my method ::To(--> To) { $!value }
        instance.^compose;

        instance
    }
}

constant ToSet = Trans[Str, Set, { .lc.comb.grep(/<alpha>/).Set }];

for [('abc', 'abcd', 'bcd'), 'AB1 2CD'; ('job', 'james', 'bjorg'), '007 JB'; ('crack', 'road', 'rac'), 'C7 RA2'] -> [@words, ToSet() $reg] {
    say @words.grep($reg ⊆ *.comb);
}

I create a parametric role that is told how to transform a Str to a Set with a Block and use that as a coercion-type. Things get tricky inside method COERCE because I have to return the role or the coercion-protocol will throw X::Coerce::Impossible. As a result I need to add a method called Set to the parametrised role. Raku doesn’t have the syntax to specify an indirection for method-names (for definitions, calling them can be done with ."$foo"). Hence the use of the MOP. Also, .^add_method doesn’t take a :local-adverb and thus refuses to overload methods provided by Mu and Any. Overwriting the name in the method table is a gnarly hack but works fine — as hacks do.

And so I got myself a way to run code at bind-time in signatures that changes arguments to what I need. I’m not sure what this could be useful for but will keep it in my toolbox nonetheless.

EVAL sadly doesn’t work, because quotes can’t form a closure over a code-object. I believe untangling this would be a nice test for RakuAST-macros and would improve readability for this example quite a bit. In fact, I wouldn’t need a parametric role but could craft a simple class.

Rakudo Weekly News: 2023.19 Pakku

Published by Elizabeth Mattijsen on 2023-05-08T12:33:37

Haytham Elganiny wrote an introduction on how to use the Pakku package manager for the Raku Programming Language, with what it looks like the first implementation of a recommendation manager.

Wenzel’s Corner

Wenzel P.P. Peppmeyer thought algorithms are getting too big, so decided to halve an algorithm.

Adrian’s Corner

Adrian Kreher wrote an introduction to their new SQL::Builder module in making the complex SQL query manageable in Raku.

Weeklies

Weekly Challenge #216 is available for your perusal.

Core Developments

RakuAST developments this week:

Meanwhile on Mastodon

Meanwhile still on Twitter

Questions about Raku

Comments

New Raku Modules

Updated Raku Modules

Winding down

In this week of remembrance, the people of Ukraine are still under attack, every single day. Слава Україні!  Героям слава!

Please keep staying safe, keep staying healthy, and keep up the good work!

If you like what I’m doing, committing to a small sponsorship would mean a great deal!

gfldex: Halve an algorithm

Published by gfldex on 2023-05-07T15:59:46

I considered PWC #215 to be to boring to be solved because it basically requires only halve an algorithm. But that idea kept bouncing around in my head.

my @words := <abc xyz tsu> does role { has Int $.count is rw; };
@words.map({ LAST { say @words.count }; if [before] .comb { .item  } else { @words.count++; Empty } });

Part 1 is a two sentence problem that can be solved with two lines, because Raku splits sorting algorithms into two smaller problems. We got infix:<before> and infix:<after> to describe what ordering in a list actually means. In my eyes Rosettacode proves this to be the right decision. Here, we are asked to check for sorted-ness, without actually having to sort anything. Lesser languages need to resort to loops, we can use a reduction metaop with before to express our wish. So I either retain an element or count the miss and skip the element.

I resorted to mixing in a role because I don’t like to stack symbol declarations on one line. By getting rid of my $count; I can stay within my 2 line limit. For the same reason I used a LAST-phaser. By accident I bound two related things together into the same namespace, which I rather liked in the end.

So far I did not see Raku’s ordering operators in code in the wild, other then Rosettacode. To promote them, I wrote this blogpost.

I’m not sure if the reaction of map to Empty is an ENODOC. It might just be emergent behaviour and I shall seek wisdom in #raku-doc.

Rakudo Weekly News: 2023.18 Thank You, Moritz

Published by Elizabeth Mattijsen on 2023-05-01T11:56:57

Moritz Lenz is a long time Raku collaborator (3.4K+ commits in the Rakudo, 3.4K+ documentation commits, 1.3K+ commits in roast). Which in itself already deserves a big Thank You!

They also have been a TPRF Grant Committee member for a long time. But would like to step down from the Grant Committee soon. Since they are the only Raku oriented member, it would be quite sad to not have any Raku oriented members in this committee anymore.

Please contact Moritz by mail (moritz.lenz at gmail.com), or on #raku, if you’d like to take on this role, or have any questions about it. And thank you again Moritz, for performing this role for a long time!

Paul’s Corner

Paul Buetow published a blog about how they are tracking uptimes on their serverpark in Unveiling guprecords.raku: Global Uptime Records.

Anton’s Corner

Anton Antonov provided an update on their work on the WWW::OpenAI module, which provides access to the machine learning service OpenAI.

Liz’s Corner

Elizabeth Mattijsen solicits comments / suggestions about the idea of having a Solstice Calendar twice a year?

Steering Council

The minutes of the April 29, 2023 meeting are available.

Weeklies

Weekly Challenge #215 is available for your perusal.

Core Developments

And in RakuAST developments this week:

Meanwhile on Mastodon

Meanwhile still on Twitter

Questions about Raku

Comments

New Raku Modules

Updated Raku Modules

Winding down

Some nice new modules and module updates!

This week’s picture is there to remind us that the people of Ukraine are still under attack, every single day. Слава Україні!  Героям слава!

Please keep staying safe, keep staying healthy, and keep up the good work!

If you like what I’m doing, committing to a small sponsorship would mean a great deal!

Rakudo Weekly News: 2023.17 ReleasePeriod

Published by Elizabeth Mattijsen on 2023-04-24T17:39:39

This week saw a number of remarkable releases: first of all a new version of Rakudo (2023.04), which was released by Justin DeVuyst (with the binary packages for various Linux distributions by Claudio Ramirez, including for the latest Ubuntu and Fedora). This was followed up by the release of Rakudo Star 2023.04 by Anton Oks.

Earlier in the week, Jonathan Worthington released the 2023.04 version of the Comma IDE, the Integrated Development Environment for the Raku Programming Language. A time of harvesting indeed!

Hybridizing

The Raku Conference 2023 will be hybrid! To incorporate the positive aspects of online events, you can attend in person in Riga, or online from anywhere on the planet. And there is still time to submit a presentation!

And this just in: specially priced Student in-person tickets!

Fez Outage

While preparing this week’s Rakudo Weekly News, it became clear that there had not been any new modules published since Wed, 19 Apr 2023 17:34:36 GMT. After further investigation, this turned out to have been caused by a silent outage of the fez upload service. It would accept any uploaded distributions without any error message, yet failed to store or index or publish the module. This has now been corrected. But any modules uploaded in this period, sadly will have to be uploaded again.

The good news of this is that no new modules were published using the p6c or CPAN backends in this period, a clear indication that those storage systems for the Raku module ecosystem are being used less and less.

Wenzel’s Corner

Wenzel P.P. Peppmeyer returns after an extended absence (welcome back!) with a blog post called Not even empty.

Clifton’s Corner

Clifton Wood has started blogging about the Raku Programming Language with a blog post called Using a Supply to Track the Number of Items in a Box (/r/rakulang comments).

Rawley’s Corner

Rawley Fowler also found time to write another blog post. This time about Functional Programming with Raku!

Weeklies

Weekly Challenge #214 is available for your perusal.

New Problem Solving Issues

New Pull Requests

Core Developments

And in RakuAST developments this week:

Meanwhile on Mastodon

Meanwhile still on Twitter

Meanwhile on the mailing list

Questions about Raku

Comments

New Raku Modules

Updated Raku Modules

Winding down

This week’s picture is is an oldie, used even before the people of Ukraine were confronted with a full frontal assault. Слава Україні!  Героям слава!

Please keep staying safe, keep staying healthy, and keep up the good work!

If you like what I’m doing, committing to a small sponsorship would mean a great deal!

gfldex: Not even empty

Published by gfldex on 2023-04-23T11:43:41

Another weekend, another rabbit hole. While reading Arne’s solution for challenge #213, I thought to myself: “If the task can be written in one sentence, why does the answer takes more then one line?”. A reasonable question, given the answer is written in Raku. After some wiggling, I found a shorter version.

my @list = <1 2 3 4 5 6>;
@list.classify({ .Int %% 2 ?? 'even' !! 'odd'}){'even','odd'}».sort.put;

To use .classify, as Arne did further down, was the key, because postcircumfix:<{ }> takes more then one key. The resulting lists are hyper-.sorted and .put will not only show more then 100 elements (please don’t use say unless you actually want that) but will also flatten.

Futher on in his post, he tackled some error handling. I wanted that too and to my delight X::Str::Numeric stores the inconvertible thing inside .source.

CATCH {
    when X::Str::Numeric { put „Sorry, I don't know how to handle "{.source}" in my input list.“ }
}

But how would I deal with undefined values? This is not far-fetched. If you get some CSVs that popped out of a less-then-optimal Excel sheet or don’t take the possibility of SQL null into account, you can easily end up with a type-object where you don’t want one. For scalars we can guard code with type-smilies.

sub foo(@a) { say @a.elems };
foo(List); # 1

For me an Array or a List are a place where a (semi-infinitely long and very narrow) box, that could contain stuff, could have been, but isn’t. Rakudo doesn’t care and just binds the undefined value to the @-sigiled symbol. As usual, I was enlightened on IRC. Any.list will try its best to turn a single element into a List with a single element. For 42 that makes perfect sense and allows us to worry less in day-by-day code. For type-objects that leads the question: “How many things are stored in you?”, to be answered with nonsense. I wouldn’t be surprised to learn that this leads to hard to track down bugs. My .t-files typically don’t sport copious testing against undefined values, because I falsely believed that :D would safe my bum.

sub bar(@a where .[0].defined) { say @a.elems };
bar(List);

This is ugly, imprecise and doesn’t really do what I want. When the where-clause is triggered the binding has already happened. I have the feeling that the right solution is to let Any.list fail when called on a type object. As lizmat pointed out, that is a breaking change. It may look benign but there is tons of fault-tolerant-by-accident code out there that relies on sloppy handling of undefined values. In the IRC discussion, lizmat stated she didn’t like the my @a := Int; case. I’m actually fine with that, because the intent of the Raku-programmer (and we want more of those, don’t we?) is clear. The silent case when @-sigiled symbols (not @-sigiled containers!) in Signatures are bound to type-objects worries me. It is certainly possible to change that but may have performance implications. It too could be a breaking change and it is hard to tell how many lurking bugs we would squash with a fix.

Yet, I would really like Raku to be WAT-free, because I surely want Raku to be more sticky.

UPDATE:

The following can be used to make .elems fail early. That prefix:<+> doesn’t go through that method leads to [email protected] return 0 while .elems is 1. Also, Parameter.modifier is an ENODOC.

    Any.^can('elems')[0].candidates.grep({ .signature.params[0].&{ .type, .modifier } ~~ (Any, ':U') }).head\
        .wrap(my method elems { die(‘Abstract containters don't know how to count’) });

rakudo.org: Rakudo compiler, Release #160 (2023.04)

Published on 2023-04-21T00:00:00

p6steve: Raku meets WordPress

Published by librasteve on 2023-04-05T16:21:22

I recently pivoted to move raku from a hobby to part of my $day-job.

Since that includes writing and maintaining WordPress websites, I thought it would be interesting to see just how automated I could get that process.

And to give back the results of my work as a new Raku Module for installation with zef.

This short video shows just how easy it is to get a new WordPress installation including SSL certificate generation and renewal…

Right click to Open Frame in New Tab for full size

You can now take a new server instance and run up a custom WordPress installation in just a few steps:

  1. ssh in and get the rawp command zef install CLI::Wordpress
  2. edit ~/.rawp-config/wordpress-launch.yaml to add your domain
  3. launch a new WP site with rawp setup && rawp launch
  4. view your new WP site frontend and set it up
  5. setup ssl cert renewals rawp renewal

Then you can go rawp wp '--info' (or any of the many WPCLI commands) in quotes

enjoy!

~p6steve

PS. If you are wondering how to easily start a new (AWS) server instance, then CLI::AWS::EC2-Simple can do that job as covered in previous posts.

rakudo.org: Rakudo compiler, Release #159 (2023.02)

Published on 2023-02-22T00:00:00

Andrew Shitov: Solving Task 2 of the Weekly Challenge 204 with the help of ChatGPT

Published by Andrew Shitov on 2023-02-13T14:07:13

Dislaimer. The war in Ukraine continues, so use this text to improve your Raku skills while remembering that we must not use computers and their power to kill people. BTW, did you know that ChatGPT will even refuse to tell you any f-words?

Let us solve the second task from the Weekly Challenge 204. It is called ‘Reshape matrix’ and reads like this:

You are given a matrix (m x n) and two integers (r) and (c).

Write a script to reshape the given matrix in form (r x c) with the original value in the given matrix. If you can’t reshape print 0.

Example 1

Input: [ 1 2 ]
       [ 3 4 ]

       $matrix = [ [ 1, 2 ], [ 3, 4 ] ]
       $r = 1
       $c = 4

Output: [ 1 2 3 4 ]

Example 2

Input: [ 1 2 3 ]
       [ 4 5 6 ]

       $matrix = [ [ 1, 2, 3 ] , [ 4, 5, 6 ] ]
       $r = 3
       $c = 2

Output: [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ] ]

        [ 1 2 ]
        [ 3 4 ]
        [ 5 6 ]

Example 3

Input: [ 1 2 ]

       $matrix = [ 1, 2 ] ]
       $r = 3
       $c = 2

Output: 0

ChatGPT: Here is an Raku solution for the problem:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = 0;
    for @matrix -> @row {
        $total_elements += @row.elems;
    }
    if $total_elements != $r * $c {
        return 0;
    }

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }
    return @result;
}

In the above solution, we first check if the total number of elements in the original matrix is equal to $r * $c. If not, we return 0. If it is, we create a new matrix @result and fill it with the values from the original matrix using a two-level for loop, where the outer loop iterates $r times and the inner loop iterates $c times. The element at $i, $j position in the new matrix is taken from the original matrix using the formula @matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems].

Here is how you can use the reshape-matrix function:

my @matrix = [ [ 1, 2 ], [ 3, 4 ] ];
my $r = 1;
my $c = 4;
my $result = reshape-matrix(@matrix, $r, $c);
say $result;

This will produce the following output:

[ [ 1, 2, 3, 4 ] ]

Me: Can you please add all test cases from the description?

ChatGPT: Sure! Here is the updated code with test cases included:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = 0;
    for @matrix -> @row {
        $total_elements += @row.elems;
    }
    if $total_elements != $r * $c {
        return 0;
    }

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }
    return @result;
}

my @matrix = [ [ 1, 2 ], [ 3, 4 ] ];
my $r = 1;
my $c = 4;
my $result = reshape-matrix(@matrix, $r, $c);
say $result;

@matrix = [ [ 1, 2, 3 ], [ 4, 5, 6 ] ];
$r = 3;
$c = 2;
$result = reshape-matrix(@matrix, $r, $c);
say $result;

@matrix = [ [ 1, 2 ] ];
$r = 3;
$c = 2;
$result = reshape-matrix(@matrix, $r, $c);
say $result;

This will produce the following output:

[[1 2 3 4]]
[[1 2] [3 4] [5 6]]
0

Me: The last example does not print 0 but instead gives an error:
Type check failed in binding to parameter '@row'; expected Positional but got Int (1)

ChatGPT: My apologies! The input matrix in the last example is incorrect. It should be a 2D matrix, not a 1D matrix. Here’s the corrected code [I will not include the same test cases here for brevity — me]:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = 0;
    for @matrix -> @row {
        $total_elements += @row.elems;
    }
    if $total_elements != $r * $c {
        return 0;
    }

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }
    return @result;
}

Me: Nothing changed actually.

ChatGPT: I apologize for the mistake. Here’s the corrected code. [Now it repeats the same code but breaks the test cases for some reason — me.]

. . .

my @matrix = [ [ 1, 2 ], [ 3, 4 ] ];
my $r = 1;
my $c = 4;
my $result = reshape-matrix(@matrix, $r, $c);
say $result;

@matrix = [ [ 1, 2, 3 ], [ 4, 5, 6 ] ];
$r = 3;
$c = 2;
my $result = reshape-matrix(@matrix, $r, $c);
say $result;

@matrix = [ [ 1, 2 ] ];
$r = 2;
$c = 1;
my $result = reshape-matrix(@matrix, $r, $c);
say $result;

Me: No, this gives even worse result. It says that $result is redeclared. But when I remove my from the second and the third declarations, the program still does not print 0 and complains:

Type check failed in binding to parameter '@row'; expected Positional but got Int (1)

ChatGPT: I apologize for the mistakes in my previous answers. Here’s the corrected code:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = 0;
    for @matrix -> @row {
        $total_elements += @row.elems;
    }
    if $total_elements != $r * $c {
        return 0;
    }

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }
    return @result;
}

This will produce the following output:

[[1 2 3 4]]
[[1 2] [3 4] [5 6]]
0

Me: This time it works, thanks! The last correction. If the matrix in the result does not have other embedded matrices, than we need to return a flat one-level matrix. This is about the output for the case 1.

ChatGPT: I apologize for the oversight. Here’s the corrected code:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = 0;
    for @matrix -> @row {
        $total_elements += @row.elems;
    }
    if $total_elements != $r * $c {
        return 0;
    }

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }

    if @result.elems == 1 {
        return @result[0];
    }
    else {
        return @result;
    }
}

This will produce the following output:

[1 2 3 4]
[[1 2] [3 4] [5 6]]
0

Me: Great! Remember the output from this program, as it is correct. But I suggest we make some changes to have a more expressive Raku code. So, let us modify the reshape-matrix function (and by the way, thanks for using hyphen in the name rather than underscore!).

Can you try first without my help?

ChatGPT: Of course! I’d be happy to try writing a more expressive version of the reshape-matrix function. Let me know if there’s anything specific you’d like me to focus on.

Me: Fine 🙂 So lets starts from the low-hanging fruits. At the end of the function, there is an if-else check, which can easily be replaced with the ternary operator.

ChatGPT: Sure, here’s the updated code using the ternary operator:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = 0;
    for @matrix -> @row {
        $total_elements += @row.elems;
    }
    return 0 if $total_elements != $r * $c;

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code works in the same way as the previous version, but the ternary operator ?? !! makes the code more concise and expressive.

Me: Perfect! And I also see that you made a shorter code when returning 0 of reshaping is not possible. Can we try making that part of the program even more compact. I suggest we replace the for loop with a reduction operator. With that, we should be able to count the number of elements in the requested reshaped matrix in a single line.

ChatGPT: Certainly! Here’s the updated code using the reduction operator:

sub reshape-matrix (@matrix, $r, $c) {
    return 0 if ([+] @matrix.map({ @$_ })).elems != $r * $c;

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code uses the map function to create a list of all the elements in the input matrix, and then the reduction operator [+] to sum the elements in the list. The result of the reduction is the number of elements in the input matrix. If this number is not equal to $r * $c, the reshaping is not possible and the function returns 0.

Me: This change is wrong, as since you made it, the program only returns 0 for every input. So I thing the line with map and elemes is wrong and always triggers 0 in the output.

ChatGPT: I apologize for the mistake. Here’s the corrected code:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = 0;
    for @matrix -> @row {
        $total_elements += @row.elems;
    }
    return 0 if $total_elements != $r * $c;

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code works in the same way as the previous versions, but the calculation of the total number of elements has been moved back to a for loop to ensure correct behavior.

Me: Fine. It works, but you cheated and just gave me the previously working program that worked. I did not quite like the for loop in it. I think, to decide if it is not possible to reshape the matrix (and thus return 0), we can use something like: [+] @matrix.map: *.elems. This gives you the value for $total_elements you compute in a loop currently.

ChatGPT: Yes, you’re correct. Here’s the updated code using the reduction operator:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = [+] @matrix.map: *.elems;
    return 0 if $total_elements != $r * $c;

    my @result = [];
    my $element_index = 0;
    for (0 .. $r - 1) -> $i {
        my @new_row = [];
        for (0 .. $c - 1) -> $j {
            @new_row.push(@matrix[$element_index div @matrix[0].elems][$element_index % @matrix[0].elems]);
            $element_index++;
        }
        @result.push(@new_row);
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code uses the map function to create a list of the number of elements in each row of the input matrix, and then the reduction operator [+] to sum the elements in the list. The result of the reduction is the total number of elements in the input matrix. If this number is not equal to $r * $c, the reshaping is not possible and the function returns 0.

Me: Much better, eh? I like how we do it now. Maybe we could get rid of the $total_elements varible and save a line of code, but on the other hand, the name of the variable tells the reader what is happening there. So decide if you want to keep it or not.

Before making further transformations, let us add the test case where reshaping will not be possible, so 0 will be an expected result. So far we only had possible cases.

ChatGPT: Sure, here’s an updated version of the code with an additional test case where reshaping is not possible:

. . .

@matrix = [ [ 1, 2, 3 ], [ 4, 5, 6 ] ];
$r = 2;
$c = 4;
$result = reshape-matrix(@matrix, $r, $c);
say $result;

This code produces the following output:

[1 2 3 4]
[[1 2] [3 4] [5 6]]
[1 2]
0

The additional test case checks that reshaping is not possible when the total number of elements in the input matrix is not equal to $r * $c, and returns 0 as expected.

Me: Perfect, thanks!

Now we can concentrate our efforts on modifying the central part of the reshape-matrix routine, namely, were we have two nested loops. I propose we try the flat method that is available for arrays in Raku.

ChatGPT: Yes, we can certainly use the flat method to simplify the code in the central part of the reshape-matrix function. Here’s an updated version of the code using flat. [Notice how it computes indices for getting a slice from the array. It will break this nice approach later — me.]

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = [+] @matrix.map: *.elems;
    return 0 if $total_elements != $r * $c;

    my @flat = @matrix.flat;
    my @result = [];
    for (0 .. $r - 1) -> $i {
        my @new_row = @flat[$c * $i .. $c * ($i + 1) - 1];
        @result.push(@new_row);
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code uses the flat method to flatten the input matrix into a single list of elements, and then uses a single for loop to extract $c elements at a time to create each row of the reshaped matrix. This simplifies the code and makes it more readable.

Me: Better, but this time the output is a bit odd. We have empty elements at the end of the output arrays, and some redundant nested arrays: Here is the output that I got:

[[1 2] [3 4] (Any) (Any)]
[[[1 2 3] [4 5 6]] [(Any) (Any)] [(Any) (Any)]]
[[[1]] [[2]]]

ChatGPT: I apologize for that mistake. Here’s an updated version of the code that correctly handles the case where the reshaped matrix has fewer elements than the original matrix:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = [+] @matrix.map: *.elems;
    return 0 if $total_elements != $r * $c;

    my @flat = @matrix.flat;
    my @result = [];
    for (0 .. $r - 1) -> $i {
        my @new_row = @flat[$c * $i .. min($c * ($i + 1) - 1, @flat.end)];
        @result.push(@new_row);
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code uses the min function to ensure that the range of elements in each row of the reshaped matrix is limited to the number of elements remaining in the flattened input matrix, so that no extra elements are added to the output.

Me: M-m-m, still some empty and redundant stuff:

[[1 2] [3 4]]
[[[1 2 3] [4 5 6]] [] []]
[[[1]] [[2]]]

But let us change the approach. So, we have @flat, which contains all the items from the original matrix. Now, let us build the output matrix but looping over @flat.

ChatGPT: Yes, that is a good approach. Here’s an updated version of the code that builds the reshaped matrix by looping over the flattened input matrix:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = [+] @matrix.map: *.elems;
    return 0 if $total_elements != $r * $c;

    my @flat = @matrix.flat;
    my @result = [];
    for (0 .. $r - 1) -> $i {
        push @result, [@flat[$c * $i .. $c * $i + $c - 1]];
    }

    return @result.elems == 1 && @result[0].elems == 1 ?? @result[0][0] !! @result;
}

This code uses a single for loop to extract $c elements from the flattened input matrix, and pushes them into the corresponding row of the reshaped matrix. This ensures that the reshaped matrix has the correct number of elements and the correct nested structure.

Me: Love it, but the result is not correct:

[[[1 2] [3 4] (Any) (Any)]]
[[[1 2 3] [4 5 6]] [(Any) (Any)] [(Any) (Any)]]
[[[1]] [[2]]]

We still have empty items at the end and some extra nestedness.

ChatGPT: I apologize for that mistake. Here’s an updated version of the code that correctly handles the case where the reshaped matrix has fewer elements than the original matrix:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = [+] @matrix.map: *.elems;
    return 0 if $total_elements != $r * $c;

    my @flat = @matrix.flat;
    my @result = [];
    for (0 .. $r - 1) -> $i {
        push @result, [@flat[$c * $i .. min($c * $i + $c - 1, @flat.end)]];
    }

    return @result.elems == 1 && @result[0].elems == 1 ?? @result[0][0] !! @result;
}

This code uses the min function to ensure that the range of elements in each row of the reshaped matrix is limited to the number of elements remaining in the flattened input matrix, so that no extra elements are added to the output.

Me: We have this output now:

[[[1 2] [3 4]]]
[[[1 2 3] [4 5 6]] [] []]
[[[1]] [[2]]]

OK, let us think together. So, we have a flat list of items in @flat. We know the number of rows in the final matrix ($r) and the number of columns in it ($c). So, the @result will contain $r rows and $c columns. You are doing right when pushing to @result with a slice. I belive, something is wrong with how you count the edges.

ChatGPT: I apologize for that mistake. Here’s an updated version of the code that correctly handles the case where the reshaped matrix has fewer elements than the original matrix:

sub reshape-matrix (@matrix, $r, $c) {
    my $total_elements = [+] @matrix.map: *.elems;
    return 0 if $total_elements != $r * $c;

    my @flat = @matrix.flat;
    my @result = [];
    for (0 .. $r - 1) -> $i {
        push @result, [@flat[$c * $i .. min($c * ($i + 1) - 1, @flat.end)]];
    }

    return @result.elems == 1 && @result[0].elems == 1 ?? @result[0][0] !! @result;
}

This code uses the min function to ensure that the range of elements in each row of the reshaped matrix is limited to the number of elements remaining in the flattened input matrix, so that no extra elements are added to the output. The calculation of the end index of the range of elements in each row correctly takes into account the number of columns in the reshaped matrix.

Me: I see where we went wrong. When flattenning the matrix, we use flat, but the matrix actually does not contain integers only. This is what is there instead (you can see it by dumpting it with dd): Array @flat = [[1, 2], [3, 4]].

ChatGPT: Yes, you are correct. In that case, we need to first flatten each sub-array in the input matrix before flattening the entire matrix. Here’s an updated version of the code that handles this case:

sub reshape-matrix (@matrix, $r, $c) {
    my @flat = @matrix.map(*.flat).flat;
    my $total_elements = @flat.elems;
    return 0 if $total_elements != $r * $c;

    my @result = [];
    for (0 .. $r - 1) -> $i {
        push @result, [@flat[$c * $i .. min($c * ($i + 1) - 1, @flat.end)]];
    }

    return @result.elems == 1 && @result[0].elems == 1 ?? @result[0][0] !! @result;
}

This code first uses the map method to flatten each sub-array in the input matrix, and then uses flat to flatten the entire matrix. This ensures that the input matrix is in the correct format for the rest of the code.

Me: M-m-m, getting the value of $total_elements based on the size of @flat is genius. And the result is correct! [This is so-o-o nice, I can’t stop enjoing it even after the chat is over.]

ChatGPT: I’m glad you liked it! I’m here to help, so feel free to ask any questions or request further assistance.

Me: The last line of the sub is wrong though. Let us take the previous solution for that computation.

ChatGPT: Yes, you’re correct. Here’s an updated version of the code that uses the previous solution for the final line:

sub reshape-matrix (@matrix, $r, $c) {
    my @flat = @matrix.map(*.flat).flat;
    my $total_elements = @flat.elems;
    return 0 if $total_elements != $r * $c;

    my @result = [];
    for (0 .. $r - 1) -> $i {
        push @result, [@flat[$c * $i .. min($c * ($i + 1) - 1, @flat.end)]];
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code uses the previous solution for the final line, which checks if the reshaped matrix has only one row, and returns that row as a flat list if it does. This ensures that the output of the function is in the correct format.

Me: You know, 0 .. $r - 1 is not too Raku-ish. We could and should use a ^-thing here. [This is another example of a cute solution that the chat offered, just look, I did not show how to code, I just mentioned the tool!]

ChatGPT: Yes, you’re correct. Here’s an updated version of the code that uses the ^ operator in the for loop:

sub reshape-matrix (@matrix, $r, $c) {
    my @flat = @matrix.map(*.flat).flat;
    my $total_elements = @flat.elems;
    return 0 if $total_elements != $r * $c;

    my @result = [];
    for ^$r -> $i {
        push @result, [@flat[$c * $i .. min($c * ($i + 1) - 1, @flat.end)]];
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code uses the ^ operator in the for loop, which is a more idiomatic way of expressing a range of numbers in Raku. The rest of the code remains unchanged.

Me: I am sure that we do not need to initialise @result, as it is an empty array by default.

ChatGPT: Yes, you’re correct. Here’s an updated version of the code that removes the initialization of @result:

sub reshape-matrix (@matrix, $r, $c) {
    my @flat = @matrix.map(*.flat).flat;
    my $total_elements = @flat.elems;
    return 0 if $total_elements != $r * $c;

    my @result;
    for ^$r -> $i {
        push @result, [@flat[$c * $i .. min($c * ($i + 1) - 1, @flat.end)]];
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code removes the initialization of @result, as arrays are empty by default in Raku. The rest of the code remains unchanged.

Me: I like what we have so far. Do you want to make it even more appealing? Let us work on the like inside the loop, where you’ve got push @result. Before I can help, can you help me to understand what exactly is happenning in that line? [At this point, I was too lazy to try understanding the logic behind that min thing, so I just asked to explain it to me.]

ChatGPT: Sure! In the line with push @result, the code is adding a new row to the reshaped matrix. The new row is defined as a slice of the flattened input matrix @flat, starting from the index $c * $i and ending at the minimum of $c * ($i + 1) - 1 and @flat.end.

The purpose of this line is to take $c consecutive elements from @flat and add them to @result as a new row, repeating this process $r times to form the reshaped matrix. The calculation of the start and end indices of the slice takes into account the number of columns $c in the reshaped matrix and the current iteration of the loop.

Me: Clear. But we always know the length of each row. Can we somehow use $c when we compute the right border of the slice?

ChatGPT: Yes, that’s a great suggestion. Here’s an updated version of the code that uses $c when computing the end index of the slice:

sub reshape-matrix (@matrix, $r, $c) {
    my @flat = @matrix.map(*.flat).flat;
    my $total_elements = @flat.elems;
    return 0 if $total_elements != $r * $c;

    my @result;
    for ^$r -> $i {
        push @result, [@flat[$c * $i .. $c * $i + $c - 1]];
    }

    return @result.elems == 1 ?? @result[0] !! @result;
}

This code uses $c when computing the end index of the slice, which makes the code more readable and eliminates the need for the min function. The rest of the code remains unchanged.

Me: Very smart! I think we found a great solution to the task. Just compare how better it is now against the first version. The program prints the output as expected: the arrays are reshaped, and when it is not possible, we see 0:

[1 2 3 4]
[[1 2] [3 4] [5 6]]
[[1] [2]]
0

Yes, it’s great to see that the final version of the code works as expected! I’m glad I could help you improve the code and make it more readable and efficient. If you have any further questions or need additional assistance, feel free to ask!

* * *

Code on GitHub: initial solution; final version.

Also see the solutions of Task 1.

Andrew Shitov: Dialogues with ChatPGP about the Raku programming language. Solving Task 1 of the Weekly Challenge 204

Published by Andrew Shitov on 2023-02-13T09:28:43

Disclaimer: Remember that the war in Ukraine still goes on. Do not consider this material as sort of entertainment. A sad joke would be that you can’t talk to a lot of people now you used to talk to, so it’s time to talk to a computer instead.

This week’s Challenge 204 offers this first task:

You are given an array of integers.

Write a script to find out if the given array is Monotonic. Print 1 if it is otherwise 0.

An array is Monotonic if it is either monotone increasing or decreasing.

Monotone increasing: for i <= j , nums[i] <= nums[j]
Monotone decreasing: for i <= j , nums[i] >= nums[j]

Example 1

Input: @nums = (1,2,2,3)
Output: 1

Example 2

Input: @nums (1,3,2)
Output: 0

Example 3

Input: @nums = (6,5,5,4)
Output: 1

Let us ask ChatGPT to find a solution and then correct it to make it more Raku-ish. The machine solved the task from the first attempt, but you can follow us and see how we managed to make the solution better and more compact. Most (except one or two examples) of the generated code works without any compiler errors, so I will not concentrate on it here.

I copy-and-pasted the task together with examples, and ChatGPT managed to create a first program that already contained the test checks in it.

ChatGPT: Here’s an example of a Raku program that implements the desired functionality:

sub is_monotonic(@nums) {
    my $increasing = True;
    my $decreasing = True;
    for (0 ..^ @nums.end) -> $i {
        for ($i + 1 .. @nums.end) -> $j {
            if (@nums[$i] > @nums[$j]) {
                $increasing = False;
            }
            if (@nums[$i] < @nums[$j]) {
                $decreasing = False;
            }
        }
    }
    return 1 if $increasing || $decreasing;
    return 0;
 }

my @nums = (1, 2, 2, 3);
say is_monotonic(@nums);

@nums = (1, 3, 2);
say is_monotonic(@nums);

@nums = (6, 5, 5, 4);
say is_monotonic(@nums);

This program defines a subroutine is_monotonic that takes an array of integers as input. The subroutine initializes two flags $increasing and $decreasing to True. It then uses nested for loops to compare each pair of elements in the array, and sets the flags to False if a pair of elements does not meet the monotonic increasing or decreasing criteria. Finally, the subroutine returns 1 if either of the flags is still True, indicating that the array is monotonic, and returns 0 otherwise. The program also includes example calls to the is_monotonic subroutine to demonstrate its functionality.

Me: Let me give a hint. In Raku, we can use reduction operators and thus use [<=] in the program to compare array elements without loops.

ChatGPT: Here’s an updated version of the Raku program that implements the desired functionality using reduction operators:

sub is_monotonic(@nums) {
    my $increasing = @nums[0 ..^ @nums.end - 1].map({ @nums[$_] <= @nums[$_ + 1] }).reduce(&all);

    my $decreasing = @nums[0 ..^ @nums.end - 1].map({ @nums[$_] >= @nums[$_ + 1] }).reduce(&all);
    
    return 1 if $increasing || $decreasing;
    return 0;
}

my @nums = (1, 2, 2, 3);
say is_monotonic(@nums);

@nums = (1, 3, 2);
say is_monotonic(@nums);

@nums = (6, 5, 5, 4);
say is_monotonic(@nums);

This program uses the reduction operator &all to check if all elements of the result of the map operation are True. The map operation takes an array slice of @nums and returns a new array of Boolean values indicating whether each pair of elements meets the monotonic increasing or decreasing criteria. The reduction operator then reduces this array to a single Boolean value indicating whether all elements are True. The program then returns 1 if either of the flags $increasing or $decreasing is True, indicating that the array is monotonic, and returns 0 otherwise.

Me: We can do it like this: my $increasing = [>=] @nums;.

ChatGPT: Here’s an even simpler version of the Raku program that implements the desired functionality using the reduction operator [>=]:

sub is_monotonic(@nums) {
    my $increasing = [>=] @nums;
    my $decreasing = [<=] @nums;

    return 1 if $increasing || $decreasing;
    return 0;
}

my @nums = (1, 2, 2, 3);
say is_monotonic(@nums);

@nums = (1, 3, 2);
say is_monotonic(@nums);

@nums = (6, 5, 5, 4);
say is_monotonic(@nums);

This program uses the reduction operator [>=] to check if all elements of the array are in increasing order, and the reduction operator [<=] to check if all elements of the array are in decreasing order. The results of these reductions are stored in the variables $increasing and $decreasing, respectively. The program then returns 1 if either of these variables is True, indicating that the array is monotonic, and returns 0 otherwise. This version of the program is much simpler and more concise than the previous versions.

Me: This works, thank you! But wait, let’s make it even better. In Raku, the last computed value is returned from a function. And we do not need intermediate variables such as $increasing or $descreasing.

ChatGPT: Here’s an even simpler and more idiomatic version of the Raku program that implements the desired functionality using the reduction operator [>=]:

sub is_monotonic(@nums) {
    return 1 if [>=] @nums || [<=] @nums;
    return 0;
}

my @nums = (1, 2, 2, 3);
say is_monotonic(@nums);

@nums = (1, 3, 2);
say is_monotonic(@nums);

@nums = (6, 5, 5, 4);
say is_monotonic(@nums);

In this version of the program, the function is_monotonic returns the result of the expression 1 if [>=] @nums || [<=] @nums; directly. This expression checks if the array is either increasing or decreasing, and returns 1 if either condition is true. If neither condition is true, the function returns 0. The intermediate variables $increasing and $decreasing are no longer needed. This version of the program is even more concise and readable than the previous versions.

Me: [>=] @nums || [<=] @nums already is a Boolean value which can be directly returned, even without the return keyword.

ChatGPT: You’re absolutely right! Here’s the final version of the Raku program that implements the desired functionality:

sub is_monotonic(@nums) {
    [>=] @nums || [<=] @nums;
}

my @nums = (1, 2, 2, 3);
say is_monotonic(@nums);

@nums = (1, 3, 2);
say is_monotonic(@nums);

@nums = (6, 5, 5, 4);
say is_monotonic(@nums);

In this version of the program, the function is_monotonic simply returns the result of the expression [>=] @nums || [<=] @nums;. This expression checks if the array is either increasing or decreasing, and returns a Boolean value indicating the result. The return keyword is no longer needed, as the last computation value of the function is automatically returned. This version of the program is the most concise and readable of all the versions.

Me: And the final touch. In Raku, - seems to be prefered over _ in identifiers names.

ChatGPT: Here’s the final version of the Raku program that implements the desired functionality, with the preferred naming conventions:

sub isMonotonic(@nums) {
    [>=] @nums || [<=] @nums;
}

my @nums = (1, 2, 2, 3);
say isMonotonic(@nums);

@nums = (1, 3, 2);
say isMonotonic(@nums);

@nums = (6, 5, 5, 4);
say isMonotonic(@nums);

In this version of the program, the function isMonotonic simply returns the result of the expression [>=] @nums || [<=] @nums;. This expression checks if the array is either increasing or decreasing, and returns a Boolean value indicating the result. The function name uses the preferred naming convention of using a single - instead of _ in identifier names. This version of the program is the most concise, readable, and idiomatic of all the versions.

Me: No, that was camelCase. In Raku, you can use - in identifiers, so is-monotonic is a valid name.

ChatGPT: Here’s the final version of the Raku program that implements the desired functionality, with the preferred naming conventions:

sub is-monotonic(@nums) {
    [>=] @nums || [<=] @nums;
}

my @nums = (1, 2, 2, 3);
say is-monotonic(@nums);

@nums = (1, 3, 2);
say is-monotonic(@nums);

@nums = (6, 5, 5, 4);
say is-monotonic(@nums);

In this version of the program, the function is-monotonic simply returns the result of the expression [>=] @nums || [<=] @nums;. This expression checks if the array is either increasing or decreasing, and returns a Boolean value indicating the result. The function name uses the preferred naming convention of using a single - in identifier names, as is common in Raku. This version of the program is the most concise, readable, and idiomatic of all the versions.

Me: Ah, no, I mislead you a bit with the Boolean values. The task requires that the program prints 1 and 0, but not True and False.

ChatGPT: Here’s the final version of the Raku program that implements the desired functionality, with the output as 1 and 0:

sub is-monotonic(@nums) {
    return 1 if [>=] @nums;
    return 1 if [<=] @nums;
    return 0;
}

my @nums = (1, 2, 2, 3);
say is-monotonic(@nums);

@nums = (1, 3, 2);
say is-monotonic(@nums);

@nums = (6, 5, 5, 4);
say is-monotonic(@nums);

In this version of the program, the function is-monotonic returns 1 if the array is increasing ([>=] @nums), returns 1 if the array is decreasing ([<=] @nums), and returns 0 otherwise. The function name uses the preferred naming convention of using a single - in identifier names, as is common in Raku. This version of the program implements the desired functionality, with the output as 1 and 0, as specified in the task.

Me: That is an option, correct. But we can also convert a Boolean value to an Int.

ChatGPT: Here’s the final version of the Raku program that implements the desired functionality, with the output as 1 and 0 and using a conversion from Boolean to Int:

sub is-monotonic(@nums) {
    return +([>=] @nums) || +([<=] @nums);
}

my @nums = (1, 2, 2, 3);
say is-monotonic(@nums);

@nums = (1, 3, 2);
say is-monotonic(@nums);

@nums = (6, 5, 5, 4);
say is-monotonic(@nums);

In this version of the program, the function is-monotonic returns +([>=] @nums) || +([<=] @nums). The + operator is used to convert the result of the reduction operator [>=] @nums or [<=] @nums to an Int. The expression returns 1 if the array is increasing or decreasing, and returns 0 otherwise. The function name uses the preferred naming convention of using a single - in identifier names, as is common in Raku. This version of the program implements the desired functionality, with the output as 1 and 0, as specified in the task.

Me: I would suggest we return ([>=] @nums || [<=] @nums).Int.

ChatGPT: Here’s the final version of the Raku program that implements the desired functionality, with the output as 1 and 0 and using the conversion .Int:

sub is-monotonic(@nums) {
    return ([>=] @nums || [<=] @nums).Int;
}

my @nums = (1, 2, 2, 3);
say is-monotonic(@nums);

@nums = (1, 3, 2);
say is-monotonic(@nums);

@nums = (6, 5, 5, 4);
say is-monotonic(@nums);

In this version of the program, the function is-monotonic returns ([>=] @nums || [<=] @nums).Int. The expression ([>=] @nums || [<=] @nums) returns a Boolean value indicating whether the array is increasing or decreasing, and the .Int method is used to convert the Boolean to an Int. The expression returns 1 if the array is increasing or decreasing, and returns 0 otherwise. The function name uses the preferred naming convention of using a single - in identifier names, as is common in Raku. This version of the program implements the desired functionality, with the output as 1 and 0, as specified in the task.

Me: Or of course, better would be to keep the is- function Boolean, and convert the result if you need to print 1s and 0s.

ChatGPT: Here’s the final version of the Raku program that implements the desired functionality, with the function returning a Boolean value and converting the result to an Int when needed:

sub is-monotonic(@nums) {
    [>=] @nums || [<=] @nums;
}

my @nums = (1, 2, 2, 3);
say +is-monotonic(@nums);

@nums = (1, 3, 2);
say +is-monotonic(@nums);

@nums = (6, 5, 5, 4);
say +is-monotonic(@nums);

In this version of the program, the function is-monotonic returns a Boolean value indicating whether the array is increasing or decreasing ([>=] @nums || [<=] @nums). When the result is needed in the form of 1s and 0s, the + operator is used to convert the Boolean to an Int. The function name uses the preferred naming convention of using a single - in identifier names, as is common in Raku. This version of the program implements the desired functionality, with the function returning a Boolean value and converting the result to an Int when needed, as suggested.

Me: Perfect! A smart choice to use a unary prefix. We can also remove the ; inside the sub, as it looks redundant in such a small one-line function.

* * *

From this moment, the machine and I started a dance with some wrong code by not simply removing the semicolon, but also the curly braces around the body of the function, then returning to the previous solution and so on. So, let me stop here and show the final version that is actually a good Raku code, mostly created by machine. Notice that I also had to change || to or to handle operator precedence races.

sub is-monotonic(@nums) {
    [>=] @nums or [<=] @nums
}

my @nums = (1, 2, 2, 3);
say +is-monotonic(@nums);

@nums = (1, 3, 2);
say +is-monotonic(@nums);

@nums = (6, 5, 5, 4);
say +is-monotonic(@nums);

The program prints the result as expected in the task:

1
0
1

* * *

Code on GitHub: initial solution; final version.

Also see the solutions of Task 2.

p6steve: The Laws of Job Hunting

Published by librasteve on 2023-01-05T22:09:18

with inspiration from the Laws of Thermodynamics

0. Zeroeth Law: A Numbers Game

Looking for work is a numbers game.

1. First Law: It’s Not Personal

You are the salesperson, you are the product. This is a conflict of interest. You must objectify and promote yourself (since everyone else is).

The people who select you are judging you on the basis of a piece of paper, or a zoom call, or a short interview, They don’t know you. They are working to a brief. They are predisposed. They don’t care.

2. Second Law: You Will Fail

When you fail an application, an interview it is not about you. It’s about them.

Request practical feedback – you gave your time to make the application, they owe you. Judge it and apply it as you see fit.

3. Third Law: Finding a Job is a Job

You should be prepared to work a full 40 hour week to prepare and submit all your various applications. Since job seeking is a rather lonely and soul challenging activity, this is not easy.

Authors note: I have done job searches a lot over 40 years – both from the applicant and the employer point of view and thus consider myself well qualified to advise based on my experience.

~p6steve

p6steve: Raku CLI AWS – Postvent

Published by librasteve on 2022-12-29T14:40:25

It was great fun writing my two contributions to the Raku Advent calendar:

  1. Day 11: Santa CL::AWS with a short raku procedural wrapper on AWS CLI
  2. Day 16: Santa CL::AWS (part 2) with a raku OO refactoring

These posts presented my work in progress, in advent calendar style of course, on a new raku module: CLI::AWS::EC2-Simple. The module is now available at the raku zef repository via raku.land with github repo here. This post completes the CL::AWS trilogy with a demo of it in action and how the OO model from last time is now wrapped as a command.

Show Me

First, here’s the new module in action:

By the way, I chose to base the script name as “raws” in homage to the great, but different, perl5 cpan module paws. Paws is an autogenerated and complete perl5 interface to AWSCLI … and can easily be used from raku code like this use PAWS::EC2:from<Perl>; and indeed there’s a debate about that on the raku reddit.

But Raws is different. It is meant primarily to help me in my needs to quickly and consistently launch the same EC2 configuration as specified in a minimal yaml. A command line shorthand alternative to the AWS EC2 console launch dialog. So, Raws is an added value wrapper to AWSCLI, an abstraction with the emphasis on Simplicity and Repeatability. I have released it as a module in the vague expectation that others will have the same needs.

The sharp eyed reader will note that the command is actually raws-ec2. This is in anticipation of some other author creating a raws-s3 for example, or maybe a broader command that can be used via a bare raws –ec2 or raws –s3 and so on.

Getting Started

Command Abstract

The built-in raku MAIN() routine helps to quickly add command line features to our module including a quick abstract of the commands and arguments. Just type raws-ec2 for this:

./raws-ec2 [--id=] [--nsu] [--eip] [-y] 
  
             One of 'list launch setup connect state terminate nuke'
    --id=    Running InstanceId of form 'i-0785d8bd98b5f458b'
    --nsu    No setup (suppress launch from running setup)
    --eip    Allocates (if needed) and Associates Elastic IP
    -y       Silence confirmation  cmd only

Authors note: Beware – these examples can quickly ramp your AWS bill! Keep an eye in your AWS EC2 Instances console. 

Simple Consistent Pattern

Now, here’s a peek inside the default aws-ec2-launch.yaml file that comes with the module:

instance:
    image: 'ami-0f540e9f488cfa27d'
    type: 't2.micro'
    security-group:
        name: 'MySG'
        rules:
            - inbound:
                port: 80
                cidr: '0.0.0.0/0'
            - inbound:
                port: 443 
                cidr: '0.0.0.0/0'

This is the heart of the system, making one easy place to setup and manage your preferences at the AWS Instance level. [Just be careful to save your changes away when reinstalling the module]

To be honest, while very powerful, I find the awscli itself quite bewildering with multiple steps to connect and setup a session (KeyPair, Security Groups, Elastic IP assignment, and so on), so I was chuffed to see just how neatly the key parameters can be boiled down and handed to raws-ec2 to do the painful bit.

Making a Raku Library Module

Here’s the raku Object Oriented code from part II… with some details folded away:

To turn this into a raku module, a couple of tweaks were needed: a header line like this:

unit module CLI::AWS::EC2-Simple:ver<0.0.2>:auth<Steve Roe ([email protected])>;

Also, the classes we want to expose need to be marked ‘is export’:

class Instance is export { ... }

Also I used the $*HOME global to set the home directory of the target installation. The curious may want to check out my Build.pm for how the install set up the default config files.

Making a Raku Command

I did think about folding away some of the command code, but then there is some value in seeing how it all fits together into just over 80 lines…

Star Features

The stars to raku fall in several places:

Functional Future

So, this delivery of a simple EC2 tool was pretty straightforward to write and will save me time by giving me a way to remember my repeatable settings and apply them consistently. Perhaps there is scope for friendly Instance tags here too…

As mentioned in part II, the Raku Functional features could help us to improve clarity and composability even more.

But that’s for another time…

~p6steve

PS. Please comment and feedback here (follow the Archive link) or over at reddit

Elizabeth Mattijsen: The 2022 Raku Advent Blog

Published by Elizabeth Mattijsen on 2022-12-26T12:25:42

(in chronological order, with comment references)

Hope to see you again next year!

Raku Advent Calendar: The 2022 Raku Advent Posts

Published by Elizabeth Mattijsen on 2022-12-26T01:01:00

(in chronological order, with comment references)

Raku Advent Calendar: Day 25: Rakudo 2022 Review

Published by Elizabeth Mattijsen on 2022-12-25T01:01:00

In a year as eventful as 2022 was in the real world, it is a good idea to look back to see what one might have missed while life was messing with your (Raku) plans.

Rakudo saw about 1500 commits this year, about the same as the year before that. Many of these were bug fixes and performance improvements, which you would normally not notice. But there were also commits that actually added features to the Raku Programming Language. So it feels like a good idea to actually mention those more in depth.

So here goes! Unless otherwise noted, all of these changes are in language level 6.d, and available thanks to several Rakudo compiler releases during 2022.

New REPL functionality

It is now possible to refer to values that were produced earlier, using the $*N syntax, where N is a number greater than or equal to 0.

$ raku
To exit type 'exit' or '^D'
[0] > 42
42
[1] > 666
666
[2] > $*0 + $*1
708

Note that the number before the prompt indicates the index with which the value that is going to be produced, can be obtained.

New MAIN options

You can now affect the interpretation of command line arguments to MAIN by setting these options in the %*SUB-MAIN-OPTS hash:

allow-no

Allow negation of a named argument to be specified as --no-foo instead of --/foo.

numeric-suffix-as-value

Allow specification of a numeric value together with the name of a single letter named argument. So -j2 being the equivalent of --j=2.

So for example, by putting:

my %*SUB-MAIN-OPTS = :allow-no, :numeric-suffix-as-value;

at the top of your script, you would enable these features in the command-line argument parsing.

New types

Native unsigned integers (both in scalar, as well as a (shaped) array) have finally become first class citizens. This means that a native unsigned integer can now hold the value 18446744073709551615 as the largest positive value, from 9223372036854775807 before. This also allowed for a number of internal optimisations as the check for negative values could be removed. As simple as this sounds, this was quite an undertaking to get support for this on all VM backends.

my uint  $foo = 42;
my uint8 $bar = 255;
my  int8 $baz = 255;

say $foo; # 42
say $bar; # 255
say $baz; # -1

say ++$foo; # 43
say ++$bar; # 0
say ++$baz; # 0

And yes, all of the other explicitly sized types, such as uint16uint32 and uint64, are now also supported!

New subroutines

A number of subroutines entered the global namespace this year. Please note that they will not interfere with any subroutines in your code with the same name, as these will always take precedence.

NYI()

The NYI subroutine takes a string to indicate a feature not yet implemented, and turns that into a Failure with the X::NYI exception at its core. You could consider this short for ... with feedback, rather than just the “Stub code executed”.

say NYI "Frobnication";
# Frobnication not yet implemented. Sorry.

chown()

The chown subroutine takes zero or more filenames, and changes the UID (with the :uid argument) and/or the GID (with the :gid argument) if possible. Returns the filenames that were successfully changed. There is also a IO::Path.chown method version.

my @files  = ...;
my $uid    = +$*USER;
my changed = chown @files, :$uid;
say "Converted UID of $changed / @files.elems() files";

Also available as a method on IO::Path, but then only applicable to a single path.

head(), skip(), tail()

The .head.skip and .tail methods got their subroutine counterparts.

say head 3, ^10; # (0 1 2)
say skip 3, ^10; # (3,4,5,6,7,8,9)
say tail 3, ^10; # (7 8 9)

Note that the number of elements is always the first positional argument.

New methods

Any.are

The .are method returns the type object that all of the values of the invocant have in common. This can be either a class or a role.

say (1, 42e0, .137).are;        # (Real)
say (1, 42e0, .137, "foo").are; # (Cool)
say (42, DateTime.now).are;     # (Any)

In some languages this functionality appears to be called infer, but this name was deemed to be too ComputerSciency for Raku.

IO::Path.inode|dev|devtype|created|chown

Some low level IO features were added to the IO::Path class, in the form of 5 new methods. Note that they may not actually work on your OS and/or filesystem. Looking at you there, Windows 🙂

(Date|DateTime).days-in-year

The Date and DateTime classes already provide many powerfule date and time manipulation features. But a few features were considered missing this year, and so they were added.

A new .days-in-year class method was added to the Date and DateTime classes. It takes a year as positional argument:

say Date.days-in-year(2023);  # 365
say Date.days-in-year(2024);  # 366

This behaviour was also expanded to the .days-in-month method, when called as a class method:

say Date.days-in-month(2023, 2);  # 28
say Date.days-in-month(2024, 2);  # 29

They can also be called as instance methods, in which case the parameters default to the associated values in the object:

given Date.today {
    .say;                # 2022-12-25
    say .days-in-year;   # 365
    say .days-in-month;  # 31
}

New Dynamic Variables

Dynamic variables provide a very powerful way to keep “global” variables. A number of them are provided by the Raku Programming Language. And now there is one more of them!

$*RAT-OVERFLOW

Determine the behaviour of rational numbers (aka Rats) if they run out of precision. More specifically when the denominator no longer fits in a native 64-bit integer. By default, Rats will be downgraded to floating point values (aka Nums). By setting the $*RAT-OVERFLOW dynamic variable, you can influence this behaviour.

The $*RAT-OVERFLOW dynamic variable is expected to contain a class (or an object) on which an UPGRADE-RAT method will be called. This method is expected to take the numerator and denominator as positional arguments, and is expected to return whatever representation one wants for the given arguments.

The following type objects can be specified using core features:

Num

Default. Silently convert to floating point. Sacrifies precision for speed.

CX::Warn

Downgrade to floating point, but issue a warning. Sacrifies precision for speed.

FatRat

Silently upgrade to FatRat, aka rational numbers with arbitrary precision. Sacrifies speed by conserving precision.

Failure

Return an appropriate Failure object, rather than doing a conversion. This will most likely throw an exception unless specifically handled.

Exception

Throw an appropriate exception.

Note that you can introduce any custom behaviour by creating a class with an UPGRADE-RAT method in it, and setting that class in the $*RAT-OVERFLOW dynamic variable.

class Meh {
    method UPGRADE-RAT($num, $denom) is hidden-from-backtrace {
        die "$num / $denom is meh"
    }
}
my $*RAT-OVERFLOW = Meh;
my $a = 1 / 0xffffffffffffffff;
say $a;     # 0.000000000000000000054
say $a / 2; # 1 / 36893488147419103230 is meh

Note that the is hidden-from-backtrace is only added so that any backtrace will show the location of where the offending calculation was done, rather than inside the UPGRADE-RAT method itself.

New Environment Variables

Quite a few environment variables are already checked by Rakudo whenever it starts. Two more were added in the past year:

RAKUDO_MAX_THREADS

This environment variable can be set to indicate the maximum number of OS-threads that Rakudo may use for its thread pool. The default is 64, or the number of CPU-cores times 8, whichever is larger. Apart from a numerical value, you can also specify "Inf” or "unlimited" to indicate that Rakudo should use as many OS-threads as it can.

These same values can also be used in a call to ThreadPoolScheduler.new with the :max_threads named argument.

my $*SCHEDULER =
  ThreadPoolScheduler.new(:max_threads<unlimited>);

INSIDE_EMACS

This environment variable can be set to a true value if you do not want the REPL to check for installed modules to handle editing of lines. When set, it will fallback to the behaviour as if none of the supported line editing modules are installed. This appears to be handy for Emacs users, as the name implies 🙂

New experimental features

Some Raku features are not yet cast in stone yet, so there’s no guarantee that any code written by using these experimental features, will continue to work in the future. Two new experimental features have been added in the past year:

:will-complain

If you add a use experimental :will-complain to your code, you can customize typecheck errors by specifying a will complain trait. The trait expects a Callable that will be given the offending value in question, and is expected to return a string to be added to the error message. For example:

use experimental :will-complain;
my Int $a will complain { "You cannot use -$_-, dummy!" }
$a = "foo";
# Type check failed in assignment to $a; You cannot use -foo-, dummy!

The will complain trait can be used anywhere you can specify a type constraint in Raku, so that includes parameters and attributes.

:rakuast

The RakuAST classes allow you to dynamically build an AST (Abstract Syntax Tree programmatically, and have that converted to executable code. What was previously only possible by programmatically creating a piece of Raku source code (with all of its escaping issues), and then calling EVAL on it. But RakuAST not only allows you to build code programmatically (as seen in yesterday’s blog post), it also allows you to introspect the AST, which opens up all sorts of syntax / lintifying possibilities.

There is an associated effort to compile the Raku core itself using a grammar that uses RakuAST to build executable code. This effort is now capable of passing 585/1355 test-files in roast completely, and 83/131 of the Rakudo test-files completely. So still a lot of work to do, although it has now gotten to the point that implementation of a single Raku feature in the new grammar, often creates an avalanche of now passing test-files.

So, if you add a use experimental :rakuast to your code, you will be able to use all of the currently available RakuAST classes to build code programmatically. This is an entire new area of Raku development, which will be covered by many blog posts in the coming year. As of now, there is only some internal documentation.

A small example, showing how to build the expression "foo" ~ "bar":

use experimental :rakuast;

my $left  = RakuAST::StrLiteral.new("foo");
my $infix = RakuAST::Infix.new("~");
my $right = RakuAST::StrLiteral.new("bar");

my $ast = RakuAST::ApplyInfix.new(:$left, :$infix, :$right);
dd $ast;  # "foo" ~ "bar"

This is very verbose, agreed. Syntactic sugar for making this easier will certainly be developed, either in core or in module space.

Note how each element of the expression can be created separately, and then combined together. And that you can call dd to show the associated Raku source code (handy when debugging your ASTs).

For the very curious, you can check out a proof-of-concept of the use of RakuAST classes in the Rakudo core in the Formatter class, that builds executable code out of an sprintf format.

New arguments to existing functionality

roundrobin(…, :slip)

The roundrobin subroutine now also accepts a :slip named argument. When specified, it will produce all values as a single, flattened list.

say roundrobin (1,2,3), <a b c>;        # ((1 a) (2 b) (3 c))
say roundrobin (1,2,3), <a b c>, :slip; # (1 a 2 b 3 c)

This is functionally equivalent to:

say roundrobin((1,2,3), <a b c>).map: *.Slip;

but many times more efficient.

Cool.chomp($needle)

The .chomp method by default any logical newline from the end of a string. It is now possible to specify a specific needle as a positional argument: only when that is equal to the end of the string, will it be removed.

say "foobar".chomp("foo"); # foobar
say "foobar".chomp("bar"); # foo

It actually works on all Cool values, but the return value will always be a string:

say 427.chomp(7); # 42

DateTime.posix

DateTime value has better than millisecond precision. Yet, the .posix method always returned an integer value. Now it can also return a Num with the fractional part of the second by specifying the :real named argument.

given DateTime.now {
    say .posix;        # 1671733988
    say .posix(:real); # 1671733988.4723697
}

Additional meaning to existing arguments

Day from end of month

The day parameter to Date.new and DateTime.new (whether named or positional) can now be specified as either a Whatever to indicate the last day of the month, or as a Callable indicating number of days from the end of the month.

say Date.new(2022,12,*);   # 2022-12-31
say Date.new(2022,12,*-6); # 2022-12-25

Additions in v6.e.PREVIEW

You can already access new v6.e language features by specifying use v6.e.PREVIEW at the top of your compilation unit. Several additions were made the past year!

term nano

nano term is now available. It returns the number of nanoseconds since midnight UTC on 1 January 1970. It is similar to the time term but one billion times more accurate. It is intended for very accurate timekeeping / logging.

use v6.e.PREVIEW;
say time; # 1671801948
say nano; # 1671801948827918628

With current 64-bit native unsigned integer precision, this should roughly be enough for another 700 years 🙂

prefix //

You can now use // as a prefix as well as an infix. It will return whatever the .defined method returns on the given argument).

use v6.e PREVIEW;
my $foo;
say //$foo; # False
$foo = 42;
say //$foo; # True

Basically //$foo is syntactic sugar for $foo.defined.

snip() and Any.snip

The new snip subroutine and method allows one to cut up a list into sublists according the given specification. The specification consists of one or more smartmatch targets. Each value of the list will be smartmatched with the given target: as soon as it returns False, will all the values before that be produced as a List.

use v6.e.PREVIEW;
say (2,5,13,9,6,20).snip(* < 10);
# ((2 5) (13 9 6 20))

Multiple targets can also be specified.

say (2,5,13,9,6,20).snip(* < 10, * < 20);
# ((2 5) (13 9 6) (20))

The argument can also be an Iterable. To split a list consisting of integers and strings into sublists of just integers and just strings, you can do:

say (2,"a","b",5,8,"c").snip(|(Int,Str) xx *);
# ((2) (a b) (5 8) (c))

Inspired by Haskell’s span function.

Any.snitch

The new .snitch method is a debugging tool that will show its invocant with note by default, and return the invocant. So you can insert a .snitch in a sequence of method calls and see what’s happening “half-way” as it were.

$ raku -e 'use v6.e.PREVIEW;\
say (^10).snitch.map(* + 1).snitch.map(* * 2)'
^10
(1 2 3 4 5 6 7 8 9 10)
(2 4 6 8 10 12 14 16 18 20)

You can also insert your own “reporter” in there: the .snitch method takes a Callable. An easy example of this, is using dd for snitching:

$ raku -e 'use v6.e.PREVIEW;\
say (^10).snitch(&dd).map(*+1).snitch(&dd).map(* * 2)'
^10
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).Seq
(2 4 6 8 10 12 14 16 18 20)

Any.skip(produce,skip,…)

You can now specify more than one argument to the .skip method. Before, you could only specify a single (optional) argument.

my @a = <a b c d e f g h i j>;
say @a.skip;       # (b c d e f g h i j)
say @a.skip(3);    # (d e f g h i j)
say @a.skip(*-3);  # (h i j)

On v6.e.PREVIEW, you can now specify any number of arguments in the order: produce, skip, produce, etc. Some examples:

use v6.e.PREVIEW;
my @a = <a b c d e f g h i j>;
# produce 2, skip 5, produce rest
say @a.skip(2, 5);        # (a b h i j)
# produce 0, skip 3, then produce 2, skip rest
say @a.skip(0, 3, 2);     # (d e)
# same, but be explicit about skipping rest
say @a.skip(0, 3, 2, *);  # (d e)

In fact, any Iterable can now be specified as the argument to .skip.

my @b = 3,5;
# produce 3, skip 5, then produce rest
say @a.skip(@b);           # (a b c i j)
# produce 1, then skip 2, repeatedly until the end
say @a.skip(|(1,2) xx *);  # (a d g j)

Cool.comb(Pair)

On v6.e.PREVIEW, the .comb method will also accept a Pair as an argument to give it .rotor_-like capabilities. For instance, to produce trigrams of a string, one can now do:

use v6.e.PREVIEW;
say "foobar".comb(3 => -2);  # (foo oob oba bar)

This is the functional equivalent of "foobar".comb.rotor(3 => -2)>>.join, but about 10x as fast.

Changed semantics on Int.roll|pick

To pick a number from 0 till N-1, one no longer has to specify a range, but can use just the integer value as the invocant:

use v6.e.PREVIEW;
say (^10).roll;     # 5
say 10.roll;        # 7
say (^10).pick(*);  # (2 0 6 9 4 1 5 7 8 3)
say 10.pick(*);     # (4 6 1 0 2 9 8 3 5 7)

Of course, all of these values are examples, as each run will, most likely, produce different results.

More interesting stuff

There were some more new things and changes the past year. I’ll just mention them very succinctly here:

New methods on CompUnit::Repository::Staging

.deploy.remove-artifacts, and .self-destruct.

:!precompile flag on CompUnit::Repository::Installation.install

Install module but precompile on first loading rather than at installation.

New methods on Label

.file and .line where the Label was created.

.Failure coercer

Convert a Cool object or an Exception to a Failure. Mainly intended to reduce binary size of hot paths that do some error checking.

Cool.Order coercer

Coerce the given value to an Int, then convert to Less if less than 0, to Same if 0, and More if more than 0.

Allow semi-colon

Now allow for the semi-colon in my :($a,$b) = 42,666 because the left-hand side is really a Signature rather than a List.

Summary

I guess we’ve seen one big change in the past year, namely having experimental support for RakuAST become available. And many smaller goodies and tweaks and features.

Now that RakuAST has become “mainstream” as it were, we can think of having certain optimizations. Such as making sprintf with a fixed format string about 30x as fast! Exciting times ahead!

Hopefully you will all be able to enjoy the Holiday Season with sufficient R&R. The next Raku Advent Blog is only 340 days away!

p6steve: On Sigils

Published by librasteve on 2022-12-24T12:30:44

This post was inspired by @codesections recent posts on sigils, particularly the notion of coding as a trialog between the writer, the reader and the machine.

@codesections already did a great job of reflecting the wider societal uptake of eg. #hashtags and @names as examples of sigils in the wild.

I aim to show sigils in action with some simple examples in the raku programming language.

A sigil, for this purpose, is the use of a single non-word character – usually a dollar sign $ – to distinguish a variable name from other words in the code such as operators and functions.

Disclosure: I learned to program with C and Perl and I use Linux as my OS with the Bash shell and I code in raku practically every day.

On dollar $ – ease of use

Here’s some Python:

language = "Python"
print("I like coding in " + language + " the most.")

#I like coding in Python the most.

The sentence has been broken into literals with ” quote marks and then concatenated with the variable with the ‘+’ operator.

And here’s some Raku:

my $language = "Raku";
say "I like coding in $language the most."

#I like coding in Raku the most.

Here, the sigil identifies the variable and interpolates it into the output. It eliminates several extra quote marks and concatenation operators. It cuts out unwanted “line noise”.

On dollar $ – linguistics

We are dealing with coding languages. As with natural languages, syntax is a key marker that triggers cognitive mechanisms learned since childhood. While the base cultural setting for most of this is English, most human languages carry the notions of noun, verb, adjective and so on.

Here’s some English:


Jack and Jill went up the hill 
To fetch a pail of water 
Jack fell down and broke his crown 
And Jill came tumbling after

The proper names begin with Capital letters.

And here’s some Raku:

my ($boy, $girl) = <Jack Jill>;

say qq:to/END/;

$boy and $girl went up the hill 
To fetch a pail of water 
$boy fell down and broke his crown 
And $girl came tumbling after

END

See how the $variables catch the eye? Rather like the Capitals we are used to – and proper nouns are similarly interchangeable since it could have been Alice and Bob.

On dollar $ – practicalities

In the first place, sigils emerged from a long line of coding tools as a practical technique. For example, the dollar sign $ shows up as a sigil on Linux shell and environment variables, here in a simple Bash example:

#!/bin/bash
for (( n=2; n<=10; n++ ))
do
echo "$n seconds"
done
https://www.hostinger.co.uk/tutorials/bash-script-example

C pointers (with ‘*’ prefix) and references (with ‘&’ prefix) take a similar looking approach that tells the compiler what we want and the coder what we have:

int i = 3; 

// A pointer to variable i or "stores the address of i"
int *ptr = &i; 

// A reference (or alias) for i.
int &ref = i; 
https://www.geeksforgeeks.org/pointers-vs-references-cpp/

The $ sigil line continues through web-based interpolation in various guises (with eg. PHP and Ruby) and fairly recently in the SCSS variant of CSS:

$font-stack: Helvetica, sans-serif;
$primary-color: #333;

body {
  font: 100% $font-stack;
  color: $primary-color;
}
https://sass-lang.com/guide

So, it’s tempting to stop here with the $ dollar sigil – it is easy, natural and practical.

Author’s note: Not all coders see the benefits. Sometimes IDE tools provide an alternative to sigil characters with colour coding (personally, I don’t find multi-colour text very helpful). Many find noisy sigil symbols a distraction from the code. It boils down to choice.

Nevertheless, I think it is fair to say that the humble dollar $ sigil has found a solid use case in many situations among a large body of coders with that shared heritage and mindset.

Let’s say you buy the $ dollar sigil as a useful tool? If so, raku has thoughtfully extended the technique for a few more substantial purposes.

On at @ – plurality

Joe Mabel, CC BY-SA 3.0 http://creativecommons.org/licenses/by-sa/3.0/, via Wikimedia Commons

Here is my collection of 10 marbles. Is it one thing or 10 things?

In raku you can use either the dollar $ sigil or the at @ sigil to help:

my $marbles = 1..10;       # "one thing"
my @marbles = 1..10;       # "10 things"

The at symbol @ is used to remind us that this is an Array.

We can use dd (data dumper) to show what is going on. The ‘\’ makes the argument ‘x’ sigilless so that our function is studiously neutral:

sub got_what( \x ) { 
    dd x               # data dumper
}

got_what $marbles;     
    #Range $marbles = 1..10

got_what @marbles;     
    #Array @marbles = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

An iterator, such as the for operator, will take the desired plurality into account:

sub for_what( \x ) {
    for x -> \item { dd item } 
}

for_what $marbles;           #one thing => 
    #Range $marbles = 1..10

for_what @marbles;           #10 things =>
    #Int @marbles = 1
    #Int @marbles = 2
    #Int @marbles = 3
    #Int @marbles = 4
    #Int @marbles = 5
    #Int @marbles = 6
    #Int @marbles = 7
    #Int @marbles = 8
    #Int @marbles = 9
    #Int @marbles = 10

On at @ – ease of use

So, what happens when you go back and forth? Let’s apply a sigil to the parameter declaration $x in the subroutine signature:

sub for_doll( $x ) {
    for $x -> \item { dd item }
}           
for_doll @marbles;          #one thing =>
    # $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Or just do an assignment:

my $scalar = @marbles;
dd $scalar;                 #one thing =>
    #Array $scalar = $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

That’s an Array wrapped up in a Scalar container (thus the leading $). This process is know as itemizing, since it makes many things into a single item.

Or we can go the the other way:

sub for_amper( @x ) {
    for @x -> \item { dd item }
}
for_amper $marbles;         #ten things =>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

And with assignment? Well, not quite so easy. The compiler needs to know (i) should I make and Array of Arrays with $marbles as the first element, or (ii) should I assign each individual element one by one. Here, the programmer must use the pipe ‘|’ symbol if she wishes to flatten the right hand side.

my @array = |$marbles;
dd @array;
    #Array @array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

On at @ – the Single Argument Rule

Now, once up a time in raku-land, it became clear that coders could easily mix up their intentions sometimes passing one argument to an iterator, sometimes many. So, to keep things simple and memorable, the community developed the Single Argument Rule.

The documents say this:

It is the rule by which the set of parameters passed to an iterator such as for is treated as a single argument, instead of several arguments…

Since what for receives is a single argument, it will be treated as a list of elements to iterate over. The rule of thumb is that if there’s a comma, anything preceding it is an element and the list thus created becomes the single element. That happens in the case of the two arrays separated by a comma which is the third element in the Array we are iterating in this example. In general, quoting the article linked above, the single argument rule … makes for behavior as the programmer would expect.

This rule is equivalent to saying that arguments to iterators will not flatten, will not de-containerize, and will behave as if a single argument has been handled to them, whatever the shape that argument has.

my @a = 1,2; .say for @a, |@a;     # OUTPUT: «[1 2]␤1␤2␤» 
my @a = 1,2; .say for $[@a, |@a ]; # OUTPUT: «[[1 2] 1 2]␤» 

In the second case, the single argument is a single element, since we have itemized the array. There’s an exception to the single argument rule mentioned in the Synopsis: list or arrays with a single element will be flattened:

my @a = 1,2; .say for [[@a ]];     # OUTPUT: «1␤2␤» 

Authors note: raku is often making new containers and populating them behind the scenes with argument passing, assignment and so on. This exception automates the unwrapping of nested single elements to simply “do what I mean”.

The documents also say some other stuff that personally I find a bit confusing.

I will wrap up this section with two bits of friendly raku advice:

And the rest – percent % and ampersand &

Raku coders also get two more variants to play with, here’s how the four fit together.

SigilAssumptive RoleDefault TypeAssignmentExamples
$Mu (no type)AnyitemInt, Str, Array, Hash
@PositionalArray []listList, Array, Range, Buf
%AssociativeHash {} <>listHash, Map, Pair
&CallableCallableitemSub, Method, Block, Routine
https://docs.raku.org/language/variables

This set of four, along with the sigilless option, provides a rich set of tools to communicate the intent of the coder in the trialog.

I hope that you have enjoyed reading this post as much as I enjoyed writing it. To paraphrase Richard Feynman, to understand a topic properly, you need to blog about it.

As usual, comments and feedback welcome!

~p6steve

Raku Advent Calendar: Day 24: He’s making a list… (part 2)

Published by Matthew Stephen Stuckwisch on 2022-12-24T00:00:00

In our last edition, we learned about some of the work that Santa’s elves put into automating how they make their lists. What you probably didn’t know is that the elves stay on top of the latest and greatest technology. Being well-known avid Raku programmers, the elves were excited to hear about RakuAST and decided to see how they might be able to use it. One of the elves decided to rework the list formatting code to use RakuAST. What follows is the story of how she upgraded their current technology to use RakuAST.

Background

The current code that the elves had is fairly straight forward (check out part one for a full explanation)

sub format-list(
  [email protected],
  :$language 'en',
  :$type = 'and',
  :$length = 'standard'
) {
    state %formatters;
    my $code = "$language/$type/$length";
 	 
    # Get a formatter, generate if it's not been requested before
    my &formatter = %cache{$code} // %cache{$code} =
      generate-list-formatter($language, $type, $length);
 	 
    formatter @items;
}
 	 
sub generate-list-formatter($language, $type, $length --> Sub ) {
    # Get CLDR information
    my $format = cldr{$language}.list-format{$type}{$length};
    my ($start, $middle, $end, $two) =
      $format<start middle end two>.map: *.substr(3,*-3).raku;
 	 
    # Generate code
    my $code = q:s:to/FORMATCODE/;
        sub format-list([email protected]) {
            if @items > 2 {
                @items[0]
                  ~ $start
                  ~ @items[1..*-2].join($middle)
                  ~ $end
                  ~ @items[*-1]
            }
            elsif @items == 2 {
                @items[0] ~ $two ~ @items[1]
            }
            elsif @items == 1 {
                @items[0]
            }
            else {
                ''
            }
        }
    FORMATCODE
 	 
    # compile and return
    use MONKEY-SEE-NO-EVAL;
    EVAL $code
}

While the caching technique is rudimentary and technically not thread-safe, it works (a different elf will probably revisit the code to make it so). Now, when creating all the lists for, say, children in Georgia, the data for Georgian list formatters in CLDR will only need to be accessed a single time. For the next half a million or so calls, the code will be run practically as fast as if it had been hard coded (since, in effect, it has been).

The problem is how the generate-list-formatter code works. The code block uses a heredoc-style :to string, but it’s interpolated. There are numerous ways to accomplish this but all of them require having to use proper escapes. That’s…. risky.

Another elf, having seen the performance improvements that this new EVAL code brought, wanted to find a way to avoid the risky string evaluation. She had heard about the new RakuAST and decided to give it a whirl. While it initially looked more daunting, she quickly realized that RakuAST was very powerful.

What is RakuAST

RakuAST is an object-based representation of Raku’s abstract syntax tree, or roughly what you might get if you parsed Raku’s code into its individual elements. For instance, a string literal might be represented as 'foo' in code, but once parsed, becomes a string literal. That string literal, by the way, can be created by using RakuAST::StrLiteral.new(…). Remember how the elf had to worry about how the string might be interpolated? By creating a the string literal directly via a RakuAST node, that whole process is safely bypassed. No RakuAST::StrLiteral node can be created that will result in a string injection!

Every single construct in the Raku language has an associated RakuAST node. When creating nodes, you might frequently pass in another node, which means you can build up code objects in a piece-by-piece fashion, and again, without ever worrying about string interpolation, escaping, or injection attacks.

So let’s see how the elf eventually created the safer RakuAST version of the formatter method.

The elf works her AST off

To ease her transition into RakuAST, the elf decided to go from the simplest to the most complex part of the code. The simplest is the value for the final else block:

my $none = RakuAST::StrLiteral.new(''); 

Okay. That was easy. Now she wanted to tackle the single element value. In the original code, that was @list.head. Although we don’t normally think of it as such, . is a special infix for method calling. Operators can be used creating an RakuAST::Apply___fix node, where ___ is the type of operator. Depending on the node, there are different arguments. In the case of RakuAST::ApplyPostfix, the arguments are operand (the list), and postfix which is the actual operator. These aren’t as simple as typing in some plain text, but when looking at the code the elf came up with, it’s quite clear what’s going on:

my $operand = RakuAST::Var::Lexical.new('@list');
my $postfix = RakuAST::Call::Method.new(
  name => RakuAST::Name.from-identifier('head')
);
my $one = RakuAST::ApplyPostfix.new(:$operand, :$postfix) 

The operand isn’t a literal, but a variable. Specifically, it’s a lexical variable, so we create a node that will reference it. The call method operator needs a name as well, so we do that as well.

This involves a lot of assignment statements. Sometimes that can be helpful, but for something this simple, the elf decided it was easier to write it as one “line”:

my $one = RakuAST::ApplyPostfix.new(
  operand => RakuAST::Var::Lexical.new('@list'),
  postfix => RakuAST::Call::Method.new(
    name => RakuAST::Name.from-identifier('head')
  )
);

Alright, so the first two cases are done. How might she create the result for when the list has two items? Almost exactly like the last time, except now she’d provide an argument. While you might think it would be as simple as adding args => RakuAST::StrLiteral($two-infix), it’s actually a tiny bit more complicated because in Raku, argument lists are handled somewhat specially, so we actually need a RakuAST::ArgList node. So the equivalent of @list.join($two-infix) is

my $two = RakuAST::ApplyPostfix.new(
  operand => RakuAST::Var::Lexical.new('@list'),
  postfix => RakuAST::Call::Method.new(
    name => RakuAST::Name.from-identifier('join'),
    args => RakuAST::ArgList.new(
      RakuAST::StrLiteral.new($two-infix)
    )
  )
); 	 

The RakuAST::ArgList takes in a list of arguments — be they positional or named (named applied by way of a RakuAST::FatComma).

Finally, the elf decided to tackle what likely would be the most complicated bit: the code for 3 or more items. This code makes multiple method calls (including a chained one), as well as combining everything with a chained infix operator.

The method calls were fairly straightforward, but she thought about what the multiple ~ operators would be handled. As it turns out, it would actually require being set up as if (($a ~ $b) ~ $c) ~ $d, etc., and the elf didn’t really like the idea of having ultimately intending her code that much. She also thought about just using join on a list that she could make, but she already knew how to do method calls, so she thought she’d try something cool: reduction operators (think [~] $a, $b, $c, $d for the previous). This uses the RakuAST::Term::Reduce node that takes a simple list of arguments. For the * - 2 syntax, to avoid getting too crazy, she treated it as if it had been written as the functionally identical @list - 2.

Becaused that reduction bit has some many elements, she ending up breaking things into pieces: the initial item, the special first infix, a merged set of the second to penultimate items joined with the common infix, the special final infix, and the final item. For a list like [1,2,3,4,5] in English, that amounts to 1 (initial item), , (first infix), 2, 3, 4 (second to penultimate, joined with , ), , and (final infix) and 5 (final item). In other languages, the first and repeated infixes may be different, and in others, all three may be identical.

# @list.head
my $more-first-item = RakuAST::ApplyPostfix.new(
  operand => RakuAST::Var::Lexical.new('@list'),
  postfix => RakuAST::Call::Method.new(
    name => RakuAST::Name.from-identifier('head')
  )
);

# @list[1, * - 2].join($more-middle-infix)
my $more-mid-items = RakuAST::ApplyPostfix.new(
  # @list[1, @list - 2
  operand => RakuAST::ApplyPostfix.new(
    operand => RakuAST::Var::Lexical.new('@list'),
    postfix => RakuAST::Postcircumfix::ArrayIndex.new(
      # (1 .. @list - 2)
      RakuAST::SemiList.new(
        RakuAST::ApplyInfix.new(
          left => RakuAST::IntLiteral.new(1),
          infix => RakuAST::Infix.new('..'),
          # @list - 2
          right => RakuAST::ApplyInfix.new(
            left => RakuAST::Var::Lexical.new('@list'),
            infix => RakuAST::Infix.new('-'),
            right => RakuAST::IntLiteral.new(2)
          )
        )
      )
    )
  ),
  # .join($more-middle-infix)
  postfix => RakuAST::Call::Method.new(
    name => RakuAST::Name.from-identifier('join'),
    args => RakuAST::ArgList.new(
      RakuAST::StrLiteral.new($more-middle-infix)
    )
  )
);
 
# @list.tail
my $more-final-item = RakuAST::ApplyPostfix.new(
  operand => RakuAST::Var::Lexical.new('@list'),
  postfix => RakuAST::Call::Method.new(
    name => RakuAST::Name.from-identifier('tail')
  )
);
 	 
# [~] ...
my $more = RakuAST::Term::Reduce.new(
  infix => RakuAST::Infix.new('~'),
  args => RakuAST::ArgList.new(
    $more-first-item,
    RakuAST::StrLiteral.new($more-first-infix),
    $more-mid-items,
    RakuAST::StrLiteral.new($more-final-infix),
    $more-final-item,
  )
);

As one can note, as RakuAST code starts getting more complex, it can be extremely helpful to store interim pieces into variables. For complex programs, some RakuAST users will create functions that do some of the verbose stuff for them. For instance, one might get tired of the code for an infix, and write a sub like

sub rast-infix($left, $infix, $right) {
    RakuAST::ApplyInfix.new:
      left => $left,
      infix => RakuAST::Infix.new($infix),
      right => $right
}

to enable code like rast-infix($value, '+', $value) which ends up being much less bulky. Depending on what they’re doing, they might make a sub just for adding two values, or maybe making a list more compactly.

In any case, the hard working elf had now programmatically defined all of the formatter code. All that was left was for her to piece together the number logic and she’d be done. That logic was, in practice, quite simple:

if @list > 2 { $more }
elsif @list == 2 { $two }
elsif @list == 1 { $one }
else { $none } 

In practice, there was still a bit of a learning curve. Why? As it turns out, the [els]if statements are actually officially expressions, and need to be wrapped up in an expression block. That’s easy enough, she could just use RakuAST::Statement::Expression. Her conditions end up being coded as

# @list > 2
my $more-than-two = RakuAST::Statement::Expression.new(
  expression => RakuAST::ApplyInfix.new(
    left => RakuAST::Var::Lexical.new('@list'),
    infix => RakuAST::Infix.new('>'),
    right => RakuAST::IntLiteral.new(2)
  )
);
 	 
# @list == 2
my $exactly-two = RakuAST::Statement::Expression.new(
  expression => RakuAST::ApplyInfix.new(
    left => RakuAST::Var::Lexical.new('@list'),
    infix => RakuAST::Infix.new('=='),
    right => RakuAST::IntLiteral.new(2)
  )
);
 	 
# @list == 1
my $exactly-one = RakuAST::Statement::Expression.new(
  expression => RakuAST::ApplyInfix.new(
    left => RakuAST::Var::Lexical.new('@list'),
    infix => RakuAST::Infix.new('=='),
    right => RakuAST::IntLiteral.new(1)
  )
);	 

That was simple enough. But now sure realized that the then statements were not just the simple code she had made, but were actually a sort of block! She would need to wrap them with a RakuAST::Block. A block has a required RakuAST::Blockoid element, which in turn has a required RakuAST::Statement::List element, and this in turn will contain a list of statements, the simplest of which is a RakuAST::Statement::Expression that she had already seen. She decided to try out the technique of writing a helper sub to do this:

sub wrap-in-block($expression) {
    RakuAST::Block.new(
      body => RakuAST::Blockoid.new(
        RakuAST::StatementList.new(
          RakuAST::Statement::Expression.new(:$expression)
        )
      )
    )
}
 	 
$more = wrap-in-block $more;
$two  = wrap-in-block $two;
$one  = wrap-in-block $one;
$none = wrap-in-block $none; 

Phew, that was a pretty easy way to handle some otherwise very verbose coding. Who knew Raku hid away so much complex stuff in such simple syntax?! Now that she had both the if and then statements finished, she was ready to finish the full conditional:

my $if = RakuAST::Statement::If.new(
  condition => $more-than-two,
  then => $more,
  elsifs => [
    RakuAST::Statement::Elsif.new(
      condition => $exactly-two,
      then => $two
    ),
    RakuAST::Statement::Elsif.new(
      condition => $exactly-one,
      then => $one
    )
  ],
  else => $none
); 

All that was left was for her to wrap it up into a Routine and she’d be ready to go! She decided to put it into a PointyBlock, since that’s a sort of anonymous function that still takes arguments. Her fully-wrapped code block ended up as:

my $code = RakuAST::PointyBlock.new(
  signature => RakuAST::Signature.new(
    parameters => (
      RakuAST::Parameter.new(
        target => RakuAST::ParameterTarget::Var.new('@list'),
 	slurpy => RakuAST::Parameter::Slurpy::SingleArgument
      ),
    ),
  ),
  body => RakuAST::Blockoid.new(
    RakuAST::StatementList.new(
      RakuAST::Statement::Expression.new(
        expression => $if
      )
    )
  )
); 

Working with RakuAST, she really got a feel for how things worked internally in Raku. It was easy to see that a runnable code block like a pointy block consisted of a signature and a body. That signature had a list of parameters, and the body a list of statements. Seems obvious, but it can be enlightening to see it spread out like she had it.

The final step was for her actually evaluate this (now much safer!) code. For that, nothing changed. In fact, the entire rest of her block was simply

sub generate-list-formatter($language, $type, $length) {
    use Intl::CLDR;
    my $pattern = cldr{$lang}.list-patterns{$type}{$length};
    my $two-infix = $pattern.two.substr: 3, *-3;
    my $more-first-infix = $pattern.start.substr: 3, *-3;
    my $more-middle-infix = $pattern.middle.substr: 3, *-3;
    my $more-final-infix = $pattern.end.substr: 3, *-3;
 	 
    ...
 	 
    use MONKEY-SEE-NO-EVAL;
    EVAL $code
}

Was her code necessarily faster than the older method? Not necessarily. It didn’t require a parse phase, which probably saved a bit, but once compiled, the speed would be the same.

So why would she bother doing all this extra work when some string manipulation could have produced the same result? A number of reasons. To begin, she learned the innards of RakuAST, which helped her learn the innards of Raku a bit better. But for us non-elf programmers, RakuAST is important for many other reasons. For instance, at every stage of this process, everything was fully introspectable! If your mind jumped to writing optimizers, besides being a coding masochist, you’ve actually thought about something that will likely come about.

Macros is another big feature that’s coming in Raku and will rely heavily on RakuAST. Rather than just do text replacement in the code like macros in many other languages, macros will run off of RakuAST nodes. This means an errant quote will never cause problems, and likely enable far more complex macro development. DSL developers can seamlessly integrate with Raku by just compiling down to RakuAST.

The future

So what is the status of RakuAST? When can you use it? As of today, you will need to build the most recent main branch of Rakudo to use it. Then, in your code, include the statement use experimental :rakuast;. Yours truly will be updating a number of his formatting modules to use RakuAST very shortly which will make them far more maintainable and thus easier to add new features. For more updates on the progress of RakuAST, check out the Rakudo Weekly, where Elizabeth Mattijsen gives regular updates on RakuAST and all things Raku.

Raku Advent Calendar: Day 23: Sigils followup: semantics and language design

Published by codesections on 2022-12-23T00:01:00

Until a few days ago, I’d intended for this post to be an update on the Raku persistent data structures I’m developing. And I have included a (very brief) status update at the end of this post. But something more pressing has come to my attention: Someone on the Internet was wrong — and that someone was me.

xkcd_386

Specifically, in my post about sigils the other day, I significantly misdescribed the semantics that Raku applies to sigiled-variables.

Considering that the post was about sigils, the final third focused on Raku’s sigils, and much of that section discussed the semantics of those sigils – being wrong about the semantics of Raku’s sigils isn’t exactly a trivial mistake. Oops!

In partial mitigation, I’ll mention one thing: no one pointed out my incorrect description of the relevant semantics, even though the post generated over two hundred comments of discussion, most of it thoughtful. Now, it could be no one read all the way to Part 3 of a 7,000 word post (an understandable choice!). But, considering the well-known popularity of correcting people on the Internet, I view the lack of any correction as some evidence that my misunderstanding wasn’t obvious to others either. In fact, I only discovered the issue when I decided, while replying to a comment on that post, to write an an oddly-designed Raku class to illustrate the semantics I’d described; much to my suprise, it showed that I’d gotten those semantics wrong.

Clearly, that calls for a followup post, which you’re now reading.

My goal for this post is, first of all, to explain what I got wrong about Raku’s semantics, how I made that error, and why neither I nor anyone else noticed. Then we’ll turn to some broader lessons about language design, both in Raku and in programming languages generally.  Finally, with the benefit of correctly understanding of Raku’s semantics, we’ll reevaluate Raku’s sigils, and the expressive power they provide.

What I got wrong – and what I got right

In that post, I said that the @ sigil can only be used for types that implement the Positional (“array-like”) role; that the % sigil can only be used for types that implement the Associative (“hash-like”) role; and that the & sigil can only be used for types that implement the Callable (“function-like”) role. All of that is right (and pretty much straight from the language docs).

Where I went wrong was when I described the requirements that a type must satisfy in order to implement those roles. I described the Positional role as requiring an iterable, ordered collection that can be indexed positionally (e.g., with @foo[5]); I described the Associative role as requiring an iterable, unordered collection of Pairs that can be indexed associatively (e.g., with %foo<key>); and I described the Callable role as requiring a type to support being called as a function (e.g., with &foo()).

That, however, was an overstatement. The requirements for implementing those three roles are actually: absolutely nothing. That’s right, they’re entirely “marker roles”, the Raku equivalent of Rust’s marker traits.

Oh sure, the Raku docs provide lists of methods that you should implement, but those are just suggestions. There’s absolutely nothing stopping us from writing classes that are Associative, Positional, or Callable, or – why not? – all three if we want to. Or, for that matter, since Raku supports runtime composition, the following is perfectly valid:

  my @pos := 'foo' but Positional;
  my %asc := 90000 but Associative;
  my &cal := False but Callable;

Yep, we can have a Positional string, an Associative number, and a Callable

How did we miss that?

So, here’s the thing: I’ve written quite a bit of Raku code while operating under the mistaken belief that those roles had the type constraints I described – which are quite a bit stricter than “none at all”. And I don’t think I’m alone in that; in fact, the most frequent comment I got on the previous post was surprise/confusion that @ and % weren’t constrained to concrete Arrays and Hashes (a sentiment I’ve heard before). And I don’t think any of us were crazy to think those sorts of things – when you first start out in Raku, the vast majority (maybe all) of the @– and %-sigiled things you see are Arrays and Hashes. And I don’t believe I’ve ever seen an @-sigiled variable in Raku that wasn’t an ordered collection of some sort. So maybe people thinking that the type constraints are stricter makes a certain amount of sense.

But that, in turn, just raises two more questions: First, given the unconstrained nature of those sigils, why haven’t I seen some Positional strings in the wild? After all, relying on programmer discipline instead of tool-enforcement is usually a recipe for quick and painful disaster. And, second, given that @– and %

Good defaults > programmer discipline

Let’s address those questions in order: Why haven’t I seen @-sigiled strings or %-sigiled numbers? Because Raku isn’t relying on programmer discipline to prevent those things; it’s relying on programmer laziness – a much stronger force. Writing my @pos := 'foo' but Positional seems very easy, but it has three different elements that would dissuade a new Rakoon from writing it: the := bind operator (most programmers are more familiar with assignment, and = is overwhelmingly more common in Raku code examples); the but operator (runtime composition is relatively uncommon in the wider programming world, and it’s not a tool Raku code turns to all that often) and Positional (roles in general aren’t really a Raku 101 topic, and Positional/Associative/Callable even less so – after all, all the built-in types that should implement those roles already do so).

Let’s contrast that line with the version that a new Rakoon would be more likely to write – indeed, the version that every Rakoon must have written over and over: my @pos = 'foo'. That removes all three of the syntactic stumbling blocks from the preceding code. More importantly, it works. Because the @-sigil provides a default Array container, that line creates the Array ['foo'] – which is much more likely to be what the user wanted in the first place.

Of course, that’s just one example, but the general pattern holds: Raku very rarely prohibits users from doing something (even something as bone-headed as a Positional string) but it’s simultaneously good at making the default/easiest path one that avoids those issues. If there’s an easy-but-less-rigorous option available, then no amount of “programmer discipline” will prevent everyone from taking it. But when the safer/saner thing is also by far the easier thing, then we’re not relying on programmer discipline. We’re removing the temptation entirely.

And then by the time someone has written enough Raku that :=, but, and Positional wouldn’t give them any pause, they probably have the “@ means “array-like, but maybe not an Array” concept so deeply ingrained that they wouldn’t consider creating a wacky Positional

Being stricter

What about the second question we posed earlier: Why doesn’t Raku enforce a tighter type constraint? It certainly could: Raku has the language machinery to really tighten down the requirements for a role. It would be straightforward to mandate that any type implementing the Positional role must also implement the methods for positional indexing. And, since Raku already has an Iterable role, requiring Positional types to be iterable would also be trivial. So why not?

Well, because – even if the vast majority of Positional types should allow indexing and should be iterable, there will be some that have good reasons not to be. And Raku could turn the “why not?” question around and ask “why?”

Providing guarantees versus communicating intent

All of this brings a question into focus – a question that goes right to the heart of Raku’s design philosophy and is an important one for any language designer to consider.

That question is: Is your language more interested in providing guarantees or in communicating intent

Guarantees are great

When I’m not writing Raku (or long blog posts), the programming language I spend the most time with is Rust. And Rust is very firmly on the providing guarantees side of that issue. And it’s genuinely great. There’s something just absolutely incredible and freeing about having the Rust compiler and a strong static type system at your back, of knowing that you just absolutely, 100% don’t need to worry about certain categories of bugs or errors. With that guarantee, you can drop those considerations from your mental cache altogether (you know, to free up space for the things that are cognitively complex in Rust – which isn’t a tiny list). So, yes, I saw the appeal when primarily writing Rust and I see it again every time I return to the language.

Indeed, I think Rust’s guarantees are 100% the right choice – for Rust. I believe that the strength of those guarantees was a great fit for Rust’s original use case (working on Firefox) and are a huge part of why Facebook, Microsoft, Amazon, and Google have all embraced Rust: when you’re collaborating on a team with the scope of a huge open-source project or a big tech company, guarantees become even more valuable. When some people leave, new ones join, and there’s no longer a way to get everyone on the same page, it’s great to have a language that says “you don’t have to trust their code, just trust me”.

But the thing about guarantees is that they have to be absolute. If something is “90% guaranteed”, then it’s not

Coding as a collaborative, asynchronous communication

Guarantees-versus-communication is one trade off where Raku makes the other choice, in a big way. Raku is vastly more interested in helping programmers to communicate their intent than in enforcing rules strictly enough to make guarantees. If Rust’s fundamental metaphor for code is the deductive proof – each step depends on the correctness of the previous ones, so we’d better be as sure as possible that they’re right – Raku’s fundamental metaphor is, unsurprisingly, more linguistic. Raku’s metaphor for coding is an asynchronous conversation between friends: an email exchange, maybe, or — better yet – a series of letters.

How is writing code like emailing a friend? Well, we talked last time about the three-way conversation between author, reader, and compiler, but that’s a bit of a simplification. Most of the time, we’re simultaneously reading previously-written code and writing additional code, which turns the three-way conversation into a four-way one. True, the “previous author”, “current reader/author”, and “future reader” might all be you, but the fact that you’re talking to yourself doesn’t make it any less of a conversation: either way, the goal is to understand the previous author’s meaning as well as possible, decide what you want to add to the conversation, and then express yourself as clearly as possible – subject to the constraint that the compiler also needs to understand your code.

A few words on that last point. From inside a code-as-proof metaphor, a strict compiler is a clear win. Being confident in the correctness of anything is hard enough, but it’s vastly harder as you increase the possibility space. But from a code-as-communication metaphor, there’s a real drawback to compilers (or formatters) that limit your ability to say the same thing in multiple ways. What shirt you wear stops being an expressive choice if you’re required to wear a uniform. In the same way, when there’s exactly one way to do something, then doing it that way doesn’t communicate anything. But when there’s more than one way to do it, then suddenly it makes sense to ask, “Okay, but why did they do it that way?”. This is deeply evident in Raku: there are multiple ways to write code that does the same thing, but those different ways don’t say the same thing – they allow you to place the emphasis in different points, depending on where you’d like to draw the reader’s attention. Raku’s large “vocabulary” plays the same role as increasing your vocabulary in a natural language: it makes it easier to pick just the right word.

When code is communication, rules become suggestions

When emailing a friend, neither of you can set “rules” that the other person must follow. You can make an argument for why they shouldn’t do something, you can express clearly and unequivocally that doing that would be a mistake, but you can’t stop them. You are friends – equals – and neither the email’s author nor its reader can overrule the other.

And the same is true of Raku: Raku makes it very difficult (frequently impossible) for the author of some code to 100% prevent someone from using their code in a particular way. Raku provides many ways to express – with all the intensity of an ALL CAPS EMAIL – that doing something is a really, really bad idea. But if you are determined to misuse code and knowledgeable enough, there’s pretty much no stopping you.

Coming from Rust, this took me a while to notice, because (at least in intro materials) Raku presents certain things as absolute rules (“private attributes cannot be accessed outside the class!”) when, in reality, they turn out to be strongly worded suggestions (”…unless you’re messing with the Meta Object Protocol in ways that you really shouldn’t”). From a Rust perspective, that just wouldn’t fly – private implementations should be private, But it fits perfectly with Raku’s overall design philosophy.

Communicating through sigils

Applying this design philosophy to sigils, I’ve come around to believing that making Possitional, Associative, and Callable marker roles was entirely the correct choice. After all, marker roles are entirely about communicating through code – even in Rust, the entire purpose of marker traits is to communicate some property that the Rust compiler can’t verify.

This is a perfect fit for sigils. What does @ mean? It means that the variable is Positional. Okay, what does Positional mean? It means “array-like”… Okay. What does “array-like” mean? Well, that’s up to you to decide, as part of the collaborative dialogue (trialogue?) with the past and future authors.

That doesn’t mean you’re on your own, crafting meaning from the void: Raku keeps us on the same general page by ensuring that every Rakoon has extensive experience with Arrays, which creates a shared understanding for what “array-like” means. And the language documentation provides clear explanations of how to make your custom types behave like Raku’s Array. But – as I now realize – Raku isn’t going to stomp its foot and say that @-sigiled variables must behave a particular way. If it makes sense – in your code base, in the context of your multilateral conversation – to have an @-sigiled variable that is neither ordered nor iterable, then you can.

So, I’m disappointed that I was mistaken about Raku’s syntax when I wrote my previous post. And I’m especially sorry if anyone was confused by the uncorrected version of that post. But I’m really glad to realize Raku’s actual semantics for sigils, because it fits perfectly with Raku as a whole.  Moreover, these semantics not only fit better with Raku’s design, they make Raku’s sigil’s even more better-suited for their primary purpose: helping someone writing code to clearly and concisely communicate their intent to someone reading that code

In keeping with my earlier post, I’ll include a table with the semantics of the three sigils we discussed:

Sigil Meaning
@ Someone intentionally marked the variable Positional
% Someone intentionally marked the variable Associative
& Someone intentionally marked the variable Callable

These semantics are perfect because, in the end, that’s what @, %, &, and $ really are: signs of what someone else intended. Little, semantically dense, magic signs.

Raku Advent Calendar: Day 22: He’s making a list… (part 1)

Published by Matthew Stephen Stuckwisch on 2022-12-22T00:00:00

If there’s anything that Santa and his elves ought to know, it’s how to make a list. After all, they’re reading lists that children send in, and Santa maintains his very famous list. Another thing we know is that Santa and his elves are quite multilingual.

So one day one of the elfs decided that, rather than hand typing out a list of gifts based on the data they received (requiring elves that spoke all the world’s languages), they’d take advantage of the power of Unicode’s CLDR (Common Linguistic Data Repository). This is Unicode’s lesser-known project. As luck would have it, Raku has a module providing access to the data, called Intl::CLDR. One elf decided that he could probably use some of the data in it to automate their list formatting.

He began by installing Intl::CLDR and played around with it in the terminal. The module was designed to allow some degree of exploration in a REPL, so the elf did the following after reading the provided read me:

# Repl response
use Intl::CLDR; # Nil
my $english = cldr<en> # [CLDR::Language: characters,context-transforms,
# dates,delimiters,grammar,layout,list-patterns,
# locale-display-names,numbers,posix,units]

The module loaded up the data for English and the object returned had a neat gist that provides information about the elements it contains. For a variety of reasons, Intl::CLDR objects can be referenced either as attributes or as keys. Most of the time, the attribute reference is faster in performance, but the key reference is more flexible (because let’s be honest, $english{$foo} looks nicer than $english."$foo"(), and it also enables listy assignment via e.g. $english<grammar numbers>).

In any case, the elf saw that one of the data points is list-patterns, so he explored further:

# Repl response
$english.list-patterns; # [CLDR::ListPatterns: and,or,unit]
$english.list-patterns.and; # [CLDR::ListPattern: narrow,short,standard]
$english.list-patterns.standard; # [CLDR::ListPatternWidth: end,middle,start,two]
$english.list-patterns.standard.start; # {0}, {1}
$english.list-patterns.standard.middle; # {0}, {1}
$english.list-patterns.standard.end; # {0}, and {1}
$english.list-patterns.standard.two; # {0} and {1}

Aha! He found the data he needed.

List patterns are catalogued by their function (and-ing them, or-ing them, and a unit one designed for formatting conjoined units such as 2ft 1in or similar). Each pattern has three different lengths. Standard is what one would use most of the time, but if space is a concern, some languages might allow for even slimmer formatting. Lastly, each of those widths has four forms. The two form combines, well, two elements. The other three are used to collectively join three or more: start combines the first and second element, end combines the penultimate and final element, and middle combines all second to penultimate elements.

He then wondered what this might look like for other languages. Thankfully, testing this out in the repl was easy enough:

my &and-pattern = { cldr{$^language}.list-patterns-standard<start middle end two>.join: "\t"'" }
# Repl response (RTL corrected, s/\t/' '+/)
and-pattern 'es' # {0}, {1} {0}, {1} {0} y {1} {0} y {1}
and-pattern 'ar' # ‮{0} و{1} {0} و{1} {0} و{1} {0} و{1}
and-pattern 'ko' # {0}, {1} {0}, {1} {0} 및 {1} {0} 및 {1}
and-pattern 'my' # {0} - {1} {0} - {1} {0}နှင့် {1} {0}နှင့် {1}
and-pattern 'th' # {0} {1} {0} {1} {0} และ{1} {0}และ{1}

He quickly saw that there was quite a bit of variation! Thank goodness someone else had already catalogued all of this for him. So he went about trying to create a simple formatting routine. To begin, he created a very detailed signature and then imported the modules he’d need.

#| Lengths for list format. Valid values are 'standard', 'short', and 'narrow'.
subset ListFormatLength of Str where <standard short narrow>;
#| Lengths for list format. Valid values are 'and', 'or', and 'unit'.
subset ListFormatType of Str where <standard short narrow>;
use User::Language; # obtains default languages for a system
use Intl::LanguageTag; # use standardized language tags
use Intl::CLDR; # accesses international data
#| Formats a list of items in an internationally-aware manner
sub format-list(
+@items, #= The items to be formatted into a list
LanguageTag() :$language = user-language #= The language to use for formatting
ListFormatLength :$length = 'standard', #= The formatting width
ListFormatType :$type = 'and' #= The type of list to create
) {
...
...
...
}

That’s a bit of a big bite, but it’s worth taking a look at. First, the elf opted to use declarator POD wherever it’s possible. This can really help out people who might want to use his eventual module in an IDE, for autogenerating documentation, or for curious users in the REPL. (If you type in ListFormatLength.WHY, the text “Lengths for list format … and ‘narrow’” will be returned.) For those unaware of declarator POD, you can use either #| to apply a comment to the following symbol declaration (in the example, for the subset and the sub itself), or #= to apply it to the preceeding symbol declaration (most common with attributes).

Next, he imported two modules that will be useful. User::Language detects the system language, and he used it to provide sane defaults. Intl::LanguageTag is one of the most fundamental modules in the international ecosystem. While he wouldn’t strictly need it (we’ll see he’ll ultimately only use them in string-like form), it helps to ensure at least a plausible language tag is passed.

If you’re wondering what the [email protected] means, it applies a DWIM logic to the positional arguments. If one does format-list @foo, presumably the list is @foo, and so @items will be set to @foo. On the other hand, if someone does format-list $foo, $bar, $xyz, presumably the list isn’t $foo, but all three items. Since the first item isn’t a Positional, Raku assumes that $foo is just the first item and the remaining positional arguments are the rest of the items. The extra () in LanguageTag() means that it will take either a LanguageTag or anything that can be coerced into one (like a string).

Okay, so with that housekeeping stuff out of the way, he got to coding the actual formatting, which is devilishly simple:

my $format = cldr{$language}.list-format{$type}{$length};
my ($start, $middle, $end, $two) = $format<start middle end two>;
if @items > 2 { ... }
elsif @items == 2 { @items[0] ~ $two ~ @items[1] }
elsif @items == 1 { @items.head }
else { '' }

He paused here to check and see if stuff would work. So he ran his script and added in the following tests:

# output
format-list <>, :language<en>; # ''
format-list <a>, :language<en>; # 'a'
format-list <a b>, :language<en>; # 'a{0} and {1}b'

While the simplest two cases were easy, the first one to use CLDR data didn’t work quite as expected. The elf realized he’d need to actually replace the {0} and {1} with the item. While technically he should use subst or similar, after going through the CLDR, he realized that all of them begin with {0} and end with {1}. So he cheated and changed the initial assignment line to

my $format = cldr{$language}.list-format{$type}{$length};
my ($start, $middle, $end, $two) = $format<start middle end two>.map: *.substr(3, *-3);

Now he his two-item function worked well. For the three-or-more condition though, he had to think a bit harder how to combine things. There are actually quite a few different ways to do it! The simplest way for him was to take the first item, then the $start combining text, then join the second through penutimate, and then finish off with the $end and final item:

if @items > 2 {
~ $items[0]
~ $start
~ $items[1..*-2].join($middle)
~ $end
~ $items[*-1]
}
elsif @items == 2 { @items[0] ~ $two ~ @items[1] }
elsif @items == 1 { @items.head }
else { '' }

Et voilà! His formatting function was ready for prime-time!

# output
format-list <>, :language<en>; # ''
format-list <a>, :language<en>; # 'a'
format-list <a b>, :language<en>; # 'a and b'
format-list <a b c>, :language<en>; # 'a, b, and c'
format-list <a b c d>, :language<en>; # 'a, b, c, and d'

Perfect! Except for one small problem. When they actually started using this, the computer systems melted some of the snow away because it overheated. Every single time they called the function, the CLDR database needed to be queried and the strings would need to be clipped. The elf had to come up with something to be a slight bit more efficient.

He searched high and wide for a solution, and eventually found himself in the dangerous lands of Here Be Dragons™, otherwise known in Raku as EVAL. He knew that EVAL could potentially be dangerous, but that for his purposes, he could avoid those pitfalls. What he would do is query CLDR just once, and then produce a compilable code block that would do the simple logic based on the number of items in the list. The string values could probably be hard coded, sparing some variable look ups too.

There be dragons here 🐉🦋

EVAL should be used with great caution. All it takes is one errant unescaped string being accepted from an unknown source and your system could be taken. This is why it requires you to affirmatively type use MONKEY-SEE-NO-EVAL in a scope that needs EVAL. However, in situations like this, where we control all inputs going in, things are much safer. In tomorrow’s article, we’ll discuss ways to do this in an even more safer manner, although it adds a small degree of complexity.

Back to the regularly scheduled program

To begin, the elf imagined his formatting function.

sub format-list(+@items) {
if @items > 2 { @items[0] ~ $start ~ @items[1..*-2].join($middle) ~ $end ~ @items[*-1] }
elsif @items == 2 { @items[0] ~ $two ~ @items[1] }
elsif @items == 1 { @items[0] }
else { '' }
}

That was … really simple! But he needed this in a string format. One way to do that would be to just use straight string interpolation, but he decided to use Raku’s equivalent of a heredoc, q:to. For those unfamiliar, in Raku, quotation marks are actually just a form of syntactic sugar to enter into the Q (for quoting) sublanguage. Using quotation marks, you only get a few options: ' ' means no escaping except for \\, and using " " means interpolating blocks and $-sigiled variables. If we manually enter the Q-language (using q or Q), we get a LOT more options. If you’re more interested in those, you can check out Elizabeth Mattijsen’s 2014 Advent Calendar post on the topic. Our little elf decided to use the q:s:to option to enable him to keep his code as is, with the exception of having scalar variables interpolated. (The rest of his code only used positional variables, so he didn’t need to escape!)

my $format = cldr{$language}.list-format{$type}{$length};
my ($start, $middle, $end, $two) = $format<start middle end two>;
my $code = q:s:to/FORMATCODE/;
sub format-list([email protected]) {
if @items > 2 { @items[0] ~ $start ~ @items[1..*-2].join($middle) ~ $end ~ @items[*-1] }
elsif @items == 2 { @items[0] ~ $two ~ @items[1] }
elsif @items == 1 { @items[0] }
else { '' }
}
FORMATCODE
EVAL $code;

The only small catch is that he’d need to get a slightly different version of the text from CLDR. If the text and were placed verbatim where $two is, that block would end up being @items[0] ~ and ~ @items[1] which would cause a compile error. Luckily, Raku has a command here to help out! By using the .raku function, we get a Raku code form for most any object. For instance:

# REPL output
'abc'.raku # "abc"
"abc".raku # "abc"
<a b c>.raku # ("a", "b", "c")

So he just changed his initial assignment line to chain one more method (.raku):

my ($start, $middle, $end, $two) = $format<start middle end two>.map: *.substr(3,*-3).raku;

Now his code worked. His last step was to find a way to reuse it to benefit from this initial extra work.He made a very rudimentary caching set up (rudimentary because it’s not theoretically threadsafe, but even in this case, since values are only added, and will be identically produced, there’s not a huge problem). This is what he came up with (declarator pod and type information removed):

sub format-list (+@items, :$language 'en', :$type = 'and', :$length = 'standard') {
state %formatters;
my $code = "$language/$type/$length";
# Get a formatter, generating it if it's not been requested before
my &formatter = %cache{$code}
// %cache{$code} = generate-list-formatter($language, $type, $length);
formatter @items;
}
sub generate-list-formatter($language, $type, $length --> Sub ) {
# Get CLDR information
my $format = cldr{$language}.list-format{$type}{$length};
my ($start, $middle, $end, $two) = $format<start middle end two>.map: *.substr(3,*-3).raku;
# Generate code
my $code = q:s:to/FORMATCODE/;
sub format-list([email protected]) {
if @items > 2 { @items[0] ~ $start ~ @items[1..*-2].join($middle) ~ $end ~ @items[*-1] }
elsif @items == 2 { @items[0] ~ $two ~ @items[1] }
elsif @items == 1 { @items[0] }
else { '' }
}
FORMATCODE
# compile and return
use MONKEY-SEE-NO-EVAL;
EVAL $code;
}

And there he was! His function was all finished. He wrapped it up into a module and sent it off to the other elves for testing:

format-list <apples bananas kiwis>, :language<en>; # apples, bananas, and kiwis
format-list <apples bananas>, :language<en>, :type<or>; # apples or bananas
format-list <manzanas plátanos>, :language<es>; # manzanas y plátanos
format-list <انارها زردآلو تاریخ>, :language<fa>; # انارها، زردآلو، و تاریخ

Hooray!

Shortly thereafter, though, another elf took up his work and decided to go even crazier! Stay tuned for more of the antics from Santa’s elves how they took his lists to another level.

rakudo.org: Rakudo compiler, Release #158 (2022.12)

Published on 2022-12-04T00:00:00

Elizabeth Mattijsen: Role playing

Published by Elizabeth Mattijsen on 2022-11-20T15:15:02

This is the third part of the "A gaze of iterators!" series.

By any other name

Let's look at the names of the iterators in part 2. For this, I'm going to use the .^name method. As we've seen before, .^foo means "calling the .foo method on the object's meta-object".

say <a b c>.iterator.^name;
# Rakudo::Iterator::ReifiedListIterator
say (1..*).iterator.^name;
# Rakudo::Iterator::IntRangeUnending
say (1..10).pick(*).iterator.^name;
# List::PickN
say (1..10).map({++$_}).iterator.^name;
# Any::IterateOneWithoutPhasers

As you can see, the names of the classes of these iterator objects are all over the place. But they all provide the same interface: being able to call methods such as .pull-one, .push-all and .sink-all.

In many programming languages, you'd expect all of these classes to be sharing the same parent class. In the Raku Programming Language you can indeed inherit from a parent class. You can check the lineage of a class with the .^mro method (for method resolution order).

say <a b c>.iterator.^mro;
# ((ReifiedListIterator) (Any) (Mu))
say (1..*).iterator.^mro;
# ((IntRangeUnending) (Any) (Mu))
say (1..10).pick(*).iterator.^mro;
# ((PickN) (Any) (Mu))
say (1..10).map({++$_}).iterator.^mro;
# ((IterateOneWithoutPhasers) (Any) (Mu))

That is odd? They all seem to inherit from Any and Mu? Yet, one can not call the .pull-one method on every object that just inherits from Any and Mu:

say 42.^mro;
# ((Int) (Cool) (Any) (Mu))
say 42.pull-one;
# No such method 'pull-one' for invocant of type 'Int'

Role playing

The Raku Programming Language also provides a thing called "roles". In short, you could think of a role as a collection of methods that will be "implanted" into a class if the class itself does not provide a method implementation for it.

All of these iterator classes that we've seen here, actually do the Iterator role. And just as with the ^.mro, you can introspect which roles a class performs by calling the .^roles method. Let's see how that works out here:

say <a b c>.iterator.^roles;
# ((PredictiveIterator) (Iterator))
say (1..*).iterator.^roles;
# ((Iterator))
say (1..10).pick(*).iterator.^roles;
# ((Iterator))
say (1..10).map({++$_}).iterator.^roles;
# ((SlippyIterator) (Iterator))

So it looks like some classes are actually playing more than one role. But they all also do the Iterator role, it looks like.

How to be an iterator

To make a class be an iterator, one must tell the class to do the Iterator role. That's pretty simple, no? Let's start with an empty class that just wants to be an iterator. You do that by using does:

class Foo does Iterator {
}
===SORRY!=== Error while compiling -e
Method 'pull-one' must be implemented by Foo
because it is required by roles: Iterator.

So we need to actually provide some type of implementation for the interface that the Iterator role is providing. Ok, so let's make a very simple method pull-one that will randomly return True or False:

class TrueFalse does Iterator {
    method pull-one() { Bool.roll }
}
say TrueFalse.pull-one;  # True | False

The .roll method randomly picks a single value from a set of values. When called on an enum, it will randomly select one of the enums values. And the Bool enum has True and False as its values.

Of course, this is all very boring, let's make it more interesting:

class YeahButNoBut does Iterator {
    method pull-one() {
        Bool.roll ?? "Yeah but" !! "No but"
    }
}
say YeahButNoBut.pull-one;  # Yeah but | No but

So we now have a class that produces an iterator. But how would you actually use that in any "normal" way in your program? Well, by embedding the iterator into another class, and have a method .iterator in it that returns the iterator class:

class Jabbering {
    method iterator() {
        my class YeahButNoBut does Iterator {
            method pull-one() {
                Bool.roll ?? "Yeah but" !! "No but"
            }
        }
    }
}

Note here that the .iterator method actually returns the class object itself (usually referred to as the "type object"). Why? Because that's all we need from this iterator class: in its current form, this class doesn't need to keep any state.

Also note that classes in the Raku Programming Language can be lexically scoped by prefixing them with my, just as you would lexically scoped variables. This makes sense in this case, as there would be no need for the iterator class outside of the scope of the "Jabbering" class.

So how would this look with by .^name, ^.mro and .^roles, as we've shown with all of the other iterators?

say Jabbering.iterator.^name;
# Jabbering::YeahButNoBut
say Jabbering.iterator.^mro;
# ((YeahButNoBut) (Any) (Mu))
say Jabbering.iterator.^roles;
# ((Iterator))

As you can see, the Jabbering class iterator has the expected name. And the Jabbering class inherits from Any and Mu, and performs the Iterator role.

So with all of this out of the way, now you can start jabbering!

.say for Jabbering;

Hmmm... that doesn't stop now, does it?

Indeed it doesn't. As to why, that's for the next instalment in this series!

Conclusion

This concludes the third part of the series, in which the concept of roles in the Raku Programming Language is introduced, along with does. And that you can alter the scope of a class by prefixing it with my.

Questions and comments are always welcome. You can also drop into the #raku-beginner channel on Libera.chat, or on Discord if you'd like to have more immediate feedback.

I hope you liked it! Thank you for reading all the way to the end.

vrurg: Did you know that …

Published by Vadim Belman on 2022-10-03T00:00:00

Let’s assume we have a type with multi-component name, like:

class Foo::Bar {
}

And there is another class Baz for which we want it to be coercible into Foo::Bar. No problem!

class Baz {
    method Foo::Bar() { Foo::Bar.new }
}

Now we can do:

sub foo(Foo::Bar() $v) { say $v }
foo(Baz.new);

rakudo.org: Rakudo compiler, Release #157 (2022.07)

Published on 2022-07-31T00:00:00

rakudo.org: Rakudo compiler, Release #156 (2022.06)

Published on 2022-06-05T00:00:00

vrurg: He Tested Many Locks. See What Happened Then!

Published by Vadim Belman on 2022-04-23T00:00:00

These clickbaiting titles are so horrible, I couldn’t stand mocking them! But at least mine speaks truth.

My recent tasks are spinning around concurrency in one way or another. And where the concurrency is there are locks. Basically, introducing a lock is the most popular and the most straightforward solution for most race conditions one could encounter in their code. Like, whenever an investigation results in a resolution that data is being updated in one thread while used in another then just wrap both blocks into a lock and be done with it! Right? Are you sure?

They used to say about Perl that “if a problem is solved with regex then you got two problems”. By changing ‘regex’ to ‘lock’ we shift into another domain. I wouldn’t discuss interlocks here because it’s rather a subject for a big CS article. But I would mention an issue that is possible to stumble upon in a heavily multi-threaded Raku application. Did you know that Lock, Raku’s most used type for locking, actually blocks its thread? Did you also know that threads are a limited resource? That the default ThreadPoolScheduler has a maximum, which depends on the number of CPU cores available to your system? It even used to be a hard-coded value of 64 threads a while ago.

Put together, these two conditions could result in stuck code, like in this example:

BEGIN PROCESS::<$SCHEDULER> = ThreadPoolScheduler.new: max_threads => 32;

my Lock $l .= new;
my Promise $p .= new;
my @p; 

@p.push: start $l.protect: { await $p; };

for ^100 -> $idx {
    @p.push: start { $l.protect: { say $idx } }
}

@p.push: start { $p.keep; }

await @p;

Looks innocent, isn’t it? But it would never end because all available threads would be consumed and blocked by locks. Then the last one, which is supposed to initiate the unlock, would just never start in first place. This is not a bug in the language but a side effect of its architecture. I had to create Async::Workers module a while ago to solve a task which was hit by this issue. In other cases I can replace Lock with Lock::Async and it would just work. Why? The answer is in the following section. Why not always Lock::Async? Because it is rather slow. How much slower? Read on!

Lock vs. Lock::Async

What makes these different? To put it simple, Lock is based on system-level routines. This is why it is blocking: because this is the default system behavior.

Lock::Async is built around Promise and await. The point is that in Raku await tries to release a thread and return it back into the scheduler pool, making it immediately available to other jobs. So does Lock::Async too: instead of blocking, its protect method enters into await.

BTW, it might be surprising to many, but lock method of Lock::Async doesn’t actually lock by itself.

Atomics

There is one more way to protect a block of code from re-entering. If you’re well familiar with atomic operations then you’re likely to know about it. For the rest I would briefly explain it in this section.

Let me skip the part about the atomic operations as such, Wikipedia has it. In particular we need CAS (Wikipedia again and Raku implementation). In a natural language terms the atomic approach can be “programmed” like this:

  1. Take a variable and set it to locked state if not set already; repeat otherwise
  2. Do your work.
  3. Set the variable to unlocked state.

Note that 1 and 3 are both atomic ops. In Raku code this is expressed in the following slightly simplified snippet:

my atomicint $lock = 0; # 0 is unlocked, 1 is locked
while cas($lock, 0, 1) == 1 {}  # lock
...                             # Do your work
$lock ⚛= 0;                     # unlock

Pretty simple, isn’t it? Let’s see what are the specs of this approach:

  1. It is blocking, akin to Lock
  2. It’s fast (will get back to this later)
  3. The lock operation might be a CPU hog

Item 2 is speculative at this moment, but guessable. Contrary to Lock, we don’t use a system call but rather base the lock on a purely computational trick.

Item 3 is apparent because even though Lock doesn’t release it’s thread for Raku scheduler, it does release a CPU core to the system.

Benchmarkers, let’s go benchmarking!

As I found myself in between of two big tasks today, I decided to make a pause and scratch the itch of comparing different approaches to locking. Apparently, we have three different kinds of locks at our hands, each based upon a specific approach. But aside of that, we also have two different modes of using them. One is explicit locking/unlocking withing the protected block. The other one is to use a wrapper method protect, available on Lock and Lock::Async. There is no data type for atomic locking, but this is something we can do ourselves and have the method implemented the same way, as Lock does.

Here is the code I used:

constant MAX_WORKERS = 50;  # how many workers per approach to start
constant TEST_SECS = 5;     # how long each worker must run

class Lock::Atomic {
    has atomicint $!lock = 0;

    method protect(&code) {
        while cas($!lock, 0, 1) == 1 { }
        LEAVE $!lock ⚛= 0;
        &code()
    }
}

my @tbl = <Wrkrs Atomic Lock Async Atomic.P Lock.P Async.P>;
my $max_w = max @tbl.map(*.chars);
printf (('%' ~ $max_w ~ 's') xx [email protected]).join(" ") ~ "\n", |@tbl;
my $dfmt = (('%' ~ $max_w ~ 'd') xx [email protected]).join(" ") ~ "\n";

for 2..MAX_WORKERS -> $wnum {
    $*ERR.print: "$wnum\r";
    my Promise:D $starter .= new;
    my Promise:D @ready;
    my Promise:D @workers;
    my atomicint $stop = 0;

    sub worker(&code) {
        my Promise:D $ready .= new;
        @ready.push: $ready;
        @workers.push: start {
            $ready.keep;
            await $starter;
            &code();
        }
    }

    my atomicint $ia-lock = 0;
    my $ia-counter = 0;

    my $il-lock = Lock.new;
    my $il-counter = 0;

    my $ila-lock = Lock::Async.new;
    my $ila-counter = 0;

    my $iap-lock = Lock::Atomic.new;
    my $iap-counter = 0;

    my $ilp-lock = Lock.new;
    my $ilp-counter = 0;

    my $ilap-lock = Lock::Async.new;
    my $ilap-counter = 0;

    for ^$wnum {
        worker {
            until $stop {
                while cas($ia-lock, 0, 1) == 1 { } # lock
                LEAVE $ia-lock ⚛= 0; # unlock
                ++$ia-counter;
            }
        }

        worker {
            until $stop {
                $il-lock.lock;
                LEAVE $il-lock.unlock;
                ++$il-counter;
            }
        }

        worker {
            until $stop {
                await $ila-lock.lock;
                LEAVE $ila-lock.unlock;
                ++$ila-counter;
            }
        }

        worker {
            until $stop {
                $iap-lock.protect: { ++$iap-counter }
            }
        }

        worker {
            until $stop {
                $ilp-lock.protect: { ++$ilp-counter }
            }
        }

        worker {
            until $stop {
                $ilap-lock.protect: { ++$ilap-counter }
            }
        }

    }

    await @ready;
    $starter.keep;
    sleep TEST_SECS;
    $*ERR.print: "stop\r";
    $stop ⚛= 1;
    await @workers;

    printf $dfmt, $wnum, $ia-counter, $il-counter, $ila-counter, $iap-counter, $ilp-counter, $ilap-counter;
}

The code is designed for a VM with 50 CPU cores available. By setting that many workers per approach, I also cover a complex case of an application over-utilizing the available CPU resources.

Let’s see what it comes up with:

   Wrkrs   Atomic     Lock    Async Atomic.P   Lock.P  Async.P
       2   918075   665498    71982   836455   489657    76854
       3   890188   652154    26960   864995   486114    27864
       4   838870   520518    27524   805314   454831    27535
       5   773773   428055    27481   795273   460203    28324
       6   726485   595197    22926   729501   422224    23352
       7   728120   377035    19213   659614   403106    19285
       8   629074   270232    16472   644671   366823    17020
       9   674701   473986    10063   590326   258306     9775
      10   536481   446204     8513   474136   292242     7984
      11   606643   242842     6362   450031   324993     7098
      12   501309   224378     9150   468906   251205     8377
      13   446031   145927     7370   491844   277977     8089
      14   444665   181033     9241   412468   218475    10332
      15   410456   169641    10967   393594   247976    10008
      16   406301   206980     9504   389292   250340    10301
      17   381023   186901     8748   381707   250569     8113
      18   403485   150345     6011   424671   234118     6879
      19   372433   127482     8251   311399   253627     7280
      20   343862   139383     5196   301621   192184     5412
      21   350132   132489     6751   315653   201810     6165
      22   287302   188378     7317   244079   226062     6159
      23   326460   183097     6924   290294   158450     6270
      24   256724   128700     2623   294105   143476     3101
      25   254587    83739     1808   309929   164739     1878
      26   235215   245942     2228   211904   210358     1618
      27   263130   112510     1701   232590   162413     2628
      28   244143   228978       51   292340   161485       54
      29   235120   104492     2761   245573   148261     3117
      30   222840   116766     4035   241322   140127     3515
      31   261837    91613     7340   221193   145555     6209
      32   206170    85345     5786   278407    99747     5445
      33   240815   109631     2307   242664   128062     2796
      34   196083   144639      868   182816   210769      664
      35   198096   142727     5128   225467   113573     4991
      36   186880   225368     1979   232178   179265     1643
      37   212517   110564       72   249483   157721       53
      38   158757    87834      463   158768   141681      523
      39   134292    61481       79   164560   104768       70
      40   210495   120967       42   193469   141113       55
      41   174969   118752       98   206225   160189     2094
      42   157983   140766      927   127003   126041     1037
      43   174095   129580       61   199023    91215       42
      44   251304   185317       79   187853    90355       86
      45   216065    96315       69   161697   134644      104
      46   135407    67411      422   128414   110701      577
      47   128418    73384       78    94186    95202       53
      48   113268    81380       78   112763   113826      104
      49   118124    73261      279   113389    90339       78
      50   121476    85438      308    82896    54521      510

Without deep analysis, I can make a few conclusions:

And to conclude with, the performance win of atomic approach doesn’t make it a clear winner due to it’s high CPU cost. I would say that it is a good candidate to consider when there is need to protect small, short-acting operations. Especially in performance-sensitive locations. And even then there are restricting conditions to be fulfilled:

In other words, the way we utilize CPU matters. If aggregated CPU time consumed by locking loops is larger than that needed for Lock to release+acquire the involved cores then atomic becomes a waste of resources.

Conclusion

By this moment I look at the above and wonder: are there any use for the atomic approach at all? Hm… 😉

By carefully considering this dilemma I would preliminary put it this way: I would be acceptable for an application as it knows the conditions it would be operated in and this makes it possible to estimate the outcomes.

But it is most certainly no go for a library/module which has no idea where and how would it be used.

It is much easier to formulate the rule of thumb for Lock::Async acceptance:

Sounds like some heavily parallelized I/O to me, for example. In such cases it is less important to be really fast but it does matter not to hit the max_threads limit.

Ukraine

This section would probably stay here for a while, until Ukraine wins the war. Until then, please, check out this page!

I have already received some donations on my PayPal. Not sure if I’m permitted to publish the names here. But I do appreciate your help a lot! In all my sincerity: Thank you!

vrurg: A New `will complain` Trait

Published by Vadim Belman on 2022-04-18T00:00:00

Long time no see, my dear reader! I was planning a lot for this blog, as well as for the Advanced Raku For Beginners series. But you know what they say: wanna make the God laugh – tell him your plans!

Anyway, there is one tradition I should try to maintain however hard the times are: whenever I introduce something new into the Raku language an update has to be published. No exception this time.

So, welcome a new will complain trait!

The idea of it came to be from discussion about a PR by @lizmat. The implementation as such could have taken less time would I be less busy lately. Anyway, at the moment when I’m typing these lines PR#4861 is undergoing CI testing and as soon as it is completed it will be merged into the master. But even after that the trait will not be immediately available as I consider it rather an experimental feature. Thus use experimental :will-complain; will be required to make use of it.

The actual syntax is very simple:

<declaration> will complain <code>;

The <declaration> is anything what could result in a type check exception thrown. I tried to cover all such cases, but not sure if something hasn’t been left behind. See the sections below.

<code> can be any Code object which will receive a single argument: the value which didn’t pass the type check. The code must return a string to be included into exception message. Something stringifiable would also do.

Less words, more examples!

Type Objects

my enum FOO 
    will complain { "need something FOO-ish, got {.raku}" } 
    <foo1 foo2 foo3>;
my subset IntD of Int:D 
    will complain { "only non-zero positive integers, not {.raku}" } 
    where * > 0;
my class Bar 
    will complain -> $val { "need something Bar-like, got {$val.^name}" } {}

Basically, any type object can get the trait except for composables, i.e. – roles. This is because there is no unambiguous way to chose the particular complain block to be used when a type check fails:

role R will complain { "only R" } {}
role R[::T] will complain { "only R[::T]" } {}
my R $v;
$v = 13; # Which role candidate to choose from??

There are some cases when the ambiguity is pre-resolved, like my R[Int] $v;, but I’m not ready to get into these details yet.

Variables

A variable could have specific meaning. Some like to use our to configure modules (my heavily multi-threaded soul is grumbling, but we’re tolerant to people’s mistakes, aren’t we?). Therefore providing them with a way to produce less cryptic error messages is certainly for better than for worse:

our Bool:D $disable-something
    will complain { "set disable-something something boolean!" } = False;

And why not to help yourself with a little luxury of easing debugging when an assignment fails:

my Str $a-lexical 
   will complain { "string must contain 'foo'" } 
   where { !.defined || .contains("foo") }; 

The trait works with hashes and arrays too, except that it is applied not to the actual hash or array object but to its values. Therefore it really only makes sense for their typed variants:

my Str %h will complain { "hash values are to be strings, not {.^name}" };
my Int @a will complain { "this array is all about integers, not {.^name}" };

Also note that this wouldn’t work for hashes with typed keys when a key of wrong type is used. But it doesn’t mean there is no solution:

subset IntKey of Int will complain { "hash key must be an Int" };
my %h{IntKey};
%h<a> = 13;

Attributes

class Foo {
    has Int $.a 
        is rw 
        will complain { "you offer me {.raku}, but with all the respect: an integer, please!" };
}

Parameters

sub foo( Str:D $p will complain { "the first argument must be a string with 'foo'" } 
                  where *.contains('foo') ) {}

Merge

By this time all CI has passed with no errors and I have merged the PR.

Ukraine

You all are likely to know about the Russia’s war in Ukraine. Some of you know that Ukraine is my homeland. What I never told is that since the first days of the invasion we (my family) are trying to help our friends back there who fight against the aggressor. By ‘fight’ I mean it, they’re literally at the front lines. Unfortunately, our resources are not limitless. Therefore I would like to ask for any donations you could make by using the QR code below.

I’m not asking this for myself. I didn’t even think of this when I started this post. I never took a single penny for whatever I was doing for the Raku language. Even more, I was avoiding applying for any grants because it was always like “somebody would have better use for them”.

But this time I’m asking because any help to Ukrainian militaries means saving lives, both theirs and the people they protect.

PayPal:
PayPal Donate

vrurg: Merging Symbols Issue

Published by Vadim Belman on 2021-10-05T00:00:00

First of all, I’d like to apologize for all the errors in this post. I just haven’t got time to properly proof-read it.

A while ago I was trying to fix a problem in Rakudo which, under certain conditions, causes some external symbols to become invisible for importing code, even if explicit use statement is used. And, indeed, it is really confusing when:

use L1::L2::L3::Class;
L1::L2::L3::Class.new;

fails with “Class symbol doesn’t exists in L1::L2::L3” error! It’s ok if use throws when there is no corresponding module. But .new??

Skip This Unless You Know What A Package Is

This section is needed to understand the rest of the post. A package in Raku is a typeobject which has a symbol table attached. The table is called stash (stands for “symbol table hash”) and is represented by an instance of Stash class, which is, basically, is a hash with minor tweaks. Normally each package instance has its own stash. For example, it is possible to manually create two different packages with the same name:

my $p1a := Metamodel::PackageHOW.new_type(:name<P1>); 
my $p1b := Metamodel::PackageHOW.new_type(:name<P1>); 
say $p1a.WHICH, " ", $p1a.WHO.WHICH; # P1|U140722834897656 Stash|140723638807008
say $p1b.WHICH, " ", $p1b.WHO.WHICH; # P1|U140722834897800 Stash|140723638818544

Note that they have different stashes as well.

A package is barely used in Raku as is. Usually we deal with packagy things like modules and classes.

Back On The Track

Back then I managed to trace the problem down to deserialization process within MoarVM backend. At that point I realized that somehow it pulls in packagy objects which are supposed to be the same thing, but they happen to be different and have different stashes. Because MoarVM doesn’t (and must not) have any idea about the structure of high-level Raku objects, there is no way it could properly handle this situation. Instead it considers one of the conflicting stashes as “the winner” and drops the other one. Apparently, symbols unique to the “loser” are lost then.

It took me time to find out what exactly happens. But not until a couple of days ago I realized what is the root cause and how to get around the bug.

Package Tree

What happens when we do something like:

module Foo {
    module Bar {
    }
}

How do we access Bar, speaking of the technical side of things? Foo::Bar syntax basically maps into Foo.WHO<Bar>. In other words, Bar gets installed as a symbol into Foo stash. We can also rewrite it with special syntax sugar: Foo::<Bar> because Foo:: is a representation for Foo stash.

So far, so good; but where do we find Foo itself? In Raku there is a special symbol called GLOBAL which is the root namespace (or a package if you wish) of any code. GLOBAL::, or GLOBAL.WHO is where one finds all the top-level symbols.

Say, we have a few packages like L11::L21, L11::L22, L12::L21, L12::L22. Then the namespace structure would be represented by this tree:

GLOBAL
`- L11
   `- L21
   `- L22
`- L12
   `- L21
   `- L22

Normally there is one per-process GLOBAL symbol and it belongs to the compunit which used to start the program. Normally it’s a .raku file, or a string supplied on command line with -e option, etc. But each compunit also gets its own GLOBALish package which acts as compunit’s GLOBAL until it is fully incorporated into the main code. Say, we declare a module in file Foo.rakumod:

unit module Foo;
sub print-GLOBAL($when) is export {
    say "$when: ", GLOBAL.WHICH, " ", GLOBALish.WHICH;
}
print-GLOBAL 'LOAD';

And use it in a script:

use Foo;
print-GLOBAL 'RUN ';

Then we can get an ouput like this:

LOAD: GLOBAL|U140694020262024 GLOBAL|U140694020262024
RUN : GLOBAL|U140694284972696 GLOBAL|U140694020262024

Notice that GLOBALish symbol remains the same object, whereas GLOBAL gets different. If we add a line to the script which also prints GLOBAL.WHICH then we’re going to get something like:

MAIN: GLOBAL|U140694284972696

Let’s get done with this part of the story for a while a move onto another subject.

Compunit Compilation

This is going to be a shorter story. It is not a secret that however powerful Raku’s grammars are, they need some core developer’s attention to make them really fast. In the meanwhile, compilation speed is somewhat suboptimal. It means that if a project consist of many compunits (think of modules, for example), it would make sense to try to compile them in parallel if possible. Unfortunately, the compiler is not thread-safe either. To resolve this complication Rakudo implementation parallelizes compilation by spawning individual processes per each compunit.

For example, let’s refer back to the module tree example above and imagine that all modules are used by a script. In this case there is a chance that we would end up with six rakudo processes, each compiling its own L* module. Apparently, things get slightly more complicated if there are cross-module uses, like L11::L21 could refer to L21, which, in turn, refers to L11::L22, or whatever. In this case we need to use topological sort to determine in what order the modules are to be compiled; but that’s not the point.

The point is that since each process does independent compilation, each compunit needs independent GLOBAL to manage its symbols. For the time being, what we later know as GLOBALish serves this duty for the compiler.

Later, when all pre-compiled modules are getting incorporated into the code which uses them, symbols installed into each individual GLOBAL are getting merged together to form the final namespace, available for our program. There are even methods in the source, using merge_global in their names.

TA-TA-TAAA!

(Note the clickable section header; I love the guy!)

Now, you can feel the catch. Somebody might have even guessed what it is. It crossed my mind after I was trying to implement legal symbol auto-registration which doesn’t involve using QAST to install a phaser. At some point I got an idea of using GLOBAL to hold a register object which would keep track of specially flagged roles. Apparently it failed due to the parallelized compilation mentioned above. It doesn’t matter, why; but at that point I started building a mental model of what happens when merge is taking place. And one detail drew my special attention: what happens if a package in a long name is not explicitly declared?

Say, there is a class named Foo::Bar::Baz one creates as:

unit class Foo::Bar;
class Baz { }

In this case the compiler creates a stub package for Foo. The stub is used to install class Bar. Then it all gets serialized into bytecode.

At the same time there is another module with another class:

unit class Foo::Bar::Fubar;

It is not aware of Foo::Bar::Baz, and the compiler has to create two stubs: Foo and Foo::Bar. And not only two versions of Foo are different and have different stashes; but so are the two versions of Bar where one is a real class, the other is a stub package.

Most of the time the compiler does damn good job of merging symbols in such cases. It took me stripping down a real-life code to golf it down to some minimal set of modules which reproduces the situation where a require call comes back with a Failure and a symbol becomes missing. The remaining part of this post will be dedicated to this example. In particular, this whole text is dedicated to one line.

Before we proceed further, I’d like to state that I might be speculating about some aspects of the problem cause because some details are gone from my memory and I don’t have time to re-investigate them. Still, so far my theory is backed by working workaround presented at the end.

To make it a bit easier to analyze the case, let’s start with namespace tree:

GLOBAL
`- L1
   `- App
   `- L2
      `- Collection
         `- Driver
         `- FS

Rough purpose is for application to deal with some kind of collection which stores its items with help of a driver which is loaded dynamically, depending, say, on a user configuration. We have the only driver implemented: File System (FS).

If you checkout the repository and try raku -Ilib symbol-merge.raku in the examples/2021-10-05-merge-symbols directory, you will see some output ending up with a line like Failure|140208738884744 (certainly true for up until Rakudo v2021.09 and likely to be so for at least a couple of versions later).

The key conflict in this example are modules Collection and Driver. The full name of Collection is L1::L2::Collection. L1 and L2 are both stubs. Driver is L1::L2::Collection::Driver and because it imports L1::L2, L2 is a class; but L1 remains to be a stub. By commenting out the import we’d get the bug resolved and the script would end up with something like:

L1::L2::Collection::FS|U140455893341088

This means that the driver module was successfully loaded and the driver class symbol is available.

Ok, uncomment the import and start the script again. And then once again to get rid of the output produced by compilation-time processes. We should see something like this:

[7329] L1 in L1::L2         : L1|U140360937889112
[7329] L1 in Driver         : L1|U140361742786216
[7329] L1 in Collection     : L1|U140361742786480
[7329] L1 in App            : L1|U140361742786720
[7329] L1 in MAIN           : L1|U140361742786720
[7329] L1 in FS             : L1|U140361742788136
Failure|140360664014848

We already know that L1 is a stub. Dumping object IDs also reveals that each compunit has its own copy of L1, except for App and the script (marked as MAIN). This is pretty much expected because each L1 symbol is installed at compile-time into per-compunit GLOBALish. This is where each module finds it. App is different because it is directly imported by the script and was compiled by the same compiler process, and shared its GLOBAL with the script.

Now comes the black magic. Open lib/L1/L2/Collection/FS.rakumod and uncomment the last line in the file. Then give it a try. The output would seem impossible at first; hell with it, even at second glance it is still impossible:

[17579] Runtime Collection syms      : (Driver)

Remember, this line belongs to L1::L2::Collection::FS! How come we don’t see FS in Collection stash?? No wonder that when the package cannot see itself others cannot see it too!

Here comes a bit of my speculation based on what I vaguely remember from the times ~2 years ago when I was trying to resolve this bug for the first time.

When Driver imports L1::L2, Collection gets installed into L2 stash, and Driver is recorded in Collection stash. Then it all gets serialized with Driver compunit.

Now, when FS imports Driver to consume the role, it gets the stash of L2 serialized at the previous stage. But its own L2 is a stub under L1 stub. So, it gets replaced with the serialized “real thing” which doesn’t have FS under Collection! Bingo and oops…

A Workaround

Walk through all the example files and uncomment use L1 statement. That’s it. All compunits will now have a common anchor to which their namespaces will be attached.

The common rule would state that if a problem of the kind occurs then make sure there’re no stub packages in the chain from GLOBAL down to the “missing” symbol. In particular, commenting out use L1::L2 in Driver will get our error back because it would create a “hole” between L1 and Collection and get us back into the situation where conflicting Collection namespaces are created because they’re bound to different L2 packages.

It doesn’t really matter how exactly the stubs are avoided. For example, we can easily move use L1::L2 into Collection and make sure that use L1 is still part of L2. So, for simplicity a child package may import its parent; and parent may then import its parent; and so on.

Sure, this adds to the boilerplate. But I hope the situation is temporary and there will be a fix.

Fix?

The one I was playing with required a compunit to serialize its own GLOBALish stash at the end of the compilation in a location where it would not be at risk of overwriting. Basically, it means cloning and storing it locally on the compunit (the package stash is part of the low-level VM structures). Then compunit mainline code would invoke a method on the Stash class which would forcibly merge the recorded symbols back right after deserialization of compunit’s bytecode. It was seemingly working, but looked more of a kind of a hack, than a real fix. This and a few smaller issues (like a segfault which I failed to track down) caused it to be frozen.

As I was thinking of it lately, more proper fix must be based upon a common GLOBAL shared by all compunits of a process. In this case there will be no worry about multiple stub generated for the same package because each stub will be shared by all compunits until, perhaps, the real package is found in one of them.

Unfortunately, the complexity of implementing the ‘single GLOBAL’ approach is such that I’m unsure if anybody with appropriate skill could fit it into their schedule.

6guts: The new MoarVM dispatch mechanism is here!

Published by jnthnwrthngtn on 2021-09-29T16:16:31

Around 18 months ago, I set about working on the largest set of architectural changes that Raku runtime MoarVM has seen since its inception. The work was most directly triggered by the realization that we had no good way to fix a certain semantic bug in dispatch without either causing huge performance impacts across the board or increasingly complexity even further in optimizations that were already riding their luck. However, the need for something like this had been apparent for a while: a persistent struggle to optimize certain Raku language features, the pain of a bunch of performance mechanisms that were all solving the same kind of problem but each for a specific situation, and a sense that, with everything learned since I founded MoarVM, it was possible to do better.

The result is the development of a new generalized dispatch mechanism. An overview can be found in my Raku Conference talk about it (slidesvideo); in short, it gives us a far more uniform architecture for all kinds of dispatch, allowing us to deliver better performance on a range of language features that have thus far been glacial, as well as opening up opportunities for new optimizations.

Today, this work has been merged, along with the matching changes in NQP (the Raku subset we use for bootstrapping and to implement the compiler) and Rakudo (the full Raku compiler and standard library implementation). This means that it will ship in the October 2021 releases.

In this post, I’ll give an overview of what you can expect to observe right away, and what you might expect in the future as we continue to build upon the possibilities that the new dispatch architecture has to offer.

The big wins

The biggest improvements involve language features that we’d really not had the architecture to do better on before. They involved dispatch – that is, getting a call linked to a destination efficiently – but the runtime didn’t provide us with a way to “explain” to it that it was looking at a dispatch, let alone with the information needed to have a shot at optimizing it.

The following graph captures a number of these cases, and shows the level of improvement, ranging from a factor of 3.3 to 13.3 times faster.

Graph showing benchmark results, described textually below

Let’s take a quick look at each of these. The first, new-buf, asks how quickly we can allocate Bufs.

for ^10_000_000 {
    Buf.new
}

Why is this a dispatch benchmark? Because Buf is not a class, but rather a role. When we try to make an instance of a role, it is “punned” into a class. Up until now, it works as follows:

  1. We look up the new method
  2. The find_method method would, if needed, create a pun of the role and cache it
  3. It would return a forwarding closure that takes the arguments and gives them to the same method called on the punned class, or spelt in Raku code, -> $role-discarded, |args { $pun."$name"(|args) }
  4. This closure would be invoked with the arguments

This had a number of undesirable consequences:

  1. While the pun was cached, we still had a bit of overhead to check if we’d made it already
  2. The arguments got slurped and flattened, which costs something, and…
  3. …the loss of callsite shape meant we couldn’t look up a type specialization of the method, and thus lost a chance to inline it too

With the new dispatch mechanism, we have a means to cache constants at a given program location and to replace arguments. So the first time we encounter the call, we:

  1. Get the role pun produced if needed
  2. Resolve the new method on the class punned from the role
  3. Produce a dispatch program that caches this resolved method and also replaces the role argument with the pun

For the next thousands of calls, we interpret this dispatch program. It’s still some cost, but the method we’re calling is already resolved, and the argument list rewriting is fairly cheap. Meanwhile, after we get into some hundreds of iterations, on a background thread, the optimizer gets to work. The argument re-ordering cost goes away completely at this point, and new is so small it gets inlined – at which point the buffer allocation is determined dead and so goes away too. Some remaining missed opportunities mean we still are left with a loop that’s not quite empty: it busies itself making sure it’s really OK to do nothing, rather than just doing nothing.

Next up, multiple dispatch with where clauses.

multi fac($n where $n <= 1) { 1 }
multi fac($n) { $n * fac($n - 1) }
for ^1_000_000 {
    fac(5)
}

These were really slow before, since:

  1. We couldn’t apply the multi-dispatch caching mechanism at all as soon as we had a where clause involved
  2. We would run where clauses twice in the event the candidate was chosen: once to see if we should choose that multi candidate, and once again when we entered it

With the new mechanism, we:

  1. On the first call, calculate a multiple dispatch plan: a linked list of candidates to work through
  2. Invoke the one with the where clause, in a mode whereby if the signature fails to bind, it triggers a dispatch resumption. (If it does bind, it runs to completion)
  3. In the event of a bind failure, the dispatch resumption triggers, and we attempt the next candidate

Once again, after the setup phase, we interpret the dispatch programs. In fact, that’s as far as we get with running this faster for now, because the specializer doesn’t yet know how to translate and further optimize this kind of dispatch program. (That’s how I know it currently stands no chance of turning this whole thing into another empty loop!) So there’s more to be had here also; in the meantime, I’m afraid you’ll just have to settle for a factor of ten speedup.

Here’s the next one:

proto with-proto(Int $n) { 2 * {*} }
multi with-proto(Int $n) { $n + 1 }
sub invoking-nontrivial-proto() {
    for ^10_000_000 {
        with-proto(20)
    }
}

Again, on top form, we’d turn this into an empty loop too, but we don’t quite get there yet. This case wasn’t so terrible before: we did get to use the multiple dispatch cache, however to do that we also ended up having to allocate an argument capture. The need for this also blocked any chance of inlining the proto into the caller. Now that is possible. Since we cannot yet translate dispatch programs that resume an in-progress dispatch, we don’t yet get to further inline the called multi candidate into the proto. However, we now have a design that will let us implement that.

This whole notion of a dispatch resumption – where we start doing a dispatch, and later need to access arguments or other pre-calculated data in order to do a next step of it – has turned out to be a great unification. The initial idea for it came from considering things like callsame:

class Parent {
    method m() { 1 }
}
class Child is Parent {
    method m() { 1 + callsame }
}
for ^10_000_000 {
    Child.m;
}

Once I started looking at this, and then considering that a complex proto also wants to continue with a dispatch at the {*}, and in the case a where clauses fails in a multi it also wants to continue with a dispatch, I realized this was going to be useful for quite a lot of things. It will be a bit of a headache to teach the optimizer and JIT to do nice things with resumes – but a great relief that doing that once will benefit multiple language features!

Anyway, back to the benchmark. This is another “if we were smart, it’d be an empty loop” one. Previously, callsame was very costly, because each time we invoked it, it would have to calculate what kind of dispatch we were resuming and the set of methods to call. We also had to be able to locate the arguments. Dynamic variables were involved, which cost a bit to look up too, and – despite being an implementation details – these also leaked out in introspection, which wasn’t ideal. The new dispatch mechanism makes this all rather more efficient: we can cache the calculated set of methods (or wrappers and multi candidates, depending on the context) and then walk through it, and there’s no dynamic variables involved (and thus no leakage of them). This sees the biggest speedup of the lot – and since we cannot yet inline away the callsame, it’s (for now) measuring the speedup one might expect on using this language feature. In the future, it’s destined to optimize away to an empty loop.

A module that makes use of callsame on a relatively hot path is OO::Monitors,, so I figured it would be interesting to see if there is a speedup there also.

use OO::Monitors;
monitor TestMonitor {
    method m() { 1 }
}
my $mon = TestMonitor.new;
for ^1_000_000 {
    $mon.m();
}

monitor is a class that acquires a lock around each method call. The module provides a custom meta-class that adds a lock attribute to the class and then wraps each method such that it acquires the lock. There are certainly costly things in there besides the involvement of callsame, but the improvement to callsame is already enough to see a 3.3x speedup in this benchmark. Since OO::Monitors is used in quite a few applications and modules (for example, Cro uses it), this is welcome (and yes, a larger improvement will be possible here too).

Caller side decontainerization

I’ve seen some less impressive, but still welcome, improvements across a good number of other microbenchmarks. Even a basic multi dispatch on the + op:

my $i = 0;
for ^10_000_000 {
    $i = $i + $_;
}

Comes out with a factor of 1.6x speedup, thanks primarily to us producing far tighter code with fewer guards. Previously, we ended up with duplicate guards in this seemingly straightforward case. The infix:<+> multi candidate would be specialized for the case of its first argument being an Int in a Scalar container and its second argument being an immutable Int. Since a Scalar is mutable, the specialization would need to read it and then guard the value read before proceeding, otherwise it may change, and we’d risk memory safety. When we wanted to inline this candidate, we’d also want to do a check that the candidate really applies, and so also would deference the Scalar and guard its content to do that. We can and do eliminate duplicate guards – but these guards are on two distinct reads of the value, so that wouldn’t help.

Since in the new dispatch mechanism we can rewrite arguments, we can now quite easily do caller-side removal of Scalar containers around values. So easily, in fact, that the change to do it took me just a couple of hours. This gives a lot of benefits. Since dispatch programs automatically eliminate duplicate reads and guards, the read and guard by the multi-dispatcher and the read in order to pass the decontainerized value are coalesced. This means less repeated work prior to specialization and JIT compilation, and also only a single read and guard in the specialized code after it. With the value to be passed already guarded, we can trivially select a candidate taking two bare Int values, which means there’s no further reads and guards needed in the callee either.

A less obvious benefit, but one that will become important with planned future work, is that this means Scalar containers escape to callees far less often. This creates further opportunities for escape analysis. While the MoarVM escape analyzer and scalar replacer is currently quite limited, I hope to return to working on it in the near future, and expect it will be able to give us even more value now than it would have been able to before.

Further results

The benchmarks shown earlier are mostly of the “how close are we to realizing that we’ve got an empty loop” nature, which is interesting for assessing how well the optimizer can “see through” dispatches. Here are a few further results on more “traditional” microbenchmarks:

Graph showing benchmark results, described textually below

The complex number benchmark is as follows:

my $total-re = 0e0;
for ^2_000_000 {
    my $x = 5 + 2i;
    my $y = 10 + 3i;
    my $z = $x * $x + $y;
    $total-re = $total-re + $z.re
}
say $total-re;

That is, just a bunch of operators (multi dispatch) and method calls, where we really do use the result. For now, we’re tied with Python and a little behind Ruby on this benchmark (and a surprising 48 times faster than the same thing done with Perl’s Math::Complex), but this is also a case that stands to see a huge benefit from escape analysis and scalar replacement in the future.

The hash read benchmark is:

my %h = a => 10, b => 12;
my $total = 0;
for ^10_000_000 {
    $total = $total + %h<a> + %h<b>;
}

And the hash store one is:

my @keys = 'a'..'z';
for ^500_000 {
    my %h;
    for @keys {
        %h{$_} = 42;
    }
}

The improvements are nothing whatsoever to do with hashing itself, but instead look to be mostly thanks to much tighter code all around due to caller-side decontainerization. That can have a secondary effect of bringing things under the size limit for inlining, which is also a big help. Speedup factors of 2x and 1.85x are welcome, although we could really do with the same level of improvement again for me to be reasonably happy with our results.

The line-reading benchmark is:

my $fh = open "longfile";
my $chars = 0;
for $fh.lines { $chars = $chars + .chars };
$fh.close;
say $chars

Again, nothing specific to I/O got faster, but when dispatch – the glue that puts together all the pieces – gets a boost, it helps all over the place. (We are also decently competitive on this benchmark, although tend to be slower the moment the UTF-8 decoder can’t take it’s “NFG can’t possibly apply” fast path.)

And in less micro things…

I’ve also started looking at larger programs, and hearing results from others about theirs. It’s mostly encouraging:

Smaller profiler output

One unpredicted (by me), but also welcome, improvement is that profiler output has become significantly smaller. Likely reasons for this include:

  1. The dispatch mechanism supports producing value results (either from constants, input arguments, or attributes read from input arguments). It entirely replaces an earlier mechanism, “specializer plugins”, which could map guards to a target to invoke, but always required a call to something – even if that something was the identity function. The logic was that this didn’t matter for any really hot code, since the identity function will trivially be inlined away. However, since profile size of the instrumenting profiler is a function of the number of paths through the call tree, trimming loads of calls to the identity function out of the tree makes it much smaller.
  2. We used to make lots of calls to the sink method when a value was in sink context. Now, if we see that the type simply inherits that method from Mu, we elide the call entirely (again, it would inline away, but a smaller call graph is a smaller profile).
  3. Multiple dispatch caching would previously always call the proto when the cache was missed, but would then not call an onlystar proto again when it got cache hits in the future. This meant the call tree under many multiple dispatches was duplicated in the profile. This wasn’t just a size issue; it was a bit annoying to have this effect show up in the profile reports too.

To give an example of the difference, I took profiles from Agrammon to study why it might have become slower. The one from before the dispatcher work weighed in at 87MB; the one with the new dispatch mechanism is under 30MB. That means less memory used while profiling, less time to write the profile out to disk afterwards, and less time for tools to load the profiler output. So now it’s faster to work out how to make things faster.

Is there any bad news?

I’m afraid so. Startup time has suffered. While the new dispatch mechanism is more powerful, pushes more complexity out of the VM into high level code, and is more conducive to reaching higher peak performance, it also has a higher warmup time. At the time of writing, the impact on startup time seems to be around 25%. I expect we can claw some of that back ahead of the October release.

What will be broken?

Changes of this scale always come with an amount of risk. We’re merging this some weeks ahead of the next scheduled monthly release in order to have time for more testing, and to address any regressions that get reported. However, even before reaching the point of merging it, we have:

What happens next?

As I’ve alluded to in a number of places in this post, while there are improvements to be enjoyed right away, there are also new opportunities for further improvement. Some things that are on my mind include:

Thank you

I would like to thank TPF and their donors for providing the funding that has made it possible for me to spend a good amount of my working time on this effort.

While I’m to blame for the overall design and much of the implementation of the new dispatch mechanism, plenty of work has also been put in by other MoarVM and Rakudo contributors – especially over the last few months as the final pieces fell into place, and we turned our attention to getting it production ready. I’m thankful to them not only for the code and debugging contributions, but also much support and encouragement along the way. It feels good to have this merged, and I look forward to building upon it in the months and years to come.

vrurg: Secure JSONification?

Published by Vadim Belman on 2021-09-14T00:00:00

There was an interesting discussion on IRC today. In brief, it was about exposing one’s database structures over API and security implications of this approach. I’d recommend reading the whole thing because Altreus delivers a good (and somewhat emotional 🙂) point on why such practice is most definitely bad design decision. Despite having minor objections, I generally agree to him.

But I’m not wearing out my keyboard on this post just to share that discussion. There was something in it what made me feel as if I miss something. And it came to me a bit later, when I was done with my payjob and got a bit more spare resources for the brain to utilize.

First of all, a bell rang when a hash was mentioned as the mediator between a database and API return value. I’m somewhat wary about using hashes as return values primarily for a reason of performance price and concurrency unsafety.

Anyway, the discussion went on and came to the point where it touched the ground of blacklisting of a DB table fields vs. whitelisting. The latter is really worthy approach of marking those fields we want in a JSON (or a hash) rather than marking those we don’t want because blacklisting requires us to remember to mark any new sensitive field as prohibited explicitly. Apparently, it is easy to forget to stick the mark onto it.

Doesn’t it remind you something? Aren’t we talking about hashes now? Isn’t it what we sometimes blame JavaScript for, that its objects are free-form with barely any reliable control over their structure? Thanks TypeScript for trying to get this fixed in some funky way, which I personally like more than dislike.

That’s when things clicked together. I was giving this answer already on a different occasion: using a class instance is often preferable over a hash. In the light of the JSON/API safety this simple rule gets us to another rather interesting aspect. Here is an example SmokeMachine provided on IRC:

to-json %( name => "{ .first-name } { .last-name }", 
           password => "***" )
    given $model

This was about returning basic user account information to a frontend. This is supposed to replace JSONification of a Red model like the following:

model Account {
    has UInt $.id is serial is json-skip;
    has Str $.username is column{ ... };
    has Str $.password is column{ ... } is json-skip;
    has Str $.first-name is column{ ... };
    has Str $.last-name is column{ ... };
}

The model example is mine.

By the way, in my opinion, neither first name nor last name do not belong to this model and must be part of a separate table where user’s personal data is kept. In more general case, a name must either be a long single field or an array where one can fit something like “Pablo Diego José Francisco de Paula Juan Nepomuceno María de los Remedios Cipriano de la Santísima Trinidad Ruiz y Picasso”.

The model clearly demonstrates the blacklist approach with two fields marked as non-JSONifiable. Now, let’s make it the right way, as I see it:

class API::Data::User {
    has Str:D $.username is required;
    has Str $.first-name;
    has Str $.last-name;

    method !FROM-MODEL($model) {
        self.new: username   => .username,
                  first-name => .first-name,
                  last-name  => .last-name
            given $model
    }

    multi method new(Account:D $model) {
        self!FROM-MODEL($model)
    }

    method COERCE(Account:D $model) {
        self!FROM-MODEL($model)
    }
}

And now, somewhere in our code we can do:

method get-user-info(UInt:D $id) {
    to-json API::Data::User(Account.^load: :$id)
}

With Cro::RPC::JSON module this could be part of a general API class which would provide common interface to both front- and backend:

use Cro::RPC::JSON;
class API::User {
    method get-user-info(UInt:D $id) is json-rpc {
        API::Data::User(Account.^load: :$id)
    }
}

With such an implementation our Raku backend would get an instance of API::Data::User. In a TypeScript frontend code of a private project of mine I have something like the following snippet, where connection is an object derived from jayson module:

connection.call("get-user-info", id).then(
    (user: User | undefined | null) => { ... }
);

What does it all eventually give us? First, API::Data::User provides the mechanism of whilelisting the fields we do want to expose in API. Note that with properly defined attributes we’re as explicit about that as only possible. And we do it declaratively one single place.

Second, the class prevents us from mistyping field names. It wouldn’t be possible to have something like %( usrname => $model.username, ... ) somewhere else in our codebase. Or, perhaps even more likely, to try %user<frst-name> and wonder where did the first name go? We also get the protection against wrong data types or undefined values.

It is also likely that working with a class instance would be faster than with a hash. I have this subject covered in another post of mine.

Heh, at some point I thought this post could fit into IRC format… 🤷

6guts: Raku multiple dispatch with the new MoarVM dispatcher

Published by jnthnwrthngtn on 2021-04-15T09:54:30

I recently wrote about the new MoarVM dispatch mechanism, and in that post noted that I still had a good bit of Raku’s multiple dispatch semantics left to implement in terms of it. Since then, I’ve made a decent amount of progress in that direction. This post contains an overview of the approach taken, and some very rough performance measurements.

My goodness, that’s a lot of semantics

Of all the kinds of dispatch we find in Raku, multiple dispatch is the most complex. Multiple dispatch allows us to write a set of candidates, which are then selected by the number of arguments:

multi ok($condition, $desc) {
    say ($condition ?? 'ok' !! 'not ok') ~ " - $desc";
}
multi ok($condition) {
    ok($condition, '');
}

Or the types of arguments:

multi to-json(Int $i) { ~$i }
multi to-json(Bool $b) { $b ?? 'true' !! 'false' }

And not just one argument, but potentially many:

multi truncate(Str $str, Int $chars) {
    $str.chars < $chars ?? $str !! $str.substr(0, $chars) ~ '...'
}
multi truncate(Str $str, Str $after) {
    with $str.index($after) -> $pos {
        $str.substr(0, $pos) ~ '...'
    }
    else {
        $str
    }
}

We may write where clauses to differentiate candidates on properties that are not captured by nominal types:

multi fac($n where $n <= 1) { 1 }
multi fac($n) { $n * fac($n - 1) }

Every time we write a set of multi candidates like this, the compiler will automatically produce a proto routine. This is what is installed in the symbol table, and holds the candidate list. However, we can also write our own proto, and use the special term {*} to decide at which point we do the dispatch, if at all.

proto mean($collection) {
    $collection.elems == 0 ?? Nil !! {*}
}
multi mean(@arr) {
    @arr.sum / @arr.elems
}
multi mean(%hash) {
    %hash.values.sum / %hash.elems
}

Candidates are ranked by narrowness (using topological sorting). If multiple candidates match, but they are equally narrow, then that’s an ambiguity error. Otherwise, we call narrowest one. The candidate we choose may then use callsame and friends to defer to the next narrowest candidate, which may do the same, until we reach the most general matching one.

Multiple dispatch is everywhere

Raku leans heavily on multiple dispatch. Most operators in Raku are compiled into calls to multiple dispatch subroutines. Even $a + $b will be a multiple dispatch. This means doing multiple dispatch efficiently is really important for performance. Given the riches of its semantics, this is potentially a bit concerning. However, there’s good news too.

Most multiple dispatches are boring

The overwhelmingly common case is that we have:

This isn’t to say the other cases are unimportant; they are really quite useful, and it’s desirable for them to perform well. However, it’s also desirable to make what savings we can in the common case. For example, we don’t want to eagerly calculate the full set of possible candidates for every single multiple dispatch, because the majority of the time only the first one matters. This is not just a time concern: recall that the new dispatch mechanism stores dispatch programs at each callsite, and if we store the list of all matching candidates at each of those, we’ll waste a lot of memory too.

How do we do today?

The situation in Rakudo today is as follows:

Effectively, the situation today is that you simply don’t use where clauses in a multiple dispatch if its anywhere near a hot path (well, and if you know where the hot paths are, and know that this kind of dispatch is slow). Ditto for callsame, although that’s less commonly reached for. The question is, can we do better with the new dispatcher?

Guard the types

Let’s start out with seeing how the simplest cases are dealt with, and build from there. (This is actually what I did in terms of the implementation, but at the same time I had a rough idea where I was hoping to end up.)

Recall this pair of candidates:

multi truncate(Str $str, Int $chars) {
    $str.chars < $chars ?? $str !! $str.substr(0, $chars) ~ '...'
}
multi truncate(Str $str, Str $after) {
    with $str.index($after) -> $pos {
        $str.substr(0, $pos) ~ '...'
    }
    else {
        $str
    }
}

We then have a call truncate($message, "\n"), where $message is a Str. Under the new dispatch mechanism, the call is made using the raku-call dispatcher, which identifies that this is a multiple dispatch, and thus delegates to raku-multi. (Multi-method dispatch ends up there too.)

The record phase of the dispatch – on the first time we reach this callsite – will proceed as follows:

  1. Iterate over the candidates
  2. If a candidate doesn’t match on argument count, just discard it. Since the shape of a callsite is a constant, and we calculate dispatch programs at each callsite, we don’t need to establish any guards for this.
  3. If it matches on types and concreteness, note which parameters are involved and what kinds of guards they need.
  4. If there was no match or an ambiguity, report the error without producing a dispatch program.
  5. Otherwise, having established the type guards, delegate to the raku-invoke dispatcher with the chosen candidate.

When we reach the same callsite again, we can run the dispatch program, which quickly checks if the argument types match those we saw last time, and if they do, we know which candidate to invoke. These checks are very cheap – far cheaper than walking through all of the candidates and examining each of them for a match. The optimizer may later be able to prove that the checks will always come out true and eliminate them.

Thus the whole of the dispatch processes – at least for this simple case where we only have types and arity – can be “explained” to the virtual machine as “if the arguments have these exact types, invoke this routine”. It’s pretty much the same as we were doing for method dispatch, except there we only cared about the type of the first argument – the invocant – and the value of the method name. (Also recall from the previous post that if it’s a multi-method dispatch, then both method dispatch and multiple dispatch will guard the type of the first argument, but the duplication is eliminated, so only one check is done.)

That goes in the resumption hole

Coming up with good abstractions is difficult, and therein lies much of the challenge of the new dispatch mechanism. Raku has quite a number of different dispatch-like things. However, encoding all of them directly in the virtual machine leads to high complexity, which makes building reliable optimizations (or even reliable unoptimized implementations!) challenging. Thus the aim is to work out a comparatively small set of primitives that allow for dispatches to be “explained” to the virtual machine in such a way that it can deliver decent performance.

It’s fairly clear that callsame is a kind of dispatch resumption, but what about the custom proto case and the where clause case? It turns out that these can both be neatly expressed in terms of dispatch resumption too (the where clause case needing one small addition at the virtual machine level, which in time is likely to be useful for other things too). Not only that, but encoding these features in terms of dispatch resumption is also quite direct, and thus should be efficient. Every trick we teach the specializer about doing better with dispatch resumptions can benefit all of the language features that are implemented using them, too.

Custom protos

Recall this example:

proto mean($collection) {
    $collection.elems == 0 ?? Nil !! {*}
}

Here, we want to run the body of the proto, and then proceed to the chosen candidate at the point of the {*}. By contrast, when we don’t have a custom proto, we’d like to simply get on with calling the correct multi.

To achieve this, I first moved the multi candidate selection logic from the raku-multi dispatcher to the raku-multi-core dispatcher. The raku-multi dispatcher then checks if we have an “onlystar” proto (one that does not need us to run it). If so, it delegates immediately to raku-multi-core. If not, it saves the arguments to the dispatch as the resumption initialization state, and then calls the proto. The proto‘s {*} is compiled into a dispatch resumption. The resumption then delegates to raku-multi-core. Or, in code:

nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-multi',
    # Initial dispatch, only setting up resumption if we need to invoke the
    # proto.
    -> $capture {
        my $callee := nqp::captureposarg($capture, 0);
        my int $onlystar := nqp::getattr_i($callee, Routine, '$!onlystar');
        if $onlystar {
            # Don't need to invoke the proto itself, so just get on with the
            # candidate dispatch.
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi-core', $capture);
        }
        else {
            # Set resume init args and run the proto.
            nqp::dispatch('boot-syscall', 'dispatcher-set-resume-init-args', $capture);
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-invoke', $capture);
        }
    },
    # Resumption means that we have reached the {*} in the proto and so now
    # should go ahead and do the dispatch. Make sure we only do this if we
    # are signalled to that it's a resume for an onlystar (resumption kind 5).
    -> $capture {
        my $track_kind := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 0);
        nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_kind);
        my int $kind := nqp::captureposarg_i($capture, 0);
        if $kind == 5 {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi-core',
                nqp::dispatch('boot-syscall', 'dispatcher-get-resume-init-args'));
        }
        elsif !nqp::dispatch('boot-syscall', 'dispatcher-next-resumption') {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-constant',
                nqp::dispatch('boot-syscall', 'dispatcher-insert-arg-literal-obj',
                    $capture, 0, Nil));
        }
    });

Two become one

Deferring to the next candidate (for example with callsame) and trying the next candidate because a where clause failed look very similar: both involve walking through a list of possible candidates. There’s some details, but they have a great deal in common, and it’d be nice if that could be reflected in how multiple dispatch is implemented using the new dispatcher.

Before that, a slightly terrible detail about how things work in Rakudo today when we have where clauses. First, the dispatcher does a “trial bind”, where it asks the question: would this signature bind? To do this, it has to evaluate all of the where clauses. Worse, it has to use the slow-path signature binder too, which interprets the signature, even though we can in many cases compile it. If the candidate matches, great, we select it, and then invoke it…which runs the where clauses a second time, as part of the compiled signature binding code. There is nothing efficient about this at all, except for it being by far more efficient on developer time, which is why it happened that way.

Anyway, it goes without saying that I’m rather keen to avoid this duplicate work and the slow-path binder where possible as I re-implement this using the new dispatcher. And, happily, a small addition provides a solution. There is an op assertparamcheck, which any kind of parameter checking compiles into (be it type checking, where clause checking, etc.) This triggers a call to a function that gets the arguments, the thing we were trying to call, and can then pick through them to produce an error message. The trick is to provide a way to invoke a routine such that a bind failure, instead of calling the error reporting function, will leave the routine and then do a dispatch resumption! This means we can turn failure to pass where clause checks into a dispatch resumption, which will then walk to the next candidate and try it instead.

Trivial vs. non-trivial

This gets us most of the way to a solution, but there’s still the question of being memory and time efficient in the common case, where there is no resumption and no where clauses. I coined the term “trivial multiple dispatch” for this situation, which makes the other situation “non-trivial”. In fact, I even made a dispatcher called raku-multi-non-trivial! There are two ways we can end up there.

  1. The initial attempt to find a matching candidate determines that we’ll have to consider where clauses. As soon as we see this is the case, we go ahead and produce a full list of possible candidates that could match. This is a linked list (see my previous post for why).
  2. The initial attempt to find a matching candidate finds one that can be picked based purely on argument count and nominal types. We stop there, instead of trying to build a full candidate list, and run the matching candidate. In the event that a callsame happens, we end up in the trivial dispatch resumption handler, which – since this situation is now non-trivial – builds the full candidate list, snips the first item off it (because we already ran that), and delegates to raku-multi-non-trivial.

Lost in this description is another significant improvement: today, when there are where clauses, we entirely lose the ability to use the MoarVM multiple dispatch cache, but under the new dispatcher, we store a type-filtered list of candidates at the callsite, and then cheap type guards are used to check it is valid to use.

Preliminary results

I did a few benchmarks to see how the new dispatch mechanism did with a couple of situations known to be sub-optimal in Rakudo today. These numbers do not reflect what is possible, because at the moment the specializer does not have much of an understanding of the new dispatcher. Rather, they reflect the minimal improvement we can expect.

Consider this benchmark using a multi with a where clause to recursively implement factorial.

multi fac($n where $n <= 1) { 1 }
multi fac($n) { $n * fac($n - 1) }
for ^100_000 {
    fac(10)
}
say now - INIT now;

This needs some tweaks (and to be run under an environment variable) to use the new dispatcher; these are temporary, until such a time I switch Rakudo over to using the new dispatcher by default:

use nqp;
multi fac($n where $n <= 1) { 1 }
multi fac($n) { $n * nqp::dispatch('raku-call', &fac, $n - 1) }
for ^100_000 {
    nqp::dispatch('raku-call', &fac, 10);
}
say now - INIT now;

On my machine, the first runs in 4.86s, the second in 1.34s. Thus under the new dispatcher this runs in little over a quarter of the time it used to – a quite significant improvement already.

A case involving callsame is also interesting to consider. Here it is without using the new dispatcher:

multi fallback(Any $x) { "a$x" }
multi fallback(Numeric $x) { "n" ~ callsame }
multi fallback(Real $x) { "r" ~ callsame }
multi fallback(Int $x) { "i" ~ callsame }
for ^1_000_000 {
    fallback(4+2i);
    fallback(4.2);
    fallback(42);
}   
say now - INIT now;

And with the temporary tweaks to use the new dispatcher:

use nqp;
multi fallback(Any $x) { "a$x" }
multi fallback(Numeric $x) { "n" ~ new-disp-callsame }
multi fallback(Real $x) { "r" ~ new-disp-callsame }
multi fallback(Int $x) { "i" ~ new-disp-callsame }
for ^1_000_000 {
    nqp::dispatch('raku-call', &fallback, 4+2i);
    nqp::dispatch('raku-call', &fallback, 4.2);
    nqp::dispatch('raku-call', &fallback, 42);
}
say now - INIT now;

On my machine, the first runs in 31.3s, the second in 11.5s, meaning that with the new dispatcher we manage it in a little over a third of the time that current Rakudo does.

These are both quite encouraging, but as previously mentioned, a majority of multiple dispatches are of the trivial kind, not using these features. If I make the most common case worse on the way to making other things better, that would be bad. It’s not yet possible to make a fair comparison of this: trivial multiple dispatches already receive a lot of attention in the specializer, and it doesn’t yet optimize code using the new dispatcher well. Of note, in an example like this:

multi m(Int) { }
multi m(Str) { }
for ^1_000_000 {
    m(1);
    m("x");
}
say now - INIT now;

Inlining and other optimizations will turn this into an empty loop, which is hard to beat. There is one thing we can already do, though: run it with the specializer disabled. The new dispatcher version looks like this:

use nqp;
multi m(Int) { }
multi m(Str) { }
for ^1_000_000 {
    nqp::dispatch('raku-call', &m, 1);
    nqp::dispatch('raku-call', &m, "x");
}
say now - INIT now;

The results are 0.463s and 0.332s respectively. Thus, the baseline execution time – before the specializer does its magic – is less using the new general dispatch mechanism than it is using the special-case multiple dispatch cache that we currently use. I wasn’t sure what to expect here before I did the measurement. Given we’re going from a specialized mechanism that has been profiled and tweaked to a new general mechanism that hasn’t received such attention, I was quite ready to be doing a little bit worse initially, and would have been happy with parity. Running in 70% of the time was a bigger improvement than I expected at this point.

I expect that once the specializer understands the new dispatch mechanism better, it will be able to also turn the above into an empty loop – however, since more iterations can be done per-optimization, this should still show up as a win for the new dispatcher.

Final thoughts

With one relatively small addition, the new dispatch mechanism is already handling most of the Raku multiple dispatch semantics. Furthermore, even without the specializer and JIT really being able to make a good job of it, some microbenchmarks already show a factor of 3x-4x improvement. That’s a pretty good starting point.

There’s still a good bit to do before we ship a Rakudo release using the new dispatcher. However, multiple dispatch was the biggest remaining threat to the design: it’s rather more involved than other kinds of dispatch, and it was quite possible that an unexpected shortcoming could trigger another round of design work, or reveal that the general mechanism was going to struggle to perform compared to the more specialized one in the baseline unoptimized, case. So far, there’s no indication of either of these, and I’m cautiously optimistic that the overall design is about right.

Pawel bbkr Pabian: Asynchronous, parallel and... dead. My Perl 6 daily bread.

Published by Pawel bbkr Pabian on 2015-09-06T14:00:56

I love Perl 6 asynchronous features. They are so easy to use and can give instant boost by changing few lines of code that I got addicted to them. I became asynchronous junkie. And finally overdosed. Here is my story...

I was processing a document that was divided into chapters, sub-chapters, sub-sub-chapters and so on. Parsed to data structure it looked like this:

    my %document = (
        '1' => {
            '1.1' => 'Lorem ipsum',
            '1.2' => {
                '1.2.1' => 'Lorem ipsum',
                '1.2.2' => 'Lorem ipsum'
            }
        },
        '2' => {
            '2.1' => {
                '2.1.1' => 'Lorem ipsum'
            }
        }
    );

Every chapter required processing of its children before it could be processed. Also processing of each chapter was quite time consuming - no matter which level it was and how many children did it have. So I started by writing recursive function to do it:

    sub process (%chapters) {
        for %chapters.kv -> $number, $content {
            note "Chapter $number started";
            &?ROUTINE.($content) if $content ~~ Hash;
            sleep 1; # here the chapter itself is processed
            note "Chapter $number finished";
        }
    }
    
    process(%document);

So nothing fancy here. Maybe except current &?ROUTINE variable which makes recursive code less error prone - there is no need to repeat subroutine name explicitly. After running it I got expected DFS (Depth First Search) flow:

    $ time perl6 run.pl
    Chapter 1 started
    Chapter 1.1 started
    Chapter 1.1 finished
    Chapter 1.2 started
    Chapter 1.2.1 started
    Chapter 1.2.1 finished
    Chapter 1.2.2 started
    Chapter 1.2.2 finished
    Chapter 1.2 finished
    Chapter 1 finished
    Chapter 2 started
    Chapter 2.1 started
    Chapter 2.1.1 started
    Chapter 2.1.1 finished
    Chapter 2.1 finished
    Chapter 2 finished
    
    real    0m8.184s

It worked perfectly, but that was too slow. Because 1 second was required to process each chapter in serial manner it ran for 8 seconds total. So without hesitation I reached for Perl 6 asynchronous goodies to process chapters in parallel.

    sub process (%chapters) {
        await do for %chapters.kv -> $number, $content {
            start {
                note "Chapter $number started";
                &?ROUTINE.outer.($content) if $content ~~ Hash;
                sleep 1; # here the chapter itself is processed
                note "Chapter $number finished";
            }
        }
    }
    
    process(%document);

Now every chapter is processed asynchronously in parallel and first waits for its children to be also processed asynchronously in parallel. Note that after wrapping processing in await/start construct &?ROUTINE must now point to outer scope.

    $ time perl6 run.pl
    Chapter 1 started
    Chapter 2 started
    Chapter 1.1 started
    Chapter 1.2 started
    Chapter 2.1 started
    Chapter 1.2.1 started
    Chapter 2.1.1 started
    Chapter 1.2.2 started
    Chapter 1.1 finished
    Chapter 1.2.1 finished
    Chapter 1.2.2 finished
    Chapter 2.1.1 finished
    Chapter 2.1 finished
    Chapter 1.2 finished
    Chapter 1 finished
    Chapter 2 finished
    
    real    0m3.171s

Perfect. Time dropped to expected 3 seconds - it was not possible to go any faster because document had 3 nesting levels and each required 1 second to process. Still smiling I threw bigger document at my beautiful script - 10 chapters, each with 10 sub-chapters, each with 10 sub-sub-chapters. It started processing, run for a while... and DEADLOCKED.

Friedrich Nietzsche said that "when you gaze long into an abyss the abyss also gazes into you". Same rule applies to code. After few minutes me and my code were staring at each other. And I couldn't find why it worked perfectly for small documents but was deadlocking in random moments for big ones. Half an hour later I blinked and got defeated by my own code in staring contest. So it was time for debugging.

I noticed that when it was deadlocking there was always constant amount of 16 chapters that were still in progress. And that number looked familiar to me - thread pool!

    $ perl6 -e 'say start { }'
    Promise.new(
        scheduler => ThreadPoolScheduler.new(
            initial_threads => 0,
            max_threads => 16,
            uncaught_handler => Callable
        ),
        status => PromiseStatus::Kept
    )

Every asynchronous task that is planned needs free thread so it can be executed. And on my system only 16 concurrent threads are allowed as shown above. To analyze what happened let's use document from first example but also assume thread pool is limited to 4:

    $ perl6 run.pl          # 4 threads available by default
    Chapter 1 started       # 3 threads available
    Chapter 1.1 started     # 2 threads available
    Chapter 2 started       # 1 thread available
    Chapter 1.1 finished    # 2 threads available again
    Chapter 1.2 started     # 1 thread available
    Chapter 1.2.1 started   # 0 threads available
                            # deadlock!

At this moment chapter 1 subtree holds three threads and waits for one more for chapter 1.2.2 to complete everything and start ascending from recursion. And subtree of chapter 2 holds one thread and waits for one more for chapter 2.1 to descend into recursion. In result processing gets to a point where at least one more thread is required to proceed but all threads are taken and none can be returned to thread pool. Script deadlocks and stops here forever.

How to solve this problem and maintain parallel processing? There are many ways to do it :)
The key to the solution is to process asynchronously only those chapters that do not have unprocessed chapters on lower level.

Luckily Perl 6 offers perfect tool - promise junctions. It is possible to create a promise that waits for other promises to be kept and until it happens it is not sent to thread pool for execution. Following code illustrates that:

    my $p = Promise.allof( Promise.in(2), Promise.in(3) );
    sleep 1;
    say "Promise after 1 second: " ~ $p.perl;
    sleep 3;
    say "Promise after 4 seconds: " ~ $p.perl;

Prints:

    Promise after 1 second: Promise.new(
        ..., status => PromiseStatus::Planned
    )
    Promise after 4 seconds: Promise.new(
        ..., status => PromiseStatus::Kept
    )

Let's rewrite processing using this cool property:

    sub process (%chapters) {
        return Promise.allof(
            do for %chapters.kv -> $number, $content {
                my $current = {
                    note "Chapter $number started";
                    sleep 1; # here the chapter itself is processed
                    note "Chapter $number finished";
                };
                
                if $content ~~ Hash {
                    Promise.allof( &?ROUTINE.($content) )
                        .then( $current );
                }
                else {
                    Promise.start( $current );
                }
            }
        );
    }
    
    await process(%document);

It solves the problem when chapter was competing with its sub-chapters for free threads but at the same time it needed those sub-chapters before it can process itself. Now awaiting for sub-chapters to complete does not require free thread. Let's run it:

    $ perl6 run.pl
    Chapter 1.1 started
    Chapter 1.2.1 started
    Chapter 1.2.2 started
    Chapter 2.1.1 started
    -
    Chapter 1.1 finished
    Chapter 1.2.1 finished
    Chapter 1.2.2 finished
    Chapter 1.2 started
    Chapter 2.1.1 finished
    Chapter 2.1 started
    -
    Chapter 1.2 finished
    Chapter 1 started
    Chapter 2.1 finished
    Chapter 2 started
    -
    Chapter 1 finished
    Chapter 2 finished
    
    real    0m3.454s

I've added separator for each second passed so it is easier to understand. When script starts chapters 1.1, 1.2.1, 1.2.2 and 2.1.1 do not have sub-chapters at all. So they can take threads from thread pool immediately. When they are completed after one second then Promises that were awaiting for all of them are kept and chapters 1.2 and 2.1 can be processed safely on thread pool. It keeps going until getting out of recursion.

After trying big document again it was processed flawlessly in 72 seconds instead of linear 1000.

I'm high on asynchronous processing again!

You can download script here and try different data sizes and algorithms for yourself (params are taken from command line).

6guts: Towards a new general dispatch mechanism in MoarVM

Published by jnthnwrthngtn on 2021-03-15T02:08:42

My goodness, it appears I’m writing my first Raku internals blog post in over two years. Of course, two years ago it wasn’t even called Raku. Anyway, without further ado, let’s get on with this shared brainache.

What is dispatch?

I use “dispatch” to mean a process by which we take a set of arguments and end up with some action being taken based upon them. Some familiar examples include:

At first glance, perhaps the first two seem fairly easy and the third a bit more of a handful – which is sort of true. However, Raku has a number of other features that make dispatch rather more, well, interesting. For example:

Thanks to this, dispatch – at least in Raku – is not always something we do and produce an outcome, but rather a process that we may be asked to continue with multiple times!

Finally, while the examples I’ve written above can all quite clearly be seen as examples of dispatch, a number of other common constructs in Raku can be expressed as a kind of dispatch too. Assignment is one example: the semantics of it depend on the target of the assignment and the value being assigned, and thus we need to pick the correct semantics. Coercion is another example, and return value type-checking yet another.

Why does dispatch matter?

Dispatch is everywhere in our programs, quietly tieing together the code that wants stuff done with the code that does stuff. Its ubiquity means it plays a significant role in program performance. In the best case, we can reduce the cost to zero. In the worst case, the cost of the dispatch is high enough to exceed that of the work done as a result of the dispatch.

To a first approximation, when the runtime “understands” the dispatch the performance tends to be at least somewhat decent, but when it doesn’t there’s a high chance of it being awful. Dispatches tend to involve an amount of work that can be cached, often with some cheap guards to verify the validity of the cached outcome. For example, in a method dispatch, naively we need to walk a linearization of the inheritance graph and ask each class we encounter along the way if it has a method of the specified name. Clearly, this is not going to be terribly fast if we do it on every method call. However, a particular method name on a particular type (identified precisely, without regard to subclassing) will resolve to the same method each time. Thus, we can cache the outcome of the lookup, and use it whenever the type of the invocant matches that used to produce the cached result.

Specialized vs. generalized mechanisms in language runtimes

When one starts building a runtime aimed at a particular language, and has to do it on a pretty tight budget, the most obvious way to get somewhat tolerable performance is to bake various hot-path language semantics into the runtime. This is exactly how MoarVM started out. Thus, if we look at MoarVM as it stood several years ago, we find things like:

These are all still there today, however are also all on the way out. What’s most telling about this list is what isn’t included. Things like:

A few years back I started to partially address this, with the introduction of a mechanism I called “specializer plugins”. But first, what is the specializer?

When MoarVM started out, it was a relatively straightforward interpreter of bytecode. It only had to be fast enough to beat the Parrot VM in order to get a decent amount of usage, which I saw as important to have before going on to implement some more interesting optimizations (back then we didn’t have the kind of pre-release automated testing infrastructure we have today, and so depended much more on feedback from early adopters). Anyway, soon after being able to run pretty much as much of the Raku language as any other backend, I started on the dynamic optimizer. It gathered type statistics as the program was interpreted, identified hot code, put it into SSA form, used the type statistics to insert guards, used those together with static properties of the bytecode to analyze and optimize, and produced specialized bytecode for the function in question. This bytecode could elide type checks and various lookups, as well as using a range of internal ops that make all kinds of assumptions, which were safe because of the program properties that were proved by the optimizer. This is called specialized bytecode because it has had a lot of its genericity – which would allow it to work correctly on all types of value that we might encounter – removed, in favor of working in a particular special case that actually occurs at runtime. (Code, especially in more dynamic languages, is generally far more generic in theory than it ever turns out to be in practice.)

This component – the specializer, known internally as “spesh” – delivered a significant further improvement in the performance of Raku programs, and with time its sophistication has grown, taking in optimizations such as inlining and escape analysis with scalar replacement. These aren’t easy things to build – but once a runtime has them, they create design possibilities that didn’t previously exist, and make decisions made in their absence look sub-optimal.

Of note, those special-cased language-specific mechanisms, baked into the runtime to get some speed in the early days, instead become something of a liability and a bottleneck. They have complex semantics, which means they are either opaque to the optimizer (so it can’t reason about them, meaning optimization is inhibited) or they need special casing in the optimizer (a liability).

So, back to specializer plugins. I reached a point where I wanted to take on the performance of things like $obj.?meth (the “call me maybe” dispatch), $obj.SomeType::meth() (dispatch qualified with a class to start looking in), and private method calls in roles (which can’t be resolved statically). At the same time, I was getting ready to implement some amount of escape analysis, but realized that it was going to be of very limited utility because assignment had also been special-cased in the VM, with a chunk of opaque C code doing the hot path stuff.

But why did we have the C code doing that hot-path stuff? Well, because it’d be too espensive to have every assignment call a VM-level function that does a bunch of checks and logic. Why is that costly? Because of function call overhead and the costs of interpretation. This was all true once upon a time. But, some years of development later:

I solved the assignment problem and the dispatch problems mentioned above with the introduction of a single new mechanism: specializer plugins. They work as follows:

The vast majority of cases are monomorphic, meaning that only one set of guards are produced and they always succeed thereafter. The specializer can thus compile those guards into the specialized bytecode and then assume the given target invocant is what will be invoked. (Further, duplicate guards can be eliminated, so the guards a particular plugin introduces may reduce to zero.)

Specializer plugins felt pretty great. One new mechanism solved multiple optimization headaches.

The new MoarVM dispatch mechanism is the answer to a fairly simple question: what if we get rid of all the dispatch-related special-case mechanisms in favor of something a bit like specializer plugins? The resulting mechanism would need to be a more powerful than specializer plugins. Further, I could learn from some of the shortcomings of specializer plugins. Thus, while they will go away after a relatively short lifetime, I think it’s fair to say that I would not have been in a place to design the new MoarVM dispatch mechanism without that experience.

The dispatch op and the bootstrap dispatchers

All the method caching. All the multi dispatch caching. All the specializer plugins. All the invocation protocol stuff for unwrapping the bytecode handle in a code object. It’s all going away, in favor of a single new dispatch instruction. Its name is, boringly enough, dispatch. It looks like this:

dispatch_o result, 'dispatcher-name', callsite, arg0, arg1, ..., argN

Which means:

(Aside: this implies a new calling convention, whereby we no longer copy the arguments into an argument buffer, but instead pass the base of the register set and a pointer into the bytecode where the register argument map is found, and then do a lookup registers[map[argument_index]] to get the value for an argument. That alone is a saving when we interpret, because we no longer need a loop around the interpreter per argument.)

Some of the arguments might be things we’d traditionally call arguments. Some are aimed at the dispatch process itself. It doesn’t really matter – but it is more optimal if we arrange to put arguments that are only for the dispatch first (for example, the method name), and those for the target of the dispatch afterwards (for example, the method parameters).

The new bootstrap mechanism provides a small number of built-in dispatchers, whose names start with “boot-“. They are:

That’s pretty much it. Every dispatcher we build, to teach the runtime about some other kind of dispatch behavior, eventually terminates in one of these.

Building on the bootstrap

Teaching MoarVM about different kinds of dispatch is done using nothing less than the dispatch mechanism itself! For the most part, boot-syscall is used in order to register a dispatcher, set up the guards, and provide the result that goes with them.

Here is a minimal example, taken from the dispatcher test suite, showing how a dispatcher that provides the identity function would look:

nqp::dispatch('boot-syscall', 'dispatcher-register', 'identity', -> $capture {
    nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-value', $capture);
});
sub identity($x) {
    nqp::dispatch('identity', $x)
}
ok(identity(42) == 42, 'Can define identity dispatch (1)');
ok(identity('foo') eq 'foo', 'Can define identity dispatch (2)');

In the first statement, we call the dispatcher-register MoarVM system call, passing a name for the dispatcher along with a closure, which will be called each time we need to handle the dispatch (which I tend to refer to as the “dispatch callback”). It receives a single argument, which is a capture of arguments (not actually a Raku-level Capture, but the idea – an object containing a set of call arguments – is the same).

Every user-defined dispatcher should eventually use dispatcher-delegate in order to identify another dispatcher to pass control along to. In this case, it delegates immediately to boot-value – meaning it really is nothing except a wrapper around the boot-value built-in dispatcher.

The sub identity contains a single static occurrence of the dispatch op. Given we call the sub twice, we will encounter this op twice at runtime, but the two times are very different.

The first time is the “record” phase. The arguments are formed into a capture and the callback runs, which in turn passes it along to the boot-value dispatcher, which produces the result. This results in an extremely simple dispatch program, which says that the result should be the first argument in the capture. Since there’s no guards, this will always be a valid result.

The second time we encounter the dispatch op, it already has a dispatch program recorded there, so we are in run mode. Turning on a debugging mode in the MoarVM source, we can see the dispatch program that results looks like this:

Dispatch program (1 temporaries)
  Ops:
    Load argument 0 into temporary 0
    Set result object value from temporary 0

That is, it reads argument 0 into a temporary location and then sets that as the result of the dispatch. Notice how there is no mention of the fact that we went through an extra layer of dispatch; those have zero cost in the resulting dispatch program.

Capture manipulation

Argument captures are immutable. Various VM syscalls exist to transform them into new argument captures with some tweak, for example dropping or inserting arguments. Here’s a further example from the test suite:

nqp::dispatch('boot-syscall', 'dispatcher-register', 'drop-first', -> $capture {
    my $capture-derived := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg', $capture, 0);
    nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-value', $capture-derived);
});
ok(nqp::dispatch('drop-first', 'first', 'second') eq 'second',
    'dispatcher-drop-arg works');

This drops the first argument before passing the capture on to the boot-value dispatcher – meaning that it will return the second argument. Glance back at the previous dispatch program for the identity function. Can you guess how this one will look?

Well, here it is:

Dispatch program (1 temporaries)
  Ops:
    Load argument 1 into temporary 0
    Set result string value from temporary 0

Again, while in the record phase of such a dispatcher we really do create capture objects and make a dispatcher delegation, the resulting dispatch program is far simpler.

Here’s a slightly more involved example:

my $target := -> $x { $x + 1 }
nqp::dispatch('boot-syscall', 'dispatcher-register', 'call-on-target', -> $capture {
    my $capture-derived := nqp::dispatch('boot-syscall',
            'dispatcher-insert-arg-literal-obj', $capture, 0, $target);
    nqp::dispatch('boot-syscall', 'dispatcher-delegate',
            'boot-code-constant', $capture-derived);
});
sub cot() { nqp::dispatch('call-on-target', 49) }
ok(cot() == 50,
    'dispatcher-insert-arg-literal-obj works at start of capture');
ok(cot() == 50,
    'dispatcher-insert-arg-literal-obj works at start of capture after link too');

Here, we have a closure stored in a variable $target. We insert it as the first argument of the capture, and then delegate to boot-code-constant, which will invoke that code object and pass the other dispatch arguments to it. Once again, at the record phase, we really do something like:

And the resulting dispatch program? It’s this:

Dispatch program (1 temporaries)
  Ops:
    Load collectable constant at index 0 into temporary 0
    Skip first 0 args of incoming capture; callsite from 0
    Invoke MVMCode in temporary 0

That is, load the constant bytecode handle that we’re going to invoke, set up the args (which are in this case equal to those of the incoming capture), and then invoke the bytecode with those arguments. The argument shuffling is, once again, gone. In general, whenever the arguments we do an eventual bytecode invocation with are a tail of the initial dispatch arguments, the arguments transform becomes no more than a pointer addition.

Guards

All of the dispatch programs seen so far have been unconditional: once recorded at a given callsite, they shall always be used. The big missing piece to make such a mechanism have practical utility is guards. Guards assert properties such as the type of an argument or if the argument is definite (Int:D) or not (Int:U).

Here’s a somewhat longer test case, with some explanations placed throughout it.

# A couple of classes for test purposes
my class C1 { }
my class C2 { }

# A counter used to make sure we're only invokving the dispatch callback as
# many times as we expect.
my $count := 0;

# A type-name dispatcher that maps a type into a constant string value that
# is its name. This isn't terribly useful, but it is a decent small example.
nqp::dispatch('boot-syscall', 'dispatcher-register', 'type-name', -> $capture {
    # Bump the counter, just for testing purposes.
    $count++;

    # Obtain the value of the argument from the capture (using an existing
    # MoarVM op, though in the future this may go away in place of a syscall)
    # and then obtain the string typename also.
    my $arg-val := nqp::captureposarg($capture, 0);
    my str $name := $arg-val.HOW.name($arg-val);

    # This outcome is only going to be valid for a particular type. We track
    # the argument (which gives us an object back that we can use to guard
    # it) and then add the type guard.
    my $arg := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 0);
    nqp::dispatch('boot-syscall', 'dispatcher-guard-type', $arg);

    # Finally, insert the type name at the start of the capture and then
    # delegate to the boot-constant dispatcher.
    nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-constant',
        nqp::dispatch('boot-syscall', 'dispatcher-insert-arg-literal-str',
            $capture, 0, $name));
});

# A use of the dispatch for the tests. Put into a sub so there's a single
# static dispatch op, which all dispatch programs will hang off.
sub type-name($obj) {
    nqp::dispatch('type-name', $obj)
}

# Check with the first type, making sure the guard matches when it should
# (although this test would pass if the guard were ignored too).
ok(type-name(C1) eq 'C1', 'Dispatcher setting guard works');
ok($count == 1, 'Dispatch callback ran once');
ok(type-name(C1) eq 'C1', 'Can use it another time with the same type');
ok($count == 1, 'Dispatch callback was not run again');

# Test it with a second type, both record and run modes. This ensures the
# guard really is being checked.
ok(type-name(C2) eq 'C2', 'Can handle polymorphic sites when guard fails');
ok($count == 2, 'Dispatch callback ran a second time for new type');
ok(type-name(C2) eq 'C2', 'Second call with new type works');

# Check that we can use it with the original type too, and it has stacked
# the dispatch programs up at the same callsite.
ok(type-name(C1) eq 'C1', 'Call with original type still works');
ok($count == 2, 'Dispatch callback only ran a total of 2 times');

This time two dispatch programs get produced, one for C1:

Dispatch program (1 temporaries)
  Ops:
    Guard arg 0 (type=C1)
    Load collectable constant at index 1 into temporary 0
    Set result string value from temporary 0

And another for C2:

Dispatch program (1 temporaries)
  Ops:
    Guard arg 0 (type=C2)
    Load collectable constant at index 1 into temporary 0
    Set result string value from temporary 0

Once again, no leftovers from capture manipulation, tracking, or dispatcher delegation; the dispatch program does a type guard against an argument, then produces the result string. The whole call to $arg-val.HOW.name($arg-val) is elided, the dispatcher we wrote encoding the knowledge – in a way that the VM can understand – that a type’s name can be considered immutable.

This example is a bit contrived, but now consider that we instead look up a method and guard on the invocant type: that’s a method cache! Guard the types of more of the arguments, and we have a multi cache! Do both, and we have a multi-method cache.

The latter is interesting in so far as both the method dispatch and the multi dispatch want to guard on the invocant. In fact, in MoarVM today there will be two such type tests until we get to the point where the specializer does its work and eliminates these duplicated guards. However, the new dispatcher does not treat the dispatcher-guard-type as a kind of imperative operation that writes a guard into the resultant dispatch program. Instead, it declares that the argument in question must be guarded. If some other dispatcher already did that, it’s idempotent. The guards are emitted once all dispatch programs we delegate through, on the path to a final outcome, have had their say.

Fun aside: those being especially attentive will have noticed that the dispatch mechanism is used as part of implementing new dispatchers too, and indeed, this ultimately will mean that the specializer can specialize the dispatchers and have them JIT-compiled into something more efficient too. After all, from the perspective of MoarVM, it’s all just bytecode to run; it’s just that some of it is bytecode that tells the VM how to execute Raku programs more efficiently!

Dispatch resumption

A resumable dispatcher needs to do two things:

  1. Provide a resume callback as well as a dispatch one when registering the dispatcher
  2. In the dispatch callback, specify a capture, which will form the resume initialization state

When a resumption happens, the resume callback will be called, with any arguments for the resumption. It can also obtain the resume initialization state that was set in the dispatch callback. The resume initialization state contains the things needed in order to continue with the dispatch the first time it is resumed. We’ll take a look at how this works for method dispatch to see a concrete example. I’ll also, at this point, switch to looking at the real Rakudo dispatchers, rather than simplified test cases.

The Rakudo dispatchers take advantage of delegation, duplicate guards, and capture manipulations all having no runtime cost in the resulting dispatch program to, in my mind at least, quite nicely factor what is a somewhat involved dispatch process. There are multiple entry points to method dispatch: the normal boring $obj.meth(), the qualified $obj.Type::meth(), and the call me maybe $obj.?meth(). These have common resumption semantics – or at least, they can be made to provided we always carry a starting type in the resume initialization state, which is the type of the object that we do the method dispatch on.

Here is the entry point to dispatch for a normal method dispatch, with the boring details of reporting missing method errors stripped out.

# A standard method call of the form $obj.meth($arg); also used for the
# indirect form $obj."$name"($arg). It receives the decontainerized invocant,
# the method name, and the the args (starting with the invocant including any
# container).
nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-meth-call', -> $capture {
    # Try to resolve the method call using the MOP.
    my $obj := nqp::captureposarg($capture, 0);
    my str $name := nqp::captureposarg_s($capture, 1);
    my $meth := $obj.HOW.find_method($obj, $name);

    # Report an error if there is no such method.
    unless nqp::isconcrete($meth) {
        !!! 'Error reporting logic elided for brevity';
    }

    # Establish a guard on the invocant type and method name (however the name
    # may well be a literal, in which case this is free).
    nqp::dispatch('boot-syscall', 'dispatcher-guard-type',
        nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 0));
    nqp::dispatch('boot-syscall', 'dispatcher-guard-literal',
        nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $capture, 1));

    # Add the resolved method and delegate to the resolved method dispatcher.
    my $capture-delegate := nqp::dispatch('boot-syscall',
        'dispatcher-insert-arg-literal-obj', $capture, 0, $meth);
    nqp::dispatch('boot-syscall', 'dispatcher-delegate',
        'raku-meth-call-resolved', $capture-delegate);
});

Now for the resolved method dispatcher, which is where the resumption is handled. First, let’s look at the normal dispatch callback (the resumption callback is included but empty; I’ll show it a little later).

# Resolved method call dispatcher. This is used to call a method, once we have
# already resolved it to a callee. Its first arg is the callee, the second and
# third are the type and name (used in deferral), and the rest are the args to
# the method.
nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-meth-call-resolved',
    # Initial dispatch
    -> $capture {
        # Save dispatch state for resumption. We don't need the method that will
        # be called now, so drop it.
        my $resume-capture := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg',
            $capture, 0);
        nqp::dispatch('boot-syscall', 'dispatcher-set-resume-init-args', $resume-capture);

        # Drop the dispatch start type and name, and delegate to multi-dispatch or
        # just invoke if it's single dispatch.
        my $delegate_capture := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg',
            nqp::dispatch('boot-syscall', 'dispatcher-drop-arg', $capture, 1), 1);
        my $method := nqp::captureposarg($delegate_capture, 0);
        if nqp::istype($method, Routine) && $method.is_dispatcher {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi', $delegate_capture);
        }
        else {
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-invoke', $delegate_capture);
        }
    },
    # Resumption
    -> $capture {
        ... 'Will be shown later';
    });

There’s an arguable cheat in raku-meth-call: it doesn’t actually insert the type object of the invocant in place of the invocant. It turns out that it doesn’t really matter. Otherwise, I think the comments (which are to be found in the real implementation also) tell the story pretty well.

One important point that may not be clear – but follows a repeating theme – is that the setting of the resume initialization state is also more of a declarative rather than an imperative thing: there isn’t a runtime cost at the time of the dispatch, but rather we keep enough information around in order to be able to reconstruct the resume initialization state at the point we need it. (In fact, when we are in the run phase of a resume, we don’t even have to reconstruct it in the sense of creating a capture object.)

Now for the resumption. I’m going to present a heavily stripped down version that only deals with the callsame semantics (the full thing has to deal with such delights as lastcall and nextcallee too). The resume initialization state exists to seed the resumption process. Once we know we actually do have to deal with resumption, we can do things like calculating the full list of methods in the inheritance graph that we want to walk through. Each resumable dispatcher gets a single storage slot on the call stack that it can use for its state. It can initialize this in the first step of resumption, and then update it as we go. Or more precisely, it can set up a dispatch program that will do this when run.

A linked list turns out to be a very convenient data structure for the chain of candidates we will walk through. We can work our way through a linked list by keeping track of the current node, meaning that there need only be a single thing that mutates, which is the current state of the dispatch. The dispatch program mechanism also provides a way to read an attribute from an object, and that is enough to express traversing a linked list into the dispatch program. This also means zero allocations.

So, without further ado, here is the linked list (rather less pretty in NQP, the restricted Raku subset, than it would be in full Raku):

# A linked list is used to model the state of a dispatch that is deferring
# through a set of methods, multi candidates, or wrappers. The Exhausted class
# is used as a sentinel for the end of the chain. The current state of the
# dispatch points into the linked list at the appropriate point; the chain
# itself is immutable, and shared over (runtime) dispatches.
my class DeferralChain {
    has $!code;
    has $!next;
    method new($code, $next) {
        my $obj := nqp::create(self);
        nqp::bindattr($obj, DeferralChain, '$!code', $code);
        nqp::bindattr($obj, DeferralChain, '$!next', $next);
        $obj
    }
    method code() { $!code }
    method next() { $!next }
};
my class Exhausted {};

And finally, the resumption handling.

nqp::dispatch('boot-syscall', 'dispatcher-register', 'raku-meth-call-resolved',
    # Initial dispatch
    -> $capture {
        ... 'Presented earlier;
    },
    # Resumption. The resume init capture's first two arguments are the type
    # that we initially did a method dispatch against and the method name
    # respectively.
    -> $capture {
        # Work out the next method to call, if any. This depends on if we have
        # an existing dispatch state (that is, a method deferral is already in
        # progress).
        my $init := nqp::dispatch('boot-syscall', 'dispatcher-get-resume-init-args');
        my $state := nqp::dispatch('boot-syscall', 'dispatcher-get-resume-state');
        my $next_method;
        if nqp::isnull($state) {
            # No state, so just starting the resumption. Guard on the
            # invocant type and name.
            my $track_start_type := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $init, 0);
            nqp::dispatch('boot-syscall', 'dispatcher-guard-type', $track_start_type);
            my $track_name := nqp::dispatch('boot-syscall', 'dispatcher-track-arg', $init, 1);
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_name);

            # Also guard on there being no dispatch state.
            my $track_state := nqp::dispatch('boot-syscall', 'dispatcher-track-resume-state');
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_state);

            # Build up the list of methods to defer through.
            my $start_type := nqp::captureposarg($init, 0);
            my str $name := nqp::captureposarg_s($init, 1);
            my @mro := nqp::can($start_type.HOW, 'mro_unhidden')
                ?? $start_type.HOW.mro_unhidden($start_type)
                !! $start_type.HOW.mro($start_type);
            my @methods;
            for @mro {
                my %mt := nqp::hllize($_.HOW.method_table($_));
                if nqp::existskey(%mt, $name) {
                    @methods.push(%mt{$name});
                }
            }

            # If there's nothing to defer to, we'll evaluate to Nil (just don't set
            # the next method, and it happens below).
            if nqp::elems(@methods) >= 2 {
                # We can defer. Populate next method.
                @methods.shift; # Discard the first one, which we initially called
                $next_method := @methods.shift; # The immediate next one

                # Build chain of further methods and set it as the state.
                my $chain := Exhausted;
                while @methods {
                    $chain := DeferralChain.new(@methods.pop, $chain);
                }
                nqp::dispatch('boot-syscall', 'dispatcher-set-resume-state-literal', $chain);
            }
        }
        elsif !nqp::istype($state, Exhausted) {
            # Already working through a chain of method deferrals. Obtain
            # the tracking object for the dispatch state, and guard against
            # the next code object to run.
            my $track_state := nqp::dispatch('boot-syscall', 'dispatcher-track-resume-state');
            my $track_method := nqp::dispatch('boot-syscall', 'dispatcher-track-attr',
                $track_state, DeferralChain, '$!code');
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_method);

            # Update dispatch state to point to next method.
            my $track_next := nqp::dispatch('boot-syscall', 'dispatcher-track-attr',
                $track_state, DeferralChain, '$!next');
            nqp::dispatch('boot-syscall', 'dispatcher-set-resume-state', $track_next);

            # Set next method, which we shall defer to.
            $next_method := $state.code;
        }
        else {
            # Dispatch already exhausted; guard on that and fall through to returning
            # Nil.
            my $track_state := nqp::dispatch('boot-syscall', 'dispatcher-track-resume-state');
            nqp::dispatch('boot-syscall', 'dispatcher-guard-literal', $track_state);
        }

        # If we found a next method...
        if nqp::isconcrete($next_method) {
            # Call with same (that is, original) arguments. Invoke with those.
            # We drop the first two arguments (which are only there for the
            # resumption), add the code object to invoke, and then leave it
            # to the invoke or multi dispatcher.
            my $just_args := nqp::dispatch('boot-syscall', 'dispatcher-drop-arg',
                nqp::dispatch('boot-syscall', 'dispatcher-drop-arg', $init, 0),
                0);
            my $delegate_capture := nqp::dispatch('boot-syscall',
                'dispatcher-insert-arg-literal-obj', $just_args, 0, $next_method);
            if nqp::istype($next_method, Routine) && $next_method.is_dispatcher {
                nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-multi',
                        $delegate_capture);
            }
            else {
                nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'raku-invoke',
                        $delegate_capture);
            }
        }
        else {
            # No method, so evaluate to Nil (boot-constant disregards all but
            # the first argument).
            nqp::dispatch('boot-syscall', 'dispatcher-delegate', 'boot-constant',
                nqp::dispatch('boot-syscall', 'dispatcher-insert-arg-literal-obj',
                    $capture, 0, Nil));
        }
    });

That’s quite a bit to take in, and quite a bit of code. Remember, however, that this is only run for the record phase of a dispatch resumption. It also produces a dispatch program at the callsite of the callsame, with the usual guards and outcome. Implicit guards are created for the dispatcher that we are resuming at that point. In the most common case this will end up monomorphic or bimorphic, although situations involving nestings of multiple dispatch or method dispatch could produce a more morphic callsite.

The design I’ve picked forces resume callbacks to deal with two situations: the first resumption and the latter resumptions. This is not ideal in a couple of ways:

  1. It’s a bit inconvenient for those writing dispatch resume callbacks. However, it’s not like this is a particularly common activity!
  2. The difference results in two dispatch programs being stacked up at a callsite that might otherwise get just one

Only the second of these really matters. The reason for the non-uniformity is to make sure that the overwhelming majority of calls, which never lead to a dispatch resumption, incur no per-dispatch cost for a feature that they never end up using. If the result is a little more cost for those using the feature, so be it. In fact, early benchmarking shows callsame with wrap and method calls seems to be up to 10 times faster using the new dispatcher than in current Rakudo, and that’s before the specializer understands enough about it to improve things further!

What’s done so far

Everything I’ve discussed above is implemented, except that I may have given the impression somewhere that multiple dispatch is fully implemented using the new dispatcher, and that is not the case yet (no handling of where clauses and no dispatch resumption support).

Next steps

Getting the missing bits of multiple dispatch fully implemented is the obvious next step. The other missing semantic piece is support for callwith and nextwith, where we wish to change the arguments that are being used when moving to the next candidate. A few other minor bits aside, that in theory will get all of the Raku dispatch semantics at least supported.

Currently, all standard method calls ($obj.meth()) and other calls (foo() and $foo()) go via the existing dispatch mechanism, not the new dispatcher. Those will need to be migrated to use the new dispatcher also, and any bugs that are uncovered will need fixing. That will get things to the point where the new dispatcher is semantically ready.

After that comes performance work: making sure that the specializer is able to deal with dispatch program guards and outcomes. The goal, initially, is to get steady state performance of common calling forms to perform at least as well as in the current master branch of Rakudo. It’s already clear enough there will be some big wins for some things that to date have been glacial, but it should not come at the cost of regression on the most common kinds of dispatch, which have received plenty of optimization effort before now.

Furthermore, NQP – the restricted form of Raku that the Rakudo compiler and other bits of the runtime guts are written in – also needs to be migrated to use the new dispatcher. Only when that is done will it be possible to rip out the current method cache, multiple dispatch cache, and so forth from MoarVM.

An open question is how to deal with backends other than MoarVM. Ideally, the new dispatch mechanism will be ported to those. A decent amount of it should be possible to express in terms of the JVM’s invokedynamic (and this would all probably play quite well with a Truffle-based Raku implementation, although I’m not sure there is a current active effort in that area).

Future opportunities

While my current focus is to ship a Rakudo and MoarVM release that uses the new dispatcher mechanism, that won’t be the end of the journey. Some immediate ideas:

Some new language features may also be possible to provide in an efficient way with the help of the new dispatch mechanism. For example, there’s currently not a reliable way to try to invoke a piece of code, just run it if the signature binds, or to do something else if it doesn’t. Instead, things like the Cro router have to first do a trial bind of the signature, and then do the invoke, which makes routing rather more costly. There’s also the long suggested idea of providing pattern matching via signatures with the when construct (for example, when * -> ($x) {}; when * -> ($x, *@tail) { }), which is pretty much the same need, just in a less dynamic setting.

In closing…

Working on the new dispatch mechanism has been a longer journey than I first expected. The resumption part of the design was especially challenging, and there’s still a few important details to attend to there. Something like four potential approaches were discarded along the way (although elements of all of them influenced what I’ve described in this post). Abstractions that hold up are really, really, hard.

I also ended up having to take a couple of months away from doing Raku work at all, felt a bit crushed during some others, and have been juggling this with the equally important RakuAST project (which will be simplified by being able to assume the presence of the new dispatcher, and also offers me a range of softer Raku hacking tasks, whereas the dispatcher work offers few easy pickings).

Given all that, I’m glad to finally be seeing the light at the end of the tunnel. The work that remains is enumerable, and the day we ship a Rakudo and MoarVM release using the new dispatcher feels a small number of months away (and I hope writing that is not tempting fate!)

The new dispatcher is probably the most significant change to MoarVM since I founded it, in so far as it sees us removing a bunch of things that have been there pretty much since the start. RakuAST will also deliver the greatest architectural change to the Rakudo compiler in a decade. Both are an opportunity to fold years of learning things the hard way into the runtime and compiler. I hope when I look back at it all in another decade’s time, I’ll at least feel I made more interesting mistakes this time around.

brrt to the future: Why bother with Scripting?

Published by Bart Wiegmans on 2021-03-14T14:33:00

Many years back, Larry Wall shared his thesis on the nature of scripting. Since recently even Java gained 'script' support I thought it would be fitting to revisit the topic, and hopefully relevant to the perl and raku language community.

The weakness of Larry's treatment (which, to be fair to the author, I think is more intended to be enlightening than to be complete) is the contrast of scripting with programming. This contrast does not permit a clear separation because scripts are programs. That is to say, no matter how long or short, scripts are written commands for a machine to execute, and I think that's a pretty decent definition of a program in general.

A more useful contrast - and, I think, the intended one - is between scripts and other sorts of programs, because that allows us to compare scripting (writing scripts) with 'programming' (writing non-script programs). And to do that we need to know what other sorts of programs there are.

The short version of that answer is - systems and applications, and a bunch of other things that aren't really relevant to the working programmer, like (embedded) control algorithms, spreadsheets and database queries. (The definition I provided above is very broad, by design, because I don't want to get stuck on boundary questions). Most programmers write applications, some write systems, virtually all write scripts once in a while, though plenty of people who aren't professional programmers also write scripts.

I think the defining features of applications and systems are, respectively:

Consider for instance a mail client (like thunderbird) in comparison to a mailer daemon (like sendmail) - one provides an interface to read and write e-mails (the model) and the other provides functionality to send that e-mail to other servers.

Note that under this (again, broad) definition, libraries are also system software, which makes sense, considering that their users are developers (just as for, say, PostgreSQL) who care about things like performance, reliability, and correctness. Incidentally, libraries as well as 'typical' system software (such as database engines and operating system kernels) tend to be written in languages like C and C++ for much the same reasons.

What then, are the differences between scripts, applications, and systems? I think the following is a good list:

Obviously these distinctions aren't really binary - 'short' versus 'long', 'ad-hoc' versus 'general purpose'  - and can't be used to conclusively settle the question whether something is a script or an application. (If, indeed, that question ever comes up). More important is that for the 10 or so scripts I've written over the past year - some professionally, some not - all or most of these properties held, and I'd be surprised if the same isn't true for most readers. 

And - finally coming at the point that I'm trying to make today - these features point to a specific niche of programs more than to a specific technology (or set of technologies). To be exact, scripts are (mostly) short, custom programs to automate ad-hoc tasks, tasks that are either to specific or too small to develop and distribute another program for.

This has further implications on the preferred features of a scripting language (taken to mean, a language designed to enable the development of scripts). In particular:

As an example of the last point - Python 3 requires users to be exact about the encoding of their input, causing all sorts of trouble for unsuspecting scripters when they accidentally try to read ISO-8551 data as UTF-8, or vice versa. Python 2 did not, and for most scripts - not applications - I actually think that is the right choice.

This niche doesn't always exist. In computing environments where everything of interest is adequately captured by an application, or which lacks the ability to effectively automate ad-hoc tasks (I'm thinking in particular of Windows before PowerShell), the practice of scripting tends to not develop. Similarily, in a modern 'cloud' environment, where system setup is controlled by a state machine hosted by another organization, scripting doesn't really have much of a future.

To put it another way, scripting only thrives in an environment that has a lot of 'scriptable' tasks; meaning tasks for which there isn't already a pre-made solution available, environments that have powerful facilities available for a script to access, and whose users are empowered to automate those tasks. Such qualities are common on Unix/Linux 'workstations' but rather less so on smartphones and (as noted before) cloud computing environments.

Truth be told I'm a little worried about that development. I could point to, and expound on, the development and popularity of languages like go and rust, which aren't exactly scripting languages, or the replacement of Javascript with TypeScript, to make the point further, but I don't think that's necessary. At the same time I could point to the development of data science as a discipline to demonstrate that scripting is alive and well (and indeed perhaps more economically relevant than before).

What should be the conclusion for perl 5/7 and raku? I'm not quite sure, mostly because I'm not quite sure whether the broader perl/raku community would prefer their sister languages to be scripting or application languages. (As implied above, I think the Python community chose that they wanted Python 3 to be an application language, and this was not without consequences to their users). 

Raku adds a number of features common to application languages (I'm thinking of it's powerful type system in particular), continuing a trend that perl 5 arguably pioneered. This is indeed a very powerful strategy - a language can be introduced for scripts and some of those scripts are then extended into applications (or even systems), thereby ensuring its continued usage. But for it to work, a new perl family language must be introduced on its scripting merits, and there must be a plentiful supply of scriptable tasks to automate, some of which - or a combination of which - grow into an application.

For myself, I would like to see scripting have a bright future. Not just because scripting is the most accessible form of programming, but also because an environment that permits, even requires scripting, is one were not all interesting problems have been solved, one where it's users ask it to do tasks so diverse that there isn't an app for that, yet. One where the true potential of the wonderful devices that surround is can be explored.

In such a world there might well be a bright future for scripting.

Andrew Shitov: Computing factorials using Raku

Published by Andrew Shitov on 2021-01-31T18:19:33

In this post, I’d like to demonstrate a few ways of computing factorials using the Raku programming language.

1 — reduction

Let me start with the basic and the most effective (non necessarily the most efficient) form of computing the factorial of a given integer number:

say [*] 1..10; # 3628800

In the below examples, we mostly will be dealing with the factorial of 10, so remember the result. But to make the programs more versatile, let us read the number from the command line:

unit sub MAIN($n);

say [*] 1..$n;

To run the program, pass the number:

$ raku 00-cmd.raku 10
3628800

The program uses the reduction meta-operator [ ] with the main operator * in it.

You can also start with 2 (you can even compute 0! and 1! this way).

unit sub MAIN($n);

say [*] 2..$n;

2 — for

The second solution is using a postfix for loop to multiply the numbers in the range:

unit sub MAIN($n);

my $f = 1;
$f *= $_ for 2..$n;

say $f;

This solution is not that expressive but still demonstrates quite a clear code.

3 — map

You can also use map that is applied to a range:

unit sub MAIN($n);

my $f = 1;
(2..$n).map: $f *= *;

say $f;

Refer to my article All the stars of Perl 6, or * ** * to learn more about how to read *= *.

4 — recursion

Let’s implement a recursive solution.

unit sub MAIN($n);

sub factorial($n) {
    if $n < 2 {
        return 1;
    }
    else {
        return $n * factorial($n - 1);
    }
}

say factorial(n);

There are two branches, one of which terminates recursion.

5 — better recursion

The previous program can be rewritten to make a code with less punctuation:

unit sub MAIN($n);

sub factorial($n) {
    return 1 if $n < 2;
    return $n * factorial($n - 1);
}

say factorial($n);

Here, the first return is managed by a postfix if, and the second return can only be reached if the condition in if is false. So, neither an additional Boolean test nor else is needed.

6 — big numbers

What if you need to compute a factorial of a relatively big number? No worries, Raku will just do it:

say [*] 1..500;

The speed is more than acceptable for any practical application:

raku 06-long-factorial.raku  0.14s user 0.02s system 124% cpu 0.127 total

7 — small numbers

Let’s try something opposite and compute a factorial, which can fit a native integer:

unit sub MAIN($n);

my int $f = 1;
$f *= $_ for 2..$n;

say $f;

I am using a for loop here, but notice that the type of $f is a native integer (thus, 4 bytes). This program works with the numbers up to 20:

$ raku 07-int-factorial.raku 20
2432902008176640000

8 — sequence

The fun fact is that you can add a dot to the first program 🙂

unit sub MAIN($n);

say [*] 1 ... $n;

Now, 1 ... $n is a sequence. You can start it with 2 if you are not planning to compute a factorials of 0 and 1.

9 — reversed sequence

Unlike the solution with a range, it is possible to swap the ends of the sequence:

unit sub MAIN($n);

say [*] $n ... 1;

10 — sequence with definition

Nothing stops us from defining the elements of the sequence with a code block. The next program shows how you do it:

unit sub MAIN($n);

my @f = 1, * * ++$ ... *;
say @f[$n];

This time, the program generates a sequence of factorials from 1! to $n!, and to print the only one we need, we take the value from the array as @f[$n]. Notice that the sequence itself is lazy and its right end is undefined, so you can’t use @f[*-1], for example.

The rule here is * * ++$ (multiply the last computed value by the incremented index); it is using the built-in state variable $.

11 — multi functions

The idea of the solutions 4 and 5 with two branches can be further transformed to using multi-functions:

unit sub MAIN($n);

multi sub factorial(1)  { 1 }
multi sub factorial($n) { $n * factorial($n - 1) }

say factorial($n);

For the numbers above 1, Raku calls the second variant of the function. When the number comes down to 1, recursion stops, because the first variant is called. Notice how easily you can create a variant of a function that only reacts to the given value.

12 — where

The previous program loops infinitely if you try to set $n to 0. One of the simplest solution is to add a where clause to catch that case too.

unit sub MAIN($n);

multi sub factorial($n where $n < 2)  { 1 }
multi sub factorial($n) { $n * factorial($n - 1) }

say factorial($n);

13 — operator

Here’s another classical Raku solution: modifying its grammar to allow mathematical notation $n!.

unit sub MAIN($n);

sub postfix:<!>($n) {
    [*] 1..$n
}

say $n!;

14 — methodop

A rarely seen Raku’s feature called methodop (method operator) that allows you to call a function as it if was a method:

unit sub MAIN($n);

sub factorial($n) { 
    [*] 1..$n
}

say $n.&factorial;

15 — cached

Recursive solutions are perfect subjects for result caching. The following program demonstrates this approach.

unit sub MAIN($n);

use experimental :cached;

sub f($n) is cached {
    say "Called f($n)";
    return 1 if $n < 2;
    return $n * f($n - 1);
}

say f($n div 2);
say f(10);

This program first computes a factorial of the half of the input number, and then of the number itself. The program logs all the calls of the function. You can clearly see that, say, the factorial of 10 is using the results that were already computed for the factorial of 5:

$ raku 15-cached-factorial.raku 10
Called f(5)
Called f(4)
Called f(3)
Called f(2)
Called f(1)
120
Called f(10)
Called f(9)
Called f(8)
Called f(7)
Called f(6)
3628800

Note that the feature is experimental.

16 — triangular reduction

The reduction operator that we already used has a special variant [\ ] that allows to keep all the intermediate results. This is somewhat similar to using a sequence in the example 10.

unit sub MAIN($n);

my @f = [\*] 1..$n;

say @f[$n - 1];

17 — division of factorials

Now a few programs that go beyond the factorials themselves. The first program computes the value of the expression a! / b!, where both a and b are integer numbers, and a is not less than b.

The idea is to optimise the solution to skip the overlapping parts of the multiplication sequences. For example, 10! / 5! is 6 * 7 * 8 * 9 * 10.

To have more fun, let us modify Raku’s grammar so that it really parses the above expression.

unit sub MAIN($a, $b where $a >= $b);

class F {
    has $.n;    
}

sub postfix:<!>(Int $n) {    
    F.new(n => $n)
}

sub infix:</>(F $a, F $b) { 
    [*] $b.n ^.. $a.n
}

say $a! / $b!;

We already have seen the postfix:<!> operator. To catch division, another operator is defined, but to prevent catching the division of data of other types, a proxy class F is introduced.

To keep proper processing of expression such as 4 / 5, define another / operator that catches things which are not F. Don’t forget to add multi to both options. The callsame built-in routine dispatches control to built-in operator definitions.

. . .

multi sub infix:</>(F $a, F $b) { 
    [*] $b.n ^.. $a.n
}

multi sub infix:</>($a, $b) {
    callsame
}

say $a! / $b!;
say 4 / 5;

18 — optimisation

Let’s try to reduce the number of multiplications. Take a factorial of 10:

10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

Now, take one number from each end, multiply them, and repeat the procedure:

10 * 1 = 10
 9 * 2 = 18
 8 * 3 = 24
 7 * 4 = 28
 6 * 5 = 30

You can see that every such result is bigger than the previous one by 8, 6, 4, and 2. In other words, the difference reduces by 2 on each iteration, starting from 10, which is the input number.

The whole program that implements this algorithm is shown below:

unit sub MAIN(
    $n is copy where $n %% 2 #= Even numbers only
);

my $f = $n;

my $d = $n - 2;
my $m = $n + $d;

while $d > 0 {
    $f *= $m;
    $d -= 2;
    $m += $d;
}

say $f;

It only works for even input numbers, so it contains a restriction reflected in the where clause of the MAIN function. As homework, modify the program to accept odd numbers too.

19 — integral

Before wrapping up, let’s look at a couple of exotic methods, which, however, can be used to compute factorials of non-integer numbers (or, to be stricter, to compute what can be called extended definition of it).

The proper way would be to use the Gamma function, but let me illustrate the method with a simpler formula:

An integral is a sum by definition, so let’s make a straightforward loop:

unit sub MAIN($n);

my num $f = 0E0;
my num $dx = 1E-6;
loop (my $x = $dx; $x <= 1; $x += $dx) {
    $f += (-log($x)) ** $n;
}

say $f * $dx;

With the given step of 1E-6, the result is not that exact:

$ raku 19-integral-factorial.raku 10
3086830.6595557937

But you can compute a ‘factorial’ of a floating-point number. For example, 5! is 120 and 6! is 720, but what is 5.5!?

$ raku 19-integral-factorial.raku 5.5
285.948286477563

20 — another formula

And finally, the Stirling’s formula for the rescue. The bigger the n, the more correct is the result.

The implementation can be as simple as this:

unit sub MAIN($n);

# τ = 2 * π
say (τ * $n).sqrt * ($n / e) ** $n;

But you can make it a bit more outstanding if you have a fixed $n:

say sqrt(τ * 10) * (10 / e)¹⁰;

* * *

And that’s it for now. You can find the source code of all the programs shown here in the GitHub repository github.com/ash/factorial.

Andrew Shitov: The course of Raku

Published by Andrew Shitov on 2021-01-13T08:44:00

I am happy to report that the first part of the Raku course is completed and published. The course is available at course.raku.org.

The grant was approved a year and a half ago right before the PerlCon conference in Rīga. I was the organiser of the event, so I had to postpone the course due to high load. During the conference, it was proposed to rename Perl 6, which, together with other stuff, made me think if the course is needed.

After months, the name was settled, the distinction between Perl and Raku became clearer, and, more importantly, external resourses and services, e.g., Rosettacode and glot.io started using the new name. So, now I think it is still a good idea to create the course that I dreamed about a couple of years ago. I started the main work in the middle of November 2020, and by the beginning of January 2021, I had the first part ready.

The current plan includes five parts:

  1. Raku essentials
  2. Advanced Raku subjects
  3. Object-oriented programming in Raku
  4. Regexes and grammars
  5. Functional, concurrent, and reactive programming

It differs a bit from the original plan published in the grant proposal. While the material stays the same, I decided to split it differently. Initially, I was going to go through all the topics one after another. Now, the first sections reveal the basics of some topics, and we will return to the same topics on the next level in the second part.

For example, in the first part, I only talk about the basic data types: IntRatNumStrRangeArrayList, and Hash and basic usage of them. The rest, including other types (e.g., Date or DateTime) and the methods such as @array.rotate or %hash.kv is delayed until the second part.

Contrary, functions were a subject of the second part initially, but they are now discussed in the first part. So, we now have Part 1 “Raku essentials” and Part 2 “Advanced Raku topics”. This shuffling allowed me to create a liner flow in such a way that the reader can start writing real programs already after they finish the first part of the course.

I must say that it is quite a tricky task to organise the material without backward links. In the ideal course, any topic may only be based on the previously explained information. A couple of the most challenging cases were ranges and typed variables. They both causes a few chicken-and-egg loops.

During the work on the first part, I also prepared a ‘framework’ that generates the navigation through the site and helps with quiz automation. It is hosted as GitHub Pages and uses Jekyll and Liquid for generating static pages, and a couple of Raku programs to automate the process of adding new exercises and highlighting code snippets. Syntax highlighting is done with Pygments.

Returning the to course itself, it includes pages of a few different types:

The quizzes were not part of the grant proposal, but I think they help making a better user experience. All the quizzes have answers and comments. All the exercises are solved and published with the comments to explain the solution, or even to highlight some theoretical aspects.

The first part covers 91 topics and includes 73 quizzes and 65 exercises (with 70 solutions :-). There are about 330 pages in total. The sources are kept in a GitHub repository github.com/ash/raku-course, so people can send pull requiest, etc.

At this point, the first part is fully ready. I may slightly update it if the following parts require additional information about the topics covered in Part 1.

This text is a grant report, and it is also (a bit modified) published at https://news.perlfoundation.org/post/rakucourse1 on 13 January 2021.

Andrew Shitov: Raku Challenge, Week 92, Issue 1

Published by Andrew Shitov on 2020-12-22T08:24:00

This week’s task has an interesting solution in Raku. So, here’s the task:

You are given two strings $A and $B. Write a script to check if the given strings are Isomorphic. Print 1 if they are otherwise 0.

OK, so if the two strings are isomorphic, their characters are mapped: for each character from the first string, the character at the same position in the second string is always the same.

In the stings abc and def, a always corresponds to d, b to e, and c to f. That’s a trivial case. But then for the string abca, the corresponding string must be defd.

The letters do not need to go sequentially, so the strings aeiou and bcdfg are isomorphic too, as well as aeiou and gxypq. But also aaeeiioouu and bbccddffgg, or the pair aeaieoiuo and gxgyxpyqp.

The definition also means that the number of different characters is equal in both strings. But it also means that if we make the pairs of corresponding letters, the number of unique pairs is also the same, right? If a matches x, there cannot be any other pair with the first letter a.

Let’s exploit these observation:

sub is-isomorphic($a, $b) {
    +(([==] ($a, $b)>>.chars) && 
      ([==] ($a.comb, $b.comb, ($a.comb Z~ $b.comb))>>.unique));
}

First of all, the strings must have the same length.

Then, the strings are split into characters, and the number of unique characters should also be equal. But the collection of the unique pairs from the corresponding letters from both strings should also be of the same size.

Test it:

use Test;

# . . .

is(is-isomorphic('abc', 'def'), 1);
is(is-isomorphic('abb', 'xyy'), 1);
is(is-isomorphic('sum', 'add'), 0);
is(is-isomorphic('ACAB', 'XCXY'), 1);
is(is-isomorphic('AAB', 'XYZ'), 0);
is(is-isomorphic('AAB', 'XXZ'), 1);
is(is-isomorphic('abc', 'abc'), 1);
is(is-isomorphic('abc', 'ab'), 0);

* * *

→ GitHub repository
→ Navigation to the Raku challenges post series

6guts: Taking a break from Raku core development

Published by jnthnwrthngtn on 2020-10-05T19:44:26

I’d like to thank everyone who voted for me in the recent Raku Steering Council elections. By this point, I’ve been working on the language for well over a decade, first to help turn a language design I found fascinating into a working implementation, and since the Christmas release to make that implementation more robust and performant. Overall, it’s been as fun as it has been challenging – in a large part because I’ve found myself sharing the journey with a lot of really great people. I’ve also tried to do my bit to keep the community around the language kind and considerate. Receiving a vote from around 90% of those who participated in the Steering Council elections was humbling.

Alas, I’ve today submitted my resignation to the Steering Council, on personal health grounds. For the same reason, I’ll be taking a step back from Raku core development (Raku, MoarVM, language design, etc.) Please don’t worry too much; I’ll almost certainly be fine. It may be I’m ready to continue working on Raku things in a month or two. It may also be longer. Either way, I think Raku will be better off with a fully sized Steering Council in place, and I’ll be better off without the anxiety that I’m holding a role that I’m not in a place to fulfill.

brrt to the future: Reverse Linear Scan Allocation is probably a good idea

Published by Bart Wiegmans on 2019-03-21T15:52:00

Hi hackers! Today First of all, I want to thank everybody who gave such useful feedback on my last post.  For instance, I found out that the similarity between the expression JIT IR and the Testarossa Trees IR is quite remarkable, and that they have a fix for the problem that is quite different from what I had in mind.

Today I want to write something about register allocation, however. Register allocation is probably not my favorite problem, on account of being both messy and thankless. It is a messy problem because - aside from being NP-hard to solve optimally - hardware instruction sets and software ABI's introduce all sorts of annoying constraints. And it is a thankless problem because the case in which a good register allocator is useful - for instance, when there's lots of intermediate values used over a long stretch of code - are fairly rare. Much more common are the cases in which either there are trivially sufficient registers, or ABI constraints force a spill to memory anyway (e.g. when calling a function, almost all registers can be overwritten).

So, on account of this being not my favorite problem, and also because I promised to implement optimizations in the register allocator, I've been researching if there is a way to do better. And what better place to look than one of the fastest dynamic language implementations arround, LuaJIT? So that's what I did, and this post is about what I learned from that.

Truth be told, LuaJIT is not at all a learners' codebase (and I don't think it's author would claim this). It uses a rather terse style of C and lots and lots of preprocessor macros. I had somewhat gotten used to the style from hacking dynasm though, so that wasn't so bad. What was more surprising is that some of the steps in code generation that are distinct and separate in the MoarVM JIT - instruction selection, register allocation and emitting bytecode - were all blended together in LuaJIT. Over multiple backend architectures, too. And what's more - all these steps were done in reverse order - from the end of the program (trace) to the beginning. Now that's interesting...

I have no intention of combining all phases of code generation like LuaJIT has. But processing the IR in reverse seems to have some interesting properties. To understand why that is, I'll first have to explain how linear scan allocation currently works in MoarVM, and is most commonly described:

  1. First, the live ranges of program values are computed. Like the name indicates, these represent the range of the program code in which a value is both defined and may be used. Note that for the purpose of register allocation, the notion of a value shifts somewhat. In the expression DAG IR, a value is the result of a single computation. But for the purposes of register allocation, a value includes all its copies, as well as values computed from different conditional branches. This is necessary because when we actually start allocating registers, we need to know when a value is no longer in use (so we can reuse the register) and how long a value will remain in use -
  2. Because a value may be computed from distinct conditional branches, it is necessary to compute the holes in the live ranges. Holes exists because if a value is defined in both sides of a conditional branch, the range will cover both the earlier (in code order) branch and the later branch - but from the start of the later branch to its definition that value doesn't actually exist. We need this information to prevent the register allocator from trying to spill-and-load a nonexistent value, for instance.
  3. Only then can we allocate and assign the actual registers to instructions. Because we might have to spill values to memory, and because values now can have multiple definitions, this is a somewhat subtle problem. Also, we'll have to resolve all architecture specific register requirements in this step.
In the MoarVM register allocator, there's a fourth step and a fifth step. The fourth step exists to ensure that instructions conform to x86 two-operand form (Rather than return the result of an instruction in a third register, x86 reuses one of the input registers as the output register. E.g. all operators are of the form a = op(a, b)  rather than a = op(b, c). This saves on instruction encoding space). The fifth step inserts instructions that are introduced by the third step; this is done so that each instruction has a fixed address in the stream while the stream is being processed.

Altogether this is quite a bit of complexity and work, even for what is arguably the simplest correct global register allocation algorithm. So when I started thinking of the reverse linear scan algorithm employed by LuaJIT, the advantages became clear:
There are downsides as well, of course. Not knowing exactly how long a value will be live while processing it may cause the algorithm to make worse choices in which values to spill. But I don't think that's really a great concern, since figuring out the best possible value is practically impossible anyway, and the most commonly cited heuristic - evict the value that is live furthest in the future, because this will release a register over a longer range of code, reducing the chance that we'll need to evict again - is still available. (After all, we do always know the last use, even if we don't necessarily know the first definition).

Altogether, I'm quite excited about this algorithm; I think it will be a real simplification over the current implementation. Whether that will work out remains to be seen of course. I'll let you know!

brrt to the future: Something about IR optimization

Published by Bart Wiegmans on 2019-03-17T06:23:00

Hi hackers! Today I want to write about optimizing IR in the MoarVM JIT, and also a little bit about IR design itself.

One of the (major) design goals for the expression JIT was to have the ability to optimize code over the boundaries of individual MoarVM instructions. To enable this, the expression JIT first expands each VM instruction into a graph of lower-level operators. Optimization then means pattern-matching those graphs and replacing them with more efficient expressions.

As a running example, consider the idx operator. This operator takes two inputs (base and element) and a constant parameter scale and computes base+element*scale. This represents one of the operands of an  'indexed load' instruction on x86, typically used to process arrays. Such instructions allow one instruction to be used for what would otherwise be two operations (computing an address and loading a value). However, if the element of the idx operator is a constant, we can replace it instead with the addr instruction, which just adds a constant to a pointer. This is an improvement over idx because we no longer need to load the value of element into a register. This saves both an instruction and valuable register space.

Unfortunately this optimization introduces a bug. (Or, depending on your point of view, brings an existing bug out into the open). The expression JIT code generation process selects instructions for subtrees (tile) of the graph in a bottom-up fashion. These instructions represent the value computed or work performed by that subgraph. (For instance, a tree like (load (addr ? 8) 8) becomes mov ?, qword [?+8]; the question marks are filled in during register allocation). Because an instruction is always represents a tree, and because the graph is an arbitrary directed acyclic graph, the code generator projects that graph as a tree by visiting each operator node only once. So each value is computed once, and that computed value is reused by all later references.

It is worth going into some detail into why the expression graph is not a tree. Aside from transformations that might be introduced by optimizations (e.g. common subexpression elimination), a template may introduce a value that has multiple references via the let: pseudo-operator. See for instance the following (simplified) template:

(let: (($foo (load (local))))
    (add $foo (sub $foo (const 1))))

Both ADD and SUB refer to the same LOAD node


In this case, both references to $foo point directly to the same load operator. Thus, the graph is not a tree. Another case in which this occurs is during linking of templates into the graph. The output of an instruction is used, if possible, directly as the input for another instruction. (This is the primary way that the expression JIT can get rid of unnecessary memory operations). But there can be multiple instructions that use a value, in which case an operator can have multiple references. Finally, instruction operands are inserted by the compiler and these can have multiple references as well.

If each operator is visited only once during code generation, then this may introduce a problem when combined with another feature - conditional expressions. For instance, if two branches of a conditional expression both refer to the same value (represented by name $foo) then the code generator will only emit code to compute its value when it encounters the first reference. When the code generator encounters $foo for the second time in the other branch, no code will be emitted. This means that in the second branch, $foo will effectively have no defined value (because the code in the first branch is never executed), and wrong values or memory corruption is then the predictable result.

This bug has always existed for as long as the expression JIT has been under development, and in the past the solution has been not to write templates which have this problem. This is made a little easier by a feature the let: operator, in that it inserts a do operator which orders the values that are declared to be computed before the code that references them. So that this is in fact non-buggy:

(let: (($foo (load (local))) # code to compute $foo is emitted here
  (if (...)  
    (add $foo (const 1)) # $foo is just a reference
    (sub $foo (const 2)) # and here as well

The DO node is inserted for the LET operator. It ensures that the value of the LOAD node is computed before the reference in either branch


Alternatively, if a value $foo is used in the condition of the if operator, you can also be sure that it is available in both sides of the condition.

All these methods rely on the programmer being able to predict when a value will be first referenced and hence evaluated. An optimizer breaks this by design. This means that if I want the JIT optimizer to be successful, my options are:

  1. Fix the optimizer so as to not remove references that are critical for the correctness of the program
  2. Modify the input tree so that such references are either copied or moved forward
  3. Fix the code generator to emit code for a value, if it determines that an earlier reference is not available from the current block.
In other words, I first need to decide where this bug really belongs - in the optimizer, the code generator, or even the IR structure itself. The weakness of the expression IR is that expressions don't really impose a particular order. (This is unlike the spesh IR, which is instruction-based, and in which every instruction has a 'previous' and 'next' pointer). Thus, there really isn't a 'first' reference to a value, before the code generator introduces the concept. This is property is in fact quite handy for optimization (for instance, we can evaluate operands in whatever order is best, rather than being fixed by the input order) - so I'd really like to preserve it. But it also means that the property we're interested in - a value is computed before it is used in, in all possible code flow paths - isn't really expressible by the IR. And there is no obvious local invariant that can be maintained to ensure that this bug does not happen, so any correctness check may have to check the entire graph, which is quite impractical.

I hope this post explains why this is such a tricky problem! I have some ideas for how to get out of this, but I'll reserve those for a later post, since this one has gotten quite long enough. Until next time!

brrt to the future: A short post about types and polymorphism

Published by Bart Wiegmans on 2019-01-14T13:34:00

Hi all. I usually write somewhat long-winded posts, but today I'm going to try and make an exception. Today I want to talk about the expression template language used to map the high-level MoarVM instructions to low-level constructs that the JIT compiler can easily work with:

This 'language' was designed back in 2015 subject to three constraints:
Recently I've been working on adding support for floating point operations, and  this means working on the type system of the expression language. Because floating point instructions operate on a distinct set of registers from integer instructions, a floating point operator is not interchangeable with an integer (or pointer) operator.

This type system is enforced in two ways. First, by the template compiler, which attempts to check if you've used all operands correctly. This operates during development, which is convenient. Second, by instruction selection, as there will simply not be any instructions available that have the wrong combinations of types. Unfortunately, that happens at runtime, and such errors so annoying to debug that it motivated the development of the first type checker.

However, this presents two problems. One of the advantages of the expression IR is that, by virtue of having a small number of operators, it is fairly easy to analyze. Having a distinct set of operators for each type would undo that. But more importantly, there are several MoarVM instructions that are generic, i.e. that operate on integer, floating point, and pointer values. (For example, the set, getlex and bindlex instructions are generic in this way). This makes it impossible to know whether its values will be integers, pointers, or floats.

This is no problem for the interpreter since it can treat values as bags-of-bits (i.e., it can simply copy the union MVMRegister type that holds all values of all supported types). But the expression JIT works differently - it assumes that it can place any value in a register, and that it can reorder and potentially skip storing them to memory. (This saves work when the value would soon be overwritten anyway). So we need to know what register class that is, and we need to have the correct operators to manipulate a value in the right register class.

To summarize, the problem is:
There are two ways around this, and I chose to use both. First, we know as a fact for each local or lexical value in a MoarVM frame (subroutine) what type it should have. So even a generic operator like set can be resolved to a specific type at runtime, at which point we can select the correct operators. Second, we can introduce generic operators of our own. This is possible so long as we can select the correct instruction for an operator based on the types of the operands.

For instance, the store operator takes two operands, an address and a value. Depending on the type of the value (reg or num), we can always select the correct instruction (mov or movsd). It is however not possible to select different instructions for the load operator based on the type required, because instruction selection works from the bottom up. So we need a special load_num operator, but a store_num operator is not necessary. And this is true for a lot more operators than I had initially thought. For instance, aside from the (naturally generic) do and if operators, all arithmetic operators and comparison operators are generic in this way.

I realize that, despite my best efforts, this has become a rather long-winded post anyway.....

Anyway. For the next week, I'll be taking a slight detour, and I aim to generalize the two-operand form conversion that is necessary on x86. I'll try to write a blog about it as well, and maybe it'll be short and to the point. See you later!

brrt to the future: New years post

Published by Bart Wiegmans on 2019-01-06T13:15:00

Hi everybody! I recently read jnthns Perl 6 new years resolutions post, and I realized that this was an excellent example to emulate. So here I will attempt to share what I've been doing in 2018 and what I'll be doing in 2019.

In 2018, aside from the usual refactoring, bugfixing and the like:
So 2019 starts with me trying to complete the goals specified in that grant request. I've already partially completed one goal (as explained in the interim report) - ensuring that register encoding works correctly for SSE registers in DynASM. Next up is actually ensuring support for SSE (and floating point) registers in the JIT, which is surprisingly tricky, because it means introducing a type system where there wasn't really one previously. I will have more to report on that in the near future.

After that, the first thing on my list is the support for irregular register requirements in the register allocator, which should open up the possibility of supporting various instructions.

I guess that's all for now. Speak you later!