Alchemist (1547 bytes)
_->In_NN+2b+al+g
al+g+0NN->ak
al+g+NN->ah
ah+b->ah+m+d+z+a
ah+0b->C+Z+Q
Z+j+z->Z+j+d
Z+j+0z->M+s
M+g+b->M+g+r
M+g+h->M+g+d
M+g+0b+0h+q->J+U
J+o+h->J+o+m
J+o+a->J+o+d
J+o+0h+0a->2C+an+Q
an+j+h->an+j+d
an+j+0h->aC+s
aC+g->e+am+P
am+l+b->am+l+d
am+l+0b->al+s
ak+b->ak+m+d
ak+0b->C+aj+Q
aj+j+h->aj+j+b
aj+j+0h->I+n
I+f+e->I+f+a
I+f+b->I+f+m+d+z
I+f+0e+0b->C+ai+Q
ai+j+h->ai+j+b
ai+j+0h->aB+n
aB+f->H
H+z->H+d
H+a+e->H
H+0z+0e->G+i
G+i+0b->ag
G+i+b->az+b+n
az+f+0b->Out_a
az+f+b->G+b+n
G+f->G+t
ag+e->ag
ag+0e->af+t
af+i+e->af+i+a
af+i+0e->Out_a
Q->F+s
F+g+b->F+g+y
F+g+A->F+g
F+g+0b+0A->av+o
av+o+0m->w
av+o+m->m+ae+A
ae+m->ae+b
ae+0m->u+n
u+f+b->u+f+m
u+f+e->u+f+E
u+f+A->u+f+k+c
u+f+0b+0e+0A->ad
ad+c->ad+A
ad+0c->ac
ac+y->ac+d+c
ac+0y->ab
ab+c->ab+y
ab+0c->V+l
V+l+0k->x
V+l+k->aa+t
aa+i+0e->W
aa+i+e->Y
Y+E->Y+D+c
Y+0E->X
X+c->X+E
X+0c->aa+i
W+D->W+e
W+0D->V+P
x+E->x
x+d->x
x+b->x+k
x+0E+0d+0b->aw
aw+h->aw+d
aw+0h->aE+s
aE+g->p
p+b->p+2r
p+k->p+d
p+B->p
p+q->p
p+0b+0k+0B+0q->r+q+av+U
w+h->w+d
w+y->w+r
w+C->w+B+q
w+0h+0y+0C->aD+U
aD+o->j
U->au+s
au+g+b->au+g+d
au+g+0b->v
v+d->d+aA+t
aA+i+k->R
aA+i+0k->at
at+B->at+k+c
at+0B->L
L+c->L+B
L+r->L+b
L+0c+0r->as+n
as+f+b->as+f+r
as+f+0b->R
R+0e->K
R+e+q->ar+D+c
ar+e+q->ar+c
ar+0q->aq
aq+c->aq+q
aq+0c->R
K+D->K+e
K+h->K+b
K+0D+0h->ap+P
ap+l+b->ap+l+h
ap+l+0b->v
v+0d+k->v
v+0d+r->v
v+0d+0k+0r->o
s+0d->g
s+d->d+ao+t
ao+i->ao+P
ao+l->s
P->O+c
O+b->2c+O
O+0b->N
N+c->b+N
N+0c+e->O
N+0c+0e->l
n+b->n+c
n+0b->T
T+c->ay
T+0c->e+n
ay+c->b+T
ay+0c->f
t+d->t+c
t+0d->S
S+c->ax
S+0c->e+t
ax+c->d+S
ax+0c->i
Online demo.
Note: this is quite slow. If testing with an interpreter which supports applying a rule multiple times at once (e.g. my one - although make sure you have the latest version which fixes a bug in the parser) then you can get a significant speed-up by adding two rules:
T+2c->b+T
S+2c->d+S
which inline a route through the existing rules
T+c->ay
ay+c->b+T
S+c->ax
ax+c->d+S
Partial dissection
At a high level, this uses the same approach as my CJam answer.
The computation model of Alchemist is essentially the Minsky register machine. However, Alchemist very nicely exposes the equivalence of code and data, and by allowing many tokens on the left hand side of a production rule effectively the state is not constrained to be represented by one atom: we can use a tuple of atoms, and this allows (non-recursive) subroutines. This is very useful for golf. The only things it's really lacking are macros and debuggability.
For arrays I'm using a pairing function which can be implemented quite golfily in RMs. The empty array is represented by \$0\$, and the result of prepending \$x\$ to array \$A\$ is \$(2A+1)2^x\$. There is one subroutine to pair: the subroutine is called P and it prepends the value of e to b. There are two subroutines to unpair: n unpairs b to e and b; and t unpairs d to e and d. This allowed me to save quite a bit of shuffling data between variables, which is important: a single "move" operation
a, b = b, 0
expands to at least 17 bytes:
S+a->S+b
S+0a->T
where S is the current state and T is the next state. A non-destructive "copy" is even more expensive, because it has to be done as a "move" from a to b and an auxiliary tmp, followed by a "move" from tmp back to a.
Obfuscation
I aliased various variables to each other and eliminated about 60 states in the process of golfing the program, and many of them didn't have particularly meaningful names anyway, but to fully golf it I wrote an minimiser so the names are now thoroughly indecipherable. Good luck reverse engineering it! Here is the minimiser (in CJam), which makes a few assumptions about the code but could be adapted to minimise other Alchemist programs:
e# Obfuscate / minimise Alchemist program
e# Tokenise
qN%[SNS]e_*S%
e# Get token frequencies for substitution purposes, special-casing the I/O ones
_["+" "0" "2" "->" "_" N "In_n" "n" "Out_tmp2" "tmp2"]-
$e`$W%1f=
e# Empirically we want a two-char input for n and a one-char one for tmp2
["In_n" "Out_tmp2" "n" "tmp2"]\+
["In_NN" "Out_a" "NN"] "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"1/:A+ A2m*:e_"NN"a-+
1$,<
er
_s,p
