hw8.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HW8\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a Linked list class (some of which was done few labs/classes back) . We'll use a linked list as a repository for bindings. We will consider an implementation where newer bindings for existing variables occur closer to the head in the linked list. Notice that we added a `repOK` which is an identity function. Take care to see where it is used."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import reprlib, numbers\n",
    "\n",
    "\n",
    "class LL:\n",
    "    \"\"\"\n",
    "    >>> A = LL()  \n",
    "    >>> A[0]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    IndexError: trying to index an empty LL\n",
    "    >>> A.insert_front(1)\n",
    "    >>> A[0]\n",
    "    1\n",
    "    >>> A.insert_back(2)\n",
    "    >>> A[1]\n",
    "    2\n",
    "    >>> A\n",
    "    LL([1,...])\n",
    "    >>> myll = LL.from_components([1,2])\n",
    "    >>> myll[1]\n",
    "    1\n",
    "    >>> len(myll)\n",
    "    2\n",
    "    >>> myll[2]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    IndexError: LL index out of range\n",
    "    >>> myll[0:1]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    TypeError: LL indices must be integers\n",
    "    \"\"\"\n",
    "    @classmethod\n",
    "    def from_components(cls, components):\n",
    "        inst = cls(components[0])\n",
    "        for c in components[1:]:\n",
    "            inst.insert_front(c)\n",
    "        return inst\n",
    "        \n",
    "    def repOK(self, element):\n",
    "        return element\n",
    "    \n",
    "    def __init__(self, head=None):\n",
    "        if head is None:\n",
    "            self._headNode = None\n",
    "        else:\n",
    "            head = self.repOK(head)\n",
    "            self._headNode = [head, None]\n",
    "            \n",
    "    def insert_front(self, element):\n",
    "        element = self.repOK(element)\n",
    "        new_node = [element, None]\n",
    "        new_node[1] = self._headNode\n",
    "        self._headNode = new_node\n",
    "        \n",
    "    def insert_back(self, element):\n",
    "        element = self.repOK(element)\n",
    "        new_node = [element, None]\n",
    "        curr_ptr = self._headNode\n",
    "        while curr_ptr[1] is not None:\n",
    "            curr_ptr = curr_ptr[1]\n",
    "        curr_ptr[1]= new_node\n",
    "        \n",
    "    def __repr__(self):\n",
    "        class_name = type(self).__name__\n",
    "        if len(self)==0:\n",
    "            components=\"\"\n",
    "        else:\n",
    "            components = reprlib.repr(self[0])\n",
    "        return '{}([{},...])'.format(class_name,components)\n",
    "\n",
    "\n",
    "    def __len__(self):\n",
    "        curr_ptr = self._headNode\n",
    "        count = 0\n",
    "        if curr_ptr==None:\n",
    "            return 0\n",
    "        while 1:\n",
    "            count = count + 1\n",
    "            if curr_ptr[1] is None:\n",
    "                break\n",
    "            curr_ptr = curr_ptr[1]\n",
    "        return count    \n",
    "    \n",
    "    def __getitem__(self, index):\n",
    "        class_name = type(self).__name__\n",
    "        if isinstance(index, numbers.Integral): \n",
    "            curr_ptr = self._headNode\n",
    "            if curr_ptr==None:\n",
    "                msg = 'trying to index an empty {class_name}' \n",
    "                raise IndexError(msg.format(class_name=class_name))\n",
    "            next_ptr = self._headNode[1]\n",
    "            count = 0\n",
    "            while 1:\n",
    "                if index == count:\n",
    "                    return curr_ptr[0]\n",
    "                if curr_ptr[1] is None:\n",
    "                    msg = '{class_name} index out of range' \n",
    "                    raise IndexError(msg.format(class_name=class_name))       \n",
    "                count += 1\n",
    "                curr_ptr = curr_ptr[1]\n",
    "        else:\n",
    "            msg = '{class_name} indices must be integers' \n",
    "            raise TypeError(msg.format(class_name=class_name))\n",
    "         \n",
    "    def index(self, element):\n",
    "        class_name = type(self).__name__\n",
    "        curr_ptr = self._headNode\n",
    "        count = 0\n",
    "        if curr_ptr==None:\n",
    "            msg = 'trying to get index from empty {class_name}' \n",
    "            raise IndexError(msg.format(class_name=class_name))\n",
    "        while 1:\n",
    "            if curr_ptr[0] == element:\n",
    "                return count\n",
    "            if curr_ptr[1] is None:\n",
    "                msg = '{element} is not in {class_name}' \n",
    "                raise ValueError(msg.format(element=element, class_name=class_name))\n",
    "            count += 1\n",
    "            curr_ptr = curr_ptr[1]\n",
    "            \n",
    "    def remove(self, element):\n",
    "        class_name = type(self).__name__\n",
    "        curr_ptr = self._headNode\n",
    "        prev_ptr = None\n",
    "        if curr_ptr==None:\n",
    "            msg = 'remove from empty {class_name}' \n",
    "            raise IndexError(msg.format(class_name=class_name))\n",
    "        while 1:\n",
    "            if curr_ptr[0] == element:\n",
    "                if prev_ptr is None:\n",
    "                    self._headNode = curr_ptr[1]\n",
    "                else:\n",
    "                    prev_ptr[1] = curr_ptr[1]\n",
    "                return None\n",
    "            if curr_ptr[1] is None:\n",
    "                msg = '{element} is not in {class_name}' \n",
    "                raise ValueError(msg.format(element=element, class_name=class_name))\n",
    "            prev_ptr=curr_ptr\n",
    "            curr_ptr = curr_ptr[1]\n",
    "        \n",
    "    def remove_front(self):\n",
    "        class_name = type(self).__name__\n",
    "        curr_ptr = self._headNode\n",
    "        if curr_ptr==None:\n",
    "            msg = 'remove from empty {class_name}' \n",
    "            raise IndexError(msg.format(class_name=class_name))\n",
    "        self._headNode = curr_ptr[1]\n",
    "        return curr_ptr[0]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import abc\n",
    "class Environment(abc.ABC):\n",
    "    \"\"\"\n",
    "    This is the interface for an Environment. The client for \n",
    "    this interface is a language intepreter. \n",
    "    \"\"\"\n",
    "    @classmethod\n",
    "    @abc.abstractmethod\n",
    "    def empty(cls):\n",
    "        return cls()\n",
    "    \n",
    "    @abc.abstractmethod\n",
    "    def extend(self, variable, value):\n",
    "        \"\"\"\n",
    "        extend an existing environment by binding variable to value.\n",
    "        The values must be an acceptable value in the language. If the\n",
    "        same variable is used twice the newer value must be bound.\n",
    "        \"\"\"\n",
    "    \n",
    "    @abc.abstractmethod\n",
    "    def extend_many(self, envdict):\n",
    "        \"\"\"\n",
    "        extend the current environment by values in the dictionary\n",
    "        envdict. If the dictionary contains variables already in the\n",
    "        environment, the newer values from the dictionary are bound\n",
    "        \"\"\"\n",
    "        \n",
    "    @abc.abstractmethod\n",
    "    def lookup(variable):\n",
    "        \"\"\"\n",
    "        return the unique binding of the variable and the environment it was bound\n",
    "        in as a tuple. If it is not found raise a NameError as below\n",
    "        \"\"\"\n",
    "        raise NameError(\"{} not found in Environment\".format(variable))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1\n",
    "\n",
    "Lets inherit from class `LL` to create a TupleLL where the values in the linked list are tuples of the type `(key, value)`. After inheriting, add an additional method `first_match` which returns a tuple `(index_of_nearest_element, nearest element)` to the head where the first member of the tuple matches `key`. Also add another method `all_matches` which returns a list of tuples of allmatches, sorted by distance to head. Currently, the structure of the other methods in the linked list do not need to know about this 2-element tuple restriction on the elements. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class TupleLL(LL):\n",
    "    \"\"\"\n",
    "    A linked list whose elements must be tuples.\n",
    "    \n",
    "    RepInv: any insertion should leave a list with only tuples as members.\n",
    "    \n",
    "    Examples\n",
    "    --------\n",
    "    >>> l = TupleLL().from_components([('a',1),('b',2),('c',1),('a',3)])\n",
    "    >>> l.first_match('a')\n",
    "    (0, ('a', 3))\n",
    "    >>> l.first_match('e') #if no instances, return None\n",
    "    None\n",
    "    >>> l.all_matches('a')\n",
    "    [(0, ('a', 3)), (3, ('a', 1))]\n",
    "    >>> l.all_matches('e') #if no instances, return empty list\n",
    "    []\n",
    "    \"\"\"\n",
    "    #could be implemented using a check on the whole list\n",
    "    def repOK(self, element):\n",
    "        assert isinstance(element, tuple), \"element needs to be a tuple\"\n",
    "        return element\n",
    "    \n",
    "    def first_match(self,key):\n",
    "        \"\"\"Finds the first tuple where the first part\n",
    "        of the tuple matches the input key \n",
    "        \"\"\"\n",
    "        current_node = self._headNode\n",
    "        if not isinstance(key,str):\n",
    "            raise TypeError(\"key must be string\")\n",
    "        if current_node == None:\n",
    "            return None\n",
    "        i = 0\n",
    "\n",
    "        while True:\n",
    "            if key == current_node[0][0]:\n",
    "                return (i, current_node[0])\n",
    "            if current_node[1] == None:\n",
    "                return None\n",
    "            current_node = current_node[1]\n",
    "            i += 1\n",
    "        \n",
    "    def all_matches(self, key):\n",
    "        \"\"\"Finds all the tuples where the first part\n",
    "        of the tuple matches the input key \n",
    "        \"\"\"\n",
    "        if not isinstance(key,str):\n",
    "            raise TypeError(\"key must be string\")\n",
    "        matches = []\n",
    "        current_node = self._headNode\n",
    "        if current_node == None:\n",
    "            return matches\n",
    "        i = 0\n",
    "        while True:\n",
    "            if key == current_node[0][0]:\n",
    "                matches.append((i, current_node[0]))\n",
    "            if current_node[1] == None:\n",
    "                return matches\n",
    "            current_node = current_node[1]\n",
    "            i += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, ('nan', 1))]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = TupleLL()\n",
    "l.insert_front(('nan', 1))\n",
    "l.all_matches('nan')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "element needs to be a tuple",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-53aaefcd81ba>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0ml\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minsert_front\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-2-ca60a92a09c4>\u001b[0m in \u001b[0;36minsert_front\u001b[0;34m(self, element)\u001b[0m\n\u001b[1;32m     49\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     50\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0minsert_front\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0melement\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 51\u001b[0;31m         \u001b[0melement\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrepOK\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0melement\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     52\u001b[0m         \u001b[0mnew_node\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0melement\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     53\u001b[0m         \u001b[0mnew_node\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_headNode\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-4-6e5673aaf0c3>\u001b[0m in \u001b[0;36mrepOK\u001b[0;34m(self, element)\u001b[0m\n\u001b[1;32m     19\u001b[0m     \u001b[0;31m#could be implemented using a check on the whole list\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     20\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mrepOK\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0melement\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 21\u001b[0;31m         \u001b[0;32massert\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0melement\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtuple\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"element needs to be a tuple\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     22\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0melement\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     23\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAssertionError\u001b[0m: element needs to be a tuple"
     ]
    }
   ],
   "source": [
    "l.insert_front(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2. AbsFun\n",
    "\n",
    "Implement a inplementation class `Env2` that impements the environment interface using the `TupleLL`. Let us ask what the AbsFun and RepInv are for this implementation. Write an AbsFun for it, noting that in this concrete representation, there can be multiple key-value pairs in the environment for the same key, and that there is a way to disambiguate the correct one. \n",
    "\n",
    "(In general, the Absfun should limit the keys and values allowed for our bindings (as according to our language) as well. But we wont do that here.)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Env2(Environment):\n",
    "    \"\"\"\n",
    "    AbsFun: The linked list containing tuples (variable, value)\n",
    "    represents the binding between values and variables\n",
    "    \n",
    "    \"\"\"\n",
    "    def __init__(self,head=None):\n",
    "        if head == None:\n",
    "            self.env = TupleLL()\n",
    "        else:\n",
    "            self.env = TupleLL(head)\n",
    "            \n",
    "    @classmethod\n",
    "    def empty(cls):\n",
    "        return cls()\n",
    "    \n",
    "    def extend(self, variable, value):\n",
    "        \"\"\"\n",
    "        extend an existing environment by binding variable to value.\n",
    "        The values must be an acceptable value in the language. If the\n",
    "        same variable is used twice the newer value must be bound.\n",
    "        \"\"\"\n",
    "        if not self.env.first_match(variable):\n",
    "            self.env.insert_front((variable, value))\n",
    "        else:\n",
    "            a,b = self.env.first_match(variable)\n",
    "            self.env.remove((b[0],b[1]))\n",
    "            self.env.insert_front((variable,value))\n",
    "    \n",
    "    def extend_many(self, envdict):\n",
    "        \"\"\"\n",
    "        extend the current environment by values in the dictionary\n",
    "        envdict. If the dictionary contains variables already in the\n",
    "        environment, the newer values from the dictionary are bound\n",
    "        \"\"\"\n",
    "        for key,value in envdict.items():\n",
    "            self.extend(key,value)\n",
    "            \n",
    "        \n",
    "    def lookup(self, variable):\n",
    "        \"\"\"\n",
    "        return the unique binding of the variable in the current \n",
    "        environment. If it is not found raise a NameError as below\n",
    "        \"\"\"\n",
    "        idx = self.env.first_match(variable)\n",
    "        if idx:\n",
    "            return idx[1][1],'Env2'\n",
    "        else:\n",
    "            raise NameError(\"{} not found in Environment\".format(variable))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3. `repinv`\n",
    "\n",
    "Now let us write and test a RepInv for this implementation. Note that just like in the case with the list-with-duplicates implementation of a set, its hard to come up with any uniqueness-of-binding RepInv. But we can ask the following: a newer binding overrides an old one. Write a Repinv which implements this and include a repOK methodwhich makes sure that any methods mutating the environment respect this RepInv and any observers return the correct binding. \n",
    "\n",
    "Hint: the `repOK` will need a signature `def repOK(self, key, value)` and also be used in the `lookup` method. It will use all_matches, and not be returning anything."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Env2(Environment):\n",
    "    \"\"\"\n",
    "    AbsFun: The linked list containing tuples (variable, value)\n",
    "    represents the binding between values and variables\n",
    "    \n",
    "    Repinv: Newer bindings override old ones so that each variable \n",
    "    is bound to only one value\n",
    "    \n",
    "    \"\"\"\n",
    "    def repOK(self,key,value):\n",
    "        all_matches = self.env.all_matches(key)\n",
    "        assert len(all_matches) == 1, \"Variables must only be bound to one value\"\n",
    "        assert all_matches[0][1][0] == key, \"Bounded key isnt correct\"\n",
    "        if value == value:\n",
    "            assert all_matches[0][1][1] == value, \"Bounded value isnt correct\"\n",
    "        \n",
    "    def __init__(self,head=None):\n",
    "        if head == None:\n",
    "            self.env = TupleLL()\n",
    "        else:\n",
    "            self.env = TupleLL(head)\n",
    "            \n",
    "    @classmethod\n",
    "    def empty(cls):\n",
    "        return cls()\n",
    "    \n",
    "    def extend(self, variable, value):\n",
    "        \"\"\"\n",
    "        extend an existing environment by binding variable to value.\n",
    "        The values must be an acceptable value in the language. If the\n",
    "        same variable is used twice the newer value must be bound.\n",
    "        \"\"\"\n",
    "        if self.env.first_match(variable) == None:\n",
    "            self.env.insert_front((variable, value))\n",
    "        else:\n",
    "            a,b = self.env.first_match(variable)\n",
    "            self.env.remove((b[0],b[1]))\n",
    "            self.env.insert_front((variable,value))\n",
    "        self.repOK(variable,value)\n",
    "\n",
    "    def extend_many(self, envdict):\n",
    "        \"\"\"\n",
    "        extend the current environment by values in the dictionary\n",
    "        envdict. If the dictionary contains variables already in the\n",
    "        environment, the newer values from the dictionary are bound\n",
    "        \"\"\"\n",
    "        for key,value in envdict.items():\n",
    "            self.extend(key,value)\n",
    "            \n",
    "        \n",
    "    def lookup(self, variable):\n",
    "        \"\"\"\n",
    "        return the unique binding of the variable in the current \n",
    "        environment. If it is not found raise a NameError as below\n",
    "        \"\"\"\n",
    "        idx = self.env.first_match(variable)\n",
    "        if idx:\n",
    "            el = idx[1]\n",
    "            self.repOK(variable,el[1])\n",
    "            return el[1],'Env2'\n",
    "        else:\n",
    "            raise NameError(\"{} not found in Environment\".format(variable))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q4. Running the program\n",
    "\n",
    "Just make sure that the program actually runs :-). Note some changes here: we are using `yield`s instead of `return`s at multiple places."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets use this class in a function which creates a global environment for our calculator referenced as `globenv`. we first register this implementation for the `Environment` interface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "__main__.Env2"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Environment.register(Env2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import math\n",
    "def global_env(envclass):\n",
    "    \"An environment with some Scheme standard procedures.\"\n",
    "    import math, operator as op\n",
    "    env = envclass.empty()\n",
    "    env.extend_many(vars(math))\n",
    "    env.extend_many({\n",
    "        '+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv, \n",
    "        'abs':     abs,\n",
    "        'max':     max,\n",
    "        'min':     min,\n",
    "        'round':   round,\n",
    "        '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '==':op.eq,\n",
    "        'not':     op.not_\n",
    "    })\n",
    "    return env"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Function():\n",
    "    def __init__(self, params, parsedbody, env):\n",
    "        self.params = params\n",
    "        self.code = parsedbody\n",
    "        self.env = env\n",
    "        self.envclass = env.__class__\n",
    "        \n",
    "    def __call__(self, *args):\n",
    "        funcenv = self.envclass(outerenv = self.env)\n",
    "        funcenv.extend_many(zip(self.params, args))\n",
    "        return eval_ptree(self.code, funcenv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "globenv = global_env(Env2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def typer(token):\n",
    "    try:\n",
    "        t = int(token)\n",
    "        return t\n",
    "    except ValueError:\n",
    "        try:\n",
    "            t = float(token)\n",
    "            return t\n",
    "        except ValueError:\n",
    "            return str(token)\n",
    "        \n",
    "def lex(loc):\n",
    "    tokenlist =  loc.replace('(', ' ( ').replace(')', ' ) ').split()\n",
    "    return [typer(t) for t in tokenlist]\n",
    "\n",
    "def syn(tokens):\n",
    "    if len(tokens) == 0:\n",
    "        return []\n",
    "    token = tokens.pop(0)\n",
    "    if token == '(':\n",
    "        L = []\n",
    "        while tokens[0] != ')':\n",
    "            L.append(syn(tokens))\n",
    "        tokens.pop(0) # pop off ')'\n",
    "        return L\n",
    "    else:\n",
    "        if token==')':\n",
    "            assert 1, \"should not have got here\"\n",
    "        return token\n",
    "    \n",
    "def parse(loc):\n",
    "    return syn(lex(loc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def eval_ptree(x, env):\n",
    "    fmap={'#t':True, '#f':False, 'nil':None}\n",
    "    Symbol=str\n",
    "    if x in ('#t', '#f', 'nil'):\n",
    "        return fmap[x] \n",
    "    elif isinstance(x, Symbol):\n",
    "        # variable lookup\n",
    "        return env.lookup(x)[0]\n",
    "    elif not isinstance(x, list):  # constant\n",
    "        return x\n",
    "    elif len(x)==0: #noop\n",
    "        return None\n",
    "    elif x[0]=='if':\n",
    "        (_, predicate, truexpr, falseexpr) = x\n",
    "        if eval_ptree(predicate, env):\n",
    "            expression = truexpr\n",
    "        else:\n",
    "            expression = falseexpr\n",
    "        return eval_ptree(expression, env)\n",
    "    elif x[0] == 'def':         # variable definition\n",
    "        (_, var, expression) = x\n",
    "        #postorder traversal by nested eval is needed below\n",
    "        # your code here\n",
    "        env.extend(var, eval_ptree(expression, env))\n",
    "    elif x[0] == 'store':           # (set! var exp)\n",
    "        (_, var, exp) = x\n",
    "        env.lookup(var)[1].extend(var, eval_ptree(exp, env))\n",
    "    elif x[0] == 'func':\n",
    "        (_, parameters, parsedbody) = x\n",
    "        return Function(parameters, parsedbody, env)\n",
    "    else:                          # operator\n",
    "        op = eval_ptree(x[0], env)\n",
    "        #postorder traversal to get subexpressione before running the op\n",
    "        args = [eval_ptree(arg, env) for arg in x[1:]]\n",
    "        return op(*args)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Program():\n",
    "    \n",
    "    def __init__(self, program, env):\n",
    "        self.program = [e.strip() for e in program.split('\\n')]\n",
    "        self.env = env\n",
    "        \n",
    "    def __iter__(self):\n",
    "        for line in self.program:\n",
    "            yield line\n",
    "    \n",
    "    def parse(self):\n",
    "        for l in iter(self):\n",
    "            yield parse(l)\n",
    "            \n",
    "    def run(self):\n",
    "        for l in iter(self):\n",
    "            yield eval_ptree(parse(l), self.env)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "program = \"\"\"\n",
    "(def radius 5)\n",
    "(* pi (* radius radius))\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['', '(def radius 5)', '(* pi (* radius radius))', '']"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p=Program(program, globenv)\n",
    "list(iter(p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "['def', 'radius', 5]\n",
      "['*', 'pi', ['*', 'radius', 'radius']]\n",
      "[]\n"
     ]
    }
   ],
   "source": [
    "for s in p.parse():\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "None\n",
      "78.53981633974483\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "for result in p.run():\n",
    "    print(result)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [py35]",
   "language": "python",
   "name": "Python [py35]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}