Day 18 – An SVG Christmas Tree

Christmas trees are a traditional symbol that date back more than four hundred years in Europe, so what could be better for an advent article than something about creating Christmas tree images.

The typical, simplified, representation of the tree is several triangles of decreasing size stacked on top of each other with a small over-lap, so are fairly easy to create with a computer program.

Here I’ll use Scalable Vector Graphics (SVG) to draw the image as, given the description above, it seems perfectly suited to the task.

Continue reading “Day 18 – An SVG Christmas Tree”

Day 17 – Compiling our way to happiness

Our mission, should we choose to accept it, is to solve the SEND + MORE = MONEY problem in code. No, hold on, let me put it like this instead:

    S E N D
+   M O R E
-----------
  M O N E Y

It means the same, but putting it up like this is more visually evocative, especially since many of us did it this way in school.

The ground rules are simple.

  • Each letter represents a digits between 0 and 9.
  • The letters represent distinct digits; two letters may not share the same digit.
  • Leading digits (in our puzzle, S and M) can’t be zero. Then they wouldn’t be leading digits!

Given these constraints, there’s a unique solution to the puzzle above.

I encourage you to find the solution. Write a bit of code, live a little! In this post, we’ll do that, but then (crucially) not be satisfied with that, and end up in a nested-doll situation where code writes code until something really neat emerges. The conclusion will spell out the ultimate vision — hold on, I’m being informed in real-time by the Plurality Committee that the correct term is “an ultimate vision” — for Perl 6.

Let’s do this.

Marcus Junius Brute Force (The Younger)

Our first language of the day, with its corresponding solution, is Perl 6 itself. There’s no finesse here; we just charge right through the solution space like an enraged bull, trying everything. In fact, we make sure not to attempt any cleverness with this one, just try to express the solution as straightforwardly as possible.

for 0..9 -> int $d {
    for 0..9 -> int $e {
        next if $e == $d;

        my int $y = ($d + $e) % 10;
        my int $_c1 = ($d + $e) div 10;

        for 0..9 -> int $n {
            next if $n == $d;
            next if $n == $e;
            next if $n == $y;

            for 0..9 -> int $r {
                next if $r == $d;
                next if $r == $e;
                next if $r == $y;
                next if $r == $n;

                next unless ($_c1 + $n + $r) % 10 == $e;
                my int $_c2 = ($_c1 + $n + $r) div 10;

                for 0..9 -> int $o {
                    next if $o == $d;
                    next if $o == $e;
                    next if $o == $y;
                    next if $o == $n;
                    next if $o == $r;

                    next unless ($_c2 + $e + $o) % 10 == $n;
                    my int $_c3 = ($_c2 + $e + $o) div 10;

                    for 1..9 -> int $s {
                        next if $s == $d;
                        next if $s == $e;
                        next if $s == $y;
                        next if $s == $n;
                        next if $s == $r;
                        next if $s == $o;

                        for 1..9 -> int $m {
                            next if $m == $d;
                            next if $m == $e;
                            next if $m == $y;
                            next if $m == $n;
                            next if $m == $r;
                            next if $m == $o;
                            next if $m == $s;

                            next unless ($_c3 + $s + $m) % 10 == $o;
                            my int $_c4 = ($_c3 + $s + $m) div 10;

                            next unless $_c4 % 10 == $m;

                            say "$s$e$n$d + $m$o$r$e == $m$o$n$e$y";
                        }
                    }
                }
            }
        }
    }
}

Again, it’s not pretty, but it works. This is the kind of indentation level your mother warned you about. If you ask me, though, I’m more annoyed about the indentation being there at all. We have one for every variable whose search space we need to scan through. (Only with Y do we get to take a shortcut.)

Though it’s a detour for today’s buffet, MJD once blogged about this and then I blogged about it too. Those blog posts were very much about “removing the indentation”, in a sense. Today’s post is where my thinking has taken me, three years later.

I took the path less traveled (and all the other paths, too)

Our second language is still mostly Perl 6, but with a neat hypothetical extension called amb, but spelled (evocatively) <-. It gets rid of all the explicit for loops and levels of indentation.

my $d <- 0..9;
my $e <- 0..9;
guard $e != any($d);
my $y = ($d + $e) % 10;
my $_c1 = ($d + $e) div 10;

my $n <- 0..9;
guard $n != any($d, $e, $y);
my $r <- 0..9;
guard $r != any($d, $e, $y, $n);
guard ($_c1 + $n + $r) % 10 == $e;
my $_c2 = ($_c1 + $n + $r) div 10;

my $o <- 0..9;
guard $o != any($d, $e, $y, $n, $r);
guard ($_c2 + $e + $o) % 10 == $n;
my $_c3 = ($_c2 + $e + $o) div 10;

my $s <- 1..9;
guard $s != any($d, $e, $y, $n, $r, $o);
my $m <- 1..9;
guard $m != any($d, $e, $y, $n, $r, $o, $s);
guard ($_c3 + $s + $m) % 10 == $o;
my $_c4 = ($_c3 + $s + $m) div 10;

guard $_c4 % 10 == $m;

say "$s$e$n$d + $m$o$r$e == $m$o$n$e$y";

This solution is shorter, more compact, and feels less “noisy” and aggravating just by ridding us of the for loops. (I suspect this has something to do with that imperative↔declarative spectrum people mention sometimes. We’re not so interested in looping as such, only seeing it get done.)

I know it won’t completely make up for the fact that Perl 6 doesn’t have the amb operator and guard implemented in core (or even in module space), but here’s a short script that will convert the above program to today’s first version:

my $indent = 0;
constant SPACE = chr(0x20);
sub indent { SPACE x 4 * $indent }

for lines() {
    when /^ my \h+ ('$' \w) \h* '<-' \h* (\d+ \h* '..' \h* \d+) ';' $/ {
        say indent, "for $1 -> int $0 \{";
        $indent++;
    }

    when /^ guard \h+ ('$' \w) \h* '!=' \h* 'any(' ('$' \w)+ % [\h* ',' \h*] ')' \h* ';' $/ {
        say indent, "next if $0 == $_;"
            for $1;
        say "";
    }

    when /^ guard \h+ ([<!before '=='> .]+ '==' <-[;]>+) ';' $/ {
        say indent, "next unless $0;";
    }

    when /^ my \h+ ('$' \w+) \h* '=' \h* (<-[;]>+) ';' $/ {
        say indent, "my int $0 = $1;";
    }

    when /^ \h* $/ {
        say "";
    }

    when /^ say \h+ (<-[;]>+) ';' $/ {
        say indent, $_;
    }

    default {
        die "Couldn't match $_";
    }
}

while $indent-- {
    say indent, "\}";
}

But we’ll not be satisfied here either. Oh no.

Thinking in equations

The third language takes us even further into the declarative, getting rid of all the guard clauses that simply state that the variables should be distinct.

ALL_DISTINCT

$d in 0..9
$e in 0..9
$n in 0..9
$r in 0..9
$o in 0..9
$s in 1..9
$m in 1..9

$y = ($d + $e) % 10
$_c1 = ($d + $e) div 10

($_c1 + $n + $r) % 10 == $e
$_c2 = ($_c1 + $n + $r) div 10

($_c2 + $e + $o) % 10 == $n
$_c3 = ($_c2 + $e + $o) div 10

($_c3 + $s + $m) % 10 == $o
$_c4 = ($_c3 + $s + $m) div 10

$_c4 % 10 == $m

We’re completely in the domain of constraint programming now, and it would be disingenuous not to mention this. We’ve left the imperative aspects of Perl 6 behind, and we’re focusing solely on describing the constraints of the problem we’re solving.

The most imperative aspect of the above program is when we do an assignment. Even this is mostly an optimization, in the cases when we know we can compute the value of a variable directly instead of searching for it.

Even in this case, we could translate back to the previous solution. I’ll leave out such a translator for now, though.

I’m going to come back to this language in the conclusion, because it turns out in many ways, it’s the most interesting one.

The fourth language

Having gotten this far, what more imperative complexity can we peel off? Specifically, where do those equations come from that are specified in the previous solution? How can we express them more succinctly?

You’ll like this, I think. The fourth language just expresses the search like this:

    S E N D
+   M O R E
-----------
  M O N E Y

Hang on, what again? Yes, you read that right. The most declarative solution to this problem is just an ASCII layout of the problem specification itself! Don’t you just love it when the problem space and the solution space meet up like that?

From this layout, we can again translate back to the constraint programming solution, weaving equations out of the manual algorithm for addition that we learn in school.

So, not only don’t we have to write those aggravating for loops; if we’re tenacious enough, we can have code generation all the way from the problem to the solution. We just need to find the appropriate languages to land on in-between.

Conclusion

My exploration with 007 has led me to think about things like the above: translating programs. Perl 6 already exposes one part of the compilation process very well: parsing. We can use grammars both in userland and within the Perl 6 toolchain itself.

I’ve come to believe we need to do that to all aspects of the compilation pipeline. Here, let me put it as a slogan or a declaration of sorts:

Perl 6 will have reached its full potential when all features we bring to bear manipulating text/data can also be turned inwards, to the compilation process itself.

Those translators I wrote (or imagined) between my different languages, they work in a pinch but they’re also fragile and a bit of a waste. The problem is to a large extent that we drop down to text all the time. We should be doing this at the AST level, where all the structure is readily available.

The gains from such a mind shift cannot be overstated. This is where we will find Lispy enlightenment in Perl 6.

For example, the third language with the equations doesn’t have to be blindly translated into code. It can be optimized, the equations massaged into narrower and more precise ones. As can be seen on Wikipedia, it’s possible to do such a good job of optimizing that there’s no searching left once the program runs.

My dream: to be able to do the above transformations, not between text files but between slangs within Perl 6. And to be able to do the optimization step as well. All without leaving the comfort of the language.

Day 16 – Checking Your List Twice

Getting to Know Perl6 From the Command Line

This was Sniffles the Elf’s big chance! After years of drudgery in the ribbon mines, they’d finally been moved up into the List Management Department. As a shiny new Associate Nice List Auditor, Sniffles was on their way to the big time.

On their first day, when Sniffles arrived, Mr. Grumble–their new boss, was waiting. “Nice List management is deep trouble, our data was accidentally erased when someone spilled milk and cookie crumbs on the server. We’d been so busy checking the list that we forgot to check our backups! And now we have to rebuild everything from scratch! After the sackings, we’re a little short handed, so it’s up to you to save the day.”

Sniffles, being particularly industrious, dove into the problem with relish. After a bit of research they realized that all the data they needed was available, they just needed to collect it.

Their friend in the ribbon mines, a self-professed oral historian named Hermie had been going on about how great Perl6 is. Sniffles decided to give it a try. Continue reading “Day 16 – Checking Your List Twice”

Day 15 – Building a (little) Spacecraft with Perl 6

Showing off long ears

In the previous post, we have encountered some kind of special elves’ magic:

enum Fuel <Solid Liquid Gas>;

class SpeedChoice does ASNChoice {
    method ASN-choice { { mph => (1 => Int), kmph => (0 => Int) } }
}

class Rocket does ASNSequence {
    has Str $.name is UTF8String;
    has Str $.message is default-value("Hello World") is UTF8String;
    has Fuel $.fuel;
    has SpeedChoice $.speed is optional;
    has Str @.payload is UTF8String;

    method ASN-order { <$!name $!message $!fuel $!speed @!payload> }
}

my $rocket = Rocket.new(
    name => 'Falcon',
    fuel => Solid,
    speed => SpeedChoice.new((mph => 18000)),
    payload => [ "Car", "GPS" ]);

my $rocket-bytes = ASN::Serializer.serialize($rocket, :mode(Implicit));

#`[ Result:
      Blob.new(
          0x30, 0x1B, # Outermost SEQUENCE
          0x0C, 0x06, 0x46, 0x61, 0x6C, 0x63, 0x6F, 0x6E, # NAME, MESSAGE is missing
          0x0A, 0x01, 0x00, # ENUMERATED
          0x81, 0x02, 0x46, 0x50, # CHOICE
          0x30, 0x0A, # SEQUENCE OF UTF8String
              0x0C, 0x03, 0x43, 0x61, 0x72,  # UTF8String
              0x0C, 0x03, 0x47, 0x50, 0x53); # UTF8String
]

say ASN::Parser.new(:type(Rocket)).parse($rocket-bytes) eqv $rocket; # Certainly true!

However, as an elf I know once quoted, ‘It’s hard to tell the difference between mastered technique and magic’. So the mystery can be resolved? Let’s glance over the way it all works.

Continue reading “Day 15 – Building a (little) Spacecraft with Perl 6”

Day 14 – Designing a (little) Spacecraft with Perl 6

Looking for a common point

Greetings!

Those days I am spending some of my time working on foundation parts for, revealing a possible surprise, a LDAP (Lightweight Directory Access Protocol) implementation for Perl 6.

However, it is yet too early to talk about this one, so I will have some mystery blanket covering this topic for now, as we have another one – spacecrafts!

And a common point between spacecrafts and LDAP is: LDAP specification uses a notation called ASN.1, which allows one to define an abstract type, using a specific textual syntax, and, with a help of ASN.1 compilers, create a type definition for particular programming language and what’s more: encoder and decoder for values of this type, which can serialize your value into some data which, for example, can be send over network and parsed nicely on another computer.

Continue reading “Day 14 – Designing a (little) Spacecraft with Perl 6”

Day 13 – Web server from scratch with Cro and Debian

I talked to Santa Claus and he said he does not know how to install Cro on Debian, so I said to myself: I’m going to help him out.

If you have some experience with web servers like Apache, and you have heard about the powerful concurrent/reactive aspects of Perl6, surely you are interested to know about Cro Services. The scope of this post are people with basic experience in Debian and basic experience or none in Perl6… like Santa.

Cro is a Perl6 module that gives everything you need to build reactive and concurrent services easily, for example: a web server.

In this post we will see how to install Cro from scratch in Debian, one of the most popular Linux distributions. Then, I will explain the demo example of Cro.

We will use Debian 9, 64-bit (Stretch) and we will start once it is installed.

Continue reading “Day 13 – Web server from scratch with Cro and Debian”

Day 12 – Building a flexible grammar

Mrs Santa has written a basic grammar to match the simple lists that GDPR ignorant elves are collecting from around the world about who has been naughty or nice this year.

Each record is a name, followed by a tab, followed by an address, followed by a tab, followed by an assessment of naughty or nice and then finishes with a newline.

Batman 1 Batman Street, Gotham Nice
Joker 5 Joker Street, Arkham Naughty
Riddler 12 Riddler Street, Arkham Naughty
Robin 2 Robin Street, Gotham Nice

She wants to filter off the Naughty people into one list and the Nice people into another, as Krampus is going to deal with all the naughty people this year. Continue reading “Day 12 – Building a flexible grammar”