homeworks/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": null,
   "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": null,
   "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 in the current \n",
    "        environment. If it is not found raise a NameError as below\n",
    "        \"\"\"\n",
    "        raise NameError(\"{} not found in Environment\".format(vaiable))"
   ]
  },
  {
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "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",
    "    #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",
    "    #your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l = TupleLL()\n",
    "l.insert_front(('a', 1))\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l.insert_front(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2.\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": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#your code here\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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#your code here"
   ]
  },
  {
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Environment.register(Env2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": null,
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "globenv = global_env(Env2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def eval_ptree(x, env):\n",
    "    fmap={'#t':True, '#f':False, 'nil':None}\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": null,
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "program = \"\"\"\n",
    "(define radius 5)\n",
    "(* pi (* radius radius))\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "p=Program(program, globenv)\n",
    "list(iter(p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for s in p.parse():\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for result in p.run():\n",
    "    print(result)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "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
}