anchor.diff:  (defpackage "FUTURE"
     (:use "CL" "SB-EXT" "SB-THREAD")
  -  (:export "FUTURE" "TASK-FUTURE" "BULK-FUTURE"
  +  (:export "FUTURE"
              "DEPENDENTS"
              "STATUS" "WAIT" "CANCEL"
  -           "MARK-DEPENDENCIES" "MARK-DONE"))
  +           "MARK-DEPENDENCIES" "MARK-DONE" "THAW"))
  +
  +;;; Infrastructure for futures: lenient-evaluated values
  +;;;
  +;;; A future is a computation with a set of dependencies; whenever
  +;;; all the dependencies for a computation have been fully executed,
  +;;; it too is executed.
  +;;;
  +;;; In order to do so, each future also tracks its antidependencies
  +;;; in list of weak pointers.  When the future is marked as done, the
  +;;; depcount (number of yet unfulfilled dependencies) of its
  +;;; antidependencies is decremented.  When all the dependencies are
  +;;; fullfilled (depcount is zero), the future is recursively executed.
  +;;;
  +;;; For convenience, futures are also bulk-tasks, but this is irrelevant
  +;;; to the interface.
  +;;;
  +;;; Slots in a FUTURE:
  +;;;  function: list designator of functions to be called on execution;
  +;;;            they receive the future as their single argument.
  +;;;  dependents: list of weak pointers to antidependencies, initialized
  +;;;              to zero and updated on demand.
  +;;;  dependencies: vector of dependencies
  +;;;  depcount: number of dependencies yet to be fullfilled, updated on
  +;;;            demand.
  +;;;  %status: current status of the future.  Upgraded to a slow, lock-ful
  +;;;           representation as needed.
  +;;;
  +;;; A future goes through a few stages:
  +;;;
  +;;;  :orphan is the initial stage.  The future is initialized, but not
  +;;;     yet linked to its dependencies.
  +;;;  :frozen futures have been linked to their dependencies (via
  +;;;    MARK-DEPENDENCIES), but not been marked for execution.
  +;;;  :waiting futures have been marked for execution (via THAW),
  +;;;    and will wait until all their dependencies are satisfied.
  +;;;  :running futures have had all their dependencies satisfied
  +;;;  :done futures have finished executing
  +;;;  :cancelled futures have been cancalled
  +;;;
  +;;; STATUS and WAIT can be used to poll a future's current status or wait
  +;;;  until it becomes equal to a value in a set of status.
  +;;;
  +;;; CANCEL marks a future as cancelled, unless it is already executing.
  +;;;
  +;;; Creating a future should follow this pattern:
  +;;;  - Allocate a future
  +;;;  - MARK-DEPENDENCIES
  +;;;  - Maybe walk its DEPENDENTS list for analyses
  +;;;  - THAW it
  +;;;  - Maybe WAIT until :cancelled or :done
   
   (in-package "FUTURE")
  +
   (deftype status ()
  -  '(member :frozen :waiting :running :done :cancelled))
  +  '(member :orphan :frozen :waiting :running :done :cancelled))
   
   (defstruct (slow-status
               (:constructor
  -                make-slow-status (&optional (status :frozen))))
  -  (status :waiting         :type status)
  +                make-slow-status (&optional (status :orphan))))
  +  (status :orphan          :type status)
     (lock   (make-mutex)     :type mutex
                              :read-only t)
     (cvar   (make-waitqueue) :type waitqueue
  
positive.code:   (unless (eql (status-upgrade future :running :waiting)
                 :waiting)
      (return-from execute))
    (funcall (future-fun future) future))
  
  (defun cancel (future)
    (declare (type future future))
    (let ((status (status-upgrade future :cancelled :waiting)))
      (when (eql status :waiting)
        ;; recursively mark as cancelled?
        (setf (future-antideps future) :cancelled))
      status))
  
  (defun mark-dependencies (future dependencies)
    (declare (type future future))
    (let ((wp          (make-weak-pointer future))
          (any-waiting nil))
      (flet ((mark-dep (dep)
               (declare (type future dep))
               (ecase (status dep)
                 ((:waiting :running))
                 (:done
                  (return-from mark-dep))
                 (:cancelled
                  (error "Dependency cancelled")))
               (let ((cons (list wp)))
                 (atomic-incf (future-waitcount future))
                 (loop
                   (let ((antideps (future-antideps dep)))
                     (setf (cdr cons) antideps)
                     (cond ((eql antideps :done)
                            (atomic-decf (future-waitcount future))
                            (return-from mark-dep))
                           ((eql antideps :cancelled)
                            ;; cancel self?
                            (atomic-decf (future-waitcount future))
                            (error "Dependency cancelled"))
                           ((eql (compare-and-swap (future-antideps dep)
                                                   antideps
                                                   cons)
                                 antideps)
                            (setf any-waiting nil)
                            (return-from mark-dep))))))))
        (declare (dynamic-extent #'mark-dep))
        (map nil #'mark-dep dependencies)
        (unless any-waiting
          (execute future)))))
  
  (defun mark-done (future)
    (declare (type future future))
    (unless (eql :running (status-upgrade future :done :running))
      (return-from mark-done))
    (let ((antideps
            (loop
              (let ((antideps (future-antideps future)))
                (when (or (eql antideps :done)
                           (eql antideps :cancelled))
                  (return-from mark-done))
                (when (eql (compare-and-swap (future-antideps future)
                                             antideps :done)
                           antideps)
                  (return antideps))))))
      (map-into antideps
                (lambda (wp)
                  (let ((value (weak-pointer-value wp)))
                    (when (and value
                               (eql :waiting (status value))
                               (= 1 (atomic-decf (future-waitcount value))))
                      (execute value)))
                  nil)
                antideps)
      nil))
  
negative.code: (defstruct (future
              (:include work-stack:bulk-task)
              (:constructor nil))
    (function     nil :type (or list symbol function) :read-only t)
    (dependents   nil :type (or list (member :done :cancelled)))
    (dependencies nil :type simple-vector    :read-only t)
    (depcount       0 :type word)
    (%status  :orphan :type (or status slow-status)))
  
  (defun dependents (future)
    (let ((dependents (future-dependents future)))
      (and (listp dependents)
           dependents)))
  
  (defun status (future)
    (declare (type future future))
  