calculadora-plus-gabarito.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instale o Lark, se necessário\n",
    "!pip install lark-parser --user"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pprint import pprint\n",
    "from collections import ChainMap\n",
    "from lark import Lark, InlineTransformer, Tree, Token\n",
    "\n",
    "# Truque para fazer as árvores mostrarem no modo \"pretty\" por padrão\n",
    "Tree._repr_html_ = lambda t: '<pre>%s</pre>' % t.pretty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Uma linguagem de programação simples\n",
    "## Calculadora tradicional\n",
    "\n",
    "Começamos nossa atividade criando uma calculadora tradicional que suporta as quatro operações básicas e mais a multiplicação. Usamos um método usual de definir a precedência e associatividade dos operadores a partir do modo como construímos a gramática."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "calc = Lark(r\"\"\"\n",
    "?start : block\n",
    "\n",
    "?block : (item) (\";\" item)* \";\"?\n",
    "\n",
    "assign : NAME \"=\" expr\n",
    "\n",
    "?item  : expr \n",
    "       | assign \n",
    "       | fn\n",
    "       \n",
    "?fn   : \"fn\" NAME \"(\" NAME \")\" \"{\" block \"}\"\n",
    "\n",
    "?expr : expr PLUS_OP term  -> binop\n",
    "      | term\n",
    "      \n",
    "?term : expr MUL_OP term   -> binop\n",
    "      | pow\n",
    "      \n",
    "?pow  : atom POW_OP pow    -> binop\n",
    "      | atom\n",
    "      \n",
    "?atom : NUMBER -> number\n",
    "      | NAME   -> name\n",
    "      | \"(\" expr \")\"\n",
    "      | NAME \"(\" expr \")\"  -> call\n",
    "\n",
    "\n",
    "// Terminais\n",
    "NUMBER  : /\\d+(\\.\\d+)?/\n",
    "NAME    : /[a-zA-Z]\\w*/\n",
    "POW_OP  : /\\^/\n",
    "PLUS_OP : /[+-]/\n",
    "MUL_OP  : /[*\\/]/\n",
    "%ignore /\\s+/\n",
    "\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esta gramática consegue reconhecer facilmente expressões matemáticas simples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre>binop\n",
       "  binop\n",
       "    number\t123\n",
       "    +\n",
       "    number\t1\n",
       "  +\n",
       "  binop\n",
       "    number\t3.14\n",
       "    ^\n",
       "    number\t2\n",
       "</pre>"
      ],
      "text/plain": [
       "Tree(binop, [Tree(binop, [Tree(number, [Token(NUMBER, '123')]), Token(PLUS_OP, '+'), Tree(number, [Token(NUMBER, '1')])]), Token(PLUS_OP, '+'), Tree(binop, [Tree(number, [Token(NUMBER, '3.14')]), Token(POW_OP, '^'), Tree(number, [Token(NUMBER, '2')])])])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calc.parse('(123 + 1) + 3.14^2')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transformer\n",
    "\n",
    "Vamos aplicar um transformer para converter as árvores geradas pelo Lark na representação de listas (também conhecidas como *S-expressions*, ou expressões simbólicas).\n",
    "\n",
    "Note que existem poucas regras para considerar, já que temos apenas valores terminais (NUMBER e NAME) e expressões binárias nas nossas árvores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('+', ('+', 123.0, 1.0), ('^', 3.14, 2.0))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class SExprTransformer(InlineTransformer):\n",
    "    # Estre truque automaticamente cria um método que transforma o argumento\n",
    "    # respectivamente para float e str\n",
    "    number = float\n",
    "    name = str\n",
    "    \n",
    "    # Passamos os elementos que formam a árvore como argumentos\n",
    "    def binop(self, left, op, right):\n",
    "        # convertemos operador de Token lark para string\n",
    "        op = str(op)\n",
    "        \n",
    "        # Retorna a S-expression\n",
    "        return (op, left, right)\n",
    "    \n",
    "    def assign(self, name, expr):\n",
    "        return ('=', str(name), expr)\n",
    "    \n",
    "    def block(self, *args):\n",
    "        return ('block', *args)\n",
    "    \n",
    "    def call(self, name, arg):\n",
    "        return (str(name), arg)\n",
    "    \n",
    "    def fn(self, name, argname, block):\n",
    "        return ('fn', str(name), str(argname), block)\n",
    "\n",
    "    \n",
    "tree = calc.parse('(123 + 1) + 3.14^2')\n",
    "SExprTransformer().transform(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Avaliador\n",
    "\n",
    "Agora que temos o parser e o transformer, vamos criar uma função que avalia o resultado de uma expressão matemática e retorna o valor associado. Tal função recebe uma árvore sintática na forma de uma S-expr e um dicionário de contexto que mapeia nomes a valores e retorna o resultado da expressão matemática correspondente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eval_sexpr(expr, ctx):\n",
    "    # Se a expressão já é um número, não é necessário fazer nada    \n",
    "    if isinstance(expr, (float, int)):\n",
    "        return expr\n",
    "    \n",
    "    # Caso seja uma string, olhamos no dicinário de contexto\n",
    "    elif isinstance(expr, str):\n",
    "        return ctx[expr]\n",
    "    \n",
    "    # Finalmente, deve ser uma S-expression. Separamos o primeiro termo\n",
    "    # dos argumentos e avaliamos o resultado condicionalmente\n",
    "    head, *args = expr\n",
    "    if head == '+':\n",
    "        x, y = args\n",
    "        return eval_sexpr(x, ctx) + eval_sexpr(y, ctx)\n",
    "    elif head == '-':\n",
    "        x, y = args\n",
    "        return eval_sexpr(x, ctx) - eval_sexpr(y, ctx)\n",
    "    elif head == '*':\n",
    "        x, y = args\n",
    "        return eval_sexpr(x, ctx) * eval_sexpr(y, ctx)\n",
    "    elif head == '/':\n",
    "        x, y = args\n",
    "        return eval_sexpr(x, ctx) / eval_sexpr(y, ctx)\n",
    "    elif head == '^':\n",
    "        x, y = args\n",
    "        return eval_sexpr(x, ctx) ** eval_sexpr(y, ctx)\n",
    "    elif head == '=':\n",
    "        name, value = args\n",
    "        value = eval_sexpr(value, ctx)\n",
    "        ctx[name] = value\n",
    "        return value\n",
    "    elif head == 'block':\n",
    "        value = 0.0\n",
    "        for arg in args:\n",
    "            value = eval_sexpr(arg, ctx)\n",
    "        return value\n",
    "    elif head == 'fn':\n",
    "        name, argname, block = args\n",
    "        \n",
    "        def fn(x):\n",
    "            local_ctx = ChainMap({}, ctx)\n",
    "            local_ctx[argname] = x\n",
    "            return eval_sexpr(block, local_ctx)\n",
    "        \n",
    "        ctx[name] = fn\n",
    "        return fn\n",
    "    elif head in ctx:\n",
    "        fn = ctx[head]\n",
    "        return fn(*(eval_sexpr(x, ctx) for x in args))\n",
    "    else:\n",
    "        raise ValueError('argumento inválido para S-expression: %r' % head)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testamos com um exemplo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Resultado: 15.0\n"
     ]
    }
   ],
   "source": [
    "tree = calc.parse('(1 + 2) + 3 * x')\n",
    "sexpr = SExprTransformer().transform(tree)\n",
    "value = eval_sexpr(sexpr, {'x': 4})\n",
    "\n",
    "print('Resultado:', value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A série de operações 1) análise sintática (parsing); 2) transformação para *S-expression*; 3) avaliação da *S-expression* com um dicionário de contexto pode ser facilmente automatizada com uma função:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate(expr, ctx=None):\n",
    "    if ctx is None:\n",
    "        ctx = {}\n",
    "    tree = calc.parse(expr)\n",
    "    sexpr = SExprTransformer().transform(tree)\n",
    "    value = eval_sexpr(sexpr, ctx)\n",
    "    return value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testamos ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42.0"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate('x + 1', {'x': 41})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculadora com passos\n",
    "\n",
    "Vamos modificar a nossa calculadora para que ela aceite atribuição de variáveis e consiga calcular uma sequência de expressões. Deste modo, será possível criar pequenos programas como:\n",
    "\n",
    "```\n",
    "x = 40;\n",
    "y = 2;\n",
    "x + y\n",
    "```\n",
    "\n",
    "### Gramática\n",
    "\n",
    "É possível reaproveitar boa parte da gramática utilizada anteriormente e acrescentar apeanas algumas regras para contemplar atribuição de variáveis e sequência de passos. Modifique a célula que define a gramática para contemplar as novas regras e rode os testes abaixo para verificar se foi implementado corretamente.\n",
    "\n",
    "**OBS:** Os testes assumem que o nome da regra de atribuição é \"assign\" e da regra de geração de um bloco de instruções de um programa é \"block\". Lembre-se de modificar a regra inicial para procurar por um programa e não uma expressão."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre>block\n",
       "  assign\n",
       "    x\n",
       "    number\t40\n",
       "  assign\n",
       "    y\n",
       "    number\t2\n",
       "  binop\n",
       "    name\tx\n",
       "    +\n",
       "    name\ty\n",
       "</pre>"
      ],
      "text/plain": [
       "Tree(block, [Tree(assign, [Token(NAME, 'x'), Tree(number, [Token(NUMBER, '40')])]), Tree(assign, [Token(NAME, 'y'), Tree(number, [Token(NUMBER, '2')])]), Tree(binop, [Tree(name, [Token(NAME, 'x')]), Token(PLUS_OP, '+'), Tree(name, [Token(NAME, 'y')])])])"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calc.parse('''\n",
    "x = 40;\n",
    "y = 2;\n",
    "x + y;\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parabéns!\n"
     ]
    }
   ],
   "source": [
    "# Teste para verificar se a as novas regras foram implementadas corretamente\n",
    "src = \"x = 1; x + 1\"\n",
    "expected = \"\"\"\n",
    "block\n",
    "  assign\n",
    "    x\n",
    "    number\t1\n",
    "  binop\n",
    "    name\tx\n",
    "    +\n",
    "    number\t1\n",
    "\"\"\"\n",
    "assert calc.parse(src).pretty() == expected.lstrip()\n",
    "print('Parabéns!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transformer\n",
    "\n",
    "As mudanças na gramática requerem algumas mudanças no transformer para lidar com as regras de \"program\" e \"assign\". Modifique a célula que define o SExprTransformer para incluir estas duas regras."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('block', ('=', 'x', 40.0), ('=', 'y', 2.0), ('+', 'x', 'y'))"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transformer = SExprTransformer()\n",
    "transformer.transform(calc.parse('''\n",
    "x = 40;\n",
    "y = 2;\n",
    "x + y\n",
    "'''))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parabéns!\n"
     ]
    }
   ],
   "source": [
    "# Teste para verificar se o transformer foi modificado corretamente\n",
    "src = \"x = 1; x + 1\"\n",
    "expected = (\n",
    "    'block', \n",
    "    ('=', 'x', 1),\n",
    "    ('+', 'x', 1),\n",
    ")\n",
    "transformer = SExprTransformer()\n",
    "assert transformer.transform(calc.parse(src)) == expected\n",
    "print('Parabéns!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Função eval\n",
    "\n",
    "Agora modificamos eval_sexpr para lidar com as duas novas regras. \n",
    "\n",
    "Podemos tratar a atribuição (regras do tipo \"assign\") simplesmente salvando o resultado do valor no lado direito a uma entrada no dicionário de contexto com o mesmo nome da variável do lado esquerdo. Isto pode ser feito alterando a estrutura de \"if\"s de eval_sexpr para aceitar regras que iniciam com um '='. Usamos a convenç~ao de assumir que o valor associado a um comando de atribuição corresponde à variável que acabou de ser salva.\n",
    "\n",
    "Já para implementar as regras do tipo \"block\", devemos executar a sequência de operaões dentro de um laço, avaliando cada comando com uma chamada recursiva a \"eval_expr\". Aqui, usamos a convenção que o valor de uma sequência de comandos é igual ao valor do último comando. Como todos os valores na nossa linguagem são numéricos, podemos assumir um valor de 0.0 a qualquer sequência vazia.\n",
    "\n",
    "Implemente as duas funcionalidades no códgo de \"eval_expr\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ctx: {'y': 2, 'x': 1}\n",
      "resultado: 3\n"
     ]
    }
   ],
   "source": [
    "ctx = {'y': 2}\n",
    "value = eval_sexpr(('block', ('=', 'x', 1), ('+', 'x', 'y')), ctx)\n",
    "print('ctx:', ctx)\n",
    "print('resultado:', value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parabéns!\n"
     ]
    }
   ],
   "source": [
    "# Teste para verificar se eval_sexpr foi modificado corretamente\n",
    "assert calculate(\"x = 1; x + 1\", {}) == 2\n",
    "print('Parabéns!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chamada de funções\n",
    "\n",
    "Vamos prosseguir de maneira similar à seção anterior para implementar uma calculadora que consiga chamar funções. A regra básica é que uma chamada de função possui a forma \"func(arg)\", onde func pode ser qualquer nome válido e arg pode ser qualquer expresssão válida. \n",
    "\n",
    "Uma expressão do tipo `sqrt(40 + 2)`, portanto, deve ser transformada para a *S-expression* ('sqrt', ('+', 40, 2)). Avaliamos esta expressão buscando o primeiro item da lista ('sqrt', neste caso) no dicionário de contexto, assumindo que o valor obtido se trata de uma função. Finalmente, usamos eval_sexpr para avaliar o argumento e chamamos a função com o resultado obtido para terminar a avaliação da chamada de função.\n",
    "\n",
    "Note que para isto funcionar, devemos passar todas as funções reconhecidas na linguagem dentro do dicionário de contexto.\n",
    "\n",
    "Implemente todos estes passos na gramática e verifique se funcionam nos testes abaixo.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Árvore sintática:\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre>block\n",
       "  assign\n",
       "    x\n",
       "    number\t40\n",
       "  binop\n",
       "    name\tx\n",
       "    +\n",
       "    call\n",
       "      sqrt\n",
       "      number\t4\n",
       "</pre>"
      ],
      "text/plain": [
       "Tree(block, [Tree(assign, [Token(NAME, 'x'), Tree(number, [Token(NUMBER, '40')])]), Tree(binop, [Tree(name, [Token(NAME, 'x')]), Token(PLUS_OP, '+'), Tree(call, [Token(NAME, 'sqrt'), Tree(number, [Token(NUMBER, '4')])])])])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S-expr: ('block', ('=', 'x', 40.0), ('+', 'x', ('sqrt', 4.0)))\n",
      "Resultado: 42.0\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "expr = 'x = 40; x + sqrt(4)'\n",
    "tree = calc.parse(expr)\n",
    "sexpr = SExprTransformer().transform(tree)\n",
    "\n",
    "print('Árvore sintática:')\n",
    "display(tree)\n",
    "print('S-expr:', sexpr)\n",
    "print('Resultado:', calculate(expr, {'sqrt': math.sqrt}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parabéns!\n"
     ]
    }
   ],
   "source": [
    "# Verifica se o resultado está correto\n",
    "\n",
    "expr = 'x = 40; x + sqrt(4)'\n",
    "tree = calc.parse(expr)\n",
    "sexpr = SExprTransformer().transform(tree)\n",
    "\n",
    "assert sexpr == ('block', ('=', 'x', 40.0), ('+', 'x', ('sqrt', 4.0)))\n",
    "assert calculate(expr, {'sqrt': math.sqrt}) == 42.0\n",
    "assert calculate(expr, {'sqrt': lambda x: x}) == 44.0\n",
    "print('Parabéns!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definição de funções\n",
    "\n",
    "Agora daremos um salto importante na nossa linguagem e permitiremos que os usuários definam as suas próprias funções. Uma função definida pelo usuário pode ser salva no dicionário de contexto e acessada normalmente se for invocada em um código posterior. A sintaxe proposta para isso é indicada abaixo:\n",
    "\n",
    "```\n",
    "fn double(x) {\n",
    "    y = x;\n",
    "    x + y\n",
    "};\n",
    "\n",
    "double(21)\n",
    "```\n",
    "\n",
    "(Lembre-se do ponto-vírgula depois da definição da função. É possível eliminá-lo, mas isso causaria mudanças relativamente grandes na gramática.)\n",
    "\n",
    "Assim como nos passos anteriores, crie a regra gramatical e o transformer que suporta esta nova funcionalidade na gramática. Os testes abaixos supõe que uma definição de função seria representada como `('fn' <nome>, <nome-argumento> <corpo>)`.\n",
    "\n",
    "**DICA:** lembre-se que Python permite criar funções dentro de funções. Desta forma, podemos criar a função a partir de uma expressão fn definindo uma função genérica associada ao bloco de comandos no corpo da função e associando o resultado ao seu nome no dicionário de contexto.\n",
    "\n",
    "**DICA 2:** Não se preocupe em implementar contexto ainda. Assim, se uma função recebe um argumento x, devemos tratá-lo como global e salvar o valor de x no dicionário de contexto. Na nossa linguagem, tratamos todas variáveis como se fossem globais."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Árvore:\n",
      " block\n",
      "  fn\n",
      "    double\n",
      "    x\n",
      "    block\n",
      "      assign\n",
      "        y\n",
      "        name\tx\n",
      "      binop\n",
      "        name\tx\n",
      "        +\n",
      "        name\ty\n",
      "  call\n",
      "    double\n",
      "    number\t21\n",
      "\n",
      "S-expr:\n",
      "('block',\n",
      " ('fn', 'double', 'x', ('block', ('=', 'y', 'x'), ('+', 'x', 'y'))),\n",
      " ('double', 21.0))\n",
      "Valor: 42.0\n"
     ]
    }
   ],
   "source": [
    "src = '''\n",
    "fn double(x) {\n",
    "    y = x;\n",
    "    x + y\n",
    "};\n",
    "\n",
    "double(21)\n",
    "'''\n",
    "\n",
    "tree = calc.parse(src)\n",
    "sexpr = SExprTransformer().transform(tree)\n",
    "\n",
    "print('Árvore:\\n', tree.pretty())\n",
    "print('S-expr:'); pprint(sexpr)\n",
    "print('Valor:', calculate(src))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parabéns!\n"
     ]
    }
   ],
   "source": [
    "# Testamos o código acima para verificar se a implementação é válida\n",
    "src = \"fn double(x) { 2 * x }; double(21)\"\n",
    "sexpr = SExprTransformer().transform(calc.parse(src))\n",
    "\n",
    "ctx = {}\n",
    "assert sexpr == ('block', ('fn', 'double', 'x', ('*', 2.0, 'x')), ('double', 21.0))\n",
    "assert calculate(src, ctx) == 42\n",
    "assert set(ctx) == {'x', 'double'} or set(ctx) == {'double'}, ctx\n",
    "print('Parabéns!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Controle do escopo\n",
    "\n",
    "O código anterior possui um problema sério no controle de escopo. Como todas as variáveis são globais, argumentos de funções e variáveis definidas dentro do escopo de uma função afetam o contexto de execução fora da função. Isto faz com que códigos como o abaixo produzam resultados não esperados, já que o argumento x da função conflita com a variável x do escopo global. \n",
    "\n",
    "```\n",
    "fn double(x) { x + x };\n",
    "x = 20;\n",
    "y = double(x + 1);\n",
    "x + y\n",
    "```\n",
    "\n",
    "O código avalia para 63 e não 62, como seria esperado. O motivo para isso é que a chamada de função double(x) modifica globalmente o valor desta variável. Este comportamento é bastante confuso e difere de como a grande maioria das linguagens de programação funciona.\n",
    "\n",
    "Para consertar este problema, é necessário criar uma hieraquia de contextos de execução de forma que quando uma função executa, ela altere apeans um escopo local, mas possa acessar as variáveis do escopo exterior para leitura, caso seja necessário. \n",
    "\n",
    "O Python possui uma implementação nativa de uma estrutura de dados ideal para isto: o ChainMap. Um ChainMap é formado por uma sequência de dicionários de forma que apenas o primeiro deles é escrito, mas caso um valor não seja encontrado no mesmo, ele busca em cada dicionário que forma a sequência. No caso abaixo,\n",
    "\n",
    "```python\n",
    "d1 = {'x': 1}\n",
    "d2 = {'y': 2}\n",
    "ctx = ChainMap(d1, d2)\n",
    "```\n",
    "\n",
    "ctx se comporta como um dicionário que modifica d1 caso façamos uma atribuição,\n",
    "\n",
    "```python\n",
    "ctx['z'] = 3\n",
    "pŕint(d1) # --> {'x': 1, 'z': 3}\n",
    "```\n",
    "e busca qualquer chave desconhecida em d2, caso ela não esteja presente em d1.\n",
    "\n",
    "```python\n",
    "print(ctx['y']) # --> 2\n",
    "```\n",
    "\n",
    "Podemos utilizar o ChainMap para fazer o controle de escopo fazendo uma pequena alteração na parte que lida com definições de funções em eval_expr(). Basta embrulhar o contexto dentro de um ChainMap e passar o contexto local para as chamadas dentro da função."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Resultado: 4.0\n",
      "Contexto: {'double': <function eval_sexpr.<locals>.fn at 0x7f0b9ff54200>}\n"
     ]
    }
   ],
   "source": [
    "ctx = {}\n",
    "value = calculate('fn double(x) {x + x}; double(2)', ctx)\n",
    "print('Resultado:', value)\n",
    "print('Contexto:', ctx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parabéns!\n"
     ]
    }
   ],
   "source": [
    "# Testamos o código acima para verificar se a implementação é válida\n",
    "ctx = {}\n",
    "src = \"fn double(x) { 2 * x }; double(21)\"\n",
    "assert calculate(src, ctx) == 42\n",
    "assert 'x' not in ctx, 'ainda está contaminando o escopo global!'\n",
    "print('Parabéns!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Outros desafios\n",
    "\n",
    "Se você chegou até aqui, tente implementar mais algumas lacunas que estão faltando na nossa linguagem:\n",
    "\n",
    "1. Implementar funções que suportam mais de um argumento.\n",
    "2. Você consegue encurtar eval_sexpr() tratando os operadores +, -, *, etc como funções regulares?. Uma dica: utilize as funções add, sub, mul e truediv do módulo operator para simplificar mais ainda a sua implementação.\n",
    "3. Suportar operadores de comparação e operadores lógicos. Operadores de comparação normalmente possuem uma precedência menor que os aritméticos, mas maior que operadores lógicos como (and, or, not). Escolha como será a gramática da sua linguagem.\n",
    "4. Tente eliminar o ponto-vírgula obrigatório do fim das expressões. \n",
    "5. Implementar condicionais usando \"if/elif/else\" ou a sintaxe que achar mais interessante.\n",
    "6. Implemente laços (while/for)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}