Implementations

/* _n_nock_on(): produce .*(bus fol).  Do not virtualize.
*/
static u3_noun
_n_nock_on(u3_noun bus, u3_noun fol)
{
  u3_noun hib, gal;

  while ( 1 ) {
    hib = u3h(fol);
    gal = u3t(fol);

#ifdef U3_CPU_DEBUG
    u3R->pro.nox_d += 1;
#endif

    if ( c3y == u3r_du(hib) ) {
      u3_noun poz, riv;

      poz = _n_nock_on(u3k(bus), u3k(hib));
      riv = _n_nock_on(bus, u3k(gal));

      u3a_lose(fol);
      return u3i_cell(poz, riv);
    }
    else switch ( hib ) {
      default: return u3m_bail(c3__exit);

      case 0: {
        if ( c3n == u3r_ud(gal) ) {
          return u3m_bail(c3__exit);
        }
        else {
          u3_noun pro = u3k(u3at(gal, bus));

          u3a_lose(bus); u3a_lose(fol);
          return pro;
        }
      }
      c3_assert(!"not reached");

      case 1: {
        u3_noun pro = u3k(gal);

        u3a_lose(bus); u3a_lose(fol);
        return pro;
      }
      c3_assert(!"not reached");

      case 2: {
        u3_noun nex = _n_nock_on(u3k(bus), u3k(u3t(gal)));
        u3_noun seb = _n_nock_on(bus, u3k(u3h(gal)));

        u3a_lose(fol);
        bus = seb;
        fol = nex;
        continue;
      }
      c3_assert(!"not reached");

      case 3: {
        u3_noun gof, pro;

        gof = _n_nock_on(bus, u3k(gal));
        pro = u3r_du(gof);

        u3a_lose(gof); u3a_lose(fol);
        return pro;
      }
      c3_assert(!"not reached");

      case 4: {
        u3_noun gof, pro;

        gof = _n_nock_on(bus, u3k(gal));
        pro = u3i_vint(gof);

        u3a_lose(fol);
        return pro;
      }
      c3_assert(!"not reached");

      case 5: {
        u3_noun wim = _n_nock_on(bus, u3k(gal));
        u3_noun pro = u3r_sing(u3h(wim), u3t(wim));

        u3a_lose(wim); u3a_lose(fol);
        return pro;
      }
      c3_assert(!"not reached");

      case 6: {
        u3_noun b_gal, c_gal, d_gal;

        u3x_trel(gal, &b_gal, &c_gal, &d_gal);
        {
          u3_noun tys = _n_nock_on(u3k(bus), u3k(b_gal));
          u3_noun nex;

          if ( 0 == tys ) {
            nex = u3k(c_gal);
          } else if ( 1 == tys ) {
            nex = u3k(d_gal);
          } else return u3m_bail(c3__exit);

          u3a_lose(fol);
          fol = nex;
          continue;
        }
      }
      c3_assert(!"not reached");

      case 7: {
        u3_noun b_gal, c_gal;

        u3x_cell(gal, &b_gal, &c_gal);
        {
          u3_noun bod = _n_nock_on(bus, u3k(b_gal));
          u3_noun nex = u3k(c_gal);

          u3a_lose(fol);
          bus = bod;
          fol = nex;
          continue;
        }
      }
      c3_assert(!"not reached");

      case 8: {
        u3_noun b_gal, c_gal;

        u3x_cell(gal, &b_gal, &c_gal);
        {
          u3_noun heb = _n_nock_on(u3k(bus), u3k(b_gal));
          u3_noun bod = u3nc(heb, bus);
          u3_noun nex = u3k(c_gal);

          u3a_lose(fol);
          bus = bod;
          fol = nex;
          continue;
        }
      }
      c3_assert(!"not reached");

      case 9: {
        u3_noun b_gal, c_gal;

        u3x_cell(gal, &b_gal, &c_gal);
        {
          u3_noun seb = _n_nock_on(bus, u3k(c_gal));
          u3_noun pro;

          u3t_off(noc_o);
          pro = u3j_kick(seb, b_gal);
          u3t_on(noc_o);

          if ( u3_none != pro ) {
            u3a_lose(fol);
            return pro;
          }
          else {
            if ( c3n == u3r_ud(b_gal) ) {
              return u3m_bail(c3__exit);
            }
            else {
              u3_noun nex = u3k(u3at(b_gal, seb));

              u3a_lose(fol);
              bus = seb;
              fol = nex;
              continue;
            }
          }
        }
      }
      c3_assert(!"not reached");

      case 10: {
        u3_noun p_gal, q_gal;

        u3x_cell(gal, &p_gal, &q_gal);
        {
          u3_noun zep, hod, nex;

          if ( c3y == u3r_du(p_gal) ) {
            u3_noun b_gal = u3h(p_gal);
            u3_noun c_gal = u3t(p_gal);
            u3_noun d_gal = q_gal;

            zep = u3k(b_gal);
            hod = _n_nock_on(u3k(bus), u3k(c_gal));
            nex = u3k(d_gal);
          }
          else {
            u3_noun b_gal = p_gal;
            u3_noun c_gal = q_gal;

            zep = u3k(b_gal);
            hod = u3_nul;
            nex = u3k(c_gal);
          }

          u3a_lose(fol);
          return _n_hint(zep, hod, bus, nex);
        }
      }

      case 11: {
        u3_noun ref = _n_nock_on(u3k(bus), u3k(u3h(gal)));
        u3_noun gof = _n_nock_on(bus, u3k(u3t(gal)));
        u3_noun val;

        u3t_off(noc_o);
        val = u3m_soft_esc(ref, u3k(gof));
        u3t_on(noc_o);

        if ( !_(u3du(val)) ) {
          u3m_bail(u3nt(1, gof, 0));
        }
        if ( !_(u3du(u3t(val))) ) {
          //
          //  replace with proper error stack push
          //
          u3t_push(u3nc(c3__hunk, _n_mush(gof)));
          return u3m_bail(c3__exit);
        }
        else {
          u3_noun pro;

          u3z(gof);
          u3z(fol);
          pro = u3k(u3t(u3t(val)));
          u3z(val);

          return pro;
        }
      }
      c3_assert(!"not reached");
    }
  }
}

(ns anock.core
  (:import anock.NockException))

(declare atom? cell? cell)

(defn noun?
  "A noun is an atom or a cell."
  [noun & ns]
  (if ns false
      (or (atom? noun) (cell? noun))))

(defn atom?
  "An atom is a natural number."
  [noun & ns]
  (if ns false
   (and (integer? noun) (>= noun 0))))

(defn cell?
  "A cell is an ordered pair of nouns."
  [noun]
  (cond
   (atom? noun) false
   (nil? noun) false
   (not= 2 (count noun)) false
   :else (and (noun? (first noun))
              (noun? (second noun)))))

(defn tis
  "= (pronounced 'tis') tests a cell for equality."
  [noun]
  (if (atom? noun) (throw (anock.NockException. "Cannot tis an atom."))
      (let [[a b] noun]
        (if (= a b) 0 1))))

(defn wut
  "? (pronounced 'wut') tests whether a noun is a cell."
  [noun]
  (cond
   (atom? noun) 1
   (cell? noun) 0
   :else (throw (anock.NockException. "Invalid noun."))))

(defn lus
  "+ (pronounced 'lus') adds 1 to an atom."
  [noun]
  (if (atom? noun) (inc noun)
      (throw (anock.NockException. "Can only lus atoms."))))

(defn fas
  "/ (pronounced 'fas') is a tree address function."
  [noun]
  (if (atom? noun) (throw (anock.NockException. "Cannot fas an atom."))
      (let [[a b] (cell noun)]
        (assert (and (pos? a) (atom? a)) "Subject of fas must be a positive atom.")
        (if (and (not (coll? b)) (or (= 2 a) (= 3 a)))
          (throw (anock.NockException. (str "Cannot fas noun: " noun))))
        (cond
          (= 1 a) b
          (= 2 a) (first b)
          (= 3 a) (second b)
          (even? a) (fas [2 (fas [(/ a 2) b])])
          (odd? a) (fas [3 (fas [(/ (dec a) 2) b])])))))

(defn tar
  "* (pronounced 'tar') means Nock"
  [noun]
  (if (atom? noun) (throw (anock.NockException. "Cannot tar an atom."))
      (try
        (let [noun (cell noun) [x [y z]] noun]
          (cond
            (cell? y) (cell (tar [x y]) (tar [x z]))
            (zero? y) (fas [z x])
            (= 1 y) z
            (= 3 y) (wut (tar [x z]))
            (= 4 y) (lus (tar [x z]))
            (= 5 y) (tis (tar [x z]))
            :else (let [[p q] z]
                    (cond
                      (= 2 y) (tar [(tar [x p]) (tar [x q])])
                      (= 6 y) (tar [x 2 [0 1] 2 [1 (first q) (second q)]
                                    [1 0] 2 [1 2 3] [1 0] 4 4 p])
                      (= 7 y) (tar [x 2 p 1 q])
                      (= 8 y) (tar [x 7 [[7 [0 1] p] 0 1] q])
                      (= 9 y) (tar [x 7 q 2 [0 1] 0 p])
                      (= 10 y) (if (cell? p)
                                 (tar [x 8 (second p) 7 [0 3] q])
                                 (tar [x q]))))))
        (catch RuntimeException e
          (throw (anock.NockException. (str "Cannot tar the noun " noun)))))))

(def nock tar)

; Some convenience functions
(defn apply* [f x]
  (if (and (= 1 (count x)) (coll? (first x)))
    (apply f x)
    (f x)))

(defn bracket
  "[a b c] -> [a [b c]]"
  [[a & b :as c]]
  (let [b (vec b)]
    (cond
      (and (noun? a) (apply noun? b)) (vec c)
      (apply noun? b) (apply vector (bracket a) b)
      (noun? a) [a (apply* bracket b)]
      :else [(bracket a) (apply* bracket b)])))

(defn cell [& nouns]
  (if (apply atom? nouns)
    (throw (anock.NockException. "Cannot convert atom to cell."))
    (apply* bracket nouns)))

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace NockInterpreter
{
    class Interpreter
    {
        static Dictionary<string, Noun> memocache = new Dictionary<string, Noun>();

        public static Noun Nock(Noun noun)
        {
        Start:
            Noun cache_noun;
            if (memocache.TryGetValue(noun.ToString(), out cache_noun))
            {
                return cache_noun;
            }

            if (Atom.IsAtom(noun))
                throw new Exception("Infinite loop nocking an atom: " + noun.ToString());
            else
            {
                Noun subject = noun.n1;
                if (Noun.IsCell(noun.n2))
                {
                    Cell formula = (Cell)noun.n2;
                    if (Noun.IsAtom(formula.n1)) // we have lines 25-37 of spec
                    {
                        Atom op = (Atom)formula.n1;
                        Noun operands = formula.n2;

                        switch (op.value)
                        {
                            case 0: // 25 ::    *[a 0 b]         /[b a]
                                memocache[noun.ToString()] = fas(operands, subject);
                                return memocache[noun.ToString()];
                            case 1: // 26 ::    *[a 1 b]         b
                                memocache[noun.ToString()] = operands;
                                return memocache[noun.ToString()];
                            case 2: // 27 ::    *[a 2 b c]       *[*[a b] *[a c]]
                                if (Noun.IsCell(operands))
                                {
                                    Noun a = Nock(subject, operands.n1);
                                    Noun b = Nock(subject, operands.n2);
                                    noun = Noun.CreateNoun(a, b);
                                    goto Start;
                                    //                                    return Nock(Nock(subject, operands.n1), Nock(subject, operands.n2));
                                }
                                throw new Exception("Atom after operand 2: " + operands.ToString());
                            case 3: // 28 ::    *[a 3 b]         ?*[a b]
                                memocache[noun.ToString()] = wut(Nock(subject, operands));
                                return memocache[noun.ToString()];
                            case 4: // 29 ::    *[a 4 b]         +*[a b]
                                memocache[noun.ToString()] = lus(Nock(subject, operands));
                                return memocache[noun.ToString()];
                            case 5: // 30 ::    *[a 5 b]         =*[a b]
                                memocache[noun.ToString()] = tis(Nock(subject, operands));
                                return memocache[noun.ToString()];
                            case 6: // 32 ::    *[a 6 b c d]     *[a 2 [0 1] 2 [1 c d] [1 0] 2 [1 2 3] [1 0] 4 4 b]
                                if (Noun.IsCell(operands) && Noun.IsCell(operands.n2))
                                {
                                    Noun b = operands.n1;
                                    Noun c = operands.n2.n1;
                                    Noun d = operands.n2.n2;
                                    noun = Noun.CreateNoun("[" + subject + " 2 [0 1] 2 [1 " + c + " " + d + "] [1 0] 2 [1 2 3] [1 0] 4 4 " + b + "]");
                                    goto Start;
                                    //                                    return Nock(Noun.CreateNoun("[" + subject + " 2 [0 1] 2 [1 " + c + " " + d + "] [1 0] 2 [1 2 3] [1 0] 4 4 " + b + "]"));
                                }
                                throw new Exception("Unhandled pattern for operand 6");
                            case 7: // 33 ::    *[a 7 b c]       *[a 2 b 1 c]
                                if (Noun.IsCell(operands))
                                {
                                    Noun b = operands.n1;
                                    Noun c = operands.n2;
                                    noun = Noun.CreateNoun("[" + subject + " 2 " + b + " 1 " + c + "]");
                                    goto Start;
                                    //                                    return Nock(Noun.CreateNoun("[" + subject + " 2 " + b + " 1 " + c + "]"));
                                }
                                throw new Exception("Atom after operand 7: " + operands.ToString());
                            case 8: // 34 ::    *[a 8 b c]       *[a 7 [[7 [0 1] b] 0 1] c]
                                if (Noun.IsCell(operands))
                                {
                                    Noun b = operands.n1;
                                    Noun c = operands.n2;
                                    noun = Noun.CreateNoun("[" + subject + " 7 [[7 [0 1] " + b + "] 0 1] " + c + "]");
                                    goto Start;
                                    //                                    return Nock(Noun.CreateNoun("[" + subject + " 7 [[7 [0 1] " + b + "] 0 1] " + c + "]"));
                                }
                                throw new Exception("Atom after operand 8: " + operands.ToString());
                            case 9: // 35 ::    *[a 9 b c]       *[a 7 c 2 [0 1] 0 b]
                                if (Noun.IsCell(operands))
                                {
                                    Noun b = operands.n1;
                                    Noun c = operands.n2;
                                    noun = Noun.CreateNoun("[" + subject + " 7 " + c + " 2 [0 1] 0 " + b + "]");
                                    goto Start;
                                    //                                    return Nock(Noun.CreateNoun("[" + subject + " 7 " + c + " 2 [0 1] 0 " + b + "]"));
                                }
                                throw new Exception("Atom after operand 9: " + operands.ToString());
                            case 10:
                                if (Noun.IsCell(operands))
                                {
                                    if (Noun.IsCell(operands.n1)) // 36 ::    *[a 10 [b c] d]  *[a 8 c 7 [0 3] d]
                                    {
                                        Noun b = operands.n1.n1;
                                        Noun c = operands.n1.n2;
                                        Noun d = operands.n2;
                                        noun = Noun.CreateNoun("[" + subject + " 8 " + c + " 7 [0 3] " + d + "]");
                                        goto Start;
                                        //                                        return Nock(Noun.CreateNoun("[" + subject + " 8 " + c + " 7 [0 3] " + d + "]"));
                                    }
                                    else // 37 ::    *[a 10 b c]      *[a c]
                                    {
                                        Noun c = operands.n2;
                                        noun = Noun.CreateNoun(subject, c);
                                        goto Start;
                                        //                                        return Nock(subject, c);
                                    }
                                }
                                throw new Exception("Atom after operand 10: " + operands.ToString());
                            default:
                                throw new Exception("Unknown operand: " + op.value);
                        }
                    }
                    else // 23 ::    *[a [b c] d]     [*[a b c] *[a d]]
                    {
                        memocache[noun.ToString()] = Noun.CreateNoun(Nock(subject, formula.n1), Nock(subject, formula.n2));
                        return memocache[noun.ToString()];
                    }
                }
            }
            throw new Exception("Unhandled pattern");
        }

        public static Noun Nock(string program)
        {
            Noun noun = Noun.CreateNoun(program);
            return Nock(noun);
        }

        public static Noun Nock(Noun n1, Noun n2)
        {
            Noun noun = Noun.CreateNoun(n1, n2);
            return Nock(noun);
        }

        private static Noun tis(Noun noun)
        {
            if (Noun.IsAtom(noun.ToString()))
                throw new Exception("Infinite loop tising an atom: " + noun.ToString());
            else
            {
                Cell cell = (Cell)noun;

                if (cell.n1.ToString() == cell.n2.ToString())
                    return Noun.CreateNoun("0");
                else
                    return Noun.CreateNoun("1");
            }
        }

        private static Noun lus(Noun noun)
        {
            if (Noun.IsAtom(noun.ToString()))
            {
                Atom a = (Atom)noun;
                int v = a.value + 1;
                return Noun.CreateNoun(v.ToString());
            }
            else
                throw new Exception("Infinite loop lusing a cell: " + noun.ToString());
        }

        private static Noun wut(Noun noun)
        {
            if (Noun.IsAtom(noun.ToString()))
                return Noun.CreateNoun("1");
            else
                return Noun.CreateNoun("0");
        }

        private static Noun fas(Noun n1, Noun n2)
        {
            Noun noun = Noun.CreateNoun(n1, n2);
            return fas(noun);
        }

        private static Noun fas(Noun noun)
        {
            if (Noun.IsAtom(noun.ToString()))
                throw new Exception("Infinite loop fasing an atom: " + noun.ToString());
            else
            {
                Cell c = (Cell)noun;
                // If n1 isn't an atom, I assume we throw? This isn't defined in the spec. Confirmed by John B by email. This spins forever.
                if (Noun.IsCell(c.n1.ToString()))
                    throw new Exception("Axis must be an atom: " + c.ToString());
                else
                {
                    Atom a = (Atom)c.n1;
                    if (a.value == 1)
                        return c.n2;
                    else if (a.value >= 2)
                    {
                        if (!Noun.IsCell(c.n2.ToString()))
                        {
                            throw new Exception("Only a cell can have an axis of 2 or 3: " + c.n2.ToString());
                        }
                        else
                        {
                            Cell c2 = (Cell)c.n2;
                            if (a.value == 2)
                                return c2.n1;
                            else if (a.value == 3)
                                return c2.n2;
                            else if (a.value % 2 == 0)
                            {
                                int half = a.value / 2;
                                return fas(Noun.CreateNoun("2", fas(Noun.CreateNoun(half.ToString(), c2))));
                            }
                            else if (a.value % 2 == 1)
                            {
                                int half = a.value / 2;
                                return fas(Noun.CreateNoun("3", fas(Noun.CreateNoun(half.ToString(), c2))));
                            }
                            else
                            {
                                throw new Exception("Infinite loop somewhere in fasing: " + c.n2.ToString());
                            }
                        }
                    }
                }
                throw new Exception("Infinite loop somewhere in fasing: " + c.n2.ToString());
            }
        }
    }

    class Noun
    {
        public Noun n1;
        public Noun n2;

        // takes a program, returns a pair of nouns, stringified.
        public static Tuple<string, string> SplitCell(string program)
        {

            int stackCount = 0;
            int i = 0;
            // split the string right after the first space
            foreach (char c in program)
            {
                if (IsValidChar(c))
                {
                    if (c == '[')
                        stackCount++;
                    else if (c == ']')
                        stackCount--;
                    else if (c == ' ')
                    {
                        // if we see a space, and our stack count is at 1, then we've found our split point
                        if (stackCount == 1)
                        {
                            string a = program.Substring(1, i - 1);
                            string b = program.Substring(i + 1, program.Length - (i + 2));

                            // to implement proper bracket closing, surround b with brackets if it isn't a cell and isn't an atom
                            if (!IsCell(b) && !IsAtom(b))
                                b = "[" + b + "]";
                            Tuple<string, string> tuple = new Tuple<string, string>(a, b);
                            return tuple;
                        }
                    }
                }
                else
                    throw new Exception("Invalid char in cell: " + c);
                i++;
            }
            throw new Exception("Invalid cell: " + program);
        }

        public static bool IsCell(string program)
        {
            // check if cell is valid, as above but make sure no space after bracket
            // valid tokens are: space, int, [, ]
            // from [ => [, int
            // from int => space, ], int
            // from ] => space, ]
            // from space => int, [

            // stack count must always be nonzero
            // first and last elements must be [ and ]

            int i = 0; // i is the stack count for brackets.
            int counter = 0;
            char s = '\0'; // s is the last seen character
            // split the string right after the first space
            foreach (char c in program)
            {
                if (s == '\0')
                {
                    if (c != '[')
                        return false;
                }
                else if (s == '[')
                {
                    if (!(c == '[' || IsInt(c)))
                        return false;
                }
                else if (IsInt(s))
                {
                    if (!(IsInt(c) || c == ' ' || c == ']'))
                        return false;
                }
                else if (s == ']')
                {
                    if (!(c == ']' || c == ' '))
                        return false;
                }
                else if (s == ' ')
                {
                    if (!(c == '[' || IsInt(c)))
                        return false;
                }
                s = c;
                counter++;
                if (c == '[')
                    i++;
                else if (c == ']')
                    i--;
                if (i <= 0 && counter != program.Length) // stack count can't be zero unless it's the last character
                    return false;
            }

            // We should end with stack count of zero
            if (i == 0)
                return true;
            else
                return false;
        }

        public static bool IsInt(char c)
        {
            if (c == '0' ||
                c == '1' ||
                c == '2' ||
                c == '3' ||
                c == '4' ||
                c == '5' ||
                c == '6' ||
                c == '7' ||
                c == '8' ||
                c == '9')
                return true;
            else
                return false;
        }

        public static bool IsValidChar(char c)
        {
            if (c == ' ' ||
                c == '[' ||
                c == ']' ||
                IsInt(c))
                return true;
            else
                return false;
        }

        public static bool IsAtom(string program)
        {
            int i = 0;
            if (int.TryParse(program, out i))
            {
                if (i >= 0)
                    return true;
            }
            return false;
        }

        public static bool IsAtom(Noun noun)
        {
            return IsAtom(noun.ToString());
        }

        public static bool IsCell(Noun noun)
        {
            return IsCell(noun.ToString());
        }

        public static Noun CreateNoun(string program)
        {
            if (IsAtom(program))
                return new Atom(program);
            else
                return new Cell(program);
        }

        public static Noun CreateNoun(Noun n1, Noun n2)
        {
            return CreateNoun("[" + n1.ToString() + " " + n2.ToString() + "]");
        }

        public static Noun CreateNoun(string p1, Noun n2)
        {
            return CreateNoun("[" + p1 + " " + n2.ToString() + "]");
        }

        public static Noun CreateNoun(Noun n1, string p2)
        {
            return CreateNoun("[" + n1.ToString() + " " + p2 + "]");
        }

        public static Noun CreateNoun(string p1, string p2)
        {
            return CreateNoun("[" + p1 + " " + p2 + "]");
        }
    }

    class Atom : Noun
    {
        public int value;

        public override string ToString()
        {
            return value.ToString();
        }

        public Atom(string program)
        {
            if (IsAtom(program))
            {
                int i = 0;
                bool result = int.TryParse(program, out i);
                value = i;
            }
            else
                throw new ArgumentException("Invalid Atom: " + program);
            n1 = null;
            n2 = null;
        }
    }

    class Cell : Noun
    {
        public override string ToString()
        {
            return "[" + n1.ToString() + " " + n2.ToString() + "]";
        }

        public Cell(string program)
        {
            if (IsCell(program))
            {
                Tuple<string, string> split = SplitCell(program);
                n1 = CreateNoun(split.Item1);
                n2 = CreateNoun(split.Item2);
            }
            else
                throw new ArgumentException("Invalid Cell: " + program);
        }
    }
}

@Memoized
def i(def a) {
  a.class in [
    byte, Byte,
    char, Character,
    short, Short,
    int, Integer,
    long, Long,
    BigInteger
  ] && a >= 0
}

@Memoized
def n(def a) {
  def r
  n(a, { r = it })
  r
}

@TailRecursive
def n(def a, def r) {
  if (a in List) {
    if (a.size() == 1) {
      r(a[0])
    } else if (a.size() >= 2) {
      n(a[0], { t ->
        n(a.size() == 2 ? a[1] : a.tail(), { h ->
          r([t, h])
        })
      })
    } else {
      throw new IllegalStateException()
    }
  } else if (i(a)) {
    r((BigInteger) a)
  } else {
    throw new IllegalStateException()
  }
}

@Memoized
def wut(def a) {
  i(a) ? 1 : 0
}

@Memoized
def lus(def a) {
  if (wut(a) == 0) {
    throw new IllegalStateException()
  }
  1 + a
}

@Memoized
def tis(def a) {
  if (wut(a) == 1) {
    throw new IllegalStateException()
  }
  a[0] == a[1] ? 0 : 1
}

@Memoized
def fas(def a) {
  def r
  fas(a, { r = it })
  r
}

@TailRecursive
def fas(def a, def r) {
  if (wut(a) == 1) {
    throw new IllegalStateException()
  }
  def h = a[0]
  if (!i(h)) {
    throw new IllegalStateException()
  }
  def t = a[1]
  if (h == 0) {
    throw new IllegalStateException()
  } else if (h == 1) {
    r(t)
  } else {
    if (i(t)) {
      throw new IllegalStateException()
    }
    if (h == 2) {
      r(t[0])
    } else if (h == 3) {
      r(t[1])
    } else {
      fas([h.intdiv(2), t], { p ->
        fas([2 + h.mod(2), p], { q ->
          r(q)
        })
      })
    }
  }
}

@Memoized
def tar(def a) {
  def r
  tar(a, { r = it})
  r
}

@TailRecursive
def tar(def a, def r) {
  if (wut(a) == 1) {
    throw new IllegalStateException()
  }
  def s = a[0]
  def f = a[1]
  if (wut(f) == 1) {
    throw new IllegalStateException()
  }
  def o = f[0]
  def v = f[1]
  if (wut(o) == 0) {
    tar([s, o], { p ->
      tar([s, v], { q ->
        r([p, q])
      })
    })
  } else {
    if (o == 0) {
      r(fas([v, s]))
    } else if (o == 1) {
      r(v)
    } else if (o == 3) {
      tar([s, v], {
        r(wut(it))
      })
    } else if (o == 4) {
      tar([s, v], {
        r(lus(it))
      })
    } else if (o == 5) {
      tar([s, v], {
        r(tis(it))
      })
    } else {
      if (wut(v) == 1) {
        throw new IllegalStateException()
      }
      def x = v[0]
      def y = v[1]
      if (o == 2) {
        tar([s, x], { p ->
          tar([s, y], { q ->
            tar([p, q], {
              r(it)
            })
          })
        })
      } else if (o == 7) {
        tar(n([s, 2, x, 1, y]), {
          r(it)
        })
      } else if (o == 8) {
        tar(n([s, 7, [[7, [0, 1], x], 0, 1], y]), {
          r(it)
        })
      } else if (o == 9) {
        tar(n([s, 7, y, 2, [0, 1], 0, x]), {
          r(it)
        })
      } else if (o == 10) {
        if (wut(x) == 1) {
          tar([s, y], {
            r(it)
          })
        } else {
          tar(n([s, 8, x[1], 7, [0, 3], y]), {
            r(it)
          })
        }
      } else {
        if (wut(y) == 1) {
          throw new IllegalStateException()
        }
        if (o == 6) {
          tar(n([s, 2, [0, 1], 2, [1, y[0], y[1]], [1, 0], 2, [1, 2, 3], [1, 0], 4, 4, x]), {
            r(it)
          })
        } else {
          throw new IllegalStateException()
        }
      }
    }
  }
}