6 заметок с тегом

sicp

SICP. Интервалы

В прошлой статье мы написали крохотную библиотеку для работы с обыкновенными дробями. Теперь напишем ещё одну для работы с интервалами. В вычислениях будут десятичные дроби, поэтому мы как бы дополним прошлую библиотеку.

Интервалы

Интервал — последовательность чисел от нижней до верхней границы с каким-то шагом, например интервал от 3 до 6 с шагом 1 выглядит так: [3, 4, 5, 6].
Интервальная арифметика часто используется в электрике, например чтобы вычислить сопротивление резистора или их соединений, обычно там важны только два числа — нижняя и верхняя границы интервала.

Размер интервала получается из разности: большее − меньшее

Как мы сказали выше, для описания интервала нужны только два значения, для этого отлично подходит пара из нашей библиотеки. Поэтому абстракция крутая штука — из одного файла, можно сделать разные сценарии с парами чисел: дроби, интервалы, координаты, комплексные числа, список, прокси в виде айпи и порта, и всё другое что можно представить в виде пары значений.

Сначала пишем конструктор для создания интервала и два селектора, они будут доставать нижнюю и верхнюю границы, потом проверим чтобы всё это работало.

from cmpd_data import pair


# Проверяем какое из чисел больше
# Это нужно чтобы первым элементом в паре всегда была нижняя граница
# Вторым элементом – верхняя
def make_interval(a, b):
    if a < b:
        return pair.cons(a, b)
    return pair.cons(b, a)


# Достаём нижнюю границу
def lower_bound(interval):
    return pair.car(interval)


# Достаём верхнюю границу
def upper_bound(interval):
    return pair.cdr(interval)


# Проверяем, что условие в конструкторе работает как нужно
interval_a = make_interval(2, 4)
print(lower_bound(interval_a), upper_bound(interval_a))

interval_b = make_interval(4, 2)
print(lower_bound(interval_b), upper_bound(interval_b))

Запускаем код и видим, что конструктор правильно расставляет границы.

$ python3 interval.py
2 4
2 4

Операции

Допишем в файл пять основных операций: сложение, вычитание, умножение, деление и вывод. Ещё напишем вычисление центрального числа и радиуса интервала, это нужно чтобы красиво выводить результаты.

Этот файл можно допиливать до бесконечности: добавить новые функции или улучшить старые, но это нам пока не нужно. Проверим как код справляется с простой задачей в электрике.

Проверяем на двух резисторах
Есть два резистора с сопротивлением в 4 и 6 Ом, погрешность каждого — 5%. Подключаем их параллельно и считаем общее сопротивление цепи, вот формула: \(\frac {R_1 * R_2} {R_1 + R_2}\), R1 и R2 — интервал сопротивления резистора с погрешностью.

Запускаем код и получаем общее сопротивление цепи в 2.29 Ом и погрешность в 23%.

$ python3 resistor.py
2.29±0.23

Зачем делить код на разные файлы

У нас есть библиотека для работы с обыкновенными дробями и интервалами, дробь и интервал мы создали через пару, можно сделать ещё всего и побольше. Мы можем всё это намешать в один файл и создание дробей и интервалов выглядело бы так

from cmpd_data import pair

x = cons(4, 5)  # Создаём обыкновенную дробь
a = cons(3.56, 5.65)  # Создаём интервал

Это грязно, так делать не нужно. Выглядит непонятно и запутанно, а в коде это ещё хуже.
Чтобы такого не было, мы делим код на логические файлы и отделяем реализацию понятия от его использования, это и есть абстракция данных. Код становится понятным даже без комментариев и его можно легко изменять: не нужно вылавливать в коде все создания дробей и связанные с ними операции, достаточно изменить код в конструкторе make_rational и его селекторах.

x = make_rational(4, 5)
a = make_interval(3.56, 5.65)
 10   20 ч   sicp

SICP. Абстракция данных. Обыкновенные дроби

В прошлых статьях мы рассказывали про абстракции функций: простых и сложных.
С этой статьи мы начнём разбирать абстракцию данных: как из простых данных строить составные типы, как их видит компьютер и другие сложности представления всего в памяти.

Чтобы посмотреть абстракцию данных на реальном примере, в курсе писали библиотеку для работы с рациональными числами и их операциями. Не будем изобретать велосипед, поэтому будем делать такую же библиотеку.

Обыкновенные дроби

На листочке выглядит достаточно просто: \(\frac{5}{9}\). Но компьютеру нельзя просто сказать: «поставь палку между двумя числами и думай, что это дробь.» Надо писать абстракции для дробей и вообще не целых чисел.

Целое число — простейший элемент абстракции.

Библиотека дробей

Как мы сказали выше, дробь это пара чисел и палка деления между ними. Тип данных «пара» мы уже делали в прошлой статье, его и возьмём.

Тут будут использоваться селекторы и конструктор, сейчас объясним:
Селекторы — функции-манипуляторы, они достают по одному значению из пары
Конструктор — функция-упаковщик с замыканием, чтобы хранить значения пары

В функции cons есть ещё функция make_pair для замыкания данных между двумя областями видимости. Так данные принимают абстрактный вид и на месте пары «числитель-знаменатель» может быть две строки. Про замыкания у нас есть статья из курса по Пайтону.

a = cons(4, 5)  # В а лежит функция, она замкнула числитель 4 и знаменатель 5

print(car(a))  # Выводится числитель – 4
print(cdr(a))  # Выводится знаменатель – 5

Этот файл нужен чтобы разделить реализацию абстракции данных от её использования. То есть в pair.py ничего не изменяется и не проверяется, просто данные.

Пишем операции

Теперь сделаем ещё файл, он будет для операций и вывода.
Чисто теоретически-технически, мы можем использовать pair.py для склеивания строк и даже других пар, потому что абстракция.

В каждой операции числители и знаменатели отделены друг от друга, потому что для компьютера это всё равно два отдельно взятых целых числа. Когда всё сделано, из новых значений опять собирается дробь через make_rational.

Красиво дошлифуем

Всё работает, но дроби не сокращаются. Нужно написать ещё функцию для поиска общего знаменателя и сокращения на него. Евклид уже всё придумал, поэтому мы заворачиваем алгоритм в отдельную функцию.
Добавляем сокращение дробей в конструктор, «//» — деление без остатка

 15   7 дн   sicp

SICP. Высшие функции

В прошлой статье про простые процессы мы разобрались, что функции это просто шаблоны для подстановки значений.

Такое же можно делать с функциями — передать её в другую функцию как аргумент и вернуть как значение. Такие функции называются высшими и они выше по уровню абстракции, чем обычные функции

Вот например, мы ищем сумму ряда чисел и сумму ряда квадратов чисел через рекурсивные функции

# Функция для поиска суммы чисел в последовательности
def sum_sequence(start, end):
    if start > end:
        return 0
    return start + sum_sequence(start + 1, end)


# Функция для поиска суммы квадратов чисел
def sum_square_sequence(start, end):
    if start > end:
        return 0
    return start ** 2 + sum_square_sequence(start + 1, end)


print(sum_sequence(1, 10))  # => 55
print(sum_square_sequence(1, 10))  # => 385

1. Пишем схему вычислений

Мы описали абстракцию суммы двух разных рядов, но схема вычислений везде одинаковая: проверяем условие, если start > end то возвращаем 0, иначе возвращаем сумму текущего значения и значение вызова функции.

Переделаем это всё в высшую функцию и назовём sum. Она будет принимать четыре аргумента:

  • current_change — функция для изменения значения start на текущем шаге
  • next_change — функция для изменения start на следующий шаг
  • start — значение нижней границы
  • end — значение верхней границы

Появляется проблема: чтобы использовать функцию sum нужны дополнительные функции, потому что изменить значения вручную не получится. Пишем дополнительные функции и упаковываем в код

# Функция для увеличения значения на единицу
def inc(x):
    return x + 1


# Функция для поиска суммы чисел в последовательности
def sum_sequence(start, end):
    # Возвращает переданное значение
    def identity(x):
        return x

    return sum(identity, inc, start, end)


# Функция для поиска суммы квадратов чисел в последовательности
def sum_square_sequence(start, end):
    # Возводит значение в квадрат
    def square(x):
        return x * x

    return sum(square, inc, start, end)


def sum(current_change, next_change, start, end):
    if start > end:
        return 0
    return current_change(start) + sum(current_change, next_change, next_change(start), end)


print(sum_sequence(1, 10))  # => 55
print(sum_square_sequence(1, 10))  # => 385

2. Рефакторим код

Всё работает, но это выглядит не красиво. Тут помогут анонимные функции — лямбды, в математике и программировании их обычно используют как одноразовые объекты.
Команда lambda создаёт функцию без имени и если её никто не использует, то транслятор её пропускает и не тратит память.

# интерпретатор просто создаст функцию и потом удалит её из памяти, она никак не используется
lambda x: x * x

# "x" – аргумент, после него пишется то, что вернёт функция. Работает как return
square = lambda x: x * x 
print(square(4))  # => 16

square = lambda x: x * x по сути то же самое, что и обычное объявление def square(x), поэтому линтер пайтона будет предлагать переписать функцию через def.

Переписываем код ещё раз с помощью лямбда функций

def sum_sequence(start, end):
    return sum(lambda x: x, lambda x: x + 1, start, end)


def sum_square_sequence(start, end):
    return sum(lambda x: x * x, lambda x: x + 1, start, end)


def sum(current_change, next_change, start, end):
    if start > end:
        return 0
    return current_change(start) + sum(current_change, next_change, next_change(start), end)


print(sum_sequence(1, 10))  # => 55
print(sum_square_sequence(1, 10))  # => 385

Теперь красиво, но это придуманный пример для наглядности. Сделаем что-то наглядное, например точки на графике.

Делаем координаты

Напишем свою библиотеку для работы с точками, самой крутой абстракцией будет точка. У точки есть две координаты: (x, y), чтобы хранить их создадим новый тип данных — пару.
Для кода возьмём имена из Скима: cons, car и cdr.
cons — создаёт список
car — достаёт первый элемент из списка
cdr — достаёт все остальные элементы

Функции car и cdr работают благодаря замыканию, мы разбирались с ним в статье про области видимости.

Теперь у нас есть новый тип данных — пара, его можно использовать для абстракции всего, что можно представить через пару чисел — точка, дробное число, комплексное число и куча всего остального.

Дальше забываем как устроена пара и используем её интерфейс чтобы написать реализацию точки

С помощью абстракции код становится легче для понимания, выглядит красивее и рефакторится без боли: мы можем изменить реализацию пары и нам не придётся переписывать код точки и всего остального над ней.

Теперь мы можем работать с абстракцией точки, нам не важно как она устроена внутри и почему работает, мы просто знаем как её использовать. Чтобы увидеть наши точки, импортируем модуль pyplot из библиотеки matplotlib.

Через свою библиотеку мы создали три точки с координатами (2, 4), (4, 6), (6, 4), а через pyplot нарисовали их
 17   14 дн   sicp
Ранее Ctrl + ↓