tutorials/nock/implementations.md · urbit.org · git.iko.soy

git.iko.soy/urbit.org

on f3ca521 help sign in

urbit.org/tutorials/nock/implementations.md

2322 lines 65 kB history raw

1+++

2title = "Implementations"

3weight = 4

4template = "doc.html"

5aliases = ["docs/learn/nock/implementations"]

6+++

7We use a C implementation for our Nock interpreter. But building a Nock interpreter in another language is a fun exercise. Check out our community Nock implementations, shown below our official C implementation. (Note: the community implementations were written for a slightly older version of Nock, Nock 5K. The current version is Nock 4K.):

9## Table of Contents

11- [C](#C)

13- [Clojure](#clojure)

15- [C#](#c-sharp)

17- [Groovy](#groovy)

19- [Haskell](#haskell)

21- [JavaScript](#javascript)

23- [Python](#python)

25- [Ruby](#ruby)

27- [Scala](#scala)

29- [Scheme](#scheme)

31- [Swift](#swift)

33## C Implementation

35The actual production Nock interpreter. Note gotos for tail-call elimination,

36and manual reference counting. More about the C environment can be found

37in the [runtime system documentation](@/docs/vere/runtime.md).

38```

39/* _n_nock_on(): produce .*(bus fol). Do not virtualize.

40*/

41static u3_noun

42_n_nock_on(u3_noun bus, u3_noun fol)

44 u3_noun hib, gal;

46 while ( 1 ) {

47 hib = u3h(fol);

48 gal = u3t(fol);

50#ifdef U3_CPU_DEBUG

51 u3R->pro.nox_d += 1;

52#endif

54 if ( c3y == u3r_du(hib) ) {

55 u3_noun poz, riv;

57 poz = _n_nock_on(u3k(bus), u3k(hib));

58 riv = _n_nock_on(bus, u3k(gal));

60 u3a_lose(fol);

61 return u3i_cell(poz, riv);

62 }

63 else switch ( hib ) {

64 default: return u3m_bail(c3__exit);

66 case 0: {

67 if ( c3n == u3r_ud(gal) ) {

68 return u3m_bail(c3__exit);

69 }

70 else {

71 u3_noun pro = u3k(u3at(gal, bus));

73 u3a_lose(bus); u3a_lose(fol);

74 return pro;

75 }

76 }

77 c3_assert(!"not reached");

79 case 1: {

80 u3_noun pro = u3k(gal);

82 u3a_lose(bus); u3a_lose(fol);

83 return pro;

84 }

85 c3_assert(!"not reached");

87 case 2: {

88 u3_noun nex = _n_nock_on(u3k(bus), u3k(u3t(gal)));

89 u3_noun seb = _n_nock_on(bus, u3k(u3h(gal)));

91 u3a_lose(fol);

92 bus = seb;

93 fol = nex;

94 continue;

95 }

96 c3_assert(!"not reached");

98 case 3: {

99 u3_noun gof, pro;

101 gof = _n_nock_on(bus, u3k(gal));

102 pro = u3r_du(gof);

104 u3a_lose(gof); u3a_lose(fol);

105 return pro;

106 }

107 c3_assert(!"not reached");

109 case 4: {

110 u3_noun gof, pro;

112 gof = _n_nock_on(bus, u3k(gal));

113 pro = u3i_vint(gof);

115 u3a_lose(fol);

116 return pro;

117 }

118 c3_assert(!"not reached");

120 case 5: {

121 u3_noun wim = _n_nock_on(bus, u3k(gal));

122 u3_noun pro = u3r_sing(u3h(wim), u3t(wim));

124 u3a_lose(wim); u3a_lose(fol);

125 return pro;

126 }

127 c3_assert(!"not reached");

129 case 6: {

130 u3_noun b_gal, c_gal, d_gal;

132 u3x_trel(gal, &b_gal, &c_gal, &d_gal);

133 {

134 u3_noun tys = _n_nock_on(u3k(bus), u3k(b_gal));

135 u3_noun nex;

137 if ( 0 == tys ) {

138 nex = u3k(c_gal);

139 } else if ( 1 == tys ) {

140 nex = u3k(d_gal);

141 } else return u3m_bail(c3__exit);

143 u3a_lose(fol);

144 fol = nex;

145 continue;

146 }

147 }

148 c3_assert(!"not reached");

150 case 7: {

151 u3_noun b_gal, c_gal;

153 u3x_cell(gal, &b_gal, &c_gal);

154 {

155 u3_noun bod = _n_nock_on(bus, u3k(b_gal));

156 u3_noun nex = u3k(c_gal);

158 u3a_lose(fol);

159 bus = bod;

160 fol = nex;

161 continue;

162 }

163 }

164 c3_assert(!"not reached");

166 case 8: {

167 u3_noun b_gal, c_gal;

169 u3x_cell(gal, &b_gal, &c_gal);

170 {

171 u3_noun heb = _n_nock_on(u3k(bus), u3k(b_gal));

172 u3_noun bod = u3nc(heb, bus);

173 u3_noun nex = u3k(c_gal);

175 u3a_lose(fol);

176 bus = bod;

177 fol = nex;

178 continue;

179 }

180 }

181 c3_assert(!"not reached");

183 case 9: {

184 u3_noun b_gal, c_gal;

186 u3x_cell(gal, &b_gal, &c_gal);

187 {

188 u3_noun seb = _n_nock_on(bus, u3k(c_gal));

189 u3_noun pro;

191 u3t_off(noc_o);

192 pro = u3j_kick(seb, b_gal);

193 u3t_on(noc_o);

195 if ( u3_none != pro ) {

196 u3a_lose(fol);

197 return pro;

198 }

199 else {

200 if ( c3n == u3r_ud(b_gal) ) {

201 return u3m_bail(c3__exit);

202 }

203 else {

204 u3_noun nex = u3k(u3at(b_gal, seb));

206 u3a_lose(fol);

207 bus = seb;

208 fol = nex;

209 continue;

210 }

211 }

212 }

213 }

214 c3_assert(!"not reached");

216 case 10: {

217 u3_noun p_gal, q_gal;

219 u3x_cell(gal, &p_gal, &q_gal);

220 {

221 u3_noun zep, hod, nex;

223 if ( c3y == u3r_du(p_gal) ) {

224 u3_noun b_gal = u3h(p_gal);

225 u3_noun c_gal = u3t(p_gal);

226 u3_noun d_gal = q_gal;

228 zep = u3k(b_gal);

229 hod = _n_nock_on(u3k(bus), u3k(c_gal));

230 nex = u3k(d_gal);

231 }

232 else {

233 u3_noun b_gal = p_gal;

234 u3_noun c_gal = q_gal;

236 zep = u3k(b_gal);

237 hod = u3_nul;

238 nex = u3k(c_gal);

239 }

241 u3a_lose(fol);

242 return _n_hint(zep, hod, bus, nex);

243 }

244 }

246 case 11: {

247 u3_noun ref = _n_nock_on(u3k(bus), u3k(u3h(gal)));

248 u3_noun gof = _n_nock_on(bus, u3k(u3t(gal)));

249 u3_noun val;

251 u3t_off(noc_o);

252 val = u3m_soft_esc(ref, u3k(gof));

253 u3t_on(noc_o);

255 if ( !_(u3du(val)) ) {

256 u3m_bail(u3nt(1, gof, 0));

257 }

258 if ( !_(u3du(u3t(val))) ) {

259 //

260 // replace with proper error stack push

261 //

262 u3t_push(u3nc(c3__hunk, _n_mush(gof)));

263 return u3m_bail(c3__exit);

264 }

265 else {

266 u3_noun pro;

268 u3z(gof);

269 u3z(fol);

270 pro = u3k(u3t(u3t(val)));

271 u3z(val);

273 return pro;

274 }

275 }

276 c3_assert(!"not reached");

277 }

278 }

280```

282## Clojure

284From [Matt Earnshaw](https://github.com/mattearnshaw/anock/blob/master/src/anock/core.clj):

286```

287(ns anock.core

288 (:import anock.NockException))

290(declare atom? cell? cell)

292(defn noun?

293 "A noun is an atom or a cell."

294 [noun & ns]

295 (if ns false

296 (or (atom? noun) (cell? noun))))

298(defn atom?

299 "An atom is a natural number."

300 [noun & ns]

301 (if ns false

302 (and (integer? noun) (>= noun 0))))

304(defn cell?

305 "A cell is an ordered pair of nouns."

306 [noun]

307 (cond

308 (atom? noun) false

309 (nil? noun) false

310 (not= 2 (count noun)) false

311 :else (and (noun? (first noun))

312 (noun? (second noun)))))

314(defn tis

315 "= (pronounced 'tis') tests a cell for equality."

316 [noun]

317 (if (atom? noun) (throw (anock.NockException. "Cannot tis an atom."))

318 (let [[a b] noun]

319 (if (= a b) 0 1))))

321(defn wut

322 "? (pronounced 'wut') tests whether a noun is a cell."

323 [noun]

324 (cond

325 (atom? noun) 1

326 (cell? noun) 0

327 :else (throw (anock.NockException. "Invalid noun."))))

329(defn lus

330 "+ (pronounced 'lus') adds 1 to an atom."

331 [noun]

332 (if (atom? noun) (inc noun)

333 (throw (anock.NockException. "Can only lus atoms."))))

335(defn fas

336 "/ (pronounced 'fas') is a tree address function."

337 [noun]

338 (if (atom? noun) (throw (anock.NockException. "Cannot fas an atom."))

339 (let [[a b] (cell noun)]

340 (assert (and (pos? a) (atom? a)) "Subject of fas must be a positive atom.")

341 (if (and (not (coll? b)) (or (= 2 a) (= 3 a)))

342 (throw (anock.NockException. (str "Cannot fas noun: " noun))))

343 (cond

344 (= 1 a) b

345 (= 2 a) (first b)

346 (= 3 a) (second b)

347 (even? a) (fas [2 (fas [(/ a 2) b])])

348 (odd? a) (fas [3 (fas [(/ (dec a) 2) b])])))))

350(defn tar

351 "* (pronounced 'tar') means Nock"

352 [noun]

353 (if (atom? noun) (throw (anock.NockException. "Cannot tar an atom."))

354 (try

355 (let [noun (cell noun) [x [y z]] noun]

356 (cond

357 (cell? y) (cell (tar [x y]) (tar [x z]))

358 (zero? y) (fas [z x])

359 (= 1 y) z

360 (= 3 y) (wut (tar [x z]))

361 (= 4 y) (lus (tar [x z]))

362 (= 5 y) (tis (tar [x z]))

363 :else (let [[p q] z]

364 (cond

365 (= 2 y) (tar [(tar [x p]) (tar [x q])])

366 (= 6 y) (tar [x 2 [0 1] 2 [1 (first q) (second q)]

367 [1 0] 2 [1 2 3] [1 0] 4 4 p])

368 (= 7 y) (tar [x 2 p 1 q])

369 (= 8 y) (tar [x 7 [[7 [0 1] p] 0 1] q])

370 (= 9 y) (tar [x 7 q 2 [0 1] 0 p])

371 (= 10 y) (if (cell? p)

372 (tar [x 8 (second p) 7 [0 3] q])

373 (tar [x q]))))))

374 (catch RuntimeException e

375 (throw (anock.NockException. (str "Cannot tar the noun " noun)))))))

377(def nock tar)

379; Some convenience functions

380(defn apply* [f x]

381 (if (and (= 1 (count x)) (coll? (first x)))

382 (apply f x)

383 (f x)))

385(defn bracket

386 "[a b c] -> [a [b c]]"

387 [[a & b :as c]]

388 (let [b (vec b)]

389 (cond

390 (and (noun? a) (apply noun? b)) (vec c)

391 (apply noun? b) (apply vector (bracket a) b)

392 (noun? a) [a (apply* bracket b)]

393 :else [(bracket a) (apply* bracket b)])))

395(defn cell [& nouns]

396 (if (apply atom? nouns)

397 (throw (anock.NockException. "Cannot convert atom to cell."))

398 (apply* bracket nouns)))

399```

401## C#

403From [Julien Beasley](https://github.com/zass30/Nock5KCSharp):

405```

406using System;

407using System.Collections.Generic;

408using System.Linq;

409using System.Text;

410using System.Text.RegularExpressions;

412namespace NockInterpreter

414 class Interpreter

415 {

416 static Dictionary<string, Noun> memocache = new Dictionary<string, Noun>();

418 public static Noun Nock(Noun noun)

419 {

420 Start:

421 Noun cache_noun;

422 if (memocache.TryGetValue(noun.ToString(), out cache_noun))

423 {

424 return cache_noun;

425 }

427 if (Atom.IsAtom(noun))

428 throw new Exception("Infinite loop nocking an atom: " + noun.ToString());

429 else

430 {

431 Noun subject = noun.n1;

432 if (Noun.IsCell(noun.n2))

433 {

434 Cell formula = (Cell)noun.n2;

435 if (Noun.IsAtom(formula.n1)) // we have lines 25-37 of spec

436 {

437 Atom op = (Atom)formula.n1;

438 Noun operands = formula.n2;

440 switch (op.value)

441 {

442 case 0: // 25 :: *[a 0 b] /[b a]

443 memocache[noun.ToString()] = fas(operands, subject);

444 return memocache[noun.ToString()];

445 case 1: // 26 :: *[a 1 b] b

446 memocache[noun.ToString()] = operands;

447 return memocache[noun.ToString()];

448 case 2: // 27 :: *[a 2 b c] *[*[a b] *[a c]]

449 if (Noun.IsCell(operands))

450 {

451 Noun a = Nock(subject, operands.n1);

452 Noun b = Nock(subject, operands.n2);

453 noun = Noun.CreateNoun(a, b);

454 goto Start;

455 // return Nock(Nock(subject, operands.n1), Nock(subject, operands.n2));

456 }

457 throw new Exception("Atom after operand 2: " + operands.ToString());

458 case 3: // 28 :: *[a 3 b] ?*[a b]

459 memocache[noun.ToString()] = wut(Nock(subject, operands));

460 return memocache[noun.ToString()];

461 case 4: // 29 :: *[a 4 b] +*[a b]

462 memocache[noun.ToString()] = lus(Nock(subject, operands));

463 return memocache[noun.ToString()];

464 case 5: // 30 :: *[a 5 b] =*[a b]

465 memocache[noun.ToString()] = tis(Nock(subject, operands));

466 return memocache[noun.ToString()];

467 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]

468 if (Noun.IsCell(operands) && Noun.IsCell(operands.n2))

469 {

470 Noun b = operands.n1;

471 Noun c = operands.n2.n1;

472 Noun d = operands.n2.n2;

473 noun = Noun.CreateNoun("[" + subject + " 2 [0 1] 2 [1 " + c + " " + d + "] [1 0] 2 [1 2 3] [1 0] 4 4 " + b + "]");

474 goto Start;

475 // return Nock(Noun.CreateNoun("[" + subject + " 2 [0 1] 2 [1 " + c + " " + d + "] [1 0] 2 [1 2 3] [1 0] 4 4 " + b + "]"));

476 }

477 throw new Exception("Unhandled pattern for operand 6");

478 case 7: // 33 :: *[a 7 b c] *[a 2 b 1 c]

479 if (Noun.IsCell(operands))

480 {

481 Noun b = operands.n1;

482 Noun c = operands.n2;

483 noun = Noun.CreateNoun("[" + subject + " 2 " + b + " 1 " + c + "]");

484 goto Start;

485 // return Nock(Noun.CreateNoun("[" + subject + " 2 " + b + " 1 " + c + "]"));

486 }

487 throw new Exception("Atom after operand 7: " + operands.ToString());

488 case 8: // 34 :: *[a 8 b c] *[a 7 [[7 [0 1] b] 0 1] c]

489 if (Noun.IsCell(operands))

490 {

491 Noun b = operands.n1;

492 Noun c = operands.n2;

493 noun = Noun.CreateNoun("[" + subject + " 7 [[7 [0 1] " + b + "] 0 1] " + c + "]");

494 goto Start;

495 // return Nock(Noun.CreateNoun("[" + subject + " 7 [[7 [0 1] " + b + "] 0 1] " + c + "]"));

496 }

497 throw new Exception("Atom after operand 8: " + operands.ToString());

498 case 9: // 35 :: *[a 9 b c] *[a 7 c 2 [0 1] 0 b]

499 if (Noun.IsCell(operands))

500 {

501 Noun b = operands.n1;

502 Noun c = operands.n2;

503 noun = Noun.CreateNoun("[" + subject + " 7 " + c + " 2 [0 1] 0 " + b + "]");

504 goto Start;

505 // return Nock(Noun.CreateNoun("[" + subject + " 7 " + c + " 2 [0 1] 0 " + b + "]"));

506 }

507 throw new Exception("Atom after operand 9: " + operands.ToString());

508 case 10:

509 if (Noun.IsCell(operands))

510 {

511 if (Noun.IsCell(operands.n1)) // 36 :: *[a 10 [b c] d] *[a 8 c 7 [0 3] d]

512 {

513 Noun b = operands.n1.n1;

514 Noun c = operands.n1.n2;

515 Noun d = operands.n2;

516 noun = Noun.CreateNoun("[" + subject + " 8 " + c + " 7 [0 3] " + d + "]");

517 goto Start;

518 // return Nock(Noun.CreateNoun("[" + subject + " 8 " + c + " 7 [0 3] " + d + "]"));

519 }

520 else // 37 :: *[a 10 b c] *[a c]

521 {

522 Noun c = operands.n2;

523 noun = Noun.CreateNoun(subject, c);

524 goto Start;

525 // return Nock(subject, c);

526 }

527 }

528 throw new Exception("Atom after operand 10: " + operands.ToString());

529 default:

530 throw new Exception("Unknown operand: " + op.value);

531 }

532 }

533 else // 23 :: *[a [b c] d] [*[a b c] *[a d]]

534 {

535 memocache[noun.ToString()] = Noun.CreateNoun(Nock(subject, formula.n1), Nock(subject, formula.n2));

536 return memocache[noun.ToString()];

537 }

538 }

539 }

540 throw new Exception("Unhandled pattern");

541 }

543 public static Noun Nock(string program)

544 {

545 Noun noun = Noun.CreateNoun(program);

546 return Nock(noun);

547 }

549 public static Noun Nock(Noun n1, Noun n2)

550 {

551 Noun noun = Noun.CreateNoun(n1, n2);

552 return Nock(noun);

553 }

555 private static Noun tis(Noun noun)

556 {

557 if (Noun.IsAtom(noun.ToString()))

558 throw new Exception("Infinite loop tising an atom: " + noun.ToString());

559 else

560 {

561 Cell cell = (Cell)noun;

563 if (cell.n1.ToString() == cell.n2.ToString())

564 return Noun.CreateNoun("0");

565 else

566 return Noun.CreateNoun("1");

567 }

568 }

570 private static Noun lus(Noun noun)

571 {

572 if (Noun.IsAtom(noun.ToString()))

573 {

574 Atom a = (Atom)noun;

575 int v = a.value + 1;

576 return Noun.CreateNoun(v.ToString());

577 }

578 else

579 throw new Exception("Infinite loop lusing a cell: " + noun.ToString());

580 }

582 private static Noun wut(Noun noun)

583 {

584 if (Noun.IsAtom(noun.ToString()))

585 return Noun.CreateNoun("1");

586 else

587 return Noun.CreateNoun("0");

588 }

590 private static Noun fas(Noun n1, Noun n2)

591 {

592 Noun noun = Noun.CreateNoun(n1, n2);

593 return fas(noun);

594 }

596 private static Noun fas(Noun noun)

597 {

598 if (Noun.IsAtom(noun.ToString()))

599 throw new Exception("Infinite loop fasing an atom: " + noun.ToString());

600 else

601 {

602 Cell c = (Cell)noun;

603 // 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.

604 if (Noun.IsCell(c.n1.ToString()))

605 throw new Exception("Axis must be an atom: " + c.ToString());

606 else

607 {

608 Atom a = (Atom)c.n1;

609 if (a.value == 1)

610 return c.n2;

611 else if (a.value >= 2)

612 {

613 if (!Noun.IsCell(c.n2.ToString()))

614 {

615 throw new Exception("Only a cell can have an axis of 2 or 3: " + c.n2.ToString());

616 }

617 else

618 {

619 Cell c2 = (Cell)c.n2;

620 if (a.value == 2)

621 return c2.n1;

622 else if (a.value == 3)

623 return c2.n2;

624 else if (a.value % 2 == 0)

625 {

626 int half = a.value / 2;

627 return fas(Noun.CreateNoun("2", fas(Noun.CreateNoun(half.ToString(), c2))));

628 }

629 else if (a.value % 2 == 1)

630 {

631 int half = a.value / 2;

632 return fas(Noun.CreateNoun("3", fas(Noun.CreateNoun(half.ToString(), c2))));

633 }

634 else

635 {

636 throw new Exception("Infinite loop somewhere in fasing: " + c.n2.ToString());

637 }

638 }

639 }

640 }

641 throw new Exception("Infinite loop somewhere in fasing: " + c.n2.ToString());

642 }

643 }

644 }

646 class Noun

647 {

648 public Noun n1;

649 public Noun n2;

651 // takes a program, returns a pair of nouns, stringified.

652 public static Tuple<string, string> SplitCell(string program)

653 {

655 int stackCount = 0;

656 int i = 0;

657 // split the string right after the first space

658 foreach (char c in program)

659 {

660 if (IsValidChar(c))

661 {

662 if (c == '[')

663 stackCount++;

664 else if (c == ']')

665 stackCount--;

666 else if (c == ' ')

667 {

668 // if we see a space, and our stack count is at 1, then we've found our split point

669 if (stackCount == 1)

670 {

671 string a = program.Substring(1, i - 1);

672 string b = program.Substring(i + 1, program.Length - (i + 2));

674 // to implement proper bracket closing, surround b with brackets if it isn't a cell and isn't an atom

675 if (!IsCell(b) && !IsAtom(b))

676 b = "[" + b + "]";

677 Tuple<string, string> tuple = new Tuple<string, string>(a, b);

678 return tuple;

679 }

680 }

681 }

682 else

683 throw new Exception("Invalid char in cell: " + c);

684 i++;

685 }

686 throw new Exception("Invalid cell: " + program);

687 }

689 public static bool IsCell(string program)

690 {

691 // check if cell is valid, as above but make sure no space after bracket

692 // valid tokens are: space, int, [, ]

693 // from [ => [, int

694 // from int => space, ], int

695 // from ] => space, ]

696 // from space => int, [

698 // stack count must always be nonzero

699 // first and last elements must be [ and ]

701 int i = 0; // i is the stack count for brackets.

702 int counter = 0;

703 char s = '\0'; // s is the last seen character

704 // split the string right after the first space

705 foreach (char c in program)

706 {

707 if (s == '\0')

708 {

709 if (c != '[')

710 return false;

711 }

712 else if (s == '[')

713 {

714 if (!(c == '[' || IsInt(c)))

715 return false;

716 }

717 else if (IsInt(s))

718 {

719 if (!(IsInt(c) || c == ' ' || c == ']'))

720 return false;

721 }

722 else if (s == ']')

723 {

724 if (!(c == ']' || c == ' '))

725 return false;

726 }

727 else if (s == ' ')

728 {

729 if (!(c == '[' || IsInt(c)))

730 return false;

731 }

732 s = c;

733 counter++;

734 if (c == '[')

735 i++;

736 else if (c == ']')

737 i--;

738 if (i <= 0 && counter != program.Length) // stack count can't be zero unless it's the last character

739 return false;

740 }

742 // We should end with stack count of zero

743 if (i == 0)

744 return true;

745 else

746 return false;

747 }

749 public static bool IsInt(char c)

750 {

751 if (c == '0' ||

752 c == '1' ||

753 c == '2' ||

754 c == '3' ||

755 c == '4' ||

756 c == '5' ||

757 c == '6' ||

758 c == '7' ||

759 c == '8' ||

760 c == '9')

761 return true;

762 else

763 return false;

764 }

766 public static bool IsValidChar(char c)

767 {

768 if (c == ' ' ||

769 c == '[' ||

770 c == ']' ||

771 IsInt(c))

772 return true;

773 else

774 return false;

775 }

777 public static bool IsAtom(string program)

778 {

779 int i = 0;

780 if (int.TryParse(program, out i))

781 {

782 if (i >= 0)

783 return true;

784 }

785 return false;

786 }

788 public static bool IsAtom(Noun noun)

789 {

790 return IsAtom(noun.ToString());

791 }

793 public static bool IsCell(Noun noun)

794 {

795 return IsCell(noun.ToString());

796 }

798 public static Noun CreateNoun(string program)

799 {

800 if (IsAtom(program))

801 return new Atom(program);

802 else

803 return new Cell(program);

804 }

806 public static Noun CreateNoun(Noun n1, Noun n2)

807 {

808 return CreateNoun("[" + n1.ToString() + " " + n2.ToString() + "]");

809 }

811 public static Noun CreateNoun(string p1, Noun n2)

812 {

813 return CreateNoun("[" + p1 + " " + n2.ToString() + "]");

814 }

816 public static Noun CreateNoun(Noun n1, string p2)

817 {

818 return CreateNoun("[" + n1.ToString() + " " + p2 + "]");

819 }

821 public static Noun CreateNoun(string p1, string p2)

822 {

823 return CreateNoun("[" + p1 + " " + p2 + "]");

824 }

825 }

827 class Atom : Noun

828 {

829 public int value;

831 public override string ToString()

832 {

833 return value.ToString();

834 }

836 public Atom(string program)

837 {

838 if (IsAtom(program))

839 {

840 int i = 0;

841 bool result = int.TryParse(program, out i);

842 value = i;

843 }

844 else

845 throw new ArgumentException("Invalid Atom: " + program);

846 n1 = null;

847 n2 = null;

848 }

849 }

851 class Cell : Noun

852 {

853 public override string ToString()

854 {

855 return "[" + n1.ToString() + " " + n2.ToString() + "]";

856 }

858 public Cell(string program)

859 {

860 if (IsCell(program))

861 {

862 Tuple<string, string> split = SplitCell(program);

863 n1 = CreateNoun(split.Item1);

864 n2 = CreateNoun(split.Item2);

865 }

866 else

867 throw new ArgumentException("Invalid Cell: " + program);

868 }

869 }

871```

873## Groovy

875From [Kohányi Róbert](https://github.com/kohanyirobert/gnock/blob/master/gnock.groovy):

877```

878@Memoized

879def i(def a) {

880 a.class in [

881 byte, Byte,

882 char, Character,

883 short, Short,

884 int, Integer,

885 long, Long,

886 BigInteger

887 ] && a >= 0

890@Memoized

891def n(def a) {

892 def r

893 n(a, { r = it })

894 r

897@TailRecursive

898def n(def a, def r) {

899 if (a in List) {

900 if (a.size() == 1) {

901 r(a[0])

902 } else if (a.size() >= 2) {

903 n(a[0], { t ->

904 n(a.size() == 2 ? a[1] : a.tail(), { h ->

905 r([t, h])

906 })

907 })

908 } else {

909 throw new IllegalStateException()

910 }

911 } else if (i(a)) {

912 r((BigInteger) a)

913 } else {

914 throw new IllegalStateException()

915 }

918@Memoized

919def wut(def a) {

920 i(a) ? 1 : 0

923@Memoized

924def lus(def a) {

925 if (wut(a) == 0) {

926 throw new IllegalStateException()

927 }

928 1 + a

931@Memoized

932def tis(def a) {

933 if (wut(a) == 1) {

934 throw new IllegalStateException()

935 }

936 a[0] == a[1] ? 0 : 1

939@Memoized

940def fas(def a) {

941 def r

942 fas(a, { r = it })

943 r

946@TailRecursive

947def fas(def a, def r) {

948 if (wut(a) == 1) {

949 throw new IllegalStateException()

950 }

951 def h = a[0]

952 if (!i(h)) {

953 throw new IllegalStateException()

954 }

955 def t = a[1]

956 if (h == 0) {

957 throw new IllegalStateException()

958 } else if (h == 1) {

959 r(t)

960 } else {

961 if (i(t)) {

962 throw new IllegalStateException()

963 }

964 if (h == 2) {

965 r(t[0])

966 } else if (h == 3) {

967 r(t[1])

968 } else {

969 fas([h.intdiv(2), t], { p ->

970 fas([2 + h.mod(2), p], { q ->

971 r(q)

972 })

973 })

974 }

975 }

978@Memoized

979def tar(def a) {

980 def r

981 tar(a, { r = it})

982 r

985@TailRecursive

986def tar(def a, def r) {

987 if (wut(a) == 1) {

988 throw new IllegalStateException()

989 }

990 def s = a[0]

991 def f = a[1]

992 if (wut(f) == 1) {

993 throw new IllegalStateException()

994 }

995 def o = f[0]

996 def v = f[1]

997 if (wut(o) == 0) {

998 tar([s, o], { p ->

999 tar([s, v], { q ->

1000 r([p, q])

1001 })

1002 })

1003 } else {

1004 if (o == 0) {

1005 r(fas([v, s]))

1006 } else if (o == 1) {

1007 r(v)

1008 } else if (o == 3) {

1009 tar([s, v], {

1010 r(wut(it))

1011 })

1012 } else if (o == 4) {

1013 tar([s, v], {

1014 r(lus(it))

1015 })

1016 } else if (o == 5) {

1017 tar([s, v], {

1018 r(tis(it))

1019 })

1020 } else {

1021 if (wut(v) == 1) {

1022 throw new IllegalStateException()

1023 }

1024 def x = v[0]

1025 def y = v[1]

1026 if (o == 2) {

1027 tar([s, x], { p ->

1028 tar([s, y], { q ->

1029 tar([p, q], {

1030 r(it)

1031 })

1032 })

1033 })

1034 } else if (o == 7) {

1035 tar(n([s, 2, x, 1, y]), {

1036 r(it)

1037 })

1038 } else if (o == 8) {

1039 tar(n([s, 7, [[7, [0, 1], x], 0, 1], y]), {

1040 r(it)

1041 })

1042 } else if (o == 9) {

1043 tar(n([s, 7, y, 2, [0, 1], 0, x]), {

1044 r(it)

1045 })

1046 } else if (o == 10) {

1047 if (wut(x) == 1) {

1048 tar([s, y], {

1049 r(it)

1050 })

1051 } else {

1052 tar(n([s, 8, x[1], 7, [0, 3], y]), {

1053 r(it)

1054 })

1055 }

1056 } else {

1057 if (wut(y) == 1) {

1058 throw new IllegalStateException()

1059 }

1060 if (o == 6) {

1061 tar(n([s, 2, [0, 1], 2, [1, y[0], y[1]], [1, 0], 2, [1, 2, 3], [1, 0], 4, 4, x]), {

1062 r(it)

1063 })

1064 } else {

1065 throw new IllegalStateException()

1066 }

1067 }

1068 }

1073## Haskell

1075From [Steve Dee](https://github.com/mrdomino/hsnock/blob/master/Language/Nock5K/Spec.hs):

1078module Language.Nock5K.Spec where

1079import Control.Monad.Instances

1081wut (a :- b) = return $ Atom 0

1082wut a = return $ Atom 1

1084lus (a :- b) = Left "+[a b]"

1085lus (Atom a) = return $ Atom (1 + a)

1087tis (a :- a') | a == a' = return $ Atom 0

1088tis (a :- b) = return $ Atom 1

1089tis a = Left "=a"

1091fas (Atom 1 :- a) = return a

1092fas (Atom 2 :- a :- b) = return a

1093fas (Atom 3 :- a :- b) = return b

1094fas (Atom a :- b) | a > 3 = do x <- fas $ Atom (a `div` 2) :- b

1095 fas $ Atom (2 + (a `mod` 2)) :- x

1096fas a = Left "/a"

1098tar (a :- (b :- c) :- d) = do x <- tar (a :- b :- c)

1099 y <- tar (a :- d)

1100 return $ x :- y

1102tar (a :- Atom 0 :- b) = fas $ b :- a

1103tar (a :- Atom 1 :- b) = return b

1104tar (a :- Atom 2 :- b :- c) = do x <- tar (a :- b)

1105 y <- tar (a :- c)

1106 tar $ x :- y

1107tar (a :- Atom 3 :- b) = tar (a :- b) >>= wut

1108tar (a :- Atom 4 :- b) = tar (a :- b) >>= lus

1109tar (a :- Atom 5 :- b) = tar (a :- b) >>= tis

1111tar (a :- Atom 6 :- b :- c :- d) = tar (a :- Atom 2 :- (Atom 0 :- Atom 1) :-

1112 Atom 2 :- (Atom 1 :- c :- d) :-

1113 (Atom 1 :- Atom 0) :- Atom 2 :-

1114 (Atom 1 :- Atom 2 :- Atom 3) :-

1115 (Atom 1 :- Atom 0) :- Atom 4 :-

1116 Atom 4 :- b)

1117tar (a :- Atom 7 :- b :- c) = tar (a :- Atom 2 :- b :- Atom 1 :- c)

1118tar (a :- Atom 8 :- b :- c) = tar (a :- Atom 7 :-

1119 ((Atom 7 :- (Atom 0 :- Atom 1) :- b) :-

1120 Atom 0 :- Atom 1) :- c)

1121tar (a :- Atom 9 :- b :- c) = tar (a :- Atom 7 :- c :- Atom 2 :-

1122 (Atom 0 :- Atom 1) :- Atom 0 :- b)

1123tar (a :- Atom 10 :- (b :- c) :- d) = tar (a :- Atom 8 :- c :- Atom 7 :-

1124 (Atom 0 :- Atom 3) :- d)

1125tar (a :- Atom 10 :- b :- c) = tar (a :- c)

1127tar a = Left "*a"

1130## Hoon

1132```hoon

1133|= {sub/* fol/*}

1134^- *

1135?< ?=(@ fol)

1136?: ?=(^ -.fol)

1137 [$(fol -.fol) $(fol +.fol)]

1138?+ fol

1139 !!

1140 {$0 b/@}

1141 ?< =(0 b.fol)

1142 ?: =(1 b.fol) sub

1143 ?< ?=(@ sub)

1144 =+ [now=(cap b.fol) lat=(mas b.fol)]

1145 $(b.fol lat, sub ?:(=(2 now) -.sub +.sub))

1147 {$1 b/*}

1148 b.fol

1150 {$2 b/{^ *}}

1151 =+ ben=$(fol b.fol)

1152 $(sub -.ben, fol +.ben)

1154 {$3 b/*}

1155 =+ ben=$(fol b.fol)

1156 .?(ben)

1158 {$4 b/*}

1159 =+ ben=$(fol b.fol)

1160 ?> ?=(@ ben)

1161 +(ben)

1163 {$5 b/*}

1164 =+ ben=$(fol b.fol)

1165 ?> ?=(^ ben)

1166 =(-.ben +.ben)

1168 {$6 b/* c/* d/*}

1169 $(fol =>(fol [2 [0 1] 2 [1 c d] [1 0] 2 [1 2 3] [1 0] 4 4 b]))

1171 {$7 b/* c/*} $(fol =>(fol [2 b 1 c]))

1172 {$8 b/* c/*} $(fol =>(fol [7 [[7 [0 1] b] 0 1] c]))

1173 {$9 b/* c/*} $(fol =>(fol [7 c 2 [0 1] 0 b]))

1174 {$10 @ c/*} $(fol c.fol)

1175 {$10 {b/* c/*} d/*} =+($(fol c.fol) $(fol d.fol))

1179## JavaScript

1181From [Joe Bryan](https://github.com/joemfb/nock.js/blob/master/nock.js):

1183```js

1184(function (self, factory) {

1185 'use strict'

1187 if (typeof define === 'function' && define.amd) {

1188 define([], factory)

1189 } else if (typeof module === 'object' && typeof module.exports === 'object') {

1190 module.exports = factory()

1191 } else {

1192 self.nock = factory()

1194}(this, function () {

1195 'use strict'

1197 /**

1198 * Nock is a combinator interpreter on nouns. A noun is an atom or a cell.

1199 * An atom is an unsigned integer of any size; a cell is an ordered pair of nouns.

1200 *

1201 * @see http://urbit.org/docs/nock/definition/

1202 * @see https://media.urbit.org/whitepaper.pdf

1203 */

1205 var useMacros = false

1207 /*

1208 * code conventions:

1209 *

1210 * `n` is a noun,

1211 * `s` is a subject noun,

1212 * `f` is a formula (or cell of formulas)

1213 */

1215 /* operators */

1217 /**

1218 * wut (?): test for atom (1) or cell (0)

1219 *

1220 * ?[a b] 0

1221 * ?a 1

1222 */

1223 function wut (n) {

1224 return typeof n === 'number' ? 1 : 0

1227 /**

1228 * lus (+): increment an atom

1229 *

1230 * +[a b] +[a b]

1231 * +a 1 + a

1232 */

1233 function lus (n) {

1234 if (wut(n) === 0) throw new Error('lus cell')

1235 return 1 + n

1238 /**

1239 * tis (=): test equality

1240 *

1241 * =[a a] 0

1242 * =[a b] 1

1243 * =a =a

1244 */

1245 function tis (n) {

1246 if (wut(n) === 1) throw new Error('tis atom')

1247 return deepEqual(n[0], n[1]) ? 0 : 1

1250 /**

1251 * fas (/): resolve a tree address

1252 *

1253 * /[1 a] a

1254 * /[2 a b] a

1255 * /[3 a b] b

1256 * /[(a + a) b] /[2 /[a b]]

1257 * /[(a + a + 1) b] /[3 /[a b]]

1258 * /a /a

1259 */

1260 function fas (addr, n) {

1261 if (n === undefined) throw new Error('invalid fas noun')

1262 if (addr === 0) throw new Error('invalid fas addr: 0')

1264 if (addr === 1) return n

1265 if (addr === 2) return n[0]

1266 if (addr === 3) return n[1]

1268 return fas(2 + (addr % 2), fas((addr / 2) | 0, n))

1271 /* formulas */

1273 /**

1274 * slot (0): resolve a tree address

1275 *

1276 * *[a 0 b] /[b a]

1277 */

1278 function slot (s, f) {

1279 var p = fas(f, s)

1281 if (p === undefined) throw new Error('invalid fas addr: ' + f)

1283 return p

1286 /**

1287 * constant (1): return the formula regardless of subject

1288 *

1289 * *[a 1 b] b

1290 */

1291 function constant (s, f) {

1292 return f

1295 /**

1296 * evaluate (2): evaluate the product of second formula against the product of the first

1297 *

1298 * *[a 2 b c] *[*[a b] *[a c]]

1299 */

1300 function evaluate (s, f) {

1301 return nock(nock(s, f[0]), nock(s, f[1]))

1304 /**

1305 * cell (3): test if the product is a cell

1306 *

1307 * *[a 3 b] ?*[a b]

1308 */

1309 function cell (s, f) {

1310 return wut(nock(s, f))

1313 /**

1314 * incr (4): increment the product

1315 *

1316 * *[a 4 b] +*[a b]

1317 */

1318 function incr (s, f) {

1319 return lus(nock(s, f))

1322 /**

1323 * eq (5): test for equality between nouns in the product

1324 *

1325 * *[a 5 b] =*[a b]

1326 */

1327 function eq (s, f) {

1328 return tis(nock(s, f))

1331 /* macro-formulas */

1333 /**

1334 * ife (6): if/then/else

1335 *

1336 * *[a 6 b c d] *[a 2 [0 1] 2 [1 c d] [1 0] 2 [1 2 3] [1 0] 4 4 b]

1337 */

1338 function macroIfe (s, f) {

1339 return nock(s, [2, [[0, 1], [2, [[1, [f[1][0], f[1][1]]], [[1, 0], [2, [[1, [2, 3]], [[1, 0], [4, [4, f[0]]]]]]]]]]])

1342 function ife (s, f) {

1343 var cond = nock(s, f[0])

1345 if (cond === 0) return nock(s, f[1][0])

1346 if (cond === 1) return nock(s, f[1][1])

1348 throw new Error('invalid ife conditional')

1351 /**

1352 * compose (7): evaluate formulas composed left-to-right

1353 *

1354 * *[a 7 b c] *[a 2 b 1 c]

1355 */

1356 function macroCompose (s, f) {

1357 return nock(s, [2, [f[0], [1, f[1]]]])

1360 function compose (s, f) {

1361 // alternate form:

1362 // return nock(nock(s, f[0]), constant(s, f[1]))

1363 return nock(nock(s, f[0]), f[1])

1366 /**

1367 * extend (8): evaluate the second formula against [product of first, subject]

1368 *

1369 * *[a 8 b c] *[a 7 [[7 [0 1] b] 0 1] c]

1370 */

1371 function macroExtend (s, f) {

1372 return nock(s, [7, [[[7, [[0, 1], f[0]]], [0, 1]], f[1]]])

1375 function extend (s, f) {

1376 // alternate form:

1377 // return nock([compose(s, [[0, 1], f[0]]), s], f[1])

1378 return nock([nock(s, f[0]), s], f[1])

1381 /**

1382 * invoke (9): construct a core and evaluate one of it's arms against it

1383 *

1384 * *[a 9 b c] *[a 7 c 2 [0 1] 0 b]

1385 */

1386 function macroInvoke (s, f) {

1387 return nock(s, [7, [f[1], [2, [[0, 1], [0, f[0]]]]]])

1390 function invoke (s, f) {

1391 var prod = nock(s, f[1])

1392 return nock(prod, slot(prod, f[0]))

1395 /**

1396 * hint (10): skip first formula, evaluate second

1397 *

1398 * *[a 10 [b c] d] *[a 8 c 7 [0 3] d]

1399 * *[a 10 b c] *[a c]

1400 */

1401 function macroHint (s, f) {

1402 if (wut(f[0]) === 0) return nock(s, [8, [f[0][1], [7, [[0, 3], f[1]]]]])

1403 return nock(s, f[1])

1406 function hint (s, f) {

1407 if (wut(f[0]) === 0) {

1408 if (wut(f[0][1]) === 1) throw new Error('invalid hint')

1409 nock(s, f[0][1])

1410 }

1411 return nock(s, f[1])

1414 /* indexed formula functions */

1415 var macroFormulas = [slot, constant, evaluate, cell, incr, eq, macroIfe, macroCompose, macroExtend, macroInvoke, macroHint]

1416 var formulas = [slot, constant, evaluate, cell, incr, eq, ife, compose, extend, invoke, hint]

1418 /**

1419 * nock (*)

1420 *

1421 * the nock function

1422 *

1423 * *[a [b c] d] [*[a b c] *[a d]]

1424 * *a *a

1425 */

1426 function nock (s, f) {

1427 if (wut(f[0]) === 0) return [nock(s, f[0]), nock(s, f[1])]

1429 var idx = f[0]

1431 if (idx > 10) throw new Error('invalid formula: ' + idx)

1433 if (useMacros) return macroFormulas[idx](s, f[1])

1435 return formulas[idx](s, f[1])

1438 /* construct a JS noun (group an array into pairs, associating right) */

1439 function assoc (x) {

1440 if (!x.length) return x

1442 if (x.length === 1) return assoc(x[0])

1444 return [assoc(x[0]), assoc(x.slice(1))]

1447 /* deep equality for arrays or primitives */

1448 function deepEqual (a, b) {

1449 if (a === b) return true

1451 if (!(Array.isArray(a) && Array.isArray(b))) return false

1452 if (a.length !== b.length) return false

1454 for (var i = 0; i < a.length; i++) {

1455 if (!deepEqual(a[i], b[i])) return false

1456 }

1458 return true

1461 /* parse a hoon-serialized nock formula and construct a JS noun */

1462 function parseNoun (x) {

1463 if (Array.isArray(x)) return assoc(x)

1465 if (typeof x === 'string') {

1466 var str = x.replace(/[\."']/g, '').split(' ').join(',')

1467 return assoc(JSON.parse(str))

1468 }

1470 return x

1473 function nockInterface () {

1474 var args = [].slice.call(arguments)

1475 var subject, formula, noun

1477 if (args.length === 1) {

1478 formula = parseNoun(args[0])

1479 } else if (args.length === 2) {

1480 subject = parseNoun(args[0])

1481 formula = parseNoun(args[1])

1482 } else {

1483 noun = assoc(args)

1484 subject = noun[0]

1485 formula = noun[1]

1486 }

1488 if (!formula) throw new Error('formula required')

1490 if (!subject) {

1491 // !=(~)

1492 subject = [1, 0]

1493 }

1495 return nock(subject, formula)

1498 return {

1499 nock: nockInterface,

1500 _nock: nock,

1501 useMacros: function (arg) {

1502 useMacros = arg === undefined || arg

1503 return this

1504 },

1505 util: {

1506 assoc: assoc,

1507 parseNoun: parseNoun,

1508 deepEqual: deepEqual

1509 },

1510 operators: {

1511 wut: wut,

1512 lus: lus,

1513 tis: tis,

1514 fas: fas

1515 },

1516 formulas: {

1517 slot: slot,

1518 constant: constant,

1519 evaluate: evaluate,

1520 cell: cell,

1521 incr: incr,

1522 eq: eq,

1523 macroIfe: macroIfe,

1524 ife: ife,

1525 macroCompose: macroCompose,

1526 compose: compose,

1527 macroExtend: macroExtend,

1528 extend: extend,

1529 macroInvoke: macroInvoke,

1530 invoke: invoke,

1531 macroHint: macroHint,

1532 hint: hint

1533 }

1538## Python

1540From [James Tauber](https://github.com/jtauber/pynock/blob/master/nock.py):

1542```py

1543#!/usr/bin/env python3

1545# []

1546def l(*lst):

1547 if len(lst) == 1:

1548 return(lst[0], 0)

1549 if len(lst) == 2:

1550 return lst

1551 else:

1552 return (lst[0], l(*lst[1:]))

1555def nock(noun):

1556 return tar(noun)

1559def wut(noun):

1560 if isinstance(noun, int):

1561 return 1

1562 else:

1563 return 0

1567def lus(noun):

1568 if isinstance(noun, int):

1569 return 1 + noun

1570 else:

1571 return noun

1575def tis(noun):

1576 if noun[0] == noun[1]:

1577 return 0

1578 else:

1579 return 1

1583def slot(noun):

1584 if noun[0] == 1:

1585 return noun[1]

1586 elif noun[0] == 2:

1587 return noun[1][0]

1588 elif noun[0] == 3:

1589 return noun[1][1]

1590 elif noun[0] % 2 == 0:

1591 return slot((2, slot((noun[0] // 2, noun[1]))))

1592 elif noun[0] % 2 == 1:

1593 return slot((3, slot(((noun[0] - 1) // 2, noun[1]))))

1596def tar(noun):

1597 if isinstance(noun[1][0], int):

1598 if noun[1][0] == 0:

1599 return slot((noun[1][1], noun[0]))

1600 elif noun[1][0] == 1:

1601 return noun[1][1]

1602 elif noun[1][0] == 2:

1603 return nock((nock((noun[0], noun[1][1][0])), nock((noun[0], noun[1][1][1]))))

1604 elif noun[1][0] == 3:

1605 return wut(nock((noun[0], noun[1][1])))

1606 elif noun[1][0] == 4:

1607 return lus(nock((noun[0], noun[1][1])))

1608 elif noun[1][0] == 5:

1609 return tis(nock((noun[0], noun[1][1])))

1610 elif noun[1][0] == 6:

1611 return nock(l(noun[0], 2, (0, 1), 2, l(1, noun[1][1][1][0], noun[1][1][1][1]), (1, 0), 2, l(1, 2, 3), (1, 0), 4, 4, noun[1][1][0]))

1612 elif noun[1][0] == 7:

1613 return nock(l(noun[0], 2, noun[1][1][0], 1, noun[1][1][1]))

1614 elif noun[1][0] == 8:

1615 return nock(l(noun[0], 7, l(l(7, (0, 1), noun[1][1][0]), 0, 1), noun[1][1][1]))

1616 elif noun[1][0] == 9:

1617 return nock(l(noun[0], 7, noun[1][1][1], l(2, (0, 1), (0, noun[1][1][0]))))

1618 elif noun[1][0] == 10:

1619 if isinstance(noun[1][1][0], int):

1620 return nock((noun[0], noun[1][1][1]))

1621 else:

1622 return nock(l(noun[0], 8, noun[1][1][0][1], 7, (0, 3), noun[1][1][1][0]))

1623 else:

1624 return (nock((noun[0], noun[1][0])), nock((noun[0], noun[1][1])))

1627## Ruby

1629From [T.J. Corcoran](https://github.com/TJamesCorcoran/nock/blob/master/nock.rb):

1631```ruby

1632def str_to_tree(str)

1633 arr = []

1634 str.scan(/\+|\=|\?|\/|\*|\[|\]|\d+/).each do |token|

1635 end

1638def max_depth(arr)

1639 ret = arr.is_a?(Array) ? [max_depth(arr[0]), max_depth(arr[1])].max + 1 : 1

1640 ret

1643def pp(arr)

1644 depth = max_depth(arr)

1645 space = 128

1646 1.up_to(8) do |depth|

1647 space = space / 2

1648 min = 2 ** (depth - 1)

1649 max = (2 ** depth) - 1

1650 min.upto(max) { |axis|

1651 end

1655def norm(arr)

1656 return arr unless arr.is_a?(Array)

1657 while arr.size > 2

1658 size = arr.size

1659 arr[size - 2] = [ arr[size - 2], arr.pop ]

1660 end

1661 arr = arr.map { |x| norm(x) }

1664def wut(arr)

1665 arr.is_a?(Array) ? YES : NO

1668def lus(atom)

1669 raise "not an atom" unless atom.is_a?(Fixnum)

1670 atom + 1

1673def tis(arr)

1674 raise "not pair" unless arr.is_a?(Array) && arr.size == 2

1675 ( arr[0] == arr[1] ) ? YES : NO

1678def slot(axis, arr, allow_error = true)

1679 raise "axis on atom" unless arr.is_a?(Array)

1680 return arr if axis == 1

1681 return arr[0] if axis == 2

1682 return arr[1] if axis == 3

1683 return slot(2, slot(axis/2, arr)) if (axis %2) == 0

1684 return slot(3, slot(axis/2, arr))

1688def nock(arr)

1689 raise "error: nocking an atom" unless arr.is_a?(Array)

1691 oper = slot(4, arr)

1692 a = slot(2, arr)

1693 b = slot(5, arr)

1695 if oper.is_a?(Array)

1696 return [ nock( [ a, [b, c]]), nock( [a, d]) ]

1697 end

1700 case oper

1701 when 0 then

1702 slot(b,a )

1704 when 1 then

1705 b

1707 when 2 then

1708 b_prime = slot(2, b)

1709 c = slot(3,b)

1710 nock( [ nock([a, b_primce]), nock([a, c]) ])

1712 when 3 then

1713 wut(nock([a, b]))

1715 when 4 then

1716 lus(nock([a, b]))

1718 when 5 then

1719 tis(nock([a, b]))

1721 when 6 then

1722 b_prime = slot(2, b)

1723 c = slot(6,b)

1724 d = slot(7,b)

1725 nock( norm([a, 2, [0, 1], 2, [1, c, d], [1, 0], 2, [1, 2, 3], [1, 0], 4, 4, b]) )

1727 when 7 then

1728 b_prime = slot(2, b)

1729 c = slot(3,b)

1730 nock( norm ([a, 2, b_prime, 1, c]))

1732 when 8 then

1733 b_prime = slot(2, b)

1734 c = slot(3,b)

1735 nock( norm ([a, 7, [[7, [0, 1], b_prime], 0, 1], c]))

1737 when 9 then

1738 b_prime = slot(2, b)

1739 c = slot(3,b)

1740 nock( norm ([a, 7, c, 2, [0, 1], 0, b_prime]))

1742 when 10 then

1743 if wut(slot(2,b)) == TRUE

1744 b_prime = slot(4, b)

1745 c = slot(5, b)

1746 d = slot(3, b)

1747 c = slot(3,b)

1748 nock( norm ([a, 8, c, 7, [0, 3], d]))

1749 else

1750 b_prime = slot(2, b)

1751 c = slot(3, b)

1752 nock( norm ([a, 10, [b, c]]))

1753 end

1754 else

1755 raise "error: unknown opcode #{oper.inspect}"

1756 end

1760## Scala

1762From [Steve Randy Waldman](https://github.com/swaldman/nnnock/blob/master/src/main/scala/com/mchange/sc/v1/nnnock/package.scala):

1764```scala

1765package object nnnock {

1767 sealed trait Noun;

1768 case class Atom( value : Int ) extends Noun;

1769 case class Cell( head : Noun, tail : Noun ) extends Noun;

1770 implicit def toAtom( value : Int ) : Atom = Atom( value );

1771 implicit def toInt( atom : Atom ) : Int = atom.value;

1773 def nock( a : Noun ) : Noun = *(a)

1776 object Cell {

1777 private def apply( nl : List[Noun] ) : Cell = {

1778 nl match {

1779 case a :: b :: Nil => Cell(a, b);

1780 case a :: b :: c :: Nil => Cell(a, Cell(b, c));

1781 case a :: b :: c :: tail => Cell(a, this.apply( b :: c :: tail ) );

1782 }

1783 }

1784 def apply(a : Noun, b : Noun, tail : Noun*) : Cell = apply( a :: b :: tail.toList );

1787 def ?( noun : Noun ) : Noun = noun match {

1788 case _ : Cell => 0;

1789 case _ : Atom => 1;

1792 @tailrec def plus( noun : Noun ) : Noun = noun match {

1793 case a : Atom => 1 + a;

1794 case c : Cell => plus( c ); //intentional endless spin

1797 def heq( noun : Noun ) : Atom = noun match {

1798 case Cell( a : Atom, b : Atom ) => if ( a == b ) 0 else 1;

1799 case Cell( a : Cell, b : Atom ) => 1;

1800 case Cell( a : Atom, b : Cell ) => 1;

1801 case Cell( a : Cell, b : Cell ) => if ((heq( Cell( a.head, b.head ) ) | heq( Cell( a.tail, b.tail ) )) == 0) 0 else 1;

1802 case a : Atom => heq( a ); //intentional endless spin

1805 def /( noun : Noun ) : Noun = noun match {

1806 case Cell(Atom(1), a) => a;

1807 case Cell(Atom(2), Cell(a, b)) => a;

1808 case Cell(Atom(3), Cell(a, b)) => b;

1809 case Cell(Atom(value), b ) => {

1810 val a = value / 2;

1811 val num = if ( value % a == 0 ) 2 else 3;

1812 /(Cell(num, /(Cell(a, b))));

1813 }

1814 case a => /( a ); //intentional endless spin

1818 def *( noun : Noun ) : Noun = noun match {

1819 case Cell( a, Cell(Cell(b, c), d) ) => Cell( *(Cell(a,b,c)), *(Cell(a,d)) );

1820 case Cell( a, Cell(Atom(value), tail) ) => {

1821 (value, tail) match {

1822 case (0, b) => /( Cell(b, a) );

1823 case (1, b) => b;

1824 case (2, Cell(b, c)) => *( Cell( *( Cell(a,b) ), *( Cell(a,c) ) ) );

1825 case (3, b) => ?( *( Cell(a,b) ) );

1826 case (4, b) => plus( *( Cell(a,b) ) );

1827 case (5, b) => heq( *( Cell(a,b) ) );

1828 case (6, Cell(b, Cell(c, d))) => *( Cell(a,2,Cell(0,1),2,Cell(1,c,d),Cell(1,0),2,Cell(1,2,3),Cell(1,0),4,4,b) ); //wtf?

1829 case (7, Cell(b, c)) => *( Cell(a,2,b,1,c) );

1830 case (8, Cell(b, c)) => *( Cell(a,7,Cell(Cell(7,Cell(0,1),b),0,1),c) ); //wtf2

1831 case (9, Cell(b, c)) => *( Cell(a,7,c,2,Cell(0,1),0,b) );

1832 case (10, Cell(Cell(b,c),d)) => *( Cell(a,8,c,7,Cell(0,3),d) );

1833 case (10, Cell(b, c)) => *( Cell(a,c) );

1834 case _ => *( noun ); //intentional endless spin

1835 }

1836 }

1837 case a => *( a ); //intentional endless spin

1838 }

1842## Scheme

1844From [Kohányi Róbert](https://github.com/kohanyirobert/snock/blob/master/snock.ss):

1846```scheme

1847(import (rnrs (6)))

1849(define (i a) a)

1851(define (n a r)

1852 (cond

1853 ((list? a)

1854 (let ((l (length a)))

1855 (cond

1856 ((equal? l 0) (raise 1))

1857 ((equal? l 1) (r (car a)))

1858 (else

1859 (let ((t (cond

1860 ((equal? l 2) (cadr a))

1861 (else (cdr a)))))

1862 (n (car a)

1863 (lambda (p) (n t

1864 (lambda (q) (r (cons p q)))))))))))

1865 ((fixnum? a) (r a))

1866 (else (raise 2))))

1868(define (wut a)

1869 (cond

1870 ((fixnum? a) 1)

1871 (else 0)))

1873(define (lus a)

1874 (cond

1875 ((equal? (wut a) 0) (raise 3))

1876 (else (+ 1 a))))

1878(define (tis a)

1879 (cond

1880 ((equal? (wut a) 1) (raise 4))

1881 ((equal? (car a) (cdr a)) 0)

1882 (else 1)))

1884(define (fas a r)

1885 (cond

1886 ((equal? (wut a) 1) (raise 5))

1887 (else

1888 (let ((h (car a))

1889 (t (cdr a)))

1890 (cond

1891 ((not (fixnum? h)) (raise 6))

1892 ((equal? h 0) (raise 7))

1893 ((equal? h 1) (r t))

1894 ((fixnum? t) (raise 8))

1895 ((equal? h 2) (r (car t)))

1896 ((equal? h 3) (r (cdr t)))

1897 (else

1898 (fas (cons (div h 2) t)

1899 (lambda (p) (fas (cons (+ 2 (mod h 2)) p)

1900 (lambda (q) (r q)))))))))))

1902(define (tar a r)

1903 (cond

1904 ((equal? (wut a) 1) (raise 9))

1905 (else

1906 (let ((s (car a))

1907 (f (cdr a)))

1908 (cond

1909 ((equal? (wut f) 1) (raise 10))

1910 (else

1911 (let ((o (car f))

1912 (v (cdr f)))

1913 (cond

1914 ((equal? (wut o) 0) (tar (cons s o)

1915 (lambda (p) (tar (cons s v)

1916 (lambda (q) (r (cons p q)))))))

1917 ((equal? o 0) (r (fas (cons v s) i)))

1918 ((equal? o 1) (r v))

1919 ((equal? o 3) (tar (cons s v)

1920 (lambda (p) (r (wut p)))))

1921 ((equal? o 4) (tar (cons s v)

1922 (lambda (p) (r (lus p)))))

1923 ((equal? o 5) (tar (cons s v)

1924 (lambda (p) (r (tis p)))))

1925 ((equal? (wut v) 1) (raise 11))

1926 (else

1927 (let ((x (car v))

1928 (y (cdr v)))

1929 (cond

1930 ((equal? o 2) (tar (cons s x)

1931 (lambda (p) (tar (cons s y)

1932 (lambda (q) (tar (cons p q)

1933 (lambda (u) (r u))))))))

1934 ((equal? o 7) (tar (n (list (list s) 2 (list x) 1 (list y)) i)

1935 (lambda (p) (r p))))

1936 ((equal? o 8) (tar (n (list (list s) 7 (list (list 7 (list 0 1) (list x)) 0 1) (list y)) i)

1937 (lambda (p) (r p))))

1938 ((equal? o 9) (tar (n (list (list s) 7 (list y) 2 (list 0 1) 0 (list x)) i)

1939 (lambda (p) (r p))))

1940 ((equal? o 10) (cond

1941 ((equal? (wut x) 1) (tar (cons s y)

1942 (lambda (p) (r p))))

1943 (else (tar (n (list (list s) 8 (list (cdr x)) 7 (list 0 3) (list y)) i)

1944 (lambda (p) (r p))))))

1945 ((equal? (wut y) 1) (raise 12))

1946 ((equal? o 6) (tar (n (list

1947 (list s)

1948 2

1949 (list 0 1)

1950 2

1951 (list 1 (list (car y)) (list (cdr y)))

1952 (list 1 0)

1953 2

1954 (list 1 2 3)

1955 (list 1 0)

1956 4

1957 4

1958 (list x))

1959 i)

1960 (lambda (p) (r p))))

1961 (else (raise 13)))))))))))))

1964## Swift

1966```swift

1967import Foundation

1968// 1 :: A noun is an atom or a cell.

1969// 2 :: An atom is a natural number.

1970// 3 :: A cell is an ordered pair of nouns.

1971// 4

1972// 5 :: nock(a) *a

1973// 6 :: [a b c] [a [b c]]

1974// 7

1975// 8 :: ?[a b] 0

1976// 9 :: ?a 1

1977// 10 :: +[a b] +[a b]

1978// 11 :: +a 1 + a

1979// 12 :: =[a a] 0

1980// 13 :: =[a b] 1

1981// 14 :: =a =a

1982// 15

1983// 16 :: /[1 a] a

1984// 17 :: /[2 a b] a

1985// 18 :: /[3 a b] b

1986// 19 :: /[(a + a) b] /[2 /[a b]]

1987// 20 :: /[(a + a + 1) b] /[3 /[a b]]

1988// 21 :: /a /a

1989// 22

1990// 23 :: *[a [b c] d] [*[a b c] *[a d]]

1991// 24

1992// 25 :: *[a 0 b] /[b a]

1993// 26 :: *[a 1 b] b

1994// 27 :: *[a 2 b c] *[*[a b] *[a c]]

1995// 28 :: *[a 3 b] ?*[a b]

1996// 29 :: *[a 4 b] +*[a b]

1997// 30 :: *[a 5 b] =*[a b]

1998// 31

1999// 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]

2000// 33 :: *[a 7 b c] *[a 2 b 1 c]

2001// 34 :: *[a 8 b c] *[a 7 [[7 [0 1] b] 0 1] c]

2002// 35 :: *[a 9 b c] *[a 7 c 2 [0 1] 0 b]

2003// 36 :: *[a 10 [b c] d] *[a 8 c 7 [0 3] d]

2004// 37 :: *[a 10 b c] *[a c]

2005// 38

2006// 39 :: *a *a

2008// 1 :: A noun is an atom or a cell.

2009public indirect enum Noun: IntegerLiteralConvertible, ArrayLiteralConvertible, Equatable, Hashable, CustomStringConvertible

2011 // 2 :: An atom is a natural number.

2012 public typealias ATOM = UIntMax

2014 case Atom(ATOM)

2015 // 3 :: A cell is an ordered pair of nouns.

2016 case Cell(Noun, Noun)

2017 case Invalid

2019 public static var YES: Noun { return .Atom(0) }

2020 public static var NO: Noun { return .Atom(1) }

2022 public init(_ noun: Noun) { self = noun }

2024 // 6 :: [a b c] [a [b c]]

2025 public init(_ nouns: [Noun]) {

2026 self = .Invalid

2027 if nouns.count > 0 {

2028 var reverse = nouns.reverse().generate()

2029 self = reverse.next()!

2030 while let n = reverse.next() {

2031 self = .Cell(n, self)

2032 }

2033 }

2034 }

2036 // protocol IntegerLiteralConvertible

2037 public typealias IntegerLiteralType = ATOM

2038 public init(integerLiteral value: IntegerLiteralType) {

2039 self = .Atom(value)

2040 }

2042 // protocol ArrayLiteralConvertible

2043 public typealias Element = Noun

2044 public init(arrayLiteral elements: Element...) {

2045 self = Noun(elements)

2046 }

2048 // Array subscript

2049 public subscript(axis: ATOM) -> Noun {

2050 return fas(.Cell(.Atom(axis), self))

2051 }

2053 // protocol Hashable

2054 public var hashValue: Int {

2055 //return self.description.hashValue

2056 switch self {

2057 case let .Atom(a):

2058 return a.hashValue

2059 case let .Cell(a, b):

2060 return (5381 + 31 &* a.hashValue) &+ b.hashValue

2061 default:

2062 abort()

2063 }

2064 }

2066 // protocol CustomStringConvertible

2067 public var description: String {

2068 return describe()

2069 }

2071 private func describe(depth: Int = 0) -> String {

2072 var sub = ""

2073 let next = depth+1

2074 switch self {

2075 case .Invalid:

2076 return "[%INVALID%]"

2077 case let .Atom(atom):

2078 return "\(atom)"

2079 case let .Cell(.Cell(a, b), c):

2080 sub = "[\(a.describe(next)) \(b.describe(next))] \(c.describe(next))"

2081 case let .Cell(a, b):

2082 sub = "\(a.describe(next)) \(b.describe(next))"

2083 }

2084 return depth == 0 ? "[\(sub)]" : sub

2085 }

2088// protocol Equatable

2089public func == (left: Noun, right: Noun) -> Bool

2091 switch (left, right) {

2092 case let (.Atom(lhs), .Atom(rhs)): return lhs == rhs

2093 case let (.Cell(lp, lq), .Cell(rp, rq)): return lp == rp && lq == rq

2094 case (.Invalid, .Invalid): return true

2095 default: return false

2096 }

2099public func wut(noun: Noun) -> Noun

2101 switch noun {

2102 // 8 :: ?[a b] 0

2103 case .Cell:

2104 return Noun.YES

2105 case .Atom:

2106 // 9 :: ?a 1

2107 return Noun.NO

2108 default:

2109 //return wut(noun)

2110 abort()

2111 }

2114public func lus(noun: Noun) -> Noun

2116 if case let .Atom(a) = noun {

2117 // 11 :: +a 1 + a

2118 return .Atom(1+a)

2119 }

2120 // 10 :: +[a b] +[a b]

2121 //return lus(noun)

2122 abort()

2125public func tis(noun: Noun) -> Noun

2127 if case let .Cell(a, b) = noun {

2128 // 12 :: =[a a] 0

2129 // 13 :: =[a b] 1

2130 return (a == b) ? Noun.YES : Noun.NO

2131 }

2132 // 14 :: =a =a

2133 //return tis(noun)

2134 abort()

2137public func fas(noun: Noun) -> Noun

2139 switch noun {

2140 // 16 :: /[1 a] a

2141 case let .Cell(1, a):

2142 return a

2143 // 17 :: /[2 a b] a

2144 case let .Cell(2, .Cell(a, _)):

2145 return a

2146 // 18 :: /[3 a b] b

2147 case let .Cell(3, .Cell(_, b)):

2148 return b

2149 // 19 :: /[(a + a) b] /[2 /[a b]]

2150 // 20 :: /[(a + a + 1) b] /[3 /[a b]]

2151 case let .Cell(.Atom(axis), tree):

2152 let inner = Noun.Atom(axis / 2)

2153 let outer = Noun.Atom(2 + (axis % 2))

2154 return fas(.Cell(outer, fas(.Cell(inner, tree))))

2155 default:

2156 // 21 :: /a /a

2157 //return fas(noun)

2158 abort()

2159 }

2162public func tar(noun: Noun) -> Noun

2164 switch noun {

2165 case let .Cell(a, formula):

2166 switch formula {

2167 // 23 :: *[a [b c] d] [*[a b c] *[a d]]

2168 case let .Cell(.Cell(b, c), d):

2169 return .Cell(tar([a, b, c]), tar([a, d]))

2171 // 25 :: *[a 0 b] /[b a]

2172 case let .Cell(0, b):

2173 return fas([b, a])

2175 // 26 :: *[a 1 b] b

2176 case let .Cell(1, b):

2177 return b

2179 // 27 :: *[a 2 b c] *[*[a b] *[a c]]

2180 case let .Cell(2, .Cell(b, c)):

2181 return tar([tar([a, b]), tar([a, c])])

2183 // 28 :: *[a 3 b] ?*[a b]

2184 case let .Cell(3, b):

2185 return wut(tar([a, b]))

2187 // 29 :: *[a 4 b] +*[a b]

2188 case let .Cell(4, b):

2189 return lus(tar([a, b]))

2191 // 30 :: *[a 5 b] =*[a b]

2192 case let .Cell(5, b):

2193 return tis(tar([a, b]))

2195 // 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]

2196 case let .Cell(6, .Cell(b, .Cell(c, d))):

2197 return tar([a, 2, [0, 1], 2, [1, c, d], [1, 0], 2, [1, 2, 3], [1, 0], 4, 4, b])

2199 // 33 :: *[a 7 b c] *[a 2 b 1 c]

2200 case let .Cell(7, .Cell(b, c)):

2201 return tar([a, 2, b, 1, c])

2203 // 34 :: *[a 8 b c] *[a 7 [[7 [0 1] b] 0 1] c]

2204 case let .Cell(8, .Cell(b, c)):

2205 return tar([a, 7, [[7, [0, 1], b], 0, 1], c])

2207 // 35 :: *[a 9 b c] *[a 7 c 2 [0 1] 0 b]

2208 case let .Cell(9, .Cell(b, c)):

2209 return tar([a, 7, c, 2, [0, 1], 0, b])

2211 // 36 :: *[a 10 [b c] d] *[a 8 c 7 [0 3] d]

2212 case let .Cell(10, .Cell(.Cell(_, c), d)):

2213 return tar([a, 8, c, 7, [0, 3], d])

2215 // 37 :: *[a 10 b c] *[a c]

2216 case let .Cell(10, .Cell(_, c)):

2217 return tar([a, c]);

2219 default:

2220 //return tar(noun)

2221 abort()

2222 }

2223 default:

2224 //return tar(noun)

2225 abort()

2226 }

2230public var nock_functions = Dictionary<Noun, Noun -> Noun>()

2232public func dao(formula: Noun) -> Noun->Noun

2234 if let cached = nock_functions[formula] {

2235 return cached

2236 }

2238 let compiler = { () -> Noun -> Noun in

2239 switch formula {

2240 case let .Cell(.Cell(b, c), d): // Distribution

2241 let (p, q) = (dao(.Cell(b, c)), dao(d))

2242 return { a in .Cell(p(a), q(a)) }

2244 case let .Cell(0, b): // Axis

2245 return { a in fas(.Cell(b, a)) }

2247 case let .Cell(1, b): // Just

2248 return { _ in b }

2250 case let .Cell(2, .Cell(b, c)): // Fire

2251 let (f, g) = (dao(b), dao(c))

2252 return { a in dao(g(a))(f(a)) }

2254 case let .Cell(3, b): // Depth

2255 let f = dao(b)

2256 return { a in wut(f(a)) }

2258 case let .Cell(4, b): // Bump

2259 let f = dao(b)

2260 return { a in lus(f(a)) }

2262 case let .Cell(5, b): // Same

2263 let f = dao(b)

2264 return { a in tis(f(a)) }

2266 case let .Cell(6, .Cell(b, .Cell(c, d))): // If

2267 let (p, q, r) = (dao(b), dao(c), dao(d))

2268 return { a in

2269 switch p(a) {

2270 case Noun.self.YES:

2271 return q(a)

2272 case Noun.self.NO:

2273 return r(a)

2274 default:

2275 return tar(.Cell(a, formula))

2276 }

2277 }

2279 case let .Cell(7, .Cell(b, c)): // Compose

2280 let (f, g) = (dao(b), dao(c))

2281 return { a in g(f(a)) }

2283 case let .Cell(8, .Cell(b, c)): // Push

2284 let (f, g) = (dao(b), dao(c))

2285 return { a in g(.Cell(f(a), a)) }

2287 case let .Cell(9, .Cell(b, c)): // Call

2288 let f = dao(c)

2289 return { a in

2290 let core = f(a)

2291 let arm = dao(fas(.Cell(b, core)))

2292 return arm(core)

2293 }

2295 case let .Cell(10, .Cell(.Cell(_, c), d)): // Hint

2296 let ignore = dao(c)

2297 let f = dao(d)

2298 return { a in ignore(a); return f(a) }

2300 case let .Cell(10, .Cell(_, c)): // Hint

2301 let f = dao(c)

2302 return { a in f(a) }

2304 default:

2305 return { a in tar(.Cell(a, formula)) }

2306 }

2307 }

2309 let r = compiler()

2310 nock_functions[formula] = r

2311 return r

2314public func nock(n: Noun) -> Noun

2316 if case let .Cell(a, b) = n {

2317 let f = dao(b)

2318 return f(a)

2319 }

2320 return nock(n)