pract6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Практическое занятие №6\n",
    "\n",
    "П.Н. Советов, РТУ МИРЭА"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 1**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напишите функцию deriv для приближенного вычисления производной в заданной точке.\n",
    "\n",
    "Пример работы:\n",
    "\n",
    "```Python\n",
    ">>> deriv(lambda x: x ** 3)(5)\n",
    "75.00014999664018\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 2**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создайте вариант именованного кортежа с помощью ФВП. Здесь и далее старайтесь использовать конструкцию match/case.\n",
    "\n",
    "Классы и готовые структуры данных (словари, кортежи и так далее) использовать нельзя.\n",
    "\n",
    "Пример работы:\n",
    "\n",
    "```Python\n",
    ">>> p1 = person(name='Иван', age=20)\n",
    ">>> p2 = replace(replace(p1, 'name', 'Алексей'), 'age', 21)\n",
    ">>> get(p1, 'name'), get(p1, 'age')\n",
    "('Иван', 20)\n",
    ">>> get(p2, 'name'), get(p2, 'age')\n",
    "('Алексей', 21)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 3**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Решите задачу 4 из практики 4 («деревья выражений») без классов, с помощью функций и match/case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 4**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создайте тип данных односвязный список с помощью ФВП.\n",
    "\n",
    "При создании списка нельзя использовать классы, готовые списки, кортежи и прочее.\n",
    "\n",
    "Добавьте ряд операций в функциональном стиле:\n",
    "\n",
    "1. Создайте функцию pair(head, tail), которая порождает элемент списка.\n",
    "1. Создайте функции first(lst) (возвращает значение головы списка) и rest(lst) (возвращает хвост списка).\n",
    "1. Создайте функцию make_list(`*args`), которая создает список на основе аргументов.\n",
    "1. Создайте функцию list_to_string(lst), возвращающую строку, содержащую элементы списка.\n",
    "1. Создайте функцию list_range(low, high), возвращающую список чисел от low до high включительно.\n",
    "1. Создайте функцию foldl(func, lst, acc), вычисляющую свертку элементов списка, аналогично reduce.\n",
    "1. Создайте функцию list_sum(lst) для вычисления суммы элементов списка с помощью foldl.\n",
    "1. Создайте функцию fact(n) для вычисления факториала с помощью foldl и list_range.\n",
    "1. Создайте функцию list_to_py(lst) для преобразования списка в обычный список Питона с помощью foldl.\n",
    "1. Создайте функцию list_reverse(lst) для разворота списка в обратном направлении с помощью foldl.\n",
    "1. Создайте функцию foldr(func, lst, acc), вычисляющую свертку справа для элементов списка.\n",
    "1. Создайте функцию list_map(func, lst), аналог map, с помощью foldr.\n",
    "1. Создайте функцию list_filter(pred, lst), аналог filter, с помощью foldr.\n",
    "1. Создайте функцию sum_odd_squares для вычисления суммы квадратов нечетных чисел списка с помощью list_sum, list_map и list_filter.\n",
    "1. Создайте функцию list_concat(lst1, lst2) для соединения двух списков.\n",
    "1. Создайте функцию list_replace(lst, index, value) для изменения элемента списка по индексу."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 5**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализуйте механизм undo/redo в функциональном стиле для следующей программы:\n",
    "\n",
    "```Python\n",
    "import turtle\n",
    "\n",
    "turtle.speed('fastest')\n",
    "screen = turtle.Screen()\n",
    "  \n",
    "def line_func(x, y):\n",
    "    turtle.goto(x, y)\n",
    "\n",
    "def undo_func():\n",
    "    turtle.goto(0, 0)\n",
    "    turtle.clear()\n",
    "    print('undo')\n",
    "\n",
    "def redo_func():\n",
    "    turtle.goto(0, 0)\n",
    "    turtle.clear()\n",
    "    print('redo')\n",
    "  \n",
    "screen.onclick(line_func)\n",
    "screen.onkey(undo_func, \"u\")\n",
    "screen.onkey(redo_func, \"r\")\n",
    "screen.listen()\n",
    "screen.mainloop()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 6**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создайте декоратор make_perf для получения статистики по количеству вызовов функций.\n",
    "\n",
    "Пример работы:\n",
    "\n",
    "```Python\n",
    ">>> PERF = {}\n",
    ">>> perf = make_perf(PERF)\n",
    ">>> @perf\n",
    "def fact(n):\n",
    "\t...\n",
    "\t\n",
    ">>> @perf\n",
    "def fib(n):\n",
    "\t...\n",
    "\n",
    ">>> fact(10), fib(27)\n",
    "3628800 196418\n",
    ">>> print(PERF)\n",
    "{'fact': 10, 'fib': 635621}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 7**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создайте декоратор memo для реализации механизма мемоизации. Для проверки используйте функции из предыдущей задачи.\n",
    "\n",
    "Пример работы:\n",
    "\n",
    "```Python\n",
    ">>> @memo\n",
    "@perf\n",
    "def fib(n):\n",
    "\t...\n",
    "    \n",
    ">>> fib(27)\n",
    "196418\n",
    ">>> PERF\n",
    "{'fact': 10, 'fib': 28}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 8**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализуйте рекурсивное вычисление факториала в виде выражения.\n",
    "\n",
    "Необходимо это сделать без использования именованных функций, переменных (в том числе без имени факториала) и присваиваний."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 9**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализуйте интерпретатор лямбда-исчисления.\n",
    "\n",
    "Проверяйте полученные результаты в других интерпретаторах: см. [здесь](https://jacksongl.github.io/files/demo/lambda/index.htm) или [здесь](https://crypto.stanford.edu/~blynn/lambda/).\n",
    "\n",
    "1. Добейтесь работы приведенных примеров из области логики, арифметики.\n",
    "1. Реализуйте факториал.\n",
    "1. Реализуйте синтаксический разбор входного, более удобного для записи кода, представления.\n",
    "1. Добавьте в интерпретатор поддержку целых чисел.\n",
    "1. Добавьте в интерпретатор поддержку операций арифметики.\n",
    "\n",
    "Заготовка кода:\n",
    "\n",
    "```Python\n",
    "class Var:\n",
    "    def __init__(self, name):\n",
    "        self.name = name\n",
    "\n",
    "    def __repr__(self):\n",
    "        return self.name\n",
    "\n",
    "\n",
    "class Func:\n",
    "    def __init__(self, var, body):\n",
    "        self.var = var\n",
    "        self.body = body\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f'(λ{self.var}.{self.body})'\n",
    "\n",
    "\n",
    "class App:\n",
    "    def __init__(self, func, arg):\n",
    "        self.func = func\n",
    "        self.arg = arg\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f'({self.func} {self.arg})'\n",
    "\n",
    "\n",
    "def subst(expr, var, arg):\n",
    "    if type(expr) is Var:\n",
    "        pass # TODO\n",
    "    elif type(expr) is Func:\n",
    "        pass # TODO\n",
    "    elif type(expr) is App:\n",
    "        pass # TODO\n",
    "\n",
    "\n",
    "def get_fresh_var():\n",
    "    pass # TODO\n",
    "\n",
    "\n",
    "def rename(expr):\n",
    "    def rec(expr, env):\n",
    "        if type(expr) is Var:\n",
    "            pass # TODO\n",
    "        elif type(expr) is Func:\n",
    "            pass # TODO\n",
    "        elif type(expr) is App:\n",
    "            pass # TODO\n",
    "    return rec(expr, {})\n",
    "\n",
    "\n",
    "def execute(expr):\n",
    "    if type(expr) is App:\n",
    "        pass # TODO\n",
    "    elif type(expr) is Func:\n",
    "        pass # TODO\n",
    "    else:\n",
    "        pass # TODO\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры программ:\n",
    "\n",
    "```Python\n",
    "I = Func(x, x)\n",
    "Z = Func(f, I)\n",
    "Succ = Func(w, Func(y, Func(x, App(y, App(App(w, y), x)))))\n",
    "N1 = App(Succ, Z)\n",
    "N2 = App(Succ, N1)\n",
    "N3 = App(Succ, N2)\n",
    "Add = Func(m, Func(n, Func(s, Func(z, App(App(m, s), App(App(n, s), z))))))\n",
    "Exp = Func(m, Func(n, App(n, m)))\n",
    "\n",
    "T = Func(t, Func(f, t))\n",
    "F = Func(t, Func(f, f))\n",
    "If = Func(l, Func(m, Func(n, App(App(l, m), n))))\n",
    "\n",
    "Test1 = App(App(Add, App(App(Exp, N3), N2)), N1)\n",
    "print(execute(Test1))\n",
    "Test2 = App(App(App(If, T), N1), Z)\n",
    "print(execute(Test2))\n",
    "```\n",
    "\n",
    "```\n",
    "(λt128.(λt129.(t128 (t128 (t128 (t128 (t128 (t128 (t128 (t128 (t128 (t128 t129))))))))))))\n",
    "(λt170.(λt171.(t170 t171)))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 10**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализуйте язык запросов (подмножество операций реляционной алгебры) с помощью генераторов.\n",
    "\n",
    "Это упражнение вдохновлено работой [A SQL to C Compiler in 500 Lines of Code](https://www.repository.cam.ac.uk/bitstream/handle/1810/293479/paper.pdf).\n",
    "\n",
    "1. Реализуйте генератор Scan('filename.csv'), который выдает очередную строку таблицы.\n",
    "1. Реализуйте функцию Print(parent), которая печатает все строки таблицы.\n",
    "1. Реализуйте генератор Filter(pred, filename), выдающий строки таблицы, для которых выполняется предикат pred. Для создания предикатов реализуйте ФВП Eq(x, y), Ne(x, y), Value(x), Field(x).\n",
    "1. Реализуйте генератор Project(new_schema, parent_schema, parent), который выполняет операцию проекции.\n",
    "1. Реализуйте генератор Join(left, right), который выполняет операцию внутреннего соединения с помощью вложенных циклов.\n",
    "\n",
    "Примеры запросов:\n",
    "\n",
    "```Python\n",
    "# select room, title from talks.csv where time='09:00 AM'\n",
    "Project(['room', 'title'], ['room', 'title'],\n",
    "        Filter(Eq(Field('time'), Value('09:00 AM')), Scan('talks.csv')))\n",
    "\n",
    "\n",
    "# select * from (select time, room, title as title1 from talks.csv)\n",
    "# join (select time, room, title as title2 from talks.csv)\n",
    "# where title1 <> title2\n",
    "Filter(Ne(Field('title1'), Field('title2')), Join(\n",
    "       Project(['time', 'room', 'title1'], [\n",
    "               'time', 'room', 'title'], Scan('talks.csv')),\n",
    "       Project(['time', 'room', 'title2'], ['time', 'room', 'title'], Scan('talks.csv')))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 11**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Изобразите [фрактал Жюлиа](http://paulbourke.net/fractals/juliaset/).\n",
    "\n",
    "Реализуйте его сначала на стандартном Питоне, а затем напишите версию на NumPy (с булевой индексацией и единственным циклом). Сравните быстродействие обоих результатов.\n",
    "\n",
    "![](images/julia.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задача 12**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализуйте [алгоритм Флойда-Стейнберга](https://intuit.ru/studies/courses/993/163/lecture/4511?page=3) с помощью NumPy.\n",
    "\n",
    "Старайтесь максимально использовать возможности NumPy.\n",
    "\n",
    "Пример работы:\n",
    "\n",
    "![](images/dither.jpg)\n",
    "\n",
    "![](images/dither_res.png)"
   ]
  }
 ],
 "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.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}