Simular una máquina de registro Minsky (I)

26

Hay muchos formalismos, por lo que si bien puede encontrar otras fuentes útiles, espero especificar esto con suficiente claridad como para que no sean necesarias.

Un RM consta de una máquina de estados finitos y un número finito de registros con nombre, cada uno de los cuales contiene un número entero no negativo. Para facilitar la entrada de texto, esta tarea requiere que también se nombren los estados.

Hay tres tipos de estado: incremento y decremento, que hacen referencia a un registro específico; y terminar. Un estado de incremento incrementa su registro y pasa el control a su único sucesor. Un estado decreciente tiene dos sucesores: si su registro no es cero, lo decrementa y pasa el control al primer sucesor; de lo contrario (es decir, el registro es cero) simplemente pasa el control al segundo sucesor.

Para "amabilidad" como lenguaje de programación, los estados de terminación toman una cadena codificada para imprimir (para que pueda indicar una terminación excepcional).

La entrada es de stdin. El formato de entrada consta de una línea por estado, seguido del contenido del registro inicial. La primera línea es el estado inicial. BNF para las líneas estatales es:

line       ::= inc_line
             | dec_line
inc_line   ::= label ' : ' reg_name ' + ' state_name
dec_line   ::= label ' : ' reg_name ' - ' state_name ' ' state_name
state_name ::= label
             | '"' message '"'
label      ::= identifier
reg_name   ::= identifier

Existe cierta flexibilidad en la definición de identificador y mensaje. Su programa debe aceptar una cadena alfanumérica no vacía como identificador, pero puede aceptar cadenas más generales si lo prefiere (por ejemplo, si su idioma admite identificadores con guiones bajos y es más fácil trabajar con usted). De manera similar, para el mensaje debe aceptar una cadena no vacía de caracteres alfanuméricos y espacios, pero puede aceptar cadenas más complejas que permitan líneas salientes y comillas dobles si lo desea.

La última línea de entrada, que proporciona los valores de registro iniciales, es una lista separada por espacios de asignaciones identificador = int, que no debe estar vacía. No es necesario que inicialice todos los registros nombrados en el programa: se supone que cualquiera que no esté inicializado es 0.

Su programa debe leer la entrada y simular el RM. Cuando alcanza un estado de terminación, debe emitir el mensaje, una nueva línea y luego los valores de todos los registros (en cualquier formato conveniente, legible para humanos y en cualquier orden).

Nota: formalmente los registros deben contener enteros ilimitados. Sin embargo, si lo desea, puede suponer que el valor de ningún registro superará los 2 ^ 30.

Algunos ejemplos simples

a + = b, a = 0
s0 : a - s1 "Ok"
s1 : b + s0
a=3 b=4

Resultados previstos:

Ok
a=0 b=7
b + = a, t = 0
init : t - init d0
d0 : a - d1 a0
d1 : b + d2
d2 : t + d0
a0 : t - a1 "Ok"
a1 : a + a0
a=3 b=4

Resultados previstos:

Ok
a=3 b=7 t=0
Casos de prueba para máquinas más difíciles de analizar
s0 : t - s0 s1
s1 : t + "t is 1"
t=17

Resultados previstos:

t is 1
t=1

y

s0 : t - "t is nonzero" "t is zero"
t=1

Resultados previstos:

t is nonzero
t=0

Un ejemplo mas complicado

Tomado del desafío del código del problema Josephus del DailyWTF. La entrada es n (número de soldados) yk (avance) y la salida en r es la posición (indexada a cero) de la persona que sobrevive.

init0 : k - init1 init3
init1 : r + init2
init2 : t + init0
init3 : t - init4 init5
init4 : k + init3
init5 : r - init6 "ERROR k is 0"
init6 : i + init7
init7 : n - loop0 "ERROR n is 0"
loop0 : n - loop1 "Ok"
loop1 : i + loop2
loop2 : k - loop3 loop5
loop3 : r + loop4
loop4 : t + loop2
loop5 : t - loop6 loop7
loop6 : k + loop5
loop7 : i - loop8 loopa
loop8 : r - loop9 loopc
loop9 : t + loop7
loopa : t - loopb loop7
loopb : i + loopa
loopc : t - loopd loopf
loopd : i + loope
loope : r + loopc
loopf : i + loop0
n=40 k=3

Resultados previstos:

Ok
i=40 k=3 n=0 r=27 t=0

Ese programa como una imagen, para aquellos que piensan visualmente y les sería útil comprender la sintaxis: Josephus problem RM

Si disfrutaste este golf, mira la secuela .

Peter Taylor
fuente
¿La entrada proviene de stdin, de un archivo o de algún otro lugar?
Kevin Brown
@Bass, de stdin.
Peter Taylor
Debe agregar algunos casos de prueba con los siguientes problemas difíciles de manejar: 1) mensajes con espacios, 2) mensajes con signos iguales, 3) mensajes en inc_line, 4) mensajes en el primer estado de una dec_line, 5) mensajes en espacios en casos 3 y 4.
MtnViewMark
La gramática tiene un error: debe haber un espacio literal entre las dos entradas de state_name en dec_line. Tampoco está claro si quiere exigir a las personas que acepten múltiples espacios entre tokens en la entrada.
MtnViewMark
2
@Peter: +1 para un código de golf realmente carnoso con un buen equilibrio de especificaciones y espacio para maniobrar. La mayoría de las preguntas aquí han sido demasiado delgadas.
MtnViewMark

Respuestas:

10

Perl, 166

@p=<>;/=/,$_{$`}=$' for split$",pop@p;$o='\w+';(map{($r
,$o,$,,$b)=$'=~/".*?"|\S+/g if/^$o :/}@p),$_=$o=($_{$r}
+=','cmp$o)<0?do{$_{$r}=0;$b}:$,until/"/;say for eval,%_

Corre con perl -M5.010 file.

Comenzó muy diferente, pero me temo que convergió con la solución Ruby en muchas áreas hacia el final. Parece que la ventaja de Ruby es "sin sigilos" y la "mejor integración de expresiones regulares" de Perl.

Un poco de detalle de las entrañas, si no lees a Perl:

  • @p=<>: lea la descripción completa de la máquina para @p
  • /=/,$_{$`}=$' for split$",pop@p: para cada ( for) asignación ( split$") en la última línea de descripción de la máquina ( @p), ubique el signo igual ( /=/) y luego asigne el valor $'a la %_clave$`
  • $o='\w+': el estado inicial sería el primero en coincidir con los "caracteres de palabras" de expresiones regulares de Perl
  • until/"/: bucle hasta llegar a un estado de terminación:
    • map{($r,$o,$,,$b)=$'=~/".*?"|\S+/g if/^$o :/}@p: descripción del bucle en la máquina @p: cuando estamos en la línea que coincide con el estado actual ( if/^$o :/), tokenize ( /".*?"|\S+/g) el resto de la línea $'a las variables ($r,$o,$,,$b). Truco: la misma variable $osi se usa inicialmente para el nombre de la etiqueta y luego para el operador. Tan pronto como la etiqueta coincida, el operador la anula y, como una etiqueta no puede (razonablemente) llamarse + o -, nunca vuelve a coincidir.
    • $_=$o=($_{$r}+=','cmp$o)<0?do{$_{$r}=0;$b}:$,:
      - ajustar el registro objetivo $_{$r}hacia arriba o hacia abajo (ASCII magic: ','cmp'+'es 1 mientras que ','cmp'-'es -1);
      - si el resultado es negativo ( <0?solo puede ocurrir para -)
      , entonces permanezca en 0 ( $_{$r}=0) y devuelva la segunda etiqueta $b;
      - de lo contrario, devuelva la primera etiqueta (posiblemente única)$,
    • Por cierto, es en $,lugar de $apor lo que se puede pegar al siguiente token untilsin espacios en blanco en el medio.
  • say for eval,%_: volcar informe ( eval) y contenido de registros en%_
JB
fuente
Realmente no necesitas el colon /^$o :/. El cuidado solo es suficiente para garantizar que solo esté mirando las etiquetas.
Lowjacker
@Lowjacker No lo necesito para determinar que estoy en la etiqueta correcta, pero necesito que se lo mantenga fuera $'. Es un personaje en la expresión regular, serían tres $c,para tener en cuenta desde el exterior. Alternativamente, algunos más grandes pero cambian a la expresión regular de tokenización.
JB
10

Python + C, 466 caracteres

Solo por diversión, un programa de Python que compila el programa RM en C, luego compila y ejecuta el C.

import sys,os,shlex
G=shlex.shlex(sys.stdin).get_token
A=B=''
C='_:'
V={}
J=lambda x:'goto '+x+';'if'"'!=x[0]else'{puts('+x+');goto _;}'
while 1:
 L,c=G(),G()
 if''==c:break
 if':'==c:
  v,d=G(),G()
  V[v]=1;B+=L+c+v+d+d+';'
  if'+'==d:B+=J(G())
  else:B+='if('+v+'>=0)'+J(G())+'else{'+v+'=0;'+J(G())+'}'
 else:A+=L+c+G()+';'
for v in V:C+='printf("'+v+'=%d\\n",'+v+');'
open('C.c','w').write('int '+','.join(V)+';main(){'+A+B+C+'}')
os.system('gcc -w C.c;./a.out')
Keith Randall
fuente
3
Esto no funcionará si los registros tienen nombres como ' main', ' if', etc.
Nabb
1
@Nabb: Buzzkill. Le dejo al lector agregar prefijos de subrayado en los lugares correctos.
Keith Randall
6

Haskell, 444 caracteres

(w%f)(u@(s,v):z)|s==w=(s,f+v):z|t=u:(w%f)z
(w%f)[]=[(w,f)]
p#(a:z)|j==a=w p++[j]&z|t=(p++[a])#z;p#[]=w p
p&(a:z)|j==a=p:""#z|t=(p++[a])&z
c x=q(m!!0)$map((\(s,_:n)->(s,read n)).break(=='=')).w$last x where
 m=map(""#)$init x
 q[_,_,r,"+",s]d=n s$r%1$d
 q[_,_,r,_,s,z]d|maybe t(==0)(lookup r d)=n z d|t=n s$r%(-1)$d
 n('"':s)d=unlines[s,d>>=(\(r,v)->r++'=':shows v" ")]
 n s d=q(filter((==s).head)m!!0)d
main=interact$c.lines
t=1<3;j='"';w=words

Hombre, eso fue duro! El manejo adecuado de los mensajes con espacios en ellos cuesta más de 70 caracteres. El formato de salida para ser más "legible para los humanos" y coincidir con los ejemplos cuesta otros 25.


  • Editar: (498 -> 482) varios forros pequeños y algunas de las sugerencias de @ FUZxxl
  • Editar: (482 -> 453) volver a usar números reales para los registros; muchos trucos de golf aplicados
  • Editar: (453 -> 444) formato de salida en línea y análisis de valor inicial
MtnViewMark
fuente
No conozco a Haskell, por lo que no puedo descifrar toda la sintaxis, pero puedo descifrar lo suficiente como para ver que estás usando listas para el contenido del registro. Debo decir que me sorprende que sea más corto que usar ints.
Peter Taylor
Poner los enlaces locales después whereen una sola línea separada por punto y coma podría ahorrarle 6 caracteres. Y supongo que podría guardar algunos caracteres en la definición de qcambiar el verbose if-then-else a un patrón protector.
FUZxxl
Y también: simplemente asuma ciegamente, que el tercer valor está "-"en la definición qy use un guión bajo en su lugar.
FUZxxl
Supongo que podrías guardar otro personaje cambiando la línea 8 a q[_,_,r,_,s,z]d|maybe t(==0)$lookup r d=n z d|t=n s$r%(-1)$d. Pero de todos modos, este programa es muy bueno.
FUZxxl
Puede acortar considerablemente el código de análisis aprovechando lexel Preludio. Por ejemplo, algo así f[]=[];f s=lex s>>= \(t,r)->t:f rdividirá una línea en tokens mientras maneja las cadenas entre comillas correctamente.
Hammar
6

Ruby 1.9, 214 212 211 198 195 192 181 175 173 175

*s,k=*$<
a,=s
b=Hash.new 0
eval k.gsub /(\w+)=/,';b["\1"]='
loop{x,y,r,o,t,f=a.scan /".*?"|\S+/
l=(b[r]-=o<=>?,)<0?(b[r]=0;f):t
l[?"]&&puts(eval(l),b)&exit
a,=s.grep /^#{l} /}
Lowjacker
fuente
Espero que esto falle en los prefijos de las etiquetas entre sí. Pensamientos?
JB
Parece que no puedo hacer que funcione con ningún otro caso que no sean los ejemplos. ¿Qué tiene de malo esto?
JB
Creo que ya está arreglado.
Lowjacker
Ah, mucho mejor Gracias.
JB
3

Delfos, 646

Delphi no ofrece mucho con respecto a la división de cadenas y otras cosas. Afortunadamente, tenemos colecciones genéricas, lo que ayuda un poco, pero esta sigue siendo una solución bastante amplia:

uses SysUtils,Generics.Collections;type P=array[0..99]of string;Y=TDictionary<string,P>;Z=TDictionary<string,Int32>;var t:Y;l,i:string;j,k:Int32;q:P;u:Z;v:TPair<string,Int32>;begin t:=Y.Create;repeat if i=''then i:=q[0];t.Add(q[0],q);ReadLn(l);for j:=0to 6do begin k:=Pos(' ',l+' ');q[j]:=Copy(l,1,k-1);Delete(l,1,k)end;until q[1]<>':';u:=Z.Create;j:=0;repeat k:=Pos('=',q[j]);u.Add(Copy(q[j],1,k-1),StrToInt(Copy(q[j],k+1,99)));Inc(j)until q[j]='';repeat q:=t[i];i:=q[4];u.TryGetValue(q[2],j);if q[3]='+'then Inc(j)else if j=0then i:=q[5]else Dec(j);u.AddOrSetValue(q[2],j)until i[1]='"';WriteLn(i);for v in u do Write(v.Key,'=',v.Value,' ')end.

Aquí la versión sangrada y comentada:

uses SysUtils,Generics.Collections;
type
  // P is a declaration line, offsets:
  // 0 = label
  // 1 = ':'
  // 2 = register
  // 3 = operation ('-' or '+')
  // 4 = 1st state (or message)
  // 5 = 2nd state (or message)
  P=array[0..99]of string;
  // T is a dictionary of all state lines :
  Y=TDictionary<string,P>;
  // Z is a dictionary of all registers :
  Z=TDictionary<string,Int32>;
var
  t:Y;
  l,
  i:string;
  j,
  k:Int32;
  q:P;
  u:Z;
  v:TPair<string,Int32>;
begin
  // Read all input lines :
  t:=Y.Create;
  repeat
    // Put all lines into a record
    if i=''then i:=q[0];
    t.Add(q[0],q);
    // Split up each input line on spaces :
    ReadLn(l);
    for j:=0to 6do
    begin
      k:=Pos(' ',l+' ');
      q[j]:=Copy(l,1,k-1);
      Delete(l,1,k)
    end;
    // Stop when there are no more state transitions :
  until q[1]<>':';
  // Scan initial registers :
  u:=Z.Create;
  j:=0;
  repeat
    k:=Pos('=',q[j]);
    // Add each name=value pair to a dictionary :
    u.Add(Copy(q[j],1,k-1),StrToInt(Copy(q[j],k+1,99)));
    Inc(j)
  until q[j]='';
  // Execute the state machine :
  repeat
    q:=t[i];
    i:=q[4];
    u.TryGetValue(q[2],j);
    if q[3]='+'then
      Inc(j)
    else
      if j=0then
        i:=q[5]
      else
        Dec(j);
    u.AddOrSetValue(q[2],j)
  until i[1]='"';
  WriteLn(i);
  for v in u do
    Write(v.Key,'=',v.Value,' ')
end.
PatrickvL
fuente
1

PHP, 446 441 402 398 395 389 371 370 366 caracteres

<?$t=trim;$e=explode;while($l=$t(fgets(STDIN))){if(strpos($l,"=")){foreach($e(" ",$l)as$b){list($k,$c)=$e("=",$b);$v[$k]=$c;}break;}list($k,$d)=$e(":",$l);$r[$z=$t($k)]=$t($d);$c=$c?:$z;}while($d=$e(" ",$r[$c],4)){$c=$v[$a=$d[0]]||!$d[3]?$d[2]:$d[3];if(!$r[$c]){eval("echo $c.'\n';");foreach($v as$k=>$c)echo$k."=".$c." ";die;}if(!$d[3]&&++$v[$a]||$v[$a]&&--$v[$a]);}

Sin golf


<?php

$register = array();
$values = array();

while($line = trim(fgets(STDIN))){

    if(strpos($line, "=")){

        // Set each value and then continue to the calculations

        foreach(explode(" ", $line) as $var){
            list($key, $val) = explode("=", $var);

            $values[$key] = $val;
        }

        break;
    }

    list($key, $data) = explode(":", $line);

    // Add data to the register

    $register[$z = trim($key)] = trim($data);

    // Set the first register

    $current = $current?:$z;
}

while($data = explode(" ", $register[$current], 4)){

    // Determine next register and current register

    $current = $values[$target = $data[0]] || !$data[3]? $data[2] : $data[3];

    // Will return true if the register does not exist (Messages wont have a register)

    if(!$register[$current]){

        // No need to strip the quotes this way

        eval("echo$current.'\n';");

        // Print all values in the right formatting

        foreach($values as $key => $val)
            echo $key."=".$val." ";

        die();
    }

    // Only subtraction has a third index
    // Only positive values return true

    // If there is no third index, then increase the value
    // If there is a third index, increment the decrease the value if it is positive

    // Uses PHP's short-circuit operators

    if(!$data[3] && ++$values[$target] || $values[$target] && --$values[$target]);
}

Registro de cambios


446 -> 441 : admite cadenas para el primer estado, y algo de compresión leve
441 -> 402 : comprime si / sino y asignaciones tanto como sea posible
402 -> 398 : los nombres de funciones se pueden usar como constantes que se pueden usar como cadenas
398 -> 395 : Utiliza operadores de cortocircuito
395 -> 389 : No necesita la parte más
389 -> 371 : No necesita usar array_key_exists ()
371 -> 370 : Espacio innecesario eliminado
370 -> 366 : Eliminado dos espacios innecesarios en el foreach

Kevin Brown
fuente
1

Groovy, 338

m={s=r=[:];z=[:]
it.eachLine{e->((e==~/\w+=.*/)?{(e=~/((\w+)=(\d+))+/).each{r[it[2]]=it[3] as int}}:{f=(e=~/(\w+) : (.*)/)[0];s=s?:f[1];z[f[1]]=f[2];})()}
while(s[0]!='"'){p=(z[s]=~/(\w+) (.) (\w+|(?:".*?")) ?(.*)?/)[0];s=p[3];a=r[p[1]]?:0;r[p[1]]=p[2]=='-'?a?a-1:{s=p[4];0}():a+1}
println s[1..-2]+"\n"+r.collect{k,v->"$k=$v"}.join(' ')}


['''s0 : a - s1 "Ok"
s1 : b + s0
a=3 b=4''':'''Ok
a=0 b=7''',
'''init : t - init d0
d0 : a - d1 a0
d1 : b + d2
d2 : t + d0
a0 : t - a1 "Ok"
a1 : a + a0
a=3 b=4''':'''Ok
a=3 b=7 t=0''',
'''s0 : t - s0 s1
s1 : t + "t is 1"
t=17''':'''t is 1
t=1''',
'''s0 : t - "t is nonzero" "t is zero"
t=1''':'''t is nonzero
t=0''',
'''init0 : k - init1 init3
init1 : r + init2
init2 : t + init0
init3 : t - init4 init5
init4 : k + init3
init5 : r - init6 "ERROR k is 0"
init6 : i + init7
init7 : n - loop0 "ERROR n is 0"
loop0 : n - loop1 "Ok"
loop1 : i + loop2
loop2 : k - loop3 loop5
loop3 : r + loop4
loop4 : t + loop2
loop5 : t - loop6 loop7
loop6 : k + loop5
loop7 : i - loop8 loopa
loop8 : r - loop9 loopc
loop9 : t + loop7
loopa : t - loopb loop7
loopb : i + loopa
loopc : t - loopd loopf
loopd : i + loope
loope : r + loopc
loopf : i + loop0
n=40 k=3''':'''Ok
i=40 k=3 n=0 r=27 t=0'''].collect {input,expectedOutput->
    def actualOutput = m(input)
    actualOutput == expectedOutput
}
Armand
fuente
1
Probé esto pero parece que no produce nada para stdout . ¿Qué necesito agregar para ver los resultados? (PD, la especificación dice que el orden de los registros en la salida es irrelevante, por lo que puede guardar 7 caracteres de .sort())
Peter Taylor
@ Peter, gracias por la sugerencia. Tendré que agregar 8 caracteres para println... ¡ah!
Armand
1

Clojure (344 caracteres)

Con algunos saltos de línea para "legibilidad":

(let[i(apply str(butlast(slurp *in*)))]
(loop[s(read-string i)p(->> i(replace(zipmap":\n=""[] "))(apply str)(format"{%s}")read-string)]
(let[c(p s)](cond(string? s)(println s"\n"(filter #(number?(% 1))p))
(=(c 1)'-)(let[z(=(get p(c 0)0)0)](recur(c(if z 3 2))(if z p(update-in p[(c 0)]dec))))
1(recur(c 2)(update-in p[(c 0)]#(if %(inc %)1)))))))
Omar
fuente
1

Postscript () () (852) (718)

De verdad esta vez. Ejecuta todos los casos de prueba. Todavía requiere que el programa RM siga inmediatamente en la secuencia del programa.

Editar: más factoring, nombres de procedimientos reducidos.

errordict/undefined{& " * 34 eq{.()= !{& " .(=). load " .( ).}forall ^()=
stop}{^ ^ " 0 @ : 0}ifelse}put<</^{pop}/&{dup}/:{def}/#{exch}/*{& 0
get}/.{print}/~{1 index}/"{=string cvs}/`{cvn # ^ #}/+={~ load add :}/++{1
~ length 1 sub getinterval}/S{/I where{^}{/I ~ cvx :}ifelse}/D{/? # :/_ #
cvlit :}/+{D S({//_ 1 +=//?})$ ^ :}/-{/| # : D S({//_ load 0 ne{//_ -1
+=//?}{//|}ifelse})$ ^ :}/![]/@{~/! #[# cvn ! aload length & 1 add #
roll]:}/;{(=)search ^ # ^ # cvi @ :}/${* 32 eq{++}if * 34 eq{& ++(")search
^ length 2 add 4 3 roll # 0 # getinterval cvx `}{token ^
#}ifelse}>>begin{currentfile =string readline ^( : )search{`( + )search{`
$ ^ +}{( - )search ^ ` $ $ ^ -}ifelse}{( ){search{;}{; I}ifelse}loop}ifelse}loop

Sangrado y comentado con el programa adjunto.

%!
%Minsky Register Machine Simulation
errordict/undefined{ %replace the handler for the /undefined error
    & " * 34 eq{ % if, after conversion to string, it begins with '"',
        .()= !{ % print it, print newline, iterate through the register list
            & " .(=). load " .( ). % print regname=value
        }forall ^()= stop % print newline, END PROGRAM
    }{ % if it doesn't begin with '"', it's an uninitialized register
        ^ ^ " 0 @ : 0 %initialize register to zero, return zero
    }ifelse
}put
<<
/^{pop}
/&{dup}
/:{def} % cf FORTH
/#{exch}
/*{& 0 get} % cf C
/.{print} % cf BF

% these fragments were repeated several times
/~{1 index}
/"{=string cvs} % convert to string
/`{cvn # ^ #} % convert to name, exch, pop, exch
/+={~ load add :} % add a value to a variable
/++{1 ~ length 1 sub getinterval} % increment a "string pointer"

/S{/I where{^}{/I ~ cvx :}ifelse} %setINIT define initial state unless already done
/D{/? # :/_ # cvlit :} %sr define state and register for generated procedure
/+{D S({//_ 1 +=//?})$ ^ :} % generate an increment state and define
/-{/| # : D S({//_ load 0 ne{//_ -1 +=//?}{//|}ifelse})$ ^ :} % decrement state
/![] %REGS list of registers
/@{~/! #[# cvn ! aload length & 1 add # roll]:} %addreg append to REGS
/;{(=)search ^ # ^ # cvi @ :} %regline process a register assignment
/${ %tpe extract the next token or "string"
    * 32 eq{++}if %skip ahead if space
    * 34 eq{ %if quote, find the end-quote and snag both
        & ++(")search ^ length 2 add 4 3 roll # 0 # getinterval cvx `
    }{
        token ^ # %not a quote: pull a token, exch, pop
    }ifelse
}
>>begin

{
    currentfile =string readline ^
    ( : )search{ % if it's a state line
        `( + )search{ % if it's an increment
            ` $ ^ + %parse it
        }{
            ( - )search ^ ` $ $ ^ - %it's a decrement. Parse it
        }ifelse
    }{ % not a state, do register assignments, and call initial state
        ( ){search{;}{; I}ifelse}loop %Look Ma, no `exit`!
    }ifelse
}loop
init0 : k - init1 init3
init1 : r + init2
init2 : t + init0
init3 : t - init4 init5
init4 : k + init3
init5 : r - init6 "ERROR k is 0"
init6 : i + init7
init7 : n - loop0 "ERROR n is 0"
loop0 : n - loop1 "Ok"
loop1 : i + loop2
loop2 : k - loop3 loop5
loop3 : r + loop4
loop4 : t + loop2
loop5 : t - loop6 loop7
loop6 : k + loop5
loop7 : i - loop8 loopa
loop8 : r - loop9 loopc
loop9 : t + loop7
loopa : t - loopb loop7
loopb : i + loopa
loopc : t - loopd loopf
loopd : i + loope
loope : r + loopc
loopf : i + loop0
n=40 k=3
luser droog
fuente
Ha pasado un tiempo desde que escribí cualquier PostScript, pero ¿estás definiendo funciones con nombres como regline? ¿No puedes ahorrar mucho llamándolos cosas así R?
Peter Taylor
Sí definitivamente. Pero también hay un problema potencial ya que todas estas definiciones coexisten con el estado y registran nombres en el mismo diccionario. Así que he estado tratando de encontrar caracteres de puntuación con algún valor mnemónico (para poder leerlo :). También espero encontrar más reducciones algorítmicas, por lo que no quería gastar demasiada energía antes de poder mirarlo con ojos nuevos.
luser droog el
1

AWK - 447

BEGIN{FS=":"}NF<2{split($1,x," ");for(y in x){split(x[y],q,"=");
g[q[1]]=int(q[2])}}NF>1{w=$1;l=$2;gsub(/ /,"",w);if(!a)a=w;for(i=0;;)
{sub(/^ +/,"",l);if(l=="")break;if(substr(l,1,1)=="\""){l=substr(l,2);
z=index(l,"\"")}else{z=index(l," ");z||z=length(l)+1}d[w,i++]=
substr(l,1,z-1);l=substr(l,z+1)}}END{for(;;){if(!((a,0)in d))break;h=d[a,0];
if(d[a,1]~/+/){g[h]++;a=d[a,2]}else{a=g[h]?d[a,2]:d[a,3];g[h]&&g[h]--}}
print a;for(r in g)print r"="g[r]}

Este es el resultado de la primera prueba:

% cat | awk -f mrm1.awk
s0 : a - s1 "Ok"
s1 : b + s0
a=3 b=4
^D
Ok
a=0
b=7
Dan Andreatta
fuente
1

Stax , 115 100 bytes

╥áípßNtP~£G±☼ΩtHô⌐╒╡~·7╝su9êq7h50Z`╩ë&ñ╝←j╞.½5└∩√I|ù┤╧Åτ╘8┼ç╕╒Æ►^█₧♫÷?²H½$IG☺S╚]«♀_≥å∩A+∩╣Δ└▐♫!}♥swα

Ejecutar y depurarlo

recursivo
fuente