Commits

Cat's Eye Technologies  committed 7232598

Import of Ypsilax version 1.1 revision 2011.0428 sources.

  • Participants
  • Parent commits bf5a7e1
  • Tags rel_1_1_2011_0428

Comments (0)

Files changed (6)

+# Makefile for Ypsilax (yoob version).
+# $Id$
+
+JAVAC?=javac
+JAVA?=java
+PATHSEP?=:
+
+JFLAGS?=-Xlint:deprecation -Xlint:unchecked
+CDIR=bin/tc/catseye/ypsilax
+CLASSES=$(CDIR)/YpsilaxState.class
+
+YOOBDIR?=../../../lab/yoob
+CLASSPATH?=bin$(PATHSEP)$(YOOBDIR)/bin
+
+all: $(CLASSES)
+
+$(CDIR)/YpsilaxState.class: src/YpsilaxState.java
+	$(JAVAC) $(JFLAGS) -cp "$(CLASSPATH)" -d bin src/YpsilaxState.java
+
+clean:
+	rm -rf $(CDIR)/*.class
+
+test: $(CLASSES)
+	$(JAVA) -cp "$(CLASSPATH)" tc.catseye.yoob.GUI -c "tc.catseye.ypsilax.YpsilaxState/Ypsilax" -s Ypsilax

File bin/README.txt

+This is where compiled Java classfiles will go.

File doc/ypsilax.html

 
 <h1>Ypsilax</h1>
 
-<p>Language version 1.0, distribution revision 2010.0429.<br/>
-Copyright &copy;2001-2010, Cat's Eye Technologies.  All rights reserved.</p>
+<p>Language version 1.1, distribution revision 2011.0428.<br/>
+Copyright &copy;2001-2011, Cat's Eye Technologies.  All rights reserved.</p>
 
-<hr/>
-
-<blockquote><p><i>"In other words then, if a machine is expected to be infallible, it
-cannot also be intelligent. There are several mathematical theorems which say almost
-exactly that. But these theorems say nothing about how much intelligence may be
-displayed if a machine makes no pretense at infallibility."</i></p>
-<p style="text-align: right">&mdash; Grush and Churchland, <i>Gaps in Penrose's Toilings</i></p></blockquote>
-<blockquote><p><i>"You know, I'm starting to think the humour of that misquote at the top
-of the Ypsilax documentation is a bit</i> too <i>subtle."</i></p>
-<p style="text-align: right">&mdash; Chris Pressey, <i>Ypsilax</i> documentation</p></blockquote>
-
-<h3>Ypsilax</h3>
+<h3>Overview</h3>
 
 <p><b>Ypsilax</b> is a minimal, non-deterministic, reflective, two-dimensional
-grid-rewriting language.</p>
-
-<h3>Notes</h3>
-
-<p>Ypsilax is a descendent of Zirgulax, which was an earlier but
+grid-rewriting language.  Ypsilax is a descendent of Zirgulax, which was an earlier but
 similar idea which used a hexnet instead of a grid.</p>
 
 <p>An Ypsilax source file is One Big Playfield.  This playfield is not
 immediately below them.</p>
 
 <p>Finally, Ypsilax just wouldn't be a proper constraint-based language
-without some form of pattern-matching.  The wildcard character in
-Ypsilax is the question mark.  When a question mark appears in the left-hand
-side of a rule (the pattern,) it will match any character during a rewrite, not
-just another question mark.  On the right-hand side of the rule (the substitution,)
-it acts just as any other literal character.</p>
+without some form of pattern-matching.  (<em>In 1.1: Updated to agree with
+existing implementation and examples</em>)
+The wildcard character in any given rule is whatever character appears just
+to the left of the <code>)</code> that delimits that rule on the right,
+as long as that character is not blank space.
+Whereever this character appears in the left-hand side of the rule (the pattern,)
+it will match any character during a rewrite, not just another of its own kind.
+Whereever this character appears in the right-hand side of the rule (the substitution,)
+it will not replace the corresponding character in the playfield when a substitution
+is made.  That character in the playfield will remain unchanged.</p>
 
 </body></html>

File make-cygwin.sh

+#!/bin/sh -x
+make \
+    JAVAC='"/cygdrive/c/Program Files/Java/jdk1.6.0_22/bin/javac"' \
+    JAVA='"/cygdrive/c/Program Files/Java/jre6/bin/java"' \
+    PATHSEP=';' \
+    $*

File script/ypsilax.pl

 #!/usr/bin/perl
 
 # ypsilax.pl - non-deterministic reflective grid-rewriting language
-# v1.0-2010.0429 Chris Pressey, Cat's Eye Technologies
+# v1.1-2011.0428 Chris Pressey, Cat's Eye Technologies
 
-# Copyright (c)2001-2010, Cat's Eye Technologies.
+# Copyright (c)2001-2011, Cat's Eye Technologies.
 # All rights reserved.
 # 
 # Redistribution and use in source and binary forms, with or without

File src/YpsilaxState.java

+/*
+ * tc.catseye.worb.YpsilaxState -- Ypsilax for yoob
+ */
+
+/*
+ * Copyright (c)2011 Cat's Eye Technologies.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ *   Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ *
+ *   Neither the name of Cat's Eye Technologies nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * A tc.catseye.worb.YpsilaxState tries to implement the semantics of the
+ * Ypsilax grid-rewriter, for running under the yoob framework.
+ *
+ * This class targets version 0.2 of the yoob framework's interface,
+ * which isn't released yet, so knowing this doesn't help you much.
+ */
+
+package tc.catseye.ypsilax;
+
+import tc.catseye.yoob.Error;
+import tc.catseye.yoob.*;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Set;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.HashMap;
+import java.util.Random;
+import java.util.Iterator;
+
+
+class Ypsilax implements Language {
+    public String getName() {
+        return "Ypsilax";
+    }
+
+    public int numPlayfields() {
+        return 1;
+    }
+
+    public int numTapes() {
+        return 0;
+    }
+
+    public boolean hasProgramText() {
+        return false;
+    }
+
+    public boolean hasInput() {
+        return false;
+    }
+
+    public boolean hasOutput() {
+        return false;
+    }
+
+    public List<String> exampleProgramNames() {
+        ArrayList<String> names = new ArrayList<String>();
+        names.add("transform it");
+        names.add("classic example");
+        names.add("abracadabra");
+        names.add("escaped");
+        names.add("multisymbol pattern");
+        names.add("grow tape");
+        names.add("wildcard");
+        //names.add("higher-order");
+        names.add("self-modifying");
+        return names;
+    }
+
+    public YpsilaxState loadExampleProgram(int index) {
+        String[][] program = {
+          {
+            "DDDD",
+            "",
+            "(  )",
+            " D* ",
+            "",
+            "DDDD",
+          },
+          {
+            "(      )  (      )",
+            "  #            #",
+            "  # ###    ### #",
+            "  #            #",
+            "",
+            "    ###   ###",
+            "",
+            "    #      #",
+            "    #      #",
+            "    #    ###",
+          },
+          {
+            "(  )   (  )",
+            " AB     BA",
+            "ABRACADABRA",
+          },
+          {
+            "*          ",
+            "(  )   (  )",
+            " AB     BA",
+            "ABRACADABRA",
+          },
+          {
+            "(    )",
+            " ABBA",
+            " ^^  ",
+            "ABRACADABRA",
+            "^^^^^^^^^^^",
+          },
+          {
+            "(      )",
+            " >  -> ",
+            " >  -> ",
+            " >  -> ",
+            "",
+            "---->",
+            "---->",
+            "---->",
+          },
+          {
+            "(   ?)",
+            " A?AX",
+            "",
+            "ABRACADABRA",
+            "",
+            "...........",
+          },/*
+          {
+            "(       ?) ",
+            "",
+            "",
+            " ?   ?",
+            " ----(  )",
+            "",
+            "",
+            "",
+            "    -------------",
+            "     ABRACADABRA",
+            "",
+            "",
+            "     ABRACADABRA",
+          },*/
+          {
+            "(X   X   )  (X   X   )",
+            " (  )(  )    (  )(  )",
+            "  AB  BA      BA  AB",
+            "",
+            "",
+            "        (  )",
+            "         AB",
+            "",
+            "",
+            "     ABRACADABRA",
+          },
+        };
+        YpsilaxState s = new YpsilaxState();
+        s.playfield.load(program[index]);
+        return s;
+    }
+
+    public YpsilaxState importFromText(String text) {
+        YpsilaxState s = new YpsilaxState();
+        s.playfield.load(text.split("\\r?\\n"));
+        return s;
+    }
+
+    public List<String> getAvailableOptionNames() {
+        ArrayList<String> names = new ArrayList<String>();
+        return names;
+    }
+
+    private static final String[][] properties = {
+        {"Author", "Chris Pressey"},
+        {"Implementer", "Chris Pressey"},
+        {"Implementation notes",
+         "In this version, patterns detected in the playfield are always within the " +
+         "current bounds of the playfield; in other words, even if the pattern contains " +
+         "spaces or wildcards, it will not match the assumed-empty space surrounding " +
+         "the defined part of the playfield."},
+    };
+
+    public String[][] getProperties() {
+        return properties;
+    }
+
+}
+
+class Rule extends OverlayPlayfield<CharacterElement> {
+    private IntegerElement width, height;
+    private CharacterElement wildcard;
+    private static final IntegerElement TWO = new IntegerElement(2);
+
+    public Rule(Playfield<CharacterElement> p, IntegerElement x, IntegerElement y,
+                IntegerElement width, CharacterElement wildcard) {
+        super(p, x, y, width, width.divide(TWO));
+        this.width = width;
+        this.height = width.divide(TWO);
+        this.wildcard = wildcard;
+    }
+
+    public Rule(Playfield<CharacterElement> p, IntegerElement x, IntegerElement y,
+                IntegerElement width, IntegerElement height, CharacterElement wildcard) {
+        super(p, x, y, width, height);
+        this.width = width;
+        this.height = height;
+        this.wildcard = wildcard;
+    }
+
+    public Rule createMatchSubject() {
+        return new Rule(getPlayfield(), getOffsetX(), getOffsetY(),
+                        getHeight(), getHeight(), getWildcard());
+    }
+
+    public IntegerElement getWidth() {
+        return width;
+    }
+
+    public IntegerElement getHeight() {
+        return height;
+    }
+
+    public CharacterElement getWildcard() {
+        return wildcard;
+    }
+
+    // This should be a method on a Dumper object which takes a Codec.
+    public String dump() {
+        IntegerElement min_x = getMinX();
+        IntegerElement min_y = getMinY();
+        IntegerElement max_x = getMaxX();
+        IntegerElement max_y = getMaxY();
+        IntegerElement x = min_x;
+        IntegerElement y = min_y;
+        StringBuffer buf = new StringBuffer();
+
+        //System.out.println("(" + getOffsetX() + "," + getOffsetY() + ")_(" + width + "x" + height + ")");
+        while (y.compareTo(max_y) <= 0) {
+            x = min_x;
+            while (x.compareTo(max_x) <= 0) {
+                CharacterElement e = get(x, y);
+                buf.append(dumpElement(e));
+                x = x.succ();
+            }
+            y = y.succ();
+            buf.append("\n");
+        }
+
+        return buf.toString();
+    }
+
+    public String dumpElement(CharacterElement e) {
+        return e.getName();
+    }
+}
+
+class WildcardMatcher implements Matcher<CharacterElement,CharacterElement> {
+    private CharacterElement wildcard;
+
+    public WildcardMatcher(CharacterElement wildcard) {
+        this.wildcard = wildcard;
+    }
+
+    public boolean match(CharacterElement sought, CharacterElement candidate) {
+        if (wildcard != null && sought.getChar() == wildcard.getChar()) {
+            return true;
+        }
+        return candidate.equals(sought);
+    }
+}
+
+class PlayfieldMatcher<E extends Element> {
+    public boolean isMatchAt(Playfield<E> haystack, Playfield<E> needle, Matcher<E,E> m, IntegerElement x, IntegerElement y) {
+        IntegerElement width = needle.getMaxX().subtract(needle.getMinX()).succ();
+        IntegerElement height = needle.getMaxY().subtract(needle.getMinY()).succ();
+      
+        if (x.pred().add(width).compareTo(haystack.getMaxX()) > 0 ||
+            y.pred().add(height).compareTo(haystack.getMaxY()) > 0) {
+            // exceeds the right or bottom edge, so, no
+            return false;
+        }
+        IntegerElement cx, cy, dx, dy;
+        for (cx = x, dx = needle.getMinX();
+             dx.compareTo(needle.getMaxX()) <= 0;
+             cx = cx.succ(), dx = dx.succ()) {
+            for (cy = y, dy = needle.getMinY();
+                 dy.compareTo(needle.getMinY()) <= 0;
+                 cy = cy.succ(), dy = dy.succ()) {
+                E soughtElem = needle.get(dx, dy);
+                E foundElem = haystack.get(cx, cy);
+                //System.out.printf("sought (%s,%s): '%s', found (%s,%s): '%s'\n",
+                //     dx, dy, soughtElem.getName(),
+                //     cx, cy, foundElem.getName());
+                if (m.match(soughtElem, foundElem)) {
+                    // add something to the result-list
+                } else {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+
+    public Set<Position> getAllMatches(Playfield<E> haystack, Playfield<E> needle, Matcher<E,E> matcher) {
+        Set<Position> results = new HashSet<Position>();
+
+        IntegerElement haystackWidth = haystack.getMaxX().subtract(haystack.getMinX()).succ();
+        IntegerElement haystackHeight = haystack.getMaxY().subtract(haystack.getMinY()).succ();
+        IntegerElement needleWidth = needle.getMaxX().subtract(needle.getMinX()).succ();
+        IntegerElement needleHeight = needle.getMaxY().subtract(needle.getMinY()).succ();
+
+        if (needleWidth.compareTo(haystackWidth) > 0 || needleHeight.compareTo(haystackHeight) > 0) {
+            // thing being sought is larger than the thing seeking in, so, no
+            return results;
+        }
+
+        IntegerElement xSpan = haystackWidth.subtract(needleWidth).succ();
+        IntegerElement ySpan = haystackHeight.subtract(needleHeight).succ();
+
+        IntegerElement x, y;
+        for (x = IntegerElement.ZERO; x.compareTo(xSpan) < 0; x = x.succ()) {
+            for (y = IntegerElement.ZERO; y.compareTo(ySpan) < 0; y = y.succ()) {
+                if (isMatchAt(haystack, needle, matcher, x, y)) {
+                    results.add(new Position(x, y));
+                } else {
+                }
+            }
+        }
+        return results;
+    }
+}
+
+class YpsilaxPlayfield extends BasicPlayfield<CharacterElement> {
+    public YpsilaxPlayfield() {
+        super(new CharacterElement(' '));
+    }
+
+    public YpsilaxPlayfield clone() {
+        YpsilaxPlayfield c = new YpsilaxPlayfield();
+        c.copyBackingStoreFrom(this);
+        return c;
+    }
+
+    public List<Position> match(YpsilaxPlayfield pattern) {
+        return null;
+    }
+
+    public List<Rule> findAllRules() {
+        IntegerElement x, y;
+        ArrayList<Rule> rules = new ArrayList<Rule>();
+
+        for (x = (IntegerElement)getMinX(); x.compareTo(getMaxX()) <= 0; x = x.succ()) {
+            for (y = (IntegerElement)getMinY(); y.compareTo(getMaxY()) <= 0; y = y.succ()) {
+                boolean escaped = (!y.isZero() && get(x, y.pred()).getChar() != ' ');
+                if (escaped) continue;
+                if (get(x, y).getChar() == '(') {
+                    //System.out.println("Found a rule start at " + x + ", " + y);
+                    IntegerElement x2 = x;
+                    CharacterElement g = get(x2, y);
+                    while (g.getChar() != ')' && x2.compareTo(getMaxX()) <= 0) {
+                        x2 = x2.succ();
+                        g = get(x2, y);
+                    }
+                    if (g.getChar() != ')') continue;
+                    //System.out.println("Found a rule from " + x + "," + y + " to " + x2);
+                    CharacterElement w = get(x2.pred(), y);
+                    if (w.getChar() == ' ') w = null;
+                    Rule r = new Rule(this, x.succ(), y.succ(), (x2.subtract(x)).pred(), w);
+                    rules.add(r);
+                }
+            }
+        }
+
+        return rules;
+    }
+
+    public List<Position> findAllRuleMatches(Rule r) {
+        //System.out.printf("%s", r.dump());
+        WildcardMatcher matcher = new WildcardMatcher(r.getWildcard());
+        PlayfieldMatcher<CharacterElement> pm = new PlayfieldMatcher<CharacterElement>();
+        List<Position> positions = new ArrayList<Position>();
+        // We only want to match the LEFT side of the rule, so we do this:
+        Rule matchSubject = r.createMatchSubject();
+        for (Position p : pm.getAllMatches(this, matchSubject, matcher)) {
+            // System.out.println("CONSIDERING (" + p.getX() + "," + p.getY() + ")");
+            // Discard all the ones that are at or above the rule
+            if (p.getY().compareTo(r.getOffsetY().add(r.getHeight())) >= 0) {
+                //System.out.println("(" + p.getX() + "," + p.getY() + ")..." + r.getOffsetY());
+                positions.add(p);
+            }
+        }
+        //System.out.println("---");
+        return positions;
+    }
+
+    /*
+     * We assume a match was made at the given position.
+     */
+    public void applyRule(Rule r, Position p) {
+        IntegerElement i, j;
+
+        CharacterElement wildcard = r.getWildcard();
+        //System.out.printf("applying at %s: %s", p.toString(), r.dump());
+        /* Note that r.getHeight() == width/2 ... */
+        for(i = IntegerElement.ZERO; i.compareTo(r.getHeight()) < 0; i = i.succ()) {
+            for(j = IntegerElement.ZERO; j.compareTo(r.getHeight()) < 0; j = j.succ()) {
+                CharacterElement replacement = r.get(i.add(r.getHeight()), j);
+                IntegerElement destX = p.getX().add(i);
+                IntegerElement destY = p.getY().add(j);
+                //System.out.printf("(%s,%s): [%s] '%s' -> (%s,%s)\n", i, j, wildcard, replacement.getChar(), destX, destY);
+                if (wildcard == null || wildcard.getChar() != replacement.getChar()) {
+                    set(destX, destY, replacement);
+                }
+            }
+        }
+    }
+}
+
+public class YpsilaxState implements tc.catseye.yoob.State {
+    protected YpsilaxPlayfield playfield;
+    protected BasicPlayfieldView view;
+    private Random rand;
+    private static final Ypsilax language = new Ypsilax();
+    private boolean halted = false;
+
+    public YpsilaxState() {
+        playfield = new YpsilaxPlayfield();
+        view = new BasicPlayfieldView();
+        rand = new Random();
+    }
+    
+    public YpsilaxState clone() {
+        YpsilaxState c = new YpsilaxState();
+        c.playfield = this.playfield.clone();
+        return c;
+    }
+
+    public Language getLanguage() {
+        return language;
+    }
+
+    public List<Error> step(World world) {
+        ArrayList<Error> errors = new ArrayList<Error>();
+        List<Rule> rules = playfield.findAllRules();
+        if (rules.size() == 0) {
+            // no sense continuing.  halt.
+            halted = true;
+            return errors;
+        }
+        //System.out.println("rules: " + rules.size());
+        Rule r = rules.get(rand.nextInt(rules.size()));
+        List<Position> positions = playfield.findAllRuleMatches(r);
+        //System.out.println("matches: " + positions.size());
+        if (positions.size() > 0) {
+            Position p = positions.get(rand.nextInt(positions.size()));
+            playfield.applyRule(r, p);
+        }
+        return errors;
+    }
+
+    public Playfield getPlayfield(int index) {
+        return playfield;
+    }
+
+    public Tape getTape(int index) {
+        return null;
+    }
+
+    public String getProgramText() {
+        return "";
+    }
+
+    public int getProgramPosition() {
+        return 0;
+    }
+
+    public List<Error> setProgramText(String text) {
+        ArrayList<Error> errors = new ArrayList<Error>();
+        return errors;
+    }
+
+    public View getPlayfieldView(int index) {
+        return view;
+    }
+
+    public View getTapeView(int index) {
+        return null;
+    }
+
+    public void setOption(String name, boolean value) {
+    }
+
+    public String exportToText() {
+        return playfield.dump();
+    }
+
+    public boolean needsInput() {
+        return false;
+    }
+
+    public boolean hasHalted() {
+        return halted;
+    }
+}
+