{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "941f6882-7137-4088-9057-c21c30ab0ab5",
   "metadata": {},
   "source": [
    "### Transformation to a Register Machine"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d1eadbf-fdb3-4df5-9067-51beae223bc8",
   "metadata": {},
   "source": [
    "We will start with a simple recursive function in MeTTa that just adds up the first *n* positive integers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f02bd99c-cdd2-47c4-a270-0b63365a7bbd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum  $n)\n",
    "    (if (== $n 0)\n",
    "        0 (+ $n (sum (- $n 1))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a391c8b-0129-4b6d-9d2a-2251c16918ed",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a85ef6fd-edde-469c-b7e6-c31a8986f14f",
   "metadata": {},
   "source": [
    "Next, we rewrite `sum` in continuation-passing style (CPS):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a1880d65-32ac-4fd1-85bb-bc82f2c528cb",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum-cps\n",
    "  $n k)\n",
    "    (if (= n 0)\n",
    "        (k 0)\n",
    "        (sum-cps (- n 1)\n",
    "          $value)\n",
    "            (k (+ n value)))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec5d5a2f-d385-45ca-8cc0-16682bf70599",
   "metadata": {},
   "source": [
    "To run `sum-cps` we need to provide the *initial continuation* `$value) value)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ad9d3a50-464b-4306-9e65-c09e41fa3517",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum-cps 5 $value) value))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4b3e87d-29cc-45a3-856e-ce0de2582920",
   "metadata": {},
   "source": [
    "For convenience, our top-level `sum` function will just call `sum-cps` with the initial continuation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72b1d569-57c6-4026-abe5-628b62b5ecca",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum $n)\n",
    "    (sum-cps n $value) value))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "089277a1-5a2f-4d89-8a10-97857d9e1d6a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af64e288-e421-40da-bf1a-b2d4b87f8fae",
   "metadata": {},
   "source": [
    "Notice that our continuations are represented as anonymous *lambda* functions. Here we are taking advantage of MeTTa's ability to easily create and pass around higher-order functions. In the above code, there are two such continuation functions: `$value) value)` and `$value) (k (+ n value)))`.  In general, a *lambda* expression that represents a continuation may or may not contain **free variables**, depending on the context in which it arises.  For example, the continuation `$value) value)` has no free variables, since `value` is bound by the lambda's formal parameter, while the continuation `$value) (k (+ n value)))` has two free variables: `k` and `n`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b40e618-d34c-4bb4-b5be-c103f0ee40e5",
   "metadata": {},
   "source": [
    "#### Changing the representation of continuations\n",
    "\n",
    "We now change the representation of continuations from MeTTa functions to MeTTa data structures, which will just be ordinary lists (also referred to as **continuation records**). Each lambda expression that represents a continuation will get replaced by a call of the form `(make-cont <label> x y z ...)`, where `<label>` is a unique identifier for the continuation being replaced, and <tt>x y z ...</tt> are the free variables (if any) of the lambda expression. Here are the new definitions of `sum` and `sum-cps`, where the `$value) value)` continuation has been labeled `<cont-1>` and the `$value) (k (+ n value)))` continuation has been labeled `<cont-2>`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3c7d807-2c87-45a4-a9bb-242eaeaf38bd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum\n",
    "  $n)\n",
    "    (sum-cps n (make-cont '<cont-1>))))\n",
    "\n",
    "(= (sum-cps $n k)\n",
    "    (if (= n 0)\n",
    "        (k 0)\n",
    "        (sum-cps (- n 1) (make-cont '<cont-2> n k)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb613cba-6bdd-4bcc-a205-438f1def8fd3",
   "metadata": {},
   "source": [
    "The `make-cont` function simply packages the `<cont-N>` label along with the values of any free variables *x, y, z, etc.* from the original lambda expression into a MeTTa list of the form `(continuation <cont-N> x y z ...)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76414fb2-a47d-4fcf-b3e5-6ce8f5bdcea3",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (make-cont\n",
    "  (lambda args\n",
    "    (cons 'continuation args)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eac19cc1-0ee5-486c-8592-345a51ec71df",
   "metadata": {},
   "source": [
    "Here are some examples of continuation records:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57a490d4-7684-495a-9eeb-8cef02f0a975",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(make-cont '<cont-1>)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c8a7af71-f7ff-4fd8-81da-98e0c743a341",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(make-cont '<cont-2> 'free1 'free2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa40c949-f982-49a7-8ad0-d719cddad498",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(make-cont '<cont-42> 10 20 30 40)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52ec56cf-c3c0-4bf7-9be0-a750f8551a13",
   "metadata": {},
   "source": [
    "To make this code actually work, we need to define a new function `apply-cont` which takes a continuation *k* represented in this new form (a MeTTa list), along with a *value*, and does the same thing to *value* as the previous functional representation of the continuation did, according to the continuation type specified by the label. Any free variables that are needed are just retrieved from the fields of the continuation record.\n",
    "\n",
    "We also need to change all applications of the form `(k value)` to `(apply-cont k value)` since *k* is no longer represented as a MeTTa function. Here is the resulting code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a0a9515-9bf4-41f5-889d-54970867b260",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum\n",
    "  $n)\n",
    "    (sum-cps n (make-cont '<cont-1>))))\n",
    "\n",
    "(= (sum-cps\n",
    "  $n k)\n",
    "    (if (= n 0)\n",
    "        (apply-cont k 0)\n",
    "        (sum-cps (- n 1) (make-cont '<cont-2> n k)))))\n",
    "\n",
    "(= (apply-cont\n",
    "  $k value)\n",
    "    ;; k is now a list of the form (continuation <label> x y z ...)\n",
    "    (let ((label (cadr k))\n",
    "          (fields (cddr k))) ;; saved values of free variables\n",
    "      (case\n",
    "       ((eq? label '<cont-1>) value)\n",
    "       ((eq? label '<cont-2>)\n",
    "        (let ((n (car fields))\n",
    "              (k (cadr fields)))\n",
    "          (apply-cont k (+ n value))))\n",
    "       (%void%  (error \"invalid continuation label\"))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a341642-f86f-41e8-b429-9a534c6ea64f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d502b31-1b29-4563-9ae9-e5b46ec086d9",
   "metadata": {},
   "source": [
    "This code works, but notice that whenever `apply-cont` receives a continuation *k* to apply to some *value*, it uses a `cond` to decide what to do, based on *k*'s label. In this example, there are only two possible continuation labels, but larger programs could have many more. To make the code more efficient, we define separate functions corresponding to each label, and then simply apply the appropriate label function to *value* and the saved free variables. Instead of the labels being MeTTa symbols, they are now MeTTa functions that can be called directly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f731d0a3-0eef-48f9-8751-8fb56bec7102",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (apply-cont\n",
    "  $k value)\n",
    "    (let ((label (cadr k))\n",
    "          (fields (cddr k)))\n",
    "      (label value fields))))\n",
    "\n",
    "(= (<cont-1>\n",
    "  $value fields)\n",
    "    value))\n",
    "\n",
    "(= (<cont-2>\n",
    "  $value fields)\n",
    "    (let ((n (car fields))\n",
    "          (k (cadr fields)))\n",
    "      (apply-cont k (+ n value)))))\n",
    "\n",
    "(= (sum\n",
    "  $n)\n",
    "    (sum-cps n (make-cont <cont-1>)))) ;; removed ' from <cont-1>\n",
    "\n",
    "(= (sum-cps\n",
    "  $n k)\n",
    "    (if (= n 0)\n",
    "        (apply-cont k 0)\n",
    "        (sum-cps (- n 1) (make-cont <cont-2> n k))))) ;; removed ' from <cont-2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7567cfcd-1ff3-4ea8-b676-96fc58cc35d6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbb4873b-6f82-443a-bc9b-ec14aaa740e1",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(make-cont <cont-1>)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "370be051-e10c-4049-aa6c-9af185277330",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(make-cont <cont-2> 'free1 'free2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a005c30-8658-4d50-af18-5ae7100ef988",
   "metadata": {},
   "source": [
    "#### Removing the reliance on the recursion stack\n",
    "\n",
    "We have now changed the representation of continuations from MeTTa functions to data structures, so our `sum-cps` function could in principle be implemented easily in languages that do not support higher-order functions. However, there is another feature of MeTTa that we are implicitly relying on, namely the fact that MeTTa imposes no limit on the depth of its recursion stack, which enables us to call `sum` with arbitrarily large values of *n*.\n",
    "\n",
    "Unfortunately, many other languages (including Python, Java, and C++) impose a maximum depth on the recursion stack, which will cause recursive programs to crash for sufficiently large input values. In order to implement our program in such a language, we need to further transform it to avoid growing the recursion stack. We can accomplish this by passing information to functions through a set of global **registers** rather than via function arguments. Each function call of the form `(func arg1 arg2 arg3 ...)` will be replaced by a call of the form`(func)`, which in most other languages can be simulated by a simple \"goto\" instruction that does not grow the stack. The appropriate registers will be initialized to *arg1*, *arg2*, *arg3*, etc., prior to calling `(func)`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f796553-9415-4e02-9e32-42c520d3bfa1",
   "metadata": {},
   "source": [
    "#### Passing information via registers\n",
    "\n",
    "We first define a set of registers to be used for passing information to functions in place of formal parameters. The registers needed by a particular function are determined by that function's formal parameters. For example, here are the `sum-cps` function and the top-level `sum` function, which calls `sum-cps` with *n* and the initial <tt>&lt;cont-1&gt;</tt> continuation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "318fe6a2-6b2f-4436-af0e-d3eb166ebeec",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum-cps\n",
    "  $n k)\n",
    "    (if (= n 0)\n",
    "        (apply-cont k 0)\n",
    "        (sum-cps (- n 1) (make-cont <cont-2> n k)))))\n",
    "\n",
    "(= (sum\n",
    "  $n)\n",
    "    (sum-cps n (make-cont <cont-1>))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdad2f21-5ed9-4e7a-ba79-443026222693",
   "metadata": {},
   "source": [
    "We will rewrite `sum-cps` as a function of no arguments, and create new registers `n_reg` and `k_reg` for passing the necessary information to `sum-cps`. In addition, wherever we call `(sum-cps)`, we must first assign the appropriate values to the registers. We also must change all references to the formal parameters <tt>n</tt> and <tt>k</tt> in `sum-cps` to <tt>n_reg</tt> and <tt>k_reg</tt>, respectively:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5448fe9d-8285-4013-816f-da03a137dd66",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (n_reg 'undefined)\n",
    "(= (k_reg 'undefined)\n",
    "\n",
    "(= (sum-cps\n",
    "  $)\n",
    "    (if (= n_reg 0)\n",
    "        (apply-cont k_reg 0)\n",
    "        (begin\n",
    "          ;; order of assignments matters!\n",
    "          (set! k_reg (make-cont <cont-2> n_reg k_reg))\n",
    "          (set! n_reg (- n_reg 1))\n",
    "          (sum-cps)))))\n",
    "\n",
    "(= (sum\n",
    "  $n)\n",
    "    (set! k_reg (make-cont <cont-1>))\n",
    "    (set! n_reg n)\n",
    "    (sum-cps)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2dc95cee-5b2f-4c34-b550-1532ece5568b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72cdae51-3420-4024-98b5-4699cd4ca3d8",
   "metadata": {},
   "source": [
    "Notice that in the definition of `sum-cps` above, the order of the assignment statements matters. The <tt>n_reg</tt> assignment must happen *after* the <tt>k_reg</tt> assignment, otherwise the value of <tt>n_reg</tt> saved in the <tt>&lt;cont-2&gt;</tt> continuation record will be incorrect.\n",
    "\n",
    "We also need to transform `apply-cont`, `<cont-1>`, and `<cont-2>` in a similar way. Here are their current definitions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3bfb04e-7514-4724-bf1f-f6b773d037d9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (apply-cont\n",
    "  $k value)\n",
    "    (let ((label (cadr k))\n",
    "          (fields (cddr k)))\n",
    "      (label value fields))))\n",
    "\n",
    "(= (<cont-1>\n",
    "  $value fields)\n",
    "    value))\n",
    "\n",
    "(= (<cont-2>\n",
    "  $value fields)\n",
    "    (let ((n (car fields))\n",
    "          (k (cadr fields)))\n",
    "      (apply-cont k (+ n value)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "153de75b-f63d-45d9-b7e6-b39c8efa5ce4",
   "metadata": {
    "tags": []
   },
   "source": [
    "We will use the registers `k_reg` and `value_reg` to pass information to `apply-cont`. To pass information to the continuation label functions `<cont-1>` and `<cont-2>`, we will use the registers `value_reg` and `fields_reg`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba74643c-26ee-45b7-9885-4db9e4cc05a7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    ";; additional registers\n",
    "(= (value_reg 'undefined)\n",
    "(= (fields_reg 'undefined)\n",
    "\n",
    "(= (apply-cont\n",
    "  $)\n",
    "    (let ((label (cadr k_reg))\n",
    "          (fields (cddr k_reg)))\n",
    "      ;; set up value_reg and fields_reg before calling (label)\n",
    "      (set! value_reg value_reg)\n",
    "      (set! fields_reg fields)\n",
    "      (label))))\n",
    "\n",
    "(= (<cont-1>\n",
    "  $)\n",
    "    value_reg))\n",
    "\n",
    "(= (<cont-2>\n",
    "  $)\n",
    "    (let ((n (car fields_reg))\n",
    "          (k (cadr fields_reg)))\n",
    "      ;; set up k_reg and value_reg before calling (apply-cont)\n",
    "      (set! k_reg k)\n",
    "      (set! value_reg (+ n value_reg))\n",
    "      (apply-cont))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "911bf292-af52-4ab7-8cd3-bc41c20a2729",
   "metadata": {
    "tags": []
   },
   "source": [
    "We also need to rewrite the call to `apply-cont` that appears in the definition of `sum-cps`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "814d8e45-6a07-40d5-8b1c-946947e9a4f2",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum-cps\n",
    "  $)\n",
    "    (if (= n_reg 0)\n",
    "        (begin\n",
    "          ;; set up k_reg and value_reg before calling (apply-cont)\n",
    "          (set! k_reg k_reg)\n",
    "          (set! value_reg 0)\n",
    "          (apply-cont))\n",
    "        (begin\n",
    "          (set! k_reg (make-cont <cont-2> n_reg k_reg))\n",
    "          (set! n_reg (- n_reg 1))\n",
    "          (sum-cps)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e92cb397-fe0b-46aa-ae40-785ad9f9454a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "153bf09d-f39a-4940-b667-bb775d396ed1",
   "metadata": {},
   "source": [
    "Notice that the assignment statements `(set! k_reg k_reg)` and `(set! value_reg value_reg)` in `sum-cps` and `apply-cont` are unnecessary, so we can simply remove them from the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7627c51-4ec4-4fbd-a13a-d3df0de47fce",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum-cps\n",
    "  $)\n",
    "    (if (= n_reg 0)\n",
    "        (begin\n",
    "          (set! value_reg 0)\n",
    "          (apply-cont))\n",
    "        (begin\n",
    "          (set! k_reg (make-cont <cont-2> n_reg k_reg))\n",
    "          (set! n_reg (- n_reg 1))\n",
    "          (sum-cps)))))\n",
    "\n",
    "(= (apply-cont\n",
    "  $)\n",
    "    (let ((label (cadr k_reg))\n",
    "          (fields (cddr k_reg)))\n",
    "      (set! fields_reg fields)\n",
    "      (label))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fbee1c15-c609-496b-912a-e68490db41a8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b82e1c6-46cb-4a6d-87a7-73898661bb66",
   "metadata": {},
   "source": [
    "#### The trampoline\n",
    "\n",
    "Although the above code works, it still generates an arbitrarily long chain of tail-recursive function calls of the form `(sum-cps)`, `(apply-cont)`, `(label)`, etc., each of which essentially acts like a \"goto\" instruction. This is not a problem in MeTTa, since no limit is imposed on the length of such call-chains. However, in other languages it could be a problem. Therefore we need to break the chain of function calls into single steps. This is accomplished through the use of a **trampoline**, which is essentially a while-loop that performs the computation one step at a time and avoids building up a chain of function calls.\n",
    "\n",
    "The trampoline uses a special register called `pc`, which contains the next function to call on each loop cycle. Calling the function simply updates the registers appropriately for the next loop cycle. The `pc` register itself also gets updated on each cycle. This process continues until the `pc` register becomes empty, at which point the final result of the computation will be available in the register `final_reg`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "183b1e72-1f51-4e6a-baae-ef149b8db89f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    ";; additional registers\n",
    "(= (pc 'undefined)\n",
    "(= (final_reg 'undefined)\n",
    "\n",
    ";; equivalent to a while-loop\n",
    "(= (trampoline\n",
    "  $)\n",
    "    (if pc\n",
    "        (begin\n",
    "          (pc)\n",
    "          (trampoline))\n",
    "        final_reg)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d56b66df-c19a-4a13-823e-4a450597355f",
   "metadata": {},
   "source": [
    "Instead of calling a function directly such as `(sum-cps)`, we replace the function call with `(set! pc sum-cps)`, which sets the `pc` register to the `sum-cps` function itself. The trampoline will then invoke it within the loop. All functions other than the trampoline simply execute if-statements and assignments, without ever calling another function directly. Here are the transformed versions of the other functions, showing the changes made to the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d29b7b88-3838-4aa6-a310-ab7429ed3bcb",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum-cps\n",
    "  $)\n",
    "    (if (= n_reg 0)\n",
    "        (begin\n",
    "          (set! value_reg 0)\n",
    "          (set! pc apply-cont))   ;; changed\n",
    "        (begin\n",
    "          (set! k_reg (make-cont <cont-2> n_reg k_reg))\n",
    "          (set! n_reg (- n_reg 1))\n",
    "          (set! pc sum-cps)))))   ;; changed\n",
    "\n",
    "(= (apply-cont\n",
    "  $)\n",
    "    (let ((label (cadr k_reg))\n",
    "          (fields (cddr k_reg)))\n",
    "      (set! fields_reg fields)\n",
    "      (set! pc label))))          ;; changed\n",
    "\n",
    "(= (<cont-1>\n",
    "  $)\n",
    "    (set! final_reg value_reg)    ;; changed\n",
    "    (set! pc #f)))                ;; added\n",
    "\n",
    "(= (<cont-2>\n",
    "  $)\n",
    "    (let ((n (car fields_reg))\n",
    "          (k (cadr fields_reg)))\n",
    "      (set! k_reg k)\n",
    "      (set! value_reg (+ n value_reg))\n",
    "      (set! pc apply-cont))))     ;; changed"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "664629e5-e584-471d-b553-aa323e52bd44",
   "metadata": {},
   "source": [
    "The top-level function `sum` initializes the registers and then starts the trampoline, which runs the computation to completion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc36d4c3-b969-4cd7-ac9c-19df33ac0a5c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(= (sum\n",
    "  $n)\n",
    "    (set! k_reg (make-cont <cont-1>))\n",
    "    (set! n_reg n)\n",
    "    (set! pc sum-cps)\n",
    "    (trampoline)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e89eb75-18ee-47d9-a162-90072963697d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bba46566-fd3c-4576-befb-cbc98626e508",
   "metadata": {},
   "source": [
    "#### The MeTTa register machine\n",
    "\n",
    "The complete register machine code is given below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8604fad1-5bec-43d8-8817-24783969e468",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    ";; global registers\n",
    "(= (n_reg 'undefined)\n",
    "(= (k_reg 'undefined)\n",
    "(= (value_reg 'undefined)\n",
    "(= (fields_reg 'undefined)\n",
    "(= (pc 'undefined)\n",
    "(= (final_reg 'undefined)\n",
    "\n",
    "(= (trampoline\n",
    "  $)\n",
    "    (if pc\n",
    "        (begin\n",
    "          (pc)\n",
    "          (trampoline))\n",
    "        final_reg)))\n",
    "\n",
    "(= (make-cont\n",
    "  (lambda args\n",
    "    (cons 'continuation args)))\n",
    "\n",
    "(= (apply-cont\n",
    "  $)\n",
    "    (let ((label (cadr k_reg))\n",
    "          (fields (cddr k_reg)))\n",
    "      (set! fields_reg fields)\n",
    "      (set! pc label))))\n",
    "\n",
    "(= (<cont-1>\n",
    "  $)\n",
    "    (set! final_reg value_reg)\n",
    "    (set! pc #f)))\n",
    "\n",
    "(= (<cont-2>\n",
    "  $)\n",
    "    (let ((n (car fields_reg))\n",
    "          (k (cadr fields_reg)))\n",
    "      (set! k_reg k)\n",
    "      (set! value_reg (+ n value_reg))\n",
    "      (set! pc apply-cont))))\n",
    "\n",
    "(= (sum-cps\n",
    "  $)\n",
    "    (if (= n_reg 0)\n",
    "        (begin\n",
    "          (set! value_reg 0)\n",
    "          (set! pc apply-cont))\n",
    "        (begin\n",
    "          (set! k_reg (make-cont <cont-2> n_reg k_reg))\n",
    "          (set! n_reg (- n_reg 1))\n",
    "          (set! pc sum-cps)))))\n",
    "\n",
    ";; top-level function\n",
    "(= (sum\n",
    "  $n)\n",
    "    (set! k_reg (make-cont <cont-1>))\n",
    "    (set! n_reg n)\n",
    "    (set! pc sum-cps)\n",
    "    (trampoline)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67863bfc-79a8-43cd-9e84-2044c776de0e",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e0a081a-7c3a-404d-82a7-42cded4a092c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(sum 5000)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f825722-32ef-4f64-bc01-20609ede7153",
   "metadata": {},
   "source": [
    "#### The Python register machine\n",
    "\n",
    "If we tried to implement `sum` recursively in Python, it would crash for values of *n* that exceed Python's recursion depth limit. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b8b0dce3-d046-4643-922d-500ff47a14a8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "def sum_recursive(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return n + sum_recursive(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d7a4050-047c-4785-9b50-8b7f7548cda0",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "sum_recursive(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5ca1ef5-faca-4fde-b961-951df318d7bb",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "sum_recursive(5000)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b70b0c2e-6d61-45e2-aba1-b400b5ab26e1",
   "metadata": {},
   "source": [
    "Fortunately, our MeTTa register machine does not grow the recursion stack, and can be easily translated directly into Python. All we need to do is define Python versions of the `car` and `cdr` primitives:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6aa36a46-ccf4-45cb-9767-a68a132cb7ad",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "def car(lst):\n",
    "    return lst[0]\n",
    "\n",
    "def cdr(lst):\n",
    "    return lst[1:]\n",
    "\n",
    "def cadr(lst):\n",
    "    return car(cdr(lst))\n",
    "   \n",
    "def cddr(lst):\n",
    "    return cdr(cdr(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "359201b3-87be-41c6-af56-775182f27372",
   "metadata": {},
   "source": [
    "Here is the register machine code translated into Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f064bb0-3aa9-43b4-aea9-9365145fad5f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "# global registers\n",
    "n_reg = None\n",
    "k_reg = None\n",
    "value_reg = None\n",
    "fields_reg = None\n",
    "pc = None\n",
    "final_reg = None\n",
    "\n",
    "def trampoline():\n",
    "    while pc:\n",
    "        pc()\n",
    "    return final_reg\n",
    "\n",
    "def make_cont(*args):\n",
    "    return (\"continuation\",) + args\n",
    "\n",
    "def apply_cont():\n",
    "    global fields_reg, pc\n",
    "    label = cadr(k_reg)\n",
    "    fields = cddr(k_reg)\n",
    "    fields_reg = fields\n",
    "    pc = label\n",
    "\n",
    "def cont_1():\n",
    "    global final_reg, pc\n",
    "    final_reg = value_reg\n",
    "    pc = False\n",
    "\n",
    "def cont_2():\n",
    "    global k_reg, value_reg, pc\n",
    "    n = car(fields_reg)\n",
    "    k = cadr(fields_reg)\n",
    "    k_reg = k\n",
    "    value_reg = n + value_reg\n",
    "    pc = apply_cont\n",
    "\n",
    "def sum_cps():\n",
    "    global value_reg, pc, k_reg, n_reg\n",
    "    if n_reg == 0:\n",
    "        value_reg = 0\n",
    "        pc = apply_cont\n",
    "    else:\n",
    "        k_reg = make_cont(cont_2, n_reg, k_reg)\n",
    "        n_reg = n_reg - 1\n",
    "        pc = sum_cps\n",
    "\n",
    "# top-level function\n",
    "def sum(n):\n",
    "    global k_reg, n_reg, pc\n",
    "    k_reg = make_cont(cont_1)\n",
    "    n_reg = n\n",
    "    pc = sum_cps\n",
    "    return trampoline()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2b8b837-cc74-43d2-b955-ae2ffb4ee605",
   "metadata": {},
   "source": [
    "The Python version is no longer subject to the recursion stack depth limit. It is also much faster than the MeTTa version:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "214868d4-b55c-48ce-8e82-8cb98d7ac3a5",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "sum(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "78e60d18-49b5-4b19-bc5b-e763cb4364fb",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "sum(5000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91f565ad-6014-479e-ba20-3098881aa7c1",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%python\n",
    "\n",
    "sum(100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c46c42d-df4e-42af-a56a-e965f8a94f20",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Vspace MeTTa 3",
   "language": "scheme",
   "name": "vspace_scheme"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "scheme"
   },
   "mimetype": "text/x-scheme",
   "name": "scheme",
   "pygments_lexer": "scheme"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}