PredicateDecl = Category Ident Signature Rules .
Category = "'nonterm'" | "'token'" | "'action'"
       | "'condition'" | "'choice'" | "'sweep'" .
Signature =
        ["(" [ParamSpec{ "," ParamSpec}] ["->"[ParamSpec{ "," ParamSpec}]]")"] .
Rules = {Head ":" Body "."} | {"'rule'" Head [":"] Body ["."]} .
Head = Ident ["(" [Pattern{ "," Pattern}] ["->" [Expression{ "," Expression}]] ")"] .
Body = {Member} [CostSpec]
CostSpec = "$" Number .

Predicate Declarations

A predicate declaration of the form

  • Category p ( T1 , ... , Tn -> S1 , ... , Sm )

introduces a predicate p of category Category with n input parameters of types T1, ..., Tn, and with m output parameters of types S1, ..., Sm.

A predicate may be used in a predicate invocation.

A predicate that is invoked with input values Tau1, ..., Taun is elaborated as follows. If no rule is applicable, the invocation fails. Otherwise, a rule is selected and elaborated, yielding output values Sigma1, ..., Sigman, and the invocation succeeds.


'condition' HasCode (Color -> INT)
'rule' HasCode(red -> 1)
'rule' HasCode(yellow -> 2)

An invocation of HasCode with input value yellow succeeds and yields output value 2. An invocation of HasCode with input value blue fails.


A rule has the form
  • 'rule' p ( P1 , ... , Pn -> E1 , ... , Em ) : M1 ... Mk

For given input values Tau1, ..., Taun, the rule is elaborated as follows. Let V1, ..., Vnin be the variables appearing in P1, ..., Pn, and W1, ..., Wnout the variables appearing in E1, ..., Em. If the input values Tau1, ..., Taun do not match the patterns P1, ..., Pn, the rule is not applicable. Otherwise, the variables V1, ..., Vnin are defined. Then the members M1 ... Mk are elaborated. If one of the members fails, the rule is not applicable. Otherwise, the variables W1, ..., Wnout are defined. The expressions E1 ... Em are evaluated, yielding output values Sigma1, ..., Sigmam.

A variable that appears in a pattern is said to be defined. A variable that appears in an expression is said to be applied. Each applied variable must be a defined variable. Variables that are applied in a member Mi must be defined by one of the patterns P1, ..., Pn or in a member Mj that appears to the left of Mi . A defined variable cannot be redefined.


'action' append(List, List -> List)
'rule' append(list(H,T), L -> list(H, TL): append(T, L -> TL)
'rule' append(nil, L -> L)

For input values Tau1 = list(red,nil) and Tau2 = list(yellow,nil), the second rule is not applicable because Tau1 nil.

The elaboration of the first rule matches Tau1 with list(H,T) defining H as red and T as nil; it matches Tau2 with L, defining L as list(yellow,nil).

The member append(T,L -> TL) defines TL as list(yellow,nil).

The output value Sigma1 = list(red,(list(yellow,nil)) is yielded by replacing H and TL in list(H,TL) by their values.