Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 5 - Программирующие Программы

5.1 Лисп - Не Функциональный Язык

Charlz_Klug 14.12.13 в 18:59

Одно из наиболее распространённых заблуждений о лиспе гласит: лисп - это функциональный язык программирования. Лисп - это не функциональный язык программирования. На самом деле можно утверждать, что лисп - это один из наименее функциональных языков программирования. Это ошибочное мнение имеет интересные корни и служит хорошим примером того, как маленькое недоразумение может может иметь долгоиграющие последствия, приводящие к путанице уже после того, как сами причины уже давно перестали соответствовать истине. Что такое функциональный язык программирования? Единственное, имеющее смысл определение следующее:

Charlz_Klug 15.12.13 в 16:07

Функциональный язык - это язык программирования, состоящий из функций.

Charlz_Klug 15.12.13 в 16:08

Итак, что же такое функция? Функция - это математическая концепция существующая на протяжении веков:

Charlz_Klug 15.12.13 в 16:10

Функция - это статичное, точно определённое преобразование исходных значений в результирующие значения.

Charlz_Klug 15.12.13 в 16:12

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

Charlz_Klug 15.12.13 в 16:17

(defun adder (x)
(+ x 1))

Charlz_Klug 15.12.13 в 16:17

Очевидно мы можем применить этот объект к любому числу и получить результат, но является ли adder настоящей функцией? Лисп утверждает что adder - это функция 1:

Charlz_Klug 17.12.13 в 03:29

1 Если вы до сих пор не знакомы с функцией COMMON LISP describe то вам нужно немедленно с ней ознакомиться. Примените describe к функции, специальной форме, макросу, переменной, символу и замыканию.

Charlz_Klug 17.12.13 в 03:33

* (describe #’adder)
#<Interpreted Function> is a function.

Charlz_Klug 17.12.13 в 03:33

Но, именование этих объектов функциями является некорректным использованием термина с глубокими корнями в истории лиспа. Defun и лямбда формы на самом деле создают процедуры, или если говорить более точно, экземпляры, вызываемые как функции (funcallable instances) [AMOP]. В чём различие? Процедуры не обязательно должны содержать в себе работу с преобразованием значений, но процедуры являются участками кода, возможно содержащим сохраняемую среду, которую можно выполнить (funcall). Когда лисп программисты пишут программы в определённом стиле, называемом функциональным стилем, то получающиеся процедуры можно рассматривать и комбинировать в математическом стиле функциональных преобразований.

Charlz_Klug 17.12.13 в 03:58

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

Charlz_Klug 17.12.13 в 04:09

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

Charlz_Klug 18.12.13 в 02:55

И наконец, обычно многие языки делают бессмысленное различие между выражением и оператором, для того, чтобы поддерживать ужасный Блаб синтаксис, например: инфиксный. В лиспе всё возвращает что-либо 2 и нет (синтаксических) ограничений для вложения или комбинации. Это простой вопрос с очевидным ответом: что более важно в языке, синтаксис, дружественный к новичкам, или настоящая гибкость? Все языки, которые используют инфиксный синтаксис уменьшают возможности абстракции многими способами. К счастью большинство современных языков доверяют своим пользователям пользователям и дают им возможность комбинировать выражения так, как они считают нужным. В сравнении с языками, которые принимают подобные мозгоубивающие синтаксические решения, лисп выглядит более функциональным.

Charlz_Klug 18.12.13 в 04:44

2 Исключением является ничего не возвращающий (values). Но, это сводится к nil и по этой причине может использоваться в выражениях.

Charlz_Klug 18.12.13 в 08:21

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

Charlz_Klug 18.12.13 в 08:40

Очевидно что лисп процедуры не являются функциями. Лисп процедуры могут возвращать не-статичные значения, эти процедуры вы можете вызывать несколько раз с одними и теми же аргументами и каждый раз можете получать разные значения. В наших примерах из предыдущих глав, лисп процедуры могут хранить состояния. Процедуры подобные rplaca могут изменять значения не только в памяти, но и в других местах (таких как регистры). Такие лисп процедуры как terpri и format создают вывод (новые строки в случае terpri) направляемые в терминал или файлы 3. Лисп процедуры подобные yes-or-no-p могут читать ввод из терминала и возвращать значения в зависимости от ввода пользователя. Являются ли эти процедуры статичными, точно определёнными преобразованиями?

Charlz_Klug 18.12.13 в 09:20

3 Terpri и rplaca - они были названы не просто так.

Charlz_Klug 18.12.13 в 09:39

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

Charlz_Klug 18.12.13 в 10:15

Выяснилось что большинство языков на самом деле не являются функциональными, после этого некоторые разработчики языков решили узнать как будет выглядеть программирование на настоящих функциональных языках. Как вы можете ожидать программирование на функциональных языках в основном раздражает и бывает непрактичным. Почти нет проблем относящихся к реальному миру и которые можно было бы выразить через статичные, чётко определённые преобразования из исходных значений в результирующие значения. Но это не значит что функциональное программирование не имеет плюсов и многие языки были спроектированы так, чтобы получить преимущества от функционального стиля программирования. Это означает нахождение удобного способа изоляции функциональных частей программ от (на самом деле интересных) не-функциональных частей. Такие языки как Haskell и OCaml используют эту изоляцию как средство создания агрессивных оптимизационных допущений.

Charlz_Klug 18.12.13 в 10:48

Но это лисп. Мы очень не-функциональны и очень гордимся этим. По мере того, как увеличивается польза от изоляции побочных эффектов, лисп программисты могут и должны реализовывать это с помощью макросов. Настоящее назначение функционального программирования в том, чтобы разделить функциональное описание того что происходит от механизма происходящих событий. Определённо, лисп не функционален, но, поскольку у нас есть макросы. И нет лучшей платформы или материала чем макросы для реализации более функционального языка чем лисп.

Charlz_Klug 18.12.13 в 11:08

5.2 Программирование Сверху-Вниз

Charlz_Klug 20.12.13 в 15:16

Вы не можете обучать новичков программированию сверху вниз, поскольку они не знают какой низ является верхом.
- Чарльз Энтони Ричард Хоар

Charlz_Klug 20.12.13 в 15:29

В разделе 3.2, Предметно Ориентированные Языки при первом знакомстве с предметно-ориентированными языками мы создали простой макрос unit-of-time. Этот макрос дал нам удобный способ определения периодов времени в различных величинах с помощью основанного на символах, интуитивно-понятного синтаксиса:

Charlz_Klug 20.12.13 в 15:33

* (unit-of-time 1 d)
86400

Charlz_Klug 20.12.13 в 15:33

Unit-of-time - это удобный предметно-ориентированный язык, поскольку программисту не требуется помнить, например, количество секунд, содержащихся в сутках. Unit-of-time реализован с помощью простого макроса, использующего оператор case в роли сердцевины для нижележащего расширения.

Charlz_Klug 20.12.13 в 15:38

Важным принципом в проектировании макросов является программирование сверху-вниз (top-down). Проектирование лисп макроса следует начать с создания абстракции.Вам нужно писать программы, использующие макросы ещё до того, как вы написали сам макрос. Что парадоксально, вам нужно знать как писать на языке ещё до того, как вы сможете написать краткое определение/реализацию этого языка.

Charlz_Klug 20.12.13 в 15:46

Таким образом первым шагом в конструировании серьёзного макроса является написание вариантов использования (use cases) макроса, даже если нет никакого способа с помощью которых вы смогли бы проверить или использовать эти макросы. Если программы, написанные в этом новом языке окажутся достаточно объемлющими, то идея о том, что лучше реализовать: компилятор или интерпретатор последует сама собой.

Charlz_Klug 20.12.13 в 15:55

Рассмотрим наш макрос unit-of-time, существует ли способ перевести этот макрос на ещё больший уровень спецификации и создать язык, предназначенный для создания макросов, создающих удобные единицы измерения? Что же, unit-of-time - это макрос, и чтобы выполнить задуманное, нам нужен макрос, определяющий другой макрос...

Charlz_Klug 20.12.13 в 16:00

Стоп! Этот низ является верхом.

Charlz_Klug 20.12.13 в 16:00

Мы начали рассматривать задачу не с реализации языка, а с того, что задали себе вопрос: для чего мы хотим использовать этот язык? Ответ оказался следующим: мы хотим получить простой способ определения вспомогательных программ, преобразующих единицы измерения. В следующем варианте использования мы хотим получить тип единицы измерения, time, базовую единицу выраженную в секундах и представленную здесь через s, набор пар из единиц и коэффициентов преобразования этих единиц в базовую единицу:

Charlz_Klug 20.12.13 в 16:14

(defunits% time s
m 60
h 3600
d 86400
ms 1/1000
us 1/ 1000000)

Charlz_Klug 20.12.13 в 16:14

Defunits% может расшириться в код, определяющий макрос, подобный unit-of-time, написанный нами в разделе 3.2, Предметно-Ориентированные Языки, что позволяет нам преобразовывать произвольные единицы времени в секунды. Можно ли ещё более улучшить этот код?

Charlz_Klug 20.12.13 в 16:22

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

Charlz_Klug 20.12.13 в 16:35

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

Charlz_Klug 20.12.13 в 16:41

(defunits%% time s
m 60
h (60 m)
d (24 h)
ms (1/1000 s)
us (1/1000 ms))

Charlz_Klug 20.12.13 в 16:42

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

Charlz_Klug 21.12.13 в 17:57

Заметьте, что этот новый язык может больше, чем просто предоставление удобного синтаксиса для добавления новых типов единиц. Этот язык также позволяет нам уменьшить воздействие округления (rounding) в наших вычислениях и позволяет лиспу использовать настолько точную арифметику насколько это возможно. Например, фарлонг - это 1/8 мили, и если мы закодируем это значение с использованием очередизации взамен, скажем, метрического приближения, то в конечном итоге мы можем получить более точные результаты или, что ещё более важно, результаты, максимально соответствующие вычислениям, произведёнными с помощью миль. Поскольку нам достаточно всего лишь добавить самый точный коэффициент преобразования не прибегая к каким-либо другим преобразованиям, то этот макрос даёт нам возможность создавать правила на уровне выражений, невозможных в других языках.

Charlz_Klug 24.12.13 в 09:48

Используя поведение автоматических gensym-ов, описанное в разделе 3.5, Нежелательный Захват, написание defunits% оказывается чрезвычайно простым делом. Функция Грэма symb сгенерирует новое имя для макроса конвертации. Например, если символ time - это тип уже существующей единицы, то новый макрос конвертации будет называться unit-of-time. Defunits% был сконструирован исходя из описания unit-of-time, описанном в разделе 3.2, Предметно-Ориентированные Языки, но, этот код окружён defmacro! и обратной кавычкой, и замещены части, нуждающиеся в повторном создании при каждом вызове макроса.

Charlz_Klug 24.12.13 в 10:19

Листинг 5.1: DEFUNITS-1
(defmacro! defunits% (quantity base-unit &rest units)
`(defmacro ,(symb 'unit-of- quantity) (,g!val ,g!un)
`(* ,,g!val
,(case ,g!un
((,base-unit) 1)
,@(mapcar (lambda (x)
`((,(car x)) ,(cadr x)))
(group units 2))))))

Charlz_Klug 24.12.13 в 10:30

Defunits% использует вложенные обратные кавычки - чрезвычайно сложную для понимания конструкцию. Программирование с обратными кавычками - это тоже самое, что и обладание ещё одним смысловым измерением в коде. В других языках, определённый программный оператор обычно обладает очень простой вычислительной семантикой. Вы знаете когда буден запущен каждый бит кода, поскольку каждый бит кода вынужден выполняться в одно и тоже время: во время выполнения. Но в лиспе с помощью вложенных обратных кавычек мы можем масштабироваться вверх и вниз по лестнице закавычивания (ladder of quotation). Каждая написанная нами обратная кавычка - это один шаг по этой лестнице: наш код - это список, вычисление которого зависит от нашего желания. Но внутри обычного списка каждая встреченная запятая переносит нас на шаг вниз по лестнице закавычивания и исполняет код из соответствующего шага лестницы [CLTL2-P967].

Charlz_Klug 24.12.13 в 11:00

Таким образом это простой алгоритм для определения времени вычисления каждого бита из лисп формы. Просто начните с корня выражения и после встречи с каждой обратной кавычкой пометьте переход на ещё один уровень закавычивания. Для каждой встреченной запятой пометьте переход на уровень ниже. Как заметил Стил [CLTL2-P530], следование этому уровню закавычивания может быть трудной задачей. Эта трудность - потребность отслеживать вашу текущую глубину вложения - это то, что заставляет ощущать использование обратных кавычек другим измерением добавленным в обычное программирование. В других языках вы можете пойти на север, юг, восток и запад, но лисп вдобавок даёт вам возможность перемещаться вверх.

Charlz_Klug 24.12.13 в 11:12

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

Charlz_Klug 24.12.13 в 11:23

Листинг 5.2: DEFUNITS-CHAINING-1
(defun defunits-chaining% (u units)
(let ((spec (find u units :key #'car)))
(if (null spec)
(error "Unknown unit ~a" u)
(let ((chain (cadr spec)))
(if (listp chain)
(* (car chain)
(defunits-chaining%
(cadr chain)
units))
chain)))))

Charlz_Klug 25.12.13 в 03:19

Следует помнить, что макросы - это на самом деле просто функции, мы создали функцию-утилиту для использования её в определении макроса, defunits-chaining%. Эта функция-утилита получает единицу, определённую символами, подобными S, M или H, и список определений единиц. Мы разрешаем работу с определениями единиц до получения числа, которое будет интерпретироваться базовой единицей, например (M 60) или списком, содержащим неявную отсылку к другой единице в очереди, например (H (60 M)).

Charlz_Klug 25.12.13 в 03:30

Это рекурсивная функция-утилита. Для нахождения множителя, применяемого для базовой единицы мы перемножаем каждое звено очереди с другим вызовом функции-утилиты используемой для обработки остальной части очереди. После возврата из стека вызовов мы получим множитель, применяемый для конвертации значения единицы в значение базовой единицы. Например, когда мы конструируем множители для часов, мы находим что в одном часе 60 минут. Мы переходим в рекурсию и находим что в одной минуте 60 секунд. Мы опять переходим в рекурсию и находим что секунда - это конец очереди - минуты были определены непосредственно в терминах базовых единиц. Итак, вернувшись из рекурсии мы вычисляем (* 60 (* 60 1)), что равняется 3600: то есть, в одном часе 3600 секунд.

Charlz_Klug 25.12.13 в 05:14

Листинг 5.3: DEFUNITS-2
(defmacro! defunits%% (quantity base-unit &rest units)
`(defmacro ,(symb 'unit-of- quantity) (,g!val ,g!un)
`(* ,,g!val
,(case ,g!un
((,base-unit) 1)
,@(mapcar (lambda (x)
`((,(car x))
,(defunits-chaining%
(car x)
(cons `(,base-unit 1)
(group units 2)))))
(group units 2))))))

Charlz_Klug 26.12.13 в 08:40

После определения этой функции-утилиты, для работы с множителем для каждой единицы требуется простая модификация defunits%, которую мы выполнили в defunits%%. Вместо объединения в значение прямо из определения единицы мы передаём каждую единицу и целое определение единицы в утилиту defunits-chaining%. Как было описано выше, эта функция рекурсивно преобразует множитель, требуемый для каждой единицы, в базовую единицу. С этим множителем defunits%% может объединять значение в case операторы, также, как это выполняет defunits%.

Charlz_Klug 26.12.13 в 09:22

Эти макросы всё ещё не завершены. Макрос defunits% не поддерживает очередизацию. Defunits%% поддерживает очередизацию, но не проверяет на наличие ошибок. Профессиональный писатель макросов всегда заботится об обработке любых возможных ошибочных состояний. Особенно важны возникновения бесконечных циклов или другие трудные для отладки в REPL-е случаи.

Charlz_Klug 26.12.13 в 09:51

Проблема связанная с defunits%% является частью создаваемого нами языка: в этом языке возможны программы, содержащие циклы. Например:

Charlz_Klug 26.12.13 в 09:53