Day 11: Testing your Times Tables with Perl 6

It’s nearly the end of Winter term at Elf Primary School near the North Pole. A keen head for figures is very important to elves, and the little elves’ numeracy teacher, Ms Hopper, wants to make sure they keep up their arithmetical skills right up to the penultimate day of term. (The last day of term is reserved for watching films and playing shove-ha’penny).

The little elves have just learned their times tables (multiplication tables) up to 12, but they aren’t all as good at it as they’d like to be, and some of them will be helping out in the toy workshops just before Christmas, when they may need to quickly tell the big elves how many more toys of a particular type to make.

Fortunately Elf Hopper is a very smart elf with an excellent head for figures – and code – herself. So she whips up a quick console app to run on the little elves’ school-issue Perlix 6.0 boxen.

The program allows the little elves to test themselves on their 2 to 12 times tables by just running it, or if they supply a single numeric argument, they can try out any multiplication table they like.

#!/usr/bin/env perl6

use v6;

my $fixednum;
my %score;
my @exits = <exit quit>;

$fixednum = @*ARGS[0] || 0;
put "Type the answer, or quit or exit to end the test.";


loop {
    my $coefficient = (2..12).pick;
    my $number = $fixednum || (2..12).pick;

    my $answer = prompt ( "$coefficient × $number = " );
    my $rightanswer = $coefficient × $number;

    last if $answer.lc ~~ any @exits;

    if $answer == $rightanswer {
        put "Correct!";
        %score<correct>++;
    } else {
        put "Sorry, that wasn't right! The answer is $rightanswer";
    }
    %score<total>++;
}

if %score<total>:exists {
    my $pc = 100 * %score<correct> / %score<total>;
    put "You scored %score<correct> out of %score<total>, i.e. ", sprintf "%2.2f%%.", $pc;
}

Elf Hopper explains the code to the little elves as follows.

“Little elves! Here’s some background on how the program works.

I’ve added use v6; near the top in case so that the code can also run under Perl 5 and it will automatically engage the Perl 6 emulator.

You’ll see that the program picks up an optional parameter when run on the command line from the special @*ARGS array. This is the Perl6 equivalent of Perl 5’s @ARGV array.

In Perl 6, arrays, array elements and array slices always use the @ sigil, unlike Perl 5 where individual array elements use the $ sigil. In the same way, hashes and hash elements now always carry the % sigil, whether the whole hash, a slice of it or a single element is being used.

There’s also another symbol there, the asterisk ‘twigil’, *. That indicates that @*ARGS is a dynamic special variable.

The prompt and loop keywords are new in Perl 6 and both are admirably named!

  • prompt simply returns the value typed in by the user, in this case to a variable.
  • loop is one of Perl 6’s new block control keywords. A simple loop block like this one just creates an infinite loop which can be ended either by the programmer exiting explicity e.g. here with the last keyword when a condition is met; or for example by the user manually terminating the program.
  • Alternatively, loop can take three arguments and behave like a traditional C-style for loop. (In Perl 6, little elves, for is now only used for iterating over a list or other container.)

Inside the loop, little elves, you can see range objects. Everything is an object in Perl 6, so I can call the pick method on the range to return a random number. (Well, a non-cryptographically-secure pseudorandom number, anyway!)

The any keyword turns the @exits array into one of the many new useful data structures in Perl 6: a Junction. This makes finding an array element using the smartmatch operator ~~ straightforward. The last keyword exits the loop, as in Perl 5.

A Junction is a new type of container or list that allows many of the most useful comparisons such as any, all, one or none, which we do in Perl 5 with grep or a module such as List::Util, but it makes them a lot easier to type, and allows them to be performed concurrently! One side-effect of this is that Junctions are unordered: but they are mostly intended to result in a single true or false value, so that’s usually OK. Junctions are great for any time you quickly want to check a value against a short list of a few specific values, as here. But they’re also capable of letting you match against much larger sets of values if required.

At the top of the last code paragraph, you will see :exists applied to the %score<total> hash key. :exists is a Perl 6 adverb! Adverbs generally modify the way methods work. :exists is a subscript adverb. It is an adverb because it changes what happens when you read the hash key: instead of returning the value, you find out whether the value exists or not. This is usually a better alternative to using the defined method familiar to those of you who were paying attention in Perl 5 class.

The exists test is just there, of course, to ensure you don’t get an error if the user exits the program on the first go.

Why have I used chevrons to quote the hash key? Well, curly braces {} are the standard subscript operators for hash keys, as in Perl 5. However, most of the time you may want to use angle brackets / chevrons, as these provide automatic quotation of single-word keys. The simple {} braces used to do this in Perl 5, but no longer do in Perl 6. Strings inside the braces need to be quoted.

In Perl 6, the standard command for outputting text to a terminal is put. This outputs the following list items, followed by a newline. say and print are still available; say and put both print to standard output and append a newline; print does not append a newline.

If you use this program as well as knowing how it works, little elves, you will have the option, and knowledge, of whether, when and how to perform multiplication in your own head, and when it is best to let a Perl 6-powered computer do it. Your Christmas homework is to familiarise your elfselves with the Perl 6 documentation at https://docs.perl6.org.”

The little elves get to work with the multiplication test program, trying to outdo each other to get the highest perfect score. They find it so addictive that the contest even spills over to the final day of school, when they are supposed to be watching ‘Elf’!

🎅

Day 10 – jmp-starting your work flow

Here’s yet another version of jmp for you to unwrap before Christmas.

jmp is a command-line tool for searching through piles of code and then quickly jumping into an $EDITOR. This helps to keep things flowing.

Computer programming, however, has plenty of potential flow stoppers. To maintain a state of flow while coding you often need to quickly jmp to a line of code in other situations: fixing bugs, running tests, inspecting log files, checking git status etc. Can jmp help speed up these tasks too?

Fortunately it was relatively easy to refactor jmp to accommodate these extra use cases. The latest version of jmp now works like this:

Prefixing a command with jmp will cause the command to be executed again and its output slurped in and paginated.

#| find matching lines
method find-files-in-command-output ($command) {

    # execute the command
    my $shell-cmd = shell $command, :out, :err;

    # join STDOUT and STDERR
    my $result = join("\n", $shell-cmd.out.slurp, 
                            $shell-cmd.err.slurp);

    # don't actually look for filenames just yet
    # do that lazily on demand by the user
    return $result.lines.map({ 
               JMP::File::HitLater.new(context => $_) 
           });
}

jmp creates result hits for each line, and paginates the result. You can then quickly browse the output and jmp into your text editor if needed (see jmp config to change it to your favourite EDITOR).

Speed is important for command-line tools. Rather than scan each line for filenames in advance, jmp only looks for filenames when the user chooses to edit a specific line. Here is the code that lazily parses a line looking for files:

submethod find-file-path {

    given self.context {

        # matches Perl 5 error output (e.g., at SomePerl.pl line 12)
        when /at \s (\S+) \s line \s (\d+)/ {
            proceed unless self.found-file-path($/[0], $/[1]);
        }

        # matches Perl 6 error output (e.g., at SomePerl6.p6:12)
        when /at \s (<-[\s:]>+) ':' (\d+)/ {
            proceed unless self.found-file-path($/[0], $/[1]);
        }

        # matches Perl 6 error output (e.g., SomePerl6.p6 (Some::Perl6):12)
        when /at \s (<-[\s:]>+) '(' \S+ ')' ':' (\d+)/ {
            proceed unless self.found-file-path($/[0], $/[1]);
        }

        # more file finding patterns HERE - PR's welcome?

        # go through each token
        default {
            for self.context.words -> $token {
                # keep trying to set the file path
                proceed if self.found-file-path($token);
            }
        }
    }
}

The when blocks match different types of error formats (e.g., Perl 5 and Perl 6)  to extract the filename and line number. The proceed statement is useful for moving on to the next when block.

This means you can jmp on an error wherever it appears in your workflow: in command output, test output, log files etc.

To upgrade to version 3 of jmp:

shell> zef upgrade jmp

To install jmp for the first time, install Perl 6, then use zef the Perl 6 module manager to install it:

shell> zef install jmp   # install the jmp command line tool
shell> jmp config # set up jmp to use your tools
shell> jmp to sub MAIN # find files containing "sub MAIN"

Hopefully jmp helps you find flow while coding. Happy Christmas!

Day 9 – Let’s get astroPhysical! – Constants in Perl 6

I wrote my first Perl 6 program (that is, one that worked) the day before the London Perl Workshop where I proudly told people. So, JJ says “Why don’t you write an Advent calendar post for Perl 6?”

With only one program under my belt, what do I have to write about? Well … I authored Astro::Constants in Perl 5, so how hard would it be to migrate it to Perl 6?

Since I couldn’t keep my big gob shut, I give you the tale of a Perl 5 module author wandering through the Perl 6 landscape.

Continue reading “Day 9 – Let’s get astroPhysical! – Constants in Perl 6”

Day 8 — Make your Perl 6 grammar compact

Welcome to Day 8 of this year’s Perl 6 Advent Calendar!

Grammars are among many things that make Perl 6 a great programming language. I would not even try predicting the result of a poll to choose between grammars, Unicode support, concurrency features, hyper-operators, or the set syntax, or a Whatever star. Google found its own list of the best Perl 6 features published on the Internet.

Anyway, today we’ll be talking about Perl 6 grammars, and I will share a few tricks that I use to make the grammars more compact.

1. Split the actions

Suppose you are writing a grammar to parse Perl’s variable declaration. You would expect it to match the following statements:

my $s; my @a;

Both of them declare a variable, so we can make a generic rule to parse either case. Below, the complete program is shown:

grammar G {
    rule TOP {
        <variable-declaration>* %% ';'
    }

    rule variable-declaration {
        | <scalar-declaration>
        | <array-declaration>
    }

    rule scalar-declaration {
        'my' '$' <variable-name>
    }

    rule array-declaration {
        'my' '@' <variable-name>
    }

    token variable-name {
        \w+
    }
}

class A {
    has %!var;

    method TOP($/) {
        dd %!var;
    }

    method variable-declaration($/) {
        if $<scalar-declaration> {
            %!var{$<scalar-declaration><variable-name>} = 0;
        }
        elsif $<array-declaration> {
            %!var{$<array-declaration><variable-name>} = [];
        }
    }
}

G.parse('my $s; my @a;', :actions(A.new));

Let me not explain every bit of this program; if you are interested, there’s an 80-minute video from one of the recent Amsterdam.pm meetings.

The object of interest now is the rule variable-declaration and its corresponding action.

The rule contains two options: whether a scalar or an array is declared. The action also selects between the options and does that using the ifelse block. Perl 6 allows you omitting parentheses around the Boolean condition, but still, the whole construction is quite big. Think, for example, that if you add hash declarations, you will need to add another elsif branch.

It would be much clearer to have separate actions for each subbranch:

method scalar-declaration($/) {
    %!var{$<variable-name>} = 0;
}

method array-declaration($/) {
    %!var{$<variable-name>} = [];
}

Now, the body of each method contains a single line of code, and you can immediately see what it is doing. Not to mention that it became less error-prone.

Before we move on to the next trick, here’s another optimisation that you may want to implement: the my keyword is present in either declaration, so use non-capturing brackets and move the common string out of them:

rule variable-declaration {
    'my' [
        | <scalar-declaration>
        | <array-declaration>
    ]
}

rule scalar-declaration {
    '$' <variable-name>
}

rule array-declaration {
    '@' <variable-name>
}

Use multi-methods

Let us improve the grammar to allow assignments in the target language:

my $s; my @a; $s = 3; $a[1] = 4;

Notice that the assignment is done in the Perl 5 style, with a dollar sigil for array elements. Having that, the assignment can be done with a single rule beginning with a dollar:

grammar G {
    rule TOP {
        [
            | <variable-declaration>
            | <assignment>
        ]
        * %% ';'
    }

    # . . .

    rule assignment {
        '$' <variable-name> <index>? '=' <value>
    }

    rule index {
        '[' <value> ']'
    }

    token value {
        \d+
    }
}

So, the assignment action must deduce what kind of assignment it is handling at the moment.

Again, you can use our old friend, the ifelse block in the action. Depending on the presence of index, you decide if this is a simple scalar or an element of an array:

method assignment($/) {
    if $<index> {
        %!var{$<variable-name>}[$<index><value>] = +$<value>;
    }
    else {
        %!var{$<variable-name>} = +$<value>;
    }
}

This code can also be easily simplified, but this time using multi-methods:

multi method assignment($/ where !$<index>) {
    %!var{$<variable-name>} = +$<value>;
}

multi method assignment($/ where $<index>) {
    %!var{$<variable-name>}[$<index><value>] = +$<value>;
}

The where clause lets Perl 6 make the decision of which method candidate is more suitable in the given situation.

Notice also how the <value> key is used twice in the second multi-method. Each entry of <value> is referring to different parts of the target code: one for the index value, another—for the right-hand side value.

3. Let Perl do the job

Sometimes, Perl can do the job for us, especially if you want to implement something that Perl is familiar with. For example, let us allow different types of numbers in the assignment:

my $a; my $b; $a = 3; $b = -3.14;

It is relatively easy to introduce floating-point numbers to the grammar:

token value {
    | '-'? \d+
    | '-'? \d+ '.' \d+
}

Would you like to add other types of numbers, refer to my article at perl.com. For now, we can limit the grammar with the above two options, as this is enough to demonstrate the trick.

If you run the code with the change, you might be surprised that you get the desired result. Both variables receive the values:

Hash %!var = {:a(3), :b(-3.14)}

In both cases, the same action was triggered:

multi method assignment($/ where !$<index>) {
    %!var{$<variable-name>} = +$<value>;
}

On the right-hand side of the assignment we see +$<value>, which is a type cast from the Match object to a number. The grammar puts either 3 or -3.14 inside $<value>, both as strings. The + unary operator makes an attempt to convert the strings to numbers. Both strings are valid numbers, so Perl 6 won’t complain.

It would be much more difficult to write your own code to convert a string to a number, taking into account all different forms of the numeric values. To have an idea of what other formats Perl 6 is aware of, look at the definition of the numish token in the Perl 6 grammar:

token numish {
[
| 'NaN' >>
| <integer>
| <dec_number>
| <rad_number>
| <rat_number>
| <complex_number>
| 'Inf' >>
| $<uinf>='∞'
| <unum=:No+:Nl>
]
}

If you allow any of the above types in your own grammar, Perl will be able to convert them for you.

4. Use multi-rules and multi-tokens

It is not only methods, which can be multi-things. Rules and tokens of a grammar are also methods, and you also can create multiple variants of them.

Let us update our grammar to allow arithmetic expressions on the right side of assignments:

my $a; $a = 6 + 5 * (4 - 3);

The new problem here is to parse an expression and take care of the operator precedence and parentheses. You can describe any expression in the following way:

  1. An expression is a sequence of terms separated by + or -.
  2. Any term in the previous rule is a sequence of items separated by * or /.
  3. Anything within parentheses is another expression, so go to rule 1.

Having that said, you end up with the following grammar changes:

grammar G {
    # . . .

    rule assignment {
        '$' <variable-name> <index>? '=' <expression>
    }

    multi token op(1) {
        '+' | '-'
    }

    multi token op(2) {
        '*' | '/'
    }

    rule expression {
        <expr(1)>
    }

    multi rule expr($n) {
        <expr($n + 1)>+ %% <op($n)>
    }

    multi rule expr(3) {
        | <value>
        | '(' <expression> ')'
    }

    # . . .
}

Here, both rules and tokes are multi-methods, which take a single integer value reflecting the depth of the expression. The same happens to operators: on the first level, you expect + and -, on the second level—* and /.

Do not forget that multi-methods (as well as multi-subs) in Perl 6 can be dispatched based on constants, that’s why it is possible, for example, to have signatures such those you see in multi token op(2).

The expr($n) rule is defined recursively via expr($n + 1). The recursion stops when $n reaches 3, and Perl 6 chooses the last candidate multi rule expr(3).

Let me be lazy and use the previous advice to let Perl evaluate the expression:

multi method assignment($/ where !$<index>) {
    use MONKEY-SEE-NO-EVAL;
    %!var{$<variable-name>} = EVAL($<expression>);
}

In general, I would suggest using EVAL only during the magical Christmas time. In the rest of the year, please compute the expression yourself and use the abstract syntax tree and the pair of methods make and made to keep partial results. See an example here, for instance.

I would also suggest some extra reading to better understand how to use the multi and proto keywords:

  1. The proto keyword in Perl 6
  2. More on the proto keyword in Perl 6

And at this point, I will leave you with this journey along the awesome Perl 6 grammars. You can find the complete examples of today’s post on GitHub. I wish you a pleasant reading of the rest of this and other Perl Advent Calendars!

Day 7 – Automatic on a Cellular Level

Today’s advent calendar post deals with Cellular Automata.

What are cellular automata? I’m glad you asked! They are systems made up of only a few parts: A kind of field or “world” made up of cells, a set of states that every cell can be in at any point, a “neighborhood” describing what cells are visible to each cell, and a set of rules governing what a cell will change its state into given its own state and the state of all cells in its neighborhood.

That is, of course, a very abstract description, so let me give a few examples for the individual parts to hopefully give you an idea of what you might see in a cellular automaton:

In typical worlds you might find cells arranged like beads on a string, or like fields on a chess or chinese checkers board. There are also more exotic configurations you can make up: Any 2-dimensional field can be mapped onto any surface, like for example the stanford bunny

Sets of states you can find out in the wild would be “the numbers from 0 through n”, “there are bacteria here or not”, “the colors black and white” (or more). Since you can represent basically any piece of information as “a number”, and any number of states is allowed, there can also be states representing “how many particles in this cell are going up, down, left, or right at this moment?” as integer or even floating point numbers.

A neighborhood can be thought of as a pattern in which cells are “wired together”. Typical neighborhoods would be “the one in front and the one behind” for the “string of beads” field, and “north, east, south, west” or “north, northeast, east, southeast, south, southwest, west, northwest” for the chess board field – these two are the Von Neumann neighborhood and the Moore neighborhood respectively.

The set of rules that govern what states in each cell’s neighborhood will cause what state to go to what other state could be considered the heart of a particular cellular automaton.

In today’s advent calendar post we’ll explore what you might call the simplest automatons. We’ll string the fields up like beads on a string, and we’ll try a neighborhood or two and a few different state sets.

To make things interesting for those at home, I’ll be giving you links that let you run example code right here in your browser, or at home with your local perl6 compiler!

Doing for Learning

Let’s get started, then:

First of all, what do we need? There’ll have to be storage for the world, a bit of code to get a cell’s eligible neighbors, and a bit of code to calculate a cell’s next state given its own state and the states of the neighbors. On top of it all, we’ll want to see what’s going on, so we’d have some code for that, too.

After deciding what states each cell can have, we’ll know what storage is appropriate for our world. Going with an array of 8 bit integers will allow us to choose from any set of states that doesn’t have more than 255 individual ones. Let’s go with 3 states in total for now, though. We can initialize the world any way we please, but setting every field to a random valid state is a good starting point. Another is to put a single cell of one of the states in the middle and have every other cell with a different state.

constant number-of-states = 3;
constant field-width = 60;

my int8 @field;

sub init-field {
    @field = (^number-of-states).roll(field-width);
}

Displaying the field is pretty straight-forward, depending on what output we’re using. Here’s a piece of code that works in any console, and below that a link to a 6pad that outputs little colored squares in the HTML part of the pad.

sub output-a-row {

    for @field {
        # Using the unicode characters "Light shade", "Medium shade", and "Dark shade"
        # and printing each field twice so they look square rather than slim and tall.
        print ["\x2591", "\x2592", "\x2593"][$_] x 2
    }

    say "";
}

init-field;
output-a-row;

Run this code in your browser. You will have to wait a few seconds for the currently rather big perl6 compiler in javascript.

Stepping ahead

Getting from just one single row to a simulated run of the cellular automaton needs a whole bunch of parts at once.

Cellular automata by their definition will advance all of their cells at the same time. We’ll of course not go out to the cloud to get a machine with as many cpu cores as there are cells in our field. We’ll settle for “calculate the next step for each cell based on what their neighbor cells were in the previous step” by going through all fields with a simple loop.

The straight-forward approach for this is to have an extra field to put calculation results and copy the results into the “real” field array after each step. Let’s give that a try.

sub simulate-step {
    my int8 @output;

    for ^field-width -> $x {
        # do some calculations here
    }
    
    @field = @output;
}

Let’s see what we need in order for the calculations to happen: The new state will depend on the neighborhood and the cell itself. We’ll go with possibly the most obvious neighborhood: A cell, it’s predecessor and successor in the field. But wait, what happens with the very first and the very last cell? Let’s just pretend they have an extra neighbor that’s just always at state 0. That way

sub simulate-step {
    my int8 @output;
  
    for ^field-width -> $x {
        my $left   = $x - 1 < 0 ?? 0 !! @field[$x - 1];
        my $middle = @field[$x];
        my $right  = $x + 1 >= field-width ?? 0 !! @field[$x + 1];
        
        # do some calculation with $left, $middle, and $right
        # then push the result into @output
    }
    
    @field = @output;
}

So, we’re finally at the spot where we need to decide what our cellular automaton is actually supposed to do in the first place. But how are we supposed to figure out what it should do when we don’t even have a meaning assigned to states “0, 1, and 2”?

The answer is simple! Literally make it all up.

Making stuff up

What I mean by that is, we currently don’t really care what the cellular automaton does, as long as it looks good. So why not decide up front for every possibility what’s supposed to happen by rolling some imaginary dice?

For this purpose it helps to know how many possible “configurations” there even are for the cell and its neighbors to be in. Fortunately, that’s very simple. You can imagine the three cells as a number made up of three digits, and each digit is allowed to be 0, 1, or 2.

000  001  002
010  011  012
020  021  022
100  101  102
110  111  112
120  121  122
200  201  202
210  211  212
220  221  222

If I didn’t mess up, that’s all the possibilities for left, middle, and right cell to make up. Just like a four digit binary number can be one of 2⁴ numbers, this three digit ternary number can be one of 3³. That means that we just have to pick 3³ numbers between 0 and 2, one for each number in the table up above.

It’s actually pleasantly easy to do this!

my int8 @lookup-table = (^number-of-states).roll(3³);

And given our $left, $middle, and $right variables, we can multiply the first one with 9, the second one with 3, and add the three together to get an index into our lookup table:

sub simulate-step {
    my int8 @output;
  
    for ^field-width -> $x {
        my $left   = $x - 1 < 0 ?? 0 !! @field[$x - 1];
        my $middle = @field[$x];
        my $right  = $x + 1 >= field-width ?? 0 !! @field[$x + 1];
        
        my $index = $left * 9 + $middle * 3 + $right;
        
        @output.push(@lookup-table[$index]);
    }
    
    @field = @output;
}

And running this will already give us a shiny to look at. All we need to do is hook up the subs:

constant number-of-states = 3;
constant field-width = 60;

my int8 @field;

sub init-field {
    @field = (^number-of-states).roll(field-width);
}
init-field;

sub output-a-row {

    for @field {
        # Using the unicode characters "Light shade", "Medium shade", and "Dark shade"
        # and printing each field twice so they look square rather than slim and tall.
        print ["\x2591", "\x2592", "\x2593"][$_] x 2
    }

    say "";
}

my int8 @lookup-table = (^number-of-states).roll(3³);

sub simulate-step {
    my int8 @output;
  
    for ^field-width -> $x {
        my $left   = $x - 1 < 0 ?? 0 !! @field[$x - 1];
        my $middle = @field[$x];
        my $right  = $x + 1 >= field-width ?? 0 !! @field[$x + 1];
        
        my $index = $left * 9 + $middle * 3 + $right;
        
        @output.push(@lookup-table[$index]);
    }
    
    @field = @output;
}

for ^100 {
    simulate-step;
    output-a-row;
}

The results already look pretty interesting some of the time! Of course we need to get lucky with the random lookup table. Here’s one I like to get you started if you get lots of uninteresting ones:

my int8 @lookup-table = <0 0 2 0 0 0 1 2 0 0 1 1 2 1 1 2 1 1 1 0 1 2 2 0 2 1 1>;

And here’s the link to the 6pad where you can try it all in your browser.

Thirdly, here’s a screenshot from my machine in case you’re reading on a mobile device or something else that can’t run perl6 yet.

fish -tmp_112

Alterations

Now that our simulator does what it’s supposed to, let’s have some fun with some tweaks.

First, let’s see what it takes to increase the number of different states:

constant number-of-states = 4;

# the size of the lookup table should be based on the number of states
my int8 @lookup-table = (^number-of-states).roll(number-of-states³);

sub output-a-row {

    for @field {
        # add unicode character "Full block" for the fourth state
        print ["\x2591", "\x2592", "\x2593", "\x2588"][$_] x 2
    }

    say "";
}

And the calculation needs to do its computation based on number-of-states as well:

my $index = $left * number-of-states * number-of-states
            + $middle * number-of-states
            + $right;

And that’s already it! Not even terribly hard so far.

Changing up the neighborhood

Now this one’s much more interesting. Changing the neighborhood will require our calculation loop to get more variables for the index calculation, and the lookup table will change its size once more as well.

Let’s go back to 3 states instead of 4 and replace the neighborhood with one that has just one more cell in it: We’ll take a cell’s predecessor and its successor, but leave out the cell itself. We then add the predecessor’s predecessor and the successor’s successor:

# three states, but four neighbors
constant number-of-states = 3;
constant number-of-neighbors = 4;

# ...

# exponentiate number-of-states with number-of-neighbors, like
# you would to get a number-of-neighbors number in base number-of-states.
my int8 @lookup-table = (^number-of-states).roll(number-of-states ** number-of-neighbors);

sub simulate-step {
   my int8 @output;

   for ^field-width -> $x {
       my $leftleft   = $x <= 1 ?? 0 !! @field[$x - 2];
       my $left       = $x == 0 ?? 0 !! @field[$x - 1];

       my $right      = $x == field-width - 1 ?? 0 !! @field[$x + 1];
       my $rightright = $x >= field-width - 2 ?? 0 !! @field[$x + 2];

       # many multiplications later ...
       my $index = $leftleft * number-of-states * number-of-states * number-of-states
                   + $left   * number-of-states * number-of-states
                   + $right  * number-of-states
                   + $rightright;

       @output.push(@lookup-table[$index]);
   }

   @field = @output;
}

fish  -tmp_113.png

Here’s the 6pad to try it out

Sadly, all it seems to do is make the output a little more chaotic.

Optimization opportunities?

At the moment, the code is a compromise between performant and readable. It could also have looked like this:

for (0, |@field, 0).rotor(3 => -2) -> ($left, $middle, $right) {
    my $index = :3[$right, $middle, $left];
}

Though my intuition tells me that would have been noticeably slower.

But we can make the code a bit faster still, without sacrificing too much readability, even!

There is one thing that our calculation loop is doing way too much of: Array accesses! Every cell gets accessed three times in a row: Once when it becomes the $right, again when it becomes the $middle and another time when it becomes $left.

So how can we do this better? The first thing I thought of was to have the variables $left, $middle, and $right stick around between iterations and shifting the cell values through:

my $left   = 0;
my $middle = @field[0];
my $right  = @field[1];

for ^field-width -> $x {
    my $index = $left * number-of-states * number-of-states
            + $middle * number-of-states
            + $right;

    @output.push: @lookup-table[$index];
    $left = $middle;
    $middle = $right;
    $right = $x + 1 >= field-width ?? 0 !! @field[$x + 1];
}

Cool, we’ve even gotten rid of one of the checks of $x vs field-width! But there’s another thing that happens over and over that we could make just a tiny bit simpler. We can have the $left, $middle, and $right variables already hold the exact value needed for the addition:

my $left   = 0;
my $middle = @field[0] * 3;
my $right  = @field[1];

for ^field-width -> $x {
    my $index = $left + $middle + $right;

    @output.push: @lookup-table[$index];
    $left = $middle * 3;
    $middle = $right * 3;
    $right = $x + 1 >= field-width ?? 0 !! @field[$x + 1];
}

I think that looks pretty neat!

Other changes?

One kind of cellular automaton I’ve encountered is one where every cell has a chance to do its calculation on each step, and otherwise just keeps its state for an extra step. Let’s see how that’s implemented:

constant probability = 0.75e0;

my $left   = 0;
my $middle = @field[0] * 3;
my $right  = @field[1];

for ^field-width -> $x {
    if rand < probability {
        my $index = $left + $middle + $right;

        @output.push: @lookup-table[$index];
    }
    else {
        @output.push: $middle;
    }
    $left = $middle * 3;
    $middle = $right * 3;
    $right = $x + 1 >= field-width ?? 0 !! @field[$x + 1];
}

Lower probabilities are easy to spot, because they will cause the resulting image to look vertically stretched. Higher probabilities can cause completely regular patterns to stay mostly intact, but at some point be broken up in a spot or two.

Here’s a screenshot for you!

fish -tmp_114

Is this useful?

Cellular automata in general are extremely versatile, and even very simple ones can already handle universal computation, like “Rule 110”. There are more complex automatons like Von Neumann’s machines capable of self-replication and WireWorld, which has been used to build a little machine that can calculate prime numbers and display them on a little seven-segment display.

Pretty astonishingly, there’s a turing machine with a literal tape built from the pretty popular Game of Life and, potentially more astonishingly, a configuration of Game of Life that can calculate and display a Game of Life.

All in all, I find cellular automata a fascinating topic. Two-dimensional cellular automata were barely mentioned in this post, but there are many interesting ones besides the ones already mentioned in this section.

Implementation wise, you would most probably not use CPU code to simulate cellular automata. At the very least, you wouldn’t use a loop that goes over every individual cell – see the fantastic HashLife algorithm that chops the world up into bigger and bigger blocks that occur often and does many whole-world steps at once. Otherwise, you would most likely simulate a CA on the GPU, which offers extreme degrees of parallelism when the code run for each cell is the same.

Thank you for staying with me through this really rather long post!

I hope I could awaken even an idle interest in the fantastic and wide world of cellular automata!

Have a lovely december, everyone!

Day 6 – Lazy and Industrious Elves

Christmas is always a busy time of the year for Santa. Fortunately, Santa has a lot of helpers. Always doing little jobs and chores, just to create the best holiday season experience there is to be!

The Object::Delayed module adds two more very interesting elves to Santa’s merry bunch of elves! Their names are slackand catchup!

Lazy slack

The slack elf is very lazy indeed. It won’t do anything until you actually want to use whatever it was that you asked the slack elf to do. Although one could consider this a very bad character trait in an elf, it’s also a very ecological trait. One could consider the slack elf to be the greenest elf of them all! How many times have you asked an elf to do something for you and then not used the result of the hard work of that elf? Even though it’s only recycled electrons that are being moved around, it still costs energy to move them around! Especially if those electrons are used to tell other elves to do something far away, like in an external database!

use Object::Delayed;
my $dbh = slack { DBIish.connect(...) }

That’s what you need to have a $dbh variable that will only make a connection to a database when it is actually needed. Of course, if you want to make a query to that database, that can also be made to slack!

use Object::Delayed;
my $dbh = slack { DBIish.connect(...) }
my $sth = slack { $dbh.prepare(...) }

Since the statement handle is also slacked, it won’t actually do the query preparation until actually needed.

use Object::Delayed;
my $dbh = slack { DBIish.connect(...) }
my $sth = slack { $dbh.prepare(...) }
# lotsa program
if $needed {
    $sth.execute;  # opens database handle + prepares query
}

So if $needed is true, calling the .execute function will make the $sth become a real statemement handle after having made $dbh a real database handle. Isn’t that great? Because if you didn’t need it, all the elves doing the query preparation could be doing other things, and the elves making the database connection could also be doing other things. Not to mention the elves of the database being blissfully ignorant of your initial plan to make a database connnection at all!

Of course, if you did need the database connection, it is always a good idea to tell the elves of the database that you’re done. In Perl 6, this doesn’t happen automatically, because Santa doesn’t keep track of how much each elf is doing. Santa likes to delegate responsibility! You typically tell the database elves that you’re done when you leave the section of code in which you needed the database handle.

LEAVE .disconnect with $dbh;

The LEAVE elf is special in that it will do the stuff it is told to do when you leave the block in which LEAVE elf is called. In this case the .disconnect method is called on $_ if the $dbh is defined: the with elf not only tests if the given value is defined, bit also sets $_.

But, but, but, won’t checking whether $dbh is defined actually make the connection to the database? No, the slack elf is smart enough that if you’re asking if something is .defined, or True or False, it will not actually start doing the work for you. Which is sooo different from the catchup elf!

Industrious catchup

If the slack elf is the greenest elf in Santa’s employ, the catchup certainly appears to be the reddest elf. Because you always are trying to catch up with the catchup elf. But the catchup elf only appears to be very industrious.

When you tell the catchup elf to do something, the catchup elf will immediately find another elf to do the actual work and tell you that it is done. Which it most likely isn’t. By the time you actually want to use the result of what you asked the catchup elf to do, there are two possibilities: If the other elf is done and the result is available, you will get it immediately from the catchup elf. If the other elf is not done yet, it will let you wait until the other elf is done: it will force you to catch up! So how does that look?

use Object::Delayed;
my $foo = catchup { sleep 5; "Merry" }      # sleep is just
my $bar = catchup { sleep 9; "Christmas" }  # another word
my $baz = catchup { sleep 8; "everyone" }   # for baking
say “$foo $bar, $baz!”;
say “Took { now - INIT now } seconds”;
# Merry Christmas, everybody!
# Took 9.008 seconds

Here, the catchup elf had 3 other elves work on producing those nicely baked lettering with that sweet crusty glaze, where each letter takes about a second to make. If it had been only one elf doing that, it would have taken at least 5 + 9 + 8 = 22 seconds. Thanks to the catchup elf, it only took slightly more than 9 seconds! More than twice as fast!

Of course, if all other elves were already busy doing other things, it might actually take a little longer than just over 9 seconds. Or even longer than 22 seconds, if the other elves are working on more important things than baking letters with the right glazing. So your elf mileage may vary. You don’t want to overwork your elves, well not for too long. A few seconds should be ok.

Use the right elf

If you want to be as green as possible, use the slack elf. If you want it, and you want it now (well, as soon as possible), then using the catchup elf is an option if you can be reasonably sure that there will be enough other elves to do the actual job!

And a happy advent from all of the elves involved in this blog post! Yours truly is pretty sure no fast, slow or any other elf was harmed in any way.

Day 5 – Variables

Such a simple thing, isn’t it? A variable is a name that holds a value.

Occasionally, the value it’s holding might be replaced by a different one — hence the name. (According to the surgeon general, variables that don’t experience change on a regular basis should see their physician, and ask to be diagnosed as constants.)

Even though they’re very easy to grasp, and basically every language has them, my goal today is to convince you that variables are actually wonderfully tricky. In a good way! I aim to make you stumble out of this blog post, dazed, mumbling “I thought I knew variables, but I really had no idea…”.

Towards the end, the experimental language 007 will also figure, because it’s completely and utterly this language’s fault that I’m thinking so much about variables.

Left or right?

The first way variables are odd is that they are used in two completely different ways.

my $x = "Christmas";

say("Merry " ~ $x);       # reading
$x = "Easter";            # writing

Sometimes we use variables to read a value, and sometimes we use them to write a value. But in both cases, the syntax looks exactly the same! Some older languages (such as Forth) actually have different syntaxes for these two usages, and I love them for it. But such a convention does not appear to have survived into the modern era.

Instead, we distinguish the two uses by grammatical location. If you’re on the left side of an assignment, you’re being written to. Otherwise, you’re being read from.

In the literature, these two uses are called lvalues and rvalues, respectively. For “left” and “right”, respectively.

Rvalues are pretty normal, and correspond to how we think about variables in general; they just evaluate to the value that they contain. Lvalues, however, are weird. They’re more like boxes that you can put something in (or memory locations? references?), or if not the box itself, then the detached ability to put something in it. If lvalues had a type, it would look something like (T) -> void, something that accepts a T but doesn’t return anything.

Parameters

Variables are entirely essential to modern programming. There’s also a principle stating that they are entirely unnecessary.

That’s right! Tennent’s Correspondence Principle! (I know what you’re thinking. No, not that Tennant).

This principle is mainly pointing to a way to rewrite all our variable declarations in our programs so they’re parameter declarations instead. One example should be enough to show the general principle:

# Before
my $veggie = "potato";
say "$veggie, and that's all I have to say about that!";

# After
(-> $veggie {
    say "$veggie, and that's all I have to say about that!";
})("potato");

See how the variable declaration turns into a parameter declaration, and the corresponding assignment turns into an argument? Experienced (or should I say war-torn) JavaScript developers recognize this construction as an IIFE.

Since we can always do this transformation, we don’t really need variables. Only parameters. I’m mainly telling you this so that you can be a little bit extra grateful that you don’t have to write your code with just parameters.

Final note about Tennent’s Correspondence Principle: its original use is described briefly on Wikipedia. It was basically forgotten until Java was about to get closures and its name was invoked and the principle was overused a bit, maybe.

Dynamic scoping

In Perl 6, variables take on an extra “twigil” (an optional symbol after the sigil) whenever the variable scope deviates from lexical scope. The most important of these alternative scopes might just be the dynamic scope.

Again, we’d better show the difference with an example:

my $lexical = "mainline";
my $*dynamic = "mainline";

sub foo() {
    my $lexical = "foo";
    my $*dynamic = "foo";
    bar();
}

sub bar() {
    say $lexical;       # "mainline"
    say $*dynamic;      # "foo"
}

foo();

Forget about Virgo and Sagittarius and the other astrological signs. The only distinction worth making about your deeper personality is whether you’re doing lexical lookup, or dynamic lookup. There are, after all, only two types of people.

Whether we like it or not, a lookup is a process. We’re given a name, and we go look for the corresponding value. It’s dispiriting, I know. But let’s do it anyway, and see where it leads.

For $lexical, the lookup happens by looking at the program text itself. Is that variable defined inside the smallest scope we’re in, that bar sub? (It’s not.) Then we proceed outwards, to the immediately surrounding scope — which turns out to be the scope of the entire program. Is it defined there? Yes! What luck. We return from the lookup, victorious, with the value "mainline".

For $*dynamic — notice the little star in the name? I told you there was astrology involved! — we also start in the innermost scope, the bar sub, and look for a definition there. (We find none.) But now something different happens. We don’t follow the block structure outwards, instead we follow the caller chain upwards. Who called us? foo. That’s where we look. Is there a definition there? Yes! So we’re done, and successful.

From a historical perspective, dynamic lookup was the “obvious” one, and most languages had it at first. Lexical lookup only gradually proved its worth, and is now endemic. Perl 5 actually straddles this history, and my variables are lexical, but the older our/package variables are dynamic. That’s what you get from being around while history is happening.

In Perl 6, we also do our part by forbidding the term “parent scope”. In a world with both lexical and dynamic lookup, it’s just too confusing. Instead, we prefer the terms OUTER (for lexical lookup) and CALLER (for dynamic lookup).

Some constructs in Perl 6 (such as return and next) try to be lexical if possible, but fall back to being dynamic if they don’t find any lexically surrounding thing to “attach” to. This type of behavior didn’t really have an academic term, it seems, so the Perl 6 synopses call it “lexotic”.

Variables in macros

Still with me? Goodie. Let’s talk about macros.

use experimental :macros;

macro moo {
    my $counter = 0;
    quasi {
        say ++$counter;
    }
}

for ^10 {
    moo;
}

This is a simple macro which just injects the code say ++$counter into that for loop there. The program will print all the numbers from 1 to 10, on individual lines.

Great, but… how? Notice that the macro-expanded code refers to $counter, but lexical lookup (as described above) would not find the variable declared in a surrounding lexical scope. But still, this program works, or rather, is meant to work.

So what is the underlying principle that makes the program work. It turns out that by a very lucky happenstance, variables that are defined inside a macro body can be “uniquified” and replaced by an lvalue. The injected code say ++$counter actually looks more like say ++☐, where the gets to represent that (unrepresentable-as-code) lvalue.

I know this is a small thing, but I was so happy when I finally put this together. In fact, I was so happy that I wrote it down as a github issue, just to make sure the details all work out. Stay tuned for an implementation of this and, consequently, hygiene.

(For those keeping score at home, hygienic macros are milestone D3 in this grant application.)

Just to be clear — this is more like an intent to implement. Full hygiene is yet to come in Perl 6 (and 007). But it feels heartening to have a clear path forward.

Anyway, that’s variables. They’re lovely, a little bit weird, but in the end we’re happy they are there. Happy advent. ☺