Co-routining

[User's Manual]
[Code--Compiling Conditionals] [Code--Coroutining Primitives]
SICStus Prolog follows a more complicated rule for computation than traditional implementations of Prolog. Instead of simply evaluating the leftmost rule in its search path, it evaluates the leftmost unblocked rule in its search path. This mechanism resembles co-routines in imperative programming languages, i.e., suspending and resuming different threads of control. SICStus Prolog provides some built-in co-routining predicates some of which, that are relevant to our discussion here, are as follows:

SICStus when/2 suspends a goal until (i) a variable is instantiated or (ii) two variables are equated or inequated. The latter case corresponds directly to structure-sharing and inequations in typed feature structures. The former, if it were to be carried over directly, would correspond to delaying until a variable was promoted to a type more specific than $\bot$ . There are degrees of instantiation in the logic of typed feature structures, however, corresponding to subsumption chains that terminate in a most specific type. With signature in which this chain is of length more than two, a more general and useful primitive is then suspending until a variable is promoted to a particular type. As discussed in the User's Guide, ALE has its own version of when/2 which is designed for work with typed-feature structures. Table 6.1 shows how various when/2 calls in ALE are compiled. Conjunction and disjunction of conditionals are compiled as conjunctions and disjunctions respectively.

Input	Output
`when((FS=F:Desc), Goal)`	`when_type(FIntro,FS,DescGoal)` where `FIntro` is the introducer of `F`; and `DescGoal` is the result of compiling `Goal`.
`when(FS=(Path1==Path2), Goal)`	Treated as `when(Y^(FS=(Path1:Y, Path2:Y)), Goal)`.
`when(FS=Var,Goal)`	`when_eq(FS,Var,Goal)` if `Var not seen`; otherwise, unify `FS` and `Var` and call `Goal`.
`when(FS=Type,Goal)`	If `Type` is $\bot$ , then call `Goal`; otherwise, `when_type(Type,FS,Goal)`.

when_type(Type,FS,Goal) is used to delay Goal until variable FS reaches type Type. To implement when_type(Type,FS,Goal), ALEactually uses the underlying Prolog implementation of when/2. Types with no appropriate features constitute the base case, in which only delaying on the internal structure of the type's representation (which can be as simple as the type's name or a compound term encoding) is necessary. For types with appropriate features, we must ensure that our suspended Goal does not fire in between the time when the internal representation of a feature structure's type is updated, and when the appropriateness conditions for that type are enforced on the representation. To do otherwise would risk passing a non-well-typed or even non-well-formed representation in FS to the delayed Goal. What when_type/3 must do is thus delay on the entire structure of the (well-typed) most general satisfier of its Type argument, relative just to appropriateness and the type system, i.e., without considering any implicational constraints. That most general satisfier is guaranteed not to have any structure-sharing since appropriateness is not able to require this. As a result, only recursively delaying on the value restrictions of its appropriate features is necessary.

More specifically, when_type/3 delays the execution of Goal until such time that FS is not a variable and Type subsumes the type of FS. If it does not subsume the type of FS, then the execution of Goal is suspended until Type is an appropriate value restriction for the type of FS. If Type and the type of FS are not unifiable, then the when_type/3 declaration is abondoned.

Another co-routining predicate used in ALE is when_eq/3. Basically, when_eq(FS1,FS2,Goal) suspends Goal until FS1 == FS2. This is implemented using Prolog when/2 together with ?=/2.

A similar co-routining predicate, when_a_(X,FS,Goal), delays the execution of Goal until the feature structure FS becomes the argument of the a_ atom used in X. when_a_chk/3 is a very similar predicate, but rather than using ==/2 as in when_a_/3, it uses subsumes_chk/2 to see whether X subsumes the argument of a_. This is necessary for checking appropriateness conditions with a_/1 value restrictions, in which token-identity of variables has no significance.

Delaying on appropriateness restrictions is performed by when_approp(Type,SVs,Goal) which, as stated above, delays Goal until, Type becomes an appropriate value restriction for SVs.