git @ Cat's Eye Technologies Samovar / master
Merge pull request #11 from catseye/develop-0.3 Develop 0.3 Chris Pressey authored 1 year, 10 months ago GitHub committed 1 year, 10 months ago
6 changed file(s) with 221 addition(s) and 28 deletion(s). Raw diff Collapse all Expand all
00 History of Samovar
11 ==================
2
3 ### Version 0.3
4
5 * The `?_` wildcard variable matches any term, without binding
6 it to anything.
7 * Multiple bindings in a `where` clause may be seperated by
8 commas.
9 * Consequences of a rule may not contain a `where` clause;
10 this is statically checked before execution.
11 * Occurrence of variables in text and consequences is also
12 statically checked.
13 * Pathologically poor performance of the lexical scanner on
14 large input files (essentially a bug) was fixed.
215
316 ### Version 0.2
417
00 Samovar
11 =======
22
3 *Version 0.2. Subject to change in backwards-incompatible ways.*
3 *Version 0.3. Subject to change in backwards-incompatible ways.*
44
55 Samovar is a DSL for modelling a world using propositions (facts), and possible
66 events that can occur based on those facts, changing them.
4949
5050 ### TODO
5151
52 * Implement a "wildcard" variable that will match anything *without* binding it.
53 * Consider what it would take to add a predicate that evaluates to whether
54 a given action has been taken previously or not.
55 * Consider macros.
56 * Consider making "wildcard" work such that you can say `¬holding(?_, club)`
57 to mean "if no one is holding the club".
58 * Statically check that the 2nd cond in a rule has no "where" clause
59 * Commas after bindings in "where"
60 * Statically check that every var in the 2nd cond was bound in the 1st cond
52 * Implement an actual solver.
53 * Maybe allow variables to be notated so that they can bind reflexively,
54 e.g. `?*A looks at ?*B` can bind both variables to Alice.
55 * Make `?_` work such that you can say `¬holding(?_, club)` to mean
56 "if no one is holding the club".
7676
7777 [actor(α),item(β),~holding(α,β)] α picks up the β. [holding(α,β)]
7878
79 Which can be read
79 Which can be read as
8080
8181 > If α is an actor and β is an item and α is not holding β, then one possible
8282 > action is to write out 'α picks up the β' and assert that α is now holding β.
8383
84 We can add a complementary rule:
84 The Greek letters represent variables, which are bound to concrete
85 terms during the pattern-matching process. (Variables can also be
86 written with Latin letters, and given names longer than one character,
87 by introducing them with a question mark, like this: `?var`.)
88
89 Now, we can add a complementary rule:
8590
8691 [actor(α),item(β),holding(α,β)] α puts down the β. [~holding(α,β)]
8792
212217 Event rules
213218 -----------
214219
215 An event may be selected if its pattern matches the current set of
216 facts.
220 We've already seen that an event may be selected if its pattern matches
221 the current set of facts. Let's take a closer look at how patterns are
222 matched.
223
224 If a variable appears more than once in a pattern, it must match
225 the same term in each occurrence.
226
227 scenario IgnatzAndMolly {
228 [actor(?A),sitting(?A)] ?A was sitting. []
229 actor(Ignatz).
230 sitting(Molly).
231
232 goal [].
233 }
234 ===>
235
236 No two variables can match with the same term. This may seem somewhat
237 unusual, if you're familiar with Prolog or other languages with
238 pattern-matching, but it prevents a "reflexive" matches (for example,
239 "Alice looks at Alice") that don't actually come up very often when
240 telling a story.
241
242 scenario IgnatzAndMolly {
243 [actor(?A),actor(?B)] ?A looks at ?B. [~actor(?A),~actor(?B)]
244 actor(Ignatz).
245 actor(Molly).
246
247 goal [].
248 }
249 ===> Ignatz looks at Molly.
250
251 scenario IgnatzWithoutMolly {
252 [actor(?A),actor(?B)] ?A looks at ?B. [~actor(?A),~actor(?B)]
253 actor(Ignatz).
254
255 goal [].
256 }
257 ===>
258
259 A variable may appear in the pattern that is not used in the text or the
260 consequences.
261
262 scenario IgnatzAndMolly {
263 [actor(?A)] Someone. []
264 actor(Ignatz).
265 actor(Molly).
266
267 goal [].
268 }
269 ===> Someone.
270 ===> Someone.
271 ===> Someone.
272 ===> Someone.
273
274 But a variable may not appear in the text if it did not appear in the
275 pattern.
276
277 scenario IgnatzAndMolly {
278 [actor(?A)] ?B sneezes. []
279 actor(Ignatz).
280 actor(Molly).
281
282 goal [].
283 }
284 ???> SamovarSyntaxError
285
286 Likewise, a variable may not appear in the consequences if it did not
287 appear in the pattern.
288
289 scenario IgnatzAndMolly {
290 [actor(?A)] Someone sneezes. [~actor(?B)]
291 actor(Ignatz).
292 actor(Molly).
293
294 goal [].
295 }
296 ???> SamovarSyntaxError
297
298 A special "wildcard" variable, `?_`, matches any term, and does not unify.
299
300 scenario UntilHoldBrick {
301 [actor(?_),item(?_)] There was an actor and an item. [~actor(Ignatz)]
302 actor(Ignatz).
303 item(brick).
304 goal [].
305 }
306 ===> There was an actor and an item.
307
308 `?_` cannot appear in the text or the consequences of a rule, even if it
309 appears in the pattern.
310
311 scenario UntilHoldBrick {
312 [actor(?_),item(?_)] There was ?_ and ?_. [~actor(Ignatz)]
313 actor(Ignatz).
314 item(brick).
315 goal [].
316 }
317 ???> SamovarSyntaxError
318
319 scenario UntilHoldBrick {
320 [actor(?_),item(?_)] There was an actor and an item. [~actor(?_)]
321 actor(Ignatz).
322 item(brick).
323 goal [].
324 }
325 ???> SamovarSyntaxError
217326
218327 The text inside the event rule is typically expanded with the values
219328 that the pattern variables matched.
272381 goal [holding(Ignatz,brick)].
273382 }
274383 ===> Ignatz picked up the brick.
384
385 A variable pre-bound in a `where` may appear in the text and consequences.
386
387 scenario IgnatzAndMolly {
388 [actor(?A) where ?B=Molly] ?B sneezes. [sneezed(?B)]
389 actor(Ignatz).
390 actor(Molly).
391
392 goal [].
393 }
394 ===> Molly sneezes.
395 ===> Molly sneezes.
396 ===> Molly sneezes.
397 ===> Molly sneezes.
398
399 There may be multiple bindings in a where clause. These may be
400 seperated by commas.
401
402 scenario UntilHoldBrick {
403 [actor(?A),item(?I),~holding(?A,?I) where ?A=Ignatz,?I=brick] ?A picked up the ?I. [holding(?A,?I)]
404 actor(Ignatz).
405 item(brick).
406 item(banana).
407 goal [holding(Ignatz,brick)].
408 }
409 ===> Ignatz picked up the brick.
410
411 You can't put a `where` clause in the consequences.
412
413 scenario UntilHoldBrick {
414 [actor(?A),item(?I),~holding(?A,?I)] ?A picked up the ?I. [holding(?A,?I) where ?A=Ignatz]
415 actor(Ignatz).
416 item(brick).
417 item(banana).
418 goal [holding(Ignatz,brick)].
419 }
420 ???> SamovarSyntaxError
275421
276422 chairs
277423 ------
1010 # Goal ::= "goal" Cond.
1111 # Proposition ::= Term.
1212 # Rule ::= Cond {Var | Atom | Punct} Cond.
13 # Cond ::= "[" Expr {"," Expr} ["where" {Var "=" Term}"]".
13 # Cond ::= "[" Expr {"," Expr} ["where" {Var "=" Term [","]}"]".
1414 # Expr ::= Term | NotSym Term.
1515 # Term ::= Var | Atom ["(" Term {AndSym Term} ")"].
1616 # Var ::= Qmark | Greek.
2020 # Punct ::= <<"',.;:?!>>.
2121 # NotSym ::= '~' | '¬'.
2222 # AndSym ::= ',' | '∧'.
23
24
25 class SamovarSyntaxError(ValueError):
26 pass
27
28
29 def variables_in_cond(cond):
30 vars_ = set()
31 for expr in cond.exprs:
32 expr.term.collect_variables(vars_)
33 for key, value in cond.bindings.items():
34 vars_.add(Var(key))
35 return vars_
2336
2437
2538 class Parser(object):
7386 while not self.scanner.on('['):
7487 words.append(self.word())
7588 post = self.cond()
89
90 if post.bindings:
91 raise SamovarSyntaxError("Consequences of a rule cannot include a `where` clause")
92
93 pre_variables = variables_in_cond(pre)
94
95 words_variables = set(w for w in words if isinstance(w, Var))
96 text = ' '.join([str(w) for w in words])
97 if '?_' in [w.name for w in words_variables]:
98 raise SamovarSyntaxError('Text "{}" contains wildcard'.format(text))
99 extra_vars_in_words = words_variables - pre_variables
100 if extra_vars_in_words:
101 extra_vars = ', '.join([str(v) for v in sorted(extra_vars_in_words)])
102 raise SamovarSyntaxError('Text "{}" contains unbound variables: {}'.format(text, extra_vars))
103
104 post_variables = variables_in_cond(post)
105 if '?_' in [w.name for w in post_variables]:
106 raise SamovarSyntaxError("Consequences contains wildcard")
107 extra_vars_in_post = post_variables - pre_variables
108 if extra_vars_in_post:
109 extra_vars = ', '.join([str(v) for v in sorted(extra_vars_in_words)])
110 raise SamovarSyntaxError("Consequences contains unbound variables: {}".format(extra_vars))
111
76112 return Rule(pre=pre, words=words, post=post)
77113
78114 def cond(self):
89125 self.scanner.expect('=')
90126 t = self.term()
91127 bindings[v.name] = t
128 self.scanner.consume(',', u'∧')
92129 self.scanner.expect(']')
93130 return Cond(exprs=exprs, bindings=bindings)
94131
4242 self.text = unicode(text)
4343 self.token = None
4444 self.type = None
45 self.pos = 0
4546 self.scan()
4647
4748 def near_text(self, length=10):
48 if len(self.text) < length:
49 return self.text
50 return self.text[:length]
49 return self.text[self.pos:self.pos+length]
5150
5251 def scan_pattern(self, pattern, type, token_group=1, rest_group=2):
53 pattern = r'^(' + pattern + r')(.*?)$'
54 match = re.match(pattern, self.text, re.DOTALL)
52 pattern = r'(' + pattern + r')'
53 regexp = re.compile(pattern, flags=re.DOTALL)
54 match = regexp.match(self.text, pos=self.pos)
5555 if not match:
5656 return False
5757 else:
5858 self.type = type
5959 self.token = match.group(token_group)
60 self.text = match.group(rest_group)
60 self.pos += len(self.token)
6161 return True
6262
6363 def scan(self):
6464 self.scan_pattern(r'[ \t\n\r]*', 'whitespace')
6565 while self.scan_pattern(r'\/\/.*?[\n\r]', 'comment'):
6666 self.scan_pattern(r'[ \t\n\r]*', 'whitespace')
67 if not self.text:
67 if self.pos >= len(self.text):
6868 self.token = None
6969 self.type = 'EOF'
7070 return
8989 if self.scan_pattern(r'.', 'unknown character'):
9090 return
9191 else:
92 raise AssertionError("this should never happen, self.text=(%s)" % self.text)
92 raise AssertionError("this should never happen, self.text=(%s), self.pos=(%s)" % (self.text, self.pos))
9393
9494 def expect(self, token):
9595 if self.token == token:
100100 return False
101101
102102 def match(self, term, env, **kwargs):
103 if self.name == '?_':
104 return env
103105 if self.name in env:
104106 bound_to = env[self.name]
105107 return bound_to.match(term, env, **kwargs)
106 else:
107 if kwargs.get('unique_binding'):
108 if term in env.values():
109 raise ValueError("Not unique")
110 return dict(list(env.items()) + [(self.name, term)])
108 if kwargs.get('unique_binding'):
109 if term in env.values():
110 raise ValueError("Not unique")
111 return dict(list(env.items()) + [(self.name, term)])
111112
112113 def subst(self, env):
113114 return env[self.name]