09 December 2011

Signals, continuations, and constraint-handling

Signals, continuations, constraint-handling, and more


I wrote about mutability and signals and automatically forcing promises where they conflict with required types.

Signals for Constraint-handling

Constraint-handling, and specifically the late-ordered evaluation it uses, could be treated by signals. Something like this:

  • Promises are our non-ground objects. They are, if you think about it, analogous to Prolog variables.
    • They can be passed around like objects.
    • But they're not "really" objects yet.
    • For them to "succeed", there must be some value that they can take.
    • That value can be determined after they are passed.
    • Everything else is either ground or a container that includes one or more of them.
  • As I already do in Klink, use of an non-ground argument is detected where it's unacceptable.
    • Generally, they're unacceptable where a type is expected (eg they're acceptable as arguments to cons)
  • Unlike what I do now, non-ground unacceptables send signals to a scheduler.
    • This implies that each evaluation is uniquely related to (owned by) one scheduler.
    • That signal passes as objects
      • the continuation as object.
      • The promise to be forced.
  • It is the job of the scheduler to ensure that the resulting computation completes.
    • In appropriate circumstances, eg with resource-quotas, or when doing parallel searches, it is reasonable to not complete.

An analogy

Computations whose flow can't be changed are analogous to constant objects and flow-changable ones analogous to mutable ones.

Another use: Precision

This mechanism could also be useful for "dataflow" precision management. Here the objects are not exactly promises, but they are incomplete in a very precise way. They are always numbers but their precision can be improved by steps.

Combiners that require more precision could signal to their generators, which could signal back their new values, propagating back their own requirements as needed. This is very manageable.

Apply-continuation and signals can mutually define

apply-continuation, while it could be used to implement signals, can also be implemented by signals between evaluations. It signals a scheduler to schedule the given continuation and deschedule the current continuation.

Done this way, it gives a scheduler flexibility. This might appear to make analysis more difficult. But a simple (brain-dead) scheduler could do it exactly the continuation way: exactly one evaluation is "in control" at all times. This might be the default scheduler.

In both cases this functionality is a neither-fish-nor-fowl hybrid between objects and computational flow. ISTM it has to be so.

signals allow indeterminate order

One mixed blessing about signals is that since they are "broadcast" 1-to-N, it can be indeterminate what is to be evaluated in what order.

  • Pro: This gives schedulers flexibility.
  • Con: Computations can give different results.
    • Continuation-based scheduling doesn't neccessarily do better. It could consult "random" to determine the order of computations.
  • Pro: Signals and their schedulers give us another handle to manage evaluation order dependency. A scheduler could co-operate with analysis by:
    • Promising that evaluations will behave "as if" done in some particular order.
    • Taking into account analysis
    • Providing information that makes analysis easier, short of simulating the scheduler.
      • Probably promising that no signals escape the scheduler itself, or only a few well-behaved ones do.
  • Pro: Regardless of the scheduler, analysis can treat signals as a propagating fringe. Everything not reached by the fringe is unaffected.

Should signal-blockers cause copies?

I suggested earlier that combiners might promise non-mutation by blocking mutation signals out.

One way to code this is to make such combiners deep-copy their arguments. Should this situation automatically cause copies to be made? ISTM yes.

  • Not an issue: User confusion. There is no case where a user reasonably expects different functionality than he gets.
    • He might expect a function to mutate an object and it doesn't - but why is he expecting that of a function that doesn't claim to mutate anything and moreover explicitly blocks that from happening? Bad docs could mislead him, but that's a documentation issue.
  • Not an issue: Performance.
    • Performance is always secondary to correctness.
    • Performance can be rescued by
      • copy-on-write objects
      • immutable objects
      • Analysis proving that no mutation actually occurs.

No comments:

Post a Comment