07.Introdução à Funções.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\" style=\"margin-top: 1em;\"><ul class=\"toc-item\"><li><span><a href=\"#Introdução-à-Funções\" data-toc-modified-id=\"Introdução-à-Funções-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Introdução à Funções</a></span><ul class=\"toc-item\"><li><span><a href=\"#Como-escrever-código?\" data-toc-modified-id=\"Como-escrever-código?-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Como escrever código?</a></span></li><li><span><a href=\"#Exercício-de-motivação\" data-toc-modified-id=\"Exercício-de-motivação-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Exercício de motivação</a></span></li><li><span><a href=\"#Decomposição-e-Abstração\" data-toc-modified-id=\"Decomposição-e-Abstração-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Decomposição e Abstração</a></span></li><li><span><a href=\"#Projetando-funções\" data-toc-modified-id=\"Projetando-funções-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Projetando funções</a></span></li><li><span><a href=\"#Documentação\" data-toc-modified-id=\"Documentação-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Documentação</a></span></li><li><span><a href=\"#Exercício:-Fatorial\" data-toc-modified-id=\"Exercício:-Fatorial-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Exercício: Fatorial</a></span></li><li><span><a href=\"#Exercício:-Combinação\" data-toc-modified-id=\"Exercício:-Combinação-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>Exercício: Combinação</a></span></li></ul></li><li><span><a href=\"#Escopo-de-Variáveis\" data-toc-modified-id=\"Escopo-de-Variáveis-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Escopo de Variáveis</a></span><ul class=\"toc-item\"><li><span><a href=\"#Exercícios\" data-toc-modified-id=\"Exercícios-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Exercícios</a></span></li></ul></li><li><span><a href=\"#Funções-como-argumentos\" data-toc-modified-id=\"Funções-como-argumentos-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Funções como argumentos</a></span></li><li><span><a href=\"#Funções-Aninhadas-e-Funções-como-valores-de-retorno\" data-toc-modified-id=\"Funções-Aninhadas-e-Funções-como-valores-de-retorno-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Funções Aninhadas e Funções como valores de retorno</a></span><ul class=\"toc-item\"><li><span><a href=\"#Algoritmo-de-Aproximações-de-Newton\" data-toc-modified-id=\"Algoritmo-de-Aproximações-de-Newton-4.1\"><span class=\"toc-item-num\">4.1&nbsp;&nbsp;</span>Algoritmo de Aproximações de Newton</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Introdução à Funções"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Como escrever código?\n",
    "- Até agora nós cobrimos alguns mecanismos da linguagem\n",
    "- Sabemos como escrever diferentes trechos de código para cada computação\n",
    "- Cada código é uma seqüência de instruções\n",
    "\n",
    "- Problemas com esta abordagem \n",
    " - fácil para problemas em pequena escala \n",
    " - complicado para problemas maiores\n",
    "  - difícil de acompanhar os detalhes\n",
    "  - como você sabe que a informação certa é fornecida à parte correta do código?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercício de motivação\n",
    "\n",
    "O número de combinações possíveis de **m** elementos em grupos de **n** elementos (n <= m) é dada pela fórmula de combinação m!/((m-n)!n!).\n",
    "\n",
    "Escreva um programa que lê dois inteiros **m** e **n** e calcula a combinação de m, n a n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     8,
     18,
     28
    ],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# leitura dos valores de entrada\n",
    "m = int(input(\"Digite m: \"))\n",
    "n = int(input(\"Digite n: \"))\n",
    "\n",
    "# calcula o fatorial de m\n",
    "k = m\n",
    "k_fat = 1\n",
    "cont = 1\n",
    "while cont < k:\n",
    "    cont += 1       # o mesmo que cont = cont + 1\n",
    "    k_fat *= cont   # o mesmo que k_fat = k_fat * cont\n",
    "\n",
    "m_fatorial = k_fat\n",
    "\n",
    "# calcula o fatorial de n\n",
    "k = n\n",
    "k_fat = 1\n",
    "cont = 1\n",
    "while cont < k:\n",
    "    cont += 1       # o mesmo que cont = cont + 1\n",
    "    k_fat *= cont   # o mesmo que k_fat = k_fat * cont\n",
    "\n",
    "n_fatorial = k_fat\n",
    "\n",
    "# calcula o fatorial de m - n\n",
    "k = m-n\n",
    "k_fat = 1\n",
    "cont = 1\n",
    "while cont < k:\n",
    "    cont += 1       # o mesmo que cont = cont + 1\n",
    "    k_fat *= cont   # o mesmo que k_fat = k_fat * cont\n",
    "\n",
    "mn_fatorial = k_fat\n",
    "\n",
    "print(\"Comb(\",m,\",\",n,\") = \", format(m_fatorial/(mn_fatorial * n_fatorial), \".0f\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Decomposição e Abstração\n",
    "Uma linguagem de programação é mais do que apenas um meio para instruir um computador a executar tarefas. Ela também serve como um framework dentro do qual organizamos nossas idéias sobre processos computacionais. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Quando escrevemos um programa, devemos prestar especial atenção aos meios que a linguagem oferece para combinar idéias simples para formar idéias mais complexas. Toda linguagem poderosa possui três desses mecanismos:\n",
    "\n",
    "- expressões e declarações primitivas, que representam os blocos de construção mais simples que a linguagem fornece,\n",
    "- meios de combinação, através dos quais os elementos compostos são construídos a partir de mais simples, e\n",
    "- meios de abstração, pelos quais elementos compostos podem ser nomeados e manipulados como unidades."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Na programação, lidamos com dois tipos de elementos: funções e dados. (Em breve, descobriremos que eles realmente não são tão distintos.) Informalmente, os dados são coisas que queremos manipular, e as funções descrevem as regras para manipular os dados. Assim, qualquer linguagem de programação poderosa deve ser capaz de descrever dados primitivos e funções primitivas, além de ter alguns métodos para combinar e abstrair funções e dados.\n",
    "\n",
    "- **Decomposição** é o mecanismo que usamos para \"dividir\" o código em pedaços ou módulos, destinados a serem reutilizados. Com isso mantemos o código coerente e organizado. Nesta aula nós vamos realizar a decomposição do programa com funções. Ao final do curso, nós iremos realizar a decomposição com o mecanismo de classes.\n",
    "\n",
    "- **Abstração** é o mecanismo na qual nós \"escondemos\" trechos de código como se fosse uma \"caixa preta\". Nós não precisamos ver os detalhes do código, mas apenas conhecer sua interface (input & output)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Projetando funções"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "As funções são um ingrediente essencial de todos os programas, grandes e\n",
    "pequenos, e servem como nosso mecanismo primário para expressar processos computacionais em uma linguagem de programação. Fundamentalmente, elas reforçam a idéia de que as funções são abstrações.\n",
    "\n",
    "- Cada função deve realizar exatamente um trabalho. Esse trabalho deve ser identificável com um nome curto e caracterizável em uma única linha de texto. As funções que executam vários trabalhos em seqüência devem ser divididas em múltiplas funções.\n",
    "- Se você se encontra copiando e colando um bloco de código, você provavelmente encontrou uma oportunidade para abstração funcional."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Lembre-se que essas simples diretrizes melhoram a legibilidade do código,\n",
    "reduzem o número de erros e muitas vezes minimizam a quantidade total de código\n",
    "escrito. Descompactar uma tarefa complexa em funções concisas é uma habilidade\n",
    "que leva tempo para dominar. Felizmente, o Python oferece vários recursos para suportar seus esforços."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Começamos examinando como expressar a idéia de \"quadrado de um número\".\n",
    "Podemos dizer: \"Para elevar um número ao quadrado, multiplicamos este número por si mesmo\".\n",
    "Isso é expresso em Python como:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def square(x):\n",
    "    return x * x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "que define uma nova função que recebeu o nome `square`. Esta função definida pelo usuário não está integrada ao interpretador python. Representa a operação composta de multiplicar algo por si mesmo.\n",
    "O $x$ nesta definição é chamado de parâmetro formal, que fornece um nome para que um número seja multiplicado. A definição cria esta função definida pelo usuário e associa-a ao nome `square`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Como definir uma função:** As definições de funções consistem em uma declaração com a construtor `def` da linguagem e indica um **nome** e uma lista, separada por vírgulas, de  `parâmetros formais`, além de uma declaração de retorno da função, presente no corpo da mesma, especificada por `return` seguido de uma expressão a ser avaliada sempre que a função é aplicada:\n",
    "```python\n",
    "def <nome> (<parâmetros formais>):\n",
    "    return <expressão de retorno>\n",
    "```\n",
    "A expressão de retorno não é avaliada imediatamente; Ela é armazenada como parte da função recém-definida e avaliada somente quando a função é eventualmente aplicada. Se o usuário não especificar uma expressão de retorno, o python implicitamente retorna o valor `None` do tipo `NoneType`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Tendo definida a função `square`, podemos aplicá-la com uma expressão de chamada:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "square(21)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "square(2 + 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "square(square(3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Nós também podemos usar a função `square` como um bloco de construção na definição de outras funções. Por exemplo, podemos definir facilmente uma função `sum_squares` que, com os dois números como argumentos, retorna a soma de seus quadrados:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def sum_squares(x, y):\n",
    "    return square(x) + square(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "sum_squares(3, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Documentação\n",
    "Uma definição de função geralmente inclui documentação que descreve a função, chamada docstring.\n",
    "Docstrings são convencionalmente inseridos entre três aspas duplas. A primeira linha descreve o objetivo da função em uma linha. As seguintes linhas podem descrever argumentos e esclarecer o comportamento da função:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def pressure(v, t, n):\n",
    "    \"\"\"Compute the pressure in pascals of an ideal gas.\n",
    "\n",
    "    v -- volume of gas, in cubic meters\n",
    "    t -- absolute temperature in degrees kelvin\n",
    "    n -- particles of gas\n",
    "    \"\"\"\n",
    "    k = 1.38e-23  # Boltzmann's constant\n",
    "    return n * k * t / v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Quando você chama o `help` com o nome de uma função como argumento, você vê sua docstring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "help(pressure)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercício: Fatorial\n",
    "\n",
    "Complete a função **fatorial** abaixo, que recebe como parâmetro um número inteiro k, k >= 0, e retorna k!.\n",
    "\n",
    "Escreva apenas o corpo da função. Observe que o código já inclui chamadas para a função **fatorial**, para que você possa testar a função."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def fatorial(k):\n",
    "    \"\"\" Recebe um inteiro k e retorna o valor de k!\n",
    "        Pre-condição: supõe que k é um numero inteiro não negativo.\n",
    "    \"\"\"\n",
    "\n",
    "    k_fat = 1\n",
    "\n",
    "    # Complete a função Fatorial\n",
    "\n",
    "    return k_fat\n",
    "\n",
    "# testes\n",
    "print(\"0! =\", fatorial(0))\n",
    "print(\"1! =\", fatorial(1))\n",
    "print(\"5! =\", fatorial(5))\n",
    "print(\"17! =\", fatorial(17))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercício: Combinação\n",
    "\n",
    "Usando a função do exercício **Fatorial**, escreva uma função que recebe dois inteiros, **m** e **n**, como parâmetros e retorna a combinação m!/((m-n)!n!)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def combinacao(m, n):\n",
    "    \"\"\" Recebe dois inteiros m e n, e retorna o valor de m!/((m-n)! n!)\n",
    "    \"\"\"\n",
    "\n",
    "    # Complete a função combinação (não se esqueça de mudar o retorno).\n",
    "\n",
    "    return None\n",
    "\n",
    "# testes\n",
    "print(\"Combinacao(4,2) =\", combinacao(4,2))\n",
    "print(\"Combinacao(5,2) =\", combinacao(5,2))\n",
    "print(\"Combinacao(10,4) =\", combinacao(10,4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Escopo de Variáveis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Nosso subconjunto de Python agora é complexo o suficiente para que o significado dos programas não seja óbvio. E se um parâmetro formal tiver o mesmo nome que uma função builtin? Duas funções podem compartilhar nomes sem confusão? Para resolver essas questões, devemos descrever os ambientes e  escopo de nomes com mais detalhes.\n",
    "\n",
    "Um ambiente em que uma expressão é avaliada consiste em uma seqüência de frames. Cada frame contém ligações (bindings), cada um dos quais associa um nome ao seu valor correspondente. Existe um único frame global. As instruções de atribuição (e importação) adicionam entradas ao primeiro frame do ambiente atual. Até agora, nosso ambiente consistiu apenas no frame global.\n",
    "Vamos visualizá-lo usando o [Python Tutor](http://www.pythontutor.com/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%load_ext tutormagic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor --lang python3 --link --heapPrimitives\n",
    "a = 1\n",
    "b = a\n",
    "a = a + 1\n",
    "c = a + b\n",
    "print(a, b, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para avaliar uma expressão de chamada cujo operador vincula uma função definida pelo usuário, o interpretador Python segue um processo computacional. Tal como acontece com qualquer expressão de chamada, o interpretador avalia as expressões operador e operando e, em seguida, aplica a função vinculada aos argumentos resultantes.\n",
    "\n",
    "A aplicação de uma função definida pelo usuário apresenta um segundo frame local, que só é acessível a essa função. Para aplicar uma função definida pelo usuário para alguns argumentos, o interpretador:\n",
    "\n",
    "- Vincula os argumentos aos nomes dos parâmetros formais da função em um novo frame local.\n",
    "- Executa o corpo da função no ambiente que começa com este frame."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O ambiente em que o corpo da função é avaliado consiste em dois frames: primeiro o frame local que contém ligações de parâmetros formais; segundo o frame global que contém todo o resto. Cada instância de um aplicativo de função possui seu próprio frame local independente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor --lang python3 --tab --heapPrimitives\n",
    "def square(x):\n",
    "    return x * x\n",
    "\n",
    "def sum_squares(x, y):\n",
    "    return square(x) + square(y)\n",
    "\n",
    "result = sum_squares(5, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O parâmetro formal é vinculado ao valor do parâmetro real quando a função é chamada. Um novo frame é \n",
    "criado quando entramos em uma função. O escopo nada mais é que o mapeamento de nomes para objetos.\n",
    "Dentro de uma função, para poder acessar uma variável definida externamente, temos que marcá-la como global, mas isto é altamente desaconselhável pois a execução de suas funções passam a ter efeitos colaterais que não ficam mais restritos aos parâmetros e valores de retorno."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor --lang python3 --tab --heapPrimitives\n",
    "def f(x):\n",
    "    x = x + 1\n",
    "    return x\n",
    "\n",
    "x = 3\n",
    "z = f(x)\n",
    "print(x, z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor --lang python3 --link --heapPrimitives\n",
    "def g(y):\n",
    "    x = 1\n",
    "    x = x + 1\n",
    "    return x\n",
    "\n",
    "x = 3\n",
    "z = g(x)\n",
    "print (x, z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor -l python3 --link --heapPrimitives\n",
    "def h(y):\n",
    "    #global x\n",
    "    x = x + 1   # UnboundLocalError: local variable 'x' referenced before assignment\n",
    "    return x\n",
    "\n",
    "x = 3\n",
    "z = h(x)\n",
    "print (x, z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercícios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- **Reverso do número**. Faça uma função que retorne o reverso de um número inteiro informado. Por exemplo: 127 -> 721."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Funções como argumentos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Os argumentos de uma função podem ser de qualquer tipo, inclusive funções. Para exemplificar, considere as três funções a seguir onde todas calculam somas. A primeira, `sum_naturals`, calcula a soma dos números naturais até $n$. A segunda, `sum_cubes`, calcula a soma dos cubos de números naturais até $n$. A terceira, `pi_sum`, calcula a soma dos termos da série:\n",
    "$\\frac{8}{1*3}+\\frac{8}{5*7}+\\frac{8}{9*11}+ ...$, que converge para $\\pi$ muito devagar.\n",
    "\n",
    "**p.s.**: Os exemplos a seguir usam um recurso do python de atribuições em tuplas para atribuir um par de valores a um par de variáveis. Este recurso será melhor explorado na aula sobre tuplas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor -l python3 --link --heapPrimitives\n",
    "def sum_naturals(n):\n",
    "    total, k = 0, 1\n",
    "    while k <= n:\n",
    "        total, k = total + k, k + 1\n",
    "    return total\n",
    "\n",
    "sum_naturals(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def sum_cubes(n):\n",
    "    total, k = 0, 1\n",
    "    while k <= n:\n",
    "        total, k = total + k*k*k, k + 1\n",
    "    return total\n",
    "\n",
    "sum_cubes(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def pi_sum(n):\n",
    "    total, k = 0, 1\n",
    "    while k <= n:\n",
    "        total, k = total + 8 / ((4*k-3) * (4*k-1)), k + 1\n",
    "    return total\n",
    "\n",
    "pi_sum(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Essas três funções compartilham claramente um padrão básico comum. Eles são na sua maioria idênticos, diferindo apenas no nome e na função de $k$ usada para calcular o termo a ser adicionado. Poderíamos gerar cada uma das funções preenchendo os slots no mesmo modelo:\n",
    "```python\n",
    "def <nome> (n):\n",
    "    total, k = 0, 1\n",
    "    while k <= n:\n",
    "        total, k = total + <termo> (k), k + 1\n",
    "    return total\n",
    "```\n",
    "A presença de um padrão tão comum é uma forte evidência de que há uma abstração útil à espera de ser trazida à superfície. Cada uma dessas funções é uma soma de termos. Como designers de programas, gostaríamos que nossa linguagem fosse suficientemente poderosa para que possamos escrever uma função que exprima o conceito de soma em si, ao invés de apenas funções que calculam somas particulares. Podemos fazê-lo facilmente em Python, tomando o modelo comum mostrado acima e transformando os \"slots\" em parâmetros formais:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "No exemplo a seguir, a função `summation` leva como seus dois argumentos o limite superior $n$ junto com a função `termo` que calcula o k-ésimo termo. Podemos usar a função `summation` exatamente como qualquer outra função. Observe, por exemplo como o \"biding\" da função `cube` com o argumento local de nome `term` garante que o resultado $1 * 1 * 1 + 2 * 2 * 2 + 3 * 3 * 3 = 36$ seja calculado corretamente. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor -l python3 --link --heapPrimitives\n",
    "def summation(n, term):\n",
    "    total, k = 0, 1\n",
    "    while k <= n:\n",
    "        total, k = total + term(k), k + 1\n",
    "    return total\n",
    "\n",
    "def cube(x):\n",
    "    return x*x*x\n",
    "\n",
    "def sum_cubes(n):\n",
    "    return summation(n, cube)\n",
    "\n",
    "result = sum_cubes(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Usando uma função identidade (i.e., função que retorna seu argumento), também podemos somar \n",
    "números naturais usando exatamente a mesma função de soma `summation`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def summation(n, term):\n",
    "    total, k = 0, 1\n",
    "    while k <= n:\n",
    "        total, k = total + term(k), k + 1\n",
    "    return total\n",
    "\n",
    "def identity(x):\n",
    "    return x\n",
    "\n",
    "def sum_naturals(n):\n",
    "    return summation(n, identity)\n",
    "\n",
    "sum_naturals(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Podemos definir uma função `pi_sum` usando nossa abstração `summation` definindo uma função `pi_term` para calcular cada termo. Passamos o argumento $1e6$, uma notação para $1 * 10^6 = 1000000$, para gerar uma aproximação próxima de $\\pi$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def summation(n, term):\n",
    "    total, k = 0, 1\n",
    "    while k <= n:\n",
    "        total, k = total + term(k), k + 1\n",
    "    return total\n",
    "\n",
    "def pi_term(x):\n",
    "    return 8 / ((4*x-3) * (4*x-1))\n",
    "\n",
    "def pi_sum(n):\n",
    "    return summation(n, pi_term)\n",
    "\n",
    "pi_sum(1e6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Funções Aninhadas e Funções como valores de retorno\n",
    "Os exemplos anteriores demonstraram como a capacidade de passar funções como argumentos aumenta\n",
    "significativamente o poder de expressão de nossa linguagem de programação. Cada conceito geral\n",
    "ou equação mapeia sua própria função. Uma conseqüência negativa dessa abordagem é que\n",
    "nosso frame global fica poluído com nomes de pequenas funções, que devem ser únicos. Outro\n",
    "problema é que somos limitados por assinaturas específicas de funções com um número fixo de\n",
    "argumentos. As definições de funções aninhadas endereçam esses dois problemas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Um ambiente pode consistir em uma cadeia arbitrariamente longa de frames, que\n",
    "sempre termina com o frame global. Nos exemplos anteriores os ambientes tinham\n",
    "no máximo dois frames: um frame local e o frame global. Ao chamar funções\n",
    "definidas dentro de outras funções, através de declarações aninhadas, podemos\n",
    "criar cadeias mais longas, como veremos no exemplo a seguir.\n",
    "\n",
    "Com isso perceberemos duas vantagens principais do escopo lexico em Python.  Os\n",
    "nomes de uma função local não interferem com nomes externos à função em que está\n",
    "definido, porque o nome da função local será vinculado no ambiente local atual\n",
    "em que foi definido, em vez do ambiente global.  Uma função local pode acessar o\n",
    "ambiente da função na qual ela está encerrada (\\textit{closure}), porque o corpo da\n",
    "função local é avaliado em um ambiente que estende o ambiente de avaliação em\n",
    "que foi definido."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Podemos alcançar um poder ainda mais expressivo em nossos programas, criando\n",
    "funções cujos valores retornados são eles próprios funções. Uma característica\n",
    "importante das linguagens de programação com alcance lexico é que as funções\n",
    "definidas localmente mantêm seu ambiente pai quando elas são retornadas. O\n",
    "exemplo que vamos estudar a seguir ilustra o poder deste recurso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Algoritmo de Aproximações de Newton\n",
    "Este exemplo irá nos mostrar como os valores de retorno da função e as\n",
    "definições locais podem funcionar juntas para expressar idéias gerais de forma\n",
    "concisa.  Vamos revisitar o algoritmo de aproximações de Newton, amplamente\n",
    "usado no aprendizado de máquinas (machine learning), computação científica,\n",
    "design de hardware e otimização.\n",
    "\n",
    "O método de Newton é uma abordagem iterativa clássica para encontrar os\n",
    "argumentos de uma função matemática que produz um valor de retorno $0$. Esses\n",
    "valores são chamados zeros da função. Encontrar um zero de uma função é muitas\n",
    "vezes equivalente a resolver algum outro problema de interesse, como por\n",
    "exemplo, calcular a raiz quadrada de um número.\n",
    "\n",
    "Observe que parte da aprendizagem de ciência da computação é entender como\n",
    "quantidades como essas podem ser computadas e a abordagem geral aqui apresentada\n",
    "é aplicável para resolver uma grande classe de equações."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O método de Newton é um poderoso método computacional geral para resolver\n",
    "equações diferenciáveis. Algoritmos muito rápidos para logaritmos e divisão de\n",
    "inteiros grandes empregam variantes desta técnica.  O método de Newton é um\n",
    "algoritmo de melhoria iterativo: melhora um palpite do zero para qualquer função\n",
    "que seja diferenciável, o que significa que pode ser aproximado por uma linha\n",
    "reta (tangente) em qualquer ponto. O método de Newton segue essas aproximações\n",
    "lineares para encontrar zeros de função.\n",
    "\n",
    "A **figura 4.1** mostra uma linha que atravessa o ponto $(x, f (x))$ e que tem a mesma inclinação\n",
    "que a curva para a função $f(x)$ nesse ponto. Essa linha é chamada de tangente, e\n",
    "sua inclinação é chamada de derivada de $f$ em $x$.\n",
    "\n",
    "A inclinação desta linha (slope) nos fornece a proporção da mudança no valor da função\n",
    "para a alteração no argumento da função. Por isso, traduzindo $x$\n",
    "por $f(x)$ dividido pela inclinação dará o valor do argumento no qual essa linha\n",
    "tangente toca o ponto $0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Usando o método de Newton, podemos calcular raízes de grau arbitrário $n$. O\n",
    "grau $n$ da raiz de $a$ é $x$, tal que $x*x*x ... x = a$ com $x$ repetido $n$\n",
    "vezes. Por exemplo,\n",
    "\n",
    "- A raiz quadrada de $64$ é $8$, porque $8*8 = 64$\n",
    "- A raiz cubica de $64$ é $4$, porque $4*4*4 = 64$\n",
    "- A raiz sexta de $64$ é $2$, porque $2*2*2*2*2*2 = 64$\n",
    "\n",
    "Podemos calcular raízes usando o método de Newton com as seguintes observações:\n",
    "A raiz n-ésima de a (escrito $\\sqrt[n]{a}$) é o valor $x$ tal que $x^n - a = 0$\n",
    "\n",
    "Se pudermos encontrar o zero dessa última equação, então podemos calcular as\n",
    "raízes de grau $n$ para um dado número $a$.  A **figura 4.2** traça as curvas para $n$ igual\n",
    "a 2, 3 e 6 e $a$ igual a 64, onde podemos visualizar essa relação."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![newton](img/newton-m.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Na solução que se segue, a função `newton_update` expressa o processo computacional de\n",
    "seguir esta linha tangente para 0, para uma função $f$ e sua derivada $df$.\n",
    "\n",
    "Em seguida, definimos a função `find_root` em termos da função `newton_update`,\n",
    "do algoritmo de melhoria `improve` e de uma função de comparação para ver se\n",
    "$f(x)$ está perto de $0$.\n",
    "\n",
    "Iremos obter as raízes de grau arbitrário n, calculando $f(x) = x^n - a$ e sua\n",
    "derivada $df(x) = n * x^{n-1}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor -l python3 --tab --heapPrimitives\n",
    "def improve(update, close, guess=1):\n",
    "        while not close(guess):\n",
    "            guess = update(guess)\n",
    "        return guess\n",
    "\n",
    "def newton_update(f, df):\n",
    "        def update(x):\n",
    "            return x - f(x) / df(x)\n",
    "        return update\n",
    "\n",
    "def find_zero(f, df):\n",
    "        def near_zero(x):\n",
    "            return abs(f(x)) <= 1e-15\n",
    "        return improve(newton_update(f, df), near_zero)\n",
    "\n",
    "def nth_root_of_a(n, a):\n",
    "        def f(x):\n",
    "            return x**n - a\n",
    "        def df(x):\n",
    "            return n * x**(n-1)\n",
    "        return find_zero(f, df)\n",
    "\n",
    "print(nth_root_of_a(3, 64))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "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.6.4"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "livereveal": {
   "theme": "solarized",
   "transition": "slide"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}