1. The method add-dependency in Task permits the creation of cycles in the dependency graph. That is, if you follow dependencies, you can eventually return to the original Task. Show how to create a graph with cycles and explain why the perform method of a Task whose dependencies contain a cycle would never terminate successfully.

Answer: You can create two tasks, and then "short-circuit" them with add-dependency:

    my $a = Task.new({ say 'A' });
    my $b = Task.new({ say 'B' }, $a);
    $a.add-dependency($b);

The perform method will never terminate because the first thing the method does is to call all the perform methods of its dependencies. Because $a and $b are dependencies of each other, none of them would ever get around to calling their callbacks. The program will exhaust memory before it ever prints 'A' or 'B'.

2. Is there a way to detect the presence of a cycle during the course of a perform call? Is there a way to prevent cycles from ever forming through add-dependency?

Answer: To detect the presence of a cycle during a perform call, keep track of which Tasks have started; prevent a Task from starting twice before finishing:

    augment class Task {
        has Bool $!started = False;

        method perform() {
            if $!started++ && !$!done {
                die "Cycle detected, aborting";
            }

            unless $!done {
                .perform() for @!dependencies;
                &!callback();
                $!done = True;
            }
        }
    }

Another approach is to stop cycles from forming during add-dependency by checking whether there's already a dependency running in the other direction. (This is the only situation in which a cycle can occur.) This requires the addition of a helper method depends-on, which checks whether a task depends on another one, either directly or transitively. Note the use of » and [||] to write succinctly what would otherwise have involved looping over all the dependencies of the Task:

    augment class Task {
        method depends-on(Task $some-task) {
            $some-task === any(@!dependencies)
            [||] @!dependencies».depends-on($some-task)
        }

        method add-dependency(Task $dependency) {
            if $dependency.depends-on(self) {
                warn 'Cannot add that task, since it would introduce a cycle.';
                return;
            }
            push @!dependencies, $dependency;
        }
    }

3. How could Task objects execute their dependencies in parallel? (Think especially about how to avoid collisions in "diamond dependencies", where a Task has two different dependencies which in turn have the same dependency.)

Answer: Enabling parallelism is easy; change the line .perform() for @!dependencies; into @!dependencies».perform(). However, there may be race conditions in the case of diamond dependencies, wherein Tasks A starts B and C in parallel, and both start a copy of D, making D run twice. The solution to this is the same as with the cycle-detection in Question 2: introducing an attribute $!started. Note that it's impolite to die if a Task has started but not yet finished, because this time it might be due to parallelism rather than cycles:

    augment class Task {
        has Bool $!started = False;

        method perform() {
            unless $!started++ {
                @!dependencies».perform();
                &!callback();
                $!done = True;
            }
        }
    }