Simulate a Minsky Register Machine (II)
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&gt;&gt;=q
q(l:":":x)=x%do a&lt;-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-&gt;unlines[init s,do(v,x)&lt;-assocs w;v++'=':show x++" "])
q(n:x)|n&lt;"*"=x%p|1&lt;3=x%asks(!n)
d v p n w|member v w&amp;&amp;w!v&gt;0=p$a v(-1)w|1&lt;3=n w
t[]=[];t x=lex x&gt;&gt;= \(y,x)-&gt;y:t x
i(v:_:x:t)=(v,read x):i t;i[]=[]
x%m=put x&gt;&gt;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.