Implement the macros version of SEND+MORE=MONEY in 007

[masak]

From this blog post.

In the post (and in Perl 6 currently), we have to resort to cheating. Let's write an implementation in 007 that doesn't resort to cheating, that is, that actually transforms the AST and generates something close to solution B.

(If it manages to speed itself up by doing some other analysis behind the scenes, all the better. It will probably still be excruciatingly slow in 007.)

The way we do this doesn't have to be "nice" or all in userland at first. As long as it works, and shows the way forward.

[masak]

I think we should stub, as soon as possible, a solution which uses four language "stages":

1. A visual description of the problem, like the LaTeX thing on Wikipedia.
2. A declarative description with equations and inequalities.
3. A language with amb (<-) in it.
4. "Plain" 007 with just loops and conditionals

That in itself would be nice, but the 2 stage could also be optimized quite a bit using constraint programming techniques, and modular arithmetic. The strategy/thought process is outlined on the Wikipedia page, but needs to be formalized into some kind of pattern matching rules. In the best case, the program would just output the solution without any search.

I dunno, I think to the extent we can pull off this well, it'll be a compelling example for what 007 (and Perl 6 macros/slangs) could do really well.

Happy to prototype this in either Perl 6 or 007.

[masak]

I ended up writing a perl6advent post about the above idea.

Next up, I'd like to prototype all of this in 007. There are two more-or-less parallel approaches that can be taken:

• (The easy/boring one) Write three 007 scripts that can parse and convert the various stages to the next one, culminating in a runnable 007 script that solves the problem.
• (The challenging/cool one) Implement three new languages — hardcoded at first, before we have mechanisms for langs/slangs — that can compile down in stages into pure 007.

The latter one is a bit similar in spirit to #324. It's unclear whether I'd want to merge anything into master which does enough cheating, but... I just might. A cheaty implementation might be better than no implementation.

Regardless, I think it'd provide useful early feedback.

[masak]

Here are my thoughts for the Qnode types for these languages:

Visual description language

• VDL.Q.Sum
• VDL.Q.Column with an array of summands and a result
• Q.Identifier (...maybe?)

Constraint language

• CSL.Q.Description contains the below declarations and equations
• CSL.Q.Declaration declares a variable to be in a range
• CSL.Q.Equation can be any of ==, !=, or = between two expressions
• Q.Expr, consequently (and all the usual terms and operators)

Amb language extension

Basically 007, but with infix:«<-» and a guard statement defined in the grammar. These don't have to do anything in particular, since the idea is to compile them down, not run them.