# 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;

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.

# 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.

# 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.

# 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”

# 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.

# 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?

# 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.

# 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.