pl6anet

Perl 6 RSS Feeds

Steve Mynott (Freenode: stmuk) steve.mynott (at)gmail.com / 2018-07-22T21:11:37


6guts: More precise deoptimization usage tracking

Published by jnthnwrthngtn on 2018-07-21T15:59:19

In my previous post here, I talked about deoptimization and its implications for usage information. If you didn’t read that post, I suggest reading it before continuing, since the work described in this post builds upon it. Further background on deoptimization and its use in MoarVM may be found in my talk slides from last year’s Swiss Perl Workshop.

An example to consider

To keep things a bit simpler, we’ll look at an NQP program. NQP is a simplified subset of Perl 6, and so its naive compilation – before the optimizer gets at it – is much simpler than that produced by Rakudo. Here’s a small program to consider.

class Wrapper {
    has $!x;
    method x() { $!x }
}
class C { }

sub test($w) {
    my $var := "Used later";
    if nqp::istype($w.x, C) {
        "C"
    }
    else {
        $var
    }
}

my int $i := 0;
my $wrapper := Wrapper.new(x => C.new);
while $i < 1_000_000 {
    say(test($wrapper));
    $i++;
}
say(test(Wrapper.new(x => NQPMu)));

We’ll consider the test subroutine’s optimization. First, let’s walk through the bytecode before optimization. We always have a dummy empty basic block at the start of the graph, used for internal purposes, so we can disregard that.

  BB 0 (0x7f1be817b070):
    line: 7 (pc 0)
    Instructions:
      no_op           
    Successors: 1
    Predecessors: 
    Dominance children: 1

The next basic block starts with a bunch of null instructions, which will be mostly deleted. In the slow path interpreter, we null out registers in case code tries to read them as part of callframe setup. However, we get rid of that in the optimized code by letting the optimizer prove that such work is mostly not needed. Since we didn’t do any optimization yet, here’s all of those instructions.

  BB 1 (0x7f1be817b0f8):
    line: 7 (pc 0)
    Instructions:
      null              r5(1)
      null              r4(1)
      null              r3(1)
      null              r1(1)
      null              r0(1)

Next we receive the parameter.

      checkarity      liti16(1), liti16(1)
      param_rp_o        r0(2), liti16(0)
      paramnamesused  

Then we have the line my $var := "used later";. Rakudo is smarter than NQP in compiling such a thing: it would just emit a reference to a single constant string rather than boxing it each time like NQP’s simpler code-gen does.

      [Annotation: Line Number: x.nqp:7]
      const_s           r2(1), lits(Used later)
      hllboxtype_s      r3(2)
      box_s             r3(3),   r2(1),   r3(2)
      set               r1(2),   r3(3)

Now we have the code for $x.w. It starts out with a decont, since we may have been passed something in a Scalar container (note that NQP code may be called from full Perl 6 code, so this is possible). We then look up the method and call it.

      [Annotation: INS Deopt One (idx 0 -> pc 46; line 9)]
      [Annotation: Logged (bytecode offset 40)]
      decont            r4(2),   r0(2)
    Successors: 2
    Predecessors: 0
    Dominance children: 2

  BB 2 (0x7f1be817b158):
    line: 9 (pc 46)
    Instructions:
      findmeth          r3(4),   r4(2), lits(x)
    Successors: 3
    Predecessors: 1
    Dominance children: 3

  BB 3 (0x7f1be817b1b8):
    line: 9 (pc 56)
    Instructions:
      [Annotation: INS Deopt One (idx 1 -> pc 56; line 9)]
      prepargs        callsite(0x7f1bf1f0b340, 1 arg, 1 pos, nonflattening, interned)
      arg_o           liti16(0),   r0(2)
      [Annotation: INS Deopt All (idx 3 -> pc 72; line 9)]
      [Annotation: INS Deopt One (idx 2 -> pc 72; line 9)]
      [Annotation: Logged (bytecode offset 66)]
      invoke_o          r3(5),   r3(4)
    Successors: 4
    Predecessors: 2
    Dominance children: 4

Notice how two various instructions here are annotated with Deopt points. These are places that we might, after optimization has taken place, insert an instruction that could cause us to deoptimize. The pc 72 refers to the offset into the unoptimized bytecode that we should continue execution back in the interpreter.

There’s also various Logged annotations, which indicate instructions that may log some statistics – for example, about what code is invoked, and what type of value it returns (for invoke_o) or what kind of type we get out of a decont operation that actually had to read from a container.

Next up is the type check. Again, there’s a decont instruction, just in case the call to $x.w returned something in a container. We then have the istype instruction.

  BB 4 (0x7f1be817b218):
    line: 9 (pc 72)
    Instructions:
      [Annotation: INS Deopt One (idx 4 -> pc 78; line 9)]
      [Annotation: Logged (bytecode offset 72)]
      decont            r4(3),   r3(5)
    Successors: 5
    Predecessors: 3
    Dominance children: 5

  BB 5 (0x7f1be817b278):
    line: 9 (pc 78)
    Instructions:
      wval              r5(2), liti16(0), liti16(5) (P6opaque: C)
      istype            r6(1),   r4(3),   r5(2)
    Successors: 6
    Predecessors: 4
    Dominance children: 6

Next comes the if part of the branch:

  BB 6 (0x7f1be817b2d8):
    line: 9 (pc 94)
    Instructions:
      unless_i          r6(1),   BB(8)
    Successors: 8, 7
    Predecessors: 5
    Dominance children: 7, 8, 9

  BB 7 (0x7f1be817b338):
    line: 9 (pc 102)
    Instructions:
      const_s           r2(2), lits(C)
      hllboxtype_s      r4(4)
      box_s             r4(5),   r2(2),   r4(4)
      set               r5(3),   r4(5)
      goto              BB(9)
    Successors: 9
    Predecessors: 6
    Dominance children: 

Followed by the else part. And what is r1(2)? It’s the “Used later” string from earlier.

  BB 8 (0x7f1be817b398):
    line: 12 (pc 134)
    Instructions:
      set               r5(4),   r1(2)
    Successors: 9
    Predecessors: 6
    Dominance children: 

Finally, we’re done, and return the result of the branch of the if statement that was executed.

  BB 9 (0x7f1be817b3f8):
    line: 12 (pc 140)
    Instructions:
      PHI               r5(5),   r5(3),   r5(4)
      PHI               r4(6),   r4(5),   r4(3)
      PHI               r2(3),   r2(2),   r2(1)
      return_o          r5(5)
    Successors: 
    Predecessors: 7, 8
    Dominance children: 

How we optimize it

Let’s now walk through the optimized output. The argument handling has been reduced to a single instruction that does an unchecked read of the incoming argument. This is because we’re producing a specialization for a particular input callsite shape and set of input arguments. In this case, it will be a single argument of type Wrapper.

  BB 0 (0x7f1be817b070):
    line: 7 (pc 0)
    Instructions:
      no_op           
    Successors: 1
    Predecessors: 
    Dominance children: 1

  BB 1 (0x7f1be817b0f8):
    line: 7 (pc 0)
    Instructions:
      sp_getarg_o       r0(2), liti16(0)

What comes next is the code to store that "Used later" string. The ops look fine, but do you notice something odd?

      const_s           r2(1), lits(Used later)
      hllboxtype_s      r3(2)
      [Annotation: INS Deopt One (idx 0 -> pc 46; line 9)]
      box_s             r1(2),   r2(1),   r3(2)

Yup, there’s a deopt annotation moved on to that box_s. Huh? Well, let’s look at what comes next.

      [Annotation: INS Deopt One (idx 1 -> pc 56; line 9)]
      sp_getspeshslot   r7(0), sslot(2)
    Successors: 2
    Predecessors: 0
    Dominance children: 2

  BB 2 (0x7f1be8356d38):
    Inlined
    line: 7 (pc 0)
    Instructions:
      [Annotation: FH Start (0)]
      [Annotation: Inline Start (0)]
      [Annotation: INS Deopt Inline (idx 5 -> pc 20; line 8)]
      set               r9(1),   r0(2)
      [Annotation: INS Deopt Inline (idx 6 -> pc 42; line 9)]
      sp_p6ogetvt_o    r11(1),   r9(1), liti16(8), sslot(4)
      [Annotation: FH End (0)]
      set               r3(5),  r11(1)
    Successors: 3
    Predecessors: 3
    Dominance children: 3

Recall that in the unoptimized code we next did $w.x by a findmeth instruction, which came after a decont of $w, and the we did an invocation of that method. What’s happened to all of that lot?

First, since $w is the argument we are producing a specialization for, we thus know it’s Wrapper, and we know that’s not a container type, so the decont can go. Since we also know its type and we know the method name, we can just resolve that method once. The resolution of it is then stored in a “spesh slot”, which you can think of as a constants table for this particular specialization. What follows is, instead of the invocation, the code for the method x() { $!x }, which has been inlined. (The sp_p6ogetvt_o instruction is what attribute lookup has been optimized into.)

Oh, and about that Deopt annotation on the box_s? That’s just because code got deleted and it got shifted. We’ll look at the consequences of that later.

Here is the rest of the code:

  BB 3 (0x7f1be817b218):
    line: 9 (pc 72)
    Instructions:
      [Annotation: Inline End (0)]
      [Annotation: FH Goto (0)]
      [Annotation: INS Deopt One (idx 2 -> pc 72; line 9)]
      [Annotation: INS Deopt One (idx 4 -> pc 78; line 9)]
      sp_guardconc      r3(5), sslot(0), litui32(72)
      const_s           r2(2), lits(C)
      hllboxtype_s      r4(4)
      box_s             r5(3),   r2(2),   r4(4)
      PHI               r5(5),   r5(3)
      return_o          r5(5)
    Successors: 
    Predecessors: 2
    Dominance children: 6

Well, that’s pretty different from what we started out with too. What on earth has happened? Where did our if statement go?!

The sp_guardconc instruction is a guard. It checks, in this case, that we have a concrete instance of C in register r3(5). It was inserted because the gathered statistics said that, so far, it had been such 100% of the time. The guard will deoptimize – that is, fall back to the interpreter – if it fails, but otherwise proceed. Since we have guarded that, then the istype will become a constant. That means we know which way the branch would go, and can delete the other part of the branch. A type check, a conditional branch, and a branch all go away, to be replaced by a single cheap guard.

But what about that “Used later” string?

Notice how we executed:

      box_s             r1(2),   r2(1),   r3(2)

But its result value, r1(2), is completely unused anywhere in the code that we have left after optimization. The instruction was, however, retained, for the sake of deoptimization. In the original code, the value was written prior to a guard that might deoptimize. Were we to throw it away, then after we deoptimized the interpreter would try to read a value that wasn’t written, and crash in some interesting way.

The original approach

The original approach taken to this problem was to:

  1. Whenever we see a Deopt annotation, take its index as our current deopt point
  2. Whenever we see a write, label it with the current deopt point
  3. Whenever we see a read, check it the deopt point of the write is not equal to the deopt point of the read. If that is the case, mark the write as needing to be retained for deopt purposes.

Effectively, if a value written before a deopt point might be read after a deopt point, then we retain it. That was originally done by bumping its usage count. In my last post here, I described how we switched to setting a “needed for deopt” flag instead. But in the grand scheme of things, that changed nothing much about the algorithm described above; only step 3 was changed.

Note that this algorithm works in the case of loops – where we might encounter a value being read in a PHI node prior to seeing it being written – because the lack of a deopt point recorded on the writer will make it unequal to the current deopt point.

Correct, but imprecise

The problem with this approach isn’t with correctness, but rather with precision. A deopt retention algorithm is correct if it doesn’t throw away anything that is needed after a deoptimization. Of course, the simplest possible algorithm would be to mark everything as required, allowing no instruction deletions! The method described above is also correct, and marks fewer things. And for a while, it was enough. However, it came to be a blocker for various other optimizations we wish to do.

There are two particular problems that motivated looking for a more precise way to handle deopt usage. First of all, many instructions that may be replaced with a guard and deoptimize are actually replaced with something else or even deleted. For example, decont will often be replaced by a set because we know that it’s not a container type. A set can never trigger deoptimization. However, we had no way to update our deopt usage information based on this change. Therefore, something written before the set that used be a decont and read after it, but otherwise not needed, would be kept alive because the decont could have had a guard inserted, even though we know it did not.

A larger problem is that even when we might insert a guard, we might later be able to prove it is not needed. Consider:

my int $i = $str.chars;

The chars method will be tiny, so we can inline it. Here’s the code that we currently produce; I’ve shown the end of the inlining of the chars method together with the assignment into $i.

      chars            r15(1),  r14(1)
      hllboxtype_i     r13(1)
      [Annotation: INS Deopt Inline (idx 7 -> pc 134; line -1)]
      box_i            r13(2),  r15(1),  r13(1)
      [Annotation: FH End (0)]
      set               r2(5),  r13(2)
    Successors: 3
    Predecessors: 4
    Dominance children: 3

  BB 3 (0x7efe0479b5f0):
    line: 1 (pc 100)
    Instructions:
      [Annotation: Inline End (0)]
      [Annotation: FH Goto (0)]
      [Annotation: INS Deopt One (idx 3 -> pc 100; line 1)]
      sp_guardconc      r2(5), sslot(2), litui32(100)
      set               r2(6),   r2(5)
      set               r5(1),  r15(1)
      bindlex         lex(idx=0,outers=0,$i),   r5(1)

Since $i is a native integer lexical, we don’t need to box the native integer result of the chars op at all here. And you can see that we have done a rewrite such that r15(1) is used to assign to $inot the boxed result. However, the box_i instruction is retained. Why?

The immediate reason is that it’s used by the guard instruction. And indeed, I will do some work in the future to eliminate that. It’s not a hugely difficult problem. But doing that still wouldn’t have been enough. Why? Because there is a deopt point on the guard, and the boxed value is written before it and used after it. This example convinced me it was time to improve our deopt handling: it was directly in the way of optimizations that could provide a significant benefit.

A more precise algorithm

It took me three attempts to reach a solution to this. The first simple thing that I tried follows from the observation that everything written after the last deopt instruction in the optimized code can never possibly be used for deoptimization purposes. This was far from a general solution, but it did help a bit with very small functions that are free of control flow and have no or perhaps just some very early guards. This was safe, easy to reason about, easy to implement – but ultimately not powerful enough. However, it was helpful in letting me frame the problem and start to grapple with it, plus it gave me a set of cases that a more powerful solution should be able to take care of.

Attempt number two was to do a repeat of the initial deopt analysis process, but after the optimizations had taken place. Thus, cases where a Deopt annotation was on an instruction that was turned into something that could never deoptimize would not be counted. This quickly fell apart, however, since in the case where entire branches of a conditional were deleted then reads could disappear entirely. They simply weren’t there to analyze any more. So, this was an utter failure, but it did drive home that any analysis that was going to work had to build up a model of deoptimization usages before we performed any significant optimizations, and then manipulate that model safely even in the light of a mutated program graph.

Attempt three took much longer to come up with and implement, though thankfully was rather more successful. The new algorithm proceeds as follows.

  1. When we see a write instruction – and provided it has at least one reader – place it into a set OW of writes with still outstanding reads.
  2. When we see a deopt point, take the set OW and record the index of this deopt point on each of those writes. This means that we are now associating the writes with which deopt points are keeping them alive.
  3. Whenever we see a read, mark it as processed. Check if the writer has now had all of its reads processed. If so, remove it from the set OW.

This algorithm works in a single pass through the program graph. However, what about loops? In a loop, no matter what order we traverse the graph in, we will always see some reads that happen before writes, and that breaks the algorithm that I described above.

After some amount of scribbling graphs and staring at them, I hit upon a way to solve it that left me with a single pass through the graph, rather than having to iterate to a fixed point. When we see a read whose writer was not yet processed, we put it into a set of reads that are to be processed later. (As an aside, we know thanks to the SSA form that all such instructions are PHI (merge) instructions, and that these are always placed at the start of the graph.) We will then process a pending read when we have processed all of the basic blocks that are its predecessors – which means that by then all possible writes will have been processed.

The result is that we now have a list of all of the deopt points that make use of a particular write. Then, after optimization, we can go through the graph again and see which deopt points actually had guards or other potentially deoptimizing instructions placed at them. For all the cases where we have no such instruction under that Deopt annotation, we can delete the deopt usage. That way, if all normal usages and deopt usages of a value are gone, and the writing instruction is pure, we can delete that instruction.

This further means that once we gain the ability to delete guards that we can prove are not required any longer – perhaps because of new information we have after inlining – we will also be able to delete the deopt usages associated with them.

Last but not least, the specializer’s log output also includes which deopt points are keeping a value alive, so we will be able to inspect the graph in cases where we aren’t entirely sure and understand what’s happening.

Future work

With this done, it will make sense to work on guard elimination, so that is fairly high on my list of upcoming tasks. Another challenge is that while the new deopt algorithm is far more precise, it’s also far more costly. Its use of the DU chains means we have to run it as a second pass after the initial facts and usage pass. Further, the algorithm to eliminate unrequired deopt usages is a two pass algorithm; with some engineering we can likely find a way to avoid having to make the first of those. The various sets are represented as linked lists too, and we can probably do better than that.

One other interesting deoptimization improvement to explore in the future is to observe that any pure instructions leading up to a deopt point can be replayed by the interpreter. Therefore, we can deopt not to the instruction mapping to the place where we put the deopt point, but to the start of a run of pure instructions before that. That would in some cases allow us to delete more code in the optimized version.

Next time, I’ll be looking at how increasingly aggressive inlining caused chaos with our context introspection, and how I made things better. Thanks go to The Perl Foundation for making this work possible.

6guts: Better usage information in the MoarVM specializer

Published by jnthnwrthngtn on 2018-07-20T00:21:39

I’ve been doing lots of work on the MoarVM specializer of late, and will be writing a few posts here to explain it. This work has been covered by my grant from The Perl Foundation.

This post covers the recent addition of DU (Define-Use) chains. I’ll explain what they are, what kind of optimizations they have helped with so far, and how they can help us ensure the specializer is free of certain kinds of bug.

A little background

The MoarVM specializer helps programs run faster by ripping out as much unrequired generality as it knows how. This involves a bunch of different analyses, and those are aided by the program being turned into SSA (Static Single Assignment) form. This happens not at the Perl 6 program level, but rather at the bytecode level. MoarVM’s interpreter is a register machine, so something like:

($a + $b) * $c

Could, assuming these are all native integer variables, compile into something like:

getlex r0, '$a'
getlex r1, '$b'
add_i r0, r0, r1
getlex r1, '$c'
mul_i r0, r0, r1

Notice how registers r0 and r1 are re-used for multiple things. Now imagine that these registers hold objects and we are trying to track types and other such information. Since a register may be used for completely different things over its lifetime, we can’t just associate information with the register.

Transforming the bytecode into SSA form helps. We give each use of the register a version number:

getlex r0(1), '$a'
getlex r1(1), '$b'
add_i r0(2), r0(1), r1(1)
getlex r1(2), '$c'
mul_i r0(3), r0(2), r1(2)

Now we can associate information with each version of the register, greatly easing analysis of the program.

Defines

When a program is in SSA form, every versioned register has one definition: the instruction that writes it. Since it can never be written again anywhere in the SSA form of the bytecode, the writer is a single instruction. There are no MoarVM instructions that write more than one register, and so an instruction defines at most one value, and every versioned register has precisely one instruction that defines it.

So, defines are easy. For as long back as I can remember, we’ve stored a reference to the writing instruction of each versioned register, so whenever we see a read of it then we can always quickly find the defining instruction.

Uses

Until recently, we stored a counter of how many times each versioned register was used. We made an initial pass through the graph representing the bytecode to be optimized, bumping the usage count each time we saw a versioned register being used. Then, as we optimized, we could update those counts.

Usage information is especially useful taken together with knowledge of which instructions are pure – that is to say, they produce a result, but don’t have any effects besides that. If the usage count of such an instruction drops to zero, then we can delete it.

For example, if we have an attribute has str $!value in a class, it would be compiled into something like this:

  wval              r4(2), liti16(1), liti16(36) (P6opaque: Str)
  getattr_s         r5(1),   r0(2),   r4(2), lits($!value)

The wval instruction grabs the type object of the class that declares the attribute. This is used together with the attribute name to do a lookup (since parent and child classes may have attributes of the same name, but they are different attributes since they are in different classes). Provided we know the type of r0(2) – which is holding self – then we might optimize it into:

  wval              r4(2), liti16(1), liti16(36) (P6opaque: Str)
  sp_p6oget_s       r5(1),   r8(3), liti16(8)

Where the 8 is an offset in bytes indicating where the attribute lives in the memory of the object. We’ve turned a lookup by name into pointer chasing, which will later JIT into some pretty simple machine code (not quite as simple as we want yet, but still vastly faster than the normal lookup path).

But wait! What about that wval there? We don’t need it now. And so, after the various optimizations have taken place, we do Dead Instruction Elimination. So long as the usage count has dropped to zero – that is, nothing else is using the value – we can delete the instruction, meaning the end result is just:

  sp_p6oget_s       r5(1),   r8(3), liti16(8)

Deoptimization complication

So far, so relatively simple. Alas, there’s complications. Some values might become unused after we optimize the code, but we still can’t delete them. We use statistics to drive optimization, and do a great deal of speculation. For example, if we see 99% of the time a particular type shows up in the program, we optimize it assuming that type. But what if the 1% case shows up? Or what if we saw a certain type 100% of the time so far, but there’s a different one in the future? In that case, we drop back to the normal interpreter to handle it. For that to work out, however, we must make sure that the values the interpreter needs are still available after this deoptimization has taken place.

Up until recently, whenever we detected that a value might be needed if deoptimization happens, we simply gave its usage count an extra bump. This meant that even if we deleted all of its uses in the graph, we’d still not delete it. (This was a very coarse-grained analysis. I’ll discuss that more in a future post.)

You can’t count on this

The usage count was a fine enough approach to start out with, but it gradually came to be insufficient.

One bug that it’s quite possible to make is to forget to increment or decrement the usage count. The cases where it ended up too high could prevent us from deleting an instruction we didn’t need, leading to worse code. This wasn’t very serious, though a bit sub-optimal. The other way round – failing to increment the count – is of course more dangerous, since it may lead to an instruction being deleted that we really need. This didn’t happen often – we’re relatively careful – but it’d be nice if we had a way to verify it wasn’t happening at all. However, the +1 for the sake of deoptimization would have frustrated doing such an analysis.

A further issue is that while finding the place that a given versioned register was defined was easy, there was no cheap way to find its usages. Having such information would make some optimizations we already did easier and more effective, as well as make it easier to do some that we’re keen to add in the near future.

Beyond that, a single number was uninformative for those of us working on the optimizer. We could see the number, but what was it telling us? Why was the register still in use?

Adding use chains

So, instead of storing a count, we’ve started storing a linked list that points to each instruction that uses the versioned register. Often we only care about used, used precisely once, or unused; in fact, the only place we need the exact count is for debug output. Therefore, we can answer all the common questions we could with the usage count without having to traverse the chain. Building the chain is easy: everywhere we used to bump the counter, we now add an entry into the chain.

This chain works well for instructions that use the value, but what about the deoptimization usage? This was handled by storing that piece of information as a separate flag. It could then be displayed alongside the real usage count in the debug output, so we could quickly understand which registers were in use only for the purpose of deoptimization.

Checking the chains

Along with this, I implemented a chain checker. It goes through the instruction graph and the use chains, and makes sure:

This isn’t done by default – it costs something – but is available as a flag MoarVM developers can turn on when implementing new optimizations to aid with verifying they are, at least in this regard, correct.

Improving elimination of set instructions

Often in Perl 6, code has to deal with both values and values held in Scalar containers – that is to say, it’s polymorphic over the two cases. In the case that we have a Scalar container, we have to remove the value from it. This is an incredibly common operation in Perl 6, and there is a single op – decont – that checks if we have a container and takes the value out of it if so. Code generation conservatively inserts quite a lot of these.

Often, we simply have a value, and so there’s nothing to do. And often, the specializer can tell there will be nothing to do. Thus, something like this:

  decont            r5(2),   r0(2)
  findmeth          r4(2),   r5(2), lits(chars)

Is turned into this:

  set               r5(2),   r0(2)
  findmeth          r4(2),   r5(2), lits(chars)

Where set simply sets the value of one register into another. For this and various other reasons, it’s quite common that – after optimizations – we end up with code chock full of set instructions. They’re cheap, but they certainly aren’t free – on two counts. Firstly, there’s the execution cost of them. Secondly, they make the optimized code larger than it needs to be. This both makes less efficient use of the CPU’s code cache once we JIT the optimized result, but also can push the code over the inlining size limit, and thus it might miss out on further powerful optimizations.

We did have some code to try and get rid of set instructions. It was less than awesome on multiple counts. Firstly, it still left quite a few behind that we could see by inspection of the code could go away. Secondly, it could make a mess of the SSA form. Since it was one of the very last optimizations we did, that wasn’t a big deal, but it did make the debug output confusing, plus we will be adding more optimizations to this second pass in the future. Thirdly, it was somewhat adhoc, mostly written to handle peephole patterns that commonly showed up.

The usage chains provide a way to do better. The new set elimination algorithm covers the previous cases and new ones, and yet only does two fairly straightforward things.

Firstly, it looks if the writer of the set‘s second operand has only one usage, which is that set instruction, and no deopt usages. If so, and if there are no interfering uses of different versions of the register that the set writes, then it can have the writing instruction changed to write to the register that the set would, and the set instruction can then be deleted.

Failing that, it uses the use chain to check if there is a single user of the versioned register that the set instruction writes to. Again, given no conflicts, it can eliminate the set instruction by arranging for the user of the set instruction to instead use the value that the set would read. So in our case:

  set               r5(2),   r0(2)
  findmeth          r4(2),   r5(2), lits(chars)

We’d end up with:

  findmeth          r4(2),   r0(2), lits(chars)

To give a practical example of this, here is how the optimized code of the chars method called on a Scalar holding a Str looks without the set elimination:

  sp_getarg_o       r1(2), liti16(0)
  set               r8(2),   r1(2)
  set               r1(3),   r8(2)
  [Annotation: Logged (bytecode offset 24)]
  sp_p6oget_o       r8(3),   r1(3), liti16(16)
  [Annotation: INS Deopt One (idx 0 -> pc 30; line 2838)]
  sp_guardconc      r8(3), sslot(1), litui32(30)
  set              r11(2),   r8(3)
  set               r0(2),  r11(2)
  [Annotation: Line Number: SETTING::src/core/Str.pm6:2838]
  takedispatcher    r3(2)
  sp_p6oget_s       r5(1),   r0(2), liti16(8)
  chars             r6(1),   r5(1)
  hllboxtype_i      r4(3)
  [Annotation: INS Deopt One (idx 1 -> pc 134; line 2839)]
  box_i             r4(4),   r6(1),   r4(3)
  return_o          r4(4)

Notice the four set instructions in there. With the new set elimination algorithm, we end up with:

  sp_getarg_o       r1(3), liti16(0)
  [Annotation: Logged (bytecode offset 24)]
  sp_p6oget_o       r8(3),   r1(3), liti16(16)
  [Annotation: INS Deopt One (idx 0 -> pc 30; line 2838)]
  sp_guardconc      r8(3), sslot(1), litui32(30)
  [Annotation: Line Number: SETTING::src/core/Str.pm6:2838]
  takedispatcher    r3(2)
  sp_p6oget_s       r5(1),   r8(3), liti16(8)
  chars             r6(1),   r5(1)
  hllboxtype_i      r4(3)
  [Annotation: INS Deopt One (idx 1 -> pc 134; line 2839)]
  box_i             r4(4),   r6(1),   r4(3)
  return_o          r4(4)

Elimination of box/unbox pairs

Another interesting use of DU chains is to eliminate boxing of native values into objects only to unbox them again a short time later. This can happen due to the compiler not being smart enough, but if it happens across two subs or methods, and especially when we have multiple dispatch and polymorphic method dispatch happening, there’s not so much we could do better at that phase.

However, MoarVM does inlining, including speculative inlining. We can therefore see between boundaries that we cannot at compile time. Recall how chars produced this boxing code, as it is declared to return an Int:

  chars             r6(1),   r5(1)
  hllboxtype_i      r4(3)
  box_i             r4(4),   r6(1),   r4(3)

What if we were to write:

my int $chars = $str.chars;

Then the boxing happens just over the boundary. It turns out that there’s quite a lot to do in order to get rid of the boxing instruction, but with use chains we can already make a start. When we encounter a box, we look if any of its users are an unbox. After inlining, we’d see that there are such cases. Therefore, that unbox instruction can be rewritten to use r6(1) – the unboxed value.

That much works now. For reasons I’ll dig into in my next post, that’s not yet quite enough to eliminate the box_i instruction. So in this case, the saving is minor. Once we can get rid of the boxing operation, however, it will be a notable saving in such cases.

Coming in the future: native ref/deref pairs

One current performance challenge we have is that if we call a method and pass it a variable declared with a native type:

my int $foo = $a + $b;
$obj.meth($foo);

Then we don’t know if that method is declared as taking an rw parameter or not. Therefore, we must not pass a native integer value, but instead form a reference that points to where $foo lives, so we can update it. Of course, in most cases is rw is not used.

After inlining, we’ll be able to see this, and so will be able to use the use chain to discover when a formed reference is used for nothing more than to do a dereference. Then we can eliminate that reference taking process entirely.

In summary

Adding use chains has allowed us to detect and fix a small number of usage handling bugs, given us a way to prevent such bugs happening in the future, allowed us to improve an existing optimization, provided for efficiently implementing a new one, and will be an important part of improving the performance of code using native types in the future. Furthermore, it means those of us working on MoarVM have more detailed information about why an operation has to take place in the optimized code, so we can better understand if we have missed opportunities.

However, that’s not the end of the usage story. It turned out that a single flag for deopt usage would not suffice. Next time, I’ll look at why, and what I’ve done to address that.

Weekly changes in and around Perl 6: 2018.29 Cross-pollination

Published by liztormato on 2018-07-16T21:05:40

With a pollen-rich environment this time of year in the Northern hemisphere, it is to be expected that some cross-pollination will take place. In an unexpected twist, the question “What are some features new to Perl 6 that should be adopted by other languages?” created some interesting answers on Quora and Reddit. Which then gave rise to the more expected question “What feature in another language would you like to see adopted in Perl 6?” with equally interesting answers.

New Marketing Poster

Futureproof Perl 6Zoffix Znet has created a thought provoking marketing poster in the Perl 6 Marketing repository (FaceBook comments). It references Paul Graham‘s concept of a hundred year programming language. A quote from this blog post of 2003:

There are some stunningly novel ideas in Perl, for example. Many are stunningly bad, but that’s always true of ambitious efforts. At its current rate of mutation, God knows what Perl might evolve into in a hundred years.

To which yours truly can only add with 20/20 hindsight: I think we’ve had most of the “stunningly bad ideas” in Perl 6 by now.

Cancellation

Zoffix Znet announced in his blog post titled “Cancellation of Perl 6 Constants and Rationals Grant that he will cease working on the “Bugfixing and Performance of Rationals Fixing Constraints on Constants grant.

In conclusion, I believe were this grant to be completed, the result would differ significantly from what was voted on during grant’s proposal. For that reason, I wish to cancel it.

Yours truly would like to thank Zoffix Znet for all the (now volunteer) work that he has put into this.

Core Developments

Meanwhile on Twitter

Meanwhile on FaceBook

Meanwhile on StackOverflow

Meanwhile on perl6-users

Perl 6 in comments

Perl 6 Modules

New Modules:

Updated Modules:

Winding Down

On the hottest day of the year (so far), it was quite a job again to get the Perl 6 Weekly together. So much happening! Yours truly hopes to be able to keep this up until next week. See you then!

Weekly changes in and around Perl 6: 2018.28 Введение в Perl 6

Published by liztormato on 2018-07-09T20:11:25

Alexander Kiryuhin has made it possible for yet another 170 million people in the world to get introduced to Perl 6 in their native language: Russian (Большое спасибо!). This now brings the number of translation of the original Introduction to Perl 6 to 12: Bulgarian, Chinese, Dutch, French, German, Indonesian, Italian, Japanese, Portuguese, Russian, Spanish and Turkish. Which means that now over 3 billion people can learn about Perl 6 in their native language.

Credit where credit is due

Zoffix Znet describes how bugs in a script caused some contributors not to be mentioned in the monthly Rakudo compiler releases. His blog post “The Missing Contributors of Perl 6 describes in detail how the bugs got introduced, how it affected the report generation, and how a Reddit post from a person claiming to be the only person to never receive any credit for their work on Perl 6, got him to look into this. In the end, the following people (who are not already in the CREDITS of Rakudo Perl 6), were not credited when they should have been:

A. Sinan Unur, Alexey Melezhik, Antonio, Antonio Quinonez, Benny Siegert, bitrauser, brian d foy, Brian Duggan, cc, Christopher Bottoms, Coleoid, coypoop, Dabrien ‘Dabe’ Murphy, Dale Evans, Dan Zwell, Daniel Dehennin, Daniel Perrett, Dave Olszewski, David Brunton, David H. Adler, Dominique Dumont, Douglas L. Schrag, elenamerelo, Emeric54, Eric de Hont, fireartist, Fritz Zaucker, gotoexit, Jake Russo, James ( Jeremy ) Carman, Jason Cole, Jeff Linahan, Jim Davis, JJ Merelo, jjatria, Joel, John Gabriele, Julien Simonet, LemonBoy, Marcel Timmerman, Mario, Mark Montague, Martin Barth, Martin Dørum Nygaard, Martin Ryan, Mathieu Gagnon, mryan, Nadim Khemir, Nat, Neil Shadrach, Nic Q, okaoka, parabolize, Patrick Sebastian Zimmermann, Paul Smith, Philippe Bruhat (BooK), Rafael Schipiura, raiph, Robert Lemmen, Robert Newbould, Salvador Ortiz, Siavash Askari Nasr, Simon Ruderich, Skarsnik, Sylvain Colinet, sylvarant, vinc17fr, VZ, wukgdu.

Again, kudos to all these people and the work they have done for Perl 6. Apologies for not having done this at the proper time. Also, always remember Hanlon’s razor!

Documentation Squashathon results

As JJ Merelo tweeted, it was Squashathon time again last weekend. You could use this very useful flowchart to find out where the best place would be for you to start. A flowchart that will generally be useful for some time to come! And the results are in: 18 people created 154 commits and 7 pull requests! The next Squashathon will be on 4 August.

JITting quite a while already

Nudged by a comment on Hacker News, Bart Wiegmans explains that MoarVM has had a JIT for quite some time already. That maybe the naming of spesh and jit in MoarVM (as opposed to JIT frontend / backend) may be the root cause for this lack of understanding.

Perl 6 Workshops at TPC in Glasgow

There will not be one, but two whole day Perl 6 workshops on Monday 13 August at the Perl Conference in Glasgow:

Each priced at a mere £125 (about 142 euro / 167 US$), you can buy your tickets here.

Five Years of SPW

Lee Johnson is looking back on five years of the Swiss Perl Workshop, which had quite a lot of Perl 6 related activities, such as a hackathon to work out the “Great List Refactor” needed for the Christmas 2015 release of Rakudo Perl 6! This year’s Swiss Perl Workshop will be in Bern on 7 / 8 September. You can still submit a talk. And of course, you can still register for this free workshop!

Understanding Perl 6 concurrency

A question on /r/perl6 created an interesting set of links if you want to better understand concurrency in Perl 6!

New sticker

Yours truly introduced a new sticker at the Dutch Perl Workshop last weekend. These will be available for free at all events that yours truly is able to visit in the foreseeable future. Interested in getting a few beforehand? Contact me on #perl6 on irc.freenode.net! Or download the image and make them yourself, or order a local sticker maker to make ones for you!

Core developments

Meanwhile on Twitter

Meanwhile on FaceBook

Meanwhile on StackOverflow

Meanwhile on perl6-users

Perl 6 in comments

Perl 6 Modules

New Modules:

Updated Modules:

Winding Down

Quite a busy, but very “gezellige” week. Meeting old friends at the Dutch Perl Workshop, is one of the best things you can do on a hot weekend. The Perl Community at its best! Looking forward to all of the other Perl events in the future. Until then, see you next week for another Perl 6 Weekly!

brrt to the future: Perl 6 on MoarVM has had a JIT for a few years

Published by Bart Wiegmans on 2018-07-05T15:32:00

Dear readers, I recently came across the following comment on the internet (via Perl 6 weekly):

perl6 on MoarVM is starting to grow a JIT

 Which is very interesting because:
  1. Someone had at least heard of our efforts, so that's a win.
  2. But they had left with the impression that it was still in a beginning phase.
Clearly, we have some PR work to do. Consider this my attempt.

When people are talking about a 'JIT' colloquially and especially in the context of dynamic languages, they usually refer to a system that has both a dynamic specialization functionality, as well as a machine-code emitting functionality. MoarVM has had support for both since 2014. Historically we've called the specializer 'spesh' and the machine code emitter 'jit'. Maybe for communicating with the rest of the world it is better to call both 'the JIT' frontend and backend, respectively.

Without further ado, let me list the history of the MoarVM JIT compiler:
  1. The April 2014 release of MoarVM introduced the dynamic specialization framework spesh (the 'frontend').
  2. In June 2014, I started working in earnest on the machine code emitter (the part that we call the JIT), and halfway through that month had compiled the first function.
  3. In July 2014 we saw the introduction of inlining and on-stack-replacement in spesh.
  4. Also July 2014 saw the introduction of the invokish mechanism by which control flow can be returned to the interpreter.
  5. In August 2014 the JIT backend was completed and merged into MoarVM master.
  6. In June 2015, I started work on a new JIT compiler backend, first by patching the assembler library we use (DynASM), then proceeded with a new intermediate representation and instruction selection.
  7. After that progress slowed until in March 2017 I completed the register allocator. (I guess register allocation was harder than I thought it would be). A little later, the register allocator would support call argument placement
  8. The new 'expression' JIT backend was merged in August 2017. Since then, many contributors have stepped up to develop expression JIT templates (that are used to generate machine code for MoarVM opcodes).
  9. In August 2017, Jonathan started working on reorganizing spesh, starting with moving specialization to a separate thread, central optimization planning, improving optimizations and installing argument guards (which makes the process of selecting the correct specialized variant more efficient).
  10. Somewhere after this - I'm not exactly sure when - nine implemented inlinig the 'NativeCall' foreign function interface into JIT compiled code.
  11. Most recently Jonathan has started work to write specializer plugins - ways for rakudo to inform MoarVM on how to cache the result of method lookups, which should help increase the effectiveness of optimization for Perl 6.
  12. Arround the same time I reworked the way that the interpreter handles control flow changes for  JIT compiled code (e.g. in exception handling).
We (mostly Jonathan and I) have also given presentations on the progress of the JIT compiler:
  1. At YAPC::EU 2014 and FOSDEM 2015, Jonathan gave a presentation on the MoarVM dynamic specialization system.
  2. At YAPC::EU 2015 (Granada) I also gave a presentation. Sadly I can no longer find the presentation online or offline.
  3. At the Swiss Perl Workshop in 2017 Jonathan gave a presentation on deoptimization  and how it is used for supporting speculative optimizations.
  4. At The Perl Conference in Amsterdam (2017) I gave a presentation on how to implement JIT expression templates in MoarVM.
I'm sure there is more out there that I haven't yet linked to. And there's still a lot of exciting work going on and still more work to do. However, I hope that after this post there can be no doubt about the reality of a Perl6 implementation backed by a specializing JIT compiler ;-)


PS: You might read this and be reasonably surprised that Rakudo Perl 6 is not, after all this, very fast yet. I have a - not entirely serious - explanation for that:
  1. All problems in computer science can be solved with a layer of indirection.
  2. Many layers of indirection make programs slow.
  3. Perl 6 solves many computer science problems for you ;-) 
In the future, we'll continue to solve those problems, just faster.

PPS: Also, it is important to note that many of practical speed improvements that Rakudo users have come to enjoy did not come from VM improvements per se, but from better use of the VM by core library routines, for which many volunteers are responsible.

    Zoffix Znet: The Missing Contributors of Perl 6

    Published on 2018-07-04T00:00:00

    Information on omitted people who helped make Perl 6 better

    Weekly changes in and around Perl 6: 2018.27 Surveyed

    Published by liztormato on 2018-07-02T20:50:55

    The first Perl 6 Survey is over. There was quite a discussion on the applicability of many options on FaceBook and other places. The 220 responses produced a raw result for which JJ Merelo created a front page and some nice graphs from the raw data as well:

    Conference Season

    The Dutch Perl Workshop will be held coming weekend in Arnhem, the Netherlands! The following Perl 6 related presentations will be given on Saturday:

    On Sunday, there will be a Hackathon (with a slight Perl 6 bias) as well as an Introduction to Perl 6 workshop given by Andrew Shitov. Registration is still open!

    In a few weeks time, the (European) Perl Conference in Glasgow will take place. This also will have workshops, like Introduction to Perl 6 by Jeff Goff. And it will have the following Perl 6 related presentations:

    And here also: registration is still open!

    Squashathon Time Again

    This Saturday (7 July ± 12 hours) will be the next Squashathon again, with the emphasis on Perl 6 documentation. All help will be deeply appreciated!

    Learn Perl 6 in Y minutes

    One of the first Perl 6 introductions (on Learn X in Y Minutes), namely Where X=perl6, now also has a Spanish version. Kudos to uzl for this work!

    More Perl 6 Benchmarks

    Shlomi Fish has started a repo for Euler problems based benchmarks (try saying that 10x in a row).

    Blog Posts

    Core Developments

    Meanwhile on Twitter

    Meanwhile on FaceBook

    Meanwhile on StackOverflow

    Meanwhile on PerlMonks

    Perl 6 in comments

    Perl 6 modules

    New Modules:

    Updated Modules:

    Winding Down

    If you’re looking for warm and sunny weather, be sure to join us at the Dutch Perl Workshop. With around 30 degrees Celsius, it’s going to be a hot one. If we don’t see you there, we’ll see you again with next week’s Perl 6 Weekly!

    Jo Christian Oterhals: This is fantastic Brad!

    Published by Jo Christian Oterhals on 2018-06-27T17:19:19

    This is fantastic Brad! When I started writing these posts I didn’t believe they would be read much, and even less commented. But your comments (and comments like yours) are SO helpful! Thank you very much 😊

    Weekly changes in and around Perl 6: 2018.26 Surveying

    Published by liztormato on 2018-06-25T17:28:43

    The very first Perl 6 User Survey (June 2018) is now available for you to take part in (Reddit comments). If you are reading this, you are at least interested in Perl 6. Which makes you an excellent candidate for taking this survey. So please do!

    MasterDuke joining

    Daniel Green has joined the group of Rakudo Perl 6 core developers with a commit bit already some 10 days ago. Yours truly, trying to get a Perl 6 Weekly published at the Perl Conference in Salt Lake City, forgot to mention this last week. A belated welcome! Looking forward to more good things done by him.

    Through the Mists of Time

    Through the hard work of David Farrell (restoring all blog posts of Perl.com) one can see that the Perl 6 Weekly has quite a history: from July 2002 until August 2005, Piers Cawley has done the hard work of writing the earliest incarnation of the Perl 6 Weekly that yours truly could find. By the way, this is the 204th Perl 6 Weekly since Timo Paulssen started writing them again in February 2014. Yours truly has not been able to find much of the second and third generation Perl 6 Weekly: links welcome!

    Rakudo Compiler 2018.06

    Thanks to the work of many, but specifically our fearless release manager Aleks-Daniel Jakimenko-Aleksejev, last week saw the Rakudo Compiler release 2018.06, which was immediately followed by a new Docker container announcement and new Linux packages.

    Videos from The Perl Conference

    All of the videos of the Perl Conference in Salt Lake City are now online. These are the videos that either directly or indirectly relate to Perl 6:

    Introduction to Application Development

    Patrick Spek has sent a grant proposal to the Perl Foundation: Introduction to Application Development with Perl 6.

    A book about getting started with application development in Perl 6. It will cover installation of Perl 6, the basics of the language, how to use the perl6 binary to run programs, how to create a terminal application and a GUI application using GTK::Simple.

    Please leave a comment if you have an opinion about this grant proposal!

    Sake anyone?

    Aleks-Daniel Jakimenko-Aleksejev is reviving an old project of Jonathan Scott Duff: Sake, a Perl 6 make-a-like inspired by rake. He invites everyone to participate in its development. It is in early stages of development but is already usable for many things.

    How to construct a hash

    Juerd Waalboer posed the question on what would be the best way to document the syntax for creating hashes. Basically { } versus %( ). Apart from the discussion itself, this also drew some attention on Reddit and Twitter.

    Blog Posts

    Core Developments

    Meanwhile on Twitter

    Meanwhile on FaceBook

    Meanwhile on StackOverflow

    Meanwhile on PerlMonks

    Meanwhile on perl6-users

    Perl 6 in comments

    Perl 6 modules

    New Modules:

    Updated Modules:

    Winding Down

    It was a very busy week in Salt Lake City for yours truly. Since it was quite busy on the channels as well, it was hard to keep track of all the things happening. Hope not too much was missed this week. See you again next week, that time from the southern part of the Netherlands again!

    Jo Christian Oterhals: I basically agree with you, botnotbot.

    Published by Jo Christian Oterhals on 2018-06-25T11:28:23

    I basically agree with you, botnotbot. I tried to clarify what I meant by stating that “Perl 6 is not Perl. At least not Perl 5” and also by acknowledging that P6 shares “Perl 5’s […] philosophical underpinnings”. I guess I could have been clearer. Thanks for commenting and and contributing to the conversation.

    Jo Christian Oterhals: Perl 6 small stuff #3: Custom operators and overloading

    Published by Jo Christian Oterhals on 2018-06-22T12:04:44

    After a few years away from programming, I’m trying to get up to speed again by learning Perl 6. This series is meant to be sort of a progress report, showcasing not only what I’ve learnt but also all of my misunderstandings and errors.

    Some would say that this post would be better if titled “You didn’t, did you?”, because custom operators and operator overloading is bound to get you in trouble. When you don’t get in trouble, however, you’ll love it.

    Before explaining how to do it, let me give a few scenarios all centered around percentages:

    1. Have you ever wondered why you can’t write “1000*20%” to calculate the answer (200), but have to do “1000*0.2”?
    2. Have you ever wondered why we do the above and not the more readable “20% of 1000”?
    3. Have you ever wondered why we can’t calculate “1000 + 20%” and get the answer 1200? “1000 + (1000 * 0.2)” is obvious when you’ve learnt it, but wouldn’t it be more fun to have a shortcut such as “1000 +% 20"?
    4. Have you ever wondered why + always have to add numbers? Wouldn’t it be fun if it subtracts and gives your colleagues endless hours of tedious debugging? (The answer, obviously, is no; but bear with me here)
    5. Have you ever wondered why not everyone uses the metric system? How can you quickly convert lbs and stone (!) to kg or fahrenheit to celcius without resorting to complex calculation each time?

    Well, you can’t do any of these in Perl 6 either. The good news is that you can implement your own operators so that you achieve what you want. Perl 6 gives you the power to define your own operators and even overload existing ones.

    Operators can be of several kinds. prefix — ++$a (aka return $a and then $a = $a + 1); infix — 1+2; postfix — $a++(aka $a = $a + 1 and then return $a); circumfix — (1+2); postcircumfix — $a[2], etc. We’ll do the simpler ones here, and we’re sticking to real simple calculations.

    Let’s do the simplest: How do we teach Perl 6 to interpret 20% as 0.2?

    sub postfix:<%>($c) {
    return $c * 0.01;
    }
    # say 20%; (would output 0.2)

    How about writing 20% of 500 and get 100 as answer? Add this to the code above:

    sub infix:<of>($a, $b) {
    return $a * $b;
    }
    say 20% of 500; # Output: 100

    Yes, I know this would break in many ways if your code is not as well behaved as the example above. But it’s meant more as an introduction than a bullet proof solution.

    The solution to 100 +% 20 = 120 would look like this:

    sub infix:<+%>($a, $b) {
    return $a + ($a * $b%);
    }
    say 500 +% 20; # Output: 600

    And if you really want to break a lot and not make sense at all, overload + so that it behaves like -:

    sub infix:<+>($a, $b) {
    return $a - $b;
    }
    say 80 + 20; # Output: 60 (!)

    And conversions…? Define them!

    sub postfix:<lbs>($a) {
    return $a * 0.45359237;
    }
    sub postfix:<F>($a) {
    return ($a - 32) * 5/9;
    }
    sub postfix:<stone>($a) {
    return $a * 6.35029318;
    }
    say 100lbs; # Output: 45.359237..
    say 8stone; # Output: 50.80234...
    say 85F; # Output: 29.44444...

    And just to round the whole thing off, so to speak: Have you ever wanted a shortcut to round it off like we humans do when making calculcations in our heads (i.e. round off to nearest half?)

    Add this and try again:

    sub prefix:<~>($a) {
    return $a.round(0.5);
    }
    say ~100lbs; # Output: 45.5
    say ~8stone; # Output: 51.
    say ~85F; # Output: 29.5.

    As I’ve often said in this series: Powerful stuff!

    I guess my examples are not the most useful nor robust (as noted above). But when it comes to custom operators, it’s more or less a toe in the water.

    Jo Christian Oterhals: Yes, you’re right.

    Published by Jo Christian Oterhals on 2018-06-19T18:04:38

    Yes, you’re right. I remember this wrongly. I must have picked this up somewhere, and thought that it was the way to do it (in a language boasting of that there’s more than one way to do things).

    I looked this up in the old Camel book, 2nd edition from 1996. And I see where I’ve misunderstood. If you try to call a sub — without arguments — before it is defined you need to call it with ampersand or parantheses (&sub_name; or sub_name();). I must have begun using & just to be on the safe side.

    Well… it only took 20 years to clear that up, a little like Perl 6 itself :-)

    Again, thanks for pointing this out to me.

    Jo Christian Oterhals: Thanks for the response, Dave.

    Published by Jo Christian Oterhals on 2018-06-19T11:25:21

    Thanks for the response, Dave. You’re right. Here I blame old habits dating all the way back to 1998. Though I have a faint memory of & being required by the version I started with (5.004) if you tried to call a sub before it was declared, i.e.

    &the_sub;  # worked
    the_sub(); # didn't work
    sub the_sub { … }
    the_sub(); # now it worked

    I probably remember this wrong, and have kept this habit for all the wrong reasons all this time :-)

    Weekly changes in and around Perl 6: 2018.25 A Quick One From Salt Lake City

    Published by liztormato on 2018-06-18T19:56:06

    The Perl Conference in Salt Lake City kicked off today with a thought-provoking keynote by Vicky Brasseur on the Importance of Ecosystem viability in the light of a possible ongoing cascade effect in the Perl community. Yours truly hopes to have a link to the video version soon!

    Sponsor of \x1F98B

    It came to the attention of yours truly that Zoffix Znet has sponsored the unicode symbol 🦋 (aka \x1F98B, aka “BUTTERFLY”) on behalf of the Perl 6 Community. Kudos! FWIW, it looks like 🐪 (aka \x1F42A, aka “DROMEDARY CAMEL”) is still available for sponsoring!

    Polish Perl 6 First Steps Experience

    Zoffix Znet argues in his blog post (/r/perl and /r/perl6 comments) that it is time to make sure that the Perl 6 experience for readers of the coming Learning Perl 6 book by brian d foy is going to be as smooth as possible. He urges all of us to try that out and make sure we’ve got rid of all of the rough edges.

    TPF Grant reports

    The past week saw two Perl Foundation Grant reports: Perl 6 CaR TPF Grant: Monthly Report (June, 2018) by Zoffix Znet and No Major Breakthroughs by Timo Paulssen (Reddit comments). Both interesting reads!

    A new perl 6 blogger

    The past months yours truly apparently missed a number of nice Perl 6 related blog posts by Jo Christian Oterhals:

    All very entertaining reads, especially if you’re coming from Perl 5

    Takers for a Russian perl6intro?

    Naoum Hankache is looking for someone to translate his excellent Introduction to Perl 6 to Russian. Please contact him if you think you’re up to it!

    Core Developments

    Meanwhile on Twitter

    Meanwhile on StackOverflow

    Meanwhile on PerlMonks

    Meanwhile on perl6-users

    Perl 6 in comments

    Perl 6 Modules

    New Modules:

    Updated Modules:

    Winding Down

    A little shorter than usual maybe. Or maybe not. Anyways, next week’s Perl 6 Weekly may either be a day early or a day late, as yours truly will be en route for most of next Monday. Be it early or be it late, see you the next time for more Perl 6 news!

    Zoffix Znet: Perl 6 Colonpairoscopy

    Published on 2018-06-18T00:00:00

    Everything to know about colonpairs in Perl 6

    my Timotimo \this: No Major Breakthroughs

    Published by Timo Paulssen on 2018-06-15T13:45:32

    Sadly, the time since the last post on this blog hasn't been fruitful with regards to the profiling project. There have been slight improvements to the profiler inside MoarVM, like handling profiles with a very deep call graph better, making the first GC run show up again, capturing allocations from optional parameters properly, and hopefully finally making programs that have multiple threads running no longer crash during the profile dumping phase. A recently merged branch by esteemed colleague brrt will allow me to properly fix one nasty issue that remains in the profiler that relates to inlining.

    Even though I can't show off lovely screenshots of the profiler UI (if you consider Coder's Art™ lovely), I can briefly go over the changes that have happened and what's next on the list. And of course I'm still very much interested in finishing the grant work!

    katzenpfote_soft

    Missed Optional Parameters

    The first change I'd like to talk about is the one that was causing allocations from boxing optional parameters to go missing from the profile. Optional parameters are implemented as an op that accesses the passed arguments to see if something was present or not. Then it either runs code to put the default value in - if no argument was present - or it skips over that code. Additionally, it handles arguments that were passed as native ints, nums, or strings.

    If an object was expected by the code that uses the parameter, this op will also create a box for the value, for example an Int object. The crucial mistake was in the instrumentation by the profiler.

    Finding everything that is allocated is done by putting a little "take note of this object" op after every op that may create an object. This op then checks if the object was probably allocated by the last instruction, or if it was probably already logged earlier. If it was just allocated, that allocation is recorded for the profile.

    The problem in this case lies in the placement of the logging op: It was placed right after the instruction that grabs the argument. However, that made it land in the place that gets skipped over if an argument was present. So either no argument was passed, and the logging op was just asked to log that a null was allocated, or an argument was passed that was perhaps boxed, and the logging op was skipped over. Oops!

    Fixing this was simply a matter of following the skip and putting the logging op in the right place.

    Multi-threaded Programs Crashing Mysteriously

    If you used the profiler on code that runs multiple threads, you may have seen very suspicious looking internal error messages like "const_iX NYI" pop up. This was caused by the instrumentation aspect of the profiler, more specifically what it did when the instrumentation was no longer needed. Allow me to explain:

    Instrumentation in this context refers to creating a version of the program bytecode that does some extra work in the right places. For the profiler this includes putting ops in the code that record that a function was called or exited, and ops that record allocations of objects.

    This instrumentation happens lazily, i.e. when a function is entered the first time, it runs into the "instrumentation barrier", which pauses the program and creates the instrumented code right then and there. The instrumented code then gets installed and the program continues. This is implemented by having a global "instrumentation level" that just gets increased by 1 every time functions should go through an instrumentation step. This is done when profiling starts, and it is done when profiling ends.

    Here's where the problem lies: Profiling is turned on before user code runs, which just happens to always be in single-threaded territory. However, profiling gets turned off as soon as the main thread is finished. This is done by increasing the instrumentation level by 1 again. Every function that is entered from now on will have to go through instrumentation again, which will restore the original bytecode in this case.

    Other threads might still continue running, though. The first example that made this problem clear was finding the 1000st prime by grepping over a hypered range from 0 to infinity. Crucially, after finding the 1000st prime, some workers were still busy with their batch of numbers.

    Here's where the instrumentation barrier becomes a problem. One of the remaining workers calls into a function, for example is-prime, for the first time since the instrumentation level was changed. It will have its instrumented bytecode replaced by the original bytecode. However, the other threads, which may still be inside is-prime in this example, will not know about this. They keep happily interpreting the bytecode when all of a sudden the bytecode changes.

    Since the uninstrumented bytecode is shorter than the instrumented bytecode, the worst case is that it reads code past the end of the bytecode segment, but the more common case is that the instruction pointer just suddenly points either at the wrong instruction, or in the middle of an instruction.

    Instructions usually start with the opcode, a 16 bit number usually between 0 and 1000. The next part is often a 16 bit number holding the index of a register, which is usually a number below about 40, but quite often below 10. If the instruction pointer accidentally treats the register number as an opcode, it will therefor often land on ops with low numbers. Opcode 0 is no_op, i.e. "do nothing". The next three ops are const_i8 through const_i32, which all just throw the exception that I mentioned in the first paragraph: "const_iX NYI". Two spots ahead is the op "const_n32", which also thrown as NYI error.

    And there you have it, mystery solved. But what's the solution to the underlying problem? In this case, I took the easy way out. All the profiling ops first check if profiling is currently turned on or not anyway, so leaving the instrumented code in after profiling has ended is not dangerous. That's why MoarVM now just keeps instrumentation the same after profiling ends. After all, the next thing is usually dumping the profile data and exiting anyway.

    The Next Steps

    The MoarVM branch that brrt recently merged is very helpful for a very specific situation that can throw the profiler off and cause gigantic profile files: When a block has its bytecode inlined into the containing routine, and the block that was inlined had a "return" in it, it knows that it has to "skip" over the inner block, since blocks don't handle returns.

    However, the block is still counted as a routine that gets entered and left. The long and short of it is that returning from the inner block jumps directly to the exit, but having the block inlined frees us from doing the whole "create a call frame, and tear it down afterwards" dance. That dance would have contained telling the profiler that a frame was exited "abnormally"; since the regular "prof_exit" op that would have recorded the exit will be skipped over, tearing down the frame would have contained the logging.

    In this particular case, though, no exit would be logged! This makes the call graph - think of it like a flame graph - look very strange. Imagine a function being called in a loop, and returning from an inner block as described above. It would miss all of the exits, so every time the function is called again, it will look like the function called itself, never returning to the loop. Every time around the loop, the call will seem to be nested deeper and deeper. Since the profiler keeps around the whole call graph, the file will just keep growing with every single iteration.

    Now, how does brrt's code change this situation? It will allow very easily to figure out how many inlines deep a "return from this routine" op is, so that the profiler can accurately log the right amount of exits.

    On the UI side of things, I want to bring the routine overview list into a good state that will finally be worth showing. The list of GC runs will also be interesting, especially since the profiler recently learned to log how each individual thread performed its GC run, but the current HTML frontend doesn't know how to display that yet.

    Hopefully the wait for the next post on my blog won't be as long as this time!
      - Timo

    Zoffix Znet: A Call to Action: Polish Perl 6 First Steps Experience

    Published on 2018-06-13T00:00:00

    Help us make beginners' Perl 6 experience better

    brrt to the future: Controlled Stack Hacking for the MoarVM JIT Compiler

    Published by Bart Wiegmans on 2018-06-10T16:29:00

    Hi readers! Today I have a story about a recently-merged set of patches that allows MoarVM to use the on-stack return pointer to reduce the overhead of exception handling and other VM features for JIT compiled code. Maybe you'll find it interesting.

    As you might know, MoarVM Is a bytecode interpreter. In some situations, MoarVM internals need to know the current position in the execution of the program. For instance in exception handling, all exception thrown within a block are caught by the associated CATCH block or propagated if no such block exists. Such blocks are indicated as a range within the bytecode, and we find the associated CATCH block by comparing the current position with the known ranges.

    This is relatively straightforward to implement for the interpreter, because the interpreter must maintain a 'current position' pointer simply to function. (MoarVM stores a pointer to this pointer in a thread context object so that it is available throughout the VM). For the JIT that is another matter, because the control flow is handled implicitly by the CPU. The instruction pointer register (called %rip on amd64) cannot be read directly. Moreover, as soon as you enter a function that might want to use the current address (like the functions responsible for exception handling), you've left the 'program' code and entered VM code.

    So what we used to do instead is take the address of a position within the bytecode (as indicated by a label in the bytecode, a somewhat involved process) and store that in a per-frame field called the jit_entry_label. This field is necessary to support another MoarVM feature  - we use the interpreter as a trampoline (in the first or second sense of that definition). Because the interpreter is not recursive, JIT compiled code needs to return to the interpreter to execute a subroutine that was invoked (as opposed to calling an interpreter function, as perl5 does for exception handling). The primary purpose of this label is to continue where we left off after returning from another invoked program. But it can be used just as well for finding where we are in the execution of the program.

    Only problem then is that we need to keep it up to date, which we did. On the entry of every basic block (uninterrupted sequence of code), we stored the current position in this field. This is quite common - every conditional statement, loop or other control flow change needs one, as well as every exception-handler scope change needed a little snippet storing the current position. This was annoying.

    Furthermore, there are numerous MoarVM instructions that might change the control flow (or might not). For instance, the instruction responsible for converting an object to a boolean value might need to invoke the Bool method specific to that objects' class - or, if no such method exists, fallback to a default implementation. We call such instructions invokish. When compiling code that contains such invokish instructions, we installed 'control guards' to check if the VM had in fact invoked another routine, and if so, to return to the interpreter to execute that routine. This too added quite a bit of overhead.

    I keep writing in the past tense because all of that is now gone, and that happened due to a simple realization. When we call a function (in C or assembly), we place the return address (the machine instruction after the call instruction) on the stack. We can read this value from the stack and use it wherever we want to know about the current position.

    I initially had implemented that using a stack walker function similar to the one in the link, except that I implemented it in assembly instead. (When writing this post I learned of the GCC __builtin_return_address and MSVC _ReturnAddress intrinsic functions, which presumably do the same thing). Unfortunately, that strategy didn't really work - it relies on the frame base pointer (%rbp) being placed right 'on top' of the return address pointer on the stack. Even with special compiler flags intended to preserve that behaviour, this assumption turned out to be unreliable.

    Fortunately I realized later that it was also unnecessary. Because the JIT compiler controls the layout of the compiled code frame, it also controls exactly where the return address will be stored when we compile a (C) function call. That means that we can simply take a pointer to this address and store that in the thread context structure. From that address, we can read exactly the current position in the compiled code, without having to explicitly store it so often. Furthermore, we can also write to this location, changing the address the function will return to. Effectively, this is a controlled 'on-stack goto', an idiom more often used for exploits than for good purposes - clearly this is an exception! We use this to force a return to the interpreter (with proper stack frame cleanup) for 'invokish' instructions that end up invoking. We can change control to go directly to an exception handler if it is in the same frame. This makes all the earlier control 'guard' fragments redundant, allowing us to remove them entirely. Thus, an invokish instruction that doesn't actually invoke now carries no extra cost.

    How much does this save? It depends a lot on the exact program, but I estimate about 5% of compiled code size, and from a hopelessly optimal (and fairly unrealistic) benchmark which I lifted from this blog post, approximately 10% of runtime. In real code, the effect is definitely nowhere near what jnthn++ or samcv++ achieved lately, but it's still nice. Also nice is that the code is quite a bit simpler than it was before.

    Anyway, that's all I have to tell today. Have fun hacking, and until next time!

    6guts: Faster dispatches with MoarVM specializer plugins

    Published by jnthnwrthngtn on 2018-06-09T00:01:42

    One of the goals for the current round of my Perl Foundation Performance and Reliability grant is to speed up private method calls in roles, as well as assignments in to Scalar containers. What I didn’t expect at the time I wrote the grant application is that these two would lead to a single new mechanism in MoarVM to make them possible.

    The Scalar container assignment improvements are still to come; currently I have a plan and hope to make good progress on it next week. I do, however, have a range of dispatch-related performance improvements to show, including the private method case.

    Background

    MoarVM runs programs faster by analyzing how they run and producing specialized versions of parts of the program based on that information. It takes note of which code is run often (frequently called methods and hot loops), which types a block of code is called with, what types are returned from calls, what code a closure points to, and more. Note that it observes the runtime behavior, and so is not dependent on whether the program has type annotations or not.

    Calls are one of the most important things that the optimizer considers, be they method calls, subroutine calls or invoking a received closure. Method calls are especially interesting, because with a call like $obj.meth($arg), the method to be called depends on the exact type of $obj. Often, we end up producing a version of the code that is specialized for a particular type of $obj. We can therefore resolve the method once in this specialization, saving the method lookup overhead.

    But there’s more. Once we know exactly what method we’ll be calling, and if the method is fairly small, we can inline it into the caller, thus eliminating the call overhead too. Further, since we are inlining a specialized version of the code and have already proved that we meet the conditions for using that specialization, we can eliminate type checks on parameters. Inlining is even more powerful than that: it opens the door to a wider range of analyses that would not be possible without it, which lead to futher program optimizations.

    The problem

    We can do this kind of optimization with method calls because MoarVM understands about method calls. It knows that if it is holding the type of the invocant constant, then the result of the dispatch can also be considered a constant.

    Unfortunately, there’s more than one case of method calling in Perl 6. While the majority of calls take the familiar $obj.foo form, we also have:

    In the first case, if the call is in a class, then we can resolve it at compilation time, since private methods aren’t virtual. Such calls are thus pretty fast. But what if the private method call is in a role? Well, then it was far slower. It took a method call on the meta-object, which then did a hash lookup to find the method, followed by invoking that method. This work was done by a call to a dispatch:<!> utility method. It was the same story for qualified calls and duck calls.

    So, let’s extend MoarVM to understand these kinds of calls?

    So if normal method calls are faster because MoarVM understands them, surely we can do better by teaching it to understand these other forms of calling too? Perhaps we could add some new ops to the VM to represent these kinds of calls?

    Maybe, but all of them come with their own rules. And those rules are already implemented in the metamodel, so we’d be doing some logic duplication. We make normal method calls fast by precomputing a method cache, which is just a hash table, and have the specializer do its lookups in that. While such an approach might work for private methods, it gets decidedly trickier in the other two cases. Plus those precomputed hashes take up a lot of space. There are hundreds of exception types in CORE.setting and every one of them has a precomputed hash table of all of its methods, with those methods from base classes denormalized in to it. This means hundreds of hashes containing mappings for all of the methods that are inherited from MuAny, and Exception. We do lazily deserialize these, which helps, but it’s still fairly costly. Introducing more such things, when I already want rid of that one, didn’t feel like a good direction.

    Let’s make MoarVM teachable

    Earlier in the post, I wrote this:

    It [the optimizer] knows that if it is holding the type of the invocant [of a method call] constant, then the result of the dispatch can also be held constant.

    And this is the key. The important thing isn’t that the specializer knows the precise semantics of the method dispatch. The important thing is that it knows the relationship between the arguments to a dispatch (e.g. the type that we’re calling the method on) and the result of the dispatch.

    This, along with considering the challenges of optimizing Scalar assignments, led me to the idea of introducing a mechanism in MoarVM where we can tell it about these relationships. This enables the specializer to insert guards as needed and then simply use the calculated result of the dispatch.

    Specializer plugins

    The new mechanism is known as “spesh plugins”, and I merged it into MoarVM’s master branch today. It works in a few steps. The first is that one registers a spesh plugin. Here’s the one for helping optimize private method calls:

    nqp::speshreg('perl6', 'privmeth', -> $obj, str $name {
        nqp::speshguardtype($obj, $obj.WHAT);
        $obj.HOW.find_private_method($obj, $name)
    });
    

    The registration provides the language the plugin is for, the name of the plugin, and a callback. The callback takes an object and a method name. The second line is the key to how the mechanism works. It indicates that the result that will be returned from this plugin will be valid provided the type of $obj precisely matches (that is, with no regard to subtyping relationships) the type of the $obj we are currently considering. Therefore, it establishes a relationship between the invocant type and the private method call result.

    Then, we just need to compile a private method call like:

    self!foo($bar, $baz)
    

    Into:

    nqp::speshresolve('privmeth', self, 'foo')(self, $bar, $baz)
    

    Taking care to only evaluate self once (obviously not a problem for self, but in general it can be any expression, and may have side-effects).

    And that’s it. So what happens at runtime?

    When the interpreter encounters this call for the first time, it calls the plugin. It then stores the result along with the conditions. On later calls made in the interpreter, it uses this mapping table to quite quickly map the invocant type into the appropriate result. It’s a little cache. (Aside: this is a little more involved because we want lookups without locking, but also need to cope with multiple threads creating resolution races. Thanks to a generalized free-at-safepoint mechanism in MoarVM, this isn’t so hard.)

    So that’s nice, and on its own would already be an improvement over what it replaced. But we haven’t even got to the exciting part yet! Each time we use this mapping, it records which mapping was used for the benefit of the optimizer. This information is stored in such a way that the specializer can work out which mappings are used with a particular set of parameter types to the method. So, in:

    role R {
        method foo() {
            self!bar
        }
    }
    class C1 does R {
        method !bar() { 1 }
    }
    class C2 does R {
        method !bar() { 2 }
    }
    

    The method foo might be invoked with invocants of type C1 and C2. Thus the mapping table for the call self!bar will have two entries. We may (if the code is hot) produce two specializations of method foo, and if we do, then we will also be able to see that there is only ever one target of the private method call in each case. Thus, we can inline the appropriate !bar into the matching specialization of foo.

    Results

    Writing a module PM.pm6 that contains:

    role R {
        method m() { self!p }
        method !p() { 42 }
    }
    class C does R {
    }
    for ^10_000_000 {
        C.m;
    }
    

    And then running it with perl6 -I. -e 'use PM6' used to run in 5.5s on my development machine. That’s only 1.8 million iterations of the loop per second, which means each is eating a whopping 1,650 CPU cycles assuming a 3GHz CPU.

    With the new spesh plugin mechanism, it runs in 0.83s, over 6.5x faster. It’s over 12 million iterations of the loop per second, or around 250 CPU cycles per iteration. That’s still a good bit higher than would be good, but it’s a heck of a lot better.

    Note that due to the way roles are handled in non-precompiled code, the use of the spesh plugin will not happen at present in a role in a script, thus why in this case I put the code into a module. This restriction can be lifted later.

    But wait, there’s more

    I also wrote a spesh plugin for qualified dispatches, like $obj.Foo::meth(). This one guards on two of its inputs, and has an error case to handle. Notice how we can avoid replicating this logic inside of MoarVM itself and just write it in NQP code.

    nqp::speshreg('perl6', 'qualmeth', -> $obj, str $name, $type {
        nqp::speshguardtype($obj, $obj.WHAT);
        if nqp::istype($obj, $type) {
            # Resolve to the correct qualified method.
            nqp::speshguardtype($type, $type.WHAT);
            $obj.HOW.find_method_qualified($obj, $type, $name)
        }
        else {
            # We'll throw an exception; return a thunk that will delegate to the
            # slow path implementation to do the throwing.
            -> $inv, *@pos, *%named {
                $inv.'dispatch:<::>'($name, $type, |@pos, |%named)
            }
        }
    });
    

    This gave an even more dramatic speedup. The program:

    role R1 {
        method m() { 1 }
    }
    role R2 {
        method m() { 2 }
    }
    class C does R1 does R2 {
        method m() {
            self.R2::m()
        }
    }
    for ^10_000_000 {
        C.m
    }
    

    Used to take 13.3s. With the spesh plugin in effect, it now takes 1.07s, a factor of more than 12x improvement.

    And even a little more…

    I also wondered if I could get $obj.?foo duck dispatches to do better using a spesh plugin too. The answer turned out to be yes. First of all, here’s the plugin:

    sub discard-and-nil(*@pos, *%named) { Nil }
    nqp::speshreg('perl6', 'maybemeth', -> $obj, str $name {
        nqp::speshguardtype($obj, $obj.WHAT);
        my $meth := $obj.HOW.find_method($obj, $name);
        nqp::isconcrete($meth)
            ?? $meth
            !! &discard-and-nil
    });
    

    There’s a couple of cases I decided to measure here. The first is the one where we wrote code with a .? call to handle the general case (for example, in a module), but then the program using the module always (or > 99% of the time) gives an object where we can call the method.

    class C {
    }
    class D {
        method m() { 42 }
    }
    for ^10_000_000 {
        (rand > 0.999 ?? C !! D).?m()
    }
    

    The rand call, compare, and conditional are all costs in this code besides the call I wanted to measure, so it’s not such a direct measurement of the real speedup of .?. Still, this program went from taking 10.9s before to 4.29s with the spesh plugin in place – an improvement of 2.5x. It achieves this by doing a speculative inline of the method m anyway, and then using deoptimization to fall back to the interpreter to handle the 0.1% of cases where we get C and not D. (It then, at the end of the loop body, falls back into the hot code again.) Note that the inlining and deopt just naturally fell out of things the specializer already knew how to do.

    But had this come at the cost of making really polymorphic cases slower? Here’s another benchmark:

    class C {
    }
    class D {
        method m() { 42 }
    }
    for ^10_000_000 {
        (rand > 0.5 ?? C !! D).?m()
    }
    

    This one goes from 7.60s to 4.92s, a 1.5x speedup. Spesh can’t just punt this to doing a deopt for the uncommon case, because there is no uncommon case. Still, the guard table scan comes out ahead.

    (By the way, I think a lot of the slowness in this code – though I didn’t think of it when I wrote the benchmark – is that rand returns a Num, but 0.5 and 0.999 are Rats, so it is doing a costly type coercion before comparing.)

    And what next?

    Next I’ll be taking on Scalar containers and assignment, seeing what I can do with spesh plugins there, and hoping my ideas lead to as positive results as has been seen here.

    Also, this isn’t the final word on the various benchmarks in this post either. I know full well that the current spesh plugin implementation is inserting some redundant guards, and a bit of effort on that front can probably get us another win.

    Zoffix Znet: How To Make Old #perl6 IRC Log Links Work

    Published on 2018-06-06T00:00:00

    Find out how where PerlGeek.De IRC log links link to

    samcv: Secure Hashing for MoarVM to Prevent DOS Attacks

    Published on 2018-05-16T07:00:00

    Hashes are very useful data structures and underlie many internal representations in Perl 6 as well as being used as themselves. These data structures are very nice since they offer O(1) insertion time and O(1) lookup time on average. Hashes have long been considered an essential feature for Perl, much loved by users. Though when exploited, hashes can cause servers to grind to a halt. New in Rakudo Perl 6 2018.5 will be a feature called hash randomization which does much to help protect against this attack. In this article I explain some hashing basics as well as how the attack against non-randomized hashing can work.

    Table of Contents

    Hashing Basics

    Some hashing basics: when we use a hash, we take a string and come up with a unique integer to represent the string. Similar to how md5 or sha1 sums take an arbitrary amount of data and condense it into a shorter number which can identify it, we do a similar thing for strings.

    my %hash; %hash<foo> = 10

    In this code, MoarVM takes the string foo and performs a hashing function on it using a series of bitwise operations. The goal is to create a shorter number which allows us to put the foo key into one of the 8 buckets that MoarVM initializes when a hash is created.

    8 Hash buckets

    Our hashing code sets up a predefined number of buckets . When a bucket fills up to have 10 items it doubles the number of buckets. In normal operation the hashes will be randomly distributed, so it would take ≈47 keys added (≈47 is the average number of items to result in one bucket being filled to 10 items) before we have to expand the buckets the first time.

    When the buckets are expanded, we will now have 16 buckets. In normal operation our previous ≈47 items should be evenly distributed into those 16 buckets.

    The Attack

    Without a random hash seed it is easy for an attacker to generate strings which will result in the same hash. This devolves to O(n️2) time for the hash lookup. This O(n2) is actually O(string_length * num_collisions). When we have hash collisions, that means that no matter how many times we double the number of buckets we have, the strings which have hash collisions will always remain in the same bucket as each other. To locate the correct string, MoarVM must go down the chain and compare each hash value with the one we’re looking for. Since they are all the same, we must fall back to also checking each string itself manually until we find the correct string in that bucket.

    Hash collision

    This attack is done by creating a function that essentially is our hashing function backward (for those curious see here for an example of code which does forward and backward hashing for Chrome V8 engine’s former hashing function). We hash our target string, t. We then use random 3 character sequences (in our case graphemes) and plug them into our backward hashing function along with the hash for our target t. The backward hash and the random character sequence are stored in the dictionary and the process is repeated until we have a very large number of backward hash’s and random 3 grapheme prefixes.

    We can then use this dictionary to construct successively longer strings (or short if we so desire) which are the same hash as our target string t. This is a simplification of how the Meet-In-The-Middle attack works.

    This has been fixed in most programming languages (Python, Ruby, Perl), and several CVE’s have been issued over the years for this exploit (See CVE’s for PHP, OCaml, Perl, Ruby and Python).

    Assuming everything is fine for the next release I will also merge changes which introduce a stronger hashing function called SipHash. SipHash is meant to protect against an attacker discovering a hash secret remotely. While randomizing the seed makes this attack much harder, a determined attacker could discover the hash and if that is done they can easily perform a meet in the middle attack. SipHash was designed to solve the vulnerability of the hash function itself to meet-in-the-middle attacks. Both the randomization of the hash secret in addition with a non-vulnerable hashing function work work together to avert hash collision denial of service attacks.

    While the hash secret randomization will be out in Rakudo 2018.05, SipHash is planned to be introduced in Rakudo 2018.06.

    Randomness Source

    On Linux and Unix we prefer function calls rather than reading from /dev/urandom. There are some very important reasons for this.

    Relying on an external file existing is potentially problematic. If we are in a chroot and /dev is not mounted we will not have access to /dev/urandom. /dev/urandom is not special, it can be deleted by accident (or on purpose) or a sparse data file mounted in its place undetectable by programs. Trusting it simply because of its path is not ideal. Also, if we exhaust the maximum number of open file descriptors we will be unable to open /dev/urandom as well.

    System Functions

    On Windows we use the pCryptGenRandom which is provided by advapi32.dll since Windows XP.

    Linux, FreeBSD, OpenBSD and MacOS all use system provided random calls (if available) to get the data rather than having to open /dev/urandom. All these OS’s guarantee these calls to be non-blocking, though MacOS’s documentation does not comment on it. This is mostly important in very early userspace, which bit Python when a developer accidentally changed the randomness source causing systems which relied on very early Python scripts to stop booting due to waiting for randomness source to initialize.

    If the function doesn’t exist we fall back to using /dev/urandom. If opening or reading it fails, on BSD’s we will use the arc4random() function. In many BSD’s this is seeded from the system’s random entropy pool, providing us with a back up in case /dev/urandom doesn’t exist.

    On Linux we use the getrandom() system call which was added to kernel 3.17 instead of using the glibc wrapper since the glibc wrapper was added much later than to the kernel.

    On MacOS, Solaris and FreeBSD we use getrandom() while on OpenBSD we use getentropy().

    User Facing Changes

    From Rakudo Perl 6 2018.05, the order that keys are returned will be random between each perl6 instance.

    perl6 -e 'my %hash = <a 1 b 1 c 1 d 1 e 1 f 1>; say %hash.keys'
    (d f c a b e)
    perl6 -e 'my %hash = <a 1 b 1 c 1 d 1 e 1 f 1>; say %hash.keys'
    (e f a d c b)

    This will also effect iterating a hash without sorting: for %hash { }

    What Do I Have To Do?

    Users and module developers should make sure that they explicitly sort hashes and not rely on a specific order being constant. If you have a module, take a look at the code and see where you are iterating on a hash’s keys and whether or not the order of processing the hash’s keys affects the output of the program.

    # This should be okay since we are putting the hash into another hash, order
    # does not matter.
    for %hash.keys -> $key {
        %stuff{$key} = $i++;
    }
    # This can potentially cause issues, depending on where `@stuff` is used.
    for %hash.keys -> $key {
        @stuff.push: $key;
    }
    # This should be OK since we are using is-deeply and comparing a hash with another
    # hash
    is-deeply my-cool-hash-returning-function($input), %( foo => 'text', bar => 'text', baz => 'text');
    # Probably best to avoid using `is`. The `is` test function converts the input to a string before
    # checking for equality, but works since we stringify it in sorted order.
    is %hash,  %( foo => 'text', bar => 'text', baz => 'text');
    # NO. Keys are not guaranteed to be in the same order on each invocation
    is %hash.keys, <a b c d>;

    Module Developers

    Module developers should check out the git master of Rakudo, or if 2018.05 has been released, use that to run the tests of your module. Make sure to run the tests multiple times, ideally at least 10 times or use a loop:

    while prove -e 'perl6 -Ilib'; do true; done

    This loop will run again and again until it encounters a test failure, in which case it will stop.

    You must run your tests many times because the hash order will be different on each run. For hashes will a small number of items, it may not fail on every run. Make sure that you also look at the source to identify items that need fixing; don’t just rely on the test’s to tell you if you must make changes to your module.

    Further Reading

    Hardening Perl’s Hash Function, article by Booking.com about changes Perl 5 has made to harden hashing.

    gfldex: Deconstructing Simple Grammars

    Published by gfldex on 2018-05-10T14:51:34

    Last year I wrote an egg timer that was parsing command line arguments similar to GNU sleep. I was happy with the stringent form of the parser as follows.

    my Seconds $to-wait = @timicles»\
        .split(/<number>/, :v)\
        .map(-> [$,Rat(Any) $count, Str(Any) $unit] --> Seconds { %unit-multipliers{$unit} * $count })\
        .sum;

    It does a few simple things and does them one after another. A grammar with an action class would be overkill. I wasn’t happy with using splits ability to return the needle with the parts. It certainly does not improve readability.

    After quite a few iterations (and stepping on a bug), I came up with a way to use Str.match instead. If I convert each Match-object into a Hash I can use deconstruction in a signature of a pointy block.

    my Seconds $to-wait = @timicles»\
        .match(/<number> <suffix>+/)».hash\ # the +-quatifier is a workaround
        .map(-> % ( Rat(Any) :$number, Str(Any) :$suffix ) { %unit-multipliers{$suffix} * $number })\
        .sum;

    Instead of using positionals I can use named arguments that correspond to the named regexes inside the match arguments.

    Even in such a small pice of code things fall into place. Hyper-method-calls get rid of simple loops. The well crafted buildin types allow signature deconstruction to actually work without loads of temporary variables. It’s almost as certain language designers where aiming to make a most elegant language.

    rakudo.org: Rakudo Star Release 2018.04

    Published on 2018-05-07T00:00:00

    Zoffix Znet: WANTED: Perl 6 Historical Items

    Published on 2018-04-16T00:00:00

    A call to collect memorabilia for a Perl 6 museum

    Perl 6 Inside Out: 🔬 75. my $x = $x in Perl 6

    Published by andrewshitov on 2018-04-10T08:51:58

    What happens if you’ll try to create a new variable and immediately initialise it by itself, as shown in the following test code:

    my $x = $x;

    This does not work (which is expected), but Perl 6 is so kind to the user  that it gives an error message prepared especially for this case:

    ===SORRY!=== Error while compiling:
    Cannot use variable $x in declaration to initialize itself
    ------> my $x = $⏏x;
      expecting any of:
      term

    Let us find the place in the code where the error message is triggered. This case is captured in the Grammar of Perl 6, at the place where variable is parsed:

    token variable {
        . . .
        | <sigil>
          [ $<twigil>=['.^'] <desigilname=desigilmetaname>
            | <twigil>? <desigilname> ]
          [ <?{ !$*IN_DECL && $*VARIABLE && $*VARIABLE eq 
            $<sigil> ~ $<twigil> ~ $<desigilname> }>
              {
                  self.typed_panic: 'X::Syntax::Variable::Initializer', 
                  name => $*VARIABLE
              }
          ]?
        . . .
    }

    The condition to throw an exception is a bit wordy, but you can clearly see here that the whole variable name is checked, including both sigil and potential twigil.

    The exception itself is located in src/core/Exception.pm6 (notice that file extensions were changed from .pm to .pm6 recently), and it is used only for the above case:

    my class X::Syntax::Variable::Initializer does X::Syntax {
        has $.name = '<anon>';
        method message() {
            "Cannot use variable $!name in declaration to initialize itself"
        }
    }

    And that’s all for today. Rakudo Perl 6 sources can be really transparent sometimes! 🙂

    Perl 6 Inside Out: 🦋 74. Typed hashes in Perl 6

    Published by andrewshitov on 2018-04-08T09:35:41

    In Perl 6, you can restrict the content of a variable container by specifying its type, for example:

    my Int $i;

    There is only one value in a scalar variable. You can extend the concept to arrays and let its element to keep only integers, as it is done in the next example:

    > my Int @i;
    []
    
    > @i.push(42);
    [42]
    
    > @i.push('Hello');
    Type check failed in assignment to @i;
    expected Int but got Str ("Hello")
      in block <unit> at <unknown file> line 1

    Hashes keeps pairs, so you can specify the type of both keys and values. The syntax is not deductible from the above examples.

    First, let us announce the type of the value:

    my Str %s;

    Now, it is possible to have strings as values:

    > %s<Hello> = 'World'
    World
    
    > %s<42> = 'Fourty-two'
    Fourty-two

    But it’s not possible to save integers:

    > %s<x> = 100
    Type check failed in assignment to %s;
    expected Str but got Int (100)
      in block <unit> at <unknown file> line 1

    (By the way, notice that in the case of %s<42> the key is a string.)

    To specify the type of the second dimension, namely, of the hash keys, give the type in curly braces:

    my %r{Rat};

    This variable is also referred to as object hash.

    Having this, Perl expects you to have Rat keys for this variable:

    > %r<22/7> = pi
    3.14159265358979
    
    > %r
    {22/7 => 3.14159265358979}

    Attempts to use integers or strings, for example, fail:

    > %r<Hello> = 1
    Type check failed in binding to parameter 'key';
    expected Rat but got Str ("Hello")
      in block <unit> at <unknown file> line 1
    
    > %r{23} = 32
    Type check failed in binding to parameter 'key';
    expected Rat but got Int (23)
      in block <unit> at <unknown file> line 1

    Finally, you can specify the types of both keys and values:

    my Str %m{Int};

    This variable can be used for translating month number to month names but not vice versa:

    > %m{3} = 'March'
    March
    
    > %m<March> = 3
    Type check failed in binding to parameter 'key';
    expected Int but got Str ("March")
      in block <unit> at <unknown file> line 1

     

    Perl 6 Inside Out: 🔬73. Keys, values, etc. of hashes in Perl 6

    Published by andrewshitov on 2018-04-07T09:46:26

    Today, we will take a look at a few methods of the Hash class that return all hash keys or values or both:

    > my %h = H => 'Hydrogen', He => 'Helium', Li => 'Lithium';
    {H => Hydrogen, He => Helium, Li => Lithium}
    
    > %h.keys;
    (H Li He)
    
    > %h.values;
    (Hydrogen Lithium Helium)
    
    > %h.kv;
    (H Hydrogen Li Lithium He Helium)

    While you may want to go directly to the src/core/Hash.pm6 file to see the definitions of the methods, you will not find them there. The Hash class is a child of Map, and all these methods are defined in src/core/Map.pm6. Getting keys and values is simple:

    multi method keys(Map:D:) {
        Seq.new(Rakudo::Iterator.Mappy-keys(self))
    }
    
    multi method values(Map:D:) {
        Seq.new(Rakudo::Iterator.Mappy-values(self))
    }
    
    

    For the kv method, more work has to be done:

    multi method kv(Map:D:) {
        Seq.new(class :: does Rakudo::Iterator::Mappy {
            has int $!on-value;
    
            method pull-one() is raw {
                . . .
            }
            method skip-one() {
                . . .
            }
            method push-all($target --> IterationEnd) {
                . . .
            }
        }.new(self))
    }

    As you see, the method returns a sequence that is built using an anonymous class implementing the Rakudo::Iterator::Mappy role. We already saw how this approach is used in combination with defining pull-one and push-all methods.

    Let us look at another set of methods, pairs and antipairs. One of them is simple and straightforward:

    multi method pairs(Map:D:) {
        Seq.new(self.iterator)
    }

    Another one is using an intermediate class:

    multi method antipairs(Map:D:) {
        Seq.new(class :: does Rakudo::Iterator::Mappy {
            method pull-one() {
                . . .
            }
            method push-all($target --> IterationEnd) {
            . . .
            }
        }.new(self))
    }

    Both methods produce results of the same structure:

    > %h.antipairs
    (Hydrogen => H Lithium => Li Helium => He)
    
    > %h.pairs
    (H => Hydrogen Li => Lithium He => Helium)

     

    Perl 6 Inside Out: 🔬72. Superscripts in Perl 6

    Published by andrewshitov on 2018-04-05T08:33:58

    In Perl 6, you can use superscript indices to calculate powers of numbers, for example:

    > 2⁵
    32
    
    > 7³
    343

    It also works with more than one digit in the superscript:

    > 10¹²
    1000000000000

    You can guess that the above cases are equivalent to the following:

    > 2**5
    32
    > 7**3
    343
    
    > 10**12
    1000000000000

    But the question is: How on Earth does it work? Let us find it out.

    For the Numeric role, the following operation is defined:

    proto sub postfix:<ⁿ>(Mu $, Mu $) is pure {*}
    multi sub postfix:<ⁿ>(\a, \b) { a ** b }

    Aha, that is what we need, and the superscript notation is converted to the simple ** operator here.

    You can visualise what exactly is passed to the operation by printing the operands:

    multi sub postfix:<ⁿ>(\a, \b) { 
        nqp::say('# a = ' ~ a);
        nqp::say('# b = ' ~ b);
        a ** b 
    }

    In this case, you’ll see the following output for the test examples above:

    > 2⁵
    # a = 2
    # b = 5
    
    > 10¹²
    # a = 10
    # b = 12

    Now, it is time to understand how the postfix that extracts superscripts works. Its name, , written in superscript, should not mislead you. This is not a magic trick of the parser, this is just a name of the symbol, and it can be found in the Grammar:

    token postfix:sym<ⁿ> {
        <sign=[⁻⁺¯]>? <dig=[⁰¹²³⁴⁵⁶⁷⁸⁹]>+ <O(|%autoincrement)>
    }

    You see, this symbol is a sequence of superscripted digits with an optional sign before them. (Did you think of a sign before we reached this moment in the Grammar?)

    Let us try negative powers, by the way:

    > say 4⁻³
    # a = 4
    # b = -3
    0.015625

    Also notice that the whole construct is treated as a postfix operator. It can also be applied to variables, for example:

    > my $x = 9
    9
    > say $x²
    # a = 9
    # b = 2
    81

    So, a digit in superscript is not a part of the variable’s name.

    OK, the final part of the trilogy, the code in Actions, which parses the index:

    method postfix:sym<ⁿ>($/) {
        my $Int := $*W.find_symbol(['Int']);
        my $power := nqp::box_i(0, $Int);
        for $<dig> {
            $power := nqp::add_I(
               nqp::mul_I($power, nqp::box_i(10, $Int), $Int),
               nqp::box_i(nqp::index("⁰¹²³⁴⁵⁶⁷⁸⁹", $_), $Int),
               $Int);
        }
    
        $power := nqp::neg_I($power, $Int) 
            if $<sign> eq '⁻' || $<sign> eq '¯';
        make QAST::Op.new(:op<call>, :name('&postfix:<ⁿ>'), 
                          $*W.add_numeric_constant($/, 'Int', $power));
    }

    As you can see here, it scans the digits and updates the $power variable by adding the value at the next decimal position (it is selected in the code above).

    The available characters are listed in a string, and to get its value, the offset in the string is used. The $<dig> match contains a digit, you can see it in the Grammar:

    <dig=[⁰¹²³⁴⁵⁶⁷⁸⁹]>+

     

    Perl 6 Inside Out: 🔬71. Implementing Int.sleep() in Perl 6

    Published by andrewshitov on 2018-04-04T08:32:37

    Hello! Yesterday, I was giving my Perl 6 Intro course at the German Perl Workshop in Gummersbash. It was a great pleasure to prepare and run this one-day course, and, while it was difficult to cover everything, we touched all main aspects of the Perl 6 language: from variables to regexes and parallel computing. Of course, it was only a top-level overview, and there was not enough time to make all the exercises. You can do them at home, here’s the Perl 6 Intro – Exercises PDF file.

    Among the rest, we tried to implement the sleep method for integers. The rationale behind that is that it is possible to say:

    > 10.rand
    9.9456903794802

    But not:

    > 10.sleep
    No such method 'sleep' for invocant of type 'Int'
      in block <unit> at <unknown file> line 1

    OK, so let’s first implement the simplest form of sleep for Ints only. Go to src/core/Int.pm6 and add the following:

    my class Int does Real {
    
        method sleep() {
            nqp::sleep($!value);
        }

    Here’s a photo from the screen:

    29695497_10156162162038326_7927919948344098147_n

    There is no declaration of the $!value attribute in this file, but we know that it can be found somewhere in Perl6/Metamodel/BOOTSTRAP.nqp:

    # class Int is Cool {
    # has bigint $!value is box_target;
    Int.HOW.add_parent(Int, Cool);
    Int.HOW.add_attribute(Int,
        BOOTSTRAPATTR.new(:name<$!value>, :type(bigint), 
                          :box_target(1), :package(Int)));
    Int.HOW.set_boolification_mode(Int, 6);
    Int.HOW.publish_boolification_spec(Int);
    Int.HOW.compose_repr(Int);

    Compile and run. The desired code works now:

    > 3.sleep
    # sleeping 3 seconds
    >

    What can be changed here? The first idea is to allow non-integer numbers as the delay duration. As Int does the Real role, just move the method to src/core/Real.pm and get the value using the Num method instead of reading $!value directly (there is no such attribute in the Real role):

    my role Real does Numeric {
    
        method sleep() { 
            nqp::sleep(self.Num);
        }

    Now it also works with rationals and floating-point numbers:

    > 2.sleep
    2
    
    > 3.14.sleep
    3.14
    
    > pi.sleep
    3.14159265358979

    Before wrapping it up, let us take a look at the body of the sleep subroutine. It is defined in src/core/Date.pm6:

    proto sub sleep(|) {*}
    multi sub sleep(--> Nil) { sleep(*) }
    multi sub sleep($seconds --> Nil) {
        # 1e9 seconds is a large enough value that still makes VMs sleep
        # larger values cause nqp::sleep() to exit immediatelly (esp. on 32-bit)
        if nqp::istype($seconds,Whatever) || $seconds == Inf {
            nqp::sleep(1e9) while True;
        }
        elsif $seconds > 1e9 {
            nqp::sleep($_) for gather {
                1e9.take xx ($seconds / 1e9);
                take $seconds - 1e9 * ($seconds / 1e9).Int;
            }
        }
        elsif $seconds > 0e0 {
            nqp::sleep($seconds.Num);
        }
    }

    The code is very clear and does not need any comments.

    And maybe just to see why our modified Rakudo printed the time after sleep in the tests above, let’s refer to the documentation of NQP to see that its sleep function’s return value is the number of seconds:

    ## sleep
    * `sleep(num $seconds --> num)`
    
    Sleep for the given number of seconds (no guarantee is made
    how exact the time sleeping is spent.)
    Returns the passed in number.

     

    my Timotimo \this: Tangentially related work

    Published by Timo Paulssen on 2018-03-26T17:30:30

    Hi there, it's already been three weeks since my first blog post on my TPF grant work. In between then and now the nice folks over at Edument made public the work I've been doing on the side for a couple of months. Fortunately, my grant work benefits a whole lot from this as well. Being able to debug (set breakpoints, inspect variable contents, single-step execution) the profile dumping code in nqp (re-used in Rakudo), as well as the heap snapshot loading code in App::MoarVM::HeapAnalyzer::Model lets me more easily figure out why things might be wrong or even crashing.

    Since Edument's product is Cro, the reactive framework for implementing and consuming microservices, I use simple Cro applications as test subjects for the profilers, as well as the debugger.


    Photo by Erik-Jan Leusink / Unsplash

    Yesterday I took the first close look at the Cro app that powers the new profiler frontends, by running it under the heap profiler. I was rather surprised to find that even while no requests were being made, the heap snapshot file kept growing at a hundred megabytes every few seconds. Something was clearly amiss.

    To understand why this happens you must know that MoarVM will take a heap snapshot after every GC run. That means something must be causing the GC to run frequently even if no actual work is being done.

    Fortunately, I know that Rakudo's ThreadPoolScheduler has a built-in supervisor that has an eye on the performance of the thread pool. It runs on its own thread and wakes up a hundred times every second.

    My recent profiler work to make multi-threaded applications run properly under the regular profiler let me have a closer look at what was being allocated. Turns out a lot of objects related to iterating over a Range object were being created. A single function was using range iteration, but that accounted for a huge chunk of allocations. Looking at what functions allocate the different types of objects, you can see that pretty much 100% of all Scalar allocations were caused by iterating over a Range.

    The Instrumented Profiler shows a table of which routines allocate how many Objects of type Scalar
    Scalars may only hold 3 pointers in them on top of the common object header that's 16 bytes big, but it surely adds up! (measurement taken over a 60 second period)

    So just changing the for ^worker-list.elems into an equivalent loop loop got allocations down significantly.

    There was, of course, more left to do. The math we were doing to figure out how active the process has been since we last woke up (including a moving average) caused some boxing and unboxing. A call to a helper method was allocating empty hashes for named arguments every time (something we can often optimize away completely, but in this case we couldn't be sure that it'd be safe). And finally, the getrusage op was creating a fresh int array every time.

    I was initially reluctant to make the code less readable in the interest of performance. However, the supervisor allocating absolutely nothing was almost achieved. Lizmat inlined the getrusage-total helper sub that caused boxing and unboxing on every call, and I decided to inline the prod-affinity-workers helper method as well – this one was only used in a single place, anyway.

    The last piece of the puzzle was the getrusage op that allocated integer arrays every time it was called. To get the last drop of performance out of the supervisor thread, I changed the implementation of nqp::getrusage to take an already allocated array.

    After all this work, the ThreadPoolScheduler will not allocate anything at all if nothing is happening.

    I hope I have given you a little insight into what working on performance can look like.

    Now that I've shaved this yak, I can properly profile and analyze Cro applications and anything that runs tasks with the start keyword, like the backend of the heap analyzer!

    I hope to see you back on my blog when the next blog post hits the 'net!
      - Timo

    6guts: Remote Debug Support for MoarVM

    Published by jnthnwrthngtn on 2018-03-13T22:29:43

    Some years back, I worked on bringing basic debug support to Rakudo Perl 6. It works by taking the program AST and instrumenting it. This approach produced a somewhat useful result, but also carries a number of limitations:

    Enter the Edument Team

    At Edument, the company where I work, we’re keen to support Perl 6 and drive it forward. Last summer, we released Cro. In the autumn, we started work on our next Perl 6 product – which we’ll be announcing in just a couple more weeks. Along the way, we realized that it really needed Perl 6 to have a better debugging solution. So what did we do?

    We decided to pitch in and fund its development, of course! During the winter, we’ve worked on adding remote debug support to MoarVM, and today we’ve opened a pull request with it.

    Some details

    With our additions, MoarVM can be started with a flag indicating it should run a debug server, along with a port that it should listen on. It can then either wait for a connection before doing anything, or run the program as normal but allow for a connection to be made later.

    The debug protocol is defined in terms of MessagePack, which you can think of as being like a binary form of JSON. The PR includes documentation of the protocol, and we hope that having based it on an existing serialization format will make implementation of that easy for those who should wish to do so.

    The implemented features available through the protocol include:

    We’ve more plans for the future, but this is already a quite decent feature set that opens up a lot of possibilities.

    A Perl 6 library and basic debug CLI

    Along with the debug server implementation in MoarVM, we’re also releasing a Perl 6 module that speaks the debug protocol, along with a basic, but useful, command line application built using it. These aren’t things that we directly needed, but we hope the CLI will be useful (and, of course, contributions are welcome – I’m sure I’ll be patching it some), and that the library will pave the way for further interesting tools that might be built in terms of the debug protocol.

    In Closing

    All being well, the next MoarVM release will include remote debug support. With time, this will lead to much better debugging support for Perl 6, to keep pace with the growing size and concurrent nature of applications people are building in Perl 6 today. Enjoy!

    my Timotimo \this: Delays and Delights

    Published by Timo Paulssen on 2018-03-04T23:24:34

    Delays and Delights

    Hi, my name is timotimo and I'm a Perl 6 developer. I've set up this blog to write reports on my TPF Grant.

    Before the actual report starts, I'd like to issue an apology. In between my grant application and the grant being accepted I developed a bit of RSI that lasted for multiple months. I already anticipated that near the end of January a move would occupy me a bit, but I had no idea how stressful it would turn out to be, and how long afterwards it would keep me occupied.

    Delays and Delights
    Photo by Lyndsey B / Unsplash

    I regret that it took me so long to actually get started. However, I've already got little bits to show for the first report of this grant!

    Delight №1: Non-crashy multi-threaded profiles

    Until now if you've added a signal handler for Ctrl-C to your program, or used run, shell, or even Proc::Async or any async IO, rakudo or moarvm will have started an additional thread for you. Even if you don't necessarily realize it, this caused the profiler to either violently explode, or return useless or partial results.

    Just these past few days I've made a bit of reliability work for the profiler available to everyone running rakudo from the latest source code. Now the profiler will only sometimes abort with the error message "profiler lost sequence" – a bug that I'm also going to chase down as part of the grant. On top of that, the HTML profiler frontend now shows timing and allocations from every thread.

    Delight №2: Faster Heap Snapshots

    N.B.: I have done the work discussed in this section before the grant actually started, but I think it's still interesting for you.

    As you can tell from the – sadly mildly messed-up – grant application, I also work on a second profiler: The Heap Snapshot Profiler. It takes a snapshot of the structure of all objects in memory, and their connections. With this information, you can figure out what kinds of objects account for how much of your memory usage, and for what reason any given object is not being removed by the garbage collector.

    If you've already tried out this profiler in the past, you may have noticed that it incurs a significant memory usage increase during run-time. After that, it takes a surprising amount of time to load in the heap snapshot analyzer. This changed noticeably when I implemented a new format for heap snapshots.

    Until then, the format had one line (i.e. \n delimited) per snapshot (i.e. for each GC run) and a json-encoded list of strings up front. The snapshots themselves were then a few lines with lists of integers.
    This caused two little issues in terms of performance:

    The binary-based format I replaced it with addresses both of these issues, and has a few extra features for speed purposes:

    Armed with the index at the end of the file, the binary format can be read by multiple threads at the same time, and that's exactly what the new Heap Snapshot Analyzer will do. In addition to the start positions of each section, there's also a pointer right into the middle of the one section that holds variable-sized entries. That way both halves can be read at the same time and cheaply combined to form the full result.

    The "summary all" command loads every snapshot, measures the total size of recorded objects, how many objects there are, and how many connections exist. The result is displayed as a table. Running this against a 1.1 gigabyte big example snapshot with 44 snapshots takes about a minute, uses up 3⅓ CPU cores out of the 4 my machine has, and maxes out at 3 gigs of ram used.[2] That's about 19 megabytes per second. It's not blazing fast, but it's decent.

    Delight №3: Web Frontend

    Sadly, there isn't anything to show for this yet, but I've started a Cro application that lets the user load up a heap snapshot file and load individual snapshots in it.

    It doesn't seem like much at all, but the foundation on which the other bits will rest is laid now.

    I intend for the next posts to have a bunch of tiny animated gif screencasts for you to enjoy!

    Delight №4: Faster Profile File Writing

    The SQL output will likely be the primary data storage format after my grant is done. Therefore I've taken first steps to optimize outputting the data. Right now it already writes out data about 30% faster during the actual writing stage. The patch needs a bit of polish, but then everyone can enjoy it!

    Next steps

    The next thing I'd like to work towards is trying out the profiler with a diverse set of workloads: From hyper/race to a Cro application. That will give me a good idea of any pain points you'd encounter. For example, once the ThreadPoolScheduler's supervisor thread runs, it'll spend a majority of its time sleeping in between ticks. This shows up very prominently in the Routines list, to name one example.

    Of course, I take inspiration from my fellow Perl 6 developers and users on the IRC channel and the mailing lists, who offer a steady supply of challenges :)

    If you have questions, suggestions, or comments, please feel free to ping me on IRC, or find this blog post on reddit.

    Thanks for reading; see you in the next one!
      - Timo


    1. It could have been done in C code, but it feels weird to have JSON string escaping code built into MoarVM. ↩︎

    2. Figuring out why the ram usage is so high is also on my list. Amusingly, the heap analyzer can help me improve the heap analyzer! ↩︎

    brrt to the future: Some things I want

    Published by Bart Wiegmans on 2018-02-27T16:38:00

    Lately I've been fixing a few bugs here and there in the JIT compiler, as well as trying to advance the JIT expression optimizer. The story of those bugs is interesting but in this post I want to focus on something else, namely some support infrastructure that I think we should have that would make working on MoarVM and spesh/jit in particular much nicer.

    There are a bunch of things related to runtime control of spesh and the JIT:
    Then there's more ambitious stuff, that still falls under 'housekeeping':
    And there's more ambitious stuff that would fall under optimizations and general functionality improvements:
    There is definitively more out there I want to do, but this should be enough to keep me busy for a while. And if anyone else wants to take a try at any of these, they'd be very welcome to :-).

    rakudo.org: Rakudo Star Release 2018.01

    Published on 2018-01-29T00:00:00

    6guts: Of sisters, stacks, and CPAN

    Published by jnthnwrthngtn on 2018-01-26T21:27:47

    Recently, an open letter was published by Elizabeth Mattijsen, a long-time contributor to the Perl community who has in recent years contributed copiously to Rakudo Perl 6, as well as working to promote Perl (both 5 and 6) at numerous events. The letter made a number of points, some of them yielding decidedly unhappy responses. I’ve been asked a number of times by now for my take on the letter and, having had time to consider things, I’ve decided to write up my own thoughts on the issues at hand.

    Oh sister

    A number of years back, I played a part in forming the “sister language narrative”. The reality – then and now – is that both Perl 5 and Perl 6 have userbases invested in them and a team willing to develop the languages and their implementations. These userbases partly overlap, and partly consist of people with an interest in only one or the other.

    Following the Perl mantra that “there’s more than one way to do it”, I saw then – and see now – no reason for the advent of Perl 6 to impose an “end of life” on Perl 5. During the many years that Perl 6 took to converge on a stable language release with a production-ready implementation, Perl 5 continued to evolve to better serve its userbase. And again, I see no reason why it should not continue to do so. For one, Perl 6 is not a drop-in replacement for Perl 5, and it’s unreasonable to expect everyone using Perl 5 today to have a business case for migrating their existing systems to use Perl 6. When there’s a team eager to carry Perl 5 forwards, what’s to lose in continuing to work towards serving that Perl 5 userbase better? Caring about and supporting an existing userbase is a sign of a mature language development community. It shows that we’re not about “move fast and break stuff”, but “you can trust us with your stuff”.

    Moreover, it’s very much the case that Perl 5 and Perl 6 make different trade-offs. To pick one concrete example, Perl 6 makes it easy to run code across multiple threads, and even uses multiple threads internally (for example, performing optimization and JIT compilation on a background thread). Which is great…except the only winning move in a game involving both threads and fork() is not to play. Sometimes one just can’t have their cake and eat it, and if you’re wanting a language that more directly gives you your POSIX, that’s probably always going to be a strength of Perl 5 over Perl 6.

    For these reasons and more, it was clear to me that the best way forward was to simply accept, and rejoice in, the Perl community having multiple actively developed languages to offer the world. So where did the sister language narrative come in?

    The number 6 happens to be a larger number than 5, and this carries some implications. I guess at the outset of the Perl 6 project, it was indeed imagined that Perl 6 would be a successor to Perl 5. By now, it’s instead like – if you’ll excuse me a beer analogy – Rochefort 8 and Rochefort 10: both excellent beers, from the same brewery, who have no reason to stop producing the 8 simply because they produce the 10. I buy both, and they’re obviously related, though different, and of course I have my preference, but I’m glad they both exist.

    The point of the “sister language” narrative was to encourage those involved with Perl 5 and Perl 6 to acknowledge that both languages will continue to move forward, and to choose their words and actions so as to reflect this.

    I continue to support this narrative, both in a personal capacity, and as the Rakudo Perl 6 Pumpking. (For those curious, “pumpking” is a cute Perl-y word for “project leader”, although one could be forgiven for guessing it means “flatulent monarch”.) Therefore, I will continue to choose my words and actions so as to support it, unless a new consensus with equally broad community buy-in comes to replace it.

    I accept that this narrative may not be perfect for everyone, but it has been quite effective in encouraging those who feel strongly about just Perl 5 or just Perl 6 to focus their efforts constructively on building things, rather than trying to tear down the work of others. Therefore, it was no surprise to me that, when Liz’s open letter and follow-up comments went against that narrative, the consequences were anything but constructive.

    I can’t, and don’t feel I should try to, control the views of others who contribute to Perl 6. Within reason, a diversity of views is part of a healthy community. I do, however, have a few things to ask of everyone. Firstly, when expressing a view that is known not to have widespread community consensus, please go to some lengths to make it clear it is a personal position. Secondly, when reading somebody’s expressed position on a matter, don’t assume it is anything more than their position unless clearly stated. And – perhaps most importantly – please also go to lengths to discuss topics calmly and politely. I was deeply disappointed by the tone of many of the discussions I saw taking place over the last week. We can do better.

    Perl 5 on the Rakudo stack?

    The next section of the letter considered the possibility of a “Butterfly Perl 5” project: effectively, a port of Perl 5 to run atop of the Rakudo stack (in reality, this doesn’t involve Rakudo much at all, but rather NQP and MoarVM). As a compiler geek, this of course piques my interest, because what could be more fun that writing a compiler? :-) And before anyone gets excited – no, I don’t have the time to work on such a thing. But, in common with Liz, I’d be supportive of anyone wishing to experiment in that direction. There will be some deep challenges, and I’ll issue my usual warning that syntax is what gets all the attention but semantics are what will eat you alive.

    Where I will disagree, however, is on the idea of a moratorium on new features in Perl 5. These appear slowly anyway (not because Perl 5 Porters are inefficient, but because adding new features to such a widely used language with a 30-year-old runtime is just a really darn hard thing to be doing). Given the immense technical challenges a Perl 5-on-new-VM effort would already face, the odd new feature would be a drop in the bucket.

    My one piece of unsolicited advice to those working on Perl 5 would be to borrow features from Perl 6 very carefully, because they are generally predicated on a different type system and many other details that differ between the Perls. (My diagnosis of why smartmatch has presented such a challenge in Perl 5 is because it was designed assuming various aspects of the Perl 6 type system, which don’t map neatly to Perl 5. This isn’t surprising, given Perl 6 very consciously set out to do differently here.) But should Perl 5 simply stop exploring ways to make things better for is userbase? No, I don’t think so. From a Perl 5 user point of view (which is the only one I have), adding subroutine signatures – which deliver existing semantics with less boilerplate – feels like a sensible thing to do. And adding features to keep up with the needs of the latest versions of the Unicode specification is a no-brainer. “Perl (5 or 6) is great at Unicode” is a meme that helps us all.

    The CPAN butterfly plan

    The final part of the letter proposes a focused porting effort of Perl 5 modules to Perl 6. This idea has my support. While the Perl 6 module ecosystem has been growing – and that’s wonderful – there’s still a good number of things missing. Efforts to address that expands the range of tasks to which Perl 6 can be conveniently applied. Of course, one can reach such modules already with the excellent Inline::Perl5 too. Some folks have reservations about dual runtimes in production, however, and interop between two runtimes has some marshalling cost – although with recent optimization work, the cost has been brought well down from what it was.

    Of course, in some areas it’s strategic to build something afresh that takes into account the opportunities offered by Perl 6. That’s why I designed Cro by reading RFCs and considering the best way to implement them in Perl 6. Even then, I did it with the benefit of 20 years experience doing web stuff – without which, I suspect the result would have been rather less useful. Porting existing modules – taking time to tweak their APIs to feel more comfortable in Perl 6 – means that existing knowledge built up by the authors of those modules can be carried forward, which is surely a win.

    In closing

    I’ve had the privilege of working with Liz for a number of years. While her open letter makes a number of points I disagree with, I have no reason to believe it wasn’t written out of good intentions. Some people have wondered if any good can come of it. That’s up to us as a community. I think we can, at least, take away:

    And, last but not least, it has been clear that – while it has in the last days often been expressed in raw and heated ways – we, as the Perl community, have two languages we’re passionate about and are keen to drive forward. Let’s do that together, in peace, not in pieces.

    gfldex: Expensive Egg-Timers

    Published by gfldex on 2017-12-31T13:28:01

    If you use a CLI you might have done something along the line.

    sleep 1m 30s; do-the-next-thing

    I have a script called OK that will display a short text in a hopeful green and morse code O-K via the PC speaker. By doing so I turn my computer into an expensive egg-timer.

    As of late I found myself waiting for longer periods of time and was missing a count-down so I could estimate how much more time I can waste playing computer games. The result is a program called count-down.

    Since I wanted to mimic the behaviour of sleep as closely as possible I had a peek into its source-code. That made me realise how lucky I am to be allowed to use Perl 6. If I strip all the extra bits a count-down needs I’m at 33 lines of code compared to 154 lines of GNU sleep. The boilerplate I have is mostly for readability. Like defining a subset called Seconds and a Rexex called number.

    Errors in the arguments to the script will be cought by the where clause in MAINs signature. Since there are no further multi candidates for MAIN that might interfere, the usage message will be displayed automatically if arguments are not recognized. Pretty much all lines in the C implementation deal with argument handling and the fact that they can’t trust their arguments until the last bit of handling is done. With a proper signature a Perl 6 Routine can fully trust its arguments and no further error handling is needed. Compared to the C version (that does a lot less) the code can be read linear from top to bottom and is much more expressive. After changing a few identifiers I didn’t feel the need for comments anymore. Even some unclear code like the splitting on numbers and keeping the values, becomes clear in the next lines where I sum up a list of seconds.

    Now I can comfortably count down the rest of a year that was made much better by a made better Perl 6. I wish you all a happy 2018.

    Perl 6 Advent Calendar: Bonus Xmas – Concurrent HTTP Server implementation and the scripter’s approach

    Published by ramiroencinas on 2017-12-25T01:52:24

    First of all, I want to highlight Jonathan Worthington‘s work with Rakudo Perl6 and IO::Socket::Async. Thanks Jon!

    ***

    I like to make scripts; write well-organized sequences of actions, get results and do things with them.

    When I began with Perl6 I discovered a spectacular ecosystem, where I could put my ideas into practice in the way that I like: script manner. One of these ideas was to implement a small HTTP server to play with it. Looking at other projects and modules related to Perl6, HTTP and sockets I discovered that the authors behind were programmers with a great experience with Object-Oriented programming.

    Perl6 paradigms

    Perl6 supports the three most popular programming paradigms:

    I think that the Object-Oriented paradigm is fine when you design an application or service that will grow, will do many and varied things and will have many changes. But I don’t like things that grow too much and will have many changes; that’s why I like scripts, for its native procedural approach, because it promote simplicity and effectiveness quickly. I like small (step by step) things that do great things quickly.

    The Functional paradigm is awesome in my opinion; you can take a function and use it like a var, among other amazings things.

    Perl6 Supplies are like a V12 engine

    When I started with Perl6 shortly after I started the translation of perl6intro.com to Spanish language. Looking at the documentation of Perl6 I discovered the great concurrent potential that Perl6 has. The concurrent aspect of Perl6 was more powerful than I thought.

    The idea I had of the HTTP server with Perl6 began with the Perl6 Supplies (Asynchronous data stream with multiple subscribers), specifically with the class IO::Socket::Async. All socket management, data transmission and concurrency is practically automatic and easy to understand. It was perfect for making and play with a small concurrent but powerful service.

    Based on the examples of the IO::Socket::Async documentation I started to implement a small HTTP server with pseudoCGI support in the mini-http-cgi-server project, and it worked as I expected. As I got what I wanted, I was satisfied and I left this project for a while. I didn’t like things to grow too much.

    But then, preparing a talk for the Madrid Perl Workshop 2017 (thanks to Madrid Perl Mongers and Barcelona Perl Mongers guys for the event support), I had enough motivation to do something more practical, something where web front-end coders could do their job well and communicate with the back-end where Perl6 is awaiting. On the one hand, the typical public html static structure, and on the other hand a Perl6 module including several webservices waiting for the web requests from the front-end guys.

    Then Wap6 was born (Web App Perl6).

    The Wap6 structure

    I like the structure for a web application that Wap6 implements:

    public folder contains the friendly front-end stuff, like static html, javascript, css, etc., that is, the front-end developer space. The webservices folder contains the back-end stuff: a Perl6 module including a function per webservice.

    This same folder level contains the solution entry point, a Perl6 script that, among other things like initialization server parameters, contains the mapping between routes and webservices:

    my %webservices =
      '/ws1' => ( &ws1, 'html' ),
      '/ws2' => ( &ws2, 'json' )
    ;
    

    As you can see, not only the routes are mapped to the corresponding webservice, but also specify the return content-type of the webservice (like HMTL or JSON). That is, you type http://domain/ws1 in the web browser and the ws1 function returns the response data with the corresponding content-type as we will see later.

    All the routes to the webservices are in %webservices hash and it is passed to the main funcion wap with other useful named params:

    wap(:$server-ip, :$server-port, :$default-html, :%webservices);

    The core of Wap6

    The wap funcion is located out side, in the core lib module that Wap6 use and contains the concurrent and elegant V12 engine:

    react {   
      whenever IO::Socket::Async.listen($server-ip,$server-port) -> $conn {
        whenever $conn.Supply(:bin) -> $buf {
          my $response = response(:$buf, :$current-dir, :$default-html, :%webservices);
          $conn.write: $response.encode('UTF-8');
          $conn.close;
        }
      }
    }
    

    This is a threes (react – whenever – IO::Socket::Async) reactive, concurrent and asynchronous context. When a transmission arrives from the web client ($conn), it is placed in a new Supply $buf of bin type ($conn.Suply(:bin)), and $buf with other things like the %webservices hash are sent to the response function that runs the HTTP logic. Finally, the return from the response function is written back to the web client.

    The response function (located out side, in the core lib too) contains the HTTP parser stuff: it splits the incoming data (the HTTP entity) into headers and body, it performs validations, it takes basic HTTP header information like the method (GET or POST) and the URI (Uniform Resource Identifier), it determines if the requested resource is a webservice (from the webservices folder) or static file (from the public folder), get the data from the resource (from static file or webservice) and returns back to wap function to write the response to the web client, as we have seen before.

    The Webservices

    The response function, validates $buf and extract the HTTP method from the request header that can be GET or POST (I don’t think that in the future it will support more HTTP methods). Case of GET method it puts the URL params (if any) into $get-params. Case of POST method, it puts the body request into $body.

    Then it’s time to check if the web client has requested a webservice. $get-params includes the URI and is extracted with the URI module, finally the result is placed in $path:

    given $path {
      when %webservices{"$_"}:exists {
        my ( &ws, $direct-type ) = %webservices{"$_"};
        my $type = content-type(:$direct-type);
        return response-headers(200, $type) ~ &ws(:$get-params, :$body);
      }
      ..
    }
    

    If $path exists in the %webservices hash, the client wants a webservice. Then it extracts the corresponding webservice callable function &ws from %webservices hash (yes, I also love Functional paradigm :-) ) and the correspondig content-type. Then it calls the webservice function &ws with the $get-params and the request $body parameters. Finally it returns the HTTP response entity that concatenates:

    The callable webservice &ws can be ws1, located in the Perl6 module from webservices folder:

    sub ws1 ( :$get-params, :$body ) is export {
      if $get-params { return 'From ws1: ' ~ $get-params; }
      if $body { return 'From ws1: ' ~ $body; }
    }
    

    In this demo context the webservice simply returns the input, that is, the $get-params (when GET) or the $body (when POST).

    When the client request a static file

    After discarding all the other possibilities, if the client request a static file hosted in the public folder, like html, js, css, etc, then:

    given $path {
    ..
      default {
        my $filepath = "$current-dir/public/$path";
        my $type = content-type(:$filepath);
        return response-headers(200, $type) ~ slurp "$current-dir/public/$path";
      }
    }
    

    It returns the response headers including the matched content-type and the requested file contents with slurp.

    And that’s all folks! a concurrent web server in the script-procedural manner: Wap6.

    Epilogue

    I’m happy with the results of Wap6. I don’t pretend that it grows a lot, but I’m always tempted to continue adding more features: SSL support (completed!), session management (in progress), cookies, file uploads, etc.

    Perl6 has put on the table a very powerful way to perform concurrent network operations: IO::Socket::Async, a masterpiece. Also, with Perl6 you can mix the Object-Oriented, Procedural and Functional paradigms as you wish. With these capabilities you can design a concurrent asynchronous service and implement it quickly.

    If you want something more serious approach with HTTP services and concurrency in the Perl6 ecosystem, take a look at Cro, it represents a great opportunity to establish Perl6 as a powerful entity in the HTTP services space. Jonathan Worthington wrote about it last 9th on this same Advent Calendar.

    Meanwhile, I will continue playing with Wap6, in the script manner, contributing with the Perl6 ecosystem and learning from the bests coders in the world, I mean: Perl and Perl6 coders, of course :-)

    Perl 6 Advent Calendar: Day 24 – Solving a Rubik’s Cube

    Published by coke on 2017-12-24T00:33:51

    Intro

    I have a speed cube on my wish list for Christmas, and I'm really excited about it. :) I wanted to share that enthusiasm with some Perl 6 code.

    I graduated from high school in '89, so I'm just the right age to have had a Rubik's cube through my formative teen years. I remember trying to show off on the bus and getting my time down to just under a minute. I got a booklet from a local toy store back in the 80s that showed an algorithm on how to solve the cube, which I memorized. I don't have the booklet anymore. I've kept at it over the years, but never at a competitive level.

    In the past few months, YouTube has suggested a few cube videos to me based on my interest in the standupmaths channel; seeing the world record come in under 5 seconds makes my old time of a minute seem ridiculously slow.

    Everyone I've spoken to who can solve the cube has been using a different algorithm than I learned, and the one discussed on standupmaths is yet a different one. The advanced version of this one seems to be commonly used by those who are regularly setting world records, though.

    Picking up this algorithm was not too hard; I found several videos, especially one describing how to solve the last layer. After doing this for a few days, I transcribed the steps to a few notes showing the list of steps, and the crucial parts for each step: desired orientation, followed by the individual turns for that step. I was then able to refer to a single page of my notebook instead of a 30-minute video, and after a few more days, had memorized the steps: being able to go from the notation to just doing the moves is a big speed up.

    After a week, I was able to solve it reliably using the new method in under two minutes; a step back, but not bad for a week's effort in my off hours. Since then (a few weeks now), I've gotten down to under 1:20 pretty consistently. Again, this is the beginner method, without any advanced techniques, and I'm at the point where I can do the individual algorithm steps without looking at the cube. (I still have a long way to go to be competitive though.)

    Notation

    A quick note about the notation for moves – given that you're holding the cube with a side on the top, and one side facing you, the relative sides are:

    L (Left) R (Right) U (Up) D (Down) F (Front) B (Back)

    If you see a lone letter in the steps, like B, that means to turn that face clockwise (relative to the center of the cube, not you). If you add a ʼ to the letter, that means counter clockwise, so would have the top piece coming down, while a R would have the bottom piece coming up.

    Additionally, you might have to turn a slice twice, which is written as U2; (Doesn't matter if it's clockwise or not, since it's 180º from the starting point.)

    Algorithm

    The beginner's algorithm I'm working with has the following basic steps:

    1. White cross 2. White corners 3. Second layer 4. Yellow cross 5. Yellow edges 6. Yellow corners 7. Orient yellow corners

    If you're curious as to what the individual steps are in each, you'll be able to dig through the Rubik's wiki or the YouTube video linked above. More advanced versions of this algorithm (CFOP by Jessica Fridrich) allow you to combine steps, have specific "shortcuts" to deal with certain cube states, or solve any color as the first side, not just white.

    Designing a Module

    As I began working on the module, I knew I wanted to get to a point where I could show the required positions for each step in a way that was natural to someone familiar with the algorithm, and to have the individual steps also be natural, something like:

     F.R.U.Rʼ.Uʼ.Fʼ 

    I also wanted to be able to dump the existing state of the cube; For now as text, but eventually being able to tie it into a visual representation as well,

    We need to be able to tell if the cube is solved; We need to be able to inspect pieces relative to the current orientation, and be able to change our orientation.

    Since I was going to start with the ability to render the state of the cube, and then quickly add the ability to turn sides, I picked an internal structure that made that fairly easy.

    The Code

    The latest version of the module is available on github. The code presented here is from the initial version.

    Perl 6 lets you create Enumerations so you can use actual words in your code instead of lookup values, so let's start with some we'll need:

    enum Side «:Up('U') :Down('D') :Front('F') :Back('B') :Left('L') :Right('R')»;
    enum Colors «:Red('R') :Green('G') :Blue('B') :Yellow('Y') :White('W') :Orange('O')»;

    With this syntax, we can use Up directly in our code, and its associated value is U.

    We want a class so we can store attributes and have methods, so our class definition has:

    class Cube::Three {
    has %!Sides;
    ...
    submethod BUILD() {
    %!Sides{Up} = [White xx 9];
    %!Sides{Front} = [Red xx 9];
    ...
    }
    }

    We have a single attribute, a Hash called %.Sides; Each key corresponds to one of the Enum sides. The value is a 9-element array of Colors. Each element on the array corresponds to a position on the cube. With white on top and red in front as the default, the colors and cell positions are shown here with the numbers & colors. (White is Up, Red is Front)

             W0 W1 W2
             W3 W4 W5
             W6 W7 W8
    G2 G5 G8 R2 R5 R8 B2 B5 B8 O2 O5 O8
    G1 G4 G7 R1 R4 R7 B1 B4 B7 O1 O4 O7
    G0 G3 G6 R0 R3 R6 B0 B3 B6 B0 B3 B6
             Y0 Y1 Y2
             Y3 Y4 Y5
             Y6 Y7 Y8
    

    The first methods I added were to do clockwise turns of each face.

    method F {
    self!rotate-clockwise(Front);
    self!fixup-sides([
    Pair.new(Up, [6,7,8]),
    Pair.new(Right, [2,1,0]),
    Pair.new(Down, [2,1,0]),
    Pair.new(Left, [6,7,8]),
    ]);
    self;
    }

    This public method calls two private methods (denoted with the !); one rotates a single Side clockwise, and the second takes a list of Pairs, where the key is a Side, and the value is a list of positions. If you imagine rotating the top of the cube clockwise, you can see that the positions are being swapped from one to the next.

    Note that we return self from the method; this allows us to chain the method calls as we wanted in the original design.

    The clockwise rotation of a single side shows a raw Side being passed, and uses array slicing to change the order of the pieces in place.

    # 0 1 2 6 3 0
    # 3 4 5 -> 7 4 1
    # 6 7 8 8 5 2
    method !rotate-clockwise(Side \side) {
    %!Sides{side}[0,1,2,3,5,6,7,8] = %!Sides{side}[6,3,0,7,1,8,5,2];
    }

    To add the rest of the notation for the moves, we add some simple wrapper methods:

    method F2 { self.F.F; }
    method Fʼ { self.F.F.F; }

    F2 just calls the move twice; Fʼ cheats: 3 rights make a left.

    At this point, I had to make sure that my turns were doing what they were supposed to, so I added a gist method (which is called when an object is output with say).

    say Cube::Three.new.U2.D2.F2.B2.R2.L2;
          W Y W
          Y W Y
          W Y W
    G B G R O R B G B O R O
    B G B O R O G B G R O R
    G B G R O R B G B O R O
          Y W Y
          W Y W
          Y W Y
    

    The source for the gist is:

    method gist {
    my $result;
    $result = %!Sides{Up}.rotor(3).join("\n").indent(6);
    $result ~= "\n";
    for 2,1,0 -> $row {
    for (Left, Front, Right, Back) -> $side {
    my @slice = (0,3,6) >>+>> $row;
    $result ~= ~%!Sides{$side}[@slice].join(' ') ~ ' ';
    }
    $result ~= "\n";
    }
    $result ~= %!Sides{Down}.rotor(3).join("\n").indent(6);
    $result;
    }

    A few things to note:

    The gist is great for stepwise inspection, but for debugging, we need something a little more compact:

    method dump {
    gather for (Up, Front, Right, Back, Left, Down) -> $side {
    take %!Sides{$side}.join('');
    }.join('|');
    }

    This iterates over the sides in a specific order, and then uses the gather take syntax to collect string representations of each side, then joining them all together with a |. Now we can write tests like:

    use Test; use Cube::Three;
    my $a = Cube::Three.new();
    is $a.R.U2...R....U2.L.U..U.L.dump,
    'WWBWWWWWB|RRRRRRRRW|BBRBBBBBO|OOWOOOOOO|GGGGGGGGG|YYYYYYYYY',
    'corners rotation';

    This is actually the method used in the final step of the algorithm. With this debug output, I can take a pristine cube, do the moves myself, and then quickly transcribe the resulting cube state into a string for testing.

    While the computer doesn't necessarily need to rotate the cube, it will make it easier to follow the algorithm directly if we can rotate the cube, so we add one for each of the six possible turns, e.g.:

    method rotate-F-U {
    self!rotate-clockwise(Right);
    self!rotate-counter-clockwise(Left);
    # In addition to moving the side data, have to
    # re-orient the indices to match the new side.
    my $temp = %!Sides{Up};
    %!Sides{Up} = %!Sides{Front};
    self!rotate-counter-clockwise(Up);
    %!Sides{Front} = %!Sides{Down};
    self!rotate-clockwise(Front);
    %!Sides{Down} = %!Sides{Back};
    self!rotate-clockwise(Down);
    %!Sides{Back} = $temp;
    self!rotate-counter-clockwise(Back);
    self;
    }

    As we turn the cube from Front to Up, we rotate the Left and Right sides in place. Because the orientation of the cells changes as we change faces, as we copy the cells from face to face, we also may have to rotate them to insure they end up facing in the correct direction. As before, we return self to allow for method chaining.

    As we start testing, we need to make sure that we can tell when the cube is solved; we don't care about the orientation of the cube, so we verify that the center color matches all the other colors on the face:

    method solved {
    for (Up, Down, Left, Right, Back, Front) -> $side {
    return False unless
    %!Sides{$side}.all eq %!Sides{$side}[4];
    }
    return True;
    }

    For every side, we use a Junction of all the colors on a side to compare to the center cell (always position 4). We fail early, and then succeed only if we made it through all the sides.

    Next I added a way to scramble the cube, so we can consider implementing a solve method.

    method scramble {
    my @random = <U D F R B L>.roll(100).squish[^10];
    for @random -> $method {
    my $actual = $method ~ ("", "2", "ʼ").pick(1);
    self."$actual"();
    }
    }

    This takes the six base method names, picks a bunch of random values, then squishes them (insures that there are no dupes in a row), and then picks the first 10 values. We then potentially add on a 2 or a ʼ. Finally, we use the indirect method syntax to call the individual methods by name.

    Finally, I'm ready to start solving! And this is where things got complicated. The first steps of the beginner method are often described as intuitive. Which means it's easy to explain… but not so easy to code. So, spoiler alert, as of the publish time of this article, only the first step of the solve is complete. For the full algorithm for the first step, check out the linked github site.

    method solve {
    self.solve-top-cross;
    }
    method solve-top-cross {
    sub completed {
    %!Sides{Up}[1,3,5,7].all eq 'W' &&
    %!Sides{Front}[5] eq 'R' &&
    %!Sides{Right}[5] eq 'B' &&
    %!Sides{Back}[5] eq 'O' &&
    %!Sides{Left}[5] eq 'G';
    }
    ...
    MAIN:
    while !completed() {
    # Move white-edged pieces in second row up to top
    # Move incorrectly placed pieces in the top row to the middle
    # Move pieces from the bottom to the top
    }
    }

    Note the very specific checks to see if we're done; we use a lexical sub to wrap up the complexity – and while we have a fairly internal check here, we see that we might want to abstract this to a point where we can say "is this edge piece in the right orientation". To start with, however, we'll stick with the individual cells.

    The guts of solve-top-cross are 100+ lines long at the moment, so I won't go through all the steps. Here's the "easy" section

    my @middle-edges =
    [Front, Right],
    [Right, Back],
    [Back, Left],
    [Left, Front],
    ;
    for @middle-edges -> $edge {
    my $side7 = $edge[0];
    my $side1 = $edge[1];
    my $color7 = %!Sides{$side7}[7];
    my $color1 = %!Sides{$side1}[1];
    if $color7 eq 'W' {
    # find number of times we need to rotate the top:
    my $turns = (
    @ordered-sides.first($side1, :k) -
    @ordered-sides.first(%expected-sides{~$color1}, :k)
    ) % 4;
    self.U for 1..$turns;
    self."$side1"();
    self.for 1..$turns;
    next MAIN;
    } elsif $color1 eq 'W' {
    my $turns = (
    @ordered-sides.first($side7, :k) -
    @ordered-sides.first(%expected-sides{~$color7}, :k)
    ) % 4;
    self.for 1..$turns;
    self."$side1"();
    self.U for 1..$turns;
    next MAIN;
    }
    }

    When doing this section on a real cube, you'd rotate the cube without regard to the side pieces, and just get the cross in place. To make the algorithm a little more "friendly", we keep the centers in position for this; we rotate the Up side into place, then rotate the individual side into place on the top, then rotate the Up side back into the original place.

    One of the interesting bits of code here is the .first(..., :k) syntax, which says to find the first element that matches, and then return the position of the match. We can then look things up in an ordered list so we can calculate the relative positions of two sides.

    Note that the solving method only calls to the public methods to turn the cube; While we use raw introspection to get the cube state, we only use "legal" moves to do the solving.

    With the full version of this method, we now solve the white cross with this program:

    #!/usr/bin/env perl6
    use Cube::Three;
    my $cube = Cube::Three.new();
    $cube.scramble;
    say $cube;
    say '';
    $cube.solve;
    say $cube;

    which generates this output given this set of moves (Fʼ L2 B2 L Rʼ Uʼ R Fʼ D2 B2). First is the scramble, and then is the version with the white cross solved.

          W G G
          Y W W
          Y Y Y
    O O B R R R G B O Y Y B
    R G O B R R G B G W O B
    Y B B R O W G G G W W O
          W W O
          Y Y O
          B R R
    
          Y W W
          W W W
          G W R
    O G W O R Y B B G R O G
    Y G G R R B R B Y R O G
    O O R Y O W O O R W Y B
          G G B
          B Y Y
          Y B B
    

    This sample prints out the moves used to do the scramble, shows the scrambled cube, "solves" the puzzle (which, as of this writing, is just the white cross), and then prints out the new state of the cube.

    Note that as we get further along, the steps become less "intuitive", and, in my estimation, much easier to code. For example, the last step requires checking the orientationof four pieces, rotating the cube if necessary, and then doing a 14-step set of moves. (shown in the test above).

    Hopefully my love of cubing and Perl 6 have you looking forward to your next project!

    I'll note in the comments when the module's solve is finished, for future readers.

    Perl 6 Advent Calendar: Day 23 – The Wonders of Perl 6 Golf

    Published by AlexDaniel on 2017-12-23T00:00:05

    Ah, Christmas! What could possibly be better than sitting around the table with your friends and family and playing code golf! … Wait, what?

    Oh, right, it’s not Christmas yet. But you probably want to prepare yourself for it anyway!

    If you haven’t noticed already, there’s a great website for playing code golf: https://code-golf.io/. The cool thing about it is that it’s not just for perl 6! At the time of writing, 6 other langs are supported. Hmmm…

    Anyway, as I’ve got some nice scores there, I thought I’d share some of the nicest bits from my solutions. All the trickety-hackety, unicode-cheatery and mind-blowety. While we are at it, maybe we’ll even see that perl 6 is quite concise and readable even in code golf. That is, if you have a hard time putting your Christmas wishes on a card, maybe a line of perl 6 code will do.

    I won’t give full solutions to not spoil your Christmas fun, but I’ll give enough hints for you to come up with competitive solutions.

    All I want for Christmas is for you to have some fun. So get yourself rakudo to make sure you can follow along. Later we’ll have some pumpkin pie and we’ll do some caroling. If you have any problems running perl 6, perhaps join #perl6 channel on freenode to get some help. That being said, https://code-golf.io/ itself gives you a nice editor to write and eval your code, so there should be no problem.

    Some basic examples

    Let’s take Pascal’s Triangle task as an example. I hear ya, I hear! Math before Christmas, that’s cruel. Cruel, but necessary.

    There’s just one basic trick you have to know. If you take any row from the Pascal’s Triangle, shift it by one element and zip-sum the result with the original row, you’ll get the next row!

    So if you had a row like:

    1 3 3 1

    All you do is just shift it to the right:

    0 1 3 3 1

    And sum it with the original row:

    1 3 3 1
    + + + +
    0 1 3 3 1
    =
    1 4 6 4 1

    As simple as that! So let’s write that in code:

    for ^16 { put (+combinations($^row,$_) for 0..$row) }

    You see! Easy!

    … oh… Wait, that’s a completely different solution. OK, let’s see:

    .put for 1, { |$_,0 Z+ 0,|$_ } … 16

    Output:

    1
    1 1
    1 2 1
    1 3 3 1
    1 4 6 4 1
    1 5 10 10 5 1
    1 6 15 20 15 6 1
    1 7 21 35 35 21 7 1
    1 8 28 56 70 56 28 8 1
    1 9 36 84 126 126 84 36 9 1
    1 10 45 120 210 252 210 120 45 10 1
    1 11 55 165 330 462 462 330 165 55 11 1
    1 12 66 220 495 792 924 792 495 220 66 12 1
    1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
    1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
    1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1

    Ah-ha! There we go. So what happened there? Well, in perl 6 you can create sequences with a very simple syntax: 2, 4, 8 … ∞. Normally you’ll let it figure out the sequence by itself, but you can also provide a code block to calculate the values. This is awesome! In other languages you’d often need to have a loop with a state variable, and here it does all that for you! This feature alone probably needs an article or 𝍪.

    The rest is just a for loop and a put call. The only trick here is to understand that it is working with lists, so when you specify the endpoint for the sequence, it is actually checking for the number of elements. Also, you need to flatten the list with |.

    If you remove whitespace and apply all tricks mentioned in this article, this should get you to 26 characters. That’s rather competitive.

    Similarly, other tasks often have rather straightforward solutions. For example, for Evil Numbers you can write something like this:

    .base(2).comb(~1) %% 2 && .say for ^50

    Remove some whitespace, apply some tricks, and you’ll be almost there.

    Let’s take another example: Pangram Grep. Here we can use set operators:

    a..z .lc.comb && .say for @*ARGS

    Basically, almost all perl 6 solutions look like real code. It’s the extra -1 character oomph that demands extra eye pain, but you didn’t come here to listen about conciseness, right? It’s time to get dirty.

    Numbers

    Let’s talk numbers! 1 ² ③ ٤ ⅴ ߆… *cough*. You see, in perl 6 any numeric character (that has a corresponding numeric value property) can be used in the source code. The feature was intended to allow us to have some goodies like ½ and other neat things, but this means that instead of writing 50 you can write . Some golfing platforms will count the number of bytes when encoded in UTF-8, so it may seem like you’re not winning anything. But what about 1000000000000 and 𖭡? In any case, code-golf.io is unicode-aware, so the length of any of these characters will be 1.

    So you may wonder, which numbers can you write in that manner? There you go:

    -0.5 0.00625 0.025 0.0375 0.05 0.0625 0.083333 0.1
    0.111111 0.125 0.142857 0.15 0.166667 0.1875 0.2
    0.25 0.333333 0.375 0.4 0.416667 0.5 0.583333 0.6
    0.625 0.666667 0.75 0.8 0.833333 0.875 0.916667 1
    1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 10
    11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
    28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
    45 46 47 48 49 50 60 70 80 90 100 200 300 400 500
    600 700 800 900 1000 2000 3000 4000 5000 6000 7000
    8000 9000 10000 20000 30000 40000 50000 60000 70000
    80000 90000 100000 200000 216000 300000 400000
    432000 500000 600000 700000 800000 900000 1000000
    100000000 10000000000 1000000000000

    This means, for example, that in some cases you can save 1 character when you need to negate the result. There are many ways you can use this, and I’ll only mention one particular case. The rest you figure out yourself, as well as how to find the actual character that can be used for any particular value (hint: loop all 0x10FFFF characters and check their .univals).

    For example, when golfing you want to get rid of unnecessary whitespace, so maybe you’ll want to write something like:

    say 5max3 # ERROR

    It does not work, of course, and we can’t really blame the compiler for not untangling that mess. However, check this out:

    saymax# OUTPUT: «5␤»

    Woohoo! This will work in many other cases.

    Conditionals

    If there is a good golfing language, that’s not Perl 6. I mean, just look at this:

    puts 10<30?1:2 # ruby
    say 10 <30??1!!2 # perl 6

    Not only TWO more characters are needed for the ternary, but also some obligatory whitespace around < operator! What’s wrong with them, right? How dare they design a language with no code golf in mind⁉

    Well, there are some ways we can work around it. One of them is operator chaining. For example:

    say 5>3>say(42)

    If 5 is ≤ than 3, then there’s no need to do the other comparison, so it won’t run it. This way we can save at least one character. On a slightly related note, remember that junctions may also come in handy:

    say yes! if 5==3|5

    And of course, don’t forget about unicode operators: , , .

    Typing is hard, let’s use some of the predefined strings!

    You wouldn’t believe how useful this is sometimes. Want to print the names of all chess pieces? OK:

    say (.uniname».words»[2]
    # KING QUEEN ROOK BISHOP KNIGHT PAWN

    This saves just a few characters, but there are cases when it can halve the size of your solution. But don’t stop there, think of error messages, method names, etc. What else can you salvage?

    Base 16? Base 36? Nah, Base 0x10FFFF!

    One of the tasks tells us to print φ to the first 1000 decimal places. Well, that’s very easy!

    say 1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374847540880753868917521266338622235369317931800607667263544333890865959395829056383226613199282902678806752087668925017116962070322210432162695486262963136144381497587012203408058879544547492461856953648644492410443207713449470495658467885098743394422125448770664780915884607499887124007652170575179788341662562494075890697040002812104276217711177780531531714101170466659914669798731761356006708748071013179523689427521948435305678300228785699782977834784587822891109762500302696156170025046433824377648610283831268330372429267526311653392473167111211588186385133162038400522216579128667529465490681131715993432359734949850904094762132229810172610705961164562990981629055520852479035240602017279974717534277759277862561943208275051312181562855122248093947123414517022373580577278616008688382952304592647878017889921990270776903895321968198615143780314997411069260886742962267575605231727775203536139362

    Yes!!!

    Okay, that takes a bit more than 1000 characters… Of course, we can try to calculate it, but that is not exactly in the Christmas spirit. We want to cheat.

    If we look at the docs about polymod, there’s a little hint:

    my @digits-in-base37 = 9123607.polymod(37 xx *); # Base conversion

    Hmmm… so that gives us digits for any arbitrary base. How high can we go? Well, it depends on what form we would like to store the number in. Given that code-golf.io counts codepoints, we can use base 0x10FFFF (i.e. using all available codepoints). Or, in this case we will go with base 0x10FFFE, because:

    ☠☠☠⚠⚠⚠ WARNING! WARNING! WARNING! ⚠⚠⚠☠☠☠
    THIS WILL MAKE YOUR COMPUTER IMPLODE!
    UNICODE STRINGS ARE SUBJECT TO NORMALIZATION SO YOUR
    DATA WILL NOT BE PRESERVED. HIDE YOUR KIDS, HIDE YOUR
    WIFE. HIDE YOUR KIDS, HIDE YOUR WIFE. HIDE YOUR KIDS,
    HIDE YOUR WIFE. AND HIDE YOUR HUSBAND.
    ☠☠☠⚠⚠⚠ WARNING! WARNING! WARNING! ⚠⚠⚠☠☠☠

    When applied to our constant, it should give something like this:

    󻁾񤍠򷒋󜹕󘶸񙦅񨚑򙯬񗈼𢍟𪱷򡀋𢕍򌠐񘦵𔇆򅳒򑠒󌋩򯫞򶝠򚘣򣥨񫵗𿞸􋻩񱷳󟝐󮃞󵹱񿢖𛒕𺬛󊹛󲝂򺗝𭙪񰕺𝧒򊕆𘝞뎛􆃂򊥍񲽤򩻛󂛕磪󡯮끝򰯬󢽈󼿶󘓥򮀓񽑖򗔝󃢖񶡁􁇘󶪼񌍌񛕄񻊺򔴩寡񿜾񿸶򌰘񡇈򦬽𥵑󧨑򕩃򳴪񾖾򌯎󿥐񱛦𱫞𵪶򁇐󑓮򄨠򾎹𛰑𗋨䨀򡒶𰌡򶟫񦲋𧮁􍰍񲍚񰃦𦅂󎓜󸾧󉦩󣲦򄉼񿒣𸖉񿡥󬯞嗟𧽘񿷦򠍍🼟򇋹񖾷𖏕񟡥󜋝􋯱񤄓򭀢򌝓𱀉𫍡󬥝򈘏򞏡񄙍𪏸࿹𺐅񢻳򘮇𐂇񘚡ந򾩴󜆵𰑕򰏷񛉿򢑬򭕴𨬎󴈂􋵔򆀍񖨸􂳚󽡂󎖪񡉽񕧣񎗎򝤉򡔙񆔈󖾩󅾜񋩟򝼤񯓦󐚉񟯶򄠔𦔏򲔐o

    How do we reverse the operation? During one of the squashathons I found a ticket about a feature that I didn’t know about previously. Basically, the ticket says that Rakudo is doing stuff that it shouldn’t, which is of course something we will abuse next time. But for now we’re within the limits of relative sanity:

    say 1.,:1114110[o򲔐𦔏򄠔񟯶󐚉񯓦򝼤񋩟󅾜󖾩񆔈򡔙򝤉񎗎񕧣񡉽󎖪󽡂􂳚񖨸򆀍􋵔󴈂𨬎򭕴򢑬񛉿򰏷𰑕󜆵򾩴ந񘚡𐂇򘮇񢻳𺐅࿹𪏸񄙍򞏡򈘏󬥝𫍡𱀉򌝓򭀢񤄓􋯱󜋝񟡥𖏕񖾷򇋹🼟򠍍񿷦𧽘嗟󬯞񿡥𸖉񿒣򄉼󣲦󉦩󸾧󎓜𦅂񰃦񲍚􍰍𧮁񦲋򶟫𰌡򡒶䨀𗋨𛰑򾎹򄨠󑓮򁇐𵪶𱫞񱛦󿥐򌯎񾖾򳴪򕩃󧨑𥵑򦬽񡇈򌰘񿸶񿜾寡򔴩񻊺񛕄񌍌󶪼􁇘񶡁󃢖򗔝񽑖򮀓󘓥󼿶󢽈򰯬끝󡯮磪󂛕򩻛񲽤򊥍􆃂뎛𘝞򊕆𝧒񰕺𭙪򺗝󲝂󊹛𺬛𛒕񿢖󵹱󮃞󟝐񱷳􋻩𿞸񫵗򣥨򚘣򶝠򯫞󌋩򑠒򅳒𔇆񘦵򌠐𢕍򡀋𪱷𢍟񗈼򙯬񨚑񙦅󘶸󜹕򷒋񤍠󻁾.ords]

    Note that the string has to be in reverse. Other than that it looks very nice. 192 characters including the decoder.

    This isn’t a great idea for printing constants that are otherwise computable, but given the length of the decoder and relatively dense packing rate of the data, this comes handy in other tasks.

    All good things must come to an end; horrible things – more so

    That’s about it for the article. For more code golf tips I’ve started this repository: https://github.com/AlexDaniel/6lang-golf-cheatsheet

    Hoping to see you around on https://code-golf.io/! Whether using perl 6 or not, I’d love to see all of my submissions beaten.

    🥧

    Perl 6 Advent Calendar: Day 22 – Features of Perl 6.d

    Published by liztormato on 2017-12-22T00:00:49

    So there we are. Two years after the first official release of Rakudo Perl 6. Or 6.c to be more precise. Since Matt Oates already touched on the performance improvements since then, Santa thought to counterpoint this with a description of the new features for 6.d that have been implemented since then. Because there have been many, Santa had to make a selection.

    Tweaking objects at creation

    Any class that you create can now have a TWEAK method. This method will be called after all other initializations of a new instance of the class have been done, just before it is being returned by .new. A simple, bit contrived example in which a class A has one attribute, of which the default value is 42, but which should change the value if the default is specified at object creation:

    class A {
        has $.value = 42;
        method TWEAK(:$value = 0) { # default prevents warning
            # change the attribute if the default value is specified
            $!value = 666 if $value == $!value;
        }
    }
    # no value specified, it gets the default attribute value
    dd A.new;              # A.new(value => 42)
    
    # value specified, but it is not the default
    dd A.new(value => 77); # A.new(value => 77)
    
    # value specified, and it is the default 
    dd A.new(value => 42); # A.new(value => 666)

    Concurrency Improvements

    The concurrency features of Rakudo Perl 6 saw many improvements under the hood. Some of these were exposed as new features. Most prominent are Lock::Async (a non-blocking lock that returns a Promise) and atomic operators.

    In most cases, you will not need to use these directly, but it is probably good that you know about atomic operators if you’re engaged in writing programs that use concurrency features. An often occurring logic error, especially if you’ve been using threads in Pumpking Perl 5, is that there is no implicit locking on shared variables in Rakudo Perl 6. For example:

       my int $a;
        await (^5).map: {
            start { ++$a for ^100000 }
        }
        say $a; # something like 419318

    So why doesn’t that show 500000? The reason for this is that we had 5 threads that were incrementing the same variable at the same time. And since incrementing consists of a read step, an increment step and write step, it became very easy for one thread to do the read step at the same time as another thread. And thus losing an increment. Before we had atomic operators, the correct way of doing the above code would be:

       my int $a;
        my $l = Lock.new;
        await (^5).map: {
           start {
               for ^100000 {
                   $l.protect( { ++$a } )
               }
           }
        }
        say $a; # 500000

    This would give you the correct answer, but would be at least 20x as slow.

    Now that we have atomic variables, the above code becomes:

       my atomicint $a;
        await (^5).map: {
            start { ++⚛$a for ^100000 }
        }
        say $a; # 500000

    Which is very much like the original (incorrect) code. And this is at least 6x as fast as the correct code using Lock.protect.

    Unicode goodies

    So many, so many. For instance, you can now use , , as Unicode versions of <=, >= and != (complete list).

    You can now also create a grapheme by specifying the Unicode name of the grapheme, e.g.:

    say "BUTTERFLY".parse-names; # 🦋

    or create the Unicode name string at runtime:

    my $t = "THUMBS UP SIGN, EMOJI MODIFIER FITZPATRICK TYPE";
    print "$t-$_".parse-names for 3..6; # 👍🏼👍🏽👍🏾👍🏿

    Or collate instead of just sort:

    # sort by codepoint value
    say <ä a o ö>.sort; # (a o ä ö)
    # sort using Unicode Collation Algorithm
    say <ä a o ö>.collate; # (a ä o ö)

    Or use unicmp instead of cmp:

    say "a" cmp "Z"; # More
     say "a" unicmp "Z"; # Less

    Or that you can now use any Unicode digits Match variables ( for $1), negative numbers ( for -1), and radix bases (:۳("22") for :3("22")).

    It’s not for nothing that Santa considers Rakudo Perl 6 to have the best Unicode support of any programming language in the world!

    Skipping values

    You can now call .skip on Seq and Supply to skip a number of values that were being produced. Together with .head and .tail this gives you ample manipulexity with Iterables and Supplies.

    By the way, .head now also takes a WhateverCode so you can indicate you want all values except the last N (e.g. .head(*-3) would give you all values except the last three). The same goes for .tail (e.g. .tail(*-3) would give you all values except the first three).

    Some additions to the Iterator role make it possible for iterators to support the .skip functionality even better. If an iterator can be more efficient in skipping a value than to actually produce it, it should implement the skip-one method. Derived from this are the skip-at-least and skip-at-least-pull-one methods that can be provided by an iterator.

    An example of the usage of .skip to find out the 1000th prime number:

    say (^Inf).grep(*.is-prime)[999]; # 7919

    Versus:

    say (^Inf).grep(*.is-prime).skip(999).head; # 7919

    The latter is slightly more CPU efficient, but more importantly much more memory efficient, as it doesn’t need to keep the first 999 prime numbers in memory.

    Of Bufs and Blobs

    Buf has become much more like an Array, as it now supports .push, .append, .pop, .unshift, .prepend, .shift and .splice. It also has become more like Str with the addition of a subbuf-rw (analogous with .substr-rw), e.g.:

    my $b = Buf.new(100..105);
    $b.subbuf-rw(2,3) = Blob.new(^5);
    say $b.perl; # Buf.new(100,101,0,1,2,3,4,105)

    You can now also .allocate a Buf or Blob with a given number of elements and a pattern. Or change the size of a Buf with .reallocate:

    my $b = Buf.allocate(10,(1,2,3));
    say $b.perl; # Buf.new(1,2,3,1,2,3,1,2,3,1)
    $b.reallocate(5);
    say $b.perl; # Buf.new(1,2,3,1,2)

    Testing, Testing, Testing!

    The plan subroutine of Test.pm now also takes an optional :skip-all parameter to indicate that all tests in the file should be skipped. Or you can call bail-out to abort the test run marking it as failed. Or set the PERL6_TEST_DIE_ON_FAIL environment variable to a true value to indicate you want the test to end as soon as the first test has failed.

    What’s Going On

    You can now introspect the number of CPU cores in your computer by calling Kernel.cpu-cores. The amount of CPU used since the start of the program is available in Kernel.cpu-usage, while you can easily check the name of the Operating System with VM.osname.

    And as if that is not enough, there is a new Telemetry module which you need to load when needed, just like the Test module. The Telemetry module provides a number of primitives that you can use directly, such as:

    use Telemetry;
    say T<wallclock cpu max-rss>; # (138771 280670 82360)

    This shows the number of microseconds since the start of the program, the number of microseconds of CPU used, and the number of Kilobytes of memory that were in use at the time of call.

    If you want get to a report of what has been going on in your program, you can use snap and have a report appear when your program is done. For instance:

    use Telemetry;
    snap;
    Nil for ^10000000;  # something that takes a bit of time

    The result will appear on STDERR:

    Telemetry Report of Process #60076
    Number of Snapshots: 2
    Initial/Final Size: 82596 / 83832 Kbytes
    Total Time:           0.55 seconds
    Total CPU Usage:      0.56 seconds
    No supervisor thread has been running
    
    wallclock  util%  max-rss
       549639  12.72     1236
    --------- ------ --------
       549639  12.72     1236
    
    Legend:
    wallclock  Number of microseconds elapsed
        util%  Percentage of CPU utilization (0..100%)
      max-rss  Maximum resident set size (in Kbytes)

    If you want a state of your program every .1 of a second, you can use the snapper:

    use Telemetry;
    snapper;
    Nil for ^10000000;  # something that takes a bit of time

    The result:

    Telemetry Report of Process #60722
    Number of Snapshots: 7
    Initial/Final Size: 87324 / 87484 Kbytes
    Total Time:           0.56 seconds
    Total CPU Usage:      0.57 seconds
    No supervisor thread has been running
    
    wallclock  util%  max-rss
       103969  13.21      152
       101175  12.48
       101155  12.48
       104097  12.51
       105242  12.51
        44225  12.51        8
    --------- ------ --------
       559863  12.63      160
    
    Legend:
    wallclock  Number of microseconds elapsed
        util%  Percentage of CPU utilization (0..100%)
      max-rss  Maximum resident set size (in Kbytes)

    And many more options are available here, such as getting the output in .csv format.

    The MAIN thing

    You can now modify the way MAIN parameters are handled by setting options in %*SUB-MAIN-OPTS. The default USAGE message is now available inside the MAIN as the $*USAGE dynamic variable, so you can change it if you want to.

    Embedding Perl 6

    Two new features make embedding Rakudo Perl 6 easier to handle:
    the &*EXIT dynamic variable now can be set to specify the action to be taken when exit() is called.

    Setting the environment variable RAKUDO_EXCEPTIONS_HANDLER to "JSON" will throw Exceptions in JSON, rather than text, e.g.:

    $ RAKUDO_EXCEPTIONS_HANDLER=JSON perl6 -e '42 = 666'
    {
      "X::Assignment::RO" : {
        "value" : 42,
        "message" : "Cannot modify an immutable Int (42)"
      }
    }

    Bottom of the Gift Bag

    While rummaging through the still quite full gift bag, Santa found the following smaller prezzies:

    Time to catch a Sleigh

    Santa would like to stay around to tell you more about what’s been added, but there simply is not enough time to do that. If you really want to keep up-to-date on new features, you should check out the Additions sections in the ChangeLog that is updated with each Rakudo compiler release.

    So, catch you again next year!

    Best wishes from

    🎅🏾

    Perl 6 Advent Calendar: Day 21 – Sudoku with Junctions and Sets

    Published by scimon on 2017-12-21T00:00:31

    There are a number of core elements in Perl6 that give you powerful tools to do things in a concise and powerful way. Two of these are Junctions and Sets which share a number of characteristics but are also wildly different. In order to demonstrate the power of these I’m going to look at how they can be used with a simple problem, Sudoku puzzles.

    Sudoku : A refresher

    So for those of you who don’t know a Sudoku puzzle is a 9 by 9 grid that comes supplied with some cells filled in with numbers between 1 and 9. The goal is to fill in all the cells with numbers between 1 and 9 so that no row, column or sub square has more than one of any of the numbers in it.

    There’s a few ways to represent a Sudoku puzzle, my personal favourite being a 9 by 9 nested array for example :

    my @game = [
        [4,0,0,0,0,0,0,0,0],
        [0,9,0,3,4,6,0,5,0],
        [5,8,0,0,9,0,0,0,6],
        [0,4,0,8,1,3,0,0,9],
        [0,0,0,5,0,4,0,0,0],
        [8,0,0,6,2,9,0,4,0],
        [3,0,0,0,5,0,0,6,2],
        [0,5,0,9,3,2,0,8,0],
        [0,0,0,0,0,0,0,0,1]
    ];
    

    In this situation the cells with no value assigned are given a 0, this way all the cells have an Integer value assigned to them. The main thing to bear in mind with this format is you need to reference cells using @game[$y][$x] rather than @game[$x][$y].

    Junctions : Quantum Logic Testing

    One of the simplest ways to use Junctions in Perl6 is in a logical test. The Junction can represent a selection of values you are wanting to test against. For example :

    if ( 5 < 1|10 < 2 ) { say "Spooky" } else { say "Boo" }
    Spooky

    So, not only does this demonstrate operator chaining (something that experienced programmers may already be looking confused about) but the any Junction ( 1|10 ) evaluates to True for both 5 < 10 and 1 < 2. In this way Junctions can be extremely powerful already, it’s when you assign a variable container to them that it gets really interesting.

    One of the tests we’d like to be able to make on our Sudoku puzzle is to see if it’s full. By which I mean every cell has been assigned a value greater than 0. A full puzzle may not be completed correctly but there’s a guess in each cell. Another way of putting that would be that none of the cells has a value of 0. Thus we can define a Junction and store it in a scalar variable we can test it at any point to see if the puzzle is full.

    my $full-test = none( (^9 X ^9).map(-> ($x,$y) { 
        @game[$y][$x];
    } ) );
    say so $full-test == 0;
    False

    In this case the game has a number of 0’s still in it so seeing if $full-test equals 0 evaluates to False. Note that without the so to cast the result to a Boolean you’ll get a breakdown of the cells that are equal to 0 only if all of these are False will the Junction evaluate to True.

    Note also the use of the ^9 and X operators to generate two Ranges from 0 to 8 and then the cross product of these two lists of 9 characters to make a list of all the possible X,Y co-ordinates of the puzzle. It’s this kind of powerful simplicity that is one of the reasons I love Perl6. But I digress.

    The strength of this method is that once you’ve defined the Junction you don’t need to modify it. If you change the values stored in the Array the Junction will look at the new values instead (note this only holds true for updating individual cells, if you swap out a whole sub array with a new one you’ll break the Junction).

    So that’s a simple use of a Junction so store a multi-variable test you can reuse. But it gets more interesting when you realise that the values in a Junction can themselves be Junctions.

    Lets look at a more complex test, a puzzle is complete if for every row, column and square in the puzzle there is only one of each number. In order to make this test we’re going to need three helper functions.

    subset Index of Int where 0 <= * <= 8; 
    sub row( Index $y ) {
        return (^9).map( { ( $_, $y ) } ); 
    } 
    sub col( Index $x ) {
         return (^9).map( { ( $x, $_ ) } ); 
    } 
    multi sub square( Index $sq ) {
        my $x = $sq % 3 * 3;
        my $y = $sq div 3 * 3;
        return self.square( $x, $y );
    } 
    multi sub square( Index $x, Index $y ) {
         my $tx = $x div 3 * 3;
         my $ty = $y div 3 * 3;
         return ( (0,1,2) X (0,1,2) ).map( -> ( $dx, $dy ) { 
            ( $tx + $dx, $ty + $dy ) 
        } );
    }

    So here we define an Index as a value between 0 and 8 and then define our sub‘s to return a List of List‘s with the sub lists being a pair of X and Y indices’s. Note that our square function can accept one or two positional arguments. In the single argument we define the sub squares with 0 being in the top left then going left to right with 8 being the bottom right. The two argument version gives use the list of cells in the square for a given cell (including itself).

    So with these in place we can define our one() lists for each row, column and square. Once we have them we can them put them into an all() junction.

    my $complete-all = all(
         (^9).map(
            {
                |(
                    one( row( $_ ).map( -> ( $x, $y ) { 
                        @game[$y][$x] 
                    } ) ),
                    one( col( $_ ).map( -> ( $x, $y ) { 
                        @game[$y][$x] 
                    } ) ),
                    one( square( $_ ).map( -> ( $x, $y ) { 
                        @game[$y][$x] 
                    } ) )
                )
            }
        )
    );

    Once we have that testing to see if the puzzle is complete is quite simple.

    say [&&] (1..9).map( so $complete-all == * );
    False

    Here we test each possible cell value of 1 through 9 against the Junction, in each case this will be True if all the one() Junctions contains only one of the value. Then we use the [] reduction meta-operator to chain these results to give a final True / False value (True if all the results are True and False otherwise). Again this test can be reused as you add values to the cells and will only return True when the puzzle has been completed and is correct.

    Once again we’ve got a complex test boiled down to a single line of code. Our $complete-all variable needs to be defined once and is then valid for the rest of the session.

    This sort of nested junction tests can reach many levels, a final example is if we want to test if a current puzzle is valid. By which I mean it’s not complete but it doesn’t have any duplicate numbers in and row, column or square. Once again we can make a Junction for this, for each row, column or square it’s valid if one or none of the cells is set to each of the possible values.  Thus our creation of the Junction is similar to the $complete-all one.

    $valid-all = all(
        (^9).map(
            {
                |(
                    one( 
                        none( row( $_ ).map( -> ( $x, $y ) {
                            @game[$y][$x]
                        } ) ),
                        one( row( $_ ).map( -> ( $x, $y ) {
                            @game[$y][$x]
                        } ) ) 
                    ), 
                    one( 
                        none( col( $_ ).map( -> ( $x, $y ) {
                            @game[$y][$x] 
                        } ) ),
                        one( col( $_ ).map( -> ( $x, $y ) { 
                            @game[$y][$x]
                        } ) ) 
                    ),
                    one( 
                        none( square( $_ ).map( -> ( $x, $y ) {
                            @game[$y][$x]
                        } ) ),
                        one( square( $_ ).map( -> ( $x, $y ) {
                            @game[$y][$x]
                        } ) ) 
                    )
                )
            }
        )
    );

    The test for validity is basically the same as the test for completeness.

    say [&&] (1..9).map( so $valid-all == * );
    True

    Except in this case our puzzle is valid and so we get a True result.

    Sets : Collections of Objects

    Whilst the Junctions are useful to test values they aren’t as useful if we want to try solving the puzzle. But Perl6 has another type of collection that can come in very handy. Sets, (and their related types Bags and Mixes) let you collect items and then apply mathematical set operations to them to find how different Sets interact with each other.

    As an example we’ll define a possible function  that returns the values that are possible for a given cell. If the cell has a value set we will return the empty list.

    sub possible( Index $x, Index $y, @game ) {
        return () if @game[$y][$x] > 0;
    
        ( 
            (1..9) 
                (-)
            set(
                ( row($y).map( -> ( $x, $y ) { 
                    @game[$y][$x] 
                } ).grep( * > 0 ) ),
                ( col($x).map( -> ( $x, $y ) { 
                    @game[$y][$x] 
                } ).grep( * > 0 ) ),
                ( square($x,$y).map( -> ( $x, $y ) { 
                    @game[$y][$x] 
                } ).grep( * > 0 ) )
            )
        ).keys.sort;
     }

    Here we find the different between the numbers 1 through 9 and the Set made up of the values of the row, column and square the given cell is in. We ignore cells with a 0 value using grep. As Sets store their details as unordered key / value pairs we get the keys and then sort them for consistency. Note that here we’re using the ascii (-) version of the operator, we could also use the Unicode version instead.

    We could define the set as the union of each of the results from row, col and square and the result would be the same. Also we’re using the two argument version of square in this case.

    It should be noted that this is the simplest definition of possible values, there’s no additional logic going on but even this simple result lets us do the simplest of solving algorithms. If this case we loop around every cell in the grid and if it’s got 1 possible value we can set the value to that. In this case we’ll loop round, get a list of cells to set, then loop through the list and set the values. If the list of ones to set is empty or the puzzle is complete then we stop.

    my @updates;
    repeat {
        @updates = (^9 X ^9).map( -> ($x,$y) { 
            ($x,$y) => possible($x,$y,@game) 
        } ).grep( *.value.elems == 1 );
        for @updates -> $pair { 
            my ( $x, $y ) = $pair.key; 
            @game[$y][$x] = $pair.value[0];
        }
    } while ( @updates.elems > 0 && 
              ! [&&] (1..9).map( so $complete-all == * ) );

    So we make a list of Pairs where the key is the x,y coordinates and the value is the possible values. Then we remove all those that don’t have one value. This is continued until there are no cells found with a single possible value or the puzzle is complete.

    Another way of finding solutions is to get values that only appear in one set of possibilities in a given, row, column or square. For example if we have the following possibilities:

    (1,2,3),(2,3,4),(),(),(4,5),(),(),(2,3,4),()

    1 and 5 only appear in the row once each. We can make use of the symmetric set difference operator and operator chaining to get this.

    say (1,2,3) (^) (2,3,4) (^) () (^) () (^) (4,5) (^) () (^) () (^) (2,3,4) (^) ()
    set(1 5)

    Of course in that case we can use the reduction meta-operator on the list instead.

    say [(^)] (1,2,3),(2,3,4),(),(),(4,5),(),(),(2,3,4),()
    set(1 5)

    So in that case the algorithm is simple (in this case I’ll just cover rows, the column and square code is basically the same).

    my @updates;
    for ^9 -> $idx {
        my $only = [(^)] row($idx).map( -> ( $x,$y ) { 
            possible($x,$y,@game) 
        } );
        for $only.keys -> $val {
            for row($idx) -> ($x,$y) {
                if $val (elem) possible($x,$y,@game) {
                    @updates.push( ($x,$y) => $val );
                }
            }
        }
    }

    We then can loop through the updates array similar to above. Combining these two algorithms can solve a large number of Sudoku puzzle by themselves and simplify others.

    Note we have to make two passes, firstly we get the numbers we’re looking for and then we have to look through each row and find where the number appears. For this we use the (elem) operator. Sets can also be referenced using Associative references for example:

    say set(1,5){1}
    True

    A note on Objects

    So for all the examples so far I’ve used basic integers. But there’s nothing stopping you using Objects in your Junctions and Sets. There are a few things to bear in mind though, Sets use the === identity operator for their tests. Most objects will fail an identity check unless you have cloned them or have defined the WHICH method in a way that will allow them to be compared.

    For the Sudoku puzzle you may want to create a CellValue class that stores whether the number was one of the initial values in the puzzle. If you do this though you’ll need to override WHICH and make it return the Integer value of the Cell. As long as you are fine with an identity check being technically invalid in this case (two different CellValues may have the same value but the won’t be the same object) then you can put them in Sets.

    I hope you’ve found this interesting, Junctions and Sets are two of the many different parts of Perl6 that give you power to do complex tasks simply. If you’re interested in the code here there’s a Object based version available to use you can install with :

    zef install Game::Sudoku

    Strangely Consistent: Has it been three years?

    Published by Carl Mäsak

    007, the toy language, is turning three today. Whoa.

    On its one-year anniversary, I wrote a blog post to chronicle it. It seriously doesn't feel like two years since I wrote that post.

    On and off, in between long stretches of just being a parent, I come back to 007 and work intensely on it. I can't remember ever keeping a side project alive for three years before. (Later note: Referring to the language here, not my son.) So there is that.

    So in a weird way, even though the language is not as far along as I would expect it to be after three years, I'm also positively surprised that it still exists and is active after three years!

    In the previous blog post, I proudly announce that "We're gearing up to an (internal) v1.0.0 release". Well, we're still gearing up for v1.0.0, and we are closer to it. The details are in the roadmap, which has become much more detailed since then.

    Noteworthy things that happened in these past two years:

    Things that I'm looking forward to right now:

    I tried to write those in increasing order of difficulty.

    All in all, I'm quite eager to one day burst into #perl6 or #perl6-dev and actually showcase examples where macros quite clearly do useful, non-trivial things. 007 is and has always been about producing such examples, and making them run in a real (if toy) environment.

    And while we're not quite over that hump yet, we're perceptibly closer than we were two years ago.

    Belated addendum: Thanks and hugs to sergot++, to vendethiel++, to raiph++ and eritain++, for sharing the journey with me so far.

    rakudo.org: Rakudo Star Release 2017.10

    Published on 2017-11-09T00:00:00

    gfldex: Racing Rakudo

    Published by gfldex on 2017-11-05T17:39:33

    In many racing sports telemetry plays a big role in getting faster.  Thanks to a torrent of commits by lizmat you can use telemetry now too!

    perl6 -e 'use Telemetry; snapper(½); my @a = (‚aaaa‘..‚zzzz‘).pick(1000); say @a.sort.[*-1 / 2];'
    zyzl
    Telemetry Report of Process #30304 (2017-11-05T17:24:38Z)
    No supervisor thread has been running
    Number of Snapshots: 31
    Initial Size:        93684 Kbytes
    Total Time:          14.74 seconds
    Total CPU Usage:     15.08 seconds
    
    wallclock  util%  max-rss  gw      gtc  tw      ttc  aw      atc
       500951  53.81     8424
       500557  51.92     9240
       548677  52.15    12376
       506068  52.51      196
       500380  51.94     8976
       506552  51.74     9240
       500517  52.45     9240
       500482  52.33     9504
       506813  51.67     6864
       502634  51.63
       500520  51.78     6072
       500539  52.13     7128
       503437  52.29     7920
       500419  52.45     8976
       500544  51.89     8712
       500550  49.92     6864
       602948  49.71     8712
       500548  50.33
       500545  49.92      320
       500518  49.92
       500530  49.92
       500529  49.91
       500507  49.92
       506886  50.07
       500510  49.93     1848
       500488  49.93
       500511  49.93
       508389  49.94
       508510  51.27      264
        27636  58.33
    --------- ------ -------- --- -------- --- -------- --- --------
     14738710  51.16   130876
    
    Legend:
    wallclock  Number of microseconds elapsed
        util%  Percentage of CPU utilization (0..100%)
      max-rss  Maximum resident set size (in Kbytes)
           gw  The number of general worker threads
          gtc  The number of tasks completed in general worker threads
           tw  The number of timer threads
          ttc  The number of tasks completed in timer threads
           aw  The number of affinity threads
          atc  The number of tasks completed in affinity threads
    

    The snapper function takes an interval at which data is collected. On termination of the program the table above is shown.

    The module comes with plenty of subs to collect the same data at hand and file your own report. What may be sensible in long running processes. Or you call the reporter sub by hand every now and then.

    use Telemetry;
    
    react {
        snapper;
        whenever Supply.interval(60) {
            say report;
        }
    }

    If the terminal wont cut it you can use http to fetch telemetry data.

    Documentation isn’t finished nor is the module. So stay tuning for more data.

    rakudo.org: Main Development Branch Renamed from "nom" to "master"

    Published on 2017-10-27T00:00:00

    gfldex: There Is More Than One Way At The Same Time

    Published by gfldex on 2017-10-22T21:21:16

    The Perl 6 Rosattacode section for parallel calculations is terribly outdated and missing all the goodies that where added or fixed in the last few weeks. With this post I would like to propose an updated version for Rosettacode. If you believe that I missed something feel free to comment below. Please keep in mind that Rosettacode is for showing off, not for being comprehensive.

    use v6.d.PREVIEW;

     

    Perl 6 provides parallel execution of code via threads. There are low level custructs that start a thread or safely pause execution.

    my $t1 = Thread.start({ say [+] 1..10_000_000 });
    my $t2 = Thread.start({ say [*] 1..10_000 });
    $t1.finish;
    $t2.finish;
    
    my $l = Lock.new;
    $l.lock;
    $t1 = Thread.start: { $l.lock; say 'got the lock'; $l.unlock };
    sleep 2; $l.unlock;
    
    $t1.finish;
    

    When processing lists, one can use a highlevel Iterator created by the methods hyper and race. The latter may return values out of order. Those Iterators will distribute the elements of the list to worker threads that are in turn assigned to OS level threads by Rakudos ThreadPoolScheduler. The whole construct will block until the last element is processed.

    my @values = 1..100;
    
    sub postfix:<!> (Int $n) { [*] 1..$n }
    
    say [+] @values.hyper.map( -> $i { print '.' if $i %% 100; $i!.chars });
    

    For for-lovers there are the race for and hyper for keyword for distributing work over threads in the same way as their respective methods forms.

    race for 1..100 {
        say .Str; # There be out of order dragons!
    }
    
    my @a = do hyper for 1..100 {
       .Int! # Here be thread dragons!
    }
    
    say [+] @a;

    Perl 6 sports constructs that follow the reactive programming model. One can spin up many worker threads and use threadsafe Channels or Supplys to move values from one thread to another. A react-block can combine those streams of values, process them and react to conditions like cleaning up after a worker thread is done producing values or dealing with errors. The latter is done by bottling up Exception-objects into Failure-objects that keep track of where the error first occured and where it was used instead of a proper value.

    my \pipe = Supplier::Preserving.new;
    
    start {
        for $*HOME {
            pipe.emit: .IO if .f & .ends-with('.txt');
    
            say „Looking in ⟨{.Str}⟩ for files that end in ".txt"“ if .IO.d;
            .IO.dir()».&?BLOCK when .IO.d;
    
            CATCH {
                default {
                    note .^name, ': ', .Str;
                    pipe.emit: Failure.new(.item);
                }
            }
        }
        pipe.done;
    }
    
    react {
        whenever pipe.Supply {
            say „Checking ⟨{.Str}⟩ for "Rosetta".“;
            say „I found Rosetta in ⟨{.Str}⟩“ if try .open.slurp.contains('Rosetta');
            LAST {
                say ‚Done looking for files.‘;
                done;
            }
            CATCH {
                default {
                    note .^name, ': ', .Str;
                }
            }
        }
        whenever Promise.in(60*10) {
            say „I gave up to find Rosetta after 10 minutes.“;
            pipe.done;
            done;
        }
    }
    

    Many build-in objects will return a Supply or a Promise. The latter will return a single value or just convey an event like a timeout. In the example above we used a Promise in that fashion. Below we shell out to find and process its output line by line. This could be used in a react block if there are many different types of events to process. Here we just tap into a stream of values and process them one by one. Since we don’t got a react block to provide a blocking event loop, we wait for find to finish with await and process it’s exitcode. Anything inside the block given to .tap will run in its own thread.

    my $find = Proc::Async.new('find', $*HOME, '-iname', '*.txt');
    $find.stdout.lines.tap: {
        say „Looking for "Rosetta" in ⟨$_⟩“;
        say „Found "Rosetta" in ⟨$_⟩“ if try .open.slurp.contains('Rosetta');
    };
    
    await $find.start.then: {
        say „find finished with exitcode: “, .result.exitcode;
    };
    

    Having operators process values in parallel via threads or vector units is yet to be done. Both hyper operators and Junctions are candidates for autothreading. If you use them today please keep in mind side effects may provide foot guns in the future.

    gfldex: It’s Classes All The Way Down

    Published by gfldex on 2017-10-08T17:23:05

    While building a cache for a web api that spits out JSON I found myself walking over the same data twice to fix a lack of proper typing. The JSON knows only about strings even though most of the fields are integers and timestamps. I’m fixing the types after parsing the JSON with JSON::Fast by coercively .map-ing .

    @stations.=hyper.map: { # Here be heisendragons!
        .<lastchangetime> = .<lastchangetime>
            ?? DateTime.new(.<lastchangetime>.subst(' ', 'T') ~ 'Z', :formatter(&ISO8601))
            !! DateTime;
        .<clickcount> = .<clickcount>.Int;
        .<lastcheckok> = .<lastcheckok>.Int.Bool;
    
        (note "$_/$stations-count processed" if $_ %% 1000) with $++;
    
        .Hash
    };
    

    The hyper helps a lot to speed things up but will put a lot of stress on the CPU cache. There must be a better way to do that.

    Then lizmat showed where Rakudo shows its guts.

    m: grammar A { token a { }; rule a { } }
    OUTPUT: «5===SORRY!5=== Error while compiling <tmp>␤Package 'A' already has a regex 'a' 
    (did you mean to declare a multi-method?)␤
    

    Tokens are regex or maybe methods. But if tokens are methods then grammars must be classes. And that allows us to subclass a grammar.

    grammar WWW::Radiobrowser::JSON is JSON {
        token TOP {\s* <top-array> \s* }
        rule top-array      { '[' ~ ']' <station-list> }
        rule station-list   { <station> * % ',' }
        rule station        { '{' ~ '}' <attribute-list> }
        rule attribute-list { <attribute> * % ',' }
    
        token year { \d+ } token month { \d ** 2 } token day { \d ** 2 } token hour { \d ** 2 } token minute { \d ** 2 } token second { \d ** 2}
        token date { <year> '-' <month> '-' <day> ' ' <hour> ':' <minute> ':' <second> }
    
        token bool { <value:true> || <value:false> }
    
        token empty-string { '""' }
    
        token number { <value:number> }
    
        proto token attribute { * }
        token attribute:sym<clickcount> { '"clickcount"' \s* ':' \s* '"' <number> '"' }
        token attribute:sym<lastchangetime> { '"lastchangetime"' \s* ':' \s* '"' <date> '"' }
        token attribute:sym<lastcheckok> { '"lastcheckok"' \s* ':' \s* '"' <bool> '"' }
    }
    

    Here we overload some tokens and forward calls to tokens that got a different name in the parent grammar. The action class follows suit.

    class WWW::Radiobrowser::JSON::Actions is JSON::Actions {
        method TOP($/) {
            make $<top-array>.made;
        }
        method top-array($/) {
            make $<station-list>.made.item;
        }
        method station-list($/) {
            make $<station>.hyper.map(*.made).flat; # Here be heisendragons!
        }
        method station($/) {
            make $<attribute-list>.made.hash.item;
        }
        method attribute-list($/) {
            make $<attribute>».made.flat;
        }
        method date($_) { .make: DateTime.new(.<year>.Int, .<month>.Int, .<day>.Int, .<hour>.Int, .<minute>.Int, .<second>.Num) }
        method bool($_) { .make: .<value>.made ?? Bool::True !! Bool::False }
        method empty-string($_) { .make: Str }
    
        method attribute:sym<clickcount>($/) { make 'clickcount' => $/<number>.Int; }
        method attribute:sym<lastchangetime>($/) { make 'lastchangetime' => $/<date>.made; }
        method attribute:sym<lastcheckok>($/) { make 'lastcheckok' => $/<bool>.made; }
    }
    

    In case you wonder how to call a method with such a funky name, use the quoting version of postfix:<.>.

    class C { method m:sym<s>{} }
    C.new.'m:sym<s>'()
    

    I truncated the examples above. The full source can be found here. The .hyper-Version is still quite a bit faster but also heisenbuggy. In fact .hyper may not work at all when executed to fast after a program starts or when used in a recursive Routine. This is mostly due to the grammer being one of the oldest parts of Rakudo with the least amount of work to make it fast. That is a solvable problem. I’m looking forward to Grammar All The Things.

    If you got grammars please don’t hide them. Somebody might need them to be classy.

     

    samcv: Grant Final Report

    Published on 2017-09-25T07:00:00

    This contains the work since the last report as well as my final report.

    Table of Contents

    Work Since the Last Report

    Merged in Unicode Collation Algorithm

    I merged the Unicode Collation Algorithm branch into MoarVM. Now that the sort is stable, the coll, unicmp and .collate operators in Rakudo are no longer experimental so use experimental :collation no longer is needed to use them.

    The $*COLLATION dynamic variable is still hidden under experimental, since it is possible design changes could be made to them.

    Prepend

    In some of my other posts I talked about the difficulties of getting Prepend codepoints working properly. To do this I had changed how we store synthetics so as not to assume that the first codepoint of a synthetic is always the base character. This month I merged in change in synthetic representation and implemented the features which were now possible with the new representation.

    The feature was to detect which character is the base character and store its index in the synthetic. Most combiners, such as diacritics come after the base character and are Extend codepoints: a + ◌́. Prepend has the reverse functionality and comes before: ؀◌ + 9 (Arabic number sign + number).

    This required many assumptions our code rightfully made before Unicode 9.0 to be abandoned. When a synthetic is created, we now check to see if the first codepoint is a Prepend codepoint. If so, we keep checking until we find a codepoint that is not a Prepend. In most cases, the base character is the codepoint following the last Prepend mark.

    In degenerate cases there is no base character, which could be a grapheme composed of all Prepend’s or only Prepend’s and Extend’s. In these degenerate cases we set the first codepoint as the base character.

    Once I had that done, I was able to fix some of our ops which did not work correctly if there were Prepend characters. This included fixing our case changing op so it would now work on graphemes with Prepend marks. Since the case change ops apply the case change to the base codepoint, it is necessary for us to have the correct base character. Similarly, ordbaseat which gets the base codepoint also needed to be fixed. This allowed ignoremark to now work for graphemes with Prepend marks.

    Documentation

    I wrote documentation on our Unicode Collation Algorithm, which explains to the reader why the UCA solves, with examples of different single to multiple or multiple to single mappings of codepoints. It goes in a fair amount of detail on how it was implemented.

    UTF8-C8

    Bugs with Encoding into UTF8-C8

    Since MoarVM normalizes all input text, our way of dealing with not normalizing, is important to people who want their strings to be unchanged unchanged. Previously there was a bug where if something was a valid UTF8 storable value, such as a Surrogate or a value higher than 0x10FFFF, it would create a Str type with that value, even though it was not valid Unicode. It would then throw when this value was attempted to be used (since the Str type shouldn’t hold values higher than 0x10FFFF or Surrogates). As this is the only way we have of dealing with text unaltered, this seemed like a serious issue that would prevent UTF8-C8 from being usable in a production environment attempting to encode arbitrary data into UTF8-C8. [f112fbcf]

    Bugs While Working with UTF8-C8 Strings

    Another issue I fixed was that under concatenation, text replacement or renormalization, the UTF8-C8 codepoints would be "flattened". They would lose their special properties and instead start acting like any other set of Unicode codepoints (although unusual since it contains a private use character and a hex code of the stored value). I changed our codepoint iterator so that optionally you can choose to pass back UTF8-C8 Synthetics unchanged. We use Synthetics to store both UTF8-C8 values as well as storing graphemes which contain multiple codepoints. When iterating by codepoint on an already existing arbitrary string, we want to retain the UTF8-C8 codepoints and make sure they are not changed during the renormalization process. This has been fixed, and UTF8-C8 strings are now drastically more reliable, and hopefully, much more production ready. [2f71945d]

    Grapheme Caching and Move To

    The function which moves a grapheme iterator forward a specified number of graphemes now works even if we aren’t starting from the very start of the string. In this function we have a first loop which locates the correct strand, and had a second loop which would find the correct grapheme inside that strand. I refactored the grapheme locating code and was able to remove the loop.

    In the grapheme caching implementation we can save a lot of work by not creating a new iterator for every grapheme access. Not only that, I also sped it the move_to function about 30%. While the cached iterator reduces access to this function for the functions I added it to, there are still many which may seek for each grapheme requested, this will speed that up.

    Other MoarVM Changes

    I setup automated Appveyor builds for MoarVM so we get automated builds on Windows (Travis CI only builds MacOS and Linux builds).

    I fixed a segfault that occurred when compiling nqp on Alpine Linux which uses musl as its libc. I ended up reducing the depth of recursion in the optimize_bb() function when compiling nqp from 99 to 29 (3x reduction). In the Rakudo build, we have a 5x reduction in the depth of recursion.

    Final Report

    As I’ve already said many things in my previous grant reports (1, 2, 3, 4) I will iterate on some of the big things I did do, which is not exhaustive. For full details of all the changes please see my other grant reports as well as a partial list of bonus changes I made in MoarVM during the grant at the bottom of the page.

    The only thing not completed was implementing a whole new UCD backend. While I planned on doing this, I ended up choosing not to do so. I realized that it would not have been the best use of my time on the grant, as there were many more user noticeable changes I could do. Despite this, I did achieve the goals that the rewrite was intended to solve; namely making property values distinct for each property and making the UCD database generation more reproducible. While it is not exactly the same on different runs, the only thing that changes is the internal property codes which does not affect anything adversely. It is fully functional every time instead of database regeneration breaking our tests most of the time. Once the database was stable, I was then able to update our database to Unicode 10. Without my improvements regarding reproducibility and property values becoming distinct for each property, updating to Unicode 10 would have not been possible. In addition all Hangul (Korean) characters now have names in the Unicode database.

    A big thing I wanted to implement was the Unicode Collation Algorithm, which ended up being a total success. I was able to still retain the ability to choose which collation levels the user wanted to sort with as well as reverse the sort order of individual collation levels.

    Yet I did not only implement one algorithm, I also implemented the Knuth-Morris-Prat string search algorithm which can take advantage of repeated characters in the needle (can be multiple times faster if you have sections repeating). The Knuth-Morris-Pratt algorithm was adjusted to use either the new cached grapheme iterator or the simple lookup depending on if it was a flat or strand haystack as well. Indexing a strand based string with a one grapheme long needle was sped up by 9x by making a special case for this.

    Practically all string ops were sped up, often by multiple times due to getting MVM_string_get_grapheme_at_nocheck inlined. In addition to this, I changed the way we access strings in many of our most used string ops, intelligently using either grapheme iterators, cached grapheme iterators or direct access depending on circumstances. With the MVM_string_get_grapheme_at_nocheck inlined, the time to accessing graphemes with this function was sped up between 1.5x for strands and up to 2x for flat strings. Ops we use a lot, like the op that backs eq and nqp::eqat was given special casing for Strand ←→ Strand, Flat ←→ Flat and Strand ←→ Flat (which also covers Flat ←→ Strand as well). This special casing spec up eq by 1.7x when one is a strand and one is flat, and 2.5x when both strings are flat. Applying similar optimizations to index made a 2x speedup when haystack is flat and 1.5x speedup when haystack is a strand (on top of the previous improvements due to the Knuth-Morris-Pratt algorithm)

    I fixed a longstanding bug in NQP which caused 'ignoremark+ignorecase' operations to be totally broken. I fixed this by adding more MoarVM ops and refactoring the code to have many less branches. In MoarVM we now use a centralized function to do each variation of with/without ignorecase and ignore mark which is also fully compatible with foldcase operations as well as igoremark.

    Doing the ignoremark/ignorecase indexing work sped them up by multiple times, but then in addition to that, it became 2x faster when the haystack was made up of 10 strands by implementing a cached grapheme iterator.

    I implemented full Unicode 9.0 support not just in our grapheme segmentation, but also in our other ops, refactoring how we store synthetic codepoints to allow us to have the 'base' codepoint be a codepoint other than the 1st in the synthetic to support Prepend codepoints.

    Our concatenation was improved so as to make full renormalization of both input strings no longer needed in almost all cases. The x repeat operator was fixed so it always creates normalized strings. Previously it could create unnormalized strings instead, causing issues when it was used.

    I believe I have more than accomplished what I set out to do in this grant. I made tons of user facing changes: to speed, Unicode normalization support, full Unicode 9.0 support. I added awesome collation features and fixed all the major issues with decoding and working with UTF8-C8 representations. I have listed an incomplete list of bonus deliverables below the deliverables which were part of this project.

    Deliverables

    • I documented MoarVM’s string representation, with lots of good information for future developers as well as interested users.

    • Hangul syllables now have Unicode names in our database, with a test added in roast.

    • I implemented the Unicode Collation Algorithm [866623d9]

      • Tests have been added in roast for the UCA and the unicmp op

      • I wrote documentation on our Unicode Collation Algorithm implementation

      • Regarding language specific sort. This would involve us using data from the Unicode CLDR. Once we have this data available from MoarVM, it simply requires a conditional to override DUCET and check a different set of data before checking the DUCET data. This information is in our documentation for collation.

    • Text normalization

      • Speed of normalization was improved

      • Full Unicode 9.0 support for text segmentation and normalization was added

    • While I did not fully rewrite the database, I did solve the needed issues:

      • Property values are now unique for each property

      • Running the generation script creates a functional database every time it is run, rather than only some of the time.

      • I added Unicode Collation data to our database, generated from a Perl 6 script, which happened to be the only property required to complete my deliverables

    Bonus Deliverables

    Here is a somewhat complete list of bonus deliverables:

    • Updated our database to Unicode 10. This was only possible once I had fixed the problems with the database generation, and made property values unque.

    • Implemented Knuth-Morris-Pratt string search

    • Set up Appveyor builds. Appveyor builds and tests MoarVM on Windows, similar to Travis CI.

    • Fixed ignoremark+ignorecase regex when used together as well as huge speed increases.

    UTF8-C8/UTF-8

    • Fix UTF8-C8 encoding so it can encode values > 0x10FFFF as well as surrogates

    • Fix UTF8-C8 strings so they do not get corrupted and flattened when string operations are performed on them.

    • MVM_string_utf8_decodestream: free the buffer on malformed UTF-8 [a22f98db]

    String Ops

    • Have MVM_string_codes iterate the string with codepoint iterator [ed84a632]

    • Make eqat 1.7x-2.5x faster [3e823659]

    • Speed up index 9x when Haystack is strand, needle is 1 long [0b364cb8]

    • Implement the Knuth-Morris-Pratt string search algorithm [6915d80e]

    • Add indexim_s op and improve/fix bugs in eqatim_s [127fa2ce]

    • Fix a bug in index/eqat(im) and in ord_getbasechar causing us to not decompose the base character when the grapheme was a synthetic [712cff33]

    • Fix MVM_string_compare to support deterministic comparing of synthetics [abc38137]

    • Added a codes op which gets the number of codepoints in a string rather than the number of graphemes. Rakudo is now multipe times faster doing the .codes op now. Before it would request an array of all the codepoints and then get number of elements, which was much slower.

    Fix string ops with Prepend characters

    • Rework MVMNFGSynthetic to not store base separately [3bd371f1]

    • Fix case change when base cp isn’t the first cp in synthetic [49b90b99]

    • For degenerate Synth’s with Prepend and Extend set base cp to 1st cp [db3102c4]

    • Fix ignoremark with Prepend characters and ordbaseat op [f8a639e2]

    Memory/GC/Build Fixes

    • Fix segfault when compiling nqp with musl as libc [5528083d]

    • Avoid recursion in optimize_bb() when only 1 child node [6d844e00]

    • Fix various memory access/garbage collection issues in some string ops that were showing up when running in Valgrind or using Address Sanitizer

    Grapheme Iteration

    • Ensure we can move forward in a grapheme iterator even if we aren’t starting at the very beginning of a string.

    • Use grapheme iterator cached for ignorecase/ignoremark index ops [b2770e27]

    • Optimize MVM_string_gi_move_to. Optimize the loop which finds the correct location within a strand so that it isn’t a loop and is just conditionals.[c2fc14dd]

    • Use MVMGraphemeIter_cached for strands in KMP index [ce76c994]

    • Allow MVM_string_get_grapheme_at_nocheck to be inlined

    • Refactor code into iterate_gi_into_string() to reduce code duplication [1e92fc96]

    Tests Added to Roast

    • Add tests for testing collation. Tests for the unicmp operator [5568a0d63]

    • Test that Hangul syllables return the correct Unicode name [6a4bc5450]

    • Add tests for case changes when we have Prepend codepoints [00554ccbd]

    • Add tests for x operator to ensure normalization retained [1e4fd2148] [59909ca9a]

    • Add a large number of string comparison tests [51c4ac08b]

      • Add tests to make sure synthetics compare properly with cmp [649d9dc50]

    • Improve ignoremark tests to cover many different cases [810e218c8]

      • Add ignoremark tests to cover JSON::Tiny regression + other issue [c185acc57]

    • Add generated tests (from UCD data) and manually created ones to ensure strings concatenation is stable, when the concatenated string would change the normalization. [2e1f7d92a][9f304b070] [64e385faf][0976d07b9][59909ca9a][2e1f7d92a] [88635564e] [a6bbc73cf] [a363e3ff1]

    • Add test for MoarVM Issue #566 .uniprop overflow [9227bc3d8]

    • Add tests to cover RT #128875 [0a80d0d2e]

    • Make new version of GraphemeBreakTest.t to better test grapheme segmentation [54c96043c]

    NQP Work

    Below is a listing of some of the commits I made to NQP. This included adding the ops I created over the course of the grant: eqatim, indexim, indexicim, eqaticim, and codes (gets the number of codepoints in a string rather than graphemes).

    The testing in NQP was inadequate for our string ops, so I added hundreds of tests for practically all of the string ops, so we could properly test the different variations of index* and eqat*.

    NQP Documentation

    • Add docs for a few variations of index/eqat [589a3dd5c] Bring the unicmp_s op docs up to date [091625799]

    • Document hasuniprop moar op [650840d74]

    NQP Tests

    • Add more index* tests to test empty string paths [8742805cb]

    • run indexicim through all of the indexic tests [26adef6be]

    • Add tests for RT #128875, ignorecase+ignoremark false positives [b96a0afe7]

    • Add tests for nqp::eqatim op on MoarVM [6fac0036e]

    Other Work

    • Added script to find undocumented NQP ops [0ead16794]

    • Added nqp::codes to QASTOperationsMAST.nqp [59421ffe1]

    • Update QASTRegexCompilerMAST to use new indexicim and eqaticim ops [18e40936a]

    • Added eqatim and indexim ops. Fix a bug when using ignoremark [9b94aae27]

    • Added nqp::hasuniprop op to QASTOperationsMAST.nqp [d03c4023a]

    p6steve: Clone Wars

    Published by p6steve on 2017-09-20T18:52:04

    Apologies to those that have OO steeped in their blood. I am a wary traveller in OO space,  maybe I am an technician, not an architect at heart. So for me, no sweeping frameworks unless and until they are needed. And, frankly, one can go a long way on procedural code with subroutines to gather repetitive code sequences.

    (And don’t get me started on functional programming…)

    Some time ago, I was tasked to write a LIMS in old perl. Physical ‘aliquots’ with injections of various liquids would be combined and recombined by bio-machines. This led to a dawning realization that these aliquot objects could be modelled in an object style with parent / child relationships. After a few weeks, I proudly delivered my lowly attempt at ‘Mu’ for this (and only this) problem. Kudos to the P6 team – after a couple of weeks in here, it’s just sensational the level of OO power that the real Mu delivers:

    Screenshot 2017-09-20 19.32.21

    Now, hard at work, on the perl6 version of Physics::Unit, I am wondering how to put the OO theory into productive practice. One of my aims was to find a medium sized (not core tools) problem that (i) I know something about and (ii) would be a good-sized problem to wrangle.

    So I am enjoying the chance to design some classes and some interfaces that will make this all hang together. But – as an explorer, it has become clear that I only have three options. The problem runs like this:

    Initially I had some success with object types ::T – but these only let you read the type and  duplicate if needed for a new left hand side container. Then I tried the built in (shallow) clone method. But…

    Ultimately, thanks to rosettacode.org, I worked out that $x.perl.EVAL with some ~~ s/// substitions on the way would do the trick!

    Phew. Please comment below if you have a better way to share – or would like to point out the risks of this technique…


    p6steve: perl6 Atomic Fission

    Published by p6steve on 2017-09-03T18:46:48

    I have been listening to the reaction on the web to the incorporation of an emoji as a unicode symbol in perl6 rakudo. Here’s a flavour…

    (https://p6weekly.wordpress.com/2017/08/21/2017-34-going-atomic/ )

    The rationale for the use of unicode symbols is as follows:

    BTW- ASCII versions are known as Texas versions since they are always bigger

    Certainly this has caused some consternation – ranging from how can I type ⚛️ on my keyboard (hit CTRL-CMD-SPACE if you are on macOS ) to this will never be accepted for the coding standards of my company.

    On reflection, while it is understandable that programmers have a well established comfort zone of ASCII text and using English for keywords, I think that perl6 is leading the way on an irresistible path. Of the 6.5bn people on the planet, only a small fraction prefer to work in English – or even in Latin alphabets. Now, the pioneering work to embed unicode in a programming language will open the doors to all kinds of invention. What about:

    And this, in combination with perl6 Grammars, opens some interesting conceptual doors.

    ~p6steve