Функциональное программирование на Python. Часть 4. Данные и программы

Рассмотрим два подхода, определяющих взгляд на то, чем являются программы и данные. Первый с позиции фон неймановской архитектуры и Машины Тьюринга, второй с позиции Лямбда-исчисления и функционального подхода.

Путь первый

Для начала представим, что у нас есть файл, который содержит текстовую строку: hello:

Если мы посмотрим на этот файл в hex-редакторе, то увидим, что он представляет собой последовательность байт (цифр). В нашем случае это цифры: 0x68, 0x65, 0x6C, 0x6C, 0x6F:

Но с другой стороны эту последовательность можно представить как единое натуральное число: 448378203247:

Сделаем копию этого файла:

Новый файл будет тем же самым числом, но располагаться будет уже в другом месте.

А что из себя представляет сама программа для копирования файлов?

Она также является натуральным числом, только больше чем то, что представляло файл file1.txt:

На рисунке copy() – это утилита cp из Ubuntu Linux. Приведенные цифры – это то, что вы увидите, если откроете cp в hex-редакторе (в вашем случае они могут отличаться).

Из вышесказанного, можно сделать вывод, что данные и программы, для их обработки – это числа!

Программы принимают на вход числа, модифицируют и возвращают их в качестве результата:

Такой взгляд на данные и программы характерен для фон неймановской архитектуры. Т.е. данные и программы, по сути, ничем не отличаются друг от друга. Конкретный набор байт мы можем выполнить как программу, передавая соответствующие значения в процессор, либо можем провести над ними некоторую операцию обработки, считая их набором данных (например, если мы хотим зашифровать программу или включить ее в архив). Есть такие программы – упаковщики, они определенным образом изменяют исполняемый файл (сжимают, шифруют). Для пользователя, работа с полученной в результате “упаковки” программой, ничем не отличается от работы с исходным вариантом. Структурно, “упакованная” программа состоит из загрузчика и оригинальной программы в закодированном виде. При ее запуске, вначале выполняется загрузчик, он декодирует исходную программу (т.е. программа здесь воспринимается как набор данных для обработки), после этого распакованная программа запускается. Набор байт, который только что воспринимался для одной программы (загрузчика) как данные, теперь интерпретируется (для нас) как программа.

Теоретической базой такого подхода является Машина Тьюринга (далее МТ). Кратко рассмотрим, как она работает. В нашем распоряжении есть бесконечная лента (в оба направления), на ленту мы может записывать и считывать с нее определенные символы из набора (алфавита), который заранее известен. Работа с лентой осуществляется с помощью считывающей головки. Сама машина может находиться в одном из определенных состояний. Вся ее работа заключается в том, что считывающая головка передвигается вдоль ленты (или двигается лента, а головка остается на месте), считывает и записывает на ленту данные и меняет свое состояние в соответствии с определенным алгоритмом, который называется описание Машины Тьюринга (фактически это программа на специализированном языке).

Структурно МТ выглядит следующим образом:

Для примера построим МТ, которая будет проверять четное или нечетное число записано на ленте. Зададим множество символов, которые могут быть записаны / считаны с ленты: S = {0, 1, B}, множество состояний МТ: Q = {q0, q1, H} и множество направлений движения считывающей головки: M = {L, R}.

Теперь мы можем описать МТ с нужным нам функционалом, для этого воспользуемся языком следующего вида:

(символ, считанный с ленты), (состояние МТ) -> (символ, записанный на ленту) (новое состояние МТ) (направление движения головки)

Опишем МТ, определяющую четность числа:

0, q0 -> 0, q0, R
0, q1 -> 0, q1, R
1, q0 -> 0, q1, R
1, q1 -> 0, q0, R
B, q0 -> 0, H, -
B, q1 -> 1, H, -

После того, как созданная нами МТ останавливается, в ячейку, на которую указывает считывающая головка, будет записана цифра 1 если число нечетное или 0 если оно четное.

Проверим четность числа 9, в двоичной записи оно имеет вид 0b1001.

Набор символов, который мы может записывать/считывать с ленты, и тот, с помощью которого можно описать МТ (см. на нашу программу выше), может быть одним и тем же. Развивая эту идею, мы придем к тому, что можно построить универсальную МТ, которая считывает с ленты описание другой МТ и выполняет ее.

Интерпретатор Python, по сути – это универсальная МТ, а программный код, который она выполняет – конкретная МТ. Мы можем на языке Python написать интерпретатор Python, который будет выполнять Python-скрипты. Т.е. универсальная МТ, может выполнять универсальную МТ и т.д.

Мы сформировали первую точку зрения на данные и программы для их обработки – все есть числа! То есть по сути, все является данными, только некоторые наборы данных интерпретируются как вычислительные процессы, если с ними работать определенным образом.

В архитектуре фон Неймана данные и программы находятся в одном месте, память для них общая. Есть альтернативные архитектуры, например, Гарвардская, в которой предусмотрена отдельная область памяти для программ, отдельная для данных. В качестве примера вычислительных устройств, использующих Гарвардскую архитектуру, можно привести микроконтроллеры фирмы Atmel линейки ATMega.

Путь второй

Теперь предлагаем вам подумать немного по другому.

Представьте, что у нас есть кортеж из двух элементов – пара (см. ФП на Python. Часть 3):

(a, b).

Помимо конструктора пары, как вы помните, нам нужны два селектора: fst и snd, для извлечения первого и второго элементов:

Такая задача довольно просто решается на Python, и мы уже это делали:

А теперь посмотрите, пожалуйста, очень внимательно, на выделенный кусок кода на картинке ниже, который реализует альтернативный вариант построения конструктора и селекторов:

Приведем этот код в текстовом виде, чтобы вы могли его скопировать, если вдруг вам захочется с ним поэкспериментировать:

def pair(a, b):
    def helper(z):
        if z == 0:
            return a
        elif z == 1:
            return b
        else:
            return None
    return helper

def fst(p):
    return p(0)

def snd(p):
    return p(1)

С точки зрения пользователя библиотеки ничего не поменялось, он, как работал с функциями pair, fst, snd, так и продолжает это делать. Но с точки зрения реализации это совершенно полярная вещь! Теперь мы оперируем функциями, pair возвращает уже не кортеж из двух элементов, которые в виде структуры данных хранятся в памяти, а функцию, которая возвращает первый или второй аргумент в зависимости от переданного в нее значения! В данном случае граница между тем, что мы обычно (интуитивно) считаем как данные, а что определяем как функцию размылась. Только теперь, мы все воспринимаем не как данные (числа), а как функции.

Идея функционального подхода ко всему, как к функциям, так и к данным, лежит в основе lambda calculus (λ-calculus) – лямбда исчисления (далее λ-C), которое разработал Алонзо Черч в 1930-х годах для формализации и анализа понятия вычислимости. Хорошее введение в λ-C можете посмотреть здесь. В двух словах расскажем, что это такое.

Основным строительным блоком в λ-C является терм. Термом может быть:

x – переменная
(λx.M) – абстракция
(M N) – применение

Абстракция задает функцию (далее понятия функция и абстракция будем воспринимать как синонимы). Например, функция id(x), которая возвращает переданный ей аргумент будет выглядеть на языке λ-C так:

id := λx.x

В математике мы бы написали:

id(x)=x

На Python можно это реализовать через def:

def id(x):
    return x

либо через lambda:

id = lambda x: x

Применение – это применение функции (алгоритма) к набору входных данных. В нашем примере M N, M – это функция, а N – это данные, с которыми она будет работать. Принципиально в λ-C, то что разницы между алгоритмами и данными нет. Точно также, когда мы говорили про Машины Тьюринга, мы не делали разницы между МТ и данными для обработки, там все было данными (числами). В λ-C тоже нет разницы, но теперь все есть функции.

Приведем пример работы абстракции и применения. Создадим абстракцию:

λx.2x

Теперь применим ее к 7-ке:

(λx.2x) 7

Проведем редукцию полученного выражения:

=> (λx.2x) 7
=> 2*7
=> 14

Воспринимайте его пока как иллюстрацию принципа. Дело в том, что в λ-C нет чисел (которыми мы только что оперировали: 2, 7, 14), в нем есть только функции, а числа – это конструируемый объект.

Вспомните, пожалуйста, как работает логическая функция AND:

X	Y	AND(X, Y)
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	FALSE	FALSE
FALSE	FALSE	FALSE

Попробуем ее реализовать. Для начала решим вопрос с TRUE и FALSE, т.к. таких элементов в λ-C нет, построим их с помощью абстракций (т.е. сконструируем по аналогии с тем, как мы сделали pair):

TRUE := λx.λy.x
FALSE := λx.λy.y

ТRUE – это функция, которая принимает на вход два аргумента (x и y) и возвращает первый, FALSE также принимает два аргумента, но возвращает уже второй. Другими словами мы приняли следующее утверждение: вот такую функцию λx.λy.x будем называть TRUE, а такую λx.λy.y – FALSE.

Теперь построим функцию AND:

AND := λp.λq.p q p

Реализуем TRUE, FALSE и AND на Python:

TRUE = lambda x: lambda y: x
TRUE.__name__ = "TRUE"

FALSE = lambda x: lambda y: y
FALSE.__name__ = "FALSE"

AND = lambda p: lambda q: p(q)(p)

Попробуем поэкспериментировать:

>>> AND(TRUE)(TRUE).__name__
'TRUE'

>>> AND(TRUE)(FALSE).__name__
'FALSE'

>>> AND(FALSE)(TRUE).__name__
'FALSE'

>>> AND(FALSE)(FALSE).__name__
'FALSE'

Все работает как надо! Подобным образом мы может сконструировать числа, например ноль, единица и двойка будут выглядеть так:

0 := λf.λx.x
1 := λf.λx.f x
2 := λf.λx.f (f x)

Сложение можно представить как:

PLUS := λm.λn.λf.λx.m f (n f x)

На рассмотренном выше примере мы увидели, что данные и программы (функции), которые работают с ними, являются функциями!

Наша функция AND принимает в качестве аргументов функции и результатом ее работы тоже является функция.

В зависимости от того, как мы “смотрим” на программы (функции) и данные, будет использоваться та или иная формальная система (МТ, λ-C). Оба этих подхода самодостаточны, все, что вы можете сделать с помощью Машины Тьюринга (или написать программу на языке, поддерживающем императивный стиль программирования (C, C++, Java, C#, Python)), вы это же можете сделать на lambda calculus – (функциональном языке (Haskell, OCaml)). Существует ещё довольно много различных видов формальных систем для анализа и формализации вычислимости: Машины Поста, Нормальные алгоритмы Маркова, Рекурсивные функции и т.п., все они, с теоретической точки зрения, эквивалентны друг другу. С практической же стороны у каждого из подходов есть свои достоинства и недостатки. В первую очередь это определяется моделью вычисления (“подстановочная” либо “с окружениями”). Об этом мы поговорим в следующей статье.

P.S.

Вводные уроки по “Линейной алгебре на Python” вы можете найти соответствующей странице нашего сайта. Все уроки по этой теме собраны в книге “Линейная алгебра на Python”.

Если вам интересна тема анализа данных, то мы рекомендуем ознакомиться с библиотекой Pandas. Для начала вы можете познакомиться с вводными уроками. Все уроки по библиотеке Pandas собраны в книге “Pandas. Работа с данными”.