On LISP

Как правило, знакомство с LISPом (не имею в виду какую-то конкретную реализацию) начинается с представления s-expressions как “особой записи привычных по другим языкам вызовов функций”. Это не очень точно и скучно. На мой взгляд, куда интереснее проследить рост лисп-программы с самых ее корней, от простейшей структуры данных.

Для тех, кто совсем-совсем не в теме — лисп-машина это полная по Тьюрингу система, состоящая из вложенных друг в друга вызовов eval(). Ну примерно так. Лисп (для краткости буду так дальше сию машину именовать) очень прост в синтаксисе. Что придает ему особую уникальность — одна из его главных selling points — код и данные представляются единообразно и зачастую друг от друга неотличимы. Это позволяет, например, написать программу, оптимизирующую саму себя.

Какая же базовая структура данных (и кода) в лиспе? Это т. н. cons: кортеж из двух элементов, первый из которых называется car/кар, а второй cdr/кедер (записывается как car . cdr). Над такой структурой определены одноименные операции: car[x . xs] = x; cdr[x . xs] = xs.

Через эту структуру можно легко определить список — это конс, кедер которого — список или символ. В лиспе списки представляются при помощи s-expressions; так, список, записанный в виде консов как a . [b . [c . d]] в лиспе выглядит как (a b c d). В приведенном выше случае car вернет a, cdr — (b c d).

Очевидно, консом можно сделать и кар. Конс, и кар и кедер которого — консы или символы — это, по сути, несортированное 1-2-B+ дерево. Дерево, записанное консами как [a . b] . [c . d] выглядит в лиспе как ((a b) c d). Понятно, что car возвращает левую ветвь дерева, а cdr — правую.

Дерево, вообще говоря, довольно универсальная структура. Данные неплохо представляются деревом, например, XML-документ — вполне себе дерево. Код, надо сказать, им тоже представляется — если вы имели дело с компиляторами, то понятие AST вам должно быть знакомо. Но и в том и в том случае речь не идет о двоичных, тем более B+ деревьях — нужна более общая структура, позволяющая иметь произвольное количество листьев на каждой ветви.

На самом деле, такие структуры эквивалентны лисповым деревьям. Наверное, интересующиеся отыщут в теории графов соответствующую теорему; я же просто выношу каждый узел, у которого есть листья, на уровень ниже. Дерево, тем не менее, от этого не становится двоичным — тут на помощь придет currying — будем считать, что самый левый элемент конкретного уровня дерева (car, ага) — лямбда-форма, а все остальные элементы этого же уровня — ее аргументы. Из лямбда-исчисления известно, что лямбда-форма нескольких аргументов представима в виде суперпозиции нескольких функций одного аргумента. Хлоп — и в руках 1-2-B+ дерево. Несортированное, да — но нам этого и не нужно.

Догадываетесь, почему лисп так явно выделяет car в записи s-expressions? CAR расшифровывается как contents of address register, а CDR — contents of data register  (на самом деле чуть сложнее [1]), и поведение лиспа по умолчанию при встрече s-expressionа — отыскать функцию, указанную каром и передать ей в качестве аргументов кедер. Построение AST из исходного кода — проще некуда.

Вложенные списки, таким образом, становятся композицией соответствующих функций. Ну, для примера, (* 1 2 3 (+ 4 5)). Не зря я упомянул currying — каноническим приемом при написании функции от n аргументов в лиспе считается рекурсия: первый аргумент выносится за скобку, а функция вызывается уже на кедере (конечно, данный способ подходит только для правоассоциативных функций).

Интересный случай — когда кар сам представлен в виде списка. Как лисп обрабатывает такие конструкции? No big deal — лисп предполагает, что результат выполнения функции сам представляет из себя функцию (т. н. high-order functions). Например, (в теории) можно написать high-order функцию, вычисляющую производную от переданной в нее функции.

Вообще говоря, здесь лисп и кончается. Макросы, квотинг, псевдоквотинг — лишь указания лисп-машине о том, как воспринимать тот или иной конс.

Надеюсь, я хоть кого-то заинтересовал этой тягомотиной =)

О записи

Вы читаете “On LISP,” в блоге Полоса отчуждения

Опубликовано:
02.08.07 / 11пп
Рубрика:
архитектура, lisp