1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2018, VU University Amsterdam 7 CWI, Amsterdam 8 All rights reserved. 9 10 Redistribution and use in source and binary forms, with or without 11 modification, are permitted provided that the following conditions 12 are met: 13 14 1. Redistributions of source code must retain the above copyright 15 notice, this list of conditions and the following disclaimer. 16 17 2. Redistributions in binary form must reproduce the above copyright 18 notice, this list of conditions and the following disclaimer in 19 the documentation and/or other materials provided with the 20 distribution. 21 22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 25 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 26 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 27 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 28 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 29 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 30 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 32 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 POSSIBILITY OF SUCH DAMAGE. 34*/ 35 36:- module(dcg_high_order, 37 [ sequence//2, % :Element, ?List 38 sequence//3, % :Element, :Sep, ?List 39 sequence//5, % :Start, :Element, :Sep, :End, ?List 40 optional//2, % :Match, :Otherwise 41 foreach//2, % :Generator, :Element 42 foreach//3 % :Generator, :Element, :Sep 43 ]). 44:- use_module(library(ordsets)). 45 46:- meta_predicate 47 sequence(,,,), 48 sequence(,,,,), 49 sequence(,,,,,,), 50 optional(, , , ), 51 foreach(,,,), 52 foreach(,,,,). 53 54/** <module> High order grammar operations 55 56This library provides facilities comparable maplist/3, ignore/1 and 57foreach/2 for DCGs. 58 59__STATUS__: This library is experimental. The interface and 60implementation may change based on feedback. Please send feedback to the 61mailinglist or the issue page of the `swipl-devel.git` repository. 62*/ 63 64%! sequence(:Element, ?List)// is nondet. 65% 66% Match or generate a sequence of Element. This predicate is 67% deterministic if List is fully instantiated and Element is 68% deterministic. When parsing, this predicate is _gready_ and does not 69% prune choice points. For example: 70% 71% ?- phrase(sequence(digit, Digits), `123a`, L). 72% Digits = "123", 73% L = [97] ; 74% Digits = [49, 50], 75% L = [51, 97] ; 76% ... 77 78sequence(OnElem, List) --> 79 sequence_(List, OnElem). 80 81sequence_([H|T], P) --> 82 call(P, H), 83 sequence_(T, P). 84sequence_([], _) --> 85 []. 86 87%! sequence(:Element, :Sep, ?List)// is nondet. 88% 89% Match or generate a sequence of Element where each pair of elements 90% is separated by Sep. When _parsing_, a matched Sep _commits_. The 91% final element is _not_ committed. More formally, it matches the 92% following sequence: 93% 94% (Element, (Sep,Element)*)? 95% 96% See also sequence//5. 97 98sequence(OnElem, OnSep, List) --> 99 sequence_(List, OnElem, OnSep). 100 101%! sequence(:Start, :Element, :Sep, :End, ?List)// is semidet. 102% 103% Match or generate a sequence of Element enclosed by Start end End, 104% where each pair of elements is separated by Sep. More formally, it 105% matches the following sequence: 106% 107% Start, (Element, (Sep,Element)*)?, End 108% 109% The example below matches a Prolog list of integers: 110% 111% ?- phrase(sequence(("[",blanks), 112% number, (",",blanks), 113% (blanks,"]"), L), 114% `[1, 2, 3 ] a`, Tail). 115% L = [1, 2, 3], 116% Tail = [32, 97]. 117 118sequence(Start, OnElem, OnSep, End, List) --> 119 , 120 sequence_(List, OnElem, OnSep), 121 , !. 122 123sequence_(List, OnElem, OnSep) --> 124 {var(List)}, 125 !, 126 ( call(OnElem, H) 127 *-> ( 128 -> !, 129 {List = [H|T]}, 130 sequence_as(T, OnElem, OnSep) 131 ; {List=[H]} 132 ) 133 ; {List=[]} 134 ). 135sequence_([H|T], OnElem, OnSep) --> 136 call(OnElem, H), 137 ( {T==[]} 138 -> [] 139 ; , 140 sequence_(T, OnElem, OnSep) 141 ). 142sequence_([], _, _) --> 143 []. 144 145%! sequence_as(?List, :OnElem, :OnSep)// 146% 147% Matches: Elem, (Sep,Elem)* 148 149sequence_as([H|T], OnElem, OnSep) --> 150 call(OnElem, H), 151 ( 152 -> !, 153 sequence_as(T, OnElem, OnSep) 154 ; {T=[]} 155 ). 156 157%! optional(:Match, :Default)// is det. 158% 159% Perform an optional match, executing Default if Match is not 160% matched. This is comparable to ignore/1. Both Match and Default are 161% DCG body terms. Default is typically used to instantiate the output 162% variables of Match, but may also be used to match a default 163% representation. Using `[]` for Default succeeds without any 164% additional actions if Match fails. For example: 165% 166% ?- phrase(optional(number(X), {X=0}), `23`, Tail). 167% X = 23, 168% Tail = []. 169% ?- phrase(optional(number(X), {X=0}), `aap`, Tail). 170% X = 0, 171% Tail = `aap`. 172 173optional(Match, _Default) --> 174 , !. 175optional(_, Default) --> 176 , !. 177 178%! foreach(:Generator, :Element)// is det. 179%! foreach(:Generator, :Element, :Sep)// is det. 180% 181% Generate a list from the solutions of Generator. This predicate 182% collects all solutions of Generator, applies Element for each 183% solution and Sep _between_ each pair of solutions. For example: 184% 185% ?- phrase(foreach(between(1,5,X), number(X), ", "), L). 186% L = "1, 2, 3, 4, 5". 187 188foreach(Generator, Rule) --> 189 foreach(Generator, Rule, []). 190 191foreach(Generator, Rule, Sep) --> 192 { term_variables(Generator, GenVars0), sort(GenVars0, GenVars), 193 term_variables((Rule,Sep), GoalVars0), sort(GoalVars0, GoalVars), 194 ord_subtract(GoalVars, GenVars, SharedGoalVars), 195 ord_intersection(GenVars, GoalVars, SharedVars), 196 Templ =.. [v|SharedVars], 197 SharedTempl =.. [v|SharedGoalVars], 198 findall(Templ, Generator, List) 199 }, 200 emit_list(List, Templ, SharedTempl, Rule, Sep). 201 202emit_list([], _, _, _, _) --> 203 []. 204emit_list([H|T], Templ, SharedTempl, OnElem, OnSep) --> 205 { copy_term(t(Templ,SharedTempl,OnElem,OnSep), 206 t(H,SharedTempl,OnElemCopy,OnSepCopy)) 207 }, 208 call_dcg(OnElemCopy), 209 ( { T == [] } 210 -> [] 211 ; call_dcg(OnSepCopy), 212 emit_list(T, Templ, SharedTempl, OnElem, OnSep) 213 ). 214 215 216 /******************************* 217 * SANDBOX * 218 *******************************/ 219 220:- multifile sandbox:safe_meta_predicate/1. 221 222sandbox:safe_meta_predicate(dcg_high_order:sequence/4). 223sandbox:safe_meta_predicate(dcg_high_order:sequence/5). 224sandbox:safe_meta_predicate(dcg_high_order:sequence/7). 225sandbox:safe_meta_predicate(dcg_high_order:optional/4). 226sandbox:safe_meta_predicate(dcg_high_order:foreach/4). 227sandbox:safe_meta_predicate(dcg_high_order:foreach/5)