Strangely Consistent

Musings about programming, Perl 6, and programming Perl 6

Macros: Time travel is hard

Let's say you're a plucky young time traveler from the 80s and you go back to the 50s because Libyan terrorists are chasing you and then you accidentally mess things up with the past and your time machine DeLorean is broken and you need to fix that too...

Dealing with the different phases involved in macros is a bit like dealing with the two time streams: the new present, which is very early compared to what we're used to, and the future, which we would like to get back to intact. (The slow path, wasn't much of an option for Marty, and it isn't for us either as macro authors.)

Let's try a new way of thinking of all this, instead of compile time and runtime. Those terms quickly get muddled with macros, since a macro runs (so it's kind of runtime), but it has BEGIN-time semantics (so it's definitely compile-time).

Let's call the two phases early and late. Instead. What the compiler does happens early. What the normal program does happens late. M'kay?

BEGIN blocks? Early. constant declarations? Early. CHECK blocks? Also early, though kind of at the 11th hour of early. Role bodies get executed early when they're getting concretized into a class.

Most everything else? Late. That is, in the 80s where Marty belongs. And where most people run most of their code.

Macro bodies run early too. Except for the (often-occurring) quasi block at the end, which runs late. This is how you should probably think about macros: they have a "preparation area" where you get to do some initialization early, and then they have a "code area" whose code runs, inline where you called the macro, late.

Got it? Like these terms? Eh, I guess they work. I don't expect we'll keep them around, but let's explore them.

So much for setup. I had a thought today, which led me down some wrong paths. I'd like to try and relate it. Partly because it's "fun" to analyze one's own failure modes. Partly because, and believe me on this, macros are gnarly. Far be it from me to discourage people from using macros — the past few months of thinking and investigations have convinced me that they're useful, that they have a clear place in Perl 6, and that we can make them well-designed. But wow are they weird sometimes.

Macros are so strange that once you wrap your head around closures, and accept that they're actually quite a natural consequence of first-class functions and lexical lookup, macros come along and make your brain go "wait, what?".

Part of that, I'm sure, is the weird (but consistent) scoping semantics you get from macros. But part of it is also the early/late distinction.

Ok, so back to what happened. I was thinking about implementing a 007 runtime in 007, and in particular how the runtime would invoke functions, especially built-in functions. I realized I would probably need a huge table of built-in function mappings at some point in the runtime. In Perl 6, it'd look something like this:

my %builtins =
    say => &say,
    abs => &abs,
    min => &min,
    max => &max,
    # ...and so on, for far too many lines...

As you see, it's all mappings from strings to the runtime's own built-ins. Yep, welcome to the world of metacircular runtimes.

So I wondered, "hm, shouldn't we be able to write a macro that takes a string value (that we get from a Q::Identifier) and dynamically looks it up in the current environement?". And indeed, I quickly came up with this:

macro lookup(name) {
    return Q::Identifier( melt(name) );

So easy! This example presupposes melt, which is a kind of evaluation built-in for Qtrees. We need to use melt because the name that we get in is a Qtree representing a name, not a string. But melt gives us a string.

Oh, and it works and everything!

lookup("say")("OH HAI");    # OH HAI

Unfortunately, it's also completely useless. Specifically, lookup doesn't fulfill its original purpose, which was to allow dynamic lookup of names in the scope.

Why? Because we're running the macro early, and so variables like ident_name cannot be melted because they don't have a meaningful value yet — they will, but not until late — only constants and literals like "say" have meaningful values. But in all such cases, we could just replace lookup("say") with... say. D'oh!

Ok, so that didn't work. My next bright idea was to make use of the fact that quasi blocks run late. So we can get our dynamism from there:

macro lookup_take_II(name_expr) {
    quasi {
        my name = {{{name_expr}}};
        # great, now I just need to... ummm....

There's no correct way to conclude that thought.

Why? Because you're in a quasi, which means you're back in the 80s, and you want to do a 50s thing, but you can't because the time machine is gone. In other words, it's late, and suddenly you wish it was early again. Otherwise how are you going to build that dynamic identifier? If only there were a lookup macro or something! 😀

This has been the "masak stumbles around in the dark" show. Hope you enjoyed. I also hope this shows that it's easy to go down the wrong path with macros, before you've had something like four years of practice with them. Ahem.

Anyway, these ponderings eventually led to the melt builtin — coming soon to a 007 near you! — which, happily will solve the problem of dynamic lookup (as detailed in the issue description. So all's well that ends well.

Macros are not a handgun that can accidentally shoot you in the foot if you use them wrong. They're more like an powered-off laser cannon which, if you look at it the wrong way, will shoot you in both feet, and your eyes and then your best friend's feet. That kind of power sure can come in handy sometimes! I'm convinced we as a community will learn not just to harness and contain that power, but also how to explain to ourselves how to best use the laser cannon so that it does not accidentally fire too early, or too late. Gotta stay in phase.

Macros: Your macro has been put on hold

Yes, it is me. Back to blogging about macros. Feels good.

There has been some vigorous activity around 007 lately. It started around YAPC::Europe, but really lifted off in October, for some reason. It's like 007 started out as a throwaway experiment, but lately it's been coming into its own, driving its own development and spewing out interesting findings as a by-product.

Side note: I expect to blog extensively about 007. Not today, though. For those of you who feel an irresistible urge to know more, I refer you to the exquisitely crafted page and the that has never received a single complaint for beeing too long and rambling.

Today the topic is the latest by-product to fall out of 007. I'm implementing quasi unquotes right now, and I realized:

Macro calls can't expand right after they're parsed in a quasi, if the arguments have an unquote in them.

I'm talking about something like this:

quasi {
    my-macro 1, {{{$ast}}}, 3;

Outside of a quasi block, as soon as the parser hit that ; it would whoosh off and call my-macro. Clearly that's not possible here, because there's an unquote there, a hole that's waiting to be filled with $ast.

So we must wait, patiently, until the quasi gets evaluated. (This usually happens when the surrounding macro is invoked. Quasis don't have to be found in macros, though typically they are. So we could also call this "splice-time", since likely the unquote is about to be spliced into code.) Once we're in the right scope and on the right instruction, we have an $ast, we can fit it into the unquote, and then, not before, we can expand my-macro.

Frankly I'm surprised this took me so long to realize. I don't seem to be alone; S06 has this to say about when macros are called:

Macros are functions or operators that are called by the compiler as soon as their arguments are parsed (if not sooner).

This could be a confusion of terminology: the {{{$ast}}} was parsed, but we still don't know what expression it will contain. We still don't know what it is.

Maybe it should say something like this:

Macros are functions or operators that are called by the compiler as soon as their arguments are known.

The question arises: should we call unquote-less macros immediately, but hold off unquote-ful macros until the quasi is evaluated? In my opinion, no, for reasons of consistency. Let's just "hold all calls" instead:

Macro calls don't expand right after they're parsed in a quasi, they expand when the quasi is evaluated.

Be aware, this is by no means a bad thing. Macros as a whole get more flexible and capable if they're put on hold in quasis. I don't have a full example ready, but imagine we had a data structure (like a HTML DOM or something) expressed as code, and we send it off to a macro. Thanks to macro calls being put on hold, we can now code-gen stuff recursively based on the specific contents of the data structure. That's pretty far out.

Previously (when macro calls always evaluated right after they were parsed, a design we now know can't work), whenever you put a recursive macro call inside the macro itself, you were hosed as either the parser disappeared into the black lagoon as it explored the feasibility of recursion without a base case... or it would just fail outright because we caught that case. Now, instead, you can recurse, as long as you put the macro call in the quasi block.

So I'm pretty happy with this discovery. (And I'm fully prepared for TimToady coming along saying that he knew this already, and I just didn't read the spec in the right way. 😜)

There's more. This finding is part of a larger trend where parsing gets un-tangled from another, later process that I don't yet have a really good name for. Within the scope of this post, let's call it checking... and I'll reserve the right to call it something better once I have a better name. Suggestions welcome. ("Checking" is slightly unfortunate, because it sounds like it would happen at CHECK time. Some of these things, such as the macro expansion, need to happen before that.)

Some random examples of checking:

Many things that we consider to be part of parsing turn out to be part of checking, when you start to think about it. Taking quasis seriously leads to needing to tease parsing and checking apart. Some parts of checking we still want to do ASAP, interleaved with parsing. (For example: I'd expect to get an immediate "not declared" error if I typo'd a variable inside a quasi. Shouldn't have to wait until I call the macro.)

The rabbit hole goes deep on this one. If we expect quasis to have unquotes for operators, then we can't even reliably parse an expression into a tree, because the exact structure of that tree depends on the precedence and maybe associativity of the operator we haven't injected yet! This leads to the uncomfortable question of what a quasi really is, if it isn't a Qtree representation of some code. In this case at least, it seems the best we can do is store the sequential order of terms and operators, so that we can expand them into the correct tree upon checking. (And this needs to be reflected somehow in Qtree introspection.) This should worry you: producing that tree is what parsing traditionally does. But here we provably can't: heck, the operator we end up injecting might not even be defined yet.

Despite all, I'm hopeful. I'm happy quasis force macros to late-bind, because that makes macros more useful. I'm curious where the whole parsing/checking distinction will lead. The stuff with the operators looks challenging, but that's an improvement over what we had before in that slot, which was "what huh wait I don't even".

Not addressed in this prop... hey, wait

This isn't a proposal. It's just the harsh, undeniable reality. I find that the five-or-so things I usually bring up as addressed or not addressed aren't really relevant here.

However, let's do a quick summary, since it's been long since I posted about this:

When I don't even feel like using blame

The other day we ran into a bug in the following code in the Perl 6 setting:

multi method sign(Real:D:) {
    self < 0 ?? -1 !! self == 0 ?? 0 !! 1

Kudos to you if you automatically start poring over the cases in that function, trying to see which one is the wrong one. You won't find it though.

The function implements what is more or less the mathematical definition of the sign (or sgn) function:

          | -1      if x  < 0
sign(x) = |  0      if x == 0
          | +1      if x  > 0

The method does exactly this. So what's the problem?

Right, NaN.

Before the bug was fixed, you'd get this, which is surely wrong:

$ perl6 -e 'say sign(NaN)'

Oh, and this is what the fixed code looks like:

multi method sign(NaN:)    { NaN }
multi method sign(Real:D:) { self < 0 ?? -1 !! self == 0 ?? 0 !! 1 }

(That is, original method remains the same, but a new multi candidate handles the NaN-invocant case.)

And now it does the right thing:

$ perl6 -e 'say sign(NaN)'

I'm trying to come up with an appropriate emotion to go with this kind of bug. It's hard to muster any strong sentiment either way, but I think it's appropriate to say I'm sick of this kind of bug. I wish it were a thing of the past. It feels like it should be a thing of the past.

See, the code looks right. It's based right off of the mathematical definition of real numbers. The only slight mistake the original author made was briefly forgetting about the strange numeric value IEEE 754 specifies called "not a number" (NaN), which demands to be taken into account when doing this kind of exhaustive case-matching.

Don't get me wrong. NaN is there for a reason, and I'm not clamoring for its removal. The IEEE 754 people certainly had their hearts and their heads in the right place. They got a lot of things right, including the inclusion of NaN. There has to be something that's returned when you take the square root of negative 1, or multiply zero with infinity, or try to find a limit which doesn't exist.

No, what frustrates and exhausts me is that it's 2015, and we're still creating bugs rooted in lack of exhaustive case-matching. This should be a solved problem by now. We ought to have moved on to more interesting challenges.

And indeed, solutions exist out there. There are linters that will point out when you've left out an important case. (Not for Perl 6, yet, but there's nothing to stop us from having one.) Some languages have case statements over enum types where you're not allowed to leave out a case. Nowadays we also handle things with Maybe or Option types.

These things are not even fancy new technology at this point. They're proven to work, and to improve the incidence of thinkos and the quality of code. If we're not equipped with a language (or tooling) that checks this stuff for us, we're part of a rapidly shrinking unfortunate majority. If we're not looking to fix that in our home language, we're increasingly irresponsible and reckless.

This is what computing machines are good at! Enumerating cases! We should be having them do that all the time, on our business-critical code. Or, conversely, just writing code without the safety net of full enumeration of cases should be rightly recognized as belonging with other barbaric development practices of the mid-20th century, surely caused by extreme scarcity of memory or CPU, but which we have — ought to have — grown out of by now.

But... sigh... yes, the code looks right. Which is why I don't particularly feel like running git blame on it this time.

Maybe the code snippet was even code-reviewed, and someone had looked at it, nodded, and (at some more or less conscious level) noted that the code aligns perfectly with the mathematical three-case definition. A real number is either smaller than, equal to, or greater than zero. Sure, we know that! This hypothetical code reviewer did not have alarm bells go off just becase the case of NaN wasn't considered. Because NaN is an exception, a fairly uncommon one, and humans enjoy thinking about happy paths.

A lot of what constitutes "experience" in a developer seems to be installing these alarm bells in prominent places in one's brain, so that one can write code that's "robust" in the face of unusual values and unhappy paths. Two other such cases spring to mind:

(And indeed, NaN is a kind of "null value" for floating-point numbers.)

But it's also about considering edge cases in general. What if the list is empty when we ask for an element? What if the network is unavailable when we try to access a web service? What if the player can exceed 2,147,483,647 points in the game? Things like this can, and should be checked automatically, by the machine, as we developers worry about higher levels of abstraction.

Don't settle for less. Let the machine check that we've considered all the cases.