How are Junctions evaluated?

Question

The idea of Junctions were originally introduced by Damian Conway in order to mimick Quantum superposition and express Quantum Computing algorithms.

As cute at this may be, the concepts of superposition and collapsing don't make sense in a programming context and the evaluations rules are far from being clear.

Answer 1

A junction is just a set of values inside of a wrapper which is any, all, one, or none depending on the operator used to create the junction. We'll talk about the differences between the four types later; for the most part they behave exactly the same.

When you pass a junction to any function, method, or operator except those explicitly declared to take a Junction, the call is "autothreaded" and the result will be a junction. This is actually very simple and not at all quantum: (1 & 2 & 3) * 2 equals 1 * 2 & 2 * 2 & 3 * 2 equals
2 & 4 & 6, and f(any(1, 2, 3)) equals any(f(1), f(2), f(3)). The order of items in a junction, as with a set, is insignificant, and Raku can, if it feels like it, evaluate autothreaded operations in parallel, so there might be more than one call to f going on at once.

When a junction is coerced to Bool, either by context or by an explicit operator like so, it becomes a single value. An any junction will be True if any of the values it contains are true, an all junction is true only if all of its values are true (including the case where it contains no values), a none junction is true if none of its values are true, and a one if exactly one value inside is true.

So suppose we have

my @words = <raku is fun>;
if all(@words).chars < 10 {
    say "nice short words";
}

this will print, because all(@words).chars < 10 is the same as
all('raku'.chars, 'is'.chars, 'fun'.chars) < 10, which is
all(4, 2, 3) < 10, which is
all(4 < 10, 2 < 10, 3 < 10), which is
all(True, True, True), and so all(True, True, True) is True.

Likewise so $num %% one(3, 5) will be true if $num is a multiple of 3, or a multiple of 5, but not a multiple of 15.

Answer 2

As a follow up on Hobbs answer and comments:

As it turns out, the distributivity behavior of the junctions is not the whole story. This is how the following expression would be evaluated if that were the case.

(1 | 2) + (3 & 4)

1 + (3 & 4)       ==> all(4, 5)
2 + (3 & 4)       ==> all(5, 6)

(4 & 5) | (5 & 6) ==> any(all(4, 5), all(5, 6))

but the actual evaluation produces:

(1 | 2) + (3 & 4) ==> all(any(4, 5), any(5, 6))

The junctive types affect the evaluation of an expression composed of more than one junctions. The solution was found here: https://design.raku.org/S09.html#Junctions, which I'll just quote.

If two or more arguments are junctive, then the argument that is chosen to be "autothreaded" is:

• the left-most all or none junction (if any), or else
• the left-most one or any junction

with the tests applied in that order.

Each of the resulting set of calls is then recursively autothreaded until no more junctive arguments remain. That is:

   substr("camel", 0|1, 2&3)
-> all( substr("camel", 0|1, 2),      # autothread the conjunctive arg
        substr("camel", 0|1, 3)
      )
-> all( any( substr("camel", 0, 2),   # autothread the disjunctive arg
             substr("camel", 1, 2),
           ),
        any( substr("camel", 0, 3),   # autothread the disjunctive arg
             substr("camel", 1, 3),
           )
      )
-> all( any( "ca",                    # evaluate
             "am",
           ),
        any( "cam",
             "ame",
           )
-> ("ca"|"am") & ("cam"|"ame")        # recombine results in junctions

Following these rules, (1 | 2) + (3 & 4) is evaluated as follows:

(1 | 2) + (3 & 4)

((1 | 2) + 3) & ((1 | 2) + 4)

(4 | 5) & (5 | 6)

The same rules also correctly derive the evaluation of the following expressions:

any(1, 2) + all(10, 20)
==>
all(any(11, 12), any(21, 22))

all(1, 2) + any(10, 20)
==>
all(any(11, 21), any(12, 22))


one(1, 2, 3) + any(4, 5)
==>
one(any(5, 6), any(6, 7), any(7, 8))

one(1, 2, 3) + one(4, 5)
==>
one(one(5, 6), one(6, 7), one(7, 8))

one(1, 2, 3) + all(4, 5)
==>
all(one(5, 6, 7), one(6, 7, 8))

one(1, 2, 3) + none(4, 5)
==>
none(one(5, 6, 7), one(6, 7, 8))

Those basic expression evaluation rules are completely missing from https://docs.raku.org/type/Junction, so the official documentation wasn't of any help.

PS: Kudos to raiph for finding the answer too.

EDIT:

After reading this section https://design.raku.org/S09.html#Junctions, you would think that expressions containing junctions would be desugared at compile time with macros but that's not how it is done. Everything happens at run time but what happens in the AUTOTHREAD method below looks a lot like the macro expansion process.

How are junctions evaluated?

• regular values (values of type Any, any value that isn't a junction) evaluate to themselves

• junctions (there are 4 junctive types: any, all, one, none) evaluate to themselves

• any(), all(), one(), none() (or their respective operators infix:<|>, infix:<&>, infix:<^>. none() does not have an associated operator) have their arguments evaluated normally and a junction value is constructed and returned. The type of the arguments (Any or Junction) is irrelevant.

(type really means type/subtype here)

• function calls where all arguments are of the type Any, or of the type Junction but with a corresponding parameter also of type Junction (or Mu) are regular function calls

• function calls with at least one argument of type Junction with a corresponding parameter of type Any have multiple dispatch failing and falling back to method AUTOTHREAD(&call, |args) in https://github.com/rakudo/rakudo/blob/main/src/core.c/Junction.pm6.

Below is a simplified (and mostly correct) translation of AUTOTHREAD in Perl.

Calling infix:<+>(1 | 2, 3) have the effect that infix:<+>(1, 3) | infix:<+>(2, 3) is returned and that process is really similar to macro expansion, which is possible because of the indirection created by the multiple dispatch and the fallback to AUTOTHREAD. This is both fascinating and horrifying.

sub AUTOTHREAD {
    my ($call, $args) = @_;
    my $positionals = $args->{list};

    sub thread_junction {
        my $pos = shift;
        my $junction = $positionals->[$pos];
        my @storage = $junction->{eigenstates}->@*;
        my @result;

        for (my $i=0; $i < @storage; $i++) {
            $positionals->[$pos] = $storage[$i];
            push @result, $call->($args);   # really multiple_dispatch($call, $args)
        }
        Junction->new(type => $junction->{type}, eigenstates => \@result);
    }

    for (my $i=0; $i < $positionals->@*; $i++) {
        my $arg = $positionals->[$i];
        if ($arg isa Junction) {
            if ($arg->{type} eq "all" || $arg->{type} eq "none") {
                return thread_junction($i);
            }
        }
    }

    for (my $i=0; $i < $positionals->@*; $i++) {
        my $arg = $positionals->[$i];
        if ($arg isa Junction) {
            if ($arg->{type} eq "any" || $arg->{type} eq "one") {
                return thread_junction($i);
            }
        }
    }

    my $named = $args->{hash};

    for my $key (keys $named->%*) {
        my $arg = $named->{$key};
        if ($arg isa Junction) {

            my $junction = $arg;
            my @storage = $junction->{eigenstates}->@*;
            my @result;

            for (my $i=0; $i < @storage; $i++) {
                $named->{$key} = $storage[$i];
                push @result, $call->($args);   # really multiple_dispatch($call, $args)
            }
            return Junction->new(type => $junction->{type}, eigenstates => \@result);
        }
    }

    $call->($args);   # really multiple_dispatch($call, $args)
}