Simulate a Minsky Register Machine (II)

Question

This is an extension of Simulate a Minsky Register Machine (I). I'm not going to repeat all of the description there, so please read that problem description first.

The grammar in part (I) was as simple as possible, but results in rather long programs. Since this is a code golf site, we'd rather have a golfed grammar, wouldn't we?

At a high level, the changes from the original grammar are as follows:

• The label on the first line is optional
• Whitespace is optional except where required to separate two adjacent identifiers
• States can be inlined. To ensure non-ambiguous parsing, if the first state of a decrement operation is an inlined state, it must be enclosed in parentheses. This means that any program can be golfed into a one-liner.

For example, in the original test cases we had:

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

In the golfed grammar this could be shortened to:

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

or even:

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

The new BNF for the "program" lines (as opposed to the final line, which is data) is:

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

Identifiers and messages are flexible as in the previous challenge.

---

All of the test cases from the previous challenge are still applicable. In addition, the following golfed Josephus solution should exercise most of the grammar:

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

Expected output:

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

And I think this covers the remaining case:

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

Expected output:

nop
k=3

---

You may assume that all programs will have sensible semantics. In particular, they will have at least one state and will not redefine a state. However, as before, a state may be used before it is defined.

The scoring is a variant on code-golf. You can write a self-contained program and it will score as the length of the program in bytes after UTF-8-encoding. Alternatively, because code reuse is a Good Thing, if you have implemented part (I) in n1 bytes, you can write a program which turns a part (II) program into a part (I) program, ready for piping to the original. Your score will then be the length of your transformation program plus ceil(n1 / 2).

NB If you opt for the transformation, you will need to generate names for the anonymous states in such a way that you guarantee that they don't clash with named states.

Answer 1

Haskell, 552 499 493 characters

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

Did more or less a full rewrite. Replaced CPS with a RWS monad which reads its own output to look up states it hasn't parsed yet (yay for laziness!), plus some other tweaks.