Custom operators for Knuth’s Arrow

The Wikipedia page for Knuth’s up arrow notation makes some claims about superscripts:

But many environments — such as programming languages and plain-text e-mail — do not support superscript typesetting.

I’ll ignore the claim that plain text (their parochial definition) is the same thing as 7-bit text ASCII.

The first claim, however, isn’t strictly true for Perl 6 and probably many other more esoteric languages (let me know if you know which ones you know about). It got me thinking about what I could do in Perl 6.

Perl 6 uses superscripts as operators defined in the core language. I found this out between the time they were implemented and later documented when I tried to use them in variable names. Now I can write some exponentiations with superscripts:

my $square = $n²;  # valid Perl 6, same as $n ** 2

I can’t superscript superscripts or superscript superscripts of superscripts though and that’s what most of that claim is about. Adding a character that is already a superscript isn’t the point. We typically don’t type something like these power towers directly without some sort of being-the-scenes formatting instructions (so, not plain text). I do this with \(\LaTeX\):




But Perl 6 also provides builtin features that it fully expects people to use to extend the language. I can create these operators myself. (Note that in mathematics, the up arrow is an example of a hyperoperator but that has a completely different meaning from the Perl 6 hyperoperators that apply an operation to corresponding elements of two lists.)

I can create an up-arrow operator, . Had I googled first I would have found that it’s already been done in Math::Arrow.

A single up arrow is the same as exponentiation but without a superscript. The operand on the left is raised to the power on the right. It’s in the progression of + for addition, * for multiplication, and then for exponentation. This is the basis for higher orders later.

It’s a binary infix operator (takes two operands and goes in the middle) so I add my symbols in the angle brackets after the infix:. I specify that it’s right associative (as is exponentiation) and that it has the same precedence as exponentiation:

sub infix:<↑> ( Int:D \n, Int:D \m  --> Int:D )
	is equiv(&infix:<**>)
	is assoc<right>
	{ n ** m }

put 2 ↑  3;  # 2  * 2  * 2 =  8

That’s only the starting point. With this notation I can define higher orders of repetition. The double up arrow, ↑↑, is repeated exponentiation just like multiplication is repeated addition. The number on the right is one more than the number of exponentiations in the power tower (the other one is the base):

$$2↑↑4 = 2^{2^{2^2}}$$

I make a couple of subroutine definitions here to handle the special cases where the second operand is 0 or 1 since the reduction operator won’t deal with those cases. Since these subroutines have the same name I use multi to define the candidates. The dispatcher figures out which one fits best and use that:

proto infix:<↑↑> ( Int:D \n, Int:D \m  --> Int:D )
	is tighter(&infix:<↑>)
	is assoc<right>
	{ * }
multi infix:<↑↑> ( \n, 0  ) { 1 }
multi infix:<↑↑> ( \n, 0  ) { \n }
multi infix:<↑↑> ( \n, \m ) { [↑] n xx m }

put 2 ↑  3;  # 2  * 2  * 2 =  8
put 2 ↑↑ 3;  # 2 ** 2 ** 2 = 16

The proto defines the basic template for all candidates with the same name. That’s where I can constrain the types of values and set the associativity and precedence. It’s the gatekeeper; once I annotate the types and set the traits I don’t need to annotate them in the candidates (and in some cases can’t re-define them).

I make the double arrow version tighter than the single arrow one I just defined. The * in the proto block dispatches to the best candidate of the same name. The two multis can then assume everything that needs to be checked was already handled.

Now I can extend that to the triple up arrow ↑↑↑. It’s the same thing with an additional up arrow:

proto infix:<↑↑↑> ( Int:D \n, Int:D \m  --> Int:D )
	is assoc<right>
	is tighter(&infix:<↑↑>)  { * }
multi infix:<↑↑↑> ( \n,  0 ) { 1 }
multi infix:<↑↑↑> ( \n, \m ) { [↑↑] n xx m }

put 2 ↑   3;  # 2  *  2  * 2  =  8
put 2 ↑↑  3;  # 2 ↑   2 ↑  2  = 16
put 2 ↑↑↑ 3;  # 2 ↑↑ (2 ↑↑ 2) = 256

But there’s an alternate notation that goes back further than Knuth’s up arrow. I can define prefix superscripts that denote particular up arrow versions. These use superscripts:

multi prefix:<⁰>  ( Int:D $m ) { 1 }
multi prefix:<²>  ( Int:D $m ) { $m ↑↑ 2 }
multi prefix:<³>  ( Int:D $m ) { $m ↑↑ 3 }
multi prefix:<³>  ( Int:D $m ) { $m ↑↑ 4 }

put ²2;
put ⁴2;
put ²3;
put ³3;

There’s yet another notation that doesn’t use repeated arrows. It uses a superscript on the arrow to specify how many arrows there are:

multi infix:<↑²> ( Int:D \n, 0        --> Int:D )
	is equiv(&infix:<↑↑>)
	is assoc<right> { 1 }
multi infix:<↑²> ( Int:D \n, 1        --> Int:D )
	is equiv(&infix:<↑↑>)
	is assoc<right> { n }
multi infix:<↑²> ( Int:D \n, Int:D \m --> Int:D )
	is equiv(&infix:<↑↑>)
	is assoc<right> { [↑] n xx m }

You get the idea. I’ve made a much longer demonstration program that’s in a gist.

Some things that came out of exercise

Leave a Reply

Your email address will not be published. Required fields are marked *