pl6anet

Perl 6 RSS Feeds

Steve Mynott (Freenode: stmuk) steve.mynott (at)gmail.com / 2016-12-09T21:19:10


6guts: Complex cocktail causes cunning crash

Published by jnthnwrthngtn on 2016-12-09T00:02:33

I did a number of things for Perl 6 yesterday. It was not, however, hard to decide which of them to write up for the blog. So, let’s dig in.

Horrible hiding heisenbugs

It all started when I was looking into this RT, reporting a segfault. It was filed a while ago, and I could not reproduce it. So, add a test and case closed? Well, not so fast. As I discussed last week, garbage collection happens when a thread fills up its nursery. Plenty of bugs only show up when the timing is just right (or is that just wrong?) What can influence when GC runs? How many allocations we’ve done. And what can influence that? Pretty much any change to the program being run, the compiler, or the environment. The two that most often have people tearing their hair out are:

While GC-related issues are not the only cause of SEGVs, in such a simple piece of code using common features it’s far and away the most likely cause. So, to give myself more confidence that the bug truly was gone, I adjusted the nursery size to be just 32KB instead of 4MB, which causes GC to run much more often. This, of course, is a huge slowdown, but it’s good for squeezing out bugs.

And…no bug! So, in goes the test. Simples!

In even better news, it was lunch time. Well, actually, that was only sort of good news. A few days ago I cooked a rather nice chicken and berry pulao. It come out pretty good, but cooking 6 portions worth of it when I’m home alone for the week wasn’t so smart. I don’t want to see chicken pulao for a couple of months now. Anyway, while I was devouring some of my pulao mountain, I set off a spectest run on the 32KB nursery stress build of MoarVM, just to see if it showed up anything.

Putrid pointers

A couple of failures did, in fact, show up, one of them in constant.t. This rang a bell. I was sure somebody had a in the last couple of weeks reported a crash in that test file, which had then vanished. I checked in with the person who I vaguely recalled mentioning it and…sure enough, it was that very test file. In their normal test runs, the bug had long since vanished. I figured, having now got a reproduction of it, I should probably hunt it down right away. Otherwise, we’d probably end up playing “where’s Wally” with it for another month or ten.

So, how did the failure look?

$ ./perl6-m -Ilib t/spec/S04-declarations/constant.rakudo.moar 
Segmentation fault (core dumped)

It actually segfaulted while compiling the test file. Sad! So, where?

$ ./perl6-gdb-m -Ilib t/spec/S04-declarations/constant.rakudo.moar 
[boring output omitted]
Program received signal SIGSEGV, Segmentation fault.
0x0000000000000000 in ?? ()

That looks…ungood. That final line is meant to be a code location, which means something decided to tell the CPU to go execute code living at the NULL address. At this point, things could go two ways: the JIT spat out something terrible, or a function pointer somewhere was NULL. But which?

(gdb) where
#0  0x0000000000000000 in ?? ()
#1  0x00007ffff78cacbc in MVM_coerce_smart_stringify (tc=0x6037c0, obj=0x605c10, res_reg=0x56624d8)
    at src/core/coerce.c:214
#2  0x00007ffff789dff4 in MVM_interp_run (tc=tc@entry=0x6037c0, initial_invoke=0x60ea80, 
    invoke_data=0x56624d8) at src/core/interp.c:827
#3  0x00007ffff7978b21 in MVM_vm_run_file (instance=0x603010, 
    filename=0x7fffffffe09f "/home/jnthn/dev/rakudo/perl6.moarvm") at src/moar.c:309
#4  0x000000000040108b in main (argc=9, argv=0x7fffffffdbc8) at src/main.c:192

Phew, it looks like the second case, given there’s no JIT entry stub on the stack. So, we followed a NULL function pointer. Really?

(gdb) frame 1
#1  0x00007ffff78cacbc in MVM_coerce_smart_stringify (tc=0x6037c0, obj=0x605c10, res_reg=0x56624d8)
at src/core/coerce.c:214
214     ss = REPR(obj)->get_storage_spec(tc, STABLE(obj));

Yes, really. Presumably, that get_storage_spec is bogus. (I did a p to confirm it.) So, how is obj looking?

(gdb) p *obj
$1 = {header = {sc_forward_u = {forwarder = 0x48000000000001, sc = {sc_idx = 1, idx = 4718592}, 
  st = 0x48000000000001}, owner = 6349760, flags = 0, size = 0}, st = 0x6d06c0}

Criminally corrupt; let me count the ways. For one, 6349760 looks like a very high thread ID for a program that’s only running a single thread (they are handed out sequentially). For two, 0 is not a valid object size. And for three, idx is just a nuts value too (even Rakudo’s CORE.setting isn’t made up of 4 million objects). So, where does this object live? Well, let’s try out last week’s handy object locator to figure out:

(gdb) p MVM_gc_debug_find_region(tc, obj)
In tospace of thread 1

Well. Hmpfh. That’s actually an OK place for an object to be. Of course, the GC spaces swap often enough at this nursery size that a pointer could fail to be updated, point into fromspace after one GC run, not be used until a later GC run, and then come to point into some random bit of tospace again. How to test this hypothesis? Well, instead of 32768 bytes of nursery, what if I make it…well, 40000 maybe?

Here we go again:

$ ./perl6-gdb-m -Ilib t/spec/S04-declarations/constant.rakudo.moar 
[trust me, this omitted stuff is boring]
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff78b00db in MVM_interp_run (tc=tc@entry=0x6037c0, initial_invoke=0x0, invoke_data=0x563a450)
    at src/core/interp.c:2855
2855                    if (obj && IS_CONCRETE(obj) && STABLE(obj)->container_spec)

Aha! A crash…somewhere else. But where is obj this time?

(gdb) p MVM_gc_debug_find_region(tc, obj)
In fromspace of thread 1

Hypothesis confirmed.

Dump diving

So…what now? Well, just turn on that wonder MVM_GC_DEBUG flag and the bug will make itself clear, of course. Alas, no. It didn’t trip a single one of the sanity checks added by enabling thee flag. So, what next?

The where in gdb tells us where in the C code we are. But what high level language code was MoarVM actually running at the time? Let’s dump the VM frame stack and find out:

(gdb) p MVM_dump_backtrace(tc)
   at <unknown>:1  (./blib/Perl6/Grammar.moarvm:initializer:sym<=>)
 from gen/moar/stage2/QRegex.nqp:1378  (/home/jnthn/dev/MoarVM/install/share/nqp/lib/QRegex.moarvm:!protoregex)
 from <unknown>:1  (./blib/Perl6/Grammar.moarvm:initializer)
 from src/Perl6/Grammar.nqp:3140  (./blib/Perl6/Grammar.moarvm:type_declarator:sym<constant>)
 from gen/moar/stage2/QRegex.nqp:1378  (/home/jnthn/dev/MoarVM/install/share/nqp/lib/QRegex.moarvm:!protoregex)
 from <unknown>:1  (./blib/Perl6/Grammar.moarvm:type_declarator)
 from <unknown>:1  (./blib/Perl6/Grammar.moarvm:term:sym<type_declarator>)
 from gen/moar/stage2/QRegex.nqp:1378  (/home/jnthn/dev/MoarVM/install/share/nqp/lib/QRegex.moarvm:!protoregex)
 from src/Perl6/Grammar.nqp:3825  (./blib/Perl6/Grammar.moarvm:termish)
 from gen/moar/stage2/NQPHLL.nqp:886  (/home/jnthn/dev/MoarVM/install/share/nqp/lib/NQPHLL.moarvm:EXPR)
from src/Perl6/Grammar.nqp:3871  (./blib/Perl6/Grammar.moarvm:EXPR)
...

I’ve snipped out a good chunk of a fairly long stack trace. But look! We were parsing and compiling a constant at the time of the crash. That’s somewhat interesting, and explains why constant.t was a likely test file to show this bug up. But MoarVM has little idea about parsing or Perl 6’s idea of constants. Rather, something on that codepath of the compiler must run into a bug of sorts.

Looking at the location in interp.c the op being interpreted at the time was decont, which takes a value out of a Scalar container, if it happens to be in one. Combined with knowing what code we were in, I can invoke moar --dump blib/Perl6/Grammar.moarvm, and then locate the disassembly of initializer:sym<=>.

There were a few uses of the decont op in that function. All of them seemed to be on things looked up lexically or dynamically. So, I instrumented those ops with a fromspace check. Re-compiled, and…

(gdb) break MVM_panic
Breakpoint 1 at 0x7ffff78a19a0: file src/core/exceptions.c, line 779.
(gdb) r
Starting program: /home/jnthn/dev/MoarVM/install/bin/moar --execname=./perl6-gdb-m --libpath=/home/jnthn/dev/MoarVM/install/share/nqp/lib --libpath=/home/jnthn/dev/MoarVM/install/share/nqp/lib --libpath=. /home/jnthn/dev/rakudo/perl6.moarvm --nqp-lib=blib -Ilib t/spec/S04-declarations/constant.rakudo.moar
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, MVM_panic (exitCode=1, 
    messageFormat=0x7ffff799bc58 "Collectable %p in fromspace accessed") at src/core/exceptions.c:779
779 void MVM_panic(MVMint32 exitCode, const char *messageFormat, ...) {
(gdb) where
#0  MVM_panic (exitCode=1, messageFormat=0x7ffff799bc58 "Collectable %p in fromspace accessed")
    at src/core/exceptions.c:779
#1  0x00007ffff78ba657 in MVM_interp_run (tc=0x1, tc@entry=0x6037c0, initial_invoke=0x0, 
    invoke_data=0x604b80) at src/core/interp.c:374
#2  0x00007ffff7979071 in MVM_vm_run_file (instance=0x603010, 
    filename=0x7fffffffe09f "/home/jnthn/dev/rakudo/perl6.moarvm") at src/moar.c:309
#3  0x000000000040108b in main (argc=9, argv=0x7fffffffdbc8) at src/main.c:192

And what’s in interp.c around that line? The getdynlex op. That’s the one that is used to lookup things like $*FOO in Perl 6. So, a dynamic lexical lookup seemed to be handing back an outdated object. How could that happen?

Interesting idea is insufficient

My next idea was to see if I could catch the moment that something bad was put into the lexical. I’d already instrumented the obvious places with no luck. But…what if I could intercept every single VM register access and see if an object from fromspace was read? Hmmm… It turned out that I could make that happen with a sufficiently cunning patch. I made it opt-in rather than the default for MVM_GC_DEBUG because it’s quite a slow-down. I’m sure that this will come in really useful for finding some GC bug some day. But for this bug? It was no direct help.

It was of some indirect help, however. It suggested strongly that at the time the lexical was set (actually, it turned out to be $*LEFTSIGIL), everything was valid. Somewhere between then and the lookup of it using the getdynlex op, things went bad.

Cache corruption

So what does getdynlex actually do? It checks if the current frame declares a lexical of the specified name. If so, it returns the value. If not, it looks in the caller for the value. If that fails, it goes on to the caller’s caller, until it runs out of stack to search and then gives up.

If that’s what it really did, then this bug would never have happened. But no, people actually want Perl 6 to run fast and stuff, so we can’t just implement the simplest possible thing and go chill. Instead, there’s a caching mechanism. And, as well all know, the two hardest problems in computer science are cache invalidation and cache invalidation.

The caching is relatively simple: each frame has slots for sticking a name, register pointer, and type in it.

MVMString   *dynlex_cache_name;
MVMRegister *dynlex_cache_reg;
MVMuint16    dynlex_cache_type;

When getdynlex finds something the slow way, it then looks down the stack again and finds a frame with an empty dynlex_cache_name. It then sticks the name of dynamic lexical into the name slot, a pointer to the MoarVM lexical into the reg slot, and what type of lexical it was (native int, native num, object, etc.) into the type slot. The most interesting of these is the reg slot. The MVMRegister type is actually a union of different types that we may store in a register or lexical. We re-use the union for registers that live while the frame is on the callstack and lexicals that may need to live longer thanks to closures. So, each frame as two arrays of these:

MVMRegister *env;   /* The lexical environment */
MVMRegister *work;  /* Working space that dies with the frame */

And so the dynlex_cache_reg ends up pointing to env somewhere in the frame that we found the lexical in.

So, the big question: was the caching to blame? I shoved in a way to disable it and…the bug vanished.

Note by this point we’re up to two pieces that contribute to the bug: the GC and the dynamic lexical cache. The thing is, the dynamic lexical cache is used very heavily. My gut feeling told me there must be at least one more factor at play here.

Suspicious specialization

So, what could the other factor be? I re-enabled the cache, verified the crash came back, and then stuck MVM_SPESH_DISABLE=1 into the environment. And…no bug. So, it appeared that dynamic optimization was somehow involved too. That’s the magic that looks at what types actually show up at runtime, and compiles specialized versions of the code that fast-paths a bunch of operations based on that (this specialization being where the name “spesh” comes from). Unfortunately, MVM_SPESH_DISABLE is a rather blunt instrument. It disables a huge range of things, leaving a massive surface area to consider for the bug. Thankfully, there are some alternative environment variables that just turn off parts of spesh.

First, I tried MVM_JIT_DISABLE=1, which results in spesh interpreting the specialized version of the code rather than turning it into machine code to remove the interpreter overhead. The bug remained.

Next, I tried MVM_SPESH_OSR_DISABLE, which disables On Stack Replacement. This is a somewhat fiddly optimization that detects hot loops as they are being interpreted, pauses execution, produces an optimized version of the code, and then recalculates the program counter so it points to the appropriate point in the optimize code and continues execution. Basically, the interpreter gets the code it’s executing replaced under it – perhaps with machine code, which the interpreter is instructed to jump into immediately. Since this also fiddles with frames “in flight”, it seemed like a good candidate. But…nope. Bug remained.

Finally, I tried MVM_SPESH_INLINE_DISABLE, which disables inlining. That’s where we spot a call to a relatively small subroutine or method, and just replace the call with the code of the sub or method itself, saving the cost of setting up callframes. And…bug vanished!

So, inlining was apparently a factor too. The trouble is, that also didn’t seem to add up to an obvious bug. Consider:

sub foo($a) {
    bar($a);
}
sub bar($b) {
    my $c = $b + 6;
    $c * 6
}

Imagine that bar was to be inlined into foo. Normally they’d have lexical slots in ->env as follows:

A:  | $_ | $! | $/ | $a |
B:  | $_ | $! | $/ | $b | $c |

The environment for the frame inline(A, B) would look like:

inline(A, B):  | $_ | $! | $/ | $a | $_ | $! | $/ | $b | $c |
                \---- from A ----/  \------- from B -------/

Now, it’s easy to imagine various bugs that could arise in the initial lookup of a dynamic lexical in such a frame. Indeed, the dynamic lexical lookup code actually has two bunches of code that deal with such frames, one in the case the specialized code is being interpreted and one in the case where it has been JIT compiled. But by the time we are hitting the cache, there’s nothing smart going on at all: it’s just a cheap pointer deference.

Dastardly deoptimization

So, it seems we need a fourth ingredient to explain the bug. By now, I had a pretty good idea what it was. MoarVM doesn’t just to optimizations based on properties it can prove will always hold. It can also do speculative optimization based on properties that it expects will probably hold up. For example, suppose we have:

sub foo($a, $b) {
    $b.some-huge-complex-call($a);
    return $a.Str;
}

Imagine we’re generating a specialization of this routine for the case $a is an object of type Product. The Str method is tiny, so we go ahead and inline it. However, some-huge-complex-call takes all kinds of code paths. We can’t be sure, from our analysis, that at some point it won’t mix in to the object in $a. What if it mixes in a role that has an alternate Str method? Our inlining would break stuff! We’d end up calling the Product.Str method, not the one from the mixin.

One reaction is to say “well, we’ll just not ever optimize stuff unless we can be REALLY sure”, which is either hugely limiting or relies on much more costly analyses. The other path, which MoarVM does, is to say “eh, let’s just assume mixins won’t happen, and if they do, we’ll fix things then!” The process of fixing things up is called deoptimization. We walk the call stack, rewriting return addresses to point to the original interpreted code instead of the optimized version of the code.

But what, you might wonder, do we do if there’s a frame on the stack that is actually the result of an inlining operation? What if we’re in the code that resulted from inline(A,B), in the bit that corresponds to the code of B? Well, we have to perform – you guessed it – uninlining! The composite call frame has to be dissected, and the call stack rewritten to look like it would have if we’d been running the original interpreted code. To do this, we’d create a call frame for B, complete with space for its lexicals, and copy the lexicals from inline(A,B) that belong to B into that new buffer.

The code that does this is one of the very few parts of MoarVM that frightens me.

For good reason, it turns out. This deoptimization, together with uninlining, was the final ingredient needed for the bug. Here’s what happened:

  1. The method EXPR in Perl6::Grammar was inlined into one of its callers. This EXPR method declares a $*LEFTSIGIL variable.
  2. While parsing the constant, the $*LEFTSIGIL is assigned to the sigil of the constant being declared, if it has one (so, in constant $a = 42 it would be set to $).
  3. Something does a lookup of $*LEFTSIGIL. It is located and cached. The cache entry points into a region of the ->env of the frame that inlined, and thus incorporated, the lexical environment of EXPR.
  4. At some point, a mixin happens, causing a deoptimization of the call stack. The frame that inlined EXPR gets pulled apart. A new EXPR frame comes to exist, with the lexicals that used to live in the composite frame copied into them. Execution continues.
  5. A GC happens. The object containing the $ substring moves. The new EXPR frame’s lexical environment is updated.
  6. Another lookup of $*LEFTSIGIL happens. It hits the cache. The cache, however, still points to the place the lexical used to live in the composite frame. This memory has not been freed, because the first part of it is still being used. However, the GC no longer cares about its contents because that content is unreachable. Therefore, it contains an outdated pointer, thus leading to accessing memory that’s being used for something else entirely by that point, leading to the eventual segmentation fault.

The most natural fix was to invalidate the cache during deoptimization.

Lessons learned

The bug I wrote up last week was thanks to a comparatively simple oversight made within the scope of a few lines of a single C function. While this one could be fixed with a small amount of code added in a single file, the segfault arose from the interaction of four distinct features existing in MoarVM:

Even when a segfault was not produced, thanks to “lucky” GC timing, the bug would lead to reading of stale data. It just so turned out that the data wasn’t ever stale enough in reality to break things on this particular code path.

All of garbage collection, inlining, and deoptimization are fairly complicated. By contrast, the dynamic lexical lookup cache is fairly easy. Interestingly, it was the addition of this easy feature that introduced the bug – not because the code that was added was wrong, but rather because it did something that some other far flung piece of code – the deoptimizer – had quietly relied on not happening.

So, what might be learned for the future?

The most immediate practical learning is that taking interior pointers into mutable data structures is risky. In this case, that data structure was a composite lexical environment, that later got taken apart. Conceptually, the environment was resized and the interior pointer was off the end of the new size. This suggests either providing a safe way to acquire such a reference, or an alternative design for the dynamic lexical cache to avoid needing to do so.

Looking at the bigger picture, this is all about managing complexity. Folks who work with me tend to observe I worry a good bit about loose coupling, to the degree that I’m much more hesitant than the typical developer when it comes to code re-use. Acutely aware that re-use means use, and use means dependency, and dependency means coupling, I tend to want things to prove they really are the same thing rather than just looking like they might be the same thing. MoarVM reflects this in various ways: to the degree I can, I try to organize it as a collection of parts that either keep themselves very much to themselves, or that collaborate over a small number of very stable data structures. One of the reasons Git works architecturally is because while all the components of it are messing with the same data structure, it’s a very stable and well-understood data structure.

In this bug, MVMFrame is the data structure in question. A whole load of components know about it and work with it because – so the theory went – it’s one of the key stable data structures of the VM. Contrast it with the design of things like the Unicode normalizer or the fixed size allocator, which nothing ever pokes into directly. These are likely to want to evolve over time to choose smarter data structures, or to get extra bits of state to cope with Unicode’s latest and greatest emoji boundary specification. Therefore, all work with them is hidden nicely behind an API.

In reality, MVMFrame has grown to contain quite a fair few things as MoarVM has evolved. At the same time, its treated as a known quantity by lots of parts of the codebase. This is only sustainable if every addition to MVMFrame is followed by considering how every other part of the VM that interacts with it will be affected by the change, and making compensating changes to those components. In this case, the addition of the dynamic lexical cache into the frame data structure was not accompanied by sufficient analysis of which other parts of the VM may need compensating changes.

The bug I wrote up last week isn’t really the kind that causes an architect a headache. It was a localized coding slip-up that could happen to anyone on a bad day. It’s a pity we didn’t catch it in code review, but code reviewers are also human. This bug, by contrast, arose as a result of the complexity of the VM – or, more to the point, insufficient management of that complexity. And no, I’m not beating myself up over this. But, as MoarVM architect, this is exactly the type of bug that catches my eye, and causes me to question assumptions. In the immediate, it tells me what kinds of patches I should be reviewing really carefully. In the longer run, the nature of the MVMFrame data structure and its level of isolation from the rest of the codebase deserves some questioning.


Perl 6 Advent Calendar: Day 9 – A preview of the ‘hackable’ JIT compiler

Published by bartwiegmans on 2016-12-09T00:00:48

Among programming languages Perl 6 has an unfortunate but historically well-deserved reputation for being slow, even compared to languages such as Perl 5, Ruby or Python. This is not really an accident, however. From the outset, perl6 was designed to be extensible by the programmer in many different ways, including defining custom operators, dynamic containers for variables, and a powerful meta-object protocol that allow you to modify the behaviour of objects and classes from regular Perl code. In the future, we might well add macros to that list. To this are added a rich set of control structures and phasers. Such features are useful, powerful and fun.

But such features also make it relatively difficult to execute perl6 efficiently, because they introduce overhead and polymorphism. Even before the language was released last year, work had started to improve the efficiency of Rakudo Perl 6. Because Rakudo is complex and layered, this works involves many aspects and many individuals, from core routine efficiency improvements to precompilation of modules. MoarVM also tries to specialize ‘hot’ code for specific object types at runtime, which reduces the polymorphism of that code, and allows simpler operations to be substituted for complex operations. For example, object attribute access can in many cases be reduced to a simple memory read instruction.

Since late summer 2014, MoarVM has contained a JIT compiler that I developed. At its core, JIT compilation reduces the overhead from interpretation. That is to say, rather than fetch new instructions from a bytecode stream and dispatch to execute them, a JIT compiler generates the code to execute these instructions in a series. Ideally, this allows the executed code to ‘flow’ directly through the program without interruption. In practice, there is still the machinery of the VM, for example for garbage collection, to take into account. Also, note that in many VM implementations, the JIT compiler and the type specialization code are combined, whereas in MoarVM they are distinct components.

Since summer 2015 (yes, that long) I’ve been working on an improved backend for that compiler, which was funded by the Perl foundation. One of the goals for the development of that backend (which I misleadingly call the ‘expression JIT compiler’) was to enable extension points for specialized object types and instructions. These extension points are designed to enable a greater range of type specialization and to improve code generation gradually. The best part, I think, is that they should require relatively little knowledge of compiler internals or assembly language. For this advent calendar post, I’d like to demonstrate those extension points.

First, consider the following innocent-looking perl6 code.

sub foo(@a) {
    @a[0] = @a.elems;
}

In case this (obviously critical) `foo` subroutine is invoked hundreds of times, MoarVM will start to optimize it, first by recording what @a really is. In most cases, that will be an instance of the Array class. If it always the same, and supposing the elems method is sufficiently small (which it is), that method call will be inlined into the foo routine. The assignment of @a[0] is somewhat more involved than it looks and what it would be like in a language like Java. In Perl 6, an array holds a sequence of containers, and it is the container to which the value is assigned. So the primitive sequence of operations in ‘foo’ after MoarVM has optimized it is similar to:

my $i := nqp::elems(@a);
my $c := nqp::atpos_o(@a, 0);
nqp::assign($c, $i);

The ‘nqp’ namespace signifies that these are primitive operations in the interpreter. However, they are still polymorphic, because arrays can be represented by multiple different stores. For example, arrays that are used by NativeCall foreign function interface use a different representation (for compatibility reasons) than the arrays natively used by the VM (which are called MVMArray internally). Thus, these operations are polymorphic, and MoarVM needs a dispatch table to find the correct implementation.

If the exact implementation type of @a is known, then this polymorphism is unnecessary. In principle, the type specializer could insert a specialized non-polymorphic instruction for each of those operations for the types found during the recording phase. That is not very practical though as there are many different types and each type would have to support many different operations.

However, with the expression compiler it will be relatively easy to add specialized code for a specific implementation. See for instance the following (somewhat simplified) implementations of the ‘elems’ and ‘atpos_o’ MoarVM instructions, which would work on MVMArray objects:

(template: elems (^getf $1 MVMArray body.elems))

(template: atpos_o 
  (load (index (^getf $1 MVMArray body.slots.o) $2 8)
        (&SIZEOF MVMObject*)))

Such ‘expression templates’ are textual representations of the templates used in the compiler to convert relatively high-level MoarVM bytecode to low-level code which is easier to compile and optimize. Although the code above might look complex, it is actually pretty straightforward:

Such templates can be added without any knowledge of assembler whatsoever, although some knowledge of C structure and VM internals are probably preferable. I hope that by making this simple enough I can convince others to share the task of JIT compiler development with me :-).

For those who are feeling more adventurous yet, it is also simple to hook into the data-driven code generator known as the tiler. The tiler picks the CPU instructions to implement the low-level code generated from expression templates. Each CPU instruction is represented by a ’tile’, which ‘covers’ part of the expression graph. The tiler tries to pick the optimal instruction so that the entire code graph is covered as cheaply as possible. As the x86 instruction set is very large, it is nearly impossible for me to write tiles for every possible instruction. Adding a tile is not very hard, though. Suppose for instance that we’d be writing a program to compute the XOR of all values in the array:

my $x = 0;
for @a -> $i {
    $x +^= $i;
}

In reality, there are still multiple barriers to implementing this as a tight loop, but suppose that we have taken them down. (We can, it is a matter of time and energy). Then you might find that the sequence of INDEX, LOAD and XOR operations were be inefficient, and you could optimize that into a single instruction. You can declare a tile for that instruction as follows:

(tile: xor_load_idx 
   (xor reg (load (index reg reg $stride) $size)) reg)

The tile implementation would look as follows:

MVM_JIT_TILE_DECL(xor_load_idx) {
    MVMint8 out  = tile->values[0];
    MVMint8 base = tile->values[1];
    MVMint8 idx  = tile->values[2];
    /* this only works on 8-byte sized indexes (for now) */
    ASSERT(tile->args[0] == 8 && tile->args[1] == 8);
    | xor Rq(out), qword [Rq(base)+Rq(idx)*8];
}

The `MVM_JIT_TILE_DECL` macro declares the tile function with all required parameters. The ’tile’ parameter which is declared and passed automatically contains operational details such as the registers used (in ’tile->values’) and constant parameters (in ’tile->args’). The function of the assembly-code fragment that follows the ‘|’ symbol is to declare a piece of machine code that is to be assembled at runtime. For this we use dynasm with a few patches to support picking ‘dynamic’ registers on x86-64. The result of this addition would be that the aforementioned sequence of instructions would be compiled to a single one and your (hypothetical) program would run a few percent faster. Although small, such improvements can add up.

Unfortunately, all of this is not done yet. Although in a way the main body of the compiler exists, some essential pieces (especially the register allocator) need further development, and there are quite a few bugs and oversights that need to be fixed, too. So unfortunately you can’t play with this – yet. However, I do hope that I’ve given you a taste of what you can do when it is finished, which I hope to be soon. And with that, I wish you a happy holiday.


Perl 6 Advent Calendar: Day 8 — How to Make, Use, and Abuse Perl 6 Subsets

Published by Zoffix Znet on 2016-12-08T01:19:22

Ever reached for a Perl 6 type and found it good enough, but not perfect? Perhaps, you wanted an IntEven, StrPalindrome, or YourCustomClassWhereAttrFooIsBar. Never fear, Perl 6’s subsets are here!

What Are Subsets?

You can think of them as a refinement on some type and you can use them in most places where you’d use a type, such as in type constraints. To create one, use the subset keyword, along with a where keyword specifying your refinement:

    subset Even where * %% 2;
    say 1 ~~ Even; # False
    say 2 ~~ Even; # True

The WhateverStar * is the value being checked and the %% operator checks if that value is evenly divisible by 2. We can now use our subset on the right side of a smartmatch operator to check whether a value is an even number! Pretty awesome. What else can we do with it?

How about type-constraining a variable:

    my Even $x = 42; # all good

    $x = 43; # and this?
    # Type check failed in assignment to $x; expected Even but got Int (43)
    #   in block <unit> at script.p6 line 3

Or type-constraining input and output of a routine:

    sub takes-an-even-only (Even $x) { $x² }
    sub returns-an-even-only returns Even { $^x² }

    say takes-an-even-only   42; # 1764
    say returns-an-even-only 42; # 1764

    say takes-an-even-only   43;
    # Constraint type check failed for parameter '$x'
    #   in sub takes-an-even-only at script.p6 line 2
    #   in block <unit> at script.p6 line 8

    say returns-an-even-only 43;
    # Type check failed for return value; expected Even but got Int (1849)
    #   in sub returns-an-even-only at script.p6 line 3
    #   in block <unit> at script.p6 line 13

That’s all pretty sweet, but our Even accepts strings and other weird stuff:

    say '42.0000' ~~ Even; # True
    say class { method Real { 42 } }.new ~~ Even; # True

There’s a reason for that: we never specified what type we’re making a subset of, so by default, it used Any. Let’s fix that!

Getting Typical

If you want to create a subset based on some type, specify that type with the of keyword:

    subset IntEven of Int where * %% 2;

Now, before the where refinement even runs, the value we’re checking against must first pass the Int type constraint:

    say 42 ~~ IntEven; # True
    say 43 ~~ IntEven; # False
    say '42.0000' ~~ IntEven; # False
    say class { method Real { 42 } }.new ~~ IntEven; # False

We’re not limited to numerics! Let’s try a Str:

    subset StrPalindrome of Str where {
        .flip eq $_ given .comb(/\w+/).join.lc;
    }

    say ’Madam, I'm Adam.~~ StrPalindrome; # True
    say '1 on 1'  ~~ StrPalindrome; # False

We’re now using a more complex refinement in the where clause, using a code block. Just like the WhateverCode version with the *, the block receives the value to check as its argument, which it aliases to $_ topical variable. The code block tells us whether the argument is a palindrome, by returning a truthy or falsy value.

So how far can we go with the type constraints in our subsets?

Custom Made

We can type-constrain a subset using any class we have lying around! How about this one:

    class Awesome { has $.awesomeness-level }
    my $obj1 = Awesome.new: :10000awesomeness-level;
    my $obj2 = Awesome.new: :31337awesomeness-level;

We make a class called Awesome that has a public attribute called awesomeness-level. We also create two instances of that class, setting the awesomeness-level to 10000 in $obj1 and to 31337 in $obj1. So how about a subset that checks whether awesomeness-level is a prime number? It’s just a single line of code:

    subset AwesomePrime of Awesome where .awesomeness-level.is-prime;

    say $obj1 ~~ AwesomePrime; # False
    say $obj2 ~~ AwesomePrime; # True

The where block of the subset is “thunked,” which means the compiler takes an expression and turns it into a code block for us, so we don’t have to explicitly use a codeblock here, nor do we need a WhateverStar. The value being checked is in the $_ topical variable, which is what method calls use when you don’t specify what you’re calling them on. Thus, our subset expects a thing of type Awesome and then checks whether its awesomeness-level attribute is a prime number!

By using such subsets, you can create routines that only accept your custom objecs of a specific configuration. For example, in code of an IRC::Client bot, we can create a subset of IRC::Client::Message for messages that are received from bot admins, and then register events only for such messages:

    subset BotAdmin of IRC::Client::Message where .host eq conf<bot-admins>.any;

    multi method irc-to-me (BotAdmin $e where /:i ^ 'run' $<steps>=.+ $/ ) {
        ...
    }

The subset calls the subroutine that reads configuration and provides a list of bot admin hosts against which the host of the sender of the message is checked. We’re encapsulating the logic that checks we have an acceptable object to work with, and we’re able to call that logic even before we enter our method.

So if we can do that with subsets… is there anything we can’t do?

Time for Some Heavy Abuse!

Let’s do something crazy! A subroutine that fetches a link to a website and checks whether it contains a mention of Perl 6:

    use LWP::Simple;
    sub is-perl-site { LWP::Simple.get( $^website ).contains: 'Perl 6' }

There’s nothing crazy about that, you say? Then, how about we use that subroutine as a refiner in a subset where clause:

    subset PerlWebsite where &is-perl-site;

    say 'http://perl6.party' ~~ PerlWebsite; # True
    say 'http://lolcats.com' ~~ PerlWebsite; # False

In fact, we can make a routine that only accepts URLs to websites mentioning Perl 6:

    sub ain't-taking-non-perl-stuff (PerlWebsite $url) {
        say "Why! I can already tell $url is awesome!";
    }

    ain't-taking-non-perl-stuff 'http://perl6.party';
    # Why! I can already tell http://perl6.party is awesome!

    ain't-taking-non-perl-stuff 'http://lolcats.com';
    # Constraint type check failed for parameter '$url'
    #   in sub ain't-taking-non-perl-stuff at script.p6 line 8
    #   in block <unit> at script.p6 line 15

But do you notice something off? The error message is rather poor… Let’s improve it!

What we know so far is the where clause takes some code to run and if that code’s result is falsy, the typecheck will fail. That means inside the where we can know whether or not the typecheck will fail before we even return from it. Let’s put that to use:

    sub is-perl-site {
        given LWP::Simple.get( $^website ).contains: 'Perl 6' {
            when :so  { True }
            when :not {
                say ’This ain't no website containing "Perl 6"!‘;
                False;
            }
        }
    }

    subset PerlWebsite where &is-perl-site;

In the routine that checks a website mentions Perl 6, in the case when it does :not contain a mention of Perl 6, we say a helpful message, indicating what exactly was wrong. Let’s run this:

    sub ain't-taking-non-perl-stuff (PerlWebsite $url) {
        say "Why! I can already tell $url is awesome!";
    }

    ain't-taking-non-perl-stuff 'http://perl6.party';
    # Why! I can already tell http://perl6.party is awesome!

    ain't-taking-non-perl-stuff 'http://lolcats.com';
    # This ain't no website containing "Perl 6"!
    # This ain't no website containing "Perl 6"!
    # Constraint type check failed for parameter '$url'
    #   in sub ain't-taking-non-perl-stuff at script.p6 line 16
    #   in block <unit> at script.p6 line 23

Whoa! The message printed twice. What gives?

It’s actually expected that the refinement in subsets is an inexpensive and relatively simple operation… With that expectation in mind, the parameter binder—which doesn’t know how to generate errors—simply passes its stuff through the slower code path—which does—and it’s that slower code path that runs the where code the second time, triggering our message one more time.

So yes, doing overly complex stuff in subsets is abusive. However, you can throw an exception inside the where to avoid the repetition of the message:

    sub is-perl-site {
        LWP::Simple.get( $^website ).contains: 'Perl 6'
            or die ’This ain't no website containing "Perl 6"!‘;
    }

    ...

    ain't-taking-non-perl-stuff 'http://lolcats.com';
    # This ain't no website containing "Perl 6"!
    #   in sub is-perl-site at z.p6 line 4
    #   in any accepts_type at gen/moar/m-Metamodel.nqp line 3472
    #   in sub ain't-taking-non-perl-stuff at z.p6 line 11
    #   in block <unit> at z.p6 line 18

And don’t forget to check out Subset::Helper and Subset::Common modules.

What About a Light Spanking?

There is one type of abuse cheating with subsets that can get you out of a bind: fiddling with narrowness when it comes to resolution of multi candidates.

For example, let’s say you hate humanity and you wish to change the meaning of the infix + operator on two Ints to do subtraction instead of addition. You, of course, write this:

    multi sub infix:<+> (Int $a, Int $b) { $a$b }

But as you run a sample code, over the sound of your evil laughter…

    Ambiguous call to 'infix:<+>'; these signatures all match:
    :(Int:D \a, Int:D \b --> Int:D)
    :(Int $a, Int $b)
      in block <unit> at z.p6 line 4

… the complier errors out.

You see, core language already has an infix + operator that takes two Ints! When you add one of your own, you create an ambiguity. To resolve this issue, we need to somehow create an Int that the compiler thinks is narrower than an Int, but in reality isn’t. Sounds tough? Not an issue for subsets:

    subset NarrowInt of Int where {True};
    multi sub infix:<+> (NarrowInt $a, NarrowInt $b) { $a$b }

    say 42 + 2; # 40

It worked! We created a subset of Int, so we match all of Ints, just like we wanted. In the refinement, however, we specify a single code block that always returns True, making that refinement always succeed, and making our subset accept all the values a regular Int accepts, while being narrower than a regular Int as far as multi resolution goes.

If you’re wondering why we had to use an explicit block, it’s because the where smartmatches, and the smartmatch against a True produces a warning, because it’s always true, and while that is what we want here, in most code such a construct is a mistake.

But if you’re upset about writing one-too-many characters, here’s neat trick:

    multi sub infix:<+> (Int $a where {True}, Int $b where {True}) { $a - $b }
    say 42 + 2;

You don’t need to create an explicit subset, and can stick a where clause right onto the thing you’re working with to refine just that thing. The type constraint on it will function as the of ... of a subset.

You can also type constraint a variable with a subset and still add a where clause. Or create a subset of a subset of a subset and still add… well, we’re getting carried away.

When they stop calling…

Consider this piece of wonderful code:

    class Thingie {
        multi method stuff ($ where /meows/) { say "Meow meow!"; }
    }

    class SubThingie is Thingie {
        multi method stuff ($ where /foos/) { say "Just foos..."; }
    }

    SubThingie.new.stuff: 'meows and foos'; # Just foos...

You have a class with a multi method. Along with it, you have a subclass of it with another multi method of the same name. Both have a where clause and when you call the method with input that can match either multi, the subclass’s multi gets called. But what do you do if you want to reverse that… you want the parent class’s multi to be called, if both multies matches the input.

The first solution is very simple. Just add a type constraint (we’ll use Str) in the parent class, while leaving it off in the child:

    class Thingie {
        multi method stuff (Str $ where /meows/) { say "Meow meow!"; }
    }

    class SubThingie is Thingie {
        multi method stuff ($ where /foos/) { say "Just foos..."; }
    }

    SubThingie.new.stuff: 'meows and foos'; # Meow meow!

The presence of a type constraint on the method in the parent class makes it narrower than the one in the subclass, so even though the subclass’s method can also accept the input, it’s the parent class that gets to take care of it.

However, what if we wanted the same Str type constraint on both methods? The parent class we’ll leave as is: just a normal Str type constraint. In the kid, however, we’ll use a wider subset of Any (that’s the default if you don’t specify the of, remember?), but in its where clause we’ll smartmatch against Str, to ensure the subset accepts only Strs:

    class Thingie {
        multi method stuff (Str $ where /meows/) { say "Meow meow!"; }
    }

    class SubThingie is Thingie {
        subset WiderStr where { $_ ~~ Str };
        multi method stuff (WiderStr $ where /foos/) { say "Just foos..."; }
    }

    SubThingie.new.stuff: 'meows and foos'; # Meow meow!

The result is the opposite of a cheat we made in the previous section: instead of a subset that matches a type exactly, but is narrower than it, we now created a subset that matches a type exactly, but is wider than it, as far as multi candidate resolution goes. And yes, you can just merge the two where clauses instead of creating a subset, producing:

    multi method stuff ($ where { $_ ~~ Str and $_ ~~ /foos/ }) {
        say "Just foos...";
    }

It’ll work the same.

Conclusion

Subsets are a powerful feature that lets you specify refinements on existing core and custom types. You can smartmatch against a subset to perform a check on a value, or you can use subsets to type-contraint variables, parameters, and return values.

You can use the subset keyword to create a named subset, or you can attach a refinement onto a specific variable or parameter with a where clause. Subsets can also be used to effect alternative narrowness of a parameter, to affect multi candidate resolution order.

Subsets can also be abused to perform very complex operations, but… that’s probably a bad idea.

-Ofun


Perl 6 Advent Calendar: Day 7 — Set In Your Ways: Perl 6’s Setty and Baggy Types

Published by Zoffix Znet on 2016-12-07T01:00:19

There’s a relatively common pattern I see with people writing code that counts… say, DNA bases in a string:

my %counts;
%counts{$_}++ for 'AGTCAGTCAGTCTTTCCCAAAAT'.comb;
say %counts<A T G C>; # (7 7 3 6)

Make a Hash. For each thing you want to count, ++ that key in that Hash. So what’s the problem?

Perl 6 actually has specialized types that are more appropriate for this operation; for example, the Bag:

'AGTCAGTCAGTCTTTCCCAAAAT'.comb.Bag<A T G C>.say; # (7 7 3 6)

Let’s talk about these types and all the fancy operators that come with them!

A Note on Unicode

I’ll be using fancy-pants Unicode versions of operators and symbols in this post, because they look purty. However, all of them have what we call “Texas” equivalents you can use instead.

Ready. Set. Go.

The simplest of these types is a Set. It will keep exactly one of each item, so if you have multiple objects that are the same, the duplicates will be discarded:

say set 1, 2, 2, "foo", "a", "a", "a", "a", "b";
# OUTPUT: set(a, foo, b, 1, 2)

As you can see, the result has only one a and only one 2. We can use the , U+2208 ELEMENT OF, set membership operator to check if an item is in a set:

my $mah-peeps = set <babydrop iBakeCake Zoffix viki>;
say 'Weeee \o/' if 'Zoffix'  $mah-peeps;
# OUTPUT: Weeee \o/

The set operators are coercive, so we don’t need to explicitly create a set; they’ll do it for us:

say 'Weeee \o/' if 'Zoffix'  <babydrop iBakeCake Zoffix viki>;
# OUTPUT: Weeee \o/

But pay attention when using allomorphs:

say 'Weeee \o/' if 42  <1 42 72>;
# No output

say 'Weeee \o/' if 42  +«<1 42 72>; # coerce allomorphs to Numeric
# OUTPUT: Weeee \o/

The angle brackets create allomorphs for numerics, so in the first case above, our set contains a bunch of IntStr objects, while the left hand side of the operator has a regular Int, and so the comparison fails. In the second case, we coerce allomorphs to their numeric component with a hyper operator and the test succeeds.

While testing membership is super exciting, we can do more with our sets! How about some intersections?

my $admins = set <Zoffix mst [Coke] lizmat>;
my $live-in-North-America = set <Zoffix [Coke] TimToady huggable>;

my $North-American-admins = $admins  $live-in-North-America;
say $North-American-admins;
# OUTPUT: set(Zoffix, [Coke])

We intersected two sets with the , U+2229 INTERSECTION, intersection operator and received a set that contains only the elements present in both original sets. You can chain these operations too, so membership will be checked in all of the provided sets in the chain:

say <Zoffix lizmat>  <huggable Zoffix>  <TimToady huggable Zoffix>;
# OUTPUT: set(Zoffix)

Another handy operator is the set difference operator, whose Unicode look I find somewhat annoying: No, it’s not a backslash (\), but a U+2216 SET MINUS character (luckily, you can use the much more obvious (-) Texas version).

The usefulness of the operator compensates its shoddy looks:

my @spammers = <spammety@sam.com  spam@in-a-can.com  yum@spam.com>;
my @senders  = <perl6@perl6.org   spammety@sam.com   good@guy.com>;

for keys @senders  @spammers -> $non-spammer {
    say "Message from $non-spammer";
}

# OUTPUT:
# Message from perl6@perl6.org
# Message from good@guy.com

We have two arrays: one contains a list of spammers’ addresses and another contains a list of senders. How to get a list of senders, without any spammers in it? Just use the (fine, fine, the (-)) operator!

We then use the for loop to iterate over the results, and as you can see from the output, all spammers were omitted… But why is keys there?

The reason is Setty and Mixy types are a lot like hashes, in a sense that they have keys and values for those keys. Set types always have True as values, and since we don’t care about iterating over Pair objects in our loop, we use the keys to get just the keys of the set: the email addresses.

However, hash-like semantics aren’t useless on Sets. For example, we can take a slice, and with :k adverb return just the elements that the set contains:

my $meows = set <
    Abyssinian  Aegean  Manx      Siamese  Siberian  Snowshoe
    Sokoke      Sphynx  Suphalak  Thai
>;

say $meows<Sphynx  Raas  Ragamuffin  Thai>:k;
# OUTPUT: (Sphynx Thai)

But what happens if we try to delete an item from a set?

say $meows<Siamese>:delete;
# Cannot call 'DELETE-KEY' on an immutable 'Set'
# in block <unit> at z.p6 line 6

We can’t! The Set type is immutable. However, just like Map type has a mutable version Hash, so does the Set type has a mutable version: the SetHash. There isn’t a cutesy helper sub to create one, so we’ll use the constructor instead:

my $s = SetHash.new: <a a a b c d>;
say $s;
$s<a d>:delete;
say $s;

# SetHash.new(a, c, b, d)
# SetHash.new(c, b)

Voilà! We successfully deleted a slice. So, what other goodies does Santa have in his… bag?

Gag ’em ‘n’ Bag ’em

Related to Sets is another type: a Bag, and yes, it’s also immutable, with the corresponding mutable type being BagHash. We already saw at the start of this article we can use a Bag to count stuff, and just like a Set, a Bag is hash-like, which is why we could view a slice of the four DNA amino acids:

'AGTCAGTCAGTCTTTCCCAAAAT'.comb.Bag<A T G C>.say; # (7 7 3 6)

While a Set has all values set to True, a Bag‘s values are integer weights. If you put two things that are the same into a Bag there’ll be just one key for them, but the value will be 2:

my $recipe = bag 'egg', 'egg', 'cup of milk', 'cup of flour';
say $recipe;
# OUTPUT: bag(cup of flour, egg(2), cup of milk)

And of course, we can use our handy operators to combine bags! Here, we’ll be using , U+228E MULTISET UNION, operator, which looks a lot clearer in its Texas version: (+)

my $pancakes = bag 'egg', 'egg', 'cup of milk', 'cup of flour';
my $omelette = bag 'egg', 'egg',  'egg', 'cup of milk';

my $shopping-bag = $pancakes  $omelette  <gum  chocolate>;
say $shopping-bag;
# bag(gum, cup of flour, egg(5), cup of milk(2), chocolate)

We used two of our Bags along with a 2-item list, which got correctly coerced for us, so we didn’t have to do anything.

A more impressive operator is , U+227C PRECEDES OR EQUAL TO, and it’s mirror , U+227D SUCCEEDS OR EQUAL TO, which tell whether a Baggy on the narrow side of the operator is a subset of the Baggy on the other side; meaning all the objects in the smaller Baggy are present in the larger one and their weights are at most as big.

Here’s a challenge: we have some materials and some stuff we want to build. Problem is, we don’t have enough materials to build all the stuff, so what we want to know is what combinations of stuff we can build. Let’s use some Bags!

my $materials = bag 'wood' xx 300, 'glass' xx 100, 'brick' xx 3000;
my @wanted =
    bag('wood' xx 200, 'glass' xx 50, 'brick' xx 3000) but 'house',
    bag('wood' xx 100, 'glass' xx 50)                  but 'shed',
    bag('wood' xx 50)                                  but 'dog-house';

say 'We can build...';
.put for @wanted.combinations.grep: { $materials  [] |$^stuff-we-want };

# OUTPUT:
# We can build...
#
# house
# shed
# dog-house
# house shed
# house dog-house
# shed dog-house

The $materials is a Bag with our materials. We used xx repetition operator to indicate quantities of each. Then we have a @wanted Array with three Bags in it: that’s the stuff we want to build. We’ve also used used the but operator on them to mix in names for them to override what those bags will .put out as at the end.

Now for the interesting part! We call .combinations on our list of stuff we want, and just as the name suggests, we get all the possible combinations of stuff we can build. Then, we .grep over the result, looking for any combination that takes at most all of the materials we have (that’s the operator). On it’s fatter end, we have our $materials Bag and on its narrower end, we have the operator that adds the bags of each combination of our stuff we want together, except we use it as a metaoperator [⊎], which is the same as putting that operator between each item of $^stuff-we-want. In case you it’s new to you: the $^ twigil on $^stuff-we-want creates an implicit signature on our .grep block and we can name that variable anything we want.

And there we have it! The output of the program shows we can build any combination of stuff, except the one that contains all three items. I guess we just can’t have it all…

…But wait! There’s more!

Mixing it Up

Let’s look back at our recipe code. There’s something not quite perfect about it:

my $recipe = bag 'egg', 'egg', 'cup of milk', 'cup of flour';
say $recipe;
# OUTPUT: bag(cup of flour, egg(2), cup of milk)

What if a recipe calls for half a cup of milk instead of a whole one? How do we represent a quarter of a teaspoon of salt, if Bags can only ever have integer weights?

The answer to that is the Mix type (with the corresponding mutable version, MixHash). Unlike a Bag, a Mix supports all Real weights, including negative weights. Thus, our recipe is best modeled with a Mix.

my $recipe = Mix.new-from-pairs:  'egg'          => 2, 'cup of milk' => ½,
                                  'cup of flour' => ¾, 'salt'        => ¼;
say $recipe;
# mix(salt(0.25), cup of flour(0.75), egg(2), cup of milk(0.5))

Be sure to quote your keys and don’t use colonpair form (:42a, or :a(42)), since those are treated as named arguments. There’s also a mix routine, but it doesn’t take weights and functions just like bag routine, except returning a Mix. And, of course, you can use a .Mix coercer on a hash or a list of pairs.

Less-Than-Awesome creation aside, let’s make something with mixes! Say, you’re an alchemist. You want to make a bunch of awesome potions and you need to know the total amount of ingredients you’ll need. However, you realize that some of the ingredients needed by some reactions are actually produced as a byproduct by other reactions you’re making. So, what’s the most efficient amount of stuff you’ll need? Mixes to the rescue!

my %potions =
    immortality  => (:oxium(6.98), :morphics(123.3),  :unobtainium(2)   ).Mix,
    invisibility => (:forma(9.85), :rubidium(56.3),   :unobtainium(−0.3)).Mix,
    strength     => (:forma(9.15), :rubidium(−30.3),  :kuva(0.3)        ).Mix,
    speed        => (:forma(1.35), :nano-spores(1.3), :kuva(1.3)        ).Mix;

say [] %potions.values;
# OUTPUT: mix(unobtainium(1.7), nano-spores(1.3), morphics(123.3),
#              forma(20.35), oxium(6.98), rubidium(26), kuva(1.6))

For convenience, we set up a Hash, with keys being names of potions and values being Mixes with quantities of ingredients. For reactions that produce one of the ingredients we seek, we’ve used negative weights, indicating the amount produced.

Then, we used the same set addition operator we saw earlier, in it’s meta form: [⊎]. We supply it the .values of our Hash that are our Mixes, and it happily adds up all of our ingredients, which we see in the output.

Look at unobtainium and rubidium: the set operator correctly accounted for the quantities produced by reactions where those ingredients have negative weights!

With immortality potion successfully mixed, all we need to do now is figure out what to do for the next few millennia… How about coding some Perl 6?


Perl 6 Advent Calendar: Day 6 – Perl 6 Books — the Time is Ripe

Published by Moritz on 2016-12-06T01:00:36

One question we occasionally get on the phenomenal #perl6 IRC channel is about Perl 6 books. It turns out, some folks don’t want to learn just from tutorials, blog posts and docs. Last year, we didn’t have any good answers to that question.

A few months ago, there seemed to be a flurry of such questions, and at the same time, rumours about new book projects started to spread.

If I remember correctly, the first rumour was when Laurent Rosenfeld contacted me in June, asking for feedback on a manuscript. He had translated a good 200 pages of the Think Python book to Perl 6. This is primarily a book teaching programming to beginners. Later I was happy to hear that a major publisher has accepted the manuscript. The manuscript is now finished, and under review. So I guess we’ll see e-book and print versions of this book in due time.

Then brian d foy opened a kickstarter to raise funds for a “Learning Perl 6” book. By the time this is published, the kickstarter project should still be open, so I warmly encourage you to support this. Having a book by a prominent member of the Perl 5 community, and author of several good Perl books would surely be a boon for the Perl 6 community.

Before the publication of brian’s project, I’ve been mulling about writing my own Perl 6 book. In the past, I’ve tried that once already, and failed. But I had more success with another book project of mine, so I decided to give it another shot. The working title is Perl 6 by example. Content for the book is published in form of blog posts, and later turned into book chapters.

Later I learned that Ken Youens-Clark had written a book on metagenomics that spends about 150 pages explaining Perl 6. And it’s free, you can download the PDF, epub and mobi versions right away! If you’ve followed the advent calendar, you might have read Ken’s earlier post on Bioinformatics

In summary, we have one book starring Perl 6 content, one in progress with the manuscript in stage “feature complete”, one in the kick-starting phase which you can support, and a fourth being written right now, with parts being pre-published in the form of blog posts.

If you want to keep up-to-date with news on Perl 6 books, you can sign up for the low volume Perl 6 book mailing list (less than one mail per month).

I hope that in next year’s advent calendar, we’ll see four reviews of Perl 6 books.


Weekly changes in and around Perl 6: 2016.49 It’s Looking A Lot Like Blog Posts

Published by liztormato on 2016-12-05T22:51:34

Like snow flakes, all different, all unique! But a lot to read and to take in. On the other hand, you have a whole week to catch up!

Adventing Perl 6

Yes, it’s that time of the year again: every day a blog post about a specific Perl 6 feature. Every Day!

Quick Tipping

As part of the Learning Perl 6 Kickstarter (now 95% funded with more than 450 backers), brian d foy continued writing his Quick Tips every day:

Of course, it’s not too late yet to back his Kickstarter and become part of this unique endeavour!

Core Developments

Other Blog Posts

Ecosystem Additions

Winding Down

A tiresome week for yours truly. But that won’t stop anybody from making the coming week another good week for Perl 6 and even more tiring for yours truly. And that’s a good thing 🙂 So check in again next week for more Perl 6 news!


Perl 6 Advent Calendar: Day 5 – How to use the docs

Published by gfldex on 2016-12-05T00:00:14

…or why (nearly) everything is an object.

Spread out over all the pages of the official documentation of Perl 6, the class Signature is linked to more then 40 times. That shows not only that signatures are everywhere but also demonstrates a peculiarity of Perl 6 that will become more important as the language matures. No really, we are not done yet.

But first let’s have a look at some code.

multi sub trait_mod:<is> (Sub $s, :$foo!) is foo {
    say 'is foo called'
}
sub bar {}
&trait_mod:(&bar, :foo);

Here we define a trait that happens to be of type Sub which Rakudo (re)defines in Sub.pm. So there is actually a class for this build-in type. In fact, there are classes for anything besides classes and grammars. Having a Class for class would be a bit circular and prevent a slang to define its own object system. That you can do with Metamodel::ClassHOW, which is the Class behind class. But back to the trait.

A trait is somewhat macroish in nature as it is applied at compile time to some object its signature refers to. That allows the MMD to pick the candidate defined above when we use it with is foo. (There are a whopping 91 candidates of is defined in Rakudo.) Since it’s called at compile time it has to be called with something that exists at that time. All those classes for Sub, Label and friends provide a nice target for such a call. And yes, you can apply a trait to a label if you call it the right way in a BEGIN phaser. Combined with the power of compile time mixins and the the mighty .wrap you can go wild and improve the tool that is most dear to you — the Perl 6 compiler. If you observed the example carefully you likely spotted that the trait is applied to itself. If you really want to you could have infinite recursion at compile time.

Perl 6 is a dynamic dynamic language. The programs you write are dynamic and you can mend them and bend them to your will, both at compile- and runtime. And so you can do with the compiler. And that leads us to how to use the docs. Since language features are represented as a class, we link heavily to those classes to provide detailed discussions and you are encouraged to follow those links before you continue with the main paragraph the link refers from.

Macros will make good use of all those objects. With any luck next year will show us how.


Perlgeek.de: Perl 6 By Example: Formatting a Sudoku Puzzle

Published by Moritz Lenz on 2016-12-03T23:00:01

This blog post is part of my ongoing project to write a book about Perl 6.

If you're interested, please sign up for the mailing list at the bottom of the article, or here. It will be low volume (less than an email per month, on average).


As a gentle introduction to Perl 6, let's consider a small task that I recently encountered while pursuing one of my hobbies.

Sudoku is a number-placement puzzle played on a grid of 9x9 cells, subdivided into blocks of 3x3. Some of the cells are filled out with numbers from 1 to 9, some are empty. The objective of the game is to fill out the empty cells so that in each row, column and 3x3 block, each digit from 1 to 9 occurs exactly once.

An efficient storage format for a Sudoku is simply a string of 81 characters, with 0 for empty cells and the digits 1 to 9 for pre-filled cells. The task I want to solve is to bring this into a friendlier format.

The input could be:

000000075000080094000500600010000200000900057006003040001000023080000006063240000

On to our first Perl 6 program:

# file sudoku.p6
use v6;
my $sudoku = '000000075000080094000500600010000200000900057006003040001000023080000006063240000';
for 0..8 -> $line-number {
    say substr $sudoku, $line-number * 9, 9;
}

You can run it like this:

$ perl6 sudoku.p6
000000075
000080094
000500600
010000200
000900057
006003040
001000023
080000006
063240000

There's not much magic in there, but let's go through the code one line at a time.

The first line, starting with a # is a comment that extends to the end of the line.

use v6;

This line is not strictly necessary, but good practice anyway. It declares the Perl version you are using, here v6, so any version of the Perl 6 language. We could be more specific and say use v6.c; to require exactly the version discussed here. If you ever accidentally run a Perl 6 program through Perl 5, you'll be glad you included this line, because it'll tell you:

$ perl sudoku.p6
Perl v6.0.0 required--this is only v5.22.1, stopped at sudoku.p6 line 1.
BEGIN failed--compilation aborted at sudoku.p6 line 1.

instead of the much more cryptic

syntax error at sudoku.p6 line 4, near "for 0"
Execution of sudoku.p6 aborted due to compilation errors.

The first interesting line is

my $sudoku = '00000007500...';

my declares a lexical variable. It is visible from the point of the declaration to the end of the current scope, which means either to the end of the current block delimited by curly braces, or to the end of the file if it's outside any block. As it is in this example.

Variables start with a sigil, here a '$'. Sigils are what gave Perl the reputation of being line noise, but there is signal in the noise. The $ looks like an S, which stands for scalar. If you know some math, you know that a scalar is just a single value, as opposed to a vector or even a matrix.

The variable doesn't start its life empty, because there's an initialization right next to it. The value it starts with is a string literal, as indicated by the quotes.

Note that there is no need to declare the type of the variable beyond the very vague "it's a scalar" implied by the sigil. If we wanted, we could add a type constraint:

my Str $sudoku = '00000007500...';

But when quickly prototyping, I tend to forego type constraints, because I often don't know yet how exactly the code will work out.

The actual logic happens in the next lines, by iterating over the line numbers 0 to 8:

for 0..8 -> $line-number {
    ...
}

The for loop has the general structure for ITERABLE BLOCK. Here the iterable is a range, and the block is a pointy block. The block starts with ->, which introduces a signature. The signature tells the compiler what arguments the blocks expects, here a single scalar called $line-number.

Perl 6 allows to use a dash - or a single quote ' inside identifier, as long as there is a letter on both sides (to disambiguate it from subtraction).

Again, type constraints are optional. If you chose to include them, it would be for 0..9 -> Int $line-number { ... }.

$line-number is again a lexical variable, and visible inside the block that comes after the signature. Blocks are delimited by curly braces.

say substr $sudoku, $line-number * 9, 9;

Both say and substr are functions provided by the Perl 6 standard library. substr($string, $start, $chars) extracts a substring of (up to) $chars characters length from $string, starting from index $start. Oh, and indexes are zero-based in Perl 6.

say then prints this substring, followed by a line break.

As you can see from the example, function invocations don't need parenthesis, though you can add them if you want:

say substr($sudoku, $line-number * 9, 9);

or even

say(substr($sudoku, $line-number * 9, 9));

Making the Sudoku playable

As the output of our script stands now, you can't play the resulting Sudoku even if you printed it, because all those pesky zeros get in your way of actually entering the numbers you carefully deduce while solving the puzzle.

So, let's substitute each 0 with a blank:

# file sudoku.p6
use v6;

my $sudoku = '000000075000080094000500600010000200000900057006003040001000023080000006063240000';
$sudoku = $sudoku.trans('0' => ' ');

for 0..8 -> $line-number {
    say substr $sudoku, $line-number * 9, 9;
}

trans is a method of the Str class. Its argument is a Pair. The boring way to create a Pair would be Pair.new('0', ' '), but since it's so commonly used, there is a shortcut in the form of the fat arrow, =>. The method trans replaces each occurrence of they pair's key with the pair's value, and returns the resulting string.

Speaking of shortcuts, you can also shorten $sudoku = $sudoku.trans(...) to $sudoku.=trans(...). This is a general pattern that turns methods that return a result into mutators.

With the new string substitution, the result is playable, but ugly:

$ perl6 sudoku.p6
       75
    8  94
   5  6  
 1    2  
   9   57
  6  3 4 
  1    23
 8      6
 6324    

A bit ASCII art makes it bearable:

+---+---+---+
|   | 1 |   |
|   |   |79 |
| 9 |   | 4 |
+---+---+---+
|   |  4|  5|
|   |   | 2 |
|3  | 29|18 |
+---+---+---+
|  4| 87|2  |
|  7|  2|95 |
| 5 |  3|  8|
+---+---+---+

To get the vertical dividing lines, we need to sub-divide the lines into smaller chunks. And since we already have one occurrence of dividing a string into smaller strings of a fixed size, it's time to encapsulate it into a function:

sub chunks(Str $s, Int $chars) {
    gather for 0 .. $s.chars / $chars - 1 -> $idx {
        take substr($s, $idx * $chars, $chars);
    }
}

for chunks($sudoku, 9) -> $line {
    say chunks($line, 3).join('|');
}

The output is:

$ perl6 sudoku.p6
   |   | 75
   | 8 | 94
   |5  |6  
 1 |   |2  
   |9  | 57
  6|  3| 4 
  1|   | 23
 8 |   |  6
 63|24 |   

But how did it work? Well, sub (SIGNATURE) BLOCK declares a subroutine, short sub. Here I declare it to take two arguments, and since I tend to confuse the order of arguments to functions I call, I've added type constraints that make it very likely that Perl 6 catches the error for me.

gather and take work together to create a list. gather is the entry point, and each execution of take adds one element to the list. So

gather {
    take 1;
    take 2;
}

would return the list 1, 2. Here gather acts as a statement prefix, which means it collects all takes from within the for loop.

A subroutine returns the value from the last expression, which here is the gather for ... thing discussed above.

Coming back to the program, the for-loop now looks like this:

for chunks($sudoku, 9) -> $line {
    say chunks($line, 3).join('|');
}

So first the program chops up the full Sudoku string into lines of nine characters, and then for each line, again into a list of three strings of three characters length. The join method turns it back into a string, but with pipe symbols inserted between the chunks.

There are still vertical bars missing at the start and end of the line, which can easily be hard-coded by changing the last line:

    say '|', chunks($line, 3).join('|'), '|';

Now the output is

|   |   | 75|
|   | 8 | 94|
|   |5  |6  |
| 1 |   |2  |
|   |9  | 57|
|  6|  3| 4 |
|  1|   | 23|
| 8 |   |  6|
| 63|24 |   |

Only the horizontal lines are missing, which aren't too hard to add:

my $separator = '+---+---+---+';
my $index = 0;
for chunks($sudoku, 9) -> $line {
    if $index++ %% 3 {
        say $separator;
    }
    say '|', chunks($line, 3).join('|'), '|';
}
say $separator;

Et voila:

+---+---+---+
|   |   | 75|
|   | 8 | 94|
|   |5  |6  |
+---+---+---+
| 1 |   |2  |
|   |9  | 57|
|  6|  3| 4 |
+---+---+---+
|  1|   | 23|
| 8 |   |  6|
| 63|24 |   |
+---+---+---+

There are two new aspects here: the if conditional, which structurally very much resembles the for loop. The second new aspect is the divisibility operator, %%. From other programming languages you probably know % for modulo, but since $number % $divisor == 0 is such a common pattern, $number %% $divisor is Perl 6's shortcut for it.

Shortcuts, Constants, and more Shortcuts

Perl 6 is modeled after human languages, which have some kind of compression scheme built in, where commonly used words tend to be short, and common constructs have shortcuts.

As such, there are lots of ways to write the code more succinctly. The first is basically cheating, because the sub chunks can be replaced by a built-in method in the Str class, comb:

# file sudoku.p6
use v6;

my $sudoku = '000000075000080094000500600010000200000900057006003040001000023080000006063240000';
$sudoku = $sudoku.trans: '0' => ' ';

my $separator = '+---+---+---+';
my $index = 0;
for $sudoku.comb(9) -> $line {
    if $index++ %% 3 {
        say $separator;
    }
    say '|', $line.comb(3).join('|'), '|';
}
say $separator;

The if conditional can be applied as a statement postfix:

say $separator if $index++ %% 3;

Except for the initialization, the variable $index is used only once, so there's no need to give it name. Yes, Perl 6 has anonymous variables:

my $separator = '+---+---+---+';
for $sudoku.comb(9) -> $line {
    say $separator if $++ %% 3;
    say '|', $line.comb(3).join('|'), '|';
}
say $separator;

Since $separator is a constant, we can declare it as one:

`constant $separator = '+---+---+---+';

If you want to reduce the line noise factor, you can also forego the sigil, so constant separator = '...'.

Finally there is a another syntax for method calls with arguments: instead of $obj.method(args) you can say $obj.method: args, which brings us to the idiomatic form of the small Sudoku formatter:

# file sudoku.p6
use v6;

my $sudoku = '000000075000080094000500600010000200000900057006003040001000023080000006063240000';
$sudoku = $sudoku.trans: '0' => ' ';

constant separator = '+---+---+---+';
for $sudoku.comb(9) -> $line {
    say separator if $++ %% 3;
    say '|', $line.comb(3).join('|'), '|';
}
say separator;

IO and other Tragedies

A practical script doesn't contain its input as a hard-coded string literal, but reads it from the command line, standard input or a file.

If you want to read the Sudoku from the command line, you can declare a subroutine called MAIN, which gets all command line arguments passed in:

# file sudoku.p6
use v6;

constant separator = '+---+---+---+';

sub MAIN($sudoku) {
    my $substituted = $sudoku.trans: '0' => ' ';

    for $substituted.comb(9) -> $line {
        say separator if $++ %% 3;
        say '|', $line.comb(3).join('|'), '|';
    }
    say separator;
}

This is how it's called:

$ perl6-m sudoku-format-08.p6 000000075000080094000500600010000200000900057006003040001000023080000006063240000
+---+---+---+
|   |   | 75|
|   | 8 | 94|
|   |5  |6  |
+---+---+---+
| 1 |   |2  |
|   |9  | 57|
|  6|  3| 4 |
+---+---+---+
|  1|   | 23|
| 8 |   |  6|
| 63|24 |   |
+---+---+---+

And you even get a usage message for free if you use it wrongly, for example by omitting the argument:

$ perl6-m sudoku.p6 
Usage:
  sudoku.p6 <sudoku> 

You might have noticed that the last example uses a separate variable for the substituted Sudoku string.This is because function parameters (aka variables declared in a signature) are read-only by default. Instead of creating a new variable, I could have also written sub MAIN($sudoku is copy) { ... }.

Classic UNIX programs such as cat and wc, follow the convention of reading their input from file names given on the command line, or from the standard input if no file names are given on the command line.

If you want your program to follow this convention, lines() provides a stream of lines from either of these source:

# file sudoku.p6
use v6;

constant separator = '+---+---+---+';

for lines() -> $sudoku {
    my $substituted = $sudoku.trans: '0' => ' ';

    for $substituted.comb(9) -> $line {
        say separator if $++ %% 3;
        say '|', $line.comb(3).join('|'), '|';
    }
    say separator;
}

Get Creative!

You won't learn a programming language from reading a blog, you have to actually use it, tinker with it. If you want to expand on the examples discussed earlier, I'd encourage you to try to produce Sudokus in different output formats.

SVG offers a good ratio of result to effort. This is the rough skeleton of an SVG file for a Sudoku:

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="304" height="304" version="1.1"
xmlns="http://www.w3.org/2000/svg">
    <line x1="0" x2="300" y1="33.3333" y2="33.3333" style="stroke:grey" />
    <line x1="0" x2="300" y1="66.6667" y2="66.6667" style="stroke:grey" />
    <line x1="0" x2="303" y1="100" y2="100" style="stroke:black;stroke-width:2" />
    <line x1="0" x2="300" y1="133.333" y2="133.333" style="stroke:grey" />
    <!-- more horizontal lines here -->

    <line y1="0" y2="300" x1="33.3333" x2="33.3333" style="stroke:grey" />
    <!-- more vertical lines here -->


    <text x="43.7333" y="124.5"> 1 </text>
    <text x="43.7333" y="257.833"> 8 </text>
    <!-- more cells go here -->
    <rect width="304" height="304" style="fill:none;stroke-width:1;stroke:black;stroke-width:6"/>
</svg>

If you have a Firefox or Chrome browser, you can use it to open the SVG file.

If you are adventurous, you could also write a Perl 6 program that renders the Sudoku as a Postscript (PS) or Embedded Postscript document. It's also a text-based format.

Subscribe to the Perl 6 book mailing list

* indicates required

6guts: Taking a couple of steps backwards to fix a GC bug

Published by jnthnwrthngtn on 2016-11-30T23:16:42

When I popped up with a post here on Perl 6 OO a few days ago, somebody noted in the comments that they missed my write-ups of my bug hunting and fixing work in Rakudo and MoarVM. The good news is that the absence of posts doesn’t mean an absence of progress; I’ve fixed dozens of things over the last months. It was rather something between writers block and simply not having the energy, after a day of fixing things, to write about it too. Anyway, it seems I’ve got at least some of my desire to write back, so here goes. (Oh, and I’ll try and find a moment in the coming days to reply to the other comments people wrote on my OO post too.)

Understanding a cryptic error

There are a number of ways MoarVM can come tumbling down when memory gets corrupted. Some cases show up as segmentation faults. In other cases, the VM comes across something that simply does make any kind of sense and can infer that memory has become corrupted. Two panics commonly associated with this are “zeroed target thread ID in work pass” and “invalid thread ID XXX in GC work pass”, where XXX tends to be a sizable integer. At the start of a garbage collection – where we free up memory associated with dead objects – we do something like this:

  1. Go through all the threads that have been started, and signal those that are not blocked (e.g. waiting for I/O, a lock acquisition, or for native code to finish) to come and participate in the garbage collection run.
  2. Assign each non-blocked thread itself to work on.
  3. Assign each blocked thread’s work to a non-blocked thread.

So, every thread – blocked or not – ends up assigned to a running thread to take care of its collection work. It’s the participation of multiple threads that makes the MoarVM GC parallel (which is a different thing to having a concurrent GC; MoarVM’s GC can barely claim to be that).

The next important thing to know is that the every object, at creation, is marked with the ID of the thread that allocated it. This means that, as we perform GC, we know whether the object under consideration “belongs” to the current thread we’re doing GC work for, or some other one. In the case that the ID in the object header doesn’t match up with the thread ID we’re doing GC work for, then we stick it into a list of work to pass off to the thread that is responsible. To avoid synchronization overhead, we pass then off in batches (so there’s only synchronization overhead per batch). This is far from the only way to do parallel GC (other schemes include racing to write forwarding pointers), but it keeps the communication between participating threads down and leaves little surface area for data races in the GC.

The funny thing is that if none of that really made any sense to you, it doesn’t actually matter at all, because I only told you about it all so you’d have a clue what the “work pass” in the error message means – and even that doesn’t matter much for understanding the bug I’ll eventually get around to discussing. Anyway, TL;DR version (except you did just read it all, hah!) is that if the owner ID in an object header is either zero or an out-of-range thread ID, then we can be pretty sure there’s memory corruption afoot. The pointer under consideration is either to zeroed memory, or to somewhere in memory that does not correspond to an object header.

So, let’s debug the panic!

Getting the panic is, perhaps, marginally better than a segmentation fault. I mean, sure, I’m a bit less embarrassed when Moar panics than SEGVs, and perhaps it’s mildly less terrifying for users too. But at the end of the day, it’s not much better from a debugging perspective. At the point we spot the memory corruption, we have…a pointer. That points somewhere wrong. And, this being the GC, it just came off the worklist, which is full of a ton of pointers.

If only we could know where the pointer came from, I hear you think. Well, it turns out we can: we just need to detect the problem some steps back, where the pointer is added to the worklist. In src/gc/debug.h there’s this:

#define MVM_GC_DEBUG 0

Flip that to a 1, recompile, and magic happens. Here’s a rather cut down snippet from in worklist.h:

#if MVM_GC_DEBUG
#define MVM_gc_worklist_add(tc, worklist, item) \
    do { \
        MVMCollectable **item_to_add = (MVMCollectable **)(item); \
        if (*item_to_add) { \
            if ((*item_to_add)->owner == 0) \
                MVM_panic(1, "Zeroed owner in item added to GC worklist"); \
                /* Various other checks here.... */ 
        } \
        if (worklist->items == worklist->alloc) \
            MVM_gc_worklist_add_slow(tc, worklist, item_to_add); \
        else \
            worklist->list[worklist->items++] = item_to_add; \
    } while (0)
#else
#define MVM_gc_worklist_add(tc, worklist, item) \
    do { \
        MVMCollectable **item_to_add = (MVMCollectable **)(item); \
        if (worklist->items == worklist->alloc) \
            MVM_gc_worklist_add_slow(tc, worklist, item_to_add); \
        else \
            worklist->list[worklist->items++] = item_to_add; \
    } while (0)
#endif

So, in the debug version of the macro, we do some extra checks – including the one to detect a zeroed owner. This means that when MoarVM panics, the GC code that is placing the bad pointer into the list is on the stack. Then it’s a case of using GDB (or your favorite debugger), sticking a breakpoint on MVM_panic (spelled break MVM_panic in GDB), running the code that explodes, and then typing where. In this case, I was pointed at the last line of this bit of code from roots.c:

void MVM_gc_root_add_frame_roots_to_worklist(MVMThreadContext *tc, MVMGCWorklist *worklist,
                                             MVMFrame *cur_frame) {
    /* Add caller to worklist if it's heap-allocated. */
    if (cur_frame->caller && !MVM_FRAME_IS_ON_CALLSTACK(tc, cur_frame->caller))
        MVM_gc_worklist_add(tc, worklist, &cur_frame->caller);

    /* Add outer, code_ref and static info to work list. */
    MVM_gc_worklist_add(tc, worklist, &cur_frame->outer);

So, this tells me that the bad pointer is to an outer. The outer pointer of a call frame points to the enclosing lexical scope, which is how closures work. This provides a bit of inspiration for bug hunting; for example, it would now make sense to consider codepaths that assign outer to see if they could ever fail to keep a pointer up to date. The trouble is, for such an incredibly common language feature to be broken in that way, we’d be seeing it everywhere. It didn’t fit the pattern. In fact, both my private $dayjob application that was afflicted with this, together with the whateverable set of IRC bots, had in common that they did a bunch of concurrency work and both spawned quite a lot of subprocesses using Proc::Async.

But where does the pointer point to?

Sometimes I look at a pointer and it’s obviously totally bogus (a small integer usually suggests this). But this one looked feasible; it was relatively similar to the addresses of other valid pointers. But where exactly does it point to?

There are only a few places that a GC-managed object can live. They are:

So, it would be very interesting to know if the pointer was into one of those. Now, I could just go examining it in the debugger, but with a dozen running threads, that’s tedious as heck. Laziness is of course one of the virtues of a programmer, so I wrote a function to do the search for me. Another re-compile, reproducing the bug in GDB again, and then calling that routine from the debugger told me that the pointer was into the tospace of another thread.

Unfortunately, thinking is now required

Things get just a tad mind-bending here. Normally, when a program is running, if we see a pointer into fromspace we know we’re in big trouble. It means that the pointer points to where an object used to be, but was then moved into either tospace or the old generation. But when we’re in the middle of a GC run, the two spaces are flipped. The old tospace is now fromspace, the old fromspace becomes the new tospace, and we start evacuating living objects in to it. The space left at the end will then be zeroed later.

I should mention at this point that the crash only showed up a fraction of the time in my application. The vast majority of the time, it ran just fine. The odd time, however, it would panic – usually over a zeroed thread owner, but sometimes over a junk value being in the thread owner too. This all comes down to timing: different thread are working on GC, in different runs of the program they make progress at different paces, or get head starts, or whatever, and so whether the zeroing of the unused part of tospace happened or not yet will vary.

But wait…why didn’t it catch the problem even sooner?

When the MVM_GC_DEBUG flag is turned on, it introduces quite a few different sanity checks. One of them is in MVM_ASSIGN_REF, which happens whenever we assign a reference to one object into another. (The reason we don’t simply use the C assignment operator for that is because the inter-generational write barrier is needed.) Here’s how it looks:

#if MVM_GC_DEBUG
#define MVM_ASSIGN_REF(tc, update_root, update_addr, referenced) \
    { \
        void *_r = referenced; \
        if (_r && ((MVMCollectable *)_r)->owner == 0) \
            MVM_panic(1, "Invalid assignment (maybe of heap frame to stack frame?)"); \
        MVM_ASSERT_NOT_FROMSPACE(tc, _r); \
        MVM_gc_write_barrier(tc, update_root, (MVMCollectable *)_r); \
        update_addr = _r; \
    }
#else
#define MVM_ASSIGN_REF(tc, update_root, update_addr, referenced) \
    { \
        void *_r = referenced; \
        MVM_gc_write_barrier(tc, update_root, (MVMCollectable *)_r); \
        update_addr = _r; \
    }
#endif

Once again, the debug version does some extra checks. Those reading carefully will have spotted MVM_ASSERT_NOT_FROMSPACE in there. So, if we used this macro to assign to the ->outer that had the outdated pointer, why did it not trip this check?

It turns out, because it only cared about checking if it was in fromspace of the current thread, not all threads. (This is in turn because the GC debug bits only really get any love when I’m hunting a GC bug, and once I find it then they go back in the drawer until next time around.) So, I enriched that check and…the bug hunt came to a swift end.

Right back to the naughty deed

The next time I caught it under the debugger was not at the point that the bad ->outer assignment took place. It was even earlier than that – lo and behold, inside of some of the guts that power Proc::Async. Once I got there, the problem was clear and fixed in a minute. The problem was that the callback pointer was not rooted while an allocation took place. The function MVM_repr_alloc_init can trigger GC, which can move the object pointed to by callback. Without an MVMROOT to tell the GC where the callback pointer is so it can be updated, it’s left pointing to where the callback used to be.

So, bug fixed, but you may still be wondering how exactly this bug could have led to a bad ->outer pointer in a callframe some way down the line. Well, callback is a code object, and code objects point to an outer scope (it’s actually code objects that we clone to make closures). Since we held on to an outdated code object pointer, it in turn would point to an outdated pointer to the outer frame it closed over. When we invoked callback, the outer from the code object would be copied to be the outer of the call frame. Bingo.

Less is Moar

The hard part about GCs is not just building the collector itself. It’s that collectors bring invariants that are to be upheld, and a momentary lapse in concentration by somebody writing or reviewing a patch can let a bug like this slip through. At least 95% of the time when I handwavily say, “it was a GC bug”, what I really mean was “it was a bug that arose because some code didn’t play by the rules the GC requires”. A comparatively tiny fraction of the time, there’s actually something wrong in the code living under src/gc/.

People sometimes ask me about my plans for the future of MoarVM. I often tell them that I plan for there to be less of it. In this case, the code with the bug is something that I hope we’ll eventually write in, say, NQP, where we don’t have to worry about low-level details like getting write barriers correct. It’s just binding code to libuv, a C library, and we should be able to do that using the MoarVM native calling support (which is likely mature enough by now). Alas, that also has its own set of costs, and I suspect we’d need to improve native calling performance to not come out at a measurable loss, and that means teaching the JIT to emit native calls, but we only JIT on x64 so far. “You’re in a maze of twisty VM design trade-offs, and their funny smells are all alike.”


Weekly changes in and around Perl 6: 2016.48 Kickstarting Along

Published by liztormato on 2016-11-28T22:37:14

brian d foy‘s Learning Perl 6 Kickstarter is coming along nicely at 78% funded with about 350 backers so far. But we’re not there yet! brian really wants to get to 2000 backers, even if they only pledge 1$. So if you haven’t pledged yet, please show your support by pledging at least that!

Meanwhile, he has quite a bit of an advent going on himself:

Quick Tips #1, #2 and #3 were already mentioned last week.

Meanwhile, Moritz Lenz‘s Perl 6 By Example project can also use your support. You can support this effort by subscribing to the mailing list and telling him how much you would want to pay for his book!

New Rakudo Star Release

Steve Mynott brought us Rakudo Star 2016.11. If you’re a Rakudo Star user, you should definitely look into this release, as it may be a lot faster for your particular application.

White Camel Awards

It’s that time of the year again. Please cast your votes for the White Camel Awards! With the White Camel Award, we recognize significant non-technical achievement in Perl and its community, the people who keep the Perl community going and deserve to be recognized!

Gem From The Past

Someone mentioned a transcript of the Larry Wall presentation Present Continuous, Future Perfect at the OSDC::Israel::2006 conference. It’s quite a read, but if you really want to get an idea of how Rakudo Perl 6 got to be the way it is today, it’s worth your time!

Core Developments

Other Blog Posts

Ecosystem Additions

Winding Down

Next week’s Perl 6 Weekly may be delayed a bit because yours truly will be decommuting from the (free) London Perl Workshop 2016. Which incidentally has the following Perl 6 related presentations:

Hope to see you there! And check in again here next week for more Perl 6 news.


rakudo.org: Announce: Rakudo Star Release 2016.11

Published by Steve Mynott on 2016-11-27T18:51:38

On behalf of the Rakudo and Perl 6 development teams, I’m pleased to
announce the November 2016 release of “Rakudo Star”, a useful and usable
production distribution of Perl 6. The tarball for the November 2016 release
is available from http://rakudo.org/downloads/star/.

This is the fifth post-Christmas (production) release of Rakudo Star and
implements Perl v6.c. It comes with support for the MoarVM backend (all
module tests pass on supported platforms).

Please note that this release of Rakudo Star is not fully functional with
the JVM backend from the Rakudo compiler. Please use the MoarVM backend
only.

In the Perl 6 world, we make a distinction between the language (“Perl
6”) and specific implementations of the language such as “Rakudo Perl”.
This Star release includes release 2016.11 of the Rakudo Perl 6 compiler,
version 2016.11 of MoarVM, plus various modules, documentation, and
other resources collected from the Perl 6 community.

The changes in this release are outlined below:

New in 2016.11:

Fixes:
+ Various improvements to warning/error-reporting
+ Fixed assigning values to shaped arrays through iterators [839c762]
+ Fixed Str.Int not failing on numerics with combining characters [d540fc8]
+ [JVM] Fixed <a b c>.antipairs breakage [dd7b055]
+ defined routine now correctly authothreads with Junctions [189cb23]
+ Fixed poor randomness when .pick()ing on ranges with >32-bit numbers [34e515d]
+ Fixed infix:<x> silencing Failures [2dd0ddb]
+ Fixed edge case in is-approx that triggers DivByZero exception [f7770ed]
+ (Windows) Fixed returning of an error even when succeeding in mkdir [208a4c2]
+ (Windows) Fixed precomp unable to rename a newly compiled file [44a4c75]
+ (Test.pm) Fixed indent of multi-line diag() and test failure messages [43dbc96]
+ Fixed a callframe crash due to boxing of NULL filenames [200364a]
+ ∞ ≅ ∞ now gives True [4f3681b]
+ Fixed oversharing with grammars used by multiple threads [7a456ff]
+ Fixed incorrect calculations performed by acotan(num) [8e9fd0a]
+ Fixed incorrect calculations performed by asinh(num)/acosh(num) [a7e801f]
+ Fixed acosh return values for large negative numbers [5fe8cf7]
+ asinh(-∞) now returns -∞ instead of NaN [74d0e36]
+ atanh(1) now returns ∞ instead of throwing [906719c][66726e8]
+ Fixed missing close in IO::Path.slurp(:bin) [697a0ae]
+ :U QuantHashes now auto-vivify to their correct type and not Hash [79bb867]
+ Mix/MixHash.Bag/BagHash coersion now ignores negative weights [87bba04]
+ arity-0 infix:<Z> now returns a Seq instead of a List [3fdae43]
+ Fix augment of a nested package [87880ca]
+ Smartmatch with Regex variable now returns a Match instead of Bool [5ac593e]
+ Empty ()[0] now returns Nil instead of False [f50e39b]
+ Failed IO::Socket::Async connection no longer produces unexpected crash [f50e39b]
+ Quitting Supplies with no QUIT phasers no longer unexpectedly crash [f50e39b]
+ Fixed NativeCall issues on big endian machines [627a77e]
+ Fixed broken handling of $/ in some uses of `.match` [ba152bd]
+ Fixed Lock.protect not releasing the lock on control exceptions [48c2af6]
+ MoarVM now builds on any version of macOS [b4dfed2]
+ Fixed concurrency crashes due to garbage collection [6dc5074]
+ Fixed race condition in EmptyIterator [ed2631c]
+ Fixed hang with multi-threaded long-running NativeCall calls [f99d958]
+ Made my @a[10] = ^Inf work [aedb8e7]
+ Fixed [;]:delete [3b9c4c9]
+ Fixed incorrect handling of negative weights in ∪ operator [e10f767]
+ duckmap now preserves types of Iterables [43cb55f]
+ Fixed premature overflow to Inf with large Num literals [729d7e3]
+ Fixed race condition in NativeCall callsite used by multiple threads [49fd825]
+ Fixed instabilities in programs launching many threads at startup [0134132]
+ Fixed crash when reporting X::Composition::NotComposable or
X::Inheritance::Unsupported exceptions [a822bcf]
+ Fixed clock_gettime issue on macOS [ee8ae92]
+ Fixed SEGV in multi-threaded programs with strings-as-strands [395f369]
+ `regex` TOP Grammar rule will now backtrack if needed [4ccb2f3]
+ Fixed .rotate/.reverse on 1-dimmed arrays assigning to self [2d56751]
+ Fixed exponentiation involving zeros for Complex numbers [7f32243]
+ Fixed Label.gist [29db214][53d7b72]
+ Fixed certain edge cases of incorrect stringification of Rationals
with .Str, .perl, and .base [b5aa3c5]

Additions:
+ Added TWEAK submethod for object construction [fdc90a2][9409d68]
+ Added DateTime.hh-mm-ss [bf51eca]
+ Added parse-base routine [7e21a24]
+ is-approx with no explicit tolerances now uses more complex algorithm to
choose a tolerance to use (same as old is_approx) [82432a4]
+ on failure, is-approx now displays actual values received [b4fe680]
+ Added Iterator.skip-one to skip a single value [71a01e9]
+ Added Iterator.skip-at-least to skip several values [8d357af]
+ Re-imagined Str.match [b7201a8]:
+ the family of :nth is now lazy will return whatever can find
+ non-monotonically increasing :nth iterator values will now die
+ Str.match/subst/subst-mutate now have :as adverb [1b95636][c9a24d9][aaec517]
+ &infix: now works with Setty objects [d92e1ad]
+ :ov and :ex adverbs are now illegal in Str.subst [b90c741]
+ Made nextwith/samewith/nextsame/callwith to be real subroutines [70a367d]
+ Added CX::Emit and CX::Done control exceptions [07eeea8]
+ Setty.Mix/.MixHash coercers now use Int weights instead of Bool [7ba7eb4]
+ Implemented :kv,:p,:k,:v on 1-element multidim [;] [764cfcd]
+ .chrs can now also accepts codepoint numbers as Str [4ae3f23]
+ Added support for compilation of Rakudo on Solaris [a43b0c1]
+ IterationEnd.perl/gist/Str now returns text “IterationEnd” [59bb1b1]
+ Added X::Syntax::Number::InvalidCharacter exception [2faa55b]
+ .reverse/rotate on 1-dimmed arrays are now nodal [cd765e6]
+ .line and .file on core Code now references original source files [b068e3a]
+ .rethrow now works on unthrown exceptions [58a4826]
+ All Reals now accept `Whatever` as the second argument to .base() [c1d2599]
+ sub MAIN usage message shows possible Enum values if param is
named and is an Enum [a3be654]

Efficiency:
+ Made slip(@a) about 1.2x faster [37d0e46]
+ Made initialization of 2+dimmed array 10x to 16x faster [dfb58d4]
+ Str.match is now about 5% faster [4fc17df]
+ Str.match with :nth feature is now about 2x faster [41e2572]
+ my @a = Str.match(…) is now about 5% faster [e472420]
+ Str.comb(Regex) is now about 7x faster [1794328]
+ Simple Str.subst/subst-mutate is now about 30% faster [364e67b]
+ Match.Str|prematch|postmatch is now about 2x faster [e65d931]
+ Match.Bool is now about 1% faster (not much, but used a lot) [1fce095]
+ Made ~~ /foo/ faster: 2% for successful/6% for failed matches [05b65d0]
+ Made <foo bar baz> ~~ /foo/ about 2x faster [e4dc8b6]
+ Made %h ~~ /foo/ about 2x faster [33eeb32]
+ Frequent accesses of multiple adverbs (e.g. %h<a>:p:exists)
is now 2x faster [f22f894]
+ Made infix: faster: Str: 14x, type: 10x, Range: 3.5x,
Int|Seq|Hash: 1.5x, Array: 1.2x [bc7fcc6]
+ IO::Spec::Unix.canonpath is now 7x to 50x faster [f3f00fb]
+ Baggy.roll/pick is now about 10% faster [fc47bbf]
+ Made copying shaped arrays 10x to 20x faster [a1d8e93][0cf7b36][d27ecfa]
+ Made setting up a shaped array 2x as fast [f06e4c3]
+ Made creation of typed shaped arrays 15% faster [f5bf6c1]
+ Made 2d/3d array accesses about 7x as fast [d3a0907]
+ Made AT-POS on 1,2,3dim arrays about 20x faster [feb7bcb]
+ Made creating a shaped array about 50% faster [1293188][576f3a1]
+ Made .AT-POS on 3+ dimmed arrays 20% faster [1bb5aad]
+ Made over-indexed .AT-POS on 1,2,3 dimmed arrays about 10% faster [1bb5aad]
+ Made multi-dimmed ASSIGN-POS about 30% faster [5b2bdeb]
+ Made .ASSIGN-POS for 1,2,3dimmed arrays about 40x faster [050cf72]
+ Made n-dimmed .EXISTS-POS about 1.5x faster [006f008]
+ Made .EXISTS-POS for 1,2,3dimmed arrays about 10x faster [b1c41b7]
+ Made n-dimmed DELETE-POS about 1.3x faster [6ccecb1]
+ Made .DELETE-POS for 1,2,3dimmed arrays about 20x faster [55b9e90]
+ Made n-dimmed BIND-POS about 1.3x faster [2827edb]
+ Made .BIND-POS for 1,2,3dimmed arrays about 20x faster [9f94525]
+ Made @a[10].STORE at least as fast as @a.STORE [8064ff1]
+ Made .kv on shaped Arrays about 4x faster [e42b68e]
+ Made .pairs/.antipairs on shaped Arrays about 2.8x faster [0f2566a][f608a33]
+ Made List.kv about 30% faster [7a2baf4]
+ for loops on 1-dimmed arrays are now 3x faster [ed36e60]
+ .kv on 1-dimmed arrays is now 7x faster [608de26]
+ .pairs/.antipairs on 1-dimmed arrays is now 3x faster [b7d9537][1c425f9]
+ postcircumfix[;] on 2/3 dimmed arrays is now 9x faster [0b97362]
+ Assignment to [;] for 2/3 dimmed arrays is now 10x faster [ce85ba3]
+ [;]:exists for 2/3 dimmed arrays is now 7x faster [e3e3fef]
+ [;]:delete for 2/3 dimmed arrays is now 10x faster [3b9c4c9]
+ [;] := foo for 2/3 dimmed arrays is now 10x faster [eaf4132]
+ .iterator and .values on shaped arrays are now about 4x faster [736ab11]
+ Fixed optimization of shaped arrays that gives 10% gain on simple `for`
loops and likely will give larger gains on bigger programs [b7e632e]
+ Made starting MappyIterator faster, affecting all Hash/Map/Baggy iterator
methods. 2-elem Hash iteration is 1.6x faster [97fb6c2]
+ Made starting a grepper faster: .grep on with no adverbs on 2-element list
is now 20% faster [077c8f0]
+ Made Date/DateTime creation 20% faster [0e7f480]
+ Hashes now use 4 (32-bit) or 8 (64-bit) bytes less memory per stored item [395f369]
+ Rational.Str is now about 40% faster [b5aa3c5]
+ Rational.base is now about 30% faster [b5aa3c5]
+ Various streamlining of code that’s hard to measure the final impact of

Notable changes in modules shipped with Rakudo Star:

+ DBIish: Prepare tests for lexical module loading and do not rely on your dependencies to load modules
+ Pod-To-HTML: Bump version and use a separate element as anchor for “to top” links
+ Terminal-ANSIColor: Update Pod documentation and support 256-color and 24-bit RGB modes
+ doc: Large number of changes – too many to detail here
+ json_fast: Speed gains
+ panda: Explicitly use Panda::Project as we use it in class Panda
+ perl6-lwp-simple: Change to http.perl6.org since the main site is going https and add NO_NETWORK_TESTING

There are some key features of Perl 6 that Rakudo Star does not yet
handle appropriately, although they will appear in upcoming releases.
Some of the not-quite-there features include:

* advanced macros
* non-blocking I/O (in progress)
* some bits of Synopsis 9 and 11

There is an online resource at http://perl6.org/compilers/features
that lists the known implemented and missing features of Rakudo’s
backends and other Perl 6 implementations.

In many places we’ve tried to make Rakudo smart enough to inform the
programmer that a given feature isn’t implemented, but there are many
that we’ve missed. Bug reports about missing and broken features are
welcomed at rakudobug@perl.org.

See http://perl6.org/ for links to much more information about
Perl 6, including documentation, example code, tutorials, presentations,
reference materials, design documents, and other supporting resources.
Some Perl 6 tutorials are available under the “docs” directory in
the release tarball.

The development team thanks all of the contributors and sponsors for
making Rakudo Star possible. If you would like to contribute, see
http://rakudo.org/how-to-help, ask on the perl6-compiler@perl.org
mailing list, or join us on IRC #perl6 on freenode.

Perlgeek.de: Perl 6 By Example: Running Rakudo

Published by Moritz Lenz on 2016-11-26T23:00:01

This blog post is part of my ongoing project to write a book about Perl 6.

If you're interested, please sign up for the mailing list at the bottom of the article, or here. It will be low volume (less than an email per month, on average).


Before we start exploring Perl 6, you should have an environment where you can run Perl 6 code. So you need to install Rakudo Perl 6, currently the only actively developed Perl 6 compiler. Or even better, install Rakudo Star, which is a distribution that includes Rakudo itself, a few useful modules, and an installer that can help you install more modules.

Below a few options for getting Rakudo Star installed are discussed. Chose whatever works for you.

The examples here use Rakudo Star 2016.10.

Installers

You can download installers from http://rakudo.org/downloads/star/ for Mac OS (.dmg) and Windows (.msi). After download, you can launch them, and they walk you through the installation process.

Note that Rakudo is not relocatable, which means you have to install to a fix location that was decided by the creator of the installer. Moving the installation to a different directory.

On Windows, the installer offers you need to add C:\rakudo\bin and C:\rakudo\share\perl6\site\bin to your PATH environment. You should chose that option, as it allows you to call rakudo (and programs that the module installer installs on your behalf) without specifying full paths.

Docker

On platforms that support Docker, you can pull an existing Docker container from the docker hub:

$ docker pull mj41/perl6-star

Then you can get an interactive Rakudo shell with this command:

$ docker run -it mj41/perl6-star perl6

But that won't work for executing scripts, because the container has its own, separate file system. To make scripts available inside the container, you need to tell Docker to make the current directory available to the container:

$ docker run -v $PWD:/perl6 -w /perl6 -it mj41/perl6-star perl6

The option -v $PWD:/perl6 instructs Docker to mount the current working directory ($PWD) into the container, where it'll be available as /perl6. To make relative paths work, -w /perl6 instructs Docker to set the working directory of the rakudo process to /perl6.

Since this command line starts to get unwieldy, I created an alias (this is Bash syntax; other shells might have slightly different alias mechanisms):

alias p6d='docker run -v $PWD:/perl6 -w /perl6 -it mj41/perl6-star perl6'

I put this line into my ~/.bashrc files, so new bash instances have a p6d command, short for "Perl 6 docker".

As a short test to see if it works, you can run

$ p6d -e 'say "hi"'
hi

If you go the Docker route, just the p6d alias instead of perl6 to run scripts.

Building from Source

To build Rakudo Star from source, you need make, gcc or clang and perl 5 installed. This example installs into $HOME/opt/rakudo-star:

$ wget http://rakudo.org/downloads/star/rakudo-star-2016.10.tar.gz
$ tar xzf rakudo-star-2016.10.tar.gz
$ cd rakudo-star-2016.10/
$ perl Configure.pl --prefix=$HOME/opt/rakudo-star --gen-moar
$ make install

You should have about 2GB of RAM available for the last step; building a compiler is a resource intensive task.

You need to add paths to two directories to your PATH environment variable, one for Rakudo itself, one for programs installed by the module installer:

PATH=$PATH:$HOME/opt/rakudo-star/bin/:$HOME/opt/rakudo-star/share/perl6/site/bin

If you are a Bash user, you can put that line into your ~/.bashrc file to make it available in new Bash processes.

Testing your Rakudo Star Installation

You should now be able to run Perl 6 programs from the command line, and ask Rakudo for its version:

$ perl6 --version
This is Rakudo version 2016.10-2-gb744de3 built on MoarVM version 2016.09-39-g688796b
implementing Perl 6.c.

$ perl6 -e "say <hi>"
hi

If, against all odds, all of these approaches have failed you to produce a usable Rakudo installation, you should describe your problem to the friendly Perl 6 community, which can usually provide some help. http://perl6.org/community/ describes ways to interact with the community.

Next week we'll take a look at the first proper Perl 6 example, so stay tuned for updates!

Subscribe to the Perl 6 book mailing list

* indicates required

6guts: Perl 6 is biased towards mutators being really simple. That’s a good thing.

Published by jnthnwrthngtn on 2016-11-25T01:09:33

I’ve been meaning to write this post for a couple of years, but somehow never quite got around to it. Today, the topic of mutator methods came up again on the #perl6 IRC channel, and – at long last – conincided with me having the spare time to write this post. Finally!

At the heart of the matter is a seemingly simple question: why does Perl 6 not have something like the C# property syntax for writing complex setters? First of all, here are some answers that are either wrong or sub-optimal:

Back to OO basics

The reason the question doesn’t have a one-sentence answer is because it hinges on the nature of object orientation itself. Operationally, objects consist of:

If your eyes glazed over on the second bullet point, then I’m glad you’re reading. If I wasn’t trying to make a point, I’d have simply written “a mechanism for calling a method on an object”. So what is my point? Here’s a quote from Alan Kay, who coined the term “object oriented”:

I’m sorry that I long ago coined the term “objects” for this topic because it gets many people to focus on the lesser idea. The big idea is “messaging”…”

For years, I designed OO systems primarily thinking about what objects I’d have. In class-based languages, this really meant what classes I’d have. How did I figure that out? Well, by thinking about what fields go in which objects. Last of all, I’d write the methods.

Funnily enough, this looks very much like procedural design. How do I build a C program? By modeling the state into various structs, and then writing functions work with with those structs. Seen this way, OO looks a lot like procedural. Furthermore, since OO is often taught as “the next step up” after procedural styles of programming, this way of thinking about objects is extremely widespread.

It’s little surprise, then, that a lot of OO code in the wild might as well have been procedural code in the first place. Many so-called OO codebases are full of DTOs (“Data Transfer Objects”), which are just bundles of state. These are passed to classes with names like DogManager. And a manager is? Something that meddles with stuff – in this case, probably the Dog DTO.

Messaging thinking

This is a far cry from how OO was originally conceived: autonomous objects, with their own inner state, reacting to messages received from the outside world, and sending messages to other objects. This thinking can be found today. Of note, it’s alive and well in the actor model. These days, when people ask me how to get better at OO, one of my suggestions is that they take a look at actors.

Since I grasped that the messages are the important thing in OO, however, the way I design objects has changed dramatically. The first question I ask is: what are the behaviors? This in turn tells me what messages will be sent. I then consider the invariants – that is, rules that the behaviors must adhere to. Finally, by grouping invariants by the state they care about, I can identify the objects that will be involved, and thus classes. In this approach, the methods come first, and the state comes last, usually discovered as I TDD my way through implementing the methods.

Accessors should carry a health warning

An accessor method is a means to access, or mutate, the state held within a particular attribute of an object. This is something I believe we should do far more hesitantly than is common. Objects are intended to hide state behind a set of interesting operations. The moment the underlying state model is revealed to the outside world, our ability to refactor is diminished. The world outside of our object couples to that view of it, and it becomes far too tempting to put operations that belong inside of the object on the outside. Note that a get-accessor is a unidirectional coupling, while a mutate-accessor implies a bidirectional (and so tighter) coupling.

But it’s not just refactoring that suffers. Mutable state is one of the things that makes programs difficult to understand and reason about. Functional programming suggests abstinence. OO suggests you just stick to a pint or two, so your side-effects will be at least somewhat less obnoxious. It does this by having objects present a nice message-y view to the outside world, and keeping mutation of state locked up inside of objects. Ideas such as value objects and immutable objects take things a step further. These have objects build new objects that incorporate changes, as opposed to mutating objects in place. Perl 6 encourages these in various ways (notice how clone lets you tweak data in the resulting object, for example).

Furthermore, Perl 6 supports concurrent and parallel programming. Value objects and immutable objects are a great fit for that. But what about objects that have to mutate their state? This is where state leakage will really, really, end up hurting. Using OO::Monitors or OO::Actors, turning an existing class into a monitor (method calls are synchronous but enforce mutual exclusion) or an actor (method calls are asynchronous and performed one at a time on a given object) is – in theory – easy. It’s only that easy, however, if the object does not leak its state, and if all complex operations on the object are expressed as a single method. Contrast:

unless $seat.passenger {
    $seat.passenger = $passenger;
}

With:

$seat.assign-to($passenger);

Where the method does:

method assign-to($passenger) {
    die "Seat already taken!" if $!passenger;
    $!passenger = $passenger;
}

Making the class of which $seat is an instance into a monitor won’t do a jot of good in the accessor/mutator case; there’s still a gaping data race. With the second approach, we’d be safe.

So if mutate accessors are so bad, why does Perl 6 have them at all?

To me, the best use of is rw on attribute accessors is for procedural programming. They make it easy to create mutable record types. I’d also like to be absolutely clear that there’s no shame in procedural programming. Good OO design is hard. There’s a reason Perl 6 has sub and method, rather than calling everything a method and then coining the term static method, because subroutine sounds procedural and “that was the past”. It’s OK to write procedural code. I’d choose to deal with well organized procedural code over sort-of-but-not-really-OO code any day. OO badly used tends to put the moving parts further from each other, rather than encapsulating them.

Put another way, class is there to serve more than one purpose. As in many languages, it doubles up as the thing used for doing real OO programming, and a way to define a record type.

So what to do instead of a fancy mutator?

Write methods for semantically interesting operations that just happen to set an attribute among their various other side-effects. Give the methods appropriate and informative names so the consumer of the class knows what they will do. And please do not try to hide complex operations, potentially with side-effects like I/O, behind something that looks like an assignment. This:

$analyzer.file = 'foo.csv';

Will lead most readers of the code to think they’re simply setting a property. The = is the assignment operator. In Perl 6, we make + always mean numeric addition, and pick ~ to always mean string concatenation. It’s a language design principle that operators should have predictable semantics, because in a dynamic language you don’t statically know the types of the operands. This kind of predictability is valuable. In a sense, languages that make it easy to provide custom mutator behavior are essentially making it easy to overload the assignment operator with additional behaviors. (And no, I’m not saying that’s always wrong, simply that it’s inconsistent with how we view operators in Perl 6.)

By the way, this is also the reason Perl 6 allows definition of custom operators. It’s not because we thought building a mutable parser would be fun (I mean, it was, but in a pretty masochistic way). It’s to discourage operators from being overloaded with unrelated and surprising meanings.

And when to use Proxy?

When you really do just want more control over something that behaves like an assignment. A language binding for a C library that has a bunch of get/set functions to work with various members of a struct would be a good example.

In summary…

Language design is difficult, and involves making all manner of choices where there is no universally right or wrong answer, but just trade-offs. The aim is to make choices that form a consistent whole – which is far, far, easier said than done becuase there’s usually a dozen different ways to be consistent too. The choice to dehuffmanize (that is, make longer) the writing of complex mutators is because it:


Weekly changes in and around Perl 6: 2016.47 Perl 6 入门

Published by liztormato on 2016-11-21T21:49:54

Yes, Naoum Hankache‘s perl6intro.com has been translated to Chinese by ohmycloud and wenjie1991. I guess that adds about 1 billion people being able to start learning Perl 6 in their native language. I can’t help but think: Hindi anybody?🙂

Releases

Last weekend saw the release of Rakudo 2016.11. If you’re too lazy to compile the source, you can also download Claudio RamirezCentOS and Ubuntu packages. Since the problems that plagued the installation of Rakudo Star 2016.10 on Windows have been fixed, it is now possible again to make a full release of Rakudo Star. Which Steve Mynott started working on only moments after the compiler release was cut by Zoffix Znet. This has resulted in a Rakudo Star 2016.11 Release Candidate. Please check it out! A lot of things should have gotten significantly faster since the last fully functional Rakudo Star release (2016.07).

Dates For The Perl Conferences

Next year will see at least two Perl conferences: The Perl Conference NA on 18-23 June 2017 at the United States Patent and Trademark Office in Alexandria, Virginia. Which is very close to Washington, DC, so plenty of things to see there! Later that year will see The Perl Conference in Amsterdam on 9-11 August at B.Amsterdam in Amsterdam, The Netherlands. Plenty to see and do there as well! So mark these dates in your agendas! Please note that neither of these conferences are in any way affiliated with O’Reilly Media.

Advent Season

There are still slots available for the Perl 6 Advent Calendar! If you have something to tell about Perl 6, this is a nice place to do it with quite some exposure!

Books

This week saw a flurry of announcements about Perl 6 books and associated blog posts.

For those of you with your feet firmly in Perl 5 ground, you might want to check out brian d foy‘s Learning Perl 6 Kickstarter which already has more than 225 backers. A Perl 6 version of the bestselling Learning Perl, also published by O’Reilly. What is there not to like? If you/the company you work for/with supports this Kickstarter well enough, you will not only get a day of an on-site Perl 6 course given by brian, but also two days of Perl 5 courses! Reddit comments here and here.

Moritz Lenz announced Perl 6 By Example, in which he wants to recycle the approach taken in Using Perl 6 to introduce topics by example. It would not be a comprehensive guide to the Perl 6 language, but enough to get you started (Reddit comments).

And then there is Ken Youens-Clark‘s Metagenomics book in which all examples are written in Perl 6. And Laurent Rosenfeld‘s adaptation of Think Python, Think Perl 6 – How to Think Like a Computer Scientist, which is also in the works. All in all exciting news from the Perl 6 book front!

Core Developments

Blog Posts

Ecosystem Additions

Winding Down

Wow, it’s been a while since there was that much to tell about a week in Perl 6! I like where this is going! Check in again next week for more Perl 6 news!


Steve Mynott: Rakudo Star 2016.11 Release Candidate

Published by Steve Mynott on 2016-11-20T14:01:22

There is a Release Candidate for Rakudo Star 2016.11 (currently RC2) available at

http://pl6anet.org/drop/

This includes binary installers for Windows and Mac.

Usually Star is released about every three months but last month's release didn't include a Windows installer so there is another release.

I'm hoping to release the final version next weekend and would be grateful if people could try this out on as many systems as possible.

Any feedback email steve *dot* mynott *at* gmail *dot* com

Full draft announce at

https://github.com/rakudo/star/blob/master/docs/announce/2016.11.md

Perlgeek.de: What is Perl 6?

Published by Moritz Lenz on 2016-11-19T23:00:01

This blog post is part of my ongoing project to write a book about Perl 6.

If you're interested, please sign up for the mailing list at the bottom of the article, or here. It will be low volume (less than an email per month, on average).


Perl 6 is a programming language. It is designed to be easily learned, read and written by humans, and it is inspired by natural language. It allows the beginner to write in "baby Perl", while giving the experienced programmer freedom of expression, from concise to poetic.

Perl 6 is gradually typed. It mostly follows the paradigm of dynamically typed languages in that it accepts programs whose type safety it can't guarantee during compilation. Unlike many dynamic languages, it accepts and enforces type constraints. Where possible, the compiler uses type annotations to make decisions at compile time that would otherwise only be possible at run time.

Many programming paradigms have influenced Perl 6. You can write imperative, object-oriented and functional programs in Perl 6. Declarative programming is supported through the regex and grammar engine.

Most lookups in Perl 6 are lexical, and the language avoids global state. This makes parallel and concurrent execution of programs easier, as does Perl 6's focus on high-level concurrency primitives. Instead of threads and locks, you tend to think about promises and message queues when you don't want to be limited to one CPU core.

Perl 6 as a language is not opinionated about whether Perl 6 programs should be compiled or interpreted. Rakudo Perl 6, the main implementation, precompiles modules on the fly, and interprets scripts.

Perl 5, the Older Sister

Around the year 2000, Perl 5 development faced major strain from the conflicting desires to evolve and to keep backwards compatibility.

Perl 6 was the valve to release this tension. All the extension proposals that required a break in backwards compatibility were channeled into Perl 6, leaving it in a dreamlike state where everything was possible and nothing was fixed. It took several years of hard work to get into a more solid state.

During this time, Perl 5 also evolved, and the two languages are different enough that most Perl 5 developers don't consider Perl 6 a natural upgrade path anymore, to the point that Perl 6 does not try to obsolete Perl 5 (at least not more than it tries to obsolete any other programming language :-), and the first stable release of Perl 6 in 2015 does not indicate any lapse in support for Perl 5.

Library Availability

Being a relatively young language, Perl 6 lacks the mature module ecosystem that languages such as Perl 5 and Python provide.

To bridge this gap, interfaces exist that allow you to call into libraries written in C, Python, Perl 5 and Ruby. The Perl 5 and Python interfaces are sophisticated enough that you can write a Perl 6 class that subclasses one written in either language, and the other way around.

So if you like a particular Python library, for example, you can simply load it into your Perl 6 program through the Inline::Python module.

Why Should I Use Perl 6?

If you like the quick prototyping experience from dynamically typed programming languages, but you also want enough safety features to build big, reliable applications, Perl 6 is a good fit for you. Its gradual typing allows you to write code without having a full picture of the types involved, and later introduce type constraints to guard against future misuse of your internal and external APIs.

Perl has a long history of making text processing via regular expressions (regexes) very easy, but more complicated regexes have acquired a reputation of being hard to read and maintain. Perl 6 solves this by putting regexes on the same level as code, allowing you to name it like subroutines, and even to use object oriented features such as class inheritance and role composition to manage code and regex reuse. The resulting grammars are very powerful, and easy to read. In fact, the Rakudo Perl 6 compiler parses Perl 6 source code with a Perl 6 grammar!

Speaking of text, Perl 6 has amazing Unicode support. If you ask your user for a number, and they enter it with digits that don't happen to be the Arabic digits from the ASCII range, Perl 6 still has you covered. And if you deal with graphemes that cannot be expressed as a single Unicode code point, Perl 6 still presents it as a single character.

There are more technical benefits that I could list, but more importantly, the language is designed to be fun to use. An important aspect of that is good error messages. Have you ever been annoyed at Python for typically giving just SyntaxError: invalid syntax when something's wrong? This error could come from forgetting a closing parenthesis, for example. In this case, a Perl 6 compiler says

Unable to parse expression in argument list; couldn't find final ')'

which actually tells you what's wrong. But this is just the tip of the iceberg. The compiler catches common mistakes and points out possible solutions, and even suggests fixes for spelling mistakes.

Finally, Perl 6 gives you the freedom to express your problem domain and solution in different ways and with different programming paradigms. And if the options provided by the core language are not enough, Perl 6 is designed with extensibility in mind, allowing you to introduce both new semantics for object oriented code and new syntax.

Subscribe to the Perl 6 book mailing list

* indicates required

Perlgeek.de: Perl 6 By Example, Another Perl 6 Book

Published by Moritz Lenz on 2016-11-18T23:00:01

proposed book cover, starring a Butterfly, by Sebastian Riedl

I'm taking a shot a writing a Perl 6 book. Let's see how this goes.

My working title is Perl 6 by Example, and I want to recycle the approach taken in Using Perl 6 to introduce topics by example. Contrary to the now abandoned previous effort, I want to introduce the examples in small chunks, developing and explaining them bit by bit.

I expect the result to be rather limited in size (maybe 70 to 100 pages), and not a comprehensive guide to the Perl 6 language, but enough to get you started.

Target Audience

The reader should have previous programming experience. I assume familiarity with conditionals, variables, loops and basic data types such as various numbers, strings and lists. Some OO concepts such as classes, instances and methods will also be assumed, but I will drop some clarifying words about how I use the terminology.

Process

I will follow roughly the same process as in my previous book: First I write blog posts about the topics I intend to cover, and later distill them into chapters.

When I have some significant portion of the manuscript available, I will pre-publish it on Leanpub, and start to sell it.

If there is a lot of interest, I might investigate options to publish it in print form.

The Team

Luckily, several people have offered to help in some form or another, typically by writing or proof-reading (in no particular order):

Knowing the warm and helpful nature of the Perl 6 community, it is likely that more folks will step up to help. Any help, as well co-authors, will be highly appreciated.

Other Perl 6 Books

Information on other Perl 6 book projects is rather sparse and vague. I try my best to keep informed about these projects.

Interested?

If you are interested in progress updates or milestones about my book project, please sign up for the mailing list below. It will be low volume (probably less than one email per month). I will also try my best to inform you about news of the other Perl 6 book projects.

Numerous signups will also boost my motivation to work on the book.

Subscribe to the Perl 6 book mailing list

* indicates required

Weekly changes in and around Perl 6: 2016.46 Tweaking Cheaters

Published by liztormato on 2016-11-14T22:13:19

A week in which many of us felt stunned, be it because of the dreary November weather, people you like dying, or just because of the future state of the planet. Luckily, some exciting developments are taking place in the Perl 6 world again!

TWEAK

Last week, Timo Paulssen implemented functionality to post-process the attributes of an object after it has already been initialized using the normal BUILD procedure: TWEAK. This will make a lot of people coming from Moose happy. However, having this new feature available now, beckons the question on what constitutes use v6.c. I’m pretty sure we will have an answer on that question next week.

Meanwhile in the Twitterverse

Zoffix Znet showed a nice graph. brian d foy is building up the suspense about a Learning Perl 6 book from O’Reilly! And Matt Trout mentioned the addition of TWEAK.

Other Core Developments

Blog Posts

Winding Down

I’m glad the past week has gone by. Please check in again next week!


Weekly changes in and around Perl 6: 2016.45 Shapes Get A Boost

Published by liztormato on 2016-11-07T21:04:35

The past week has seen a lot of work on optimizing shaped arrays (and to some extent: native shaped arrays). What are shaped arrays, you might say? Simply put: at compile time you can specify how many dimensions and how many elements per dimension an array will have.

my @a;           # an array that can have anything in it
my @a[10];       # an array with 10 elements
my @a[10;10;10]; # a 3-dimensional array of 10x10x10

This Perl 6 feature was implemented in the weeks before the release last Christmas, and as such did not receive a lot of optimization love yet. A little while ago, Jonathan Worthington pointed out that there were highly optimized nqp functions for handling 2 and 3 dimension cases. The existing code only used the generic N-dimensional nqp functions. After these optimizations, generic shaped array handling is at least 2.5x as fast. Also, iterating over a 1 dimensionally shaped array is now 30% faster than over an ordinary array. Native shaped arrays should receive similar treatment in the coming week.

Lexical Module Loading

Another Perl 6 feature that was mostly implemented just before the Christmas release, was lexical module loading. Since then, Stefan Seifert has worked a lot on this area, improving efficiency and features. One feature that didn’t make it then, was enforcing the complete lexicality of a loaded Perl 6 module. In Perl 5, if you use Foo, and Foo had as use Bar in it, all of the code running could then make use of Bar, even though it had not explicitly loaded that. Currently, that is also true for Perl 6, but that is really a bug and not a feature. In the lexical_module_loading branch, Stefan Seifert fixed this. Unfortunately, this will break some modules in the ecosystem that depend on the old, Perl 5 like behaviour.

Adventing Again

Moritz Lenz reminds us that it is almost that time of the year again. If you have something to write about for the Perl 6 Advent Calendar, contact Moritz or Zoffix on the #perl6 channel so they can add your blogpost-to-be to the schedule.

Why Hasn’t Perl 6 Taken Off Yet?

A rather extensive discussion on Hacker News with over 200 comments. And not all bad. Any publicity is good publicity! There are also some reddit comments.

The Times They Are A-Changin’

Mark Keating informs us that Karen Pauley has stepped down as President of the Perl Foundation. In the Perl 6 Weekly I can only give a big Thank You! If you get the chance, please thank her for all of the hard work she has done for The Perl Foundation in the past 8½ years. Or just send her an email! I know I have!

Other Core Developments

Documentation Developments

Wenzel P. P. Peppmeyer tells us there is a new Perl 6 Grammar Tutorial for all those who wanted to ask about grammars but where to afraid to do so.

Other Blog Posts

Ecosystem Additions

Again, only two this week.

Winding Down

I like the shape of things to come! Check in next week for more fresh Perl 6 news!


brrt to the future: A guide through register allocation: Introduction

Published by Bart Wiegmans on 2016-11-06T10:29:00

This is the first post in what I intend to be a series on the register allocator for the MoarVM JIT compiler. It may be a bit less polished than usual, because I also intend to write more of these posts than I have in the past few months.

The main reason to write a register allocator is that it is needed by the compiler. The original 'lego' MoarVM JIT didn't need one, because it used what is called a 'memory-to-memory' model, meaning that every operation is expected to move operands from and to memory. In this it follows closely the behavior of virtually every other interpreter existing and especially that of MoarVM. However, many of these memory operations are logically redundant (for example, when storing and immediately loading an intermediate value, or loading the same value twice). Such redundancies are inherent to a memory-to-memory code model. In theory some of that can be optimized away, but in practice that involves building an unreasonably complicated state machine.

The new 'expression' JIT compiler was designed with the explicit (well, explicit to me, at least) goals of enabling optimization and specialization of machine code. That meant that a register-to-register code model was preferable, as it makes all memory operations explicit, which in turn enables optimization to remove some of them. (Most redundant 'load' operations can already be eliminated, and I'm plotting a way to remove most redundant 'store' operations, too). However, that also means the compiler must ensure that values can fit into the limited register set of the CPU, and that they aren't accidentally overwritten (for example as a result of a subroutine call). The job of the register allocator is to translate virtual registers to physical registers in a given code segment. This may involve modifying the original code by inserting load, store and copy operations.

Register allocation is known as a hard problem in computer science, and I think there are two reasons for that. The first reason is that finding the optimal allocation for a code segment is (probably) NP-complete. (NP-complete basically means that you have to consider all possible solutions in order to find the one you are after. A common feature of NP-complete problems is that the effect of a local choice on the global solution cannot be fully predicted). However, for what I think are excellent reasons, I can sidestep most of that complexity using the 'linear scan' register allocation algorithm. The details of that algorithm are subject of a later post.

The other reason that register allocation is hard is that the output code must meet the demanding specifications of the target CPU. For instance, some instructions take input only from specific registers, and some implicitly overwrite other registers. Calling conventions can also present a significant source of complexity as values must be placed in the right registers (or on the right stack locations) where the called function may expect them. So the register allocator must somehow encode these specific demands and ensure they are not violated.

Now that I've introduced register allocation, why it is needed, and what the challenges are, the next posts can begin to describe the solutions that I'm implementing.

Perlgeek.de: Perl 6 Advent Calendar 2016 -- Call for Authors

Published by Moritz Lenz on 2016-10-31T23:00:01

Every year since 2009, the Perl 6 community publishes a Perl 6 advent calendar, in the form of blog posts on perl6advent.wordpress.com.

To keep up this great tradition, we need 24 blog posts, and volunteers who write them. If you want to contribute a blog post about anything related to Perl 6, please add your name (and potentially also a topic already) to the schedule, and if you don't yet have a login on the advent blog, please tell me your email address so that I can send you an invitation.

Perl 6 advent blog posts should be finished the day before they are due, and published with midnight (UTC) of the due date as publishing date.

If you have any questions, or want to discuss blog post ideas, please join on the #perl6 IRC channel on irc.freenode.org, or drop me an email at moritz.lenz@gmail.com.

gfldex: You have to take what you can get

Published by gfldex on 2016-10-25T12:53:50

And sometimes you have to get it by any means necessary. If it’s a file, you could use Jonathan Stowes URI::FetchFile. Said module checks if any of four modules are available and takes the first that sticks to turn a URI into a file on disk. There is one interesting line in his code that triggered an ENODOC.

$type = try require ::($class-name);

Here require returns a type object of a class declared by a module with the same name then that module.

Checking roast for that neat trick and playing with the whole dynamic module magic made me realise, that we don’t really cover this in the docs. When I try do handle an ENODOC I like to start with an example that compiles. This time, we need two files.

# M.pm6
unit module M;
class C is export { method m { 'method C::m' } };
class D is export { method m { 'method D::m' } };
# dynamic-modules.p6
use v6;
use lib '.';

subset C where ::('M::C');

my C $context = try { 
    CATCH { default { .note } };
    require ::('M');
    ::('M::C')
};

dd $context.HOW.^methods.elems;
dd $context.HOW.shortname($context);

Any symbol that is loaded via require will not be available at runtime. Consequently, we can’t have static type checks. Using a subset and dynamic lookup, we can get us a type object to check against. The where-clause will smart match against the type object. Since dynamic lookups are slow it may be sensible to cache the type object like so:

subset C where $ //= ::('M::C');

Now we got a type constraint to guard against require not returning a type that matches the name we expect. Please note we check against a name, not a type or interface. If you have the chance to design the modules that are loaded dynamically, you may want to define a role (that may even be empty) that must be implemented by the classes you load dynamically, to make sure you can actually call the methods you expect. Not just methods with the same name.

Now we can actually load the module by its name and resolve one of the classes dynamically and return it from the try block. Since M.pm6 defined a Module (as in Perl6::Metamodel::ModuleHOW) as its top level package, we can’t just simply take the return value of require because Module is not the most introspective thing we have in Perl 6. Please note that the symbols loaded by require are available via dynamic lookup outside the try-block. What happens if you go wild and load modules that have symbols with the same fully qualified name, I do not know. There may be dragons.

The case of loading any of a set of modules that may or may not be installed is quite a general one and to my limited knowledge we don’t got a module for that in the ecosystem yet. I therefore would like to challenge my three reads to write a module that sports the following interface.

sub load-any-module(*%module-name-to-adapter);
load-any-module({'Module::Name' => &Callable-adapter});

Whereby Callable-adapter provides a common interface to translate one sub or method call of the module to whatever user code requires. With such a module Jonathan may be able to boil URI::FetchFile down to 50 lines of code.

UPDATE:

Benchmarking a little revealed that `$` is not equivalent to `state $` while it should. To get the speedup right now use the following.

subset C where state $ = ::('M::C');

UPDATE 2:

The behaviour is by design and has been documented.


rakudo.org: Announce: Rakudo Star Release 2016.10

Published by Steve Mynott on 2016-10-23T16:01:59

On behalf of the Rakudo and Perl 6 development teams, I’m pleased to announce
the October 2016 release of “Rakudo Star”, a useful and usable production
distribution of Perl 6. The tarball for the October 2016 release is available
from http://rakudo.org/downloads/star/.

This is the fourth post-Christmas (production) release of Rakudo Star and
implements Perl v6.c. It comes with support for the MoarVM backend (all module
tests pass on supported platforms).

Please note that this release of Rakudo Star is not fully functional with the
JVM backend from the Rakudo compiler. Please use the MoarVM backend only.

In the Perl 6 world, we make a distinction between the language (“Perl 6”) and
specific implementations of the language such as “Rakudo Perl”. This Star
release includes release 2016.10 of the Rakudo Perl 6 compiler, version 2016.10
of MoarVM, plus various modules, documentation, and other resources collected
from the Perl 6 community.

Some of the new compiler features since the last Rakudo Star release include:

+ Test.pm now provides bail-out()
+ Implemented $?MODULE and ::?MODULE
+ Implemented CompUnit::Repository::Installation::installed
+ .min/.max can now be called on Hashes
+ .succ now increments additional 29 digit ranges, such as Thai digits
+ Coercions now work in return types
+ Added RAKUDO_EXCEPTIONS_HANDLER env var to control exceptions output
+ CompUnit::Repository::Installation now cleans up short-name folders when empty
+ All Unicode quotes can now be used as quoters inside qqww/qww
+ Added basic Unicode 9 support (NFG changes for latest TR#29 still to do))
+ IO::Handle.new now uses ‘utf8’ encoding by default
+ It’s now possible to refer to sigiless parameters inside where clauses
+ Made Complex.new() return 0+0i
+ Added shortname() method to CurriedRoleHOW

Compiler maintenance since the last Rakudo Star release includes:

+ zef and panda now correctly install on OpenBSD and FreeBSD
+ Numerous improvements to content of error messages and addition of new previously-undetected warnings
+ Race conditions and deadlocks fixed
+ Large number of Hash, Bag, Baggie BagHash etc. speedups
+ Numerous improvements in CUR, offering up to 10x faster module loading
+ Many permutations() and combinations() speedups
+ Distribution::Path now handles native libraries correctly
+ Junctions now work in .classify
+ Fixed a memory leak involving EVAL
+ Fixed tab-completion issues with non-identifiers in REPL
+ Made huge improvement to CUR::Filesystem.id performance
+ Many fixes and additions improving JVM backend support
+ Removed argument-taking Dateish candidates for is-leap-year, days-in-month, and day-of-week (were never part of the spec)
+ Cool.IO no longer accepts any arguments
+ Overflow check has been removed from infix:<**>(int, int)

Notable changes in modules shipped with Rakudo Star:

+ prove6 has been added and will be used by panda unless PROVE_COMMAND env var set
+ perl6-pod-to-bigpage: added as dependency for doc tests
+ DBIish: Add simple Str support for Postgres type 790 (money)
+ Linenoise: Remove dependency on Native::Resources
+ Pod-To-HTML: Add support for lang=”” attribute, ignore .precomp and other changes
+ doc: Many documentation additions and improvements (too many to list!)
+ json-fast: Don’t explode when using to-json on a Num
+ p6-native-resources: Mark this module as deprecated in the ecosystem
+ panda: support for prove6 and uninstallation of modules and much else
+ perl6-lwp-simple: Make SSL testing optional and more control over character encoding.
+ svg-plot: Background color option and bubble plot type added.
+ perl6intro.pdf has also been updated.

There are some key features of Perl 6 that Rakudo Star does not yet handle
appropriately, although they will appear in upcoming releases. Some of the
not-quite-there features include:

+ advanced macros
+ non-blocking I/O (in progress)
+ some bits of Synopsis 9 and 11
+ There is an online resource at http://perl6.org/compilers/features that lists
the known implemented and missing features of Rakudo’s backends and other Perl
6 implementations.

In many places we’ve tried to make Rakudo smart enough to inform the programmer
that a given feature isn’t implemented, but there are many that we’ve missed.
Bug reports about missing and broken features are welcomed at
rakudobug@perl.org.

See http://perl6.org/ for links to much more information about Perl 6,
including documentation, example code, tutorials, presentations, reference
materials, design documents, and other supporting resources. Some Perl 6
tutorials are available under the “docs” directory in the release tarball.

The development team thanks all of the contributors and sponsors for making
Rakudo Star possible. If you would like to contribute, see
http://rakudo.org/how-to-help, ask on the perl6-compiler@perl.org mailing list,
or join us on IRC #perl6 on freenode.

Steve Mynott: Rakudo Star 2016.10 Release Candidate

Published by Steve on 2016-10-16T13:10:00

There is a Release Candidate for Rakudo Star 2016.10 (currently RC0) available at

http://pl6anet.org/drop/

This should be quite a bit faster than previous releases and work better on OpenBSD/FreeBSD than the previous release.

It also features "prove6" which is now used by Panda -- removing a run-time dependency on Perl 5. Although it still needs Perl 5 to build.

I'm hoping to release the final version next weekend (Oct 21st) and would be grateful if people could try this out on as many systems as possible (eg. exotic systems like Solaris-like ones and Windows!) 

Full draft announce at

https://github.com/rakudo/star/blob/master/docs/announce/2016.10.md

Note compiling under Windows is possible using the gcc which comes with Strawberry Perl and gmake running under cmd.exe.  Further instructions will be added (thanks to Christopher for feedback).

Any feedback email steve *underscore* mynott *at* gmail *dot* com

gfldex: Being lazy on this side of the Channel

Published by gfldex on 2016-10-03T01:23:32

While writing Concurrent::File::Find I started with a non-concurrent, lazy gather/take version that was, after working mostly correct, turned into a concurrent, Channel sporting version. This looked very nice and regular. A while ago I bragged about another nice and regular lazy program. With four lazy lists in a row it would be lovely to turn them all into Channels.

Simplified it looks like this:

my \l1 := gather for 1..10 { take .item };
my \l2 := gather for l1 { take .item * 2 };
.say for l2;

We loop over l1 to generate l2. Now we need to add a Channel, loop over the lazy lists and .send each value one-by-one, close the Channel for sure and mixin the role to be able to close the Channel from the outside. While we are on it, only create Channels when Rakudo is told to use more then one thread to avoid the overhead of heaving a Channel in the mix.

my &channelify =
    %*ENV<RAKUDO_MAX_THREADS>:!exists || %*ENV<RAKUDO_MAX_THREADS>.Int <= 1
    ?? -> \c { c }
    !! -> \list, $channel = Channel.new {
        start {
            for list {
                $channel.send($_)
            }
            LEAVE $channel.close unless $channel.closed;
        }
        $channel.list but role :: { method channel { $channel } }
    };

 

my \l1 := channelify gather for 1..10 { take .item };
my \l2 := channelify gather for l1 { take .item * 2 };
.say for l2;

The method check script went from 0m2.978s down to 0m2.555s with a fair bit of Rakudo startup time in the mix. Not bad for some quick copypasta.

It pays to be lazy early on.

UPDATE: I improved on checking the environment variable. At some point in the future Rakudo will sport a sane default. It’s hardcoded to 16 worker threads, IIRC.


gfldex: Things I found out while finding

Published by gfldex on 2016-10-02T19:33:31

Concurrent::File::Find is now in the ecosystem. Besides a lack of loop detection, thanks to a lack of readlink in Rakudo and my failed attempt to get __lxstat (GNUs libc got a strange taste when it comes to symbol names) to cooperate, it’s working quite nicely. There are a couple things I learned that I would like to share.

Having a where-clause on a sub-signature will not provide the variables inside the sub-signature. If a where-clause has to operate on all arguments, to check exclusiveness or other interdependence, it has to be applied to the very last argument. This limitation is by design, so I told the docs. That where-clauses don’t work on captures, was not by design and jnthn kindly fixed it the next day. I know that whining gets you stuff, but I didn’t expect it to be so fast.

I also found that a method called .close almost always requires a LEAVE. Let’s have a look at some code.

sub find-simple ( IO(Str) $dir,
    :$keep-going = True,
    :$no-thread = False
) is export {
    my $channel = Channel.new;

    my &start = -> ( &c ) { c } if $no-thread;

    my $promise = start { 
        for dir($dir) {
            CATCH { default { if $keep-going { note .Str } else { .rethrow } } }
            
            if .IO.l && !.IO.e {
                X::IO::StaleSymlink.new(path=>.Str).throw;
            }
            {
                CATCH { when X::Channel::SendOnClosed { last } }
                $channel.send(.IO) if .IO.f;
                $channel.send(.IO) if .IO.d;
            }
            .IO.dir()».&?BLOCK if .IO.e && .IO.d;
        }
        LEAVE $channel.close unless $channel.closed;
    }

    return $channel.list but role :: { method channel { $channel } };
}

This basically takes the List returned by dir and returns IO::Path for files and directories via a Channel. For any directory it recurses in the for-block (that’s what ».&?BLOCK means). Since any of those file-tests may fire an exception, we may leave the start-block. If there is a Promise, that would send us behind the return-statement, where there is nothing. The return-statement is actually in the main-thread and some consumer will be blocking on the returned .list.

.say for find-simple('/home/you');

For the consumer of that Channel it is by no means clear that his may block forever. Hence the LEAVE-statement that ensures a closed Channel if something goes wrong.

Mixing the role into the .listified Channel provides a side channel to hand the Channel over to the consumer, so it can be closed on that end.

my @l := find-simple(%*ENV<HOME>, :keep-going); # binding to avoid eagerness

for @l {
    @l.channel.close if $++ > 5000; # hard-close the channel after 5000 found files
    .say if $++ %% 100 # print every 100th file
}

The binding is required or the Array would eat up the entire Channel and with a scalar in it’s place we would have to flatten. Please note how well the anonymous state variables count in a most untypo-possible manner. This is one of those cases where a boatload of Perl 6 features play together. Sigils allow to indicate a variable, even if it got no name. Autovivication on Any by postfix:<++> gets us a 0 that is incremented to 1. Since we don’t got a name that is spilled into the local scope (the 2nd $++ introduces a separate variable), we don’t need a declarator. I never really liked one shot variables because they are so easy to miss when moving code around. Then the compiler would complain about a missing declaration, or worse, have a variable that is initialised with a wrong value.

There are problems though. While testing in a clean VM (Debian Jessie) I found that symlink-loops (/sys/ got plenty of those) will cause the Promised-thread to consume 100% CPU while the main-thread is doing nothing. There seams to be something amiss with threads. Maybe in conjunction with plenty of exceptions. I would not wonder if there would be a bug. Nobody is testing exception-spamming in a synthetic test.

That’s what $no-thread is for. Simply declaring &start to be a nearly empty pointy will disable any threading and turn the Channel into a glorified Array.

Anyway, both writing and using concurrent code is really easy, as long as we turn a gather/take into a start/send to channel a List through a Channel.

UPDATE: I just managed to golf and report the bug. At the time you read this it may be fixed already.


Zoffix Znet: "Perl 6: What Programming In The Future Is Like?" (Lightning Talk Slides and Video)

Published on 2016-09-29T00:00:00

Brief overview of Perl 6's multi-core power

Strangely Consistent: The curious case of the disappearing test

Published by Carl Mäsak

I've recently learned a few valuable things about testing. I outline this in my Bondcon talk — Bondcon is a fictional anti-conference running alongside YAPC::Europe 2016 in a non-corporeal location but unfortunately frozen in time due to a procrastination-related mishap, awaiting the only speaker's tuits — but I thought I might blog about it, too.

Those of us who use and rely on TDD know to test the software itself: the model, the behaviors, etc. But as a side effect of attaching TravisCI to the 007, another aspect of testing came to light: testing your repository itself. Testing code-as-artifact, not code-as-effect.

Thanks to TravisCI, we currently test a lot of linter-like things that we care about, such as four spaces for indentation, no trailing whitespace, and that META.info parses as correct JSON. That in itself is not news — it's just using the test suite as a linter.

But there are also various bits of consistency that we test, and this has turned out to be very useful. I definitely want to do more of this in the future in my projects. We often talk about coupling as something bad: if you change component A and some unrelated component B breaks, then they are coupled and things are bad.

But some types of coupling are necessary. For example, part of the point of the META.info is to declare what modules the project provides. Do you know how easy it is to forget to update META.info when you add a new module? (Hint: very.) Well, we have a test which double-checks.

We also have a consistency test that makes sure a method which does a certain resource-allocating thing also remembers to do the corresponding resource-deallocating thing. (Yes, there are still a few of those, even in memory-managed languages.) This was after a bug happened where allocations/deallocations were mismatched. The test immediately discovered another location in the code that needed fixing.

All of the consistency tests are basically programmatic ways for the test suite to send you a message from a future, smarter you that remembered to do some B action immediately after doing some A action. No wonder I love them. You could call it "managed coupling", perhaps: yes, there's non-ideal coupling, but the consistency test makes it manageable.

But the best consistency check is the reason I write this post. Here's the background. 007 has a bunch of builtins: subs, operators, but also all the types. These types need to be installed into the setting by the initialization code, so that when someone actually looks up Sub from a 007 program, it actually refers to the built-in Sub type.

Every now and again, we'd notice that we'd gotten a few new types in the language, but they hadn't been added as built-ins. So we added them manually and sighed a little.

Eventually this consistency-test craze caught up, and we got a test for this. The test is text-based, which is very ironic considering the project itself; but hold that thought.

Following up on a comment by vendethiel, I realized we could do better than text-based comparison. On the Perl 6 types side, we could simply walk the appropriate module namespaces to find all the types.

There's a general rule at play here. The consistency tests are very valuable, and testing code-as-artifact is much better than nothing. But if there's a corresponding way to do it by running the program instead of just reading it, then that way invariably wins.

Anyway, the test started doing Stash traversal, and after a few more tweaks looked really nice.

And then the world paused a bit, like a good comedian, for maximal effect.

Yes, the test now contained an excellent implementation of finding all the types in Perl 6 land. This is exactly what the builtin initialization code needed to never be inconsistent in the first place. The tree walker moved into the builtins code itself. The test file vanished in the night, its job done forever.

And that is the story of the consistency check that got so good at its job that it disappeared. Because one thing that's better than managed coupling is... no coupling.

Pawel bbkr Pabian: Oh column, where art thou?

Published by Pawel bbkr Pabian on 2016-09-26T09:53:06

When ramiroencinas added FileSystem::Capacity::VolumesInfo to Perl 6 ecosystem I've spotted that it has no macOS support. And while trying to contribute to this module I've discovered how less known Perl 6 features can save the day. What FileSystem::Capacity::VolumesInfo module does is parsing output from df command, which looks like this:

$ df -k -P
Filesystem                                  1024-blocks       Used Available Capacity  Mounted on
/dev/disk3                                   1219749248  341555644 877937604    29%    /
devfs                                               343        343         0   100%    /dev
/dev/disk1s4                                  133638140  101950628  31687512    77%    /Volumes/Untitled
map -hosts                                            0          0         0   100%    /net
map auto_home                                         0          0         0   100%    /home
map -fstab                                            0          0         0   100%    /Network/Servers
//Pawel%20Pabian@biala-skrzynka.local./Data  1951417392 1837064992 114352400    95%    /Volumes/Data
/dev/disk5s2                                 1951081480 1836761848 114319632    95%    /Volumes/Time Machine Backups
bbkr@localhost:/Users/bbkr/foo 123           1219749248  341555644 877937604    29%    /Volumes/osxfuse

(if you see wrapped or trimmed output check raw one here)

And while this looks nice for humans, it is tough task for parser.

So let's use Perl 6 features to deal with this mess.

Capture command line output.

my ($header, @volumes) = run('df', '-k', '-P', :out).out.lines;

Method run executes shell command and returns Proc object. Method out creates Pipe object to receive shell command output. Method lines splits this output into lines, first goes to $header variable, remaining to @volumes array.

Parse header.

my $parsed_header = $header ~~ /^
    ('Filesystem')
    \s+
    ('1024-blocks')
    \s+
    ('Used')
    \s+
    ('Available')
    \s+
    ('Capacity')
    \s+
    ('Mounted on')
$/;

We do it because match object keeps each capture, and each capture knows from and to position at which it matched, for example:

say $parsed_header[1].Str;
say $parsed_header[1].from;
say $parsed_header[1].to;

Will return:

1024-blocks
44
55

That will help us a lot with dynamic columns width!

Extract row values.

First we have to look at border between Filesystem and 1024-blocks column. Because Filesystem is aligned to left and 1024-blocks is aligned to right so data from both columns can occupy space between those headers, for example:

Filesystem                      1024-blocks
/dev/someverybigdisk        111111111111111
me@host:/some directory 123    222222222222
         |                      |
         |<----- possible ----->|
         |<--- border space --->|

We cannot simply split it by space. But we know where 1024-blocks columns ends, so the number that ends at the same position is our volume size. To extract it, we can use another useful Perl 6 feature - regexp position anchor.

for @volumes -> $volume {
    $volume ~~ / (\d+) <.at($parsed_header[1].to)> /;
    say 'Volume size is ' ~ $/[0] ~ 'KB';
}

That finds sequence of digits that are aligned to the position of the end of the header. Every other column can be extracted using this trick if we know the data alignment.

$volume ~~ /
    # first column is not used by module, skip it
    \s+

    # 1024-blocks, right aligned
    (\d+) <.at($parsed_header[1].to)>

    \s+

    # Used, right aligned
    (\d+) <.at($parsed_header[2].to)>

    \s+

    # Available, right aligned
    (\d+) <.at($parsed_header[3].to)>

    \s+

    # Capacity, middle aligned, never longer than header
    <.at($parsed_header[4].from)>
        \s* (\d+ '%') \s*
    <.at($parsed_header[4].to)> 

    \s+

    # Mounted on, left aligned
    <.at($parsed_header[5].from)>(.*)
$/;

Profit!

By using header name positions and position anchors in regular expression we got bomb-proof df parser for macOS that works with regular disks, pendrives, NFS / AFS / FUSE shares, weird directory names and different escaping schemas.

gfldex: I left my keys in a side-channel

Published by gfldex on 2016-09-25T22:48:11

While trying to bake option groups into a module I stumbled over a neat solution to a common problem. I wanted to have a subroutine as a where-clause that slurps up named arguments, does some checks and either returns True to satisfy the where-clause or to die with a proper error message. That was simple but incomplete. The where-clause doesn’t provide the name of the argument it is checking on, what would be needed to have a proper error message. Let’s have some (simplified) code.

sub checker(*%colon-keys){ sub ($value-from-where-clause) { True } }
sub f( *%h where checker(:a, :b, :c) ) {}

The sub checker is called before the where clause is actually checking anything. In Perl6 a where-clause is kind of syntaxy. If an expression is provided it will call that expression and keep it’s returned value to then go and do the actual check against the value of %h. This does not happen at compile time and the returned value is not cached. In our example an anonymous sub is returned that takes one argument (a requirement by where) and must return True to let the where-clause-check pass.

As you can see checker takes a list of colon-pairs. That leaves the question how we can provide additional information we might want to output in an exception, esp. if we want that parameter to be optional and avoid odd syntax. We could have an optional positional but then we can’t mix positional and named arguments in checker. Storing that value would be trivial because the anonymous sub that is returned could have a closure variable. We just need to fill it. Luckily the sub is returned as a reference that is then called by the where-clause. We can sneak another call in, as long as we we don’t forget to return the code reference to the anonymous sub.

Returning a reference to the same object is done by chainable method calls. Often, when things get complicated in Perl 6-land, we just mix a role in. Then we have a method and can return self.

use v6;

sub g($i){
    my $closure-variable;
    sub ($value-from-where-clause) {
        say [$closure-variable, $value-from-where-clause];
        $value-from-where-clause == $i
            or die "bad value $value-from-where-clause for $closure-variable"
    } but role :: {
        method side-channel($second-value){
            $closure-variable = $second-value;
            self
    }
  }
}

sub f($a where g(42).side-channel($a.VAR.name) ){ 'OK' }

say f(42);
# OUTPUT
# [$a 42]
# OK

And there we have it — a side-channel to a where-clause-call or any other spot we can use higher order functions at. Now I can go and provide MTA error messages for option groups.


gfldex: These keys are LTA

Published by gfldex on 2016-09-25T14:18:26

While toying around with enums as boolean options to a routine, i found the default error message less then awesome.

Constraint type check failed for parameter '@options'

It would be hard to be even less specific. Let’s create a few exceptions to tell what is going on when things go wrong.

class X::Paramenter::Exclusive is Exception {
has $.type;
    method message {
        "Parameters of {$.type.perl} are mutual exclusive"
    }
}

Now we can check if options of Find::Type are exclusive and complain accordingly.

&& ( exclusive-argument(@options, Find::Type) or fail X::Paramenter::Exclusive.new(type => Find::Type) )

class X::Parameter::UnrecognisedOption is Exception {
    has $.type;
    has $.unrecognised;
    method message {
        "Option { $.unrecognised } not any of { $.type.map({ (.^name ~ '::') xx * Z~ .enums.keys.flat }).flat.join(', ') }"
    }
}

Since enums are containers for types and those got names we can use set operators to check and single out none matching options (basically anything the +@options slurps up we don’t know).

or fail X::Parameter::UnrecognisedOption.new(type => (Find::Type, Find::Options),
    unrecognised => .item ∖ (|Find::Type::.values, |Find::Options::.values) )

Stitching the error message together is a bit more involved because we can get a list of all enum keys in a given enum but those don’t know their qualified name. We have to prefix with the enum name and :: by hand.

class X::Parameter::UnrecognisedOption is Exception {
    has $.type;
    has $.unrecognised;
    method message {
        "Option { $.unrecognised } not any of { $.type.map: { (.^name ~ '::') xx * Z~ .enums.keys.flat } }"
    }
}

This results in a much more awesome error message:

Option 42 not any of Type::File, Type::Dir, Type::Symlink, Options::Recursive, Options::Keep-going

This looks all quite regular. We have a slurpy that is kind of parameterised with one or many enums and those enums may have a flag telling if they act like radio buttons. Sounds like this idiom would fit nicely into a module.


Zoffix Znet: Perl 6 Core Hacking: Can Has Moar Cover?

Published on 2016-09-22T00:00:00

Discussion about roast coverage of Rakudo compiler

Strangely Consistent: Where in the sky

Published by Carl Mäsak

Our 1.5yo has a favorite planet. By a long margin, it's Mars.

I've told him he's currently on Earth, and shown him where, and he's OK with that. Mars is still the favorite. Earth's moon is OK too.

Such an interest does not occur — pun not intended — in a vacuum. We have a book at home (much like this one, but a different one, and in Swedish), and we open it sometimes to admire Mars (and then everything else).

But what really left its mark is the Space Room in our local Tekniska Museet — a complete dark room with projectors filling a wall with pictures of space. Using an Xbox controller, you decide where to fly in the solar system. If anything, this is what made Mars real for our son. In that room, we've orbited Mars. We've stood on its surface, looking at the Mars moons in the Mars sky. We've admired a Mars sunrise, standing quiet together in the red sands.

Inevitably, I got the first hard science question I couldn't answer from him a couple of weeks ago.

I really should have seen it coming. I was dropping him off at kindergarten. Before we went inside, I crouched next to him to point up at the moon above the city. He looked at it and said "Moon" in Swedish. Then he turned to me, eyes intent, and said "Mars?". It was a question.

He had put together that the planets we were admiring in the book and in the Space Room were actually up there somewhere. And now he just wanted me to point him towards Mars.

I had absolutely no idea. I told him it's not on the sky right now, but for all I knew, it might have been.

Now I really want to know how to find this out. Sure, there are calculations involved. I want to learn enough about them to be able to write a small, understandable computer program for me. It should be able to answer a question such as "Where in the sky is Mars?". Being able to ask it for all the planets in our solar system seems like an easy generalization without much extra cost.

Looking at tutorials like this one with illustrations and this one with detailed calculations, I'm heartened to learn that it's not only possible to do this, but more or less the steps I hoped:

There are many complicating factors that together make a simple calculation merely approximate, and the underlying reasons are frankly fascinating, but it seems that if I just want to be able to point roughly in the right direction and have a hope of finding a planet there, a simple method will do.

I haven't written any code yet, so consider this a kind of statement of intent. I know there must be oodles of "night sky" apps and desktop programs that already present this information... but my goal is to make the calculation myself, with a program, and to get it right. Lovingly handcrafted planetary positions.

It would also be nice to be able to ask "Where in the sky is the moon?" (that one's easy to double-check) or "Where in the sky is the International Space station?". If anything, that ought to be a much simpler calculation, since these orbit Earth.

Once I can reliably calculate all the positions, being able to know at what time things rise and set would also be very useful.

I went outside to throw the garbage last night, and it turned out it was a cloudless late evening. I saw some of the brighter stars, even from the light-polluted vantage point of our yard. I may have been gazing on Mars without knowing it. It's a nice feeling to find out how to learn something. Even nicer when it's for your child, so you can show him his favorite planet in the sky.

Zoffix Znet: Perl6.Fail, Release Robots, and Other Goodies

Published on 2016-09-17T00:00:00

Description of work done to automate Perl 6 releases

Zoffix Znet: Perl 6 Core Hacking: Wrong Address; Return To Sender

Published on 2016-09-14T00:00:00

Following along with debugging dispatch bugs

Zoffix Znet: Perl 6 Core Hacking: Grammatical Babble

Published on 2016-09-12T00:00:00

Following along with fixing a grammar bug

Death by Perl6: Slightly less basic Perl6 module management

Published by Nick Logan on 2016-09-03T15:33:40

This is meant to answer some of the reoccurring questions I've seen in #perl6 about module management. Solutions use the Perl6 package manager called Zef


Q) Install a module to a custom/non-default location?
A) Use the install command with the --install-to parameter

zef --install-to=inst#/my/custom/location install My::Module

Q) I installed a module to a custom location, but rakudo doesn't see it?
A) Set the PERL6LIB env variable or -I flag accordingly

PERL6LIB="inst#/my/custom/location" perl6 -e "use Text::Table::Simple; say 'ok'"
ok

perl6 -Iinst#/my/custom/location -e "use Text::Table::Simple; say 'ok'"
ok

Q) Uninstall a module installed to a custom/non-default location?
A) Use the uninstall command with the --from parameter

zef --from=inst#/my/custom/location uninstall My::Module

Q) Install a module from a uri instead of a name?
A) JFDI - Many extraction formats are supported by default, and others can easily be added

zef install https://github.com/ugexe/zef.git
zef install https://github.com/ugexe/zef/archive/master.zip
zef install https://github.com/ugexe/zef/archive/master.tar.gz

Q) Install dependencies when the top level module fails to install?
A) Use the --serial flag in addition to the install command

# Without --serial any dependencies of My::Module would only be installed if
# My::Module passes its build/test phase (even if the dependencies pass their tests)

zef --serial install My::Module 

Q) Use TAP6 instead of prove?
A1) Temporarily disable the services that are configured to be used first via a CLI flag (--/$service-short-name>)

zef --/prove --/default-tester install My::Module
zef --/prove --/default-tester test My::Module

A2) Open resources/config.json and reorder the entries under Test so Zef::Service::TAP is first (or the only)

"Test" : [
    {
        "short-name" : "tap-harness",
        "module" : "Zef::Service::TAP",
    }
]

Q) Find out what this SHA1 string from an error message is?
A) Use the locate command with the --sha1 flag

zef --sha1 locate A9948E7371E0EB9AFDF1EEEB07B52A1B75537C31

Q) How do I search/install/etc specific versions or verion ranges?
A) The same way you'd use it in Perl6 code

zef search "CSV::Parser:ver<2.*>"
===> Found 0 results

zef search "CSV::Parser:ver<0.*>"
===> Found 2 results
...

Steve Mynott: You Wouldn't BELIEVE what I saw at YAPC::EU!!!

Published by Steve Mynott on 2016-08-28T18:57:57

We turned up in Cluj via Wizz Air to probably one of the best pre YAPC parties ever located on three levels on the rooftop of Evozon‎’s plush city centre offices. We were well supplied with excellent wine, snacks and the local Ursus beer and had many interesting conversations with old friends.

On the first day Tux spoke about his Text::CSV modules for both Perl 5 and 6 on the first day and I did a short talk later in the day on benchmarking Perl 6. Only Nicholas understood my trainspotter joke slide with the APT and Deltic! Sadly my talk clashed with Lee J talking about Git which I wanted to see so I await the youtube version! Jeff G then spoke about Perl 6 and parsing languages such as JavaScript. Sadly I missed Leon T’s Perl 6 talk which I also plan on watching on youtube. Tina M gave an excellent talk on writing command line tools. She also started the lightning talks with an evangelical talk about how tmux was better than screen. Geoffrey A spoke about configuring sudo to run restricted commands in one directory which seemed a useful technique to me. Dave C continued his conference tradition of dusting off his Perl Vogue cover and showing it again. The age of the image was emphasised by the amazingly young looking mst on it. And Stefan S ended with a call for Perl unification.

The main social event was in the courtyard of the main museum off the central square with free food and beer all evening and an impressive light show on the slightly crumbling facade. There were some strange chairs which resembled cardboard origami but proved more comfortable than they looked when I was finally able to sit in one. The quality of the music improved as the evening progressed (or maybe the beer helped) I was amazed to see Perl Mongers actually dancing apparently inspired by the younger Cluj.pm members.

Day Two started with Sawyer’s State of the Velociraptor‎ which he had, sensibly, subcontracted to various leading lights of the Perl Monger community. Sue S (former London.pm leader) was up first with a short and sweet description of London.pm. Todd R talked about Houston.pm. Aaron Crane spoke about the new improved friendlier p5p. Tina about Berlin.pm and the German Perl community site she had written back in the day. This new format worked very well and it was obvious Perl Mongers groups could learn much from each other. Max M followed with a talk about using Perl and ElasticSearch to index websites and documents and Job about accessibility.

1505 had, from the perspective of London.pm, one of the most unfortunate scheduling clashes at YAPC::EU ever, with three titans of London.pm (all former leaders) battling for audience share. I should perhaps tread carefully here lest bias become apparent but the heavyweight Sue Spence was, perhaps treacherously, talking about Go in the big room and Dave Cross and Tom talking about Perl errors and HTML forms respectively in the other rooms. This momentous event should be reproducible by playing all three talks together in separate windows once they are available.

Domm did a great talk on Postgres which made me keen to use this technology again. André W described how he got Perl 6 running on his Sailfish module phone while Larry did a good impression of a microphone stand. I missed most of Lance Wick’s talk but the bit I caught at the end made me eager to watch the whole thing.

Guinevere Nell gave a fascinating lightning talk about agent based economic modelling. Lauren Rosenfield spoke of porting (with permission) a “Python for CS” book to perl 6. Lukas Mai described his journey from Perl to Rust. Lee J talked about photography before Sue encouraged people to break the London.pm website. Outside the talk rooms on their stall Liz and Wendy had some highly cool stuffed toy Camelia butterflies produced by the Beverly Hills Teddy Bear Company and some strange “Camel Balls” bubblegum. At the end of the day Sue cat herded many Mongers to eat at the Enigma Steampunk Bar in central Cluj with the cunning ploy of free beer money (recycled from the previous year’s Sherry money).

The third day started with Larry’s Keynote in which photographs of an incredible American house “Fallingwater” and Chinese characters (including “arse rice”) featured heavily. Sweth C gave a fast and very useful introduction to swift. Nicholas C then confused a room of people for an hour with a mixture of real Perl 5 and 6 and an alternative timeline compete with T shirts. The positive conclusion was that even if the past had been different the present isn’t likely to have been much better for the Perl language family than it is now! Tom spoke about Code Review and Sawyer about new features in Perl 5.24. Later I heard Ilya talk about running Perl on his Raspberry PI Model B and increasing the speed of his application very significantly to compensate for its low speed! And we finished with lightning talks where we heard about the bug tracker OTRS (which was new to me), Job spoke about assistive tech and Nine asked us to ask our bosses for money for Perl development amongst several other talks. We clapped a lot in thanks, since this was clearly a particularly well organised YAPC::EU (due to Amalia and her team!) and left to eat pizza and fly away the next day. Some stayed to visit a salt mine (which looked most impressive from the pictures!) and some stayed longer due to Lufthansa cancelling their flights back!


6guts: Concurrency bug squishing: part 1

Published by jnthnwrthngtn on 2016-08-22T22:24:26

Most of my recent Perl 6 development time has been spent hunting down and fixing various concurrency bugs. We’ve got some nice language features in this area, and they’ve been pretty well received so far. However, compared with many areas of Perl 6, they have been implemented relatively recently. Therefore, they have had less time to mature – which, of course, means more bugs and other rough edges.

Concurrency bugs tend to be rather tedious to hunt down. This is in no small part because reproducing them reliably can be challenging. Even once a fairly reliable reproduction is available, working out what’s going on can be tricky. Like all debugging, being methodical and patient is the key. I tend to keep notes of things I’ve tried and observed, and output produced by instrumenting programs with logging (fancy words for “adding prints and exception throws when sanity checks fail”). I will use interactive debuggers when needed, but even then the data from them tends to end up in my editor on any extended bug hunt. Debugging is in some ways the experimental science of programming. Even with a good approach, being sufficiently patient – or perhaps just downright stubborn – matters plenty too.

In the next 2-3 posts here, I’ll discuss a few of the bugs I recently hunted down. It will not be anything close to an exhaustive list of them, which would surely be as boring for you to read as it would be for me to write. This is just the “greatest hits”, if you like.

A tale of silly suspicions and dodgy data

This hunt started out looking in to various hangs that had been reported. Deadlocks are a broad category of bug (there’s another completely unrelated one I’ll cover in this little series, even). However, a number of ones that had shown up looked very similar. All of them showed a number of threads trying to enter GC, stuck in the consensus loop (which, yes, really is just a loop that we go around asking, “did every thread agree we’re going to do GC yet?”)

I’ll admit I went into this one with a bit of a bias. The GC sync-up code in question is a tad clever-looking. That doesn’t mean it’s wrong, but it makes it harder to be comfortable it’s correct. I also worried a bit that the cost of the consensus loop might well be enormous. So I let myself become a bit distracted for some minutes doing a profiling run to find out. I mean, who doesn’t want to be the person who fixed concurrency bug in the GC and made it faster at the same time?!

I’ve found a lot of useful speedups over the years using callgrind. I’ve sung its praises on this blog at least once before. By counting CPU cycles, it can give very precise and repeatable measurements on things that – measured using execution time – I’d consider within noise. With such accuracy, it must be the only profiler I need in my toolbox, right?

Well, no, of course not. Any time somebody says that X tool is The Best and doesn’t explain the context when it’s The Best, be very suspicious. Running Callgrind on a multi-threaded benchmark gave me all the ammunition I could ever want for replacing the GC sync-up code. It seemed that a whopping 30% of CPU cycles were spent in the GC consensus loop! This was going to be huuuuge…

Or was it? I mean, 35% seems just a little too huge. Profiling is vulnerable to the observer effect: the very act of measuring a program’s performance inevitably changes the program’s performance. And, while on the dubious physics analogies (I shouldn’t; I was a pretty awful physicist once I reached the relativity/QM stuff), there’s a bit of an uncertainty principle thing going on. The most invasive profilers can tell you very precisely where in your program time is spent, but you’re miles off knowing how fast you’re normally going in those parts of the program. They do this by instrumenting the program (like the current Perl 6 on MoarVM profiler does) or running it on a synthetic CPU, as Callgrind does. By contrast, a sampling profiler lets your program run pretty much as normal, and just takes regular samples of the call stack. The data is much less precise about where the program is spending its time, but it is a much better reflection of how fast the program is normally going.

So what would, say, the perf sampling profiler make of the benchmark? Turns out, well less than 1% of time was spent in the GC consensus loop in question. (Interestingly, around 5% was spent in a second GC termination consensus loop, which wasn’t the one under consideration here. That will be worth looking into in the future.) The Visual Studio sampling profiler on Windows – which uses a similar methodology – also gave a similar figure, which was somewhat reassuring also.

Also working against Callgrind is the way the valgrind suite of tools deal with multi-threaded applications – in short by serializing all operations onto a single thread. For a consensus loop, which expects to be dealing with syncing up a number of running threads, this could make a radical difference.

Finally, I decided to check in on what The GC Handbook had to say on the matter. It turns out that it suggests pretty much the kind of consensus loop we already have in MoarVM, albeit rather simpler because it’s juggling a bit less (a simplification I’m all for us having in the future too). So, we’re not doing anything so unusual, and with suitable measurements it’s performing as expected.

So, that was an interesting but eventually fairly pointless detour. What makes this all the more embarassing, however, is what came next. Running an example I knew to hang under GDB, I waited for it to do so, hit Ctrl + C, and started looking at all of the threads. Here’s a summary of their states:

And yes, for the sake of this being a nice example for the blog I perhaps should not have picked one with 17 threads. Anyway, we’ll cope. First up, the easy to explain stuff. All the threads that are “blocking on concurrent queue read (cond var wait)” are fairly uninteresting. They are Perl 6 thread pool threads waiting for their next task (that is, wanting to pull an item from the scheduler’s queue, and waiting for it to be non-empty).

Thread 01 is the thread that has triggered GC. It is trying to get consensus from other threads to begin GC. A number of other threads have already been interrupted and are also in the consensus loop (those marked “in AO_load_read at MVM_gc_enter_from_interrupt”). This is where I had initially suspected the problem would be. That leaves 4 other threads.

You might wonder how we cope with threads that are simply not in a position to participate in the consensus process, because they’re stuck in OS land, blocked waiting on I/O, a lock, a condition variable, a semaphore, a thread join, and so forth. The answer is that before they hand over control, they mark themselves as blocked. Another thread will steal their work if a GC happens while the thread is blocked. When the thread becomes unblocked, it marks itself as such. However, if a GC is already happening at that point, it’s not safe for the thread to proceed. Thus, it yields until GC is done. This accounts for the 3 threads described as “in mark thread unblocked; yielded”.

Which left one thread, which was trying to acquire a lock in order to peek a queue. The code looked like this:

    if (kind != MVM_reg_obj)
        MVM_exception_throw_adhoc(tc, "Can only shift objects from a ConcBlockingQueue");

    uv_mutex_lock(&cbq->locks->head_lock);

    while (MVM_load(&cbq->elems) == 0) {
        MVMROOT(tc, root, {

Spot anything missing?

Here’s the corrected version of the code:

    if (kind != MVM_reg_obj)
        MVM_exception_throw_adhoc(tc, "Can only shift objects from a ConcBlockingQueue");

    MVM_gc_mark_thread_blocked(tc);
    uv_mutex_lock(&cbq->locks->head_lock);
    MVM_gc_mark_thread_unblocked(tc);

    while (MVM_load(&cbq->elems) == 0) {
        MVMROOT(tc, root, {

Yup, it was failing to mark itself as blocked while contending for a lock, meaning the GC could not steal its work. So, the GC’s consensus algorithm wasn’t to blame after all. D’oh.

To be continued…

I actually planned to cover a second issue in this post. But, it’s already gone midnight, and perhaps that’s enough fun for one post anyway. :-) Tune in next time, for more GC trouble and another cute deadlock!


6guts: Assorted fixes

Published by jnthnwrthngtn on 2016-07-23T17:36:04

I’ve had a post in the works for a while about my work to make return faster (as well as routines that don’t return), as well as some notable multi-dispatch performance improvements. While I get over my writer’s block on that, here’s a shorter post on a number of small fixes I did on Thursday this week.

I’m actually a little bit “between things” at the moment. After some recent performance work, my next focus will be on concurrency stability fixes and improvements, especially to hyper and race. However, a little down on sleep thanks to the darned warm summer weather, I figured I’d spend a day picking a bunch of slightly less demanding bugs off from the RT queue. Some days, it’s about knowing what you shouldn’t work on…

A nasty string bug

MoarVM is somewhat lazy about a number of string operations. If you ask it to concatenate two simple strings, it will produce a string consisting of a strand list, with two strands pointing to the two strings. Similarly, a substring operation will produce a string with one strand and an offset into the original, and a repetition (using the x operator) will just produce a string with one strand pointing to the original string and having a repetition count. Note that it doesn’t currently go so far as allowing trees of strand strings, but it’s enough to prevent a bunch of copying – or at least delay it until a bunch of it can be done together and more cheaply.

The reason not to implement such cleverness is because it’s of course a whole lot more complex than simple immutable strings. And both RT #123602 and RT #127782 were about a sequence of actions that could trigger a bug. The precise sequence of actions were a repeat, followed by a concatenation, followed by a substring with certain offsets. It was caused by an off-by-one involving the repetition optimization, which was a little tedious to find but easy to fix.

Constant folding Seqs is naughty

RT #127749 stumbled across a case where an operation in a loop would work fine if its input was variable (like ^$n X ^$n), but fail if it were constant (such as ^5 X ^5). The X operator returns a Seq, which is an iterator that produces values once, throwing them away. Thus iterating it a second time won’t go well. The constant folding optimization is used so that things like 2 + 2 will be compiled into 4 (silly in this case, but more valuable if you’re doing things with constants). However, given the 1-shot nature of a Seq, it’s not suitable for constant folding. So, now it’s disallowed.

We are anonymous

RT #127540 complained that an anon sub whose name happened to match that of an existing named sub in the same scope would trigger a bogus redeclaration error. Wait, you ask. Anonymous sub…whose name?! Well, it turns out that what anon really means is that we don’t install it anywhere. It can have a name that it knows itself by, however, which is useful should it show up in a backtrace, for example. The bogus error was easily fixed up.

Charset, :ignoremark, :global, boom

Yes, it’s the obligatory “dive into the regex compiler” that all bug fixing days seem to come with. RT #128270 mentioned that that "a" ~~ m:g:ignoremark/<[á]>/ would whine about chr being fed a negative codepoint. Digging into the MoarVM bytecode this compiled into was pretty easy, as chr only showed up one time, so the culprit had to be close to that. It turned out to be a failure to cope with end of string, and as regex bugs go wasn’t so hard to fix.

Hang, crash, wallop

This is one of those no impact on real code, but sorta embarrassing bugs. A (;) would cause an infinite loop of errors, and (;;) and [0;] would emit similar errors also. The hang was caused by a loop that did next but failed to consider that the iteration variable needed updating in the optimizer. The second was because of constructing bad AST with integers hanging around in it rather than AST nodes, which confused all kinds of things. And that was RT #127473.

Improving an underwhelming error

RT #128581 pointed out that my Array[Numerix] $x spat out an error that fell rather short of the standards we aim for in Perl 6. Of course, the error should complain that Numerix isn’t known and suggest that maybe you wanted Numeric. Instead, it spat out this:

===SORRY!=== Error while compiling ./x.pl6
An exception occurred while parameterizing Array
at ./x.pl6:1
Exception details:
  ===SORRY!=== Error while compiling
  Cannot invoke this object (REPR: Null; VMNull)
  at :

Which is ugly. The line number was at least correct, but still… Anyway, a small tweak later, it produced the much better:

$ ./perl6-m -e 'my Array[Numerix] $x;'
===SORRY!=== Error while compiling -e
Undeclared name:
    Numerix used at line 1. Did you mean 'Numeric'?

Problems mixing unit sub MAIN with where constraints

RT #127785 observed that using a unit sub MAIN – which takes the entire program body as the contents of the MAIN subroutine – seemed to run into trouble if the signature contained a where clause:

% perl6 -e 'unit sub MAIN ($x where { $^x > 1 } );  say "big"'  4
===SORRY!===
Expression needs parens to avoid gobbling block
at -e:1
------> unit sub MAIN ($x where { $^x > 1 }⏏ );  say "big"
Missing block (apparently claimed by expression)
at -e:1
------> unit sub MAIN ($x where { $^x > 1 } );⏏  say "big"

The error here is clearly bogus. Finding a way to get rid of it wasn’t too hard, and it’s what I ended up committing. I’ll admit that I’m not sure why the check involved was put there in the first place, however. After some playing around with other situations that it might have aided, I failed to find any. There were also no spectests that depended on it. So, off it went.

$?MODULE

The author of RT #128552 noticed that the docs talked about $?MODULE (“what module am I currently in”), to go with $?PACKAGE and $?CLASS. However, trying it out let to an undeclared variable error. It seems to have been simply overlooked. It was easy to add, so that’s what I did. I also found some old, provisional tests and brought them up to date in order to cover it.

Subtypes, definedness types, and parameters

The submitter of RT #127394 was creative enough to try -> SomeSubtype:D $x { }. That is, take a subset type and stick a :D on it, which adds the additional constraint that the value must be defined. This didn’t go too well, resulting in some rather strange errors. It turns out that, while picking the type apart so we can code-gen the parameter binding, we failed to consider such interesting cases. Thankfully, a small refactor made the fix easy once I’d figured out what was happening.

1 day, 10 RTs

Not bad going. Nothing earth-shatteringly exciting, but all things that somebody had run into – and so others would surely run into again in the future. And, while I’ll be getting back to the bigger, hairier things soon, spending a day making Perl 6 a little nicer in 10 different ways was pretty fun.


rakudo.org: Announce: Rakudo Star Release 2016.07

Published by Steve Mynott on 2016-07-22T10:41:46

On behalf of the Rakudo and Perl 6 development teams, I’m pleased to announce the July 2016 release of “Rakudo Star”, a useful and usable production distribution of Perl 6. The tarball for the July 2016 release is available from http://rakudo.org/downloads/star/.

This is the third post-Christmas (production) release of Rakudo Star and implements Perl v6.c. It comes with support for the MoarVM backend (all module tests pass on supported platforms).

Please note that this release of Rakudo Star is not fully functional with the JVM backend from the Rakudo compiler. Please use the MoarVM backend only.

In the Perl 6 world, we make a distinction between the language (“Perl 6”) and specific implementations of the language such as “Rakudo Perl”. This Star release includes release 2016.07 of the Rakudo Perl 6 compiler, version 2016.07 of MoarVM, plus various modules, documentation, and other resources collected from the Perl 6 community.

Some of the new compiler features since the last Rakudo Star release include:

Compiler maintenance since the last Rakudo Star release includes:

Notable changes in modules shipped with Rakudo Star:

perl6intro.pdf has also been updated.

There are some key features of Perl 6 that Rakudo Star does not yet handle appropriately, although they will appear in upcoming releases. Some of the not-quite-there features include:

In many places we’ve tried to make Rakudo smart enough to inform the programmer that a given feature isn’t implemented, but there are many that we’ve missed. Bug reports about missing and broken features are welcomed at rakudobug@perl.org.

See http://perl6.org/ for links to much more information about Perl 6, including documentation, example code, tutorials, presentations, reference materials, design documents, and other supporting resources. Some Perl 6 tutorials are available under the “docs” directory in the release tarball.

The development team thanks all of the contributors and sponsors for making Rakudo Star possible. If you would like to contribute, see http://rakudo.org/how-to-help, ask on the perl6-compiler@perl.org mailing list, or join us on IRC #perl6 on freenode.

Pawel bbkr Pabian: Comprehensive guide and tools to split monolithic database into shards using Perl

Published by Pawel bbkr Pabian on 2016-06-21T04:47:32

You can find the most recent version of this tutorial here.

Intro

When you suddenly get this brilliant idea, the revolutionary game-changer, all you want to do is to immediately hack some proof of concept to start small project flame from a spark of creativity. So I'll leave you alone for now, with your third mug of coffee and birds chirping first morning songs outside of the window...

...Few years later we meet again. Your proof of concept has grown into a mature, recognizable product. Congratulations! But why the sad face? Your clients are complaining that your product is slow and unresponsive? They want more features? They generate more data? And you cannot do anything about it, despite the fact that you bought the most shiny, expensive database server that is available?

When you were hacking your project on day 0, you were not thinking about the long term scalability. All you wanted to do was to create working prototype as fast as possible. So single database design was easiest, fastest and most obvious to use. You didn't think back then, that a single machine cannot be scaled up infinitely. And now it is already too late.

LOOKS LIKE YOU'RE STUCK ON THE SHORES OF [monolithic design database] HELL. THE ONLY WAY OUT IS THROUGH...

(DOOM quote)

Sharding to the rescue!

Sharding is the process of distributing your clients data across multiple databases (called shards). By doing so you will be able to:

But if you already have single (monolithic) database this process is like converting your motorcycle into a car... while riding.

Outline

This is step-by-step guide of a a very tricky process. And the worst thing you can do is to panic because your product is collapsing under its own weight and you have a lots of pressure from clients. The whole process may take weeks, even months. Will use significant amount of human and time resources. And will pause new features development. Be prepared for that. And do not rush to the next stage until you are absolutely sure the current one is completed.

So what is the plan?

Understand your data

In monolithic database design data classification is irrelevant but it is the most crucial part of sharding design. Your tables can be divided into three groups: client, context and neutral.

Let's assume your product is car rental software and do a quick exercise:

  +----------+      +------------+      +-----------+
  | clients  |      | cities     |      | countries |
  +----------+      +------------+      +-----------+
+-| id       |   +--| id         |   +--| id        |
| | city_id  |>--+  | country_id |>--+  | name      |
| | login    |   |  | name       |      +-----------+
| | password |   |  +------------+
| +----------+   |
|                +------+
+--------------------+  |
                     |  |     +-------+
  +---------------+  |  |     | cars  |
  | rentals       |  |  |     +-------+
  +---------------+  |  |  +--| id    |
+-| id            |  |  |  |  | vin   |
| | client_id     |>-+  |  |  | brand |
| | start_city_id |>----+  |  | model |
| | start_date    |     |  |  +-------+
| | end_city_id   |>----+  |
| | end_date      |        |
| | car_id        |>-------+   +--------------------+
| | cost          |            | anti_fraud_systems |
| +---------------+            +--------------------+
|                              | id                 |--+
|      +-----------+           | name               |  |
|      | tracks    |           +--------------------+  |
|      +-----------+                                   |
+-----<| rental_id |                                   |
       | latitude  |     +--------------------------+  |
       | longitude |     | blacklisted_credit_cards |  |
       | timestamp |     +--------------------------+  |
       +-----------+     | anti_fraud_system_id     |>-+
                         | number                   |
                         +--------------------------+

Client tables

They contain data owned by your clients. To find them, you must start in some root table - clients in our example. Then follow every parent-to-child relation (only in this direction) as deep as you can. In this case we descend into rentals and then from rentals further to tracks. So our client tables are: clients, rentals and tracks.

Single client owns subset of rows from those tables, and those rows will always be moved together in a single transaction between shards.

Context tables

They put your clients data in context. To find them, follow every child-to-parent relation (only in this direction) from every client table as shallow as you can. Skip if table is already classified. In this case we ascend from clients to cities and from cities further to countries. Then from rentals we can ascend to clients (already classified), cities (already classified) and cars. And from tracks we can ascend into rentals (already classified). So our context tables are: cities, countries and cars.

Context tables should be synchronized across all shards.

Neutral tables

Everything else. They must not be reachable from any client or context table through any relation. However, there may be relations between them. So our neutral tables are: anti_fraud_systems and blacklisted_credit_cards.

Neutral tables should be moved outside of shards.

Checkpoint

Take any tool that can visualize your database in the form of a diagram. Print it and pin it on the wall. Then take markers in 3 different colors - each for every table type - and start marking tables in your schema.

If you have some tables not connected due to technical reasons (for example MySQL partitioned tables or TokuDB tables do not support foreign keys), draw this relation and assume it is there.

If you are not certain about specific table, leave it unmarked for now.

Done? Good :)

Q&A

Q: Is it a good idea to cut all relations between client and context tables, so that only two types - client and neutral - remain?

A: You will save a bit of work because no synchronization of context data across all shards will be required. But at the same time any analytics will be nearly impossible. For example, even simple task to find which car was rented the most times will require software script to do the join. Also there won't be any protection against software bugs, for example it will be possible to rent a car that does not even exist.

There are two cases when converting a context table to neutral table is justified:

In every other case it is a very bad idea to make neutral data out of context data.

Q: Is it a good idea to shard only big tables and leave all small tables together on a monolithic database?

A: In our example you have one puffy table - tracks. It keeps GPS trail of every car rental and will grow really fast. So if you only shard this data, you will save a lot of work because there will be only small application changes required. But in real world you will have 100 puffy tables and that means 100 places in application logic when you have to juggle database handles to locate all client data. That also means you won't be able to split your clients between many data centers. Also you won't be able to reduce downtime costs to 1/nth of the amount of shards if some data corruption in monolithic database occurs and recovery is required. And analytics argument mentioned above also applies here.

It is a bad idea to do such sub-sharding. May seem easy and fast - but the sooner you do proper sharding that includes all of your clients data, the better.

Fix your monolithic database

There are a few design patterns that are perfectly fine or acceptable in monolithic database design but are no-go in sharding.

Lack of foreign key

Aside from obvious risk of referencing nonexistent records, this issue can leave junk when you will migrate clients between shards later for load balancing. The fix is simple - add foreign key if there should be one.

The only exception is when it cannot be added due to technical limitations, such as usage of TokuDB or partitioned MySQL tables that simply do not support foreign keys. Skip those, I'll tell you how to deal with them during data migration later.

Direct connection between clients

Because clients may be located on different shards, their rows may not point at each other. Typical case where it happens is affiliation.

+-----------------------+
| clients               |
+-----------------------+
| id                    |------+
| login                 |      |
| password              |      |
| referred_by_client_id |>-----+
+-----------------------+

To fix this issue you must remove foreign key and rely on software instead to match those records.

Nested connection between clients

Because clients may be located on different shards their rows may not reference another client (also indirectly). Typical case where it happens is post-and-comment discussion.

  +----------+        +------------+
  | clients  |        | blog_posts |
  +----------+        +------------+
+-| id       |---+    | id         |---+
| | login    |   +---<| client_id  |   |
| | password |        | text       |   |
| +----------+        +------------+   |
|                                      |
|    +--------------+                  |
|    | comments     |                  |
|    +--------------+                  |
|    | blog_post_id |>-----------------+
+---<| client_id    |
     | text         |
     +--------------+

First client posted something and a second client commented it. This comment references two clients at the same time - second one directly and first one indirectly through blog_posts table. That means it will be impossible to satisfy both foreign keys in comments table if those clients are not in single database.

To fix this you must choose which relation from table that refers to multiple clients is more important, remove the other foreign keys and rely on software instead to match those records.

So in our example you may decide that relation between comments and blog_posts remains, relation between comments and clients is removed and you will use application logic to find which client wrote which comment.

Accidental connection between clients

This is the same issue as nested connection but caused by application errors instead of intentional design.

                    +----------+
                    | clients  |
                    +----------+
+-------------------| id       |--------------------+
|                   | login    |                    |
|                   | password |                    |
|                   +----------+                    |
|                                                   |
|  +-----------------+        +------------------+  |
|  | blog_categories |        | blog_posts       |  |
|  +-----------------+        +------------------+  |
|  | id              |----+   | id               |  |
+-<| client_id       |    |   | client_id        |>-+
   | name            |    +--<| blog_category_id |
   +-----------------+        | text             |
                              +------------------+

For example first client defined his own blog categories for his own blog posts. But lets say there was mess with www sessions or some caching mechanism and blog post of second client was accidentally assigned to category defined by first client.

Those issues are very hard to find, because schema itself is perfectly fine and only data is damaged.

Not reachable clients data

Client tables must be reached exclusively by descending from root table through parent-to-child relations.

              +----------+
              | clients  |
              +----------+
+-------------| id       |
|             | login    |
|             | password |
|             +----------+
|
|  +-----------+        +------------+
|  | photos    |        | albums     |
|  +-----------+        +------------+
|  | id        |    +---| id         |
+-<| client_id |    |   | name       |
   | album_id  |>---+   | created_at |
   | file      |        +------------+
   +-----------+

So we have photo management software this time and when a client synchronizes photos from a camera, new album is created automatically for better import visualization. This is an obvious issue even in monolithic database - when all photos are removed from album, then it becomes zombie row. It won't be deleted automatically by cascade and cannot be matched with client anymore. In sharding, this also causes misclassification of client table as context table.

To fix this issue foreign key should be added from albums to clients. This may also fix classification for some tables below albums, if any.

Polymorphic data

Table cannot be classified as two types at the same time.

              +----------+
              | clients  |
              +----------+
+-------------| id       |-------------+
|             | login    |             |
|             | password |             |
|             +----------+         (nullable)
|                                      |
|  +-----------+        +-----------+  |
|  | blogs     |        | skins     |  |
|  +-----------+        +-----------+  |
|  | id        |    +---| id        |  |
+-<| client_id |    |   | client_id |>-+
   | skin_id   |>---+   | color     |
   | title     |        +-----------+
   +-----------+

In this product client can choose predefined skin for his blog. But can also define his own skin color and use it as well.

Here single interface of skins table is used to access data of both client and context type. A lot of "let's allow client to customize that" features end up implemented this way. While being a smart hack - with no table schema duplication and only simple WHERE client_id IS NULL OR client_id = 123 added to query to present both public and private templates for client - this may cause a lot of trouble in sharding.

The fix is to go with dual foreign key design and separate tables. Create constraint (or trigger) that will protect against assigning blog to public and private skin at the same time. And write more complicated query to get blog skin color.

              +----------+
              | clients  |
              +----------+
+-------------| id       |
|             | login    |
|             | password |
|             +----------+
|
|   +---------------+        +--------------+
|   | private_skins |        | public_skins |
|   +---------------+        +--------------+
|   | id            |--+  +--| id           |
+--<| client_id     |  |  |  | color        |
|   | color         |  |  |  +--------------+
|   +---------------+  |  |    
|                      |  |
|                   (nullable)
|                      |  |
|                      |  +------+
|                      +-----+   |
|                            |   |
|       +-----------------+  |   |
|       | blogs           |  |   |
|       +-----------------+  |   |
|       | id              |  |   | 
+------<| client_id       |  |   |
        | private_skin_id |>-+   |
        | public_skin_id  |>-----+
        | title           |
        +-----------------+

However - this fix is optional. I'll show you how to deal with maintaining mixed data types in chapter about mutually exclusive IDs. It will be up to you to decide if you want less refactoring but more complicated synchronization.

Beware! Such fix may also accidentally cause another issue described below.

Opaque uniqueness (a.k.a. horse riddle)

Every client table without unique constraint must be reachable by not nullable path of parent-to-child relations or at most single nullable path of parent-to-child relations. This is very tricky issue which may cause data loss or duplication during client migration to database shard.

              +----------+
              | clients  |
              +----------+
+-------------| id       |-------------+
|             | login    |             |
|             | password |             |
|             +----------+             |
|                                      |
|  +-----------+        +-----------+  |
|  | time      |        | distance  |  |
|  +-----------+        +-----------+  |
|  | id        |--+  +--| id        |  |
+-<| client_id |  |  |  | client_id |>-+
   | amount    |  |  |  | amount    |
   +-----------+  |  |  +-----------+
                  |  |
               (nullable)
                  |  |
                  |  |
         +--------+  +---------+
         |                     |
         |   +-------------+   |
         |   | parts       |   |
         |   +-------------+   |
         +--<| time_id     |   |
             | distance_id |>--+
             | name        |
             +-------------+

This time our product is application that helps you with car maintenance schedule. Our clients car has 4 tires that must be replaced after 10 years or 100000km and 4 spark plugs that must be replaced after 100000km. So 4 indistinguishable rows for tires are added to parts table (they reference both time and distance) and 4 indistinguishable rows are added for spark plugs (they reference only distance).

Now to migrate client to shard we have to find which rows from parts table does he own. By following relations through time table we will get 4 tires. But because this path is nullable at some point we are not sure if we found all records. And indeed, by following relations through distance table we found 4 tires and 4 spark plugs. Since this path is also nullable at some point we are not sure if we found all records. So we must combine result from time and distance paths, which gives us... 8 tires and 4 spark plugs? Well, that looks wrong. Maybe let's group it by time and distance pair, which gives us... 1 tire and 1 spark plug? So depending how you combine indistinguishable rows from many nullable paths to get final row set, you may suffer either data duplication or data loss.

You may say: Hey, that's easy - just select all rows through time path, then all rows from distance path that do not have time_id, then union both results. Unfortunately paths may be nullable somewhere earlier and several nullable paths may lead to single table, which will produce bizarre logic to get indistinguishable rows set properly.

To solve this issue make sure there is at least one not nullable path that leads to every client table (does not matter how many tables it goes through). Extra foreign key should be added between clients and part in our example.

TL;DR

Q: How many legs does the horse have?

A1: Eight. Two front, two rear, two left and two right.

A2: Four. Those attached to it.

Foreign key to not unique rows

MySQL specific issue.

CREATE TABLE `foo` (
  `id` int(10) unsigned DEFAULT NULL,
  KEY `id` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `bar` (
  `foo_id` int(10) unsigned NOT NULL,
  KEY `foo_id` (`foo_id`),
  CONSTRAINT `bar_ibfk_1` FOREIGN KEY (`foo_id`) REFERENCES `foo` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

mysql> INSERT INTO `foo` (`id`) VALUES (1);
Query OK, 1 row affected (0.01 sec)

mysql> INSERT INTO `foo` (`id`) VALUES (1);
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `bar` (`foo_id`) VALUES (1);
Query OK, 1 row affected (0.01 sec)

Which row from foo table is referenced by row in bar table?

You don't know because behavior of foreign key constraint is defined as "it there any parent I can refer to?" instead of "do I have exactly one parent?". There are no direct row-to-row references as in other databases. And it's not a bug, it's a feature.

Of course this causes a lot of weird bugs when trying to locate all rows that belong to given client, because results can be duplicated on JOINs.

To fix this issue just make sure every referenced column (or set of columns) is unique. They must not be nullable and must all be used as primary or unique key.

Self loops

Rows in the same client table cannot be in direct relation. Typical case is expressing all kinds of tree or graph structures.

+----------+
| clients  |
+----------+
| id       |----------------------+
| login    |                      |
| password |                      |
+----------+                      |
                                  |
          +--------------------+  |
          | albums             |  |
          +--------------------+  |
      +---| id                 |  |
      |   | client_id          |>-+
      +--<| parent_album_id    |
          | name               |
          +--------------------+

This causes issues when client data is inserted into target shard.

For example in our photo management software client has album with id = 2 as subcategory of album with id = 1. Then he flips this configuration, so that the album with id = 2 is on top. In such scenario if database returned client rows in default, primary key order then it won't be possible to insert album with id = 1 because it requires presence of album with id = 2.

Yes, you can disable foreign key constraints to be able to insert self-referenced data in any order. But by doing so you may mask many errors - for example broken references to context data.

For good sharding experience all relations between rows of the same table should be stored in separate table.

+----------+
| clients  |
+----------+
| id       |----------------------+
| login    |                      |
| password |                      |
+----------+                      |
                                  |
          +--------------------+  |
          | albums             |  |
          +--------------------+  |
  +-+=====| id                 |  |
  | |     | client_id          |>-+
  | |     | name               |
  | |     +--------------------+
  | |
  | |    +------------------+
  | |    | album_hierarchy  |
  | |    +------------------+
  | +---<| parent_album_id  |
  +-----<| child_album_id   |
         +------------------+

Triggers

Triggers cannot modify rows. Or roar too loud :)

            +----------+
            | clients  |
            +----------+
 +----------| id       |------------------+
 |          | login    |                  |
 |          | password |                  |
 |          +----------+                  |
 |                                        |
 |  +------------+        +------------+  |
 |  | blog_posts |        | activities |  |
 |  +------------+        +------------+  |
 |  | id         |        | id         |  |
 +-<| client_id  |        | client_id  |>-+
    | content    |        | counter    |
    +------------+        +------------+
          :                      :
          :                      :
 (on insert post create or increase activity)

This is common usage of a trigger to automatically aggregate some statistics. Very useful and safe - doesn't matter which part of application adds new blog post, activities counter will always go up.

However, when sharding this causes a lot of trouble when inserting client data. Let's say he has 4 blog posts and 4 activities. If posts are inserted first they bump activity counter through trigger and we have collision in activties table due to unexpected row. When activities are inserted first they are unexpectedly increased by posts inserts later, ending with invalid 8 activities total.

In sharding triggers can only be used if they do not modify data. For example it is OK to do sophisticated constraints using them. Triggers that modify data must be removed and their logic ported to application.

Checkpoint

Check if there are any issues described above in your printed schema and fix them.

And this is probably the most annoying part of sharding process as you will have to dig through a lot of code. Sometimes old, untested undocumented and unmaintained.

When you are done your printed schema on the wall should not contain any unclassified tables.

Ready for next step?

Prepare schema

It is time to dump monolithic database complete schema (tables, triggers, views and functions/procedures) to the shard_schema.sql file and prepare for sharding environment initialization.

Separate neutral tables

Move all tables that are marked as neutral from shard_schema.sql file to separate neutral_schema.sql file. Do not forget to also move triggers, views or procedures associated with them.

Bigints

Every primary key on shard should be of unsigned bigint type. You do not have to modify your existing schema installed on monolithic database. Just edit shard_schema.sql file and massively replace all numeric primary and foreign keys to unsigned big integers. I'll explain later why this is needed.

Create schema for dispatcher

Dispatcher tells on which shard specific client is located. Absolute minimum is to have table where you will keep client id and shard number. Save it to dispatch_schema.sql file.

More complex dispatchers will be described later.

Dump common data

From monolithic database dump data for neutral tables to neutral_data.sql file and for context tables to context_data.sql file. Watch out for tables order to avoid breaking foreign keys constraints.

Checkpoint

You should have shard_schema.sql, neutral_schema.sql, dispatch_schema.sql, neutral_data.sql and context_data.sql files.

At this point you should also freeze all schema and common data changes in your application until sharding is completed.

Set up environment

Finally you can put all those new, shiny machines to good use.

Typical sharding environment contains of:

Each database should of course be replicated.

Database for neutral data

Nothing fancy, just regular database. Install neutral_schema.sql and feed neutral_data.sql to it.

Make separate user for application with read-only grants to read neutral data and separate user with read-write grants for managing data.

Database for dispatch

Every time client logs in to your product you will have to find which shard he is located on. Make sure all data fits into RAM, have a huge connection pool available. And install dispatch_schema.sql to it.

This is a weak point of all sharding designs. Should be off-loaded by various caches as much as possible.

Databases for shards

They should all have the same power (CPU/RAM/IO) - this will speed things up because you can just randomly select shard for your new or migrated client without bothering with different hardware capabilities.

Configuration of shard databases is pretty straightforward. For every shard just install shard_schema.sql, feed context_data.sql file and follow two more steps.

Databases for shards - users

Remember that context tables should be identical on all shards. Therefore it is a good idea to have separate user with read-write grants for managing context data. Application user should have read-only access to context tables to prevent accidental context data change.

This ideal design may be too difficult to maintain - every new table will require setting up separate grants. If you decide to go with single user make sure you will add some mechanism that monitors context data consistency across all shards.

Databases for shards - mutually exclusive primary keys

Primary keys in client tables must be globally unique across whole product.

First of all - data split is a long process. Just pushing data between databases may take days or even weeks! And because of that it should be performed without any global downtime. So during monolithic to shard migration phase new rows will still be created in monolithic database and already migrated users will create rows on shards. Those rows must never collide.

Second of all - sharding does not end there. Later on you will have to load balance shards, move client between different physical locations, backup and restore them if needed. So rows must never collide at any time of your product life.

How to achieve that? Use offset and increment while generating your primary keys.

MySQL has ready to use mechanism:

Now your first shard for any table will generate 1, 101, 201, 301, ... , 901, 1001, 1101 auto increments and second shard will generate 2, 102, 202, 302, ... , 902, 1002, 1102 auto increments. And that's all! Your new rows will never collide, doesn't matter which shard they were generated on and without any communication between shards needed.

TODO: add recipes for another database types

Now you should understand why I've told you to convert all numerical primary and foreign keys to unsigned big integers. The sequences will grow really fast, in our example 100x faster than on monolithic database.

Remember to set the same increment and corresponding offsets on replicas. Forgetting to do so will be lethal to whole sharding design.

Checkpoint

Your database servers should be set up. Check routings from application, check user grants. And again - remember to have correct configurations (in puppet for example) for shards and their replicas offsets. Do some failures simulations.

And move to the next step :)

Q&A

Q: Can I do sharding without dispatch database? When client wants to log in I can just ask all shards for his data and use the one shard that will respond.

A: No. This may work when you start with three shards, but when you have 64 shards in 8 different data centers such fishing queries become impossible. Not to mention you will be very vulnerable to brute-force attacks - every password guess attempt will be multiplied by your application causing instant overload of the whole infrastructure.

Q: Can I use any no-SQL technology for dispatch and neutral databases?

A: Sure. You can use it instead of traditional SQL or as a supplementary cache.

Adapt code

Product

There will be additional step in your product. When user logs in then dispatch database must be asked for shard number first. Then you connect to this shard and... it works! Your code will also have to use separate database connection to access neutral data. And it will have to roll shard when new client registers and note this selection in dispatch database.

That is the beauty of whole clients sharding - majority of your code is not aware of it.

Synchronization of common data

If you modify neutral data this change should be propagated to every neutral database (you may have more of those in different physical locations).

Same thing applies to context data on shard, but all auto increment columns must be forced. This is because every shard will generate different sequence. When you execute INSERT INTO skins (color) VALUES ('#AA55BC') then shard 1 will assign different IDs for them than shard 2. And all client data that reference this language will be impossible to migrate between shards.

Dispatch

Dispatch serves two purposes. It allows you to find client on shard by some unique attribute (login, email, and so on) and it also helps to guarantee such uniqueness. So for example when new client is created then dispatch database must be asked if chosen login is available. Take an extra care of dispatch database. Off-load as much as you can by caching and schedule regular consistency checks between it and the shards.

Things get complicated if you have shards in many data centers. Unfortunately I cannot give you universal algorithm of how to keep them in sync, this is too much application specific.

Analytic tools

Because your clients data will be scattered across multiple shard databases you will have to fix a lot of global queries used in analytical and statistical tools. What was trivial previously - for example SELECT city.name, COUNT(*) AS amount FROM clients JOIN cities ON clients.city_id = cities.id GROUP BY city.name ORDER BY amount DESC LIMIT 8 - will now require gathering all data needed from shards and performing intermediate materialization for grouping, ordering and limiting.

There are tools that helps you with that. I've tried several solutions, but none was versatile, configurable and stable enough that I could recommend it.

Make a wish-ard

We got to the point when you have to switch your application to sharding flow. To avoid having two versions of code - old one for still running monolithic design and a new one for sharding, we will just connect monolithic database as another "fake" shard.

First you have to deal with auto increments. Set up in the configuration the same increment on your monolithic database as on shards and set up any free offset. Then check what is the current auto increment value for every client or context table and set the same value for this table located on every shard. Now your primary keys won't collide between "fake" and real shards during the migration. But beware: this can easily overflow tiny or small ints in your monolithic database, for example just adding three rows can overflow tiny int unsigned capacity of 255.

After that synchronize data on dispatch database - every client you have should point to this "fake" shard. Deploy your code changes to use dispatch logic.

Checkpoint

You should be running code with complete sharding logic but on reduced environment - with only one "fake" shard made out of your monolithic database. You may also already enable creating new client accounts on your real shards.

Tons of small issues to fix will pop up at this point. Forgotten pieces of code, broken analytics tools, broken support panels, need of neutral or dispatch databases tune up.

And when you squash all the bugs it is time for grande finale: clients migration.

Migrate clients to shards

Downtime semaphore

You do not need any global downtime to perform clients data migration. Disabling your whole product for a few weeks would be unacceptable and would cause huge financial loses. But you need some mechanism to disable access for individual clients while they are migrated. Single flag in dispatch databases should do, but your code should be aware of it and present nice information screen for client when he tries to log in. And of course do not modify clients data.

Timing

If you have some history of your client habits - use it. For example if client is usually logging in at 10:00 and logging out at 11:00 schedule his migration to another hour. You may also figure out which timezones clients are in and schedule migration for the night for each of them. The migration process should be as transparent to client as possible. One day he should just log in and bam - fast and responsive product all of a sudden.

Exodus tool

Exodus was the tool used internally at GetResponse.com to split monolithic database into shards. And is still used to load balance sharding environment. It allows to extract subset of rows from relational database and build series of queries that can insert those rows to another relational database with the same schema.

Fetch Exodus.pm and create exodus.pl file in the same directory with the following content:

#!/usr/bin/env perl

use strict;
use warnings;

my $database = DBI->connect(
    'DBI:mysql:database=test;host=localhost',
    'root', undef,
    {'RaiseError' => 1}
);

my $exodus = Exodus->new(
    'database' => $database,
    'root'     => 'clients',
);

$exodus->extract( 'id' => 1 );

Of course provide proper credentials to connect to your monolithic database.

Now when you call the script it will extract all data for client represented by record of id = 1 in clients root table. You can directly pipe it to another database to copy the client there.

./exodus.pl | mysql --host=my-shard-1 --user=....

Update dispatch shard for this client, check that product works for him and remove his rows from monolithic database.

Repeat for every client.

MySQL issues

Do not use user with SUPER grant to perform migration. Not because it is unsafe, but because they do not have locales loaded by default. You may end up with messed character encodings if you do so.

MySQL is quite dumb when it comes to cascading DELETE operations. If you have such schema

            +----------+
            | clients  |
            +----------+
 +----------| id       |----------------+
 |          | login    |                |
 |          | password |                |
 |          +----------+                |
 |                                      |
 |  +-----------+        +-----------+  |
 |  | foo       |        | bar       |  |
 |  +-----------+        +-----------+  |
 |  | id        |----+   | id        |  |
 +-<| client_id |    |   | client_id |>-+
    +------------+   +--<| foo_id    |
                         +----------+

and all relations are ON DELETE CASCADE then sometimes it cannot resolve proper order and may try to delete data from foo table before data from bar table, causing constraint error. In such cases you must help it a bit and manually delete clients data from bar table before you will be able to delete row from clients table.

Virtual foreign keys

Exodus allows you to manually add missing relations between tables, that couldn't be created in the regular way for some reasons (for example table engine does not support foreign keys).

my $exodus = Exodus->new(
    'database' => $dbh,
    'root' => 'clients',
    'relations' => [
        {
            'nullable'      => 0,
            'parent_table'  => 'foo',
            'parent_column' => 'id'
            'child_table'   => 'bar',
            'child_column'  => 'foo_id',
        },
        { ... another one ...}
    ]
);

Note that if foreign key column can be NULL such relation should be marked as nullable.

Also remember to delete rows from such table when your client migration is complete. Due to lack of foreign key it won't auto cascade.

Cleanup

When all of your clients are migrated simply remove your "fake" shard from infrastructure.

Exodus roadmap

I have a plans of refactoring this code to Perl 6 (it was prototyped in Perl 6, although back in the days when GetResponse introduced sharding Perl 6 was not fast or stable enough to deal with terabytes of data). It should get proper abstracts, more engines support and of course good test suite.

YAPC NA 2016 "Pull request challenge" seems like a good day to begin :)

Contact

If you have any questions about database sharding or want to contribute to this guide or Exodus tool contact me in person or on IRC as "bbkr".

Final screen

YOU'VE PROVEN TOO TOUGH FOR [monolithic database design] HELL TO CONTAIN

(DOOM quote)

Strangely Consistent: Train tracks

Published by Carl Mäsak

I don't know anything, but I do know that everything is interesting if you go into it deeply enough. — Richard Feynman

Someone gives you a box with these pieces of train track:

It's possible you quickly spot the one obvious way to put these pieces into one single train track:

But... if you're like me, you might stop and wonder:

Is that the only possible track? Or is there some equally possible track one could build?

I don't just mean the mirror image of the track, which is obviously a possibility but which I consider equivalent:

I will also not be interested in complete tracks that fail to use all of the pieces:

I would also reject all tracks that are physically impossible because of two pieces needing to occupy the same points in space. The only pieces which allow intersections even in 2D are the two bridge pieces, which allow something to pass under them.

I haven't done the search yet. I'm writing these words without first having written the search algorithm. My squishy, unreliable wetware is pretty certain that the obvious solution is the only one. I would love to be surprised by a solution I didn't think of!

Here goes.

Yep, I was surprised. By no less than nine other solutions, in fact. Here they are.

I really should have foreseen most of those solutions. Here's why. Already above the fold I had identified what we could call the "standard loop":

This one is missing four curve pieces:

But we can place them in a zig-zag configuration...

...which work a little bit like straight pieces in that they don't alter the angle. And they only cause a little sideways displacement. Better yet, they can be inserted into the standard loop so they cancel each other out. This accounts for seven solutions:

If we combine two zig-zag pieces in the following way:

...we get a piece which can exactly cancel out two orthogonal sets of straight pieces:

This, in retrospect, is the key to the final two solutions, which can now be extended from the small round track:

If I had required that the track pass under the bridge, then we are indeed back to only the one solution:

(But I didn't require that, so I accept that there are 10 solutions, according to my original search parameters.)

But then reality ensued, and took over my blog post. Ack!

For fun, I just randomly built a wooden train track, to see if it was on the list of ten solutions. It wasn't.

When I put this through my train track renderer, it comes up with a track that doesn't quite meet up with itself:

But it works with the wooden pieces. Clearly, there is some factor here that we're not really accounting for.

That factor turns out to be wiggle, the small amounts that two pieces can shift and rotate around the little connector that joins them:

Since there are sixteen pieces, there are sixteen connection points where wiggle can occur. All that wiggle adds up, which explains how the misrendered tack above can be made to cleanly meet up with itself.

Think of the gap in the misrendered track as a 2D vector (x, y). What was special about the ten solutions above is that they had a displacement of (0, 0). But there are clearly other small but non-zero displacements that wiggle can compensate for, leading to more working solutions.

How many working solutions? Well, armed with the new understanding of displacements-as-vectors, we can widen the search to tolerate small displacements, and then plot the results in the plane:

That's 380 solutions. Now, I hasten to add that not all of those are possible. At least one solution that I tried actually building turned out to be impossible because the track tried to run into itself in an unfixable way.

With yet another 8-shaped solution, I had given up trying to make it work because it seemed there was too much displacement. Then my wife stopped by, adjusted some things, and voilà! — it worked. (She had the idea to run the track through one of the small side-tunnels under the bridge; something that hadn't occurred to me at all. There's no way to run a wooden train through that small tunnel, but that also wasn't something I restricted up front. Clearly the track itself is possible.)

Anyway, I really enjoyed how this problem turned out to have a completely solvable constraint-programming core of 10 solutions, but then also a complete fauna — as yet largely unclassified — of approximate, more-or-less buildable solutions around it. All my searching and drawing can be found in this Github repository — others who wish to experiment may want to start from the ideas in there, rather than from scratch.

Essentially, all models are wrong, but some are useful. — George E. P. Box

brrt to the future: In praise of incremental change

Published by Bart Wiegmans on 2016-06-04T17:01:00

Hi everybody, welcome back. I'd like to share with you the things that have been happening in the MoarVM JIT since I've last posted, which was in fact March. To be brief, the JIT has been adapted to deal with moving frames, and I've started to rewrite the register allocator towards a much better design, if I do say so myself.

First, moving frames. jnthn has already written quite a bit about them. The purpose of it is to make the regular case of subroutine invocation cheaper by making special cases - like closures and continuations - a bit more expensive. I have nothing to add to that except that this was a bit of a problem for the JIT compiler. The JIT compiler liked to keep the current frame in a non-volatile register. These are CPU registers which are supposed not to be overwritten when you call a function. This is useful because it speeds up access of frequently used values. However, if the current frame object is be moved, the frame pointer in this register becomes stale. Thus, it had to go, and now we load the frame pointer from the thread context object (i.e. in memory), which never moves.

Unfortunately, that was not sufficient. Because MoarVM is an interpreter, control flow (like returning from a routine) is implemented updating the pointer to the next instruction (and the next frame). JIT compiled code never deals with this instruction pointer. Hence, whenever this instruction pointer could have been updated - we call this invokish or throwish code - the JIT may need to return control to the interpreter, which can then figure out what to do next. Originally, this had been implemented by comparing the frame pointer of the JIT frame - stored in the non-volatile register - with the frame pointer as understood by the interpreter - i.e., in the thread context object. This check no longer worked, because a): we didn't have a permanent pointer to the current frame anymore, and b): the current frame pointer might change for two different reasons, namely control flow and object movement.

I figured out a solution to this issue when I realized that what we really needed is a way to identify (cheaply) in the JIT whether or not we have changed control flow, i.e. whether we have entered another routine or returned out of the current one. This might be achieved by comparing immutable locations, but lacking those, another method is to simply assign increasing numbers to constructed frames. Such a sequence number then identifies the current position in the control flow, and whenever it is changed the JIT knows to return control to the interpreter. This caused some issues at first when I hadn't correctly updated the code in all places where the interpreter changed the current instruction, but afterwards it worked correctly. Special thanks go to lizmat who allowed me to debug this on Mac OS X, where it was broken.

Afterwards, I've focused on improving the register allocator. The primary function of a register allocator is to ensure that the values used in a calculations are placed in (correct) registers prior to that calculation. This involves, among other things, assigning the correct registers (some operations only work on specific registers), spilling registers to memory in order to make place, loading spilled values from memory if necessary, and ensuring that values in volatile registers are spilled prior to a function call. This was rather difficult because in the old design because, as it was inlined into the compilation step, it  couldn't really look behind or ahead, which is a problem if you want to place something correctly for future use. Furthermore, it allowed only for a one-on-one correspondence between a value that was computed and its current location in a register. That is a problem whenever -a value is copied to a different register, or stored in multiple memory locations.

So I've been, very slowly and methodically, in very small steps, moving code and structures through the JIT compiler in order to arrive at a register allocator that can handle these things. The first thing I did was remove the register allocation step out of compilation, into its own step (commit and another commit). Then I extracted the value descriptor structure - which describes in which location a value is stored - out of the expression tree (commit). I stored the tile list in a vector, in order to allow reverse and random access (commit). Because the register allocator works in a single pass and only requires temporary structures, I've 'internalized' it to its own file (commit one and commit two). Finally, I replaced the per-expression value structure with value descriptor structures (commit).

This places me in a position to replace register allocator structures (such as the active stack with an expiry heap), implement loads and stores, record register requirements per tile, implement pre-coloring, and correct allocation over basic blocks. All these things were impossible, or at least very difficult, with the old design.

What I think is interesting here is that in each of these commits, the logic of the program didn't substantially change, and the JIT continued to just as well as it had before. Nevertheless, all of this is progress - I replaced a rather broken design assumption (online register allocation with a value state machine) with another (offline register allocation with value descriptors) - that allows me to implement the necessary mechanics in a straightforward manner. And that, I think, demonstrates the power of incremental changes.

Independent Computing: Stock Tracker

Published by Michael on 2016-05-05T05:06:32

Stock Tracker

Today I completed a simple program to download stock pricing information. This Perl6 program takes a list of stock symbols and utilizes the Yahoo.com Finance WebService API and retrieves the current day's closing stock price. This data is then saved into a text file in my clDB database format.

Stock Tracker

Perl6 modules to the rescue

Using the HTTP::Tinyish Perl6 Module, I craft a HTTP Get request to the finance.yahoo.com WebService. In my request I state that I want the Name, stock symbol and the closing price for the current day to be returned for each stock listed.

I use the crontab service on my server to run the program every day at 1330 and grab the closing price for the stocks.

For now I have the output sent to a text file using the clDB data format. At this point I can use another program to analyze the data or even make an an SVG chart graphic. This will be a separate program I will work on latter.

Stock Tracker

Inside the Code

In this program I use the .trans and .split methods to clean up the data returned from the Yahoo.com WebService.
On line 25, @data = $line.trans(' " ' => '', :delete).split(","); takes the current text in the $line Variable and transliterats the quotes (") character and replaces it with nothing, basically removing it. Then using the .split method, it takes that and splits it every time it finds a comma (,) character. The results end up as elements in the @data array, which I then use when I craft the $dataString which gets appended (Line 27) to the output file.

Transliterate is a very useful method provide by the Str class more info and examples can be found here at the Perl6 documentation page.

Sample output

The results of of the entire process can be seen on the page listed below.
View the results of the code here

rakudo.org: Announce: Windows (64 bit) Installer for Rakudo Star 2016.04

Published by Steve Mynott on 2016-05-03T21:05:34

A Windows MSI installer is now available for x86_64 (64bit) platforms (probably Windows 7 or better) and has the JIT (Just in Time compiler) enabled.  This version was built with mingw (from Strawberry Perl) rather than the usual MSVC which may have performance implications. In order to use the module installer “panda” you will also need to install Strawberry Perl and Git for Windows. Also see http://www.perl6.org/downloads/ for Errata notices concerning panda.

Unfortunately the usual second installer targeting x86 (32bit) platforms isn’t currently available.  It’s hoped this will be available in the near future and until then the previous 2016.01 is recommended for x86 (32bit). No 32 bit versions feature the JIT. MSIs are available from http://rakudo.org/downloads/star/.

Strangely Consistent: Trinity

Published by Carl Mäsak

Lately, driven by a real itch I wanted to scratch, I finally wrote my first Perl 6 web app since the November wiki engine. (That was back in 2008. Very early days. I distinctly recall Rakudo didn't have a does-file-exist feature yet.)

Because I'm me, naturally the web app is a game. A board game. The details don't matter for this article — if you're curious, go check out the README. If you're not, I forgive you. It's just a game with a board and stones of various colors.

Here's the order in which I wrote the web app. The first thing I made work was a model, literally the game itself.

image of the model in the middle

This is the core, the heart of the application. A Games::Nex instance models the progress of a game, and the rules of Nex are encoded in this type's "algebra". Naturally, this was developed test-first, because it would be reckless not to. This is the essence of masakism: "testing gets you far" and "keep it small and simple". Eliminate all other factors, and the one which remains must be the model at the core.

The core domain is nice, but it doesn't have any face. By design, it's just mind stuff. I wanted it to be a web app, so the next reasonable step was to add a Bailador app that could show the board and allow moves to be tried on it.

image of the app+model in the middle

Of course, when you run it — it's a web app — the result turns up in your browser, as you're expect.

image of browser <--- app+model

And when you make a move by interacting with the web page, the browser goes "Hey, app! Yo! Do some stuff!"

image of browser ---> app+model

None of this is news to you, I'm sure. My point so far though is that we're now up to two environments. Two separate runloops. It has to be that way, because — in every single case except the crazy one where I am you — the server and the client will be two different computers. The GET and POST requests and their responses are simply client and server shouting to each other across the network.

Now my app had a face but no long-term memory. Every move was against an empty game board; you made it, and all traces of it disappeared into the great data limbo.

Time to add (you guessed it) a database backend:

image of browser <---> app+model <---> db

(Postgres is great, by the way. Highly recommended. Makes me feel happy just thinking about it. Mmm, Postgres.)

The database also sits in its own, separate runloop. Maybe — probably — on its own machine, too. So we have three environments.

It was at this point I felt that something was... well not wrong exactly, but odd...

<masak> I was struck by not just how wide apart the database world is from
        the server backend world, but also how wide apart the [browser]
        world is from the server backend world
<masak> you're writing three separate things, and making them interoperate
<masak> I almost feel like writing a blog post about that

Coke insightfully quipped:

<[Coke]> this reads like you discovered a 3-tier web app.

And yes, that is the name for it. Freakin' three-tier. Love those bloody tiers. Like a hamburger, but instead of meat, you got a tier, and not in bread as usual, but between two more tiers!

I have a subtle point I want to make with this post, and we're now getting to it. I'm well aware of how good it is to separate these three tiers. I teach a software architecture course several times yearly, and we've made a point to be clear about that: the model in the middle should be separated, nay, insulated, from both UI and DB. Why? Because UI layers come and go. First it's a desktop client, some years later it's a responsive Web 2.0 snazzle-pot of janky modernity, and surely in a few more decades we'll all be on VR and telepathy. Throughout all this, the model can stay the same, unfazed. Ditto the database layer; you go from RDBMS to NoSQL back to PffyeahSQL to an in-memory database to post-it-notes on the side of your screen. The model abides.

And yet... I want to make sure I'm building a single monolithic system, not three systems which just happen to talk to each other. That's my thesis today: even in a properly factored three-tier system, it's one system. If we don't reflect that in the architecture, we have problems.

If you have three tiers I feel bad for you son / I got 99 problems but message passing ain't one

So, just to be abundantly clear: the three tiers are good — besides being a near-necessity. The web is practically dripping with laud and praise of three-tier:

By segregating an application into tiers, developers acquire the option of modifying or adding a specific layer, instead of reworking the entire application. — Wikipedia

During an application's life cycle, the three-tier approach provides benefits such as reusability, flexibility, manageability, maintainability, and scalability. — Windows Dev Center

Three-tier architecture allows any one of the three tiers to be upgraded or replaced independently. — Technopedia

It's against this unisonal chorus of acclaim that I'm feeling that some kind of balancing force is missing and never talked about. Why am I writing three things again? I'm down in the database, I'm writing code in my model and my app, and I'm away writing front-end JavaScript, and they are basically unrelated. Or rather, they are only related because I tend to remember that they should be.

I think it's especially funny that I didn't really choose the three-tier model along the way. It was forced upon me: the browser is a separate thing from the server, and the database engine is a separate thing from the app. I didn't make it so! Because I didn't make that design decision, it's also not something to be proud of afterwards. "Ah, look how nice I made it." When everyone keeps repeating how good it is with a software architecture that's not a choice but a fact of the territory, it sounds a bit like this:

Potholes in the road allow us to slow down and drive more carefully, making our roads safer. — no-one, ever

Maybe we can close our eyes and imagine a parallel universe where some enlightened despot has given us the ultimate language Trinity, which encompasses all three tiers, and unites all concerns into one single conceptual runloop, one single syntax, and one single monolithic application. Sure, we still do DB and frontend stuff, but it's all the same code base, and incidentally it's so devoid of incidental complexity, that pausing to think about it will invariably make us slightly misty-eyed with gratitude.

Would that work? I honestly don't know. It might. We don't live in that universe, but I sure wouldn't mind visiting, just to see what it's like.

One very good argument that I will make at this point, before someone else makes it for me, is that the three tiers actually handle three very different concerns. Basically:

These differences go deep, to the point where each tier has a quite specialized/different view of the world. To wit:

But it doesn't end there. The three tiers also have very typical, well-defined relations to each other.

And I haven't even started talking about synchronous/asynchronous calls, timeouts, retries, optimistic UIs, user experience, contention, conflicts, events pushed from the server, message duplication, and error messages.

I guess my point is that however Trinity looks, it has a lot on its plate. I mean, it's wonderful that a Trinity system is one single application, and things that ought to be close to each other in code can be... but there's still a lot of concerns. Sometimes the abstraction leaks. You can practically see that server-code block glare in paranoid suspicion at that client-code block. And, while Trinity of course has something much more unified than SQL syntax, sometimes you'd feel a little bump in the floor when transitioning from model code to DB code.

But I could imagine liking Trinity a lot. Instead of writing one page Perl 6 and two pages JavaScript, I'd just implement the code once in Trinity. Instead of describing the model once for the server and once for the database, I'd just describe it once. Parallel universe, color me jealous.

But back to our world with three inevitable tiers. I've been thinking about what would make me feel better about the whole ui-app-db impedance mismatch. And, I haven't tried it out yet, but I've decided I want to borrow a leaf from 007 development. In 007, basically when we've found things that might go wrong during development, we've turned those things into tests. These are not testing the behavior of the system, but the source code itself. Call them consistency tests. We really like them; they make us feel ridiculous for making silly consistency mistakes, but also grateful that the test suite caught them before we pushed. (And if we accidentally push, then TravisCI notifies us that the branch is failing.)

What needs testing? As so often, the interfaces. In this case, the surface areas between frontend/app, and between app/database.

image of browser <-|-> app+model <-|-> db

Here's what I'm imagining. The frontend and app are only allowed to talk to each other in certain pre-approved ways. The tests make sure that each source file doesn't color outside of the line. (Need to make that code analysis robust enough.) Ditto with the app and database.

I figure I could use something pre-existing like Swagger for the frontend/app interaction. For the app/db interaction, actually using the database schema itself as the canonical source of truth seems like a decent idea.

Maybe it makes sense to have both static tests (which check the source code), and runtime tests (which mock the appropriate components and check that the results match in practice). Yes, that sounds about robust enough. (I'm a little unsure how to do this with the client code. Will I need to run it headless, using PhantomJS? Will that be enough? I might need to refactor just to expose the right kind of information for the tests.)

That would give me confidence that I'm not breaking anything when I'm refactoring my game. And it might make me feel a little bit better about the Trinity language being in a parallel universe and not in this one.

I might write a follow-up post after I've tried this out.

rakudo.org: Announce: Mac OS X Installer for Rakudo Star 2016.04

Published by Steve Mynott on 2016-04-27T14:13:45

A Mac OS X installer is now available. This installer has the “.dmg” file extension and is available from http://rakudo.org/downloads/star/rakudo-star-2016-04.dmg

Steve Mynott: German Perl Workshop 2016

Published by Steve Mynott on 2016-03-15T15:36:12

The meeting first night was in a large beer bar in the centre of Nuremberg.
We went back to the Best Western to find a certain exPumpkin already resident in the bar.
Despite several of the well named Bitburgers we managed to arrive at the
conference venue on time the following morning. Since my knowledge of German was
limited to a C grade 'O' Level last century my review talks will be mostly
limited to English talks. Apologies in advance to those giving German talks
(not unreasonable considering the country). Hopefully other blog posts will
cover these.

Masak spoke about the dialectic between planning (like physics) and chaos (like
biology) in software development.

http://masak.org/carl/gpw-2016-domain-modeling/talk.pdf

Tobias gave a good beginners guide to Perl 6 in German and I was able to follow
most of the slides since I knew more Perl 6 than German and even learnt a thing
or two.

After lunch Stefan told us he was dancing around drunk and naked on the turn of
the 2000s and also about communication between Perl 6 and Perl 5 and back again
via his modules Inline::Perl5 (from Perl 6) -- the most important take away
being that "use Foo::Bar:from<Perl5>" can be used from Perl 6 and "use
Inline::Perl6" from Perl 5. The modules built bridges like those built in the
old school computer game "Lemmings".

http://niner.name/talks/Perl%205%20and%20Perl%206%20-%20a%20great%20team/Perl%205%20and%20Perl%206%20-%20a%20great%20team.odp

Max told us (in German) about his Dancer::SearchApp search
engine which has based on Elastic Search but I was able to follow along on the
English version of his slides on the web.

http://corion.net/talks/dancer-searchapp/dancer-searchapp.en.html

Sue got excited about this. Tina showed us some slides in Vim and her module
to add command line tab completion to script arguments using zsh and bash. I
wondered whether some of her code could be repurposed to add fish shell man
page parsing autocompletion to zsh. She also had a good lightening talk about
Ingy's command line utility for github.

https://github.com/perlpunk/myslides/tree/master/app-spec

Second day started early with Moritz talking about Continuous Delivery which
could mean just delivering to a staging server. He was writing a book about it
at deploybook.com with slides at:

https://deploybook.com/talks/gpw2016-continuous-delivery.pdf

Salve wanted us to write elegant code as a reply to the Perl Jam guy at CCC in
a self confessed "rant".

Sawyer described writing Ref::Util to optimise things like "ref $foo" in a
Hardcore Perl 5 XS/Core talk and Masak told us about his little 007 language
written in Perl 6 as a proof of concept playroom for future Perl 6 extended
macro support and demonstrated code written over lunch in support of this.

http://masak.org/carl/gpw-2016-big-hairy-yaks/talk.pdf

Stefan gave a great talk about CURLI and explained the complexity of what was
intended.

http://niner.name/talks/A%20look%20behind%20the%20curtains%20-%20module%20loading%20in%20Perl%206/Module%20loading%20in%20Perl%206.pdf

I gave my talk on "Simple Perl 6 Fractals and Concurrency" on Friday. It
started badly with AV issues my side but seemed well received. It was useful
speaking with people about it and I managed to speed things up *after* the talk
and I should have new material for a 2.0 version.

There were very good talks on extracting data from PDFs and writing JSON apis.

https://github.com/mickeyn/PONAPI

looked very interesting and would have saved me much coding at a recent job.

There were some great lightening talks at th end of the day. Sawyer wanted
people to have English slides and gave his talk in Hebrew to stress this.
Things ended Friday night with great food and beer in a local bar.

brrt to the future: FOSDEM and the future

Published by Bart Wiegmans on 2016-03-13T11:20:00

Hi all, I realise I haven't written one of these posts for a long time. Since November, in fact. So you could be forgiven for believing I had stopped working on the MoarVM JIT. Fortunately, that is not entirely true. I have, in fact, been very busy with a project that has nothing to do with perl6, namely SciGRID, for which I've developed GridKit. GridKit is a toolkit for extracting a power network model from OpenStreetMap, which happens to contain a large number of individual power lines and stations. Such a network can then be used to compute the flow of electric power throughout Europe, which can then be used to optimize the integration of renewable energy sources, among other things. So that was and is an exciting project and I have a lot of things to write on that yet. It is not, however, the topic of my post today.

Let's talk about the expression JIT, where it stands, how it got there, and where it needs to go. Last time I wrote, I had just finished in reducing the expression JIT surface area to the point where it could just compile correct code. And that helped in making a major change, which I called tile linearisation. Tile linearisation is just one example of a major idea that I missed last summer, so it may be worthwhile to expand a bit on it.

As I've epxlained at some length before, the expression JIT initially creates trees of low-level operations out of high-level operations, which are then matched (tiled) to machine-level operations. The low-level operations can each be expressed by a machine-level operation, but some machine-level instructions match multiple low-level operations. The efficient and optimal matching of low-level to machine-level operations is the tiling step of the compiler, and it is where most of my efforts have been.

Initially, I had 'tagged' these tiles to the tree that had been created, relying on tree traversal to get the tiles to emit assembly code. This turned out to be a poor idea because it introduces implicit order based on the tree traversal order. This is first of all finicky - it forces the order of numbering tiles to be the same in the register allocator and the tile selection algorithm and again for the code emitter. In practice that means that the last two of these were implemented in a single online step. But more importantly and more troubling, it makes it more complex to determine exactly the extent of live ranges and of basic blocks.

The notion of basic blocks is also one that I missed. Expression trees are typically compiled for single basic blocks at a time. The definition of a basic block is a sequence of instructions that is executed without interruption. This allows for some nice simplifications, because it means that a value placed in a register at one instruction will still be there in the next. (In contrast, if it were possible to 'jump in between' the instructions, this is not so easy to ensure). However, these basic blocks are defined at the level of MoarVM instructions. Like most high-level language interpreters, MoarVM instructions are polymorphic and can check and dispatch based on operands. In other words, a single MoarVM instruction can form multiple basic blocks. For correct register allocation, it is  vital that the register allocator knows about these basic blocks. But this is obscured, to say the  least, by the expression 'tree' structure, which really forms a Directed Acyclic Graph, owing to the use of values by multiple consumers.

The point of tile linearisation is provide an authoritative, explicit order for tiles - and the code sequences that they represent - so that they can be clearly and obviously placed in basic blocks. This then allows the register allocator to be extended to deal with cross-basic block compilation. (In the distant future, we might even implement some form of instruction scheduling). As a side effect, it also means that the register allocation step should be moved out of the code emitter. I've asked around and got some nice papers about that, and it seems like the implementation of one of these algorithms - I'm still biased towards linear scan - is within the range of reasonable, as soon as I have the details figured out. Part of the plan is to extract value descriptors from the tree (much like the tile state) and treat them as immutable, introducing copies as necessary (for instance for live range splitting). The current register allocator can survive as the register selector, because it has some interesting properties in that aspect.

Aside from that I've implemented a few other improvements, like:
From that last bit, I've learned that the way the JIT is currently dealing with annotations is subtly broken, because the following thing can and does happen:
I'm not yet sure how to deal with this. Jonathan implemented a fix last year that introduced a dynamic control label at the start of each basic block. Ultimately, that reinforces this 'stacking' behavior, although it already happened. Ideally, we would not need to store the current location for each basic block just for the few operations that need it. It might instead be possible to refer to the current region in some other way, which is what happens to some extent in exception handling already.

Anyway, that's all for today, and I hope next time I will be able to bring you some good news. See you!