git @ Cat's Eye Technologies Ypsilax / rel_1_1_2011_0428
Import of Ypsilax version 1.1 revision 2011.0428 sources. Cat's Eye Technologies 12 years ago
6 changed file(s) with 582 addition(s) and 27 deletion(s). Raw diff Collapse all Expand all
+24
-0
Makefile less more
0 # Makefile for Ypsilax (yoob version).
1 # $Id$
2
3 JAVAC?=javac
4 JAVA?=java
5 PATHSEP?=:
6
7 JFLAGS?=-Xlint:deprecation -Xlint:unchecked
8 CDIR=bin/tc/catseye/ypsilax
9 CLASSES=$(CDIR)/YpsilaxState.class
10
11 YOOBDIR?=../../../lab/yoob
12 CLASSPATH?=bin$(PATHSEP)$(YOOBDIR)/bin
13
14 all: $(CLASSES)
15
16 $(CDIR)/YpsilaxState.class: src/YpsilaxState.java
17 $(JAVAC) $(JFLAGS) -cp "$(CLASSPATH)" -d bin src/YpsilaxState.java
18
19 clean:
20 rm -rf $(CDIR)/*.class
21
22 test: $(CLASSES)
23 $(JAVA) -cp "$(CLASSPATH)" tc.catseye.yoob.GUI -c "tc.catseye.ypsilax.YpsilaxState/Ypsilax" -s Ypsilax
+1
-0
bin/README.txt less more
0 This is where compiled Java classfiles will go.
+14
-24
doc/ypsilax.html less more
77
88 <h1>Ypsilax</h1>
99
10 <p>Language version 1.0, distribution revision 2010.0429.<br/>
11 Copyright &copy;2001-2010, Cat's Eye Technologies. All rights reserved.</p>
10 <p>Language version 1.1, distribution revision 2011.0428.<br/>
11 Copyright &copy;2001-2011, Cat's Eye Technologies. All rights reserved.</p>
1212
13 <hr/>
14
15 <blockquote><p><i>"In other words then, if a machine is expected to be infallible, it
16 cannot also be intelligent. There are several mathematical theorems which say almost
17 exactly that. But these theorems say nothing about how much intelligence may be
18 displayed if a machine makes no pretense at infallibility."</i></p>
19 <p style="text-align: right">&mdash; Grush and Churchland, <i>Gaps in Penrose's Toilings</i></p></blockquote>
20 <blockquote><p><i>"You know, I'm starting to think the humour of that misquote at the top
21 of the Ypsilax documentation is a bit</i> too <i>subtle."</i></p>
22 <p style="text-align: right">&mdash; Chris Pressey, <i>Ypsilax</i> documentation</p></blockquote>
23
24 <h3>Ypsilax</h3>
13 <h3>Overview</h3>
2514
2615 <p><b>Ypsilax</b> is a minimal, non-deterministic, reflective, two-dimensional
27 grid-rewriting language.</p>
28
29 <h3>Notes</h3>
30
31 <p>Ypsilax is a descendent of Zirgulax, which was an earlier but
16 grid-rewriting language. Ypsilax is a descendent of Zirgulax, which was an earlier but
3217 similar idea which used a hexnet instead of a grid.</p>
3318
3419 <p>An Ypsilax source file is One Big Playfield. This playfield is not
8873 immediately below them.</p>
8974
9075 <p>Finally, Ypsilax just wouldn't be a proper constraint-based language
91 without some form of pattern-matching. The wildcard character in
92 Ypsilax is the question mark. When a question mark appears in the left-hand
93 side of a rule (the pattern,) it will match any character during a rewrite, not
94 just another question mark. On the right-hand side of the rule (the substitution,)
95 it acts just as any other literal character.</p>
76 without some form of pattern-matching. (<em>In 1.1: Updated to agree with
77 existing implementation and examples</em>)
78 The wildcard character in any given rule is whatever character appears just
79 to the left of the <code>)</code> that delimits that rule on the right,
80 as long as that character is not blank space.
81 Whereever this character appears in the left-hand side of the rule (the pattern,)
82 it will match any character during a rewrite, not just another of its own kind.
83 Whereever this character appears in the right-hand side of the rule (the substitution,)
84 it will not replace the corresponding character in the playfield when a substitution
85 is made. That character in the playfield will remain unchanged.</p>
9686
9787 </body></html>
+6
-0
make-cygwin.sh less more
0 #!/bin/sh -x
1 make \
2 JAVAC='"/cygdrive/c/Program Files/Java/jdk1.6.0_22/bin/javac"' \
3 JAVA='"/cygdrive/c/Program Files/Java/jre6/bin/java"' \
4 PATHSEP=';' \
5 $*
+3
-3
script/ypsilax.pl less more
00 #!/usr/bin/perl
11
22 # ypsilax.pl - non-deterministic reflective grid-rewriting language
3 # v1.0-2010.0429 Chris Pressey, Cat's Eye Technologies
4
5 # Copyright (c)2001-2010, Cat's Eye Technologies.
3 # v1.1-2011.0428 Chris Pressey, Cat's Eye Technologies
4
5 # Copyright (c)2001-2011, Cat's Eye Technologies.
66 # All rights reserved.
77 #
88 # Redistribution and use in source and binary forms, with or without
+534
-0
src/YpsilaxState.java less more
0 /*
1 * tc.catseye.worb.YpsilaxState -- Ypsilax for yoob
2 */
3
4 /*
5 * Copyright (c)2011 Cat's Eye Technologies. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * Neither the name of Cat's Eye Technologies nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
28 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
32 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
33 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
34 * OF THE POSSIBILITY OF SUCH DAMAGE.
35 */
36
37 /*
38 * A tc.catseye.worb.YpsilaxState tries to implement the semantics of the
39 * Ypsilax grid-rewriter, for running under the yoob framework.
40 *
41 * This class targets version 0.2 of the yoob framework's interface,
42 * which isn't released yet, so knowing this doesn't help you much.
43 */
44
45 package tc.catseye.ypsilax;
46
47 import tc.catseye.yoob.Error;
48 import tc.catseye.yoob.*;
49
50 import java.util.List;
51 import java.util.ArrayList;
52 import java.util.Set;
53 import java.util.HashSet;
54 import java.util.Map;
55 import java.util.HashMap;
56 import java.util.Random;
57 import java.util.Iterator;
58
59
60 class Ypsilax implements Language {
61 public String getName() {
62 return "Ypsilax";
63 }
64
65 public int numPlayfields() {
66 return 1;
67 }
68
69 public int numTapes() {
70 return 0;
71 }
72
73 public boolean hasProgramText() {
74 return false;
75 }
76
77 public boolean hasInput() {
78 return false;
79 }
80
81 public boolean hasOutput() {
82 return false;
83 }
84
85 public List<String> exampleProgramNames() {
86 ArrayList<String> names = new ArrayList<String>();
87 names.add("transform it");
88 names.add("classic example");
89 names.add("abracadabra");
90 names.add("escaped");
91 names.add("multisymbol pattern");
92 names.add("grow tape");
93 names.add("wildcard");
94 //names.add("higher-order");
95 names.add("self-modifying");
96 return names;
97 }
98
99 public YpsilaxState loadExampleProgram(int index) {
100 String[][] program = {
101 {
102 "DDDD",
103 "",
104 "( )",
105 " D* ",
106 "",
107 "DDDD",
108 },
109 {
110 "( ) ( )",
111 " # #",
112 " # ### ### #",
113 " # #",
114 "",
115 " ### ###",
116 "",
117 " # #",
118 " # #",
119 " # ###",
120 },
121 {
122 "( ) ( )",
123 " AB BA",
124 "ABRACADABRA",
125 },
126 {
127 "* ",
128 "( ) ( )",
129 " AB BA",
130 "ABRACADABRA",
131 },
132 {
133 "( )",
134 " ABBA",
135 " ^^ ",
136 "ABRACADABRA",
137 "^^^^^^^^^^^",
138 },
139 {
140 "( )",
141 " > -> ",
142 " > -> ",
143 " > -> ",
144 "",
145 "---->",
146 "---->",
147 "---->",
148 },
149 {
150 "( ?)",
151 " A?AX",
152 "",
153 "ABRACADABRA",
154 "",
155 "...........",
156 },/*
157 {
158 "( ?) ",
159 "",
160 "",
161 " ? ?",
162 " ----( )",
163 "",
164 "",
165 "",
166 " -------------",
167 " ABRACADABRA",
168 "",
169 "",
170 " ABRACADABRA",
171 },*/
172 {
173 "(X X ) (X X )",
174 " ( )( ) ( )( )",
175 " AB BA BA AB",
176 "",
177 "",
178 " ( )",
179 " AB",
180 "",
181 "",
182 " ABRACADABRA",
183 },
184 };
185 YpsilaxState s = new YpsilaxState();
186 s.playfield.load(program[index]);
187 return s;
188 }
189
190 public YpsilaxState importFromText(String text) {
191 YpsilaxState s = new YpsilaxState();
192 s.playfield.load(text.split("\\r?\\n"));
193 return s;
194 }
195
196 public List<String> getAvailableOptionNames() {
197 ArrayList<String> names = new ArrayList<String>();
198 return names;
199 }
200
201 private static final String[][] properties = {
202 {"Author", "Chris Pressey"},
203 {"Implementer", "Chris Pressey"},
204 {"Implementation notes",
205 "In this version, patterns detected in the playfield are always within the " +
206 "current bounds of the playfield; in other words, even if the pattern contains " +
207 "spaces or wildcards, it will not match the assumed-empty space surrounding " +
208 "the defined part of the playfield."},
209 };
210
211 public String[][] getProperties() {
212 return properties;
213 }
214
215 }
216
217 class Rule extends OverlayPlayfield<CharacterElement> {
218 private IntegerElement width, height;
219 private CharacterElement wildcard;
220 private static final IntegerElement TWO = new IntegerElement(2);
221
222 public Rule(Playfield<CharacterElement> p, IntegerElement x, IntegerElement y,
223 IntegerElement width, CharacterElement wildcard) {
224 super(p, x, y, width, width.divide(TWO));
225 this.width = width;
226 this.height = width.divide(TWO);
227 this.wildcard = wildcard;
228 }
229
230 public Rule(Playfield<CharacterElement> p, IntegerElement x, IntegerElement y,
231 IntegerElement width, IntegerElement height, CharacterElement wildcard) {
232 super(p, x, y, width, height);
233 this.width = width;
234 this.height = height;
235 this.wildcard = wildcard;
236 }
237
238 public Rule createMatchSubject() {
239 return new Rule(getPlayfield(), getOffsetX(), getOffsetY(),
240 getHeight(), getHeight(), getWildcard());
241 }
242
243 public IntegerElement getWidth() {
244 return width;
245 }
246
247 public IntegerElement getHeight() {
248 return height;
249 }
250
251 public CharacterElement getWildcard() {
252 return wildcard;
253 }
254
255 // This should be a method on a Dumper object which takes a Codec.
256 public String dump() {
257 IntegerElement min_x = getMinX();
258 IntegerElement min_y = getMinY();
259 IntegerElement max_x = getMaxX();
260 IntegerElement max_y = getMaxY();
261 IntegerElement x = min_x;
262 IntegerElement y = min_y;
263 StringBuffer buf = new StringBuffer();
264
265 //System.out.println("(" + getOffsetX() + "," + getOffsetY() + ")_(" + width + "x" + height + ")");
266 while (y.compareTo(max_y) <= 0) {
267 x = min_x;
268 while (x.compareTo(max_x) <= 0) {
269 CharacterElement e = get(x, y);
270 buf.append(dumpElement(e));
271 x = x.succ();
272 }
273 y = y.succ();
274 buf.append("\n");
275 }
276
277 return buf.toString();
278 }
279
280 public String dumpElement(CharacterElement e) {
281 return e.getName();
282 }
283 }
284
285 class WildcardMatcher implements Matcher<CharacterElement,CharacterElement> {
286 private CharacterElement wildcard;
287
288 public WildcardMatcher(CharacterElement wildcard) {
289 this.wildcard = wildcard;
290 }
291
292 public boolean match(CharacterElement sought, CharacterElement candidate) {
293 if (wildcard != null && sought.getChar() == wildcard.getChar()) {
294 return true;
295 }
296 return candidate.equals(sought);
297 }
298 }
299
300 class PlayfieldMatcher<E extends Element> {
301 public boolean isMatchAt(Playfield<E> haystack, Playfield<E> needle, Matcher<E,E> m, IntegerElement x, IntegerElement y) {
302 IntegerElement width = needle.getMaxX().subtract(needle.getMinX()).succ();
303 IntegerElement height = needle.getMaxY().subtract(needle.getMinY()).succ();
304
305 if (x.pred().add(width).compareTo(haystack.getMaxX()) > 0 ||
306 y.pred().add(height).compareTo(haystack.getMaxY()) > 0) {
307 // exceeds the right or bottom edge, so, no
308 return false;
309 }
310 IntegerElement cx, cy, dx, dy;
311 for (cx = x, dx = needle.getMinX();
312 dx.compareTo(needle.getMaxX()) <= 0;
313 cx = cx.succ(), dx = dx.succ()) {
314 for (cy = y, dy = needle.getMinY();
315 dy.compareTo(needle.getMinY()) <= 0;
316 cy = cy.succ(), dy = dy.succ()) {
317 E soughtElem = needle.get(dx, dy);
318 E foundElem = haystack.get(cx, cy);
319 //System.out.printf("sought (%s,%s): '%s', found (%s,%s): '%s'\n",
320 // dx, dy, soughtElem.getName(),
321 // cx, cy, foundElem.getName());
322 if (m.match(soughtElem, foundElem)) {
323 // add something to the result-list
324 } else {
325 return false;
326 }
327 }
328 }
329 return true;
330 }
331
332 public Set<Position> getAllMatches(Playfield<E> haystack, Playfield<E> needle, Matcher<E,E> matcher) {
333 Set<Position> results = new HashSet<Position>();
334
335 IntegerElement haystackWidth = haystack.getMaxX().subtract(haystack.getMinX()).succ();
336 IntegerElement haystackHeight = haystack.getMaxY().subtract(haystack.getMinY()).succ();
337 IntegerElement needleWidth = needle.getMaxX().subtract(needle.getMinX()).succ();
338 IntegerElement needleHeight = needle.getMaxY().subtract(needle.getMinY()).succ();
339
340 if (needleWidth.compareTo(haystackWidth) > 0 || needleHeight.compareTo(haystackHeight) > 0) {
341 // thing being sought is larger than the thing seeking in, so, no
342 return results;
343 }
344
345 IntegerElement xSpan = haystackWidth.subtract(needleWidth).succ();
346 IntegerElement ySpan = haystackHeight.subtract(needleHeight).succ();
347
348 IntegerElement x, y;
349 for (x = IntegerElement.ZERO; x.compareTo(xSpan) < 0; x = x.succ()) {
350 for (y = IntegerElement.ZERO; y.compareTo(ySpan) < 0; y = y.succ()) {
351 if (isMatchAt(haystack, needle, matcher, x, y)) {
352 results.add(new Position(x, y));
353 } else {
354 }
355 }
356 }
357 return results;
358 }
359 }
360
361 class YpsilaxPlayfield extends BasicPlayfield<CharacterElement> {
362 public YpsilaxPlayfield() {
363 super(new CharacterElement(' '));
364 }
365
366 public YpsilaxPlayfield clone() {
367 YpsilaxPlayfield c = new YpsilaxPlayfield();
368 c.copyBackingStoreFrom(this);
369 return c;
370 }
371
372 public List<Position> match(YpsilaxPlayfield pattern) {
373 return null;
374 }
375
376 public List<Rule> findAllRules() {
377 IntegerElement x, y;
378 ArrayList<Rule> rules = new ArrayList<Rule>();
379
380 for (x = (IntegerElement)getMinX(); x.compareTo(getMaxX()) <= 0; x = x.succ()) {
381 for (y = (IntegerElement)getMinY(); y.compareTo(getMaxY()) <= 0; y = y.succ()) {
382 boolean escaped = (!y.isZero() && get(x, y.pred()).getChar() != ' ');
383 if (escaped) continue;
384 if (get(x, y).getChar() == '(') {
385 //System.out.println("Found a rule start at " + x + ", " + y);
386 IntegerElement x2 = x;
387 CharacterElement g = get(x2, y);
388 while (g.getChar() != ')' && x2.compareTo(getMaxX()) <= 0) {
389 x2 = x2.succ();
390 g = get(x2, y);
391 }
392 if (g.getChar() != ')') continue;
393 //System.out.println("Found a rule from " + x + "," + y + " to " + x2);
394 CharacterElement w = get(x2.pred(), y);
395 if (w.getChar() == ' ') w = null;
396 Rule r = new Rule(this, x.succ(), y.succ(), (x2.subtract(x)).pred(), w);
397 rules.add(r);
398 }
399 }
400 }
401
402 return rules;
403 }
404
405 public List<Position> findAllRuleMatches(Rule r) {
406 //System.out.printf("%s", r.dump());
407 WildcardMatcher matcher = new WildcardMatcher(r.getWildcard());
408 PlayfieldMatcher<CharacterElement> pm = new PlayfieldMatcher<CharacterElement>();
409 List<Position> positions = new ArrayList<Position>();
410 // We only want to match the LEFT side of the rule, so we do this:
411 Rule matchSubject = r.createMatchSubject();
412 for (Position p : pm.getAllMatches(this, matchSubject, matcher)) {
413 // System.out.println("CONSIDERING (" + p.getX() + "," + p.getY() + ")");
414 // Discard all the ones that are at or above the rule
415 if (p.getY().compareTo(r.getOffsetY().add(r.getHeight())) >= 0) {
416 //System.out.println("(" + p.getX() + "," + p.getY() + ")..." + r.getOffsetY());
417 positions.add(p);
418 }
419 }
420 //System.out.println("---");
421 return positions;
422 }
423
424 /*
425 * We assume a match was made at the given position.
426 */
427 public void applyRule(Rule r, Position p) {
428 IntegerElement i, j;
429
430 CharacterElement wildcard = r.getWildcard();
431 //System.out.printf("applying at %s: %s", p.toString(), r.dump());
432 /* Note that r.getHeight() == width/2 ... */
433 for(i = IntegerElement.ZERO; i.compareTo(r.getHeight()) < 0; i = i.succ()) {
434 for(j = IntegerElement.ZERO; j.compareTo(r.getHeight()) < 0; j = j.succ()) {
435 CharacterElement replacement = r.get(i.add(r.getHeight()), j);
436 IntegerElement destX = p.getX().add(i);
437 IntegerElement destY = p.getY().add(j);
438 //System.out.printf("(%s,%s): [%s] '%s' -> (%s,%s)\n", i, j, wildcard, replacement.getChar(), destX, destY);
439 if (wildcard == null || wildcard.getChar() != replacement.getChar()) {
440 set(destX, destY, replacement);
441 }
442 }
443 }
444 }
445 }
446
447 public class YpsilaxState implements tc.catseye.yoob.State {
448 protected YpsilaxPlayfield playfield;
449 protected BasicPlayfieldView view;
450 private Random rand;
451 private static final Ypsilax language = new Ypsilax();
452 private boolean halted = false;
453
454 public YpsilaxState() {
455 playfield = new YpsilaxPlayfield();
456 view = new BasicPlayfieldView();
457 rand = new Random();
458 }
459
460 public YpsilaxState clone() {
461 YpsilaxState c = new YpsilaxState();
462 c.playfield = this.playfield.clone();
463 return c;
464 }
465
466 public Language getLanguage() {
467 return language;
468 }
469
470 public List<Error> step(World world) {
471 ArrayList<Error> errors = new ArrayList<Error>();
472 List<Rule> rules = playfield.findAllRules();
473 if (rules.size() == 0) {
474 // no sense continuing. halt.
475 halted = true;
476 return errors;
477 }
478 //System.out.println("rules: " + rules.size());
479 Rule r = rules.get(rand.nextInt(rules.size()));
480 List<Position> positions = playfield.findAllRuleMatches(r);
481 //System.out.println("matches: " + positions.size());
482 if (positions.size() > 0) {
483 Position p = positions.get(rand.nextInt(positions.size()));
484 playfield.applyRule(r, p);
485 }
486 return errors;
487 }
488
489 public Playfield getPlayfield(int index) {
490 return playfield;
491 }
492
493 public Tape getTape(int index) {
494 return null;
495 }
496
497 public String getProgramText() {
498 return "";
499 }
500
501 public int getProgramPosition() {
502 return 0;
503 }
504
505 public List<Error> setProgramText(String text) {
506 ArrayList<Error> errors = new ArrayList<Error>();
507 return errors;
508 }
509
510 public View getPlayfieldView(int index) {
511 return view;
512 }
513
514 public View getTapeView(int index) {
515 return null;
516 }
517
518 public void setOption(String name, boolean value) {
519 }
520
521 public String exportToText() {
522 return playfield.dump();
523 }
524
525 public boolean needsInput() {
526 return false;
527 }
528
529 public boolean hasHalted() {
530 return halted;
531 }
532 }
533