L01.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Introduzione a Python\n",
        "\n",
        "* Fate riferimento alla [documentazione on-line](https://docs.python.org/3/), \n",
        "* Per l'esecuzione del codice si consiglia l'uso di [Visual Studio Code](https://code.visualstudio.com/).\n",
        "\n",
        "La lezione di oggi richiama brevemente i seguenti capitoli di [The Python Tutorial](https://docs.python.org/3/tutorial/):\n",
        "\n",
        "* 3 [An Informal Introduction to Python](https://docs.python.org/3/tutorial/introduction.html),\n",
        "* 4.1 - 4.6 [More Control Flow Tools](https://docs.python.org/3/tutorial/controlflow.html) \n",
        "* 5 [Data Structures](https://docs.python.org/3/tutorial/datastructures.html).\n",
        "\n",
        "## Strutture dati e iterazione \n",
        "\n",
        "Per prima cosa, un breve excursus su *liste*, *insiemi* e *dizionari* e sui\n",
        "meccanismi di iterazione (`for`, `iter` e `next`), utili anche nelle\n",
        "*comprehension*. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
            ]
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# list comprehension: i quadrati dei numeri interi in [0, 10)\n",
        "\n",
        "q = [x * x for x in range(10)]\n",
        "q"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "{0, 2, 4, 6, 8}"
            ]
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# set comprehension: i numeri pari tra gli interi in [0, 9]\n",
        "\n",
        "p = {x for x in range(9) if x % 2 == 0}\n",
        "p"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "{'un': 2, 'semplice': 8, 'esempio': 7}"
            ]
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# dict comprehension: una mappa da una lista di parle alla loro lunghezza\n",
        "\n",
        "w2l = {w: len(w) for w in ['un', 'semplice', 'esempio']}\n",
        "w2l"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "alcune\n",
            "parole\n",
            "divise\n",
            "da\n",
            "spazi\n"
          ]
        }
      ],
      "source": [
        "# iterazione tramite iter/next\n",
        "\n",
        "it = iter('alcune parole divise da spazi'.split())\n",
        "\n",
        "while True:\n",
        "  w = next(it, None)\n",
        "  if w is None: break\n",
        "  print(w)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Funzioni (uso base)\n",
        "\n",
        "Un secondo argomento importante sono le funzioni, viste come [cittadini di prim'ordine](https://en.wikipedia.org/wiki/First-class_citizen)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# una semplice funzione\n",
        "\n",
        "def quadra(x):\n",
        "  return x * x"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "9"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# assegnare una funzione ad una variable\n",
        "\n",
        "f = quadra\n",
        "\n",
        "f(3)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[1, 4, 9]"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# usare una funzione come argomento (formale)\n",
        "\n",
        "def applica(fun, lst):\n",
        "  return [fun(x) for x in lst]\n",
        "\n",
        "applica(quadra, [1, 2, 3])"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Funzioni (uso avanzato)\n",
        "\n",
        "Le funzioni, viste come [cittadini di prim'ordine](https://en.wikipedia.org/wiki/First-class_citizen), sono utili in particolare per realizzare:\n",
        "\n",
        "* [visitor](https://en.wikipedia.org/wiki/Visitor_pattern),\n",
        "* [dispatch table](https://en.wikipedia.org/wiki/Dispatch_table) con i *dizionari* e\n",
        "* [memoizzazione](https://en.wikipedia.org/wiki/Memoization) tramite i *decoratori*.\n",
        "\n",
        "### Visitor"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# una lista di liste\n",
        "\n",
        "lol = [1, [2, 3], [4, [5, 6]]]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# come applicare una funzione scalare f a tutti gli elementi?\n",
        "\n",
        "def visit(f, lol):\n",
        "  for elem in lol:\n",
        "    if isinstance(elem, list):\n",
        "      visit(f, elem)\n",
        "    else:\n",
        "      f(elem)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n",
            "6\n"
          ]
        }
      ],
      "source": [
        "visit(print, lol)"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Dispatch table"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# una espressione\n",
        "\n",
        "expr = '3 + 12 * 4 + 1 * 2'"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# divisione in token (basata sulla presenza di spazi)\n",
        "\n",
        "tokens = iter(expr.split())"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# \"semantica\" delle operazioni, tramite dispatch table\n",
        "\n",
        "def somma(x, y):\n",
        "  return x + y\n",
        "\n",
        "def prodotto(x, y):\n",
        "  return x * y\n",
        "\n",
        "DT = {\n",
        "  '+': somma,\n",
        "  '*': prodotto\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "122"
            ]
          },
          "execution_count": 14,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# valutazione (SENZA rispettare la precedenza delle operazioni, ma solo l'associatività a sinistra)\n",
        "\n",
        "result = int(next(tokens))\n",
        "\n",
        "while True:\n",
        "  t = next(tokens, None)\n",
        "  if t is None: break\n",
        "  op = DT[t]\n",
        "  result = op(result, int(next(tokens)))\n",
        "\n",
        "result"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Memoizzazione"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# trasformare una funzione rendendola \"verbosa\"\n",
        "\n",
        "def rendi_verbosa(f):\n",
        "  def f_verbosa(x):\n",
        "    result = f(x)\n",
        "    print(f'f({x}) = {result}')\n",
        "    return result\n",
        "  return f_verbosa"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "f(3) = 9\n"
          ]
        }
      ],
      "source": [
        "def quadrato(x):\n",
        "  return x * x\n",
        "\n",
        "quadrato_verboso = rendi_verbosa(quadrato)\n",
        "\n",
        "q = quadrato_verboso(3)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# tenere da parte i risultati già calcolati da una funzione…\n",
        "\n",
        "cache = {}\n",
        "\n",
        "def memoize(f):\n",
        "  def f_memoized(x):\n",
        "    if x not in cache: cache[x] = f(x)\n",
        "    return cache[x]\n",
        "  return f_memoized"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "@memoize \n",
        "def cubo(x):\n",
        "  return x ** 3"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "{1: 1, 4: 64, 6: 216}"
            ]
          },
          "execution_count": 19,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "cache = {}\n",
        "\n",
        "cubo(1), cubo(4), cubo(6)\n",
        "\n",
        "cache"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "def fib(n):\n",
        "  if n == 0 or n == 1: return 1\n",
        "  return fib(n - 1) + fib(n - 2)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "CPU times: user 300 ms, sys: 0 ns, total: 300 ms\n",
            "Wall time: 300 ms\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "3524578"
            ]
          },
          "execution_count": 21,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "%time fib(32)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "@memoize\n",
        "def fib(n):\n",
        "  if n == 0 or n == 1: return 1\n",
        "  return fib(n - 1) + fib(n - 2)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "CPU times: user 17 µs, sys: 1 µs, total: 18 µs\n",
            "Wall time: 18.8 µs\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "{1: 1,\n",
              " 0: 1,\n",
              " 2: 2,\n",
              " 3: 3,\n",
              " 4: 5,\n",
              " 5: 8,\n",
              " 6: 13,\n",
              " 7: 21,\n",
              " 8: 34,\n",
              " 9: 55,\n",
              " 10: 89,\n",
              " 11: 144,\n",
              " 12: 233,\n",
              " 13: 377,\n",
              " 14: 610,\n",
              " 15: 987,\n",
              " 16: 1597,\n",
              " 17: 2584,\n",
              " 18: 4181,\n",
              " 19: 6765,\n",
              " 20: 10946,\n",
              " 21: 17711,\n",
              " 22: 28657,\n",
              " 23: 46368,\n",
              " 24: 75025,\n",
              " 25: 121393,\n",
              " 26: 196418,\n",
              " 27: 317811,\n",
              " 28: 514229,\n",
              " 29: 832040,\n",
              " 30: 1346269,\n",
              " 31: 2178309,\n",
              " 32: 3524578}"
            ]
          },
          "execution_count": 23,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "cache = {} \n",
        "\n",
        "%time fib(32)\n",
        "\n",
        "cache"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "named-let-liblet",
      "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"
    },
    "vscode": {
      "interpreter": {
        "hash": "e1004562009730290f42c30a7c24060925c35420ba84516473ad07a3f1950c5d"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}