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.