O lis.py de Norvig

norvigs-lispy-pybr.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8b942f59",
   "metadata": {},
   "source": [
    "# O `lis.py` de Norvig\n",
    "\n",
    "\n",
    "![Norvig's lispy](lispy.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d21782ea",
   "metadata": {},
   "source": [
    "Contents:\n",
    "\n",
    "* [Introdução](#Introdução)\n",
    "* [Sintaxe de Scheme](#Sintaxe-de-Scheme)\n",
    "* [Imports e tipos](#Imports-e-tipos)\n",
    "* [O parser](#O-parser)\n",
    "  * [Exercício 0](#Exercício-0)\n",
    "* [Ambiente básico para aritmética](#Ambiente-básico-para-aritmética)\n",
    "* [Uma calculadora](#Uma-calculadora)\n",
    "* [Execução não interativa](#Execução-não-interativa)\n",
    "  * [Exercício 1](#Exercício-1)\n",
    "  * [Exercício 2](#Exercício-2)\n",
    "  * [Exercício 3](#Exercício-3)\n",
    "* [User defined procedures](#User-defined-procedures)\n",
    "* [Um ambiente mais completo](#Um-ambiente-mais-completo)\n",
    "* [`Procedure`: uma clase que representa uma _closure_](#Procedure:-uma-classe-que-representa-uma-closure)\n",
    "* [Avaliador com `lambda`, `if` e `quote`](#Avaliador-com-lambda,-if-e-quote)\n",
    "* [O REPL](#O-REPL)\n",
    "* [Exemplos](#Exemplos)\n",
    "* [Açúcar Sintático](#Açúcar-Sintático)\n",
    "  * [Exercício para casa](#Exercício-para-casa)\n",
    "\n",
    "> **LICENÇAS**:<br>\n",
    "  Código © 2010-2018 Peter Norvig, [MIT License](https://github.com/fluentpython/lispy/blob/main/LICENSE)<br>\n",
    "  Texto © 2022 Luciano Ramalho, [Creative Commons Attribution 4.0 International](https://creativecommons.org/licenses/by/4.0/)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21fc7c40",
   "metadata": {},
   "source": [
    "## Introdução\n",
    "\n",
    "[Peter Norvig](https://norvig.com/) da universidade Stanford criou\n",
    "[`lis.py`](https://github.com/norvig/pytudes/blob/main/py/lis.py):\n",
    "um interpretador em 132 linhas de código Python legível,\n",
    "para parte da linguagem Scheme—um dialeto de Lisp.\n",
    "\n",
    "Porque você deveria estudar `lis.py`?\n",
    "Para mim esses foram alguns motivos:\n",
    "\n",
    "* Depois de estudar como funciona um interpretador,\n",
    "passei a entender mais precisamente como funcionam Python e linguagens em geral—interpretadas ou compiladas.\n",
    "\n",
    "* A simplicidade de Scheme é uma aula magna de design de linguagens.\n",
    "\n",
    "* `lis.py` é um lindo exemplo de código Python idiomático.\n",
    "\n",
    "Norvig descreve `lis.py` em um texto intitulado.\n",
    "[(How to Write a (Lisp) Interpreter (in Python))](https://norvig.com/lispy.html). Altamente recomendado.\n",
    "\n",
    "Antes de examinar o código do interpretador em Python,\n",
    "vamos ver um pouco de Scheme—caso você nunca tenha visto essa linguagem ou Lisp anteriormente."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ece6da6",
   "metadata": {},
   "source": [
    "## Sintaxe de Scheme\n",
    "\n",
    "Todo código Scheme é formado por expressões.\n",
    "Não existem operadores infixos:\n",
    "todas as expressões usam notação prefixa como\n",
    "`(+ x 13)` em vez de `x + 13`.\n",
    "A mesma notação prefixa é usada para chamadas de funções—ex. `(gcd x 13)`—e\n",
    "instruções especiais—ex. `(define x 13)`, que corresponde à\n",
    "instrução de atribuição em Python: `x = 13`.\n",
    "\n",
    "A notação usada em Scheme e na maioria dos dialetos de Lisp (como Clojure) é chamada de _S-expression_ ou _expressão-S_.\n",
    "\n",
    "Eis um exemplo simples em Scheme, para calcular o máximo divisor comum:\n",
    "\n",
    "\n",
    "```lisp\n",
    "(define (resto m n)\n",
    "    (- m (* n (quotient m n))))\n",
    "\n",
    "(define (mdc m n)\n",
    "    (if (= n 0)\n",
    "        m\n",
    "        (mdc n (resto m n))))\n",
    "\n",
    "(display (mdc 18 45))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "180719db",
   "metadata": {},
   "source": [
    "O mesmo algoritmo em Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a60a43db",
   "metadata": {},
   "outputs": [],
   "source": [
    "def resto(m, n):\n",
    "    return m - (m // n * n)\n",
    "\n",
    "def mdc(m, n):\n",
    "    if n == 0:\n",
    "        return m\n",
    "    else:\n",
    "        return mdc(n, resto(m, n))\n",
    "\n",
    "print(mdc(18, 45))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cf3bc83",
   "metadata": {},
   "source": [
    "> **DICA**: Clique na célula acima para selecioná-la, então tecle `【CTRL】【ENTER】` para executá-la.\n",
    "<br>O resultado aparecerá abaixo da célula.\n",
    "\n",
    "Scheme não tem estruturas de laço como `while` ou `for`.\n",
    "Iteração é feita através de recursão.\n",
    "Note como não há atribuições nos exemplos em Scheme ou Python acima.\n",
    "O uso extensivo de recursão e o uso reduzido de atribuição\n",
    "são duas características típicas de programação em um estilo funcional.\n",
    "\n",
    "Em Python idiomático eu usaria o operador `%` em vez de reinventar `resto`,\n",
    "e seria mais eficiente usar um laço `while` do que recursão.\n",
    "Mas eu queria mostrar duas definições de funções, e\n",
    "que os exemplos ficassem parecidos para ajudar você a ler o código em Scheme.\n",
    "\n",
    "Agora vamos estudar o código de uma versão de `lis.py` para Python 3.7.\n",
    "O código completo com testes para Python 3.10 você pode encontrar no diretório\n",
    "[18-with-match/lispy/py3.10/](https://github.com/fluentpython/example-code-2e/tree/master/18-with-match/lispy/py3.10/)\n",
    "do repositório [fluentpython/example-code-2e](https://github.com/fluentpython/example-code-2e)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dcbfcb6",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Imports e tipos\n",
    "\n",
    "O código escrito pelo Norvig não usa anotações de tipo, adicionei as anotações e fiz mais algumas pequenas mudanças.\n",
    "\n",
    "Esse notebook usa Python 3.7 para rodar no [Binder](https://mybinder.org/), portanto precisamos importar alguns tipos de coleções do módulo `typing`.\n",
    "\n",
    "> **DICA**: Clique na célula abaixo para selecioná-la e então aperte `【SHIFT】【ENTER】` para executá-la e selecionar a próxima célula.<br>Use `【CTRL】【ENTER】` para executar a célula e manter ela selecionada.<br>Use esses comandos para executar as células conforme você segue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51ae4ba2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "assert sys.version_info >= (3, 7), f'Esperado Python ≥ 3.7; instalado: {sys.version}'\n",
    "sys.version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ca108b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "################ lis.py: Scheme Interpreter in Python 3.10\n",
    "## (c) Peter Norvig, 2010-18; See http://norvig.com/lispy.html\n",
    "## Type hints and minor additions by Luciano Ramalho\n",
    "\n",
    "import math\n",
    "import operator as op\n",
    "from collections import ChainMap\n",
    "from itertools import chain\n",
    "from typing import Any, NoReturn\n",
    "from typing import Union, List, MutableMapping, Optional, Iterator\n",
    "\n",
    "Symbol = str\n",
    "Atom = Union[float, int, Symbol]\n",
    "Expression = Union[Atom, List]\n",
    "\n",
    "Environment = MutableMapping[Symbol, object]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e315ae4",
   "metadata": {},
   "source": [
    "Os tipos são definidos são:\n",
    "\n",
    "`Symbol`: Apenas um apelido para o tipo `str`.\n",
    "Em _list.py_, instâncias de `Symbol` são usadas como identificadores;\n",
    "não há um tipo string com operaçoẽs como fatiamento, particionamento com `split` etc.\n",
    "\n",
    "`Atom`: Elemento sintático simples: um número ou um `Symbol`.\n",
    "Um átomo é o contrário de uma estrutura composta de diversas partes como uma lista.\n",
    "\n",
    "`Expression`: Programas em Scheme são formados por expressões feitas com átomos e listas, possivelmente aninhadas.\n",
    "\n",
    "> **NOTA**: O segundo interpretador escrito por Norvig,\n",
    "[`lispy.py`](https://github.com/fluentpython/example-code-2e/blob/master/18-with-match/lispy/original/lispy.py),\n",
    "suporta string como um tipo de dado, assim como também aceita funcionalidades avançadas como macros de sintaxe,\n",
    "chamadas de cauda eficientes e _continuations_.\n",
    "No entanto, `lispy.py` é quase três vezes mais longo do que `lis.py`, e mais difícil de entender."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59b6d725",
   "metadata": {},
   "source": [
    "## O parser\n",
    "\n",
    "O parser de Norvig são 36 linhas de código que demonstram o poder de Python aplicado ao tratamento de\n",
    "sintaxes recursivas simples de S-expression—sem comentários, tipo string, macros, e outros recursos de Scheme padrão que complicam a análise léxica (esses recursos são implementadas em `lispy.py`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "794bdcb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse(program: str) -> Expression:\n",
    "    \"Read a Scheme expression from a string.\"\n",
    "    return read_from_tokens(tokenize(program))\n",
    "\n",
    "def tokenize(s: str) -> List[str]:\n",
    "    \"Convert a string into a list of tokens.\"\n",
    "    return s.replace('(', ' ( ').replace(')', ' ) ').split()\n",
    "\n",
    "def read_from_tokens(tokens: List[str]) -> Expression:\n",
    "    \"Read an expression from a sequence of tokens.\"\n",
    "    if len(tokens) == 0:\n",
    "        raise SyntaxError('unexpected EOF while reading')\n",
    "    token = tokens.pop(0)\n",
    "    if '(' == token:\n",
    "        exp = []\n",
    "        while tokens[0] != ')':\n",
    "            exp.append(read_from_tokens(tokens))\n",
    "        tokens.pop(0)  # discard ')'\n",
    "        return exp\n",
    "    elif ')' == token:\n",
    "        raise SyntaxError('unexpected )')\n",
    "    else:\n",
    "        return parse_atom(token)\n",
    "\n",
    "def parse_atom(token: str) -> Atom:\n",
    "    \"Numbers become numbers; every other token is a symbol.\"\n",
    "    try:\n",
    "        return int(token)\n",
    "    except ValueError:\n",
    "        try:\n",
    "            return float(token)\n",
    "        except ValueError:\n",
    "            return Symbol(token)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abae6abd",
   "metadata": {},
   "source": [
    "A função principal desse grupo é `parse`, que toma o código-fonte de uma S-expression como uma `str`\n",
    "e devolve um objeto `Expression`: um `Atom` ou `list` que pode conter mais átomos e listas aninhadas.\n",
    "\n",
    "O primeiro estágio de um parser é a análise léxica: identificar onde começam e terminam as \"palavras\" da linguagem, conhecidas tecnicamente como _tokens_ ou _itens léxicos_. Isso é feito pela função `tokenize`.\n",
    "\n",
    "Norvig usa um truque esperto em `tokenize`:\n",
    "ele coloca espaços antes e depois de cada parênteses no código-fonte, e depois quebra com `.split()`,\n",
    "resultando em uma lista de tokens com `(` e `)`\n",
    "como itens distintos. Por exemplo, `(f 1)` é transformada em uma lista com quatro itens: `['(', 'f', '1', ')']`.\n",
    "\n",
    "Esse atalho funciona porque não existe um tipo de string no pequeno Scheme do _lis.py_,\n",
    "então todo `(` ou `)` é um delimitador de expressão.\n",
    "\n",
    "As regras de análise léxica para esse subconjunto do Scheme são simples:\n",
    "\n",
    "1. Um token que se parece com um número é convertido em `float` ou `int`.\n",
    "2. Qualquer outra coisa que não for `(` ou `)` é entendida como `Symbol`—uma `str` a ser usada como identificador. Isso inclui código fonte como `+`, `set` e `make-counter` que são identificadores válidos em Scheme mas não em Python.\n",
    "3. Expressões dentro de `(` e `)` são recursivamente parseadas como listas contendo atoms ou listas aninhadas que podem conter atoms e mais listas aninhadas.\n",
    "\n",
    "O código de parsing recursivo está em `read_from_tokens`, que recebe uma lista de itens léxicos e devolve listas e/ou átomos. Em uma primeira leitura, vale a pena considerar `read_from_tokens` como uma caixa preta, e se concentrar na função de alto nível `parse`. Veja alguns exemplos com `parse`:\n",
    "\n",
    "> **DICA**: Para executar o código em cada uma das células e selecionar a próxima, use `【SHIFT】【ENTER】`.<br>\n",
    "Se acontecer `NameError: name 'parse' is not defined`, use o comando ***Cell > Run All Above*** do menu para executar as células acima, incluindo aquela onde está a definição da função `parse`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c4d003e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('1.5')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c53c548a",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('ni!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ad474ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('''\n",
    "  (define double\n",
    "    (lambda (n)\n",
    "      (* n 2)))\n",
    "''')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20680ccb",
   "metadata": {},
   "source": [
    "Usando a terminologia do interpretador Python, a saída de `parse` é uma **AST** (*Abstract Syntax Tree* ou *Árvore Sintática Abstrata*):\n",
    "uma representação conveniente do programa Scheme como listas aninhadas formando uma estrutura em forma de árvore,\n",
    "onde a lista mais externa é o tronco, as listas internas são ramos e os átomos são folhas.\n",
    "\n",
    "Veja a AST do exemplo `(define double (lambda (n) (* n 2)))` como um diagrama em árvore:\n",
    "\n",
    "```\n",
    "                              '*'  'n'   2\n",
    "                        'n'    └────┼────┘\n",
    "                         │          │\n",
    "           'lambda'     [ ]        [ ]\n",
    "               └─────────┼──────────┘\n",
    "                         │\n",
    "'define'   'double'     [ ]\n",
    "    └─────────┼──────────┘\n",
    "              │\n",
    "             [ ]\n",
    "```\n",
    "\n",
    "A árvore acima corresponde à AST `['define', 'double', ['lambda', ['n'], ['*', 'n', 2]]]`.<br>\n",
    "Note que todos os elementos da AST são objetos da linguagem Python.\n",
    "\n",
    "### Exercício 0\n",
    "\n",
    "Substitua as reticências `...` com a AST correspondente à cada S-expression, para obter o resultado `True`.\n",
    "Para rodar o código na célula, tecle `【CTRL】【ENTER】`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47562dfd",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('9') == ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32a958d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('x/y') == ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "adbabd10",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('(+ 3 7)') == ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a6bee07c",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('(* c (/ 9 5))') == ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a05d152b",
   "metadata": {},
   "outputs": [],
   "source": [
    "parse('(+ 32 (* (/ 9 5) c ))') == ..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "612a8b5c",
   "metadata": {},
   "source": [
    "## Ambiente básico para aritmética\n",
    "\n",
    "A função `standard_env()` constrói e devolve um `Environment` carregado\n",
    "com funções pré definidas, similar ao módulo `__builtins__` do Python que está sempre disponível."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0ad7b2b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def standard_env() -> Environment:\n",
    "    \"An environment for an s-expression calculator.\"\n",
    "    env: Environment = {}\n",
    "    env.update(vars(math))   # sin, cos, sqrt, pi, ...\n",
    "    env.update(\n",
    "        {\n",
    "            '+': op.add,\n",
    "            '-': op.sub,\n",
    "            '*': op.mul,\n",
    "            '/': op.truediv,\n",
    "            'quotient': op.floordiv,\n",
    "            '>': op.gt,\n",
    "            '<': op.lt,\n",
    "            '>=': op.ge,\n",
    "            '<=': op.le,\n",
    "            '=': op.eq,\n",
    "            'abs': abs,\n",
    "            'begin': lambda *x: x[-1],\n",
    "            'eq?': op.is_,\n",
    "            'equal?': op.eq,\n",
    "            'max': max,\n",
    "            'min': min,\n",
    "            'not': op.not_,\n",
    "            'number?': lambda x: isinstance(x, (int, float)),\n",
    "            'procedure?': callable,\n",
    "            'round': round,\n",
    "            'symbol?': lambda x: isinstance(x, Symbol),\n",
    "        }\n",
    "    )\n",
    "    return env"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c62f7988",
   "metadata": {},
   "source": [
    "O mapeamento `env` é carregado com:\n",
    "\n",
    "* todas as funções do módulo `math` do Python;\n",
    "* operadores selecionados do módulo `op` do Python;\n",
    "* simples mas poderosas funções construídas com `lambda` do Python;\n",
    "* built-ins do Python renomeados, por exemplo `callable` como `procedure?` ou diretamente mapeados como `round`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b6e3556",
   "metadata": {},
   "source": [
    "## Uma calculadora\n",
    "\n",
    "A primeira versão da função `evaluate` trata expressões com funções embutidas e váriavies definidas pela usuária. \n",
    "\n",
    "> **NOTA**: o parser de Norvig é simples e sólido, mas seu avaliador é simples e frágil. Ele omitiu a verificação de erros para manter a lógica simples de ser acompanhada. Nas palavras dele: \"Lispy não tenta detectar, reportar razoavelmente, ou se recuperar de erros. Lispy espera que o programador seja perfeito.\" ([fonte](https://norvig.com/lispy.html))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6845ada",
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate(x: Expression, env: Environment) -> Any:\n",
    "    \"Evaluate an expression in an environment.\"\n",
    "    if isinstance(x, Symbol):                    # variable reference\n",
    "        return env[x]\n",
    "    elif not isinstance(x, list):                # constant literal\n",
    "        return x\n",
    "    elif x[0] == 'define':                       # (define var exp)\n",
    "        _, var, exp = x\n",
    "        env[var] = evaluate(exp, env)\n",
    "    else:                                        # (proc arg...)\n",
    "        proc_exp, *args = x\n",
    "        proc = evaluate(proc_exp, env)\n",
    "        arg_values = [evaluate(exp, env) for exp in args]\n",
    "        return proc(*arg_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbf0725f",
   "metadata": {},
   "source": [
    "Execute esses exemplos para ver o `evaluate` em ação.\n",
    "\n",
    "Um quadrado curioso:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61807c9a",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluate(parse('(* 11111 11111)'), standard_env())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ae03efd",
   "metadata": {},
   "source": [
    "Se existem 876 candidatas e 123 foram aprovadas, que porcentagem foi aprovada?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57d109ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluate(parse('(* (/ 123 876) 100)'), standard_env())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9ae6c8d",
   "metadata": {},
   "source": [
    "Agora vamos estudar cada parte do `if/elif/...` em `evaluate`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d54d2faf",
   "metadata": {},
   "source": [
    "### Avaliar símbolo\n",
    "\n",
    "```python\n",
    "    if isinstance(x, Symbol):\n",
    "        return env[x]\n",
    "```\n",
    "\n",
    "Se a expressão é um `Symbol`, então obtenha seu valor no ambiente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97e9a37f",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluate('pi', standard_env())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9543338d",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluate('+', standard_env())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5fb90e09",
   "metadata": {},
   "source": [
    "### Avaliar outros átomos\n",
    "\n",
    "```python\n",
    "    elif not isinstance(x, list):\n",
    "        return x\n",
    "```\n",
    "\n",
    "Se a expressão não é `list` e nem `Symbol` (devido à verificação anterior), então assuma que é uma constante literal cujo valor é ela própria. Simplesmente devolva-a. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a1299e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluate(1.5, standard_env())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dda1cda",
   "metadata": {},
   "source": [
    "### Evaluate `(define var exp)`\n",
    "\n",
    "```python\n",
    "    elif x[0] == 'define':\n",
    "        _, var, exp = x\n",
    "        env[var] = evaluate(exp, env)\n",
    "```\n",
    "\n",
    "Se a expressão é uma lista começando com a palavra reservada `define`, deveria ser seguida por um `Symbol` e uma `Expression`. Recursivamente avalie a expressão no ambiente e armazene o resultado em `env` usando o `Symbol` como chave."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f7a97338",
   "metadata": {},
   "outputs": [],
   "source": [
    "env = standard_env()\n",
    "evaluate(parse('(define answer (* 7 6))'), env)\n",
    "env['answer']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f0b21f0",
   "metadata": {},
   "source": [
    "### Avaliar chamada de função `(proc arg…)`\n",
    "\n",
    "```python\n",
    "    else:\n",
    "        proc_exp, *args = x\n",
    "        proc = evaluate(proc_exp, env)\n",
    "        arg_values = [evaluate(exp, env) for exp in args]\n",
    "        return proc(*arg_values)\n",
    "```\n",
    "\n",
    "Se a expressão é uma `list` que não começa com uma palavra reservada, então: \n",
    "\n",
    "1. Avalie a primeira expressão—seu valor deve ser um procedimento (_procedure_ é o termo usado na comunidade Scheme; na comunidade Python dizemos _função_).\n",
    "2. Avalie as expressões restantes (os valores dos argumentos).\n",
    "3. Chame a procedure passando os valores dos argumentos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f76a2aab",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluate(['quotient', 8, 3], standard_env())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44cc93f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluate(['*', ['/', 123, 876], 100], standard_env())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "574d9ad6",
   "metadata": {},
   "source": [
    "`evaluate` consegue processar expressões profundamentes aninhadas, mas somente uma expressão no nível mais alto. Para agrupar várias expressões, use a função `(begin...)`. Todos os argumentos após o `begin` são avaliados antes que `begin` seja chamada, e `begin` devolve o valor do último argumento. Por exemplo: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67d8f4c6",
   "metadata": {},
   "outputs": [],
   "source": [
    "env = standard_env()\n",
    "percent = \"\"\"\n",
    "(begin\n",
    "  (define a 126)\n",
    "  (define b (* 6 50))\n",
    "  (* (/ a b) 100)\n",
    ")\n",
    "\"\"\"\n",
    "evaluate(parse(percent), env)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce17a2de",
   "metadata": {},
   "source": [
    "Após rodar o código acima, `env` agora possui as variáveis `a` e `b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7181cd14",
   "metadata": {},
   "outputs": [],
   "source": [
    "env['a'], env['b']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "552e8d1e",
   "metadata": {},
   "source": [
    "Para avaliar um programa inteiro, use a função `run()`, descrita a seguir."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffae2ec7",
   "metadata": {},
   "source": [
    "## Execução não-interativa\n",
    "\n",
    "As funções a seguir aceitam o código fonte de um programa em Scheme como uma string formada por uma sequência de S-expressions e as executam em sequência."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c9e85e79",
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_lines(source: str, env: Optional[Environment] = None) -> Iterator[Any]:\n",
    "    global_env: Environment = ChainMap({}, standard_env())\n",
    "    if env is not None:\n",
    "        global_env.update(env)\n",
    "    tokens = tokenize(source)\n",
    "    while tokens:\n",
    "        exp = read_from_tokens(tokens)\n",
    "        yield evaluate(exp, global_env)\n",
    "\n",
    "\n",
    "def run(source: str, env: Optional[Environment] = None) -> Any:\n",
    "    for result in run_lines(source, env):\n",
    "        pass\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d36b089f",
   "metadata": {},
   "source": [
    "Com `run()` não precisamos de `(begin …)` para avaliar múltiplas expressões de uma vez só—mas\n",
    "`begin` ainda é útil em outras situações."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbf87e49",
   "metadata": {},
   "outputs": [],
   "source": [
    "porcento = \"\"\"\n",
    "(define a 126)\n",
    "(define b (* 6 50))\n",
    "(* (/ a b) 100)\n",
    "\"\"\"\n",
    "run(porcento)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4eaa71c1",
   "metadata": {},
   "source": [
    "### Exercício 1\n",
    "\n",
    "Essa é a fórmula para converter temperaturas de Celsius para Fahrenheit:\n",
    "\n",
    "`f = (9 / 5) * c + 32`\n",
    "\n",
    "Eis o código para converter 20°C para °F:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d491e977",
   "metadata": {},
   "outputs": [],
   "source": [
    "c_to_f = \"\"\"\n",
    "(define c 20)\n",
    "(+ 32 (* c (/ 9 5)))\n",
    "\"\"\"\n",
    "run(c_to_f)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01cfbf12",
   "metadata": {},
   "source": [
    "A função inversa é:\n",
    "\n",
    "`c = (f − 32) * 5 / 9`\n",
    "\n",
    "No código abaixo, substitua `(+ 1 2)` pela expressão correta para converter 68°F para °C."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "772fb5e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "f_to_c = \"\"\"\n",
    "(define f 68)\n",
    "(+ 1 2)\n",
    "\"\"\"\n",
    "run(f_to_c) == 20"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76bb8d47",
   "metadata": {},
   "source": [
    "### Exercicio 2\n",
    "\n",
    "O módulo `math` de Python inclui uma função `factorial`, que é parte do ambiente criado por `standard_env()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3f43342",
   "metadata": {},
   "outputs": [],
   "source": [
    "run('(factorial 10)')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fabf2d58",
   "metadata": {},
   "source": [
    "A linguagem Scheme aceita `!` como um identificador. Sua tarefa é fazer `factorial()` de Python ficar disponível através do símbolo `!` em Scheme.\n",
    "\n",
    "**Passo 2.1** Descomente a expressão abaixo e execute para ver o erro. Veja para a última linha da saída do erro. Qual é o erro? Você entende porque esse é o erro?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3f689d04",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run('(! 10)') == 3628800"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3089d1e0",
   "metadata": {},
   "source": [
    "**Passo 2.2.** Edite a função `standard_env` acima para adicionar uma entrada para `'!'`,\n",
    "mapeando para a função `math.factorial` de Python.\n",
    "\n",
    "**Passo 2.3.** Execute a expressão acima para confirmar que o resultado é `True`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed1188ff",
   "metadata": {},
   "source": [
    "### Exercício 3\n",
    "\n",
    "Em um Scheme padrão, o operador `+` é variádico, ou seja, aceita qualquer quantidade de argumentos.\n",
    "Com 0 argumentos, `(+)` retorna `0`; caso contrário retorna a soma de todos os argumentos.\n",
    "\n",
    "**Step 3.1.** Descomente a expressão abaixo e execute para ver o erro. O erro faz sentido para você?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63cacb62",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run('(= 10 (+ 1 2 3 4))')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5407e71a",
   "metadata": {},
   "source": [
    "**Passo 3.2.** Edite a função `standard_env` acima para reimplementar o `+`, fazendo a expressão acima devolver `True`.\n",
    "\n",
    "> **DICA 3.2.1**: Escondida abaixo está uma versão variável do `sum` do Python. Considere resolver o exercício sem revelar a dica. Para revelar o código, descomente a linha do `print()` e execute a célula.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4db59253",
   "metadata": {},
   "outputs": [],
   "source": [
    "from base64 import b64decode\n",
    "blob = (b'ZGVmIHZhcmlhZGljX3N1bSgqYXJncyk6CiAgICByZXR1cm4g'\n",
    "        b'c3VtKGFyZ3MpCgp2YXJpYWRpY19zdW0oMSwgMiwgMywgNCk=')\n",
    "# print(b64decode(blob).decode('utf8'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6443a39a",
   "metadata": {},
   "source": [
    "> **DICA 3.2.2**: A seguir, a mesma função em uma única linha do Python. Tente resolver o exercício sem revelar a dica. Para revelar, descomente a linha do `print()` e execute a célula."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "225128be",
   "metadata": {},
   "outputs": [],
   "source": [
    "blob = b'ZiA9IGxhbWJkYSAqYXJnczogc3VtKGFyZ3MpCmYoMSwgMiwgMywgNCk='\n",
    "# print(b64decode(blob).decode('utf8'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9150d11b",
   "metadata": {},
   "source": [
    "## Um ambiente mais completo"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e396b310",
   "metadata": {},
   "source": [
    "Esta nova versão de `standard_env()` define funções para trabalhar com listas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c7e2a40f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def standard_env() -> Environment:\n",
    "    \"An environment with some Scheme standard procedures.\"\n",
    "    env: Environment = {}\n",
    "    env.update(vars(math))   # sin, cos, sqrt, pi, ...\n",
    "    env.update(\n",
    "        {\n",
    "            '+': op.add,\n",
    "            '-': op.sub,\n",
    "            '*': op.mul,\n",
    "            '/': op.truediv,\n",
    "            'quotient': op.floordiv,\n",
    "            '>': op.gt,\n",
    "            '<': op.lt,\n",
    "            '>=': op.ge,\n",
    "            '<=': op.le,\n",
    "            '=': op.eq,\n",
    "            'abs': abs,\n",
    "            'append': lambda *args: list(chain(*args)),\n",
    "            'apply': lambda proc, args: proc(*args),\n",
    "            'begin': lambda *x: x[-1],\n",
    "            'car': lambda x: x[0],\n",
    "            'cdr': lambda x: x[1:],\n",
    "            'cons': lambda x, y: [x] + y,\n",
    "            'eq?': op.is_,\n",
    "            'equal?': op.eq,\n",
    "            'filter': lambda *args: list(filter(*args)),\n",
    "            'length': len,\n",
    "            'list': lambda *x: list(x),\n",
    "            'list?': lambda x: isinstance(x, list),\n",
    "            'map': lambda *args: list(map(*args)),\n",
    "            'max': max,\n",
    "            'min': min,\n",
    "            'not': op.not_,\n",
    "            'null?': lambda x: x == [],\n",
    "            'number?': lambda x: isinstance(x, (int, float)),\n",
    "            'procedure?': callable,\n",
    "            'round': round,\n",
    "            'symbol?': lambda x: isinstance(x, Symbol),\n",
    "        }\n",
    "    )\n",
    "    return env"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c18c244",
   "metadata": {},
   "source": [
    "## `Procedure`: uma classe que representa uma _closure_\n",
    "\n",
    "A próxima melhoria do `evaluate()` será incluir `(lambda …)` para permitir que\n",
    "usuários definam funções, ou _procedimentos_ no jargão de Scheme.\n",
    "Para implementar `lambda`, precisamos de uma classe que represente um procedimento."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f9e47e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Procedure:\n",
    "    \"\"\"A user-defined Scheme procedure.\"\"\"\n",
    "\n",
    "    def __init__(self, parms: List[Symbol], body: Expression, env: Environment) -> None:\n",
    "        self.parms = parms\n",
    "        self.body = body\n",
    "        self.env = env\n",
    "\n",
    "    def __call__(self, *args: Expression) -> Any:\n",
    "        local_env = dict(zip(self.parms, args))\n",
    "        env: Environment = ChainMap(local_env, self.env)\n",
    "        return evaluate(self.body, env)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4819a394",
   "metadata": {},
   "source": [
    "A classe `Procedure` poderia muito bem ser nomeada `Closure`,\n",
    "porque é isso o que ela representa:<br>\n",
    "uma definição de função junto com um ambiente capturado quando a função é definida.\n",
    "\n",
    "Os parâmetros obrigatórios para criar uma `Procedure` são:\n",
    "\n",
    "`params`: uma lista de símbolos que representam os nomes dos parâmetros da função.\n",
    "A lista pode estar vazia.\n",
    "\n",
    "`body`: o corpo da função como uma expressão que será interpretada quando a função for chamada.\n",
    "\n",
    "`env`: o ambiente onde a função é criada. Isso é o torna o procedimento uma\n",
    "[*closure*](https://en.wikipedia.org/wiki/Closure_(computer_programming)) ou\n",
    "[*clausura*](https://pt.wikipedia.org/wiki/Clausura_(ci%C3%AAncia_da_computa%C3%A7%C3%A3o)) (o termo em PT não é muito usado, mas o [artigo na Wikipédia](https://pt.wikipedia.org/wiki/Clausura_(ci%C3%AAncia_da_computa%C3%A7%C3%A3o)) é útil).\n",
    "\n",
    "O método `__init__` apenas guarda os argumentos recebidos. Nenhum deles é avaliado quando a função é definida.\n",
    "\n",
    "O ambiente `self.env` é usado quando a função é chamada para fornecer os valores de\n",
    "[variáveis não-locais](https://en.wikipedia.org/wiki/Non-local_variable):<br>\n",
    "variáveis que aparecem no corpo da função mas que não são parâmetros ou variáveis locais.\n",
    "\n",
    "Vamos criar uma `Procedure` \"na mão\" para ver como funciona:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c947663",
   "metadata": {},
   "outputs": [],
   "source": [
    "dobro = Procedure(['n'], ['*', 'n', 2], standard_env())\n",
    "dobro(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a3a72fa",
   "metadata": {},
   "source": [
    "## Avaliador com `lambda`, `if` e `quote`\n",
    "\n",
    "Para transformar a calculadora em um subconjunto digno da linguagem Scheme,\n",
    "precisamos permitir funções definidas pelo usuário,\n",
    "condicionais e a instrução `(quote …)` para lidar com expressões\n",
    "como dados ao invés de interpretá-las.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0a3c62e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate(x: Expression, env: Environment) -> Any:\n",
    "    \"\"\"Evaluate an expression in an environment.\"\"\"\n",
    "    if isinstance(x, str):                       # variable reference\n",
    "        return env[x]\n",
    "    elif not isinstance(x, list):                # constant literal\n",
    "        return x\n",
    "    elif x[0] == 'define':                       # (define var exp)\n",
    "        _, var, exp = x\n",
    "        env[var] = evaluate(exp, env)\n",
    "    elif x[0] == 'lambda':                       # (lambda (var...) body)\n",
    "        _, parms, body = x\n",
    "        return Procedure(parms, body, env)\n",
    "    elif x[0] == 'quote':                        # (quote exp)\n",
    "        _, exp = x\n",
    "        return exp\n",
    "    elif x[0] == 'if':                           # (if test consequence alternative)\n",
    "        _, test, consequence, alternative = x\n",
    "        if evaluate(test, env):\n",
    "            return evaluate(consequence, env)\n",
    "        else:\n",
    "            return evaluate(alternative, env)\n",
    "    else:                                        # (proc arg...)\n",
    "        proc_exp, *args = x\n",
    "        proc = evaluate(proc_exp, env)\n",
    "        arg_values = [evaluate(exp, env) for exp in args]\n",
    "        return proc(*arg_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "578db678",
   "metadata": {},
   "source": [
    "### Avaliar `(lambda (var…) body)`\n",
    "\n",
    "```python\n",
    "    elif x[0] == 'lambda':\n",
    "        _, parms, body = x\n",
    "        return Procedure(parms, body, env)\n",
    "```\n",
    "\n",
    "Se a expressão for uma `list` onde o primeiro elemento é a\n",
    "palavra reservada `lambda`, seguida por uma lista de zero ou mais símbolos,\n",
    "e finalmente um `body` (corpo) formado por uma única expressão, então criamos e devolvemos uma `Procedure`.\n",
    "\n",
    "Exemplo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3f8fc4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "porcentagem = run('(lambda (a b) (* (/ a b) 100))')\n",
    "porcentagem(15, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3042b243",
   "metadata": {},
   "source": [
    "O resultado de `(lambda …)` é uma função anônima,\n",
    "ela não é salva no ambiente. Para criar uma função nomeada,\n",
    "use `lambda` com `define`.\n",
    "\n",
    "> **NOTA**: Essa versão de `lis.py` só aceita uma única expressão como corpo de uma função.\n",
    "  Use `(begin …)` para criar um `body` várias expressões. O resultado da função será o valor da última expressão."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7b9a085",
   "metadata": {},
   "source": [
    "### Avaliar `(quote exp)`\n",
    "\n",
    "```python\n",
    "    elif x[0] == 'quote':\n",
    "        _, exp = x\n",
    "        return exp\n",
    "```\n",
    "\n",
    "Se a expressão for uma `list` onde o primeiro elemento\n",
    "é a palavra reservada `quote` seguida por uma única expressão,\n",
    "devolva a expressão sem interpretá-la.\n",
    "\n",
    "Exemplos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3c3ef04",
   "metadata": {},
   "outputs": [],
   "source": [
    "run('(quote no-such-name)')  # símbolo não definido, iria causar um erro se fosse interpretado"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a29b101",
   "metadata": {},
   "outputs": [],
   "source": [
    "run('(quote (99 bottles of beer))')  # 99 não é o nome de uma função ou palavra reservada"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5087cc3",
   "metadata": {},
   "outputs": [],
   "source": [
    "run('(quote (/ 10 0))')  # se interpretada, a expressão causaria uma exceção de divisão por zero"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49eafa09",
   "metadata": {},
   "source": [
    "### Avaliar `(if test consequence alternative)`\n",
    "\n",
    "```python\n",
    "    elif x[0] == 'if':\n",
    "        _, test, consequence, alternative = x\n",
    "        if evaluate(test, env):\n",
    "            return evaluate(consequence, env)\n",
    "        else:\n",
    "            return evaluate(alternative, env)\n",
    "```\n",
    "\n",
    "Se a expressão é uma `list` onde o primeiro elemento é a palavra reservada `if`,\n",
    "seguida por exatamente três expressões, avaliamos a expressão `test`.\n",
    "Se o resultado for `True` avaliamos `consequence`; caso contrário avaliamos `alternative`.\n",
    "\n",
    "Exemplos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e8791cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "run('(if (= 3 3) 1 0)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ea8ed67",
   "metadata": {},
   "outputs": [],
   "source": [
    "run('(if (= 3 30) 1 0)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d2ffb8f",
   "metadata": {},
   "outputs": [],
   "source": [
    "source = '''\n",
    "(define avaliar\n",
    "    (lambda (nota)\n",
    "        (if (>= nota 5)\n",
    "            (quote PASSOU)\n",
    "            (quote NÃO-PASSOU))))\n",
    "(avaliar 7)\n",
    "'''\n",
    "run(source)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33f5e5d7",
   "metadata": {},
   "source": [
    "## O REPL\n",
    "\n",
    "O REPL (Read-Eval-Print-Loop) de Norvig é fácil de entender porém não é\n",
    "muito amigavél. Se nenhum argumento é passado na linha de comando para o _lisp.py_,\n",
    "a função `repl()` é invocada pela função `main()` definida no final do módulo.\n",
    "Um prompt `lis.py>` aparece, e nele devemos digitar expressões corretas e completas;\n",
    "se esquecermos de fechar um paretenses o _lis.py_ irá quebrar.\n",
    "\n",
    "> **NOTA**: Quando estudei os scripts _lis.py_ e _lispy.py_ feitos por Norvig,\n",
    "  criei um fork chamado [`mylis`](https://github.com/fluentpython/lispy/blob/main/mylis)\n",
    "  com algumas funcionalidades a mais,\n",
    "  como um REPL que aceita expressões parciais que podem ser continuadas nas próximas linhas,\n",
    "  semelhante ao REPL de Python que sabe que não terminamos e nos apresenta um segundo prompt\n",
    "  `...` até que entremos um expressão ou instrução completa que possa ser interpretada.\n",
    "  `mylis` também consegue tratar alguns erros um pouco melhor, porém ainda é fácil de quebrar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79ca6a9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def repl(prompt: str = 'lis.py> ') -> NoReturn:\n",
    "    \"A prompt-read-evaluate-print loop.\"\n",
    "    global_env = standard_env()\n",
    "    while True:\n",
    "        val = evaluate(parse(input(prompt)), global_env)\n",
    "        if val is not None:\n",
    "            print(lispstr(val))\n",
    "\n",
    "\n",
    "def lispstr(exp: object) -> str:\n",
    "    \"Convert a Python object back into a Lisp-readable string.\"\n",
    "    if isinstance(exp, list):\n",
    "        return '(' + ' '.join(map(lispstr, exp)) + ')'\n",
    "    else:\n",
    "        return str(exp)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83be296e",
   "metadata": {},
   "source": [
    "A função `repl()` chama a função `standard_env()` para instalar funções essenciais no ambiente global,\n",
    "então entra em um loop infinito lendo e fazendo o parse de cada linha digitada pelo usuário,\n",
    "interpreta cada linha no ambiente global, e mostra o resultado—exceto quando é `None`.\n",
    "A variável `global_env` pode ser modificada pela função `evaluate()`.\n",
    "\n",
    "A função `lispstr()` faz o inverso de `parse()`:\n",
    "dado um objeto Python que representa uma expressão,\n",
    "`lispstr` retorna o código-fonte em Scheme para essa expressão.\n",
    "Por exemplo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "acd13c97",
   "metadata": {},
   "outputs": [],
   "source": [
    "lispstr(['+', 32, ['*', ['/', 9, 5], 'c']])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4b623ad",
   "metadata": {},
   "source": [
    "## Exemplos\n",
    "\n",
    "### Fatorial recursivo simples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15349c69",
   "metadata": {},
   "outputs": [],
   "source": [
    "fatorial_scm = '''\n",
    "(define ! (lambda (n)\n",
    "    (if (< n 2)\n",
    "        1\n",
    "        (* n (! (- n 1)))\n",
    ")))\n",
    "\n",
    "(! 5)\n",
    "'''\n",
    "run(fatorial_scm)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bc656d5",
   "metadata": {},
   "source": [
    "### Fatorial com recursão de cauda"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab26b3fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "fatorial_scm = '''\n",
    "(define ! (lambda (n)\n",
    "    (fatorial-iter n 1)))\n",
    "\n",
    "(define fatorial-iter\n",
    "    (lambda (n produto)\n",
    "        (if (= n 1)\n",
    "            produto\n",
    "            (fatorial-iter (- n 1) (* n produto))\n",
    "        )\n",
    "    )\n",
    ")\n",
    "\n",
    "(! 5)\n",
    "'''\n",
    "run(fatorial_scm)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1f10e48",
   "metadata": {},
   "source": [
    "A função `fatorial-iter` faz recursão de cauda:\n",
    "a chamada recursiva é devolvida como resultado diretamente.\n",
    "Isso é denominado uma chamada de cauda ou [*tail call*](https://en.wikipedia.org/wiki/Tail_call).\n",
    "\n",
    "Em contraste, o [Fatorial recursivo simples](#Fatorial-recursivo-simples)\n",
    "não é um exemplo de recursão de cauda:\n",
    "o resultado da chamada recursiva é multiplicado por `n` antes de ser devolvido.\n",
    "\n",
    "O sufixo `-iter` é comumente usado em Scheme para funções que fazem iteração por recursão de cauda.\n",
    "É comum que tais funções utilizem um parâmetro acumulador,\n",
    "que vai gradualmente acumulando resultados parciais.\n",
    "Em `fatorial-iter`, o parâmetro `produto` é o acumulador.\n",
    "\n",
    "> **NOTA**: `lis.py` não implementa chamadas de cauda eficientes, um recurso conhecido em inglês como _proper tail call_ (PTC) ou _tail call optimization_ (TCO), conforme o autor.\n",
    "Portanto, não há vantagem em fazer recursão de cauda. Porém\n",
    "[`lispy.py`](https://github.com/norvig/pytudes/blob/main/py/lispy.py) e\n",
    "[`mylis_2`](https://github.com/fluentpython/lispy/blob/main/mylis/mylis_2/lis.py)\n",
    "implementam PTC, o que significa que nesses interpretadores uma recursão de cauda não faz a pilha crescer a cada iteração."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a73f749a",
   "metadata": {},
   "source": [
    "### Quicksort\n",
    "\n",
    "O [algoritmo recursivo de ordenação](https://pt.wikipedia.org/wiki/Quicksort) eficiente e elegante inventado por Tony Hoare.\n",
    "\n",
    "Observe na última linha o uso de `quote` para criar uma lista de números, e na função `quicksort` o uso de funções de tratamento de listas: `null?`, `car`, `cdr`, `append`, `list`, e `filter`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "83a59feb",
   "metadata": {},
   "outputs": [],
   "source": [
    "quicksort_scm = \"\"\"\n",
    "(define quicksort (lambda (lst)\n",
    "    (if (null? lst)\n",
    "        lst\n",
    "        (begin\n",
    "            (define pivô (car lst))\n",
    "            (define resto (cdr lst))\n",
    "            (append\n",
    "                (quicksort\n",
    "                    (filter (lambda (x) (< x pivô)) resto))\n",
    "                (list pivô)\n",
    "                (quicksort\n",
    "                    (filter (lambda (x) (>= x pivô)) resto)))\n",
    "))))\n",
    "\n",
    "(quicksort (quote (2 1 6 3 4 0 8 9 7 5)))\n",
    "\"\"\"\n",
    "run(quicksort_scm)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c6501b8",
   "metadata": {},
   "source": [
    "> **NOTA**: o código acima funciona em `lis.py`, mas não em Scheme padrão. A forma `define` não pode ser usada naquele contexto em Scheme padrão; em vez dela, usaríamos a forma `let`—que não existe em `lis.py`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abb6ea46",
   "metadata": {},
   "source": [
    "### Raiz quadrada por aproximação\n",
    "\n",
    "O [método bibilônio](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method),\n",
    "um algoritmo para calcular raiz quadrada usado desde a antiguidade. É um caso especial do [Método de Newton–Raphson](https://pt.wikipedia.org/wiki/M%C3%A9todo_de_Newton%E2%80%93Raphson) para cálculo de raízes de funções.\n",
    "Este código foi adaptado de um [exemplo](https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node12.html) do livro *Structure and Interpretation of Computer Programs*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "642dd366",
   "metadata": {},
   "outputs": [],
   "source": [
    "raiz2_scm = \"\"\"\n",
    "(define raiz2 (lambda (x)\n",
    "    (raiz2-iter 1.0 x)))\n",
    "\n",
    "(define raiz2-iter (lambda (chute x)\n",
    "    (if (próximo? chute x)\n",
    "        chute\n",
    "        (raiz2-iter (melhorar chute x) x))))\n",
    "\n",
    "(define próximo? (lambda (chute x)\n",
    "    (< (abs (- (* chute chute) x)) 0.001)))\n",
    "\n",
    "(define melhorar (lambda (chute x)\n",
    "    (média chute (/ x chute))))\n",
    "\n",
    "(define média (lambda (x y)\n",
    "    (/ (+ x y) 2)))\n",
    "\n",
    "(raiz2 12345654321)\n",
    "\"\"\"\n",
    "run(raiz2_scm)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "934b8a3f",
   "metadata": {},
   "source": [
    "### Máximo divisor comum\n",
    "\n",
    "O [algoritmo de Euclides](https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c22578a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "mdc_scm = '''\n",
    "(define resto (lambda (m n)\n",
    "    (- m (* n (quotient m n)))))\n",
    "\n",
    "(define mdc (lambda (m n)\n",
    "    (if (= n 0)\n",
    "        m\n",
    "        (mdc n (resto m n)))))\n",
    "\n",
    "(mdc 18 45)\n",
    "'''\n",
    "run(mdc_scm)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b3ee3da",
   "metadata": {},
   "source": [
    "> **NOTA**: Este exemplo usa `lambda` dentro de `define` em vez da sintaxe abreviada com `define`\n",
    "ilustrada na função `mdc` em [Sintaxe de Scheme](#Sintaxe-de-Scheme). Leia mais a seguir."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2029b337",
   "metadata": {},
   "source": [
    "## Açúcar Sintático\n",
    "\n",
    "Por padrão Scheme tem uma sintaxe alternativa para `define` que permite definir funções nomeadas\n",
    "sem usar a palavra reservada `lambda`.\n",
    "\n",
    "A sintaxe é: `(define (name params…) body…)`, onde:\n",
    "\n",
    "`name`: é o nome da função a ser definida (um `Symbol`);\n",
    "\n",
    "`params…`: zero ou mais símbolos declarando o nome dos parâmetros;\n",
    "\n",
    "`body…`: uma ou mais expressões para serem usadas como o corpo da função.\n",
    "\n",
    "Isso é um exemplo de _açúcar sintático_:\n",
    "uma sintaxe nova que não adiciona nenhuma funcionalidade a linguagem,\n",
    "mas facilita o uso dela, tornando-a mais conveniente.\n",
    "\n",
    "A versão de `mdc` apresentada na seção [Sintaxe de Scheme](#Sintaxe-de-Scheme)\n",
    "usa esse atalho sintático.\n",
    "\n",
    "### Exercício para casa\n",
    "\n",
    "Valide seu entendimento do `lis.py` modificando a função `evaluate()`\n",
    "para permitir o atalho sintático `define` para funções nomeadas.<br>\n",
    "Teste sua solução rodando o exemplo abaixo. O resultado deve ser `9`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81b672c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "mdc2_scm = '''\n",
    "(define (resto m n)\n",
    "    (- m (* n (quotient m n))))\n",
    "    \n",
    "(define (mdc m n)\n",
    "    (if (= n 0)\n",
    "        m\n",
    "        (mdc n (resto m n))))\n",
    "        \n",
    "(mdc 18 45)\n",
    "'''\n",
    "# run(mdc2_scm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d766d5a5",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "jupytext": {
   "encoding": "# -*- coding: utf-8 -*-"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}