/* Version: 0.2 I propose to de-facto-standardize Definite Clause Grammars in Prolog based on the reference implementation below. I will refer to this as the "Prolog Commons DCG" (C-DCG). A system can be said to conform to C-DCG if 1. it specifies how to enable C-DCG for the system, if not enabled by default. For example, it may be provided by loading a library. 2. during "preparation for execution" it transforms every grammar rule (a clause_term with functor -->/2) with head functor F/N into a corresponding clause for predicate F/(N+2), or it raises an error (preferrably the same as the reference implementation). 3. after successful "preparation for execution", the observable behaviour of phrase/2,3 is the same as the behaviour of this reference implementation, for all inputs. NOTE: "observable behaviour" includes number and order of solutions, free variable bindings, and side effects with their order; it does not include resource usage or inspection via tracing. To clarify: details of the transformation can differ as long as the observable behaviour of the resulting code is the same. This reference implementation can be employed in a system by using an appropriate hook mechanism to invoke dcg_rule/2 on every grammar rule, and replacing the grammar rule with the generated clause. -- Relationship to and differences from WG17 work on DCGs: C-DCG is defined by the reference implementation as much as possible. C-DCG keeps the interface with the Prolog system minimal, so it can in principle be provided through a library (given an expressive enough module system). C-DCG restricts the interface with the Prolog system to a clause- expansion mechanism or some way of preprocessing a Prolog text. C-DCG does not try to hide the fact that grammar rules are translated into predicates with an additional accumulator pair argument. It does not require unrelated parts of the system to understand dedicated notation such as F//N. Otherwise, as far as applicable, the semantics of this C-DCG reference implementation coincide with those of WG17 draft 2015-11-10, except - the translation of (a->b|c) does not generate an if-then-else - \+/1 is not included, and isolated ->/2 is included - there is no type checking on the list arguments of phrase/2,3 - {} is interpreted as equivalent to {true} rather than a nonterminal - []/0 and ./2 are not allowed as nonterminals This implementation also creates less redundant unifications than the WG17 reference code, and implements the error checks. It can thus be considered, and used as, a practical implementation. -- Changes relative to 0.1: - removed the \+ construct. ROK makes a convincing case against it. - disallowed [] and ./2 as nonterminal in heads, because they cannot occur (as nonterminals) in bodies either. - for the type errors, used 'list', 'callable' and 'nonterminal' - relaxed the requirement to raise the exact same error as the reference implementation - more straightforward translation of _->_;_ - handling of :/2 */ %:- module(c_dcg, [dcg_rule/2,phrase/2,phrase/3], iso_strict). phrase(GrBody, _, _) :- var(GrBody), !, throw(error(instantiation_error, _)). phrase(GrBody, S0, S) :- dcg_body(GrBody, Goal, S0, S), call(Goal). phrase(GrBody, S0) :- phrase(GrBody, S0, []). dcg_rule((GrHeadTs --> GrBody), Clause) :- ensure_nonterminal(GrHeadTs), ( GrHeadTs = (GrHead,Ts) -> ensure_nonterminal(GrHead), Clause = (Head :- Body, S=TsS1), append_args(GrHead, [S0,S], Head), terminals_append(Ts, S1, TsS1), dcg_goal(GrBody, Body, S0, S1, _) ; Clause = (Head :- Body), append_args(GrHeadTs, [S0,S], Head), dcg_body(GrBody, Body, S0, S) ). %:- mode dcg_body(?,-,?,?). dcg_body(GrBody, Goal, S0, S) :- dcg_goal(GrBody, Goal0, S0, S1, Safety), terminate_body(Safety, Goal0, Goal, S1, S). % 'unsafe' means the tail unification must not be propagated to the left %:- mode terminate_body(+,+,-,?,?). terminate_body(safe, Goal, Goal, S, S). terminate_body(unsafe, Goal, (Goal,S0=S), S0, S). %:- mode dcg_goal(?,-,?,-,-). dcg_goal(Var, phrase(Var,S0,S), S0, S, safe) :- var(Var), !. dcg_goal(!, !, S, S, unsafe) :- !. dcg_goal({}, true, S, S, safe) :- !. dcg_goal({Goal}, Goal, S, S, unsafe) :- !. dcg_goal([], (S0=S), S0, S, safe) :- !. dcg_goal([T|Ts], (S0=TsS), S0, S, safe) :- !, terminals_append([T|Ts], S, TsS). dcg_goal((L,R), Goal, S0, S, Safety) :- !, dcg_goal(L, LGoal, S0, S1, _), dcg_goal(R, RGoal, S1, S, Safety), conjoin(LGoal, RGoal, Goal). dcg_goal((L;R), (LGoal;RGoal), S0, S, safe) :- !, ( nonvar(L), L = (C->T) -> LGoal = (CGoal->TGoal), dcg_goal(C, CGoal, S0, S1, _), dcg_body(T, TGoal, S1, S) ; dcg_body(L, LGoal, S0, S) ), dcg_body(R, RGoal, S0, S). dcg_goal((L->R), (LGoal->RGoal), S0, S, Safety) :- !, dcg_goal(L, LGoal, S0, S1, _), dcg_goal(R, RGoal, S1, S, Safety). dcg_goal('|'(L,R), Goal, S0, S, safe) :- !, dcg_body(L, LGoal, S0, S), dcg_body(R, RGoal, S0, S), % prevent accidental introduction of (_->_;_) ( LGoal=(_->_) -> Goal=(LGoal,true;RGoal) ; Goal=(LGoal;RGoal) ). dcg_goal(M:NT, MGoal, S0, S, Safety) :- !, dcg_qualified(NT, M, MGoal, S0, S, Safety). dcg_goal(NT, Goal, S0, S, safe) :- callable(NT), !, append_args(NT, [S0,S], Goal). dcg_goal(Thing, _Goal, _S0, _S, _) :- throw(error(type_error(callable,Thing),_)). %:- mode terminals_append(?,?,-). terminals_append(Xs, _T, _XsT) :- var(Xs), !, throw(error(instantiation_error,_)). terminals_append([], T, T) :- !. terminals_append([X|Xs], T, [X|XsT]) :- !, terminals_append(Xs, T, XsT). terminals_append(X, _, _) :- throw(error(type_error(list,X),_)). %:- mode conjoin(+,+,-). conjoin(true, RGoal, RGoal) :- !. conjoin(LGoal, true, LGoal) :- !. conjoin(LGoal, RGoal, (LGoal,RGoal)). append_args(T0, Bs, T) :- T0 =.. FAs, append(FAs, Bs, FAsBs), T =.. FAsBs. append([], Ys, Ys). append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs). ensure_nonterminal(X) :- var(X), !, throw(error(instantiation_error,_)). ensure_nonterminal(X) :- callable(X), X\=[_|_], X\=[], X\={_}, X\={}, !. ensure_nonterminal(X) :- throw(error(type_error(nonterminal,X),_)). %:- mode dcg_qualified(?,?,-,?,-,-). dcg_qualified(Var, M, phrase(M:Var,S0,S), S0, S, safe) :- var(Var), !. dcg_qualified(NT, M, M:Goal, S0, S, Safety) :- ensure_nonterminal(NT), dcg_goal(NT, Goal, S0, S, Safety). % (MIT licence - preliminary) % % Copyright (c) 2016 Joachim Schimpf, Prolog Commons % % Permission is hereby granted, free of charge, to any person obtaining % a copy of this software and associated documentation files (the % "Software"), to deal in the Software without restriction, including % without limitation the rights to use, copy, modify, merge, publish, % distribute, sublicense, and/or sell copies of the Software, and to % permit persons to whom the Software is furnished to do so, subject to % the following conditions: % % The above copyright notice and this permission notice shall be % included in all copies or substantial portions of the Software. % % THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, % EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF % MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. % IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY % CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, % TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE % SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. %