SICP. Основы

Начинаем проходить СИКП — это курс из университета МИТ. Он объясняет вычислительные процессы, как они развиваются и управляют разными данными, проще говоря — смысл абстракции в компутере.

Введение

Процессы создаются и управляются командами на языке программирования. Эти команды складываются в последовательность и получается программа.
Основными инструментами всех ЯПшек являются простейшие математические действия на два объекта: 4+5, 9/3, 200×5, 0-0
Из маленьких действий получаются и надстраиваются конструкции сложнее и сложнее:
$$ \left( \frac{3^{-\frac{5}{7}} \cdot 5^{-\frac{5}{7}}}{15^{-1} \cdot 2^{\frac{2}{7}}} \right)^{-7} $$
Всё раскладывается до простых арифметических, а потом и до логических действий.

Базовые элементы

Оригинальный курс изучается на языке Scheme, по-русски — Ским. Его особенность в том, что сначала пишется операция, а потом операнды и всё это в скобках. Это нужно для наглядности: что с чем складывается или умножается, на картинках они будут чёрного цвета.
Порядок действий такой же как и в обыкновенной математике: сначала возведение в степень и корни, потом умножение и деление, потом сложение и вычитание. Математические скобки будут зелёного цвета.

(+ 3 5)
(× 5 6)
(×(+ 3 5) 9) ; 8×9

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

2 × ( (2+18+13-3) / (7+3-7) ) – В математике
(* 2 (/ (- (+ (+ 2 18) 13) 3) (- (+ 7 3) 7))) – На скиме

Абстракция

Объявление переменных — самое простое средство абстракции. То есть сейчас мы говорим компьютеру: на это слово делай вот это. На переменную с этим именем, ты достаёшь из памяти вот это значение.

У нас недавно был курс по пайтону и мы решили, что СИКП мы будем описывать то на скиме, то на пайтоне.

На скиме
(define pi 3.14159)
(define radius 4)
(define height 8)
(define cylinder_capacity (* radius radius pi height))

На пайтоне
pi = 3.14159
radius = 4
height = 8

cylinder_capacity = radius ** 2 * pi * height

Развиваем абстракцию

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

Функция работает как маленькая подпрограмма: получает данные на вход, шаманит и выдаёт результат. Чтобы она работала, её нужно объявить, дать имя и задать формальные параметры входных данных. Это переменные для входных данных.

Для примера возьмём квадратный корень с формальным параметром: \(\sqrt n\)
Буква n показывает, что сюда нужно подставлять значения.

Так как это функция, пользоваться ей можно неограниченное число раз

Ещё абстрактней

Функции можно комбинировать, после этого получится функция с большей абстракцией.

# Функция для вычисления квадрата числа  
def square(num):
    return num * num

  # Функция для вычисления суммы квадратов чисел
def sum_square(a, b):
    return square(a) + square(b)

print(sum_square(2, 4))  # => 20

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

  1. Вызов функции sum_square(2, 4) в строке print(sum_square(2, 4)). Двойка подставляется на место a, четвёрка на место b
  2. Смотрим на функцию: вместо a подставляется 2, вместо b — 4. Получается square(2) + square(4)
  3. Теперь вызывается функция square. Первый вызов с 2, второй с 4. Первый возвращает 4, второй 16
  4. Возвращаемся в тело sum_sqaure, выражение square(a) + square(b) вычисляется в 4 + 16
    Это выражение вычисляется в число 20 и возвращается из функции sum_square

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

Аппликативный и нормальный

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

Нормальный — интерпретатор не будет вычислять операнды пока они не понадобятся.

В МИТе придумали тест для интерпретатора. После его выполнения становится понятно с каким порядком вычислений работает интерпретатор.

def p():
    return p()


def test(x, y):
    if x == 0:
        return 0
    return y

test(0, p())

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

Интерпретатор остановил функцию потому что она ушла в слишком глубокую рекурсию

Некоторые интерпретаторы работают с нормальным порядком. Например интерпретатор Хаскеля, код для проверки будет выглядеть так

-- Объявляем функцию с бесконечной рекурсией
p = p
-- Объявляем функцию для проверки порядка вычисления
test x y = if x == 0 then 0 else y

-- Вызываем функцию проверки
main = print( test 0 p )

При запуске код вернёт ноль, а не упадёт от бесконечной рекурсии.

Нормальный порядок ещё называют ленивыми вычислениями
Поделиться
Отправить
Запинить
 118   2 мес   sicp
Популярное