Simular una máquina de registro Minsky (II)

11

Esta es una extensión de Simulate a Minsky Register Machine (I) . No voy a repetir toda la descripción allí, así que lea primero la descripción del problema.

La gramática en la parte (I) fue lo más simple posible, pero resulta en programas bastante largos. Dado que este es un sitio de código de golf, preferimos tener una gramática de golf, ¿no?

En un nivel alto, los cambios de la gramática original son los siguientes:

  • La etiqueta en la primera línea es opcional.
  • El espacio en blanco es opcional, excepto donde sea necesario para separar dos identificadores adyacentes
  • Los estados pueden estar en línea. Para garantizar un análisis no ambiguo, si el primer estado de una operación de disminución es un estado en línea, debe encerrarse entre paréntesis. Esto significa que cualquier programa puede convertirse en una línea.

Por ejemplo, en los casos de prueba originales tuvimos:

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

En la gramática del golf esto se podría acortar a:

init:t-init d
d:a-(b+t+d)a
a:t-(a+a)"Ok"
a=3 b=4

o incluso:

init:t-init d:a-(b+t+d)a:t-(a+a)"Ok"
a=3 b=4

El nuevo BNF para las líneas de "programa" (en oposición a la línea final, que son datos) es:

program    ::= first_line (newline line)*
first_line ::= cmd
line       ::= named_cmd
state      ::= state_name
             | cmd
             | '"' message '"'
delim_state::= '(' cmd ')'
             | '"' message '"'
cmd        ::= raw_cmd
             | named_cmd
named_cmd  ::= state_name ' '* ':' ' '* raw_cmd
raw_cmd    ::= inc_cmd
             | dec_cmd
inc_cmd    ::= reg_name ' '* '+' ' '* state
dec_cmd    ::= reg_name ' '* '-' ' '* delim_state ' '* state
             | reg_name ' '* '-' ' '* state_name ' '* delim_state
             | reg_name ' '* '-' ' '* state_name ' '+ state
state_name ::= identifier
reg_name   ::= identifier

Los identificadores y los mensajes son flexibles como en el desafío anterior.


Todos los casos de prueba del desafío anterior siguen siendo aplicables. Además, la siguiente solución golfizada de Josephus debería ejercer la mayor parte de la gramática:

in:k-(r+t+in)in2:t-(k+in2)r-(i+n-0"ERROR n is 0")"ERROR k is 0"
0:n-(i+2:k-(r+t+2)5:t-(k+5)7:i-(r-(t+7)c:t-(i+r+c)i+0)a:t-(i+a)7)"Ok"
n=40 k=3

Rendimiento esperado:

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

Y creo que esto cubre el caso restante:

k+k-"nop""assert false"
k=3

Rendimiento esperado:

nop
k=3

Puede suponer que todos los programas tendrán una semántica sensata. En particular, tendrán al menos un estado y no redefinirán un estado. Sin embargo, como antes, se puede usar un estado antes de definirlo.

La puntuación es una variante en el código de golf. Puede escribir un programa autónomo y se puntuará como la longitud del programa en bytes después de la codificación UTF-8. Alternativamente, debido a que la reutilización del código es una buena cosa, si ha implementado la parte (I) en n1bytes, puede escribir un programa que convierta un programa de la parte (II) en un programa de la parte (I), listo para canalizar al original. Su puntaje será la duración de su programa de transformación más ceil(n1 / 2).

NB Si opta por la transformación, deberá generar nombres para los estados anónimos de tal manera que garantice que no entren en conflicto con los estados nombrados.

Peter Taylor
fuente

Respuestas:

6

Haskell, 552 499 493 caracteres

import Control.Monad.RWS
import Data.Map
main=interact$z.lines
z x=let(s:_,w)=evalRWS(mapM(q.t)x)w[]in s.f.i.t$last x 
p=get>>=q
q(l:":":x)=x%do a<-p;tell$f[(l,a)];r a
q(v:"+":x)=x%fmap(.a v 1)p
q(v:"-":x)=x%liftM2(d v)p p
q(('"':s):x)=x%r(\w->unlines[init s,do(v,x)<-assocs w;v++'=':show x++" "])
q(n:x)|n<"*"=x%p|1<3=x%asks(!n)
d v p n w|member v w&&w!v>0=p$a v(-1)w|1<3=n w
t[]=[];t x=lex x>>= \(y,x)->y:t x
i(v:_:x:t)=(v,read x):i t;i[]=[]
x%m=put x>>m;r=return;a=insertWith(+);f=fromList

Hizo más o menos una reescritura completa. Se reemplazó CPS con una mónada RWS que lee su propia salida para buscar estados que aún no ha analizado (¡sí, pereza!), Además de algunos otros ajustes.

hammar
fuente