Comments on 13211-3 draft of 2010-04-01

Ulrich Neumerkel, 2010-06-22, history
Source for 13211-3 draft, local copy

There are several points lacking in the current draft:

  1. Missing informal descriptions of DCG constructs.
  2. No specification of relevant properties. In particular steadfastness.
  3. Overspecification due to irrelevant and incorrect code of several reference implementations.
  4. No clear organization
The current draft lacks informal descriptions of the constructs used in DCGs. In particular, there is no description of (',')//2, !//0, (\+)//1 and the meta-call. Further, it is impossible to conclude from the current draft any correctness or incorrectness of concrete translations. In particular, the "logical expansion of grammar rules" (clause 10) contains exactly the same error as the reference implementation does. In fact, there is not much difference between both. To illustrate this point consider the rule 
p --> \+ q.
and the following translations a concrete implementation might produce: 
p(Xs0,Xs) :- \+ q(Xs0,Xs). % t1

p(Xs,Xs) :- \+ q(Xs,_). % t2

p(Xs0,Xs) :- \+ q(Xs0,Xs), Xs0 = Xs.  % t3
While all three translations are incorrect, their incorrectness cannot be derived from the current document. In fact, t3 is the translation currently employed in the document itself. A document that is not able to justify precisely which translation is acceptable and which is not is of little normative value.

The only place where the current draft gives some detail is within the reference implementations. Unfortunately these reference implementations are unnecessarily complex due to many low-level optimizations and a separate interpreter for phrase/3. Further, the reference implementations have several defects.

To better cover the actual behaviour without going into the details of a concrete implementation, actual properties must be defined. With the help of such properties it is comparatively simple to identify errors.

Steadfastness of phrase/3

The built-in predicate phrase/3 shall be steadfast in the third argument. This means that for a goal phrase(NT, Xs0, Xs) the following equivalence must hold. For all NT, Xs0, Xs and a fresh new variable XsC:
phrase(NT, Xs0, Xs) ⇔ phrase(NT, Xs0, XsC), XsC = Xs
The equivalence does cover side effects.

epsilon//0-rule

A nonterminal with a name not otherwise occuring in the program, for example epsilon//0 can be inserted in any place of the grammar where a nonterminal is permitted, without changing the meaning of the grammar. 
epsilon --> [].
Many implementation errors in DCGs that were due to an incorrect translation can be identified with these rules. To illustrate this point, consider an error in the current draft

(\+)//1 translation error

phrase(\+[a],[a],[a]).
Succeeds.
Draft.
Fails.
SICStus, SWI, XSB, YAP.
Existence error.
B, CIAO, ECLiPSe, GNU.
phrase(\+[a],[a],XsC),XsC=[a].
Fails.
Draft, SICStus, SWI, XSB, YAP.
Existence error.
B, CIAO, ECLiPSe, GNU.
All working systems agree on the treatment of (\+)//1. Only the current draft is different. By delaying unification of the third argument also the Draft's reference implementation becomes correct.

!//0 in phrase/3

phrase(({C=!;C=[]},!), []).
Suceeds, unifying C = !.
DraftA, B, GNU, SICStus, SWI, XSB, YAP.
Existence error.
CIAO, ECLiPSe.
phrase(({C=!;C=[]},C), []).
Succeeds, unifying C = !.
DraftA
Succeeds, unifying C = !.
On backtracking, succeeds, unifying C = [].
B, GNU, SICStus, SWI, XSB, YAP
Existence error.
CIAO, ECLiPSe.
phrase(({C=!;C=[]},{!}), [], []).
Succeeds, unifying C = !.
On backtracking, succeeds, unifying C = []
DraftA
Succeeds, unifying C = !.
B, GNU, SICStus, SWI, XSB, YAP
Existence error.
CIAO, ECLiPSe.
call(((C=!;C=true), C)).
Suceeds, unifying C = !.
ECLiPSe, YAP
Suceeds, unifying C = !.
On backtracking, succeeds, unifying C = true.
ISO, B, CIAO, GNU, SICStus, SWI, XSB
All working systems agree here on the treatment of cut. Only the reference implementation in Annex A of the current draft is different.

{}//0 in phrase/3

phrase([],[]).
Succeeds.
Draft, B, GNU, SICStus, SWI, XSB, YAP
Existence error.
CIAO, ECLiPSe
phrase({},[]).
Succeeds.
Draft, SWI
Existence error.
B, CIAO, ECLiPSe, GNU, SICStus, XSB, YAP
With the exception of SWI, no other system has {}//0.

Control constructs

(->)//2 - if-then shall be disabled

In 13211-1 there are two different control constructs to express "if-then". First, there is 7.8.7 (->) if-then which is written as ( If -> Then ), and second 7.8.8 (;)/2 - if-then-else which is written as ( If -> Then ; Else ). If-then is often misunderstood as meaning ( If -> Then ; true ). However, it actually means ( If -> Then ; fail ). If-then is therefore a frequent source of errors.

The same misunderstandings apply to DCGs. It seems therefore advisable to define as control constructs

For (->)//2 a permission error, or an existence error shall be produced. Maybe also translation shall be prevented. Further, user defined nonterminals (->)//2 must be rejected.

In case no agreement is possible on this point, the usage and definition of (->)//2 shall be implementation dependent.

Detailed comments

Introduction: There are no "Technical Recommendations" of ISO/IEC.
5.1. e: Which particular implementation specific feature could be excluded here? It seems that only implementation defined and dependend features are of relevance.
6.3.4.4 Add op(1105,xfy,'|') to the standard operator table. A justification is given separately.
7.14.3 push-back lists
They should be rather called context or right-context or context to the right.
7.14.6 Expand control constructs section
This part needs a more prominent place, presenting each nonterminal and describing informally its meaning.
7.14.6 unrecognized control constructs
It is required that call/1 shall not be recognized as a control construct. One paragraph later, it is mentioned that call//1 shall lead to call/3.
7.14.7 call/3
The entire section needs to be rewritten. It is probably better as call/N within a second corrigendum. Error cases must not be delegated to the implementation specific documentation!
8.1.1.2 The unclear notion "optional" errors should be clarified within the normative context: Probably implementation defined.
10 Logical expansion
Remove this section. It contains the same error for (\+)//1.
11 Reference implementations - normative impact?
The reference implementations provided in this section do not preclude alternative or optimized implementations. What is the exact role of those if they do not preclude anything?
11.1: Avoid conflicting names
The reference implementation should avoid conflicting names like phrase/3. Otherwise the reference implementation cannot be loaded unaltered.
11.1: Errors do not conform to 13211-1:1995 7.12.1
The error-term error/2 is missing. E.g. throw(instantiation_error) shall be replaced by throw(error(instantiation_error, _ImpDef))
11.1: dcg_terminals: handle errors with e.g. must_be_list/1.
11.1: dcg_rule/4: Rewrite to dcg_rule/2
Make output unifications explicit, no more optimizations!
11.1: dcg_body/4: Order of nonterminals unintuitive
Start with simple (',')//2 first.
11.1: dcg_body/4: Missing rule for call//1.
11.1: dcg_body/4: Remove (->)//2
Add extra rule for if-then-else instead.
11.1: dcg_body/4: (\+)//1
Replace last occurence of S by _.
11.1: Remove dcg_simplify/4
It contains opaque and incorrect optimizations.
11.1: Remove dcg_fold_left
It fails to translate the following rule. 
p --> {a=b}.
Further, this optimization is STO!
11.1: Remove fold_pairs
It is an incorrect optimization because intermediary variables cannot be removed - there might be other references to them. This optimizations turns the failing goal phrase(p,[]) into success. 
p --> epsilon, {_=I,I=a,I=b}.
epsilon --> [].
11.3: Auxiliary predicates
The name is_proper_list is misleading. The terminology in 13211-1 is partial list (3.125) and list.
12: Test-cases for the reference implemetations.
Are these test cases normative or not?
12: Remove test harness test_gr_preds/0, test_gr_tr/0, create_gr_file/0,
12: test case 802
This case will not compile on most processors. Why is it included?
12: test case 908, 909
A more systematic presentation would useful. E.g. p, [a,b] --> q. and p, [a], [b] --> q.(error)
Remove Appendix A
It contains an interpreter for phrase/3 that does not reflect current behaviour - in particular with respect to the metacall and cuts. The errors do not conform with 13211-1:1995, since the second argument must be an implementation defined term. However, a concrete term is given.
A: dcg_clause/1 vs. dcg_clause/2.
Which one shall be used, not both.

Comparison with Udine Resolutions

The DCG-relevant Udine resultions were:
a. Error handling on phrase is to be optional. The example phrase({X=a}, X,X) shows how complex error handling could be when the items being processed are lists.
This has been insufficiently addressed in 8.1.1.3. The notion "optional" is alien to 13211-1. It is not clear what exactly optional means. Shall every implementation offer this option? To my understanding, the idea was rather to have error handling as an implementation defined feature.
b. It was agreed that the behavior of DCG expansions that led to conflict with a Built in predicate the behaviour should be implementation defined.
This has been insufficiently covered in 7.14.8. When defining a nonterminal a//N, 7.14.8 now effectively blocks all arities for a predicate a/N' and refers to it as implementation dependend (conforming to A2 3). The current text would in consequence imply that two nonterminals of same name but different arities cannot be safely compiled separately.
a non terminal call/1 should expand to a call of call/3.
OK.
c. It was resolved (resolutions A 1) that the DCGs document shall be an independent stand alone document.
OK.
A2 1. No type checking in phrase. phrase(+callable_term, ?term, ?term).
This conflicts a bit with the agreement to make errors optional.
A2 2. phrase is the only safe way to use grammar rules.
This point has not been addressed.
A2 3. Expansion conflict implementation dependent.
Soso.
A2 4. Account will be taken of call//1 which expands to call/3
OK
A2 5. Change pred_property and current_pred to accept non terminal indicators. and other directives as required.
This resolution is very ambiguous as it is very difficult to extend the existing built-ins to nonterminal indicators.
Validated HTML