Last year, I made a bunch of changes to automatically do a lot of the manual configuration that was involved in adding a new component and also managed to package everything to do with a component into a single jar file that gets its own ClassLoader so that different components can't interfere with each other. Two major things were making the SNMP configuration almost completely automatic, and automatically adding new database rows required for new components as needed. I did all this after two people involved in implementing the service left so I didn't have to worry too much about stepping on toes or having a bunch of bureaucratic meetings.
It has worked pretty well so far. The biggest snag was that some people ran a build that automatically added some rows to the database, then moved back to an older build that would refuse to initialize because database didn't match the configured components. This is no longer be an issue, as there aren't even builds that old in production.
However, there is another associated service that has a horrible tiered maven build that requires a bunch of configuration in two of the maven components as well as requiring new database rows be added for each new component. As long as somebody else is taking care of all of that, I don't care. But I've been called on to add the configuration when there are new components, and it's annoying to have to add almost 200 lines of boilerplate XML and request a minor database script update for each new component, and then go through the convoluted maven build process.
There are a few other associated services that, as yet, require manually adding stuff for each new component, but other people have been taking care of it. One of them is a hack onto a legacy infrastructure and is the source of most of the usage. Another two really ought to fetch everything associated with a component from the main service, which does have all the mechanisms required for doing so, but were implemented to have hard-coded copies of a few things for each component. But, for at least one of them, it's in the pipeline to do it right, after which it would no longer need any changes every time a new component is added.
The mentality that all new components need a database script update seems to be somewhat ingrained. Even today, someone asked me if they needed to run a database script, presumably for their development environment, as new components are being released to production in a few weeks. Their database probably already has had all the new rows for months, since the code for the new components have been in place for months.
Monday, April 26, 2010
Monday, April 19, 2010
The turn programming language
I decided to take a shot at making a two-dimensional programming language when noting that - and |, and / and \, and N and Z are 90-degree rotations of each other.
turn is a two-dimensional programming language that is invariant under 90-degree rotations and has any number of program counters.
A program counter (PC) has a location, direction, and turn direction.
A direction is up, right, down, or left.
A turn direction is left, straight, right, or u-turn.
Each cycle, each PC executes the operation at its location, then moves to its next location. If the next location is a wall and the turn direction is not straight, the direction is changed in the turn direction until the next location is not a wall. If the PC cannot turn to a location is not a wall, the PC dies. A PC also dies if it moves off the grid. If multiple PCs have the same location, direction, and turn direction, all but one of those PCs die. Execution ends when there are no remaining PCs.
There are 8 types of locations and their operations:
/: If the direction is horizontal, the turn direction rotates 90 degrees left. If the direction is vertical, the turn direction rotates 90 degrees right.
\: If the direction is horizontal, the turn direction rotates 90 degrees right. If the direction is vertical, the turn direction rotates 90 degrees left.
-: If the direction is horizontal, there is no effect. If the direction is vertical, the turn direction rotates 180 degrees.
|: If the direction is horizontal, the turn direction rotates 180 degrees. If the direction is vertical, there is no effect.
Z: If the direction is horizontal, read a bit from input. If the direction is vertical, write a bit to output.
N: If the direction is horizontal, write a bit to output. If the direction is vertical, read a bit from input.
+: Create a new PC at this location with direction in the turned direction and turn direction straight.
O: Read from this location or write to this location. If this location contains a bit, then read that bit, otherwise, write a bit. This location initially does not contain a bit.
space or dot (.): No-op.
^ > v <: No-op. Defines the starting location and direction of a PC. The initial turn direction is straight.
any other character: Wall. No-op.
When reading a bit, if the bit read is a 0, the turn direction is rotated 90 degrees to the left. If the bit read is a 1, the turn direction is rotated 90 degrees to the right. At EOF, the turn direction is rotates 180 degrees.
If multiple PCs read the input in a cycle, they all read the same bit. If multiple PCs read the same location in a cycle, they all read the same bit.
When writing a bit, if the turn direction is left, a 0 is written. If the turn direction is right, a 1 is written. Otherwise, nothing is written.
If multiple PCs are writing to the output in a cycle, if they all write the same value, then one bit with that value is written, otherwise nothing is written. If multiple PCs are writing to the same location in a cycle, if they all write the same value, then that value is written, otherwise nothing is written.
Hello world
cat
approximate touppercase
turn is a two-dimensional programming language that is invariant under 90-degree rotations and has any number of program counters.
A program counter (PC) has a location, direction, and turn direction.
A direction is up, right, down, or left.
A turn direction is left, straight, right, or u-turn.
Each cycle, each PC executes the operation at its location, then moves to its next location. If the next location is a wall and the turn direction is not straight, the direction is changed in the turn direction until the next location is not a wall. If the PC cannot turn to a location is not a wall, the PC dies. A PC also dies if it moves off the grid. If multiple PCs have the same location, direction, and turn direction, all but one of those PCs die. Execution ends when there are no remaining PCs.
There are 8 types of locations and their operations:
/: If the direction is horizontal, the turn direction rotates 90 degrees left. If the direction is vertical, the turn direction rotates 90 degrees right.
\: If the direction is horizontal, the turn direction rotates 90 degrees right. If the direction is vertical, the turn direction rotates 90 degrees left.
-: If the direction is horizontal, there is no effect. If the direction is vertical, the turn direction rotates 180 degrees.
|: If the direction is horizontal, the turn direction rotates 180 degrees. If the direction is vertical, there is no effect.
Z: If the direction is horizontal, read a bit from input. If the direction is vertical, write a bit to output.
N: If the direction is horizontal, write a bit to output. If the direction is vertical, read a bit from input.
+: Create a new PC at this location with direction in the turned direction and turn direction straight.
O: Read from this location or write to this location. If this location contains a bit, then read that bit, otherwise, write a bit. This location initially does not contain a bit.
space or dot (.): No-op.
^ > v <: No-op. Defines the starting location and direction of a PC. The initial turn direction is straight.
any other character: Wall. No-op.
When reading a bit, if the bit read is a 0, the turn direction is rotated 90 degrees to the left. If the bit read is a 1, the turn direction is rotated 90 degrees to the right. At EOF, the turn direction is rotates 180 degrees.
If multiple PCs read the input in a cycle, they all read the same bit. If multiple PCs read the same location in a cycle, they all read the same bit.
When writing a bit, if the turn direction is left, a 0 is written. If the turn direction is right, a 1 is written. Otherwise, nothing is written.
If multiple PCs are writing to the output in a cycle, if they all write the same value, then one bit with that value is written, otherwise nothing is written. If multiple PCs are writing to the same location in a cycle, if they all write the same value, then that value is written, otherwise nothing is written.
Examples
Hello world
>/N|N|NN|N|NNNN|NN|NN|N|N|N|N|NN|N|NN|NNN|NN|N|NN|NNN|NN|N|NNNN|NN|N|NNNNNN|NN#
#N|N|NNNN|N|NNNN|N|NNNN|N|NN|NN|NNN|NN|N|NN|NN|N|NN|NNN|N|NNNN|N|NN|N|NNN|N|Z
- #
N|Z
#
cat
_v_
+
ZNZ
( )
===
approximate touppercase
##|###|#||##---------#
#.......++.-.........#
##.###.#..#NO.......+#
##.......+|-.........#
##/###.#..##.........#
-.O......O...O......+#
##.###.#..##.........#
#.|N|#...............#
#.....|#.Z##.........#
AT##-#-#\.##.........#
PO.#+/+.+.....O......N
PU.#+.+.+......O.....N
RP.#+.+.+.......O....N
OP.#+.+.+........O...N
XE.#+.+.+.........O..N
IR.#+.+.+..........O.N
MC.#.#.#..##NNNNNNNN.#
AA\#+.+.+.>/++++++++.#
TS.\/\/...|APPROXIMATE
EE#######|#TOUPPERCASE
Interpreter
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Iterator;
public class Turn {
private int height;
private int width;
private ArrayList<ArrayList<Instruction>> grid = new ArrayList<ArrayList<Instruction>>();
private ArrayList<ArrayList<Boolean>> data = new ArrayList<ArrayList<Boolean>>();
private ArrayList<PC> pcs = new ArrayList<PC>();
public enum Instruction {
SLASH, BACKSLASH, DASH, VERT, N, Z, PLUS, O, NOOP, WALL,
}
public enum TurnDir {
STRAIGHT, RIGHT, UTURN, LEFT,
}
public class PC {
private int x;
private int y;
private int dx;
private int dy;
private TurnDir turnDir;
public PC(int x, int y, char dir) {
this.x = x;
this.y = y;
switch (dir) {
case '^': dx = 0; dy = -1; break;
case '>': dx = 1; dy = 0; break;
case 'v': dx = 0; dy = 1; break;
case '<': dx = -1; dy = 0; break;
default: assert false; break;
}
turnDir = TurnDir.STRAIGHT;
}
public PC(PC pc) {
this.x = pc.x;
this.y = pc.y;
this.dx = pc.dx;
this.dy = pc.dy;
this.turnDir = pc.turnDir;
doTurn();
this.turnDir = TurnDir.STRAIGHT;
}
public boolean inBounds() {
return x >= 0 && x < width && y >= 0 && y < height;
}
public void move() {
x += dx;
y += dy;
}
public Instruction rotate(Instruction insn) {
if (dx == 0)
return insn;
switch (insn) {
case SLASH: return Instruction.BACKSLASH;
case BACKSLASH: return Instruction.SLASH;
case DASH: return Instruction.VERT;
case VERT: return Instruction.DASH;
case N: return Instruction.Z;
case Z: return Instruction.N;
default: return insn;
}
}
public TurnDir getTurnDir() {
return turnDir;
}
public void setTurnDir() {
switch (rotate(grid.get(y).get(x))) {
case SLASH:
turnDir = TurnDir.values()[(turnDir.ordinal()+1)%4];
break;
case BACKSLASH:
turnDir = TurnDir.values()[(turnDir.ordinal()+3)%4];
break;
case DASH:
turnDir = TurnDir.values()[(turnDir.ordinal()+2)%4];
break;
}
}
public boolean facingWall() {
return x + dx >= 0 && x + dx < width
&& y + dy >= 0 && y + dy < height
&& grid.get(y + dy).get(x + dx) == Instruction.WALL;
}
public void doTurn() {
int t;
switch (turnDir) {
case RIGHT: t = dx; dx = -dy; dy = t; break;
case LEFT: t = dx; dx = dy; dy = -t; break;
case UTURN: dx = -dx; dy = -dy; break;
}
}
public boolean isInput() {
return rotate(grid.get(y).get(x)) == Instruction.N;
}
public void doInput(boolean eof, boolean bit) {
if (eof)
turnDir = TurnDir.values()[(turnDir.ordinal()+2)%4];
else if (bit)
turnDir = TurnDir.values()[(turnDir.ordinal()+1)%4];
else
turnDir = TurnDir.values()[(turnDir.ordinal()+3)%4];
}
public boolean isOutput() {
return (turnDir == TurnDir.LEFT || turnDir == TurnDir.RIGHT)
&& rotate(grid.get(y).get(x)) == Instruction.Z;
}
public boolean getOutput() {
return turnDir == TurnDir.RIGHT;
}
public boolean isSpawn() {
return grid.get(y).get(x) == Instruction.PLUS
&& turnDir != TurnDir.STRAIGHT;
}
public boolean isReadSignal() {
return grid.get(y).get(x) == Instruction.O
&& data.get(y).get(x) != null;
}
public void readSignal() {
doInput(false, data.get(y).get(x));
}
public void clearSignal() {
data.get(y).set(x, null);
}
public boolean isWriteSignal() {
return (turnDir == TurnDir.LEFT || turnDir == TurnDir.RIGHT)
&& grid.get(y).get(x) == Instruction.O
&& data.get(y).get(x) == null;
}
public void setSignal() {
data.get(y).set(x, getOutput());
}
public boolean equals(PC pc) {
return pc.x == x && pc.y == y && pc.dx == dx && pc.dy == dy
&& pc.turnDir == turnDir;
}
public boolean sameLocation(PC pc) {
return pc.x == x && pc.y == y;
}
}
public Turn(BufferedReader in) throws IOException {
String line;
while ((line = in.readLine()) != null)
parseLine(line);
height = grid.size();
width = 0;
for (ArrayList<Instruction> row : grid)
width = Math.max(width, row.size());
for (ArrayList<Instruction> row : grid)
while (row.size() < width)
row.add(Instruction.NOOP);
while (data.size() < height)
data.add(new ArrayList<Boolean>());
for (ArrayList<Boolean> row : data)
while (row.size() < width)
row.add(null);
}
private void parseLine(String line) {
ArrayList<Instruction> row = new ArrayList<Instruction>();
for (int i = 0; i < line.length(); i++)
switch (line.charAt(i)) {
case '^': case '>': case 'v': case '<':
pcs.add(new PC(i, grid.size(), line.charAt(i)));
/*FALLTHROUGH*/
case ' ': case '.':
row.add(Instruction.NOOP);
break;
case '/': row.add(Instruction.SLASH); break;
case '\\': row.add(Instruction.BACKSLASH); break;
case '-': row.add(Instruction.DASH); break;
case '|': row.add(Instruction.VERT); break;
case 'N': row.add(Instruction.N); break;
case 'Z': row.add(Instruction.Z); break;
case '+': row.add(Instruction.PLUS); break;
case 'O': row.add(Instruction.O); break;
case 'X': row.add(Instruction.WALL); break;
default: row.add(Instruction.WALL); break;
}
grid.add(row);
}
public void run(BitInputStream in, BitOutputStream out) throws IOException {
ArrayList<PC> list = new ArrayList<PC>();
ArrayList<PC> list2 = new ArrayList<PC>();
for (;;) {
for (PC pc : pcs)
if (pc.isOutput())
list.add(pc);
boolean doOutput = false;
boolean output = false;
for (PC pc : list)
if (doOutput) {
if (output != pc.getOutput()) {
doOutput = false;
break;
}
} else {
doOutput = true;
output = pc.getOutput();
}
if (doOutput)
out.write(output);
list.clear();
for (PC pc : pcs) {
pc.setTurnDir();
if (pc.isInput())
list.add(pc);
}
if (list.size() > 0) {
boolean eof = in.eof();
boolean bit = in.read();
for (PC pc : list)
pc.doInput(eof, bit);
list.clear();
}
for (PC pc : pcs) {
if (pc.isReadSignal()) {
pc.readSignal();
list2.add(pc);
continue;
} else if (!pc.isWriteSignal() || list.contains(pc)) {
continue;
}
doOutput = true;
for (PC pc2 : pcs)
if (pc != pc2 && pc.sameLocation(pc2)) {
list.add(pc2);
if (pc.getOutput() != pc2.getOutput())
doOutput = false;
}
if (doOutput)
pc.setSignal();
}
list.clear();
for (PC pc : list2)
pc.clearSignal();
list2.clear();
for (PC pc : pcs)
if (pc.isSpawn())
list.add(new PC(pc));
pcs.addAll(list);
list.clear();
loop:
for (Iterator<PC> i = pcs.iterator(); i.hasNext(); ) {
PC pc = i.next();
for (PC pc2 : pcs)
if (pc2 != pc && pc2.equals(pc)) {
i.remove();
continue loop;
}
if (pc.getTurnDir() != TurnDir.STRAIGHT) {
for (int n = 0; n < 4 && pc.facingWall(); n++)
pc.doTurn();
if (pc.facingWall())
i.remove();
}
}
for (Iterator<PC> i = pcs.iterator(); i.hasNext(); ) {
PC pc = i.next();
pc.move();
if (!pc.inBounds())
i.remove();
}
if (pcs.isEmpty())
break;
}
out.flush();
}
public static class BitInputStream {
private InputStream in;
private int bit;
private int octet;
public BitInputStream(InputStream in) {
this.in = in;
this.bit = 0;
this.octet = 0;
}
public boolean eof() throws IOException {
if (octet >= 0 && bit == 0) {
bit = 128;
octet = in.read();
}
return octet < 0;
}
public boolean read() throws IOException {
if (octet >= 0 && bit == 0) {
bit = 128;
octet = in.read();
}
try {
return (octet & bit) != 0;
} finally {
bit >>>= 1;
}
}
public void close() throws IOException {
in.close();
}
}
public static class BitOutputStream {
private OutputStream out;
private int bit;
private int octet;
public BitOutputStream(OutputStream out) {
this.out = out;
this.bit = 128;
this.octet = 0;
}
public void write(boolean b) throws IOException {
if (b)
octet |= bit;
bit >>>= 1;
if (bit == 0) {
out.write(octet);
bit = 128;
octet = 0;
}
}
public void close() throws IOException {
out.close();
}
public void flush() throws IOException {
out.flush();
}
}
public static class ASCIIBitOutputStream extends BitOutputStream {
private OutputStream out;
public ASCIIBitOutputStream(OutputStream out) {
super(out);
this.out = out;
}
public void write(boolean b) throws IOException {
out.write(b ? '1' : '0');
}
}
public static void main(String[] args) throws Exception {
String src;
BitOutputStream out;
if ("-b".equals(args[0])) {
src = args[1];
out = new ASCIIBitOutputStream(System.out);
} else {
src = args[0];
out = new BitOutputStream(System.out);
}
new Turn(new BufferedReader(new FileReader(src))).run(new BitInputStream(System.in), out);
}
}
Monday, April 12, 2010
I had never taken a serious look at the Python programming language, and I really only knew it for its usage of indentation for scoping. So I decided to try using it to implement an interpreter for my 01_ programming language, which I had implemented in Java, C, and Haskell earlier. It took a few days of my spare time.
Python is dynamically typed, and I don't like dynamic typing. The static typing of Haskell, and even Java, helps catch stupid little errors.
Python classes can't be used to create abstract data types, and only naming conventions and the double-underscore name-mangling hack are used to indicate (unenforcibly) private data.
I neither like nor dislike the syntactically significant indentation. It's just another syntax. However, if I had to work with large blocks of code, I'd prefer braces, because editors can match distant pairs of braces. But maybe people using Python would avoid writing large blocks of code. People using Java certainly do write large blocks of code, though.
Python has lots of nifty syntactical sugar enabling concise code, such as with statements, list comprehensions, and iterators. The generator coroutines for writing iterators is also nice for making readable code.
The Python library seems pretty comprehensive. I don't think it matches the Java library, but I haven't really looked at it.
In any case, I've demonstrated to myself that I can pick up a new programming language. Though, in the case of Python, I didn't learn any new programming concepts, certainly nothing mind-bending like call-with-current-continuation.
In line count, the 01_ interpreter in Python is about twice the size of the interpreter in Haskell, but about half the size of the interpreter in Java, and about a fourth the size of the interpreter in C.
Python is dynamically typed, and I don't like dynamic typing. The static typing of Haskell, and even Java, helps catch stupid little errors.
Python classes can't be used to create abstract data types, and only naming conventions and the double-underscore name-mangling hack are used to indicate (unenforcibly) private data.
I neither like nor dislike the syntactically significant indentation. It's just another syntax. However, if I had to work with large blocks of code, I'd prefer braces, because editors can match distant pairs of braces. But maybe people using Python would avoid writing large blocks of code. People using Java certainly do write large blocks of code, though.
Python has lots of nifty syntactical sugar enabling concise code, such as with statements, list comprehensions, and iterators. The generator coroutines for writing iterators is also nice for making readable code.
The Python library seems pretty comprehensive. I don't think it matches the Java library, but I haven't really looked at it.
In any case, I've demonstrated to myself that I can pick up a new programming language. Though, in the case of Python, I didn't learn any new programming concepts, certainly nothing mind-bending like call-with-current-continuation.
In line count, the 01_ interpreter in Python is about twice the size of the interpreter in Haskell, but about half the size of the interpreter in Java, and about a fourth the size of the interpreter in C.
import os
import sys
def tokens(chars):
lookahead = None
while True:
if lookahead == None:
char = chars.__next__()
else:
char = lookahead
lookahead = None
if char == '0' or char == '1' or char == '.' or char == '_':
yield char
elif char == '=':
try:
lookahead = chars.__next__()
except StopIteration:
yield '='
raise StopIteration
if lookahead != '=':
yield char
else:
lookahead = None
while chars.__next__() != '\n':
pass
elif char != ' ' and char != '\t' and char != '\r' and char != '\n':
symbol = char
while True:
try:
char = chars.__next__()
except StopIteration:
yield symbol
raise StopIteration
if (char == '0' or char == '1' or char == '.' or char == '='
or char == '_' or char == ' ' or char == '\t'
or char == '\r' or char == '\n'):
yield symbol
lookahead = char
break
else:
symbol = symbol + char
class LiteralExpr:
def __init__(self, bits):
self.bits = bits
class BoundExpr:
def __init__(self, index):
self.index = index
class ConcatExpr:
def __init__(self, head, tail):
self.head = head
self.tail = tail
class CallExpr:
def __init__(self, fn, args):
self.fn = fn
self.args = args
class ParseError(BaseException):
pass
class Pattern:
def __init__(self, match, binding, index):
self.match = match
self.binding = binding
self.index = index
def is_wild(self):
return self.binding == '.'
def is_literal(self):
return self.binding == '_'
class Defn:
def __init__(self, tokens):
self.name = tokens.__next__()
if self.name == '.' or self.name == '=' or self.name == '_' \
or self.name == '0' or self.name == '1':
raise ParseError
self.patterns = self._parse_patterns(tokens)
self.body = self._collect_body(tokens)
def _parse_patterns(self, tokens):
patterns = []
match = []
index = 0
while True:
token = tokens.__next__()
if token == '=':
if match != []:
patterns.append(Pattern(match, ".", None))
return patterns
elif token == '0':
match.append(False)
elif token == '1':
match.append(True)
elif token == '.' or token == '_':
patterns.append(Pattern(match, token, None))
match = []
else:
patterns.append(Pattern(match, token, index))
match = []
index = index + 1
def _collect_body(self, tokens):
body = []
while True:
token = tokens.__next__()
if token == '.':
return body
body.append(token)
def _arity(self, fns, name):
return len(fns[name][0].patterns) if name in fns else None
def _binding(self, patterns, name):
for pattern in patterns:
if name == pattern.binding:
return pattern.index
return None
def parse_body(self, fns):
if len(self.body) == 0:
self.expr = LiteralExpr([])
else:
self.expr = self._parse_exprs(self.body, 0, self.patterns, fns)
del self.body
def _parse_exprs(self, tokens, index, patterns, fns):
exp, index = self._parse_expr(tokens, index, patterns, fns)
if index >= len(tokens):
return exp
return ConcatExpr(exp, self._parse_exprs(tokens, index, patterns, fns))
def _parse_expr(self, tokens, index, patterns, fns):
token = tokens[index]
if token == '0' or token == '1' or token == '_':
return self._parse_literal(tokens, index)
binding = self._binding(patterns, token)
if binding != None:
return BoundExpr(binding), index + 1
arity = self._arity(fns, token)
if arity == None:
raise ParseError
args = []
index = index + 1
while len(args) < arity:
if index >= len(tokens):
raise ParseError
arg, index = self._parse_expr(tokens, index, patterns, fns)
args.append(arg)
return CallExpr(token, args), index
def _parse_literal(self, tokens, index):
bits = []
while True:
if index >= len(tokens):
return LiteralExpr(bits), index
elif tokens[index] == '0':
bits.append(False)
elif tokens[index] == '1':
bits.append(True)
elif tokens[index] == '_':
return LiteralExpr(bits), index + 1
else:
return LiteralExpr(bits), index
index = index + 1
def collect_defns(fns, tokens):
def defns_list():
while True:
yield Defn(tokens)
for defn in defns_list():
if defn.name in fns:
if len(fns[defn.name][0].patterns) != len(defn.patterns):
raise ParseError
fns[defn.name].append(defn)
else:
fns[defn.name] = [defn]
def parse_file(fns, file):
def chars():
for line in file:
for char in line:
yield char
collect_defns(fns, tokens(chars()))
def parse_bodies(fns):
for name, defns in fns.items():
for defn in defns:
defn.parse_body(fns)
class UndefinedFunctionError(BaseException):
pass
class NilVal:
def value():
return None
def next():
assert False
class LiteralVal:
def __init__(self, bits, index):
self._bits = bits
self._index = index
self._next = None
def value(self):
if self._index >= len(self._bits):
return None
else:
return self._bits[self._index]
def next(self):
if self._next == None:
assert self._index < len(self._bits)
self._next = LiteralVal(self._bits, self._index + 1)
return self._next
class FileVal:
def __init__(self, file, index = 7, byte = 0):
self._file = file
self._index = index
self._byte = byte
self._next = None
def value(self):
if self._byte == None:
assert self._index == 7
bytes = self._file.read(1)
if len(bytes) == 0:
self._byte = -1
self._file.close()
else:
self._byte = bytes[0]
if self._byte < 0:
return None
return (self._byte & (1 << self._index)) != 0
def next(self):
if self._next == None:
self.value()
assert self.value() != None
if self._index > 0:
self._next = FileVal(self._file, self._index - 1, self._byte)
else:
self._next = FileVal(self._file, 7, None)
return self._next
class ConcatVal:
def __init__(self, head, tail):
self._head = head
self._tail = tail
self._value = None
self._next = None
def value(self):
if self._head != None:
bit = self._head.value()
if bit != None:
self._value = bit
self._next = ConcatVal(self._head.next(), self._tail)
else:
self._value = self._tail.value()
if self._value != None:
self._next = self._tail.next()
self._head = None
self._tail = None
return self._value
def next(self):
if self._head != None:
self.value()
assert self._value != None
return self._next
class ExprVal:
def __init__(self, fns, expr, bindings):
self._fns = fns
self._expr = expr
self._bindings = bindings
self._value = None
self._next = None
def value(self):
if self._expr != None:
if self._expr.__class__ is LiteralExpr:
self._value, self._next = self._eval_literal()
elif self._expr.__class__ is BoundExpr:
self._value, self._next = self._eval_bound()
elif self._expr.__class__ is ConcatExpr:
self._value, self._next = self._eval_concat()
elif self._expr.__class__ is CallExpr:
self._value, self._next = self._eval_call()
else:
assert False
self._expr = None
return self._value
def next(self):
if self._expr != None:
self.value()
assert self._value != None
return self._next
def _eval_literal(self):
if self._expr.bits == []:
return None, None
else:
return self._expr.bits[0], LiteralVal(self._expr.bits, 1)
def _eval_bound(self):
val = self._bindings[self._expr.index]
bit = val.value()
return bit, val.next() if bit != None else None
def _eval_concat(self):
head = ExprVal(self._fns, self._expr.head, self._bindings)
tail = ExprVal(self._fns, self._expr.tail, self._bindings)
bit = head.value()
if bit != None:
return bit, ConcatVal(head.next(), tail)
else:
bit = tail.value()
return bit, tail.next() if bit != None else None
def _eval_call(self):
val = apply(self._fns, self._expr.fn,
[ExprVal(self._fns, arg, self._bindings)
for arg in self._expr.args])
bit = val.value()
return bit, val.next() if bit != None else None
def apply(fns, fn, args):
def match(pattern, val):
for bit in pattern.match:
b = val.value()
if b == None or b != bit:
return False
val = val.next()
if pattern.is_literal():
return val.value() == None
elif pattern.is_wild():
return True
else:
return val
for defn in fns[fn]:
bindings = []
for pattern, arg in zip(defn.patterns, args):
binding = match(pattern, arg)
if binding == False:
break
elif binding == True:
continue
else:
bindings.append(binding)
else:
return ExprVal(fns, defn.expr, bindings)
raise UndefinedFunctionError
def write_value(value, stream):
b = 0
bit = 128
while value.value() != None:
if value.value():
b = b | bit
if bit == 1:
stream.write(bytes([b]))
bit = 128
b = 0
else:
bit = bit >> 1
value = value.next()
def parse_sources(files):
fns = {}
for file in files:
with open(file) as f:
parse_file(fns, f)
parse_bodies(fns)
return fns
def interpreter():
source_files = []
fn = None
args = None
stdin = FileVal(sys.stdin.buffer)
for arg in sys.argv[1:]:
if fn == None:
if arg != '-':
source_files.append(arg)
else:
fn = os.path.basename(source_files[0])
if fn.find('.') > 0:
fn = fn[0:fn.find('.')]
elif args == None:
args = []
fn = arg
elif arg == '-':
args.append(stdin)
else:
args.append(FileVal(open(arg, "rb")))
if fn == None:
fn = os.path.basename(source_files[-1])
if fn.find('.') > 0:
fn = fn[0:fn.find('.')]
if args == None:
args = []
fns = parse_sources(source_files)
arity = len(fns[fn][0].patterns)
if len(args) < arity:
args.append(stdin)
while len(args) < arity:
args.append(NilVal())
write_value(apply(fns, fn, args[0:arity]), sys.stdout.buffer)
interpreter()
Monday, April 5, 2010
Here is a RESOL interpreter in Java. I originally wrote it as multiple files, but crammed it into a single file for this post. The input and output queue size is limited to 10. The interpreter in Haskell does not have this limitation.
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.Reader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
public class ri {
public static class RESOLException extends RuntimeException {
public RESOLException(Statement statement, String message) {
super(statement.getLocation() + ": " + message);
}
public RESOLException(Statement statement, String message, Throwable t) {
super(statement.getLocation() + ": " + message, t);
}
public RESOLException(String fileName, int lineNumber, String message) {
super(fileName + ":" + lineNumber + ": " + message);
}
public RESOLException(String fileName, int lineNumber, String message, Throwable t) {
super(fileName + ":" + lineNumber + ": " + message, t);
}
}
public static class BitInputStream {
private InputStream in;
private int currentByte;
private int currentBit = 0;
private boolean eof = false;
public BitInputStream(InputStream in) {
this.in = in;
}
public boolean eof() {
return eof;
}
public boolean read() throws IOException {
if (currentBit == 0) {
currentByte = in.read();
if (currentByte < 0) {
eof = true;
in.close();
return false;
}
currentBit = 128;
}
try {
return (currentByte & currentBit) != 0;
} finally {
currentBit >>>= 1;
}
}
}
public static class BitOutputStream {
private OutputStream out;
private int currentByte = 0;
private int currentBit = 128;
public BitOutputStream(OutputStream out) {
this.out = out;
}
public void write(boolean b) throws IOException {
if (b)
currentByte |= currentBit;
currentBit >>>= 1;
if (currentBit == 0) {
out.write(currentByte);
currentByte = 0;
currentBit = 128;
}
}
}
public static class Statement {
public enum Op { DATA, CALL, CONTINUE, IF, STOP }
private String fileName;
private int lineNumber;
private String label;
private Op op;
private String arg1;
private String arg2;
private Statement next = null;
private int itemSize = 0;
private LinkedList<LinkedList<Integer>> queueStack = null;
private LinkedList<Statement> callStack = null;
public Statement(String fileName, int lineNumber, String label, Op op, String arg1, String arg2) {
this.fileName = fileName;
this.lineNumber = lineNumber;
this.label = label == null || label.length() == 0 ? null : label;
this.op = op;
this.arg1 = arg1;
this.arg2 = arg2;
switch (op) {
case DATA:
if (arg1 == null)
throw new RESOLException(this, "DATA STATEMENT REQUIRES AN ARGUMENT");
if (label != null) {
itemSize = Integer.parseInt(arg1, 10);
queueStack = new LinkedList<LinkedList<Integer>>();
queueStack.addFirst(new LinkedList<Integer>());
if (arg2 != null)
enqueueLiteral(arg2);
}
break;
case CALL:
if (arg1 == null)
throw new RESOLException(this, "CALL STATEMENT REQUIRES AN ARGUMENT");
break;
case CONTINUE:
if (arg1 == null)
throw new RESOLException(this, "CONTINUE STATEMENT REQUIRES AN ARGUMENT");
break;
case IF:
if (arg1 == null || arg2 == null)
throw new RESOLException(this, "IF STATEMENT REQUIRES TWO ARGUMENTS");
break;
case STOP:
if (arg1 != null || arg2 != null)
throw new RESOLException(this, "STOP STATEMENT CANNOT HAVE ANY ARGUMENTS");
break;
}
if (label != null)
callStack = new LinkedList<Statement>();
}
protected String getFileName() {
return fileName;
}
protected int getLineNumber() {
return lineNumber;
}
public String getLabel() {
return label;
}
protected Op getOp() {
return op;
}
protected String getArg1() {
return arg1;
}
protected String getArg2() {
return arg2;
}
public void setNext(Statement next) {
this.next = next;
}
public String getLocation() {
return fileName + ":" + lineNumber;
}
public void enqueueLiteral(String literal) {
for (int i = 0; i < literal.length(); i++)
enqueueDigit(literal.charAt(i) - '0');
}
public void enqueueItem(LinkedList<Integer> queue, int queueItemSize) {
for (int i = 0; i < Math.min(queue.size(), queueItemSize); i++)
enqueueDigit(queue.get(i));
}
public void enqueueDigit(int digit) {
assert digit >= 0 && digit <= 9;
queueStack.getFirst().addLast(digit);
}
public void dequeueItem() {
for (int i = 0; i < itemSize && queueStack.getFirst().size() > 0; i++)
queueStack.getFirst().removeFirst();
}
public int getCurrentItemSize() {
return Math.min(itemSize, queueStack.getFirst().size());
}
public int getItemDigit(int index) {
assert index < itemSize;
return queueStack.getFirst().get(index);
}
public Statement popCall(Statement t, Statement n) {
if (queueStack != null)
queueStack.removeFirst();
return callStack.removeFirst();
}
public void pushCall(Statement t, Statement n) {
if (queueStack != null)
queueStack.addFirst(new LinkedList<Integer>());
callStack.addFirst(n);
}
public boolean isData() {
return op == Op.DATA;
}
private static void enqueueTo(Statement statement, String arg, Map<String,Statement> labels) {
if (!statement.isData())
return;
Statement argStatement = labels.get(arg);
if (argStatement == null)
statement.enqueueLiteral(arg);
else
for (int i = 0; i < argStatement.getCurrentItemSize(); i++)
statement.enqueueDigit(argStatement.getItemDigit(i));
}
private static boolean equalTo(String arg1, String arg2, Map<String,Statement> labels) {
if (arg1.equals(arg2))
return true;
Statement statement1 = labels.get(arg1);
Statement statement2 = labels.get(arg2);
if (statement1 == null && statement2 == null)
return false;
if (statement1 != null && statement2 != null) {
if (statement1.getCurrentItemSize() != statement2.getCurrentItemSize())
return false;
for (int i = 0; i < statement1.getCurrentItemSize(); i++)
if (statement1.getItemDigit(i) != statement2.getItemDigit(i))
return false;
return true;
}
if (statement1 == null) {
statement1 = statement2;
arg2 = arg1;
}
if (statement1.getCurrentItemSize() != arg2.length())
return false;
for (int i = 0; i < arg2.length(); i++)
if (statement1.getItemDigit(i) != arg2.charAt(i) - '0')
return false;
return true;
}
public Statement run(Map<String,Statement> labels) {
Statement statement = null;
Statement statement2 = null;
switch (op) {
case DATA:
statement = labels.get(arg1);
if (statement == null || !statement.isData())
break;
if (arg2 == null)
statement.dequeueItem();
else
enqueueTo(statement, arg2, labels);
break;
case CALL:
statement = labels.get(arg1);
if (statement == null)
throw new RESOLException(this, "CALL TO UNKNOWN LABEL: " + arg1);
if (next == null)
throw new RESOLException(this, "UNEXPECTED END OF PROGRAM");
statement.pushCall(this, next);
if (arg2 != null)
enqueueTo(statement, arg2, labels);
return statement;
case CONTINUE:
statement = labels.get(arg1);
if (statement == null)
throw new RESOLException(this, "CONTINUE FROM UNKNOWN LABEL: " + arg1);
if (!statement.isData() || statement.getCurrentItemSize() == 0)
return statement.popCall(this, next);
if (arg2 == null)
return statement;
statement = labels.get(arg2);
if (statement == null)
throw new RESOLException(this, "CONTINUE FROM UNKNOWN LABEL: " + arg2);
return statement;
case IF:
if (!equalTo(arg1, arg2, labels)) {
if (next == null || next.next == null)
throw new RESOLException(this, "UNEXPECTED END OF PROGRAM");
return next.next;
}
break;
case STOP:
return null;
}
if (next == null)
throw new RESOLException(this, "UNEXPECTED END OF PROGRAM");
return next;
}
}
public static class FirstStatement extends Statement {
private boolean encodeOutput;
private boolean isIO;
private int[] inputItem = null;
private int inputItemSize;
private BitInputStream in;
private int[] outputItem = null;
private int outputItemSize;
private BitOutputStream out;
private int itemBitCount;
public FirstStatement(Statement statement, boolean encodeOutput) {
super(statement.getFileName(), statement.getLineNumber(), statement.getLabel(), statement.getOp(), statement.getArg1(), statement.getArg2());
this.encodeOutput = encodeOutput;
isIO = getLabel() != null && getOp() == Op.DATA;
if (isIO) {
int itemSize = Integer.parseInt(getArg1(), 10);
inputItem = new int[itemSize];
inputItemSize = 0;
in = new BitInputStream(System.in);
outputItem = new int[itemSize];
outputItemSize = 0;
out = new BitOutputStream(System.out);
int test = 0;
for (int i = 0; i < itemSize; i++)
test = test*10 + 9;
itemBitCount = 0;
boolean decCount = false;
while (test > 0) {
if ((test & 1) == 0)
decCount = true;
test >>>= 1;
itemBitCount++;
}
if (decCount)
itemBitCount--;
}
}
public void enqueueDigit(int digit) {
if (!encodeOutput) {
System.out.print(digit);
return;
}
outputItem[outputItemSize++] = digit;
if (outputItemSize >= outputItem.length)
flushOutput();
}
public void flushOutput() {
int item = 0;
for (int i = 0; i < outputItem.length; i++)
item = item*10 + outputItem[i];
int bit = 1 << (itemBitCount - 1);
while (bit != 0) {
try {
out.write((item & bit) != 0);
} catch (IOException e) {
throw new RESOLException(this, "IO EXCEPTION", e);
}
bit >>>= 1;
}
outputItemSize = 0;
Arrays.fill(outputItem, 0);
}
public void dequeueItem() {
readItem();
}
public int getCurrentItemSize() {
if (inputItemSize == 0)
readItem();
return inputItemSize;
}
public int getItemDigit(int index) {
return inputItem[index];
}
private void readItem() {
inputItemSize = 0;
if (in.eof())
return;
int item = 0;
int bit = 1 << (itemBitCount - 1);
while (!in.eof() && bit != 0) {
boolean b;
try {
b = in.read();
} catch (IOException e) {
throw new RESOLException(this, "IO EXCEPTION", e);
}
if (in.eof())
break;
if (b)
item |= bit;
bit >>>= 1;
}
for (int i = inputItem.length - 1; i >= 0; i--) {
inputItem[i] = item%10;
item = item/10;
}
inputItemSize = inputItem.length;
}
public Statement popCall(Statement t, Statement n) {
if (!isIO)
return super.popCall(t, n);
if (n == null)
throw new RESOLException(t, "UNEXPECTED END OF PROGRAM");
return n;
}
public void pushCall(Statement t, Statement n) {
if (isIO)
throw new RESOLException(t, "ILLEGAL CALL");
super.pushCall(t, n);
}
}
public static class Parser implements Iterable<Statement>, Iterator<Statement> {
private Reader in;
private String fileName;
private int lineNumber;
private int statementLineNumber = 1;
private StringBuilder currentLabel = new StringBuilder();
private StringBuilder currentStatement = new StringBuilder();
private Statement statement = null;
private boolean eof = false;
public Parser(String fileName) throws IOException {
this(fileName, new FileReader(fileName));
}
public Parser(String fileName, Reader in) {
this.fileName = fileName;
this.in = in;
this.lineNumber = 0;
}
public Iterator<Statement> iterator() {
return this;
}
public boolean hasNext() {
while (statement == null && !eof)
try {
readLine();
} catch (IOException e) {
throw new RESOLException(fileName, lineNumber, "IO EXCEPTION", e);
}
return statement != null;
}
public Statement next() {
hasNext();
try {
return statement;
} finally {
statement = null;
}
}
public void remove() {
}
private void readLine() throws IOException {
lineNumber++;
int column = 1;
int c = in.read();
if (c < 0) {
eof = true;
in.close();
finishStatement();
return;
}
if (c == 'C') {
finishStatement();
statementLineNumber++;
while (c >= 0 && c != '\n')
c = in.read();
if (c < 0) {
eof = true;
in.close();
}
return;
}
StringBuilder sb = new StringBuilder();
while (column < 6) {
if (c != ' ') {
if (isDigit(c))
sb.append((char) c);
else
throw new RESOLException(fileName, lineNumber, "ILLEGAL LABEL");
}
c = in.read();
column++;
if (c < 0) {
eof = true;
in.close();
if (sb.length() > 0)
throw new RESOLException(fileName, lineNumber, "UNEXPECTED EOF");
finishStatement();
return;
}
if (c == '\n') {
finishStatement();
return;
}
}
if (c == ' ')
finishStatement();
currentLabel.append(sb);
for (;;) {
c = in.read();
column++;
if (c < 0) {
eof = true;
in.close();
finishStatement();
return;
}
if (c == '\n')
return;
if (c == ' ' || column > 72)
continue;
if (isDigit(c) || isLetter(c) || c == ',')
currentStatement.append((char) c);
else
throw new RESOLException(fileName, lineNumber, "UNEXPECTED CHARACTER");
}
}
private boolean isDigit(int c) {
return c >= '0' && c <= '9';
}
private boolean isLetter(int c) {
return c >= 'A' && c <= 'Z';
}
private void finishStatement() {
assert statement == null;
if (currentStatement.length() == 0 && currentLabel.length() == 0) {
statementLineNumber = lineNumber;
return;
}
int i = 0;
while (i < currentStatement.length() && isLetter(currentStatement.charAt(i)))
i++;
Statement.Op op;
try {
op = Enum.valueOf(Statement.Op.class, currentStatement.substring(0, i));
} catch (IllegalArgumentException e) {
throw new RESOLException(fileName, statementLineNumber, "UNRECOGNIZED STATEMENT");
}
String arg1 = null;
int i2 = i;
while (i2 < currentStatement.length() && isDigit(currentStatement.charAt(i2)))
i2++;
if (i2 < currentStatement.length()) {
if (i2 == i || currentStatement.charAt(i2) != ',')
throw new RESOLException(fileName, statementLineNumber, "ILLEGAL ARGUMENT");
}
if (i < i2)
arg1 = currentStatement.substring(i, i2);
String arg2 = null;
i = i2 + 1;
i2 = i;
while (i2 < currentStatement.length() && isDigit(currentStatement.charAt(i2)))
i2++;
if (i2 < currentStatement.length())
throw new RESOLException(fileName, statementLineNumber, "ILLEGAL ARGUMENT");
if (i < i2)
arg2 = currentStatement.substring(i, i2);
statement = new Statement(fileName, statementLineNumber, currentLabel.toString(), op, arg1, arg2);
statementLineNumber = lineNumber;
currentLabel.setLength(0);
currentStatement.setLength(0);
}
}
public static void main(String[] args) throws Exception {
boolean encodeOutput = true;
int index = 0;
if (index < args.length && "-r".equals(args[index])) {
encodeOutput = false;
index++;
}
FirstStatement first = null;
Statement last = null;
HashMap<String,Statement> labels = new HashMap<String,Statement>();
for (; index < args.length; index++)
for (Statement s : new Parser(args[index])) {
if (first == null)
s = first = new FirstStatement(s, encodeOutput);
else if (last != null)
last.setNext(s);
last = s;
if (s.getLabel() != null) {
if (labels.containsKey(s.getLabel()))
throw new RESOLException(s, "DUPLICATE LABEL");
labels.put(s.getLabel(), s);
}
}
last = first;
while (last != null)
last = last.run(labels);
}
}
Subscribe to:
Posts (Atom)