Rosetta Code

Execute SNUSP/D: Difference between revisions

Page Discussion

Execute SNUSP/D (view source)

Revision as of 07:48, 4 June 2008

2,307 bytes added ,  15 years ago
m
re-implemented
m (re-implemented)
Line 1:
{{implementation|SNUSP}}{{collection|RCSNUSP}}[[Category:D]]
{{incorrect|D}}
<br>
'''BUG''' This implementation does not correctly run Ian Osgood's 99-bottles SNUSP example (and also some others).
<br>
'''To do''' Fix bugs, or re-implement.
<br><br>
This implementation includes all '''Bloated SNUSP''' commands, plus a minor custom feature : ''debugInput''. ''debugInput'' is a pattern to setup a predefined string for (I/O) input. That is, just before reading I/O input operation, if this string is not empty yet, a char is ''popped/taken'' from the string, instead of actually reading from I/O. The pattern is '''debug['''<''string''>''']debug'''. Similar to the starting point '$', this pattern is searched inside the source code before execution, but from bottom lines first.<br> <br>
The following are some notes.
 
This implementation supports commands from all the three SNUSP variants, as described on the [http://esolangs.org/wiki/SNUSP Esolang SNUSP page], plus an extended mode, '''SUPERNATURAL'''.
*'''Memory'''
**The memory space is represented by a class ''Mem''. Since Bloated SNUSP allows memory pointer to move up and down, the memory space is a 2-dimensional space;
**Mem is internally represented as an associative array, with ''cfloat'' as key and ''int'' as value. Externally, the ''keys'' are integer 2-dimensional coordinates tuple (x,y), which act as a memory pointer. The tuple will convert to cfloat before accessing the associative array. The conversion is unique as long as the magnitude of x and y is less than 0x7fffff. The type of the memory cells is ''int'', it will be only interpreted as ''char/string'' during IO operation;
*'''Code Pointer'''
**This again is in a 2-dimensional space. The code pointer CP structure contains the pointer position and moving direction. It also includes functions to get the ''command code'' in the SNUSP program source under the pointer position, and to manipulate its own position and direction;
**If CP goes out of the code space, no error is thrown. In this implementation, such a situation is treated as a sub-routine return (#);
*'''Core/Thread/Execution Unit''''
**This class is what actually executes the command. In fact, ''execute'' is the only non-trivial function (besides the ''fwd'' short hand ) inside this class. Each Core owns a code pointer, a memory pointer (actually 2 int) and a cp call stack, and shares the same ''CPU''. Via the CPU, each Core can access common resources like IO, Memory Space and Code Space(program) ;
**Since this implementation supports ''Bloated'' features, aka thread execution, this class is a result of separating execution unit from ''CPU''.
*'''CPU'''
**CPU acts as a resource manager and thread execution scheduler(trivially).
*'''IO'''
**This may be the simplest class.
<br>
'''Note :'''This implementation should run fine in both D1 & D2.
<d>module rcsnusp ;
import std.stdio, std.c.stdio, std.string, std.random, std.file ;
 
'''SUPERNATURAL Mode''':
// array stack template
*'''~ : code input''' (materialization):
T[] push(T)(inout T[] stk, T value) { stk ~= value ; return stk ; }
#Read the char in current code pointer as input, assign it to memory currently pointed to by memory pointer.
T pop(T)(inout T[] stk, bool discard = true)
*'''* : join and wait tasks''' (telepathy):
{ T top = stk[$-1] ; if(discard) stk.length = stk.length - 1 ; return top ; }
#A task is initialized as free-state;
bool empty(T)(T[] stk) { return stk.length <= 0 ; }
#When a free-state task first executes this '''*''' command, the task enters into a join-state;
#Then if a join-state task executes another '''*''' command, the task enters into a wait-state;
#A wait-state task stops its execution, and waits until all alive tasks are in a wait-state, which then all tasks are return to free-state;
#This command enables global synchronization of the tasks.
#Difference to original specification:
::*The original specification does not require threads execution in a specific order. For this command to be useful, the order of execution of tasks(threads) becomes important;
::*In this implementation, the order of execution is first-created-first-executed;
::*The original specification specifies that ''(&)SPLIT''-ed old thread skips the immediate code (see below 1->2->3->4 example), which may lead to anti-intuition codes (which is good for an esoteric language :). This implementation retain old-thread-skips-immediate-code behavior in ''BLOATED'' mode, but new-thread-skips-immediate-code in ''SUPERNATURAL'' mode ( A->B->C->D example)
:::<code style="line-height: 1em;">$&\&nbsp;&nbsp;&\:&\:&\:=\<br>&nbsp;&nbsp;;&nbsp;&nbsp;&nbsp;~&nbsp;&nbsp;~&nbsp;&nbsp;~&nbsp;&nbsp;~&nbsp;&\=>&nbsp;new(B)<br>&nbsp;&nbsp;;&nbsp;&nbsp;&nbsp;A&nbsp;&nbsp;B&nbsp;&nbsp;C&nbsp;&nbsp;D&nbsp;&nbsp;\=>&nbsp;old(A)<br>&nbsp;&nbsp;;&nbsp;&nbsp;&nbsp;\=!\=!\=!\===**.~&nbsp;.#<br>&nbsp;&nbsp;;&nbsp;&nbsp;&nbsp;/=!/=!/=!/===**.#<br>&nbsp;&nbsp;;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;3&nbsp;&nbsp;4&nbsp;&nbsp;1&nbsp;&\=>&nbsp;old(1)<br>&nbsp;&nbsp;;&nbsp;&nbsp;&nbsp;~&nbsp;&nbsp;~&nbsp;&nbsp;~&nbsp;&nbsp;~&nbsp;&nbsp;\=>&nbsp;new(2)<br>&nbsp;&nbsp;\&nbsp;&nbsp;&/;&/;&/;=/&nbsp;&nbsp;<br></code>
*'''^ : wrap''' (teleport):
#The code pointer will bounce back to the code space boundary in its reverse direction;
#then forward and stop after the first '''^''' it encounter in normal direction.
<d>module snud ;
private import std.string, std.random ;
 
// io interface, which has to be defined in another module
// quick element remove for non-ordered array
interface IIO {
void rem(T)(inout T[] stk, int i) {
void setDebugInput(string s) ;
if(i + 1 < stk.length) stk[i] = stk[$-1] ;
void output(int v) ;
stk.length = stk.length - 1 ;
bool inputReady() ;
int input() ;
}
 
int rnd(int b) { return b < 0 ? (-rand()) % (-b + 1) : rand() % (b + 1) ; }
class Mem { // Memory
// simple stack template
private int[cfloat] cells ;
void push(T)(inout T[] stk, T value) { stk ~= value ; }
static const int MASK = 0xffffff ;
T pop(T)(inout T[] stk, bool discard = true) {
static cfloat i2cf(int x, int y) { return (x & MASK) + (y & MASK)*1fi ; }
intT opIndex(inttop x,= intstk[$-1] y); {
if(discard) stk.length = stk.length - 1 ;
auto key = i2cf(x,y) ; int res ;
return top ;
if(key in cells) res = cells[key] ; else cells[key] = res = 0 ;
return res ;
}
void opIndexAssign(int value, int x, int y) { cells[i2cf(x,y)] = value ; }
void reset() { foreach(k, v ; cells) cells[k] = 0 ; }
}
 
// a 2x tuple type
struct CP { // Codes Pointer
struct int xX(U,V y,= dx,U) dy{ ;
static CP opCall(intU h,x int; v,V inty hd, int vd);
{void CP c ; withto(c)ref {U xa, =ref hV ;b) y = v ;{ dxa = hdx ; dyb = vdy ; } ; return c ; }
void from(U a, V b) { x = a ; y = b ; }
static CP opCall(string[] codes) {
int v, h = -1 /* _find_ return -1 if not found */;
for(v = 0 ; v < codes.length ; v++) // find location of 1st '$'
if((h = find(codes[v], '$')) != -1) break ;
if (h == -1) { h = 0 ; v = 0 ; } // default 1st char of 1st line
else h++ ; // advanced pass the '$' char found
return CP(h, v, 1, 0) ; // default direction is (1,0)
}
CP dup() { return CP(x,y,dx,dy) ; }
bool hasCode(string[] codes)
{ return !(y < 0 || x < 0 || y >= codes.length || x >= codes[y].length) ; }
string getCode(string[] codes) { return hasCode(codes) ? codes[y][x..x+1] : null ; }
void fwd(int step = 1) { x += dx*step ; y += dy*step ; }
void turn(string t) {
if(t == "\\" || t == "/") {
int sign = t == "/" ? -1 : 1 ;
int tx = dy*sign , ty = dx*sign ;
dx = tx ; dy = ty ;
}
}
}
alias X!(int) I2 ; // intxint, used as code pointer, memory pointer & direction
alias X!(I2) ST ; // (intxint)x(intxint), used as cpu state [cp,dp]
 
enum Mode : uint {CORE = 1, MODULAR, BLOATED, SUPERNATURAL } ;
class Core { // this is _thread_ :)
bool quit = false ;
this(CPU c, CP p, int xm, int ym)
{ cpu = c ; cp = p ; mx = xm ; my = ym ; }
 
// used to locate '$' and debugInput
void fwd(int step = 1) { cp.fwd(step) ; } // short hand
string pfind(I2* loc, string[] c, string sl, string sr = null) {
void execute() {
int rx, dir = 1 , start = 0 , end = c.length - 1 ;
if(quit) throw new Exception("Execute a dead core") ;
if(sr){ dir = -1 ; start = c.length - 1 ; end = 0 ; }
string code = cp.getCode(cpu.prog) ;
with(*loc)
if(code is null) code = "#" ; // treat as _return_ if out of code space
for(x = -1, y = start ; y*dir <= end*dir ; y += dir)
Mem m = cpu.mem ;
if((x = std.string.find(c[y], sl)) >= 0) {
switch(code) {
case "<" :if(sr mx--&& ;(rx fwd= ;std.string.rfind(c[y], breaksr)) ;>= 0)
case ">" : mx++ ;if(rx fwd> ;x break+ ;sl.length)
case ":" : my-- ; fwd ;return breakc[y][x + sl.length..rx] ;
case ";" : my++ ; fwd ; break ;
case "+" : m[mx,my] = m[mx,my] + 1 ; fwd ; break ;
case "-" : m[mx,my] = m[mx,my] - 1 ; fwd ; break ;
case "," :
string ss = cpu.io.get() ;
if (ss.length > 0) {
m[mx,my] = cast(int) ss[0] ;
fwd ;
} // else do nothing and not forward cp, simulate waiting input
break ;
}
case ".": cpu.io.put(m[mx,my]) ; fwd ; break ;
return null ;
case "!": fwd(2) ; break ; // skip one step == forward x 2
case "?": fwd ; if(m[mx,my] == 0) fwd ; break ;
case "%": m[mx,my] = cpu.rnd(m[mx,my]) ; fwd ; break ;
case "&": // split core/thread
fwd ;
// will run following new core in next turn, with cp, mx, my dulplicated
cpu.addCore(new Core(cpu, cp.dup, mx, my)) ;
fwd ; // old core skip one more step
break ;
case "@": stack.push(cp.dup) ; fwd ; break ;
case "#":
if(stack.empty()) quit = true ; // ready to quit
else { cp = stack.pop() ; fwd(2) ; } // return from subroutine
break ;
case "\\","/": cp.turn(code) ; fwd ; break ;
default: fwd ;
}
}
 
private :
CPU cpu ;
CP[] stack ; // call stack ;
CP cp ; // current code pointer
int mx, my ; // memory pointer
}
 
// a 2d memory space
class IO {
final class Memory {
private char[] debugInput ;
private int[I2] cells ;
string get() {
void reset() { foreach(k, v ; cells) cells[k] = 0 ; }
if(debugInput.empty())
void opIndexAssign(int value, I2 key) { cells[key] = value ; }
return kbhit() ? [cast(char)getch()] : null ;
int opIndex(I2 key) {
return [debugInput.pop()] ;
int* vp = key in cells ; // get value pointer of the key, null if no such key
}
if(vp is null) { cells[key] = 0 ; return 0 ; } // initialize the value/key pair
void put(int c) { printf("%c", cast(char)c) ; }
return *vp ; // return the already existed value
void getDebugInput(string[] codes) {
for(int i = codes.length - 1 ; i >= 0 ; i--) {
int left = std.string.find(codes[i], "debug[") ;
int right = std.string.rfind(codes[i],"]debug") ;
if(right > left + 6) {
(debugInput = codes[i][left+6..right].dup).reverse ;
break ;
}
}
}
}
 
final class CPU {
final class Task {
private string[] program ;
enum {FREE, JOINED, WAITING }
private Mem memory ;
private IO inOutconst int id ;
I2 cp, dp, mp ;
private Core[] cores ;
private Core[] newcoresint ;join = FREE ;
bool quit = false ;
private ST[] stack ;
private char curCode ;
this(I2 Cp, I2 Dp, I2 Mp)
{ cp = Cp ; dp = Dp ; mp = Mp ; id = Id++ ; }
private void fwd(int step = 1) { with(cp) from(x + dp.x*step, y + dp.y*step) ; }
private void rfx(int dir) { with(dp) from(dir*y, dir*x) ; }
// _outer_ is D keyword for an inner class to ref outer class
private bool hasCode() { return this.outer.hasCode(cp) ; }
char getCode() { return this.outer.getCode(cp) ; }
Task execute() {
curCode = getCode ;
if(curCode in acceptCmd) // this control which SNUSP variants is used
switch(curCode) {
case '<' : mp.x-- ; break ;
case '>' : mp.x++ ; break ;
case ':' : mp.y-- ; break ;
case ';' : mp.y++ ; break ;
case '+' : m[mp] = m[mp] + 1 ; break ;
case '-' : m[mp] = m[mp] - 1 ; break ;
case ',' :
if(!io.inputReady()) goto RET ; // wait input
else m[mp] = io.input() ; break ;
case '.' : io.output(m[mp]) ; break ;
case '!' : fwd ; break ;
case '?' : if(m[mp] == 0) fwd ; break ;
case '%' : m[mp] = rnd(m[mp]) ; break ;
case '\\': rfx( 1) ; break ;
case '/' : rfx(-1) ; break ;
case '@' : stack.push(ST(cp, dp)) ; break ; // save caller state
case '#' :
if(stack.length > 0) // return from subroutine
{ stack.pop().to(cp,dp) ; fwd ; break ; }
case '\0': // else process as \0, = quit
quit = true ; goto RET ;
case '&' :
if(tasksMode == Mode.BLOATED) // old task skip immediate code
{ fwd ; queued ~= new Task(cp, dp, mp) ; break ; }
else // new task skip immediate code
{ fwd(2) ; queued ~= new Task(cp, dp, mp) ; fwd(-2) ; break ; }
case '~' : fwd ; m[mp] = getCode ; break ; // read next code as input
case '*' : // join/wait threads
switch(join) {
case FREE : join = JOINED ; joinwait++ ; break ; // schedule to join
case JOINED : join = WAITING ; joinwait-- ; goto RET ; // start waiting join
case WAITING :
if(joinwait <= 0) { join = FREE ; break ; } // all joined, release all
else goto RET ; // keep waiting
}
break ;
case '^' : // wrap to the boundary in reverse direction then stop after the 1st '^'
while(hasCode) fwd(-1) ; while(getCode != '^') fwd ; break ;
default: //other char is a error command, since it should be seived out
debug throw new Exception("unknown command") ;
}
fwd ; // next code
RET: // directly go here, if waiting input/join, or quit
lastcp = cp ; lastmp = mp ;
if(quit && join == JOINED) joinwait-- ;
return this ;
}
}
this(IIO inputoutput) { m = new Memory ; io = inputoutput ; }
 
bool hasCode(I2 codePtr)
static int rnd(int b) { // return a random number between and including 0 and b
{ with(codePtr) return !(x < 0 || y < 0 || x >= width || y >= lines) ; }
int a = 0 ;
char getCode(I2 codePtr)
if(a > b) { a = b ; b = 0 ; }
return a +{ castwith(intcodePtr) return hasCode(rand(codePtr) %? (bsrc[y][x] -: a'\0' +; 1)) ;}
string program() { if(prog is null) prog = join(src,"\n") ; return prog ; }
}
staticCPU string[] normalizeload(string[] codes) {
string[] csrc = splitlines(join(codes,"\n")) ; width = 0 ; lines = src.length ; prog = null ;
intforeach(k,l; lenmaxsrc) = 0 ;
foreach(l; c) { if ((src[k] = stripr(tr(l,"\0"," "))).length > lenmaxwidth) lenmaxwidth = lsrc[k].length ; }
foreach(inout k,l ; csrc) src[k] = l ~= repeat(" ", lenmaxwidth - l.length) ;
debugInput = pfind(&start, src, "debug[", "]debug") ;
return c ;
pfind(&start, src, "$") ;
if(start.x < 0) start = I2(0,0) ; else start.x++ ;
return this ;
}
CPU initialize(Mode mode = Mode.SUPERNATURAL, bool useDebugInput = true) {
if(useDebugInput) io.setDebugInput(debugInput) ; else io.setDebugInput("") ;
tasks = [ new Task(start, I2(1,0), I2(0,0)) ] ; // 1st task
tick = 0 ; Id = 0 ; joinwait = 0 ; nTaskLeft = 1 ;
queued = null ; m.reset() ; tasksMode = mode ; acceptCmd = null ;
foreach(c ; join(command[0..mode],"")) acceptCmd[c] = c ;
return this ;
}
int run(string codes,Mode mode = Mode.SUPERNATURAL, bool useDebugInput = true)
{ return load(codes).initialize(mode, useDebugInput).run() ; }
int run() { while(nTaskLeft) run1Tick ; return m[lastmp] ; }
bool run1Tick() {
if(nTaskLeft > 0) {
nTaskLeft = 0 ; tick++ ;
foreach(tsk ; tasks) // execute & update task
if((tasks[nTaskLeft] = tsk.execute).quit == false)
nTaskLeft++ ;
tasks.length = nTaskLeft ;
if(queued) { tasks ~= queued ; queued = null ; } // join queued tasks
nTaskLeft = tasks.length ;
}
return nTaskLeft > 0 ;
}
static const string[] command = ["<>+-,.!?/\\\0","@#",":;&%","~*^"] ;
this() { memory = new Mem ; inOut = new IO ; inOut.getDebugInput(program) ; }
this(string codes) {program = normalize(splitlines(codes)) ; this() ; }
this(string[] codes) { program = normalize(codes) ; this() ; }
 
Memory m ;
string[] prog() { return program ; }
IIO io ;
Mem mem() { return memory ; }
IO io() { return inOut ; }
string prog, debugInput ;
void addCore(Core c) { newcores ~= c ; }
voidMode run()tasksMode {;
Task[] tasks, queued ;
if(program is null) throw new Exception("No program") ;
I2 start, lastcp, lastmp ;
cores = [new Core(this, CP(program), 0, 0)] ; // first core
uint width, lines, tick, joinwait, nTaskLeft ;
while(cores.length + newcores.length > 0) { // execute one command for each active core
private string[] src ;
cores ~= newcores ; newcores = null ; // join and clear newcores
private char[char] acceptCmd ;
// reverse order so _rem_ will not affect those core not yet executed
private uint Id = 0 ;
for(int i = cores.length - 1 ; i >= 0 ; i--)
}</d>
if(cores[i].quit == true) cores.rem(i) ; else cores[i].execute ;
Sample SNUSP using a console io :
}
<d>module rcsnusp ;
memory.reset ;
import snud ;
}
import std.stdio, std.file, std.conv ;
 
extern(C) {
int kbhit() ;
int getch() ;
int printf(in char*,...);
}
 
final class CIO : IIO {
void main(string[] args) {
private string debugInput ;
void setDebugInput(string s) { debugInput = cast(string)s.dup.reverse ; }
void output(int v){ printf("%1c", cast(char) v) ; }
bool inputReady() { return debugInput.length || kbhit() ; }
int input()
{ return cast(int)(debugInput.length ? debugInput.pop() : getch()) ; }
}
 
int main(string[] args) {
CPU cpu = new CPU(new CIO) ;
 
int result ;
Mode mode = Mode.SUPERNATURAL ;
bool useDebug = true ;
if(args.length <= 1) { // from stdin
string[] p ;
string b ;
while((b = readln()) != null) p ~= std.string.chomp(b) ;
cpu.load(std.string.join(p,"\n")).initialize(mode,useDebug) ;
(new CPU(p)).run ;
} else { for(int i = 0 ; i < 10 ; i++) { // fromdo filesome namesdebug action
foreach(f ; args[1cpu..$])run1Tick ;
trywith {(cpu.tasks[0])
writefln( // debug state output
(new CPU(cast(string) std.file.read(f))).run ;
"m(%3d,%3d)=[%4d][%1s] c(%3d,%3d,%3d,%3d)=[%1s](%3d) id<%3d> jc(%1d) quit[%3s]",
}
mp.x, mp.y, cpu.m[mp], cast(char) (cpu.m[mp] >= 32 && cpu.m[mp]<128 ? cpu.m[mp] : '?'),
catch(Exception e) writefln(e.msg) ;
cp.x, cp.y, dp.x, dp.y, getCode, getCode, id, join, quit ? "YES" : "NO") ;
}
result = cpu.run(std.string.join(p,"\n"), mode, useDebug) ;
} else { // from file names
if(args.length > 2 && std.string.isNumeric(args[2]))
mode = cast(Mode) toInt(args[2]) ;
if(mode < Mode.CORE || mode > Mode.SUPERNATURAL)
mode = Mode.SUPERNATURAL ;
if(args.length > 3)
useDebug = std.string.tolower(args[3]) == "no" ? false : true ;
result = cpu.run(cast(string) std.file.read(args[1]), mode, useDebug) ;
}
writefln("\ntick:%d", cpu.tick) ;
 
return result ;
}</d>
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/72343"