A critique of Abelson and Sussman or Why calculation is better than scheming

статья Филиппа Вадлера, перевод
Абельсон и Сассман написали прекрасную книгу, которая, может быть, положит начало революции в обучении программированию. Вместо акцентирования на некотором языке программирования, они делают упор на применение стандартных инженерных методов. Но, все же, их книга тесно связана с языком Scheme - диалектом Lisp'a. Я думаю, тот же подход, примененный на примере таких языков, как KRC или Miranda, может быть более удачным введением в программирование как инженерной дисциплины. Мое убеждение основано на опыте обучения Scheme и после знакомства с KRC оно только усиливается.

В этой статье, частично пользуясь текстом Абельсона и Сасмана, выявляются различия в обучении на примере Scheme и на примере KRC и Miranda. Scheme - это диалект Lisp'a с лексической областью видимости, языки похожего стиля - это T и Common Lisp. KRC - это функциональный язык в алгебраическом стиле, Miranda - его преемник. SASL и Orwell - языки, подобные KRC. (Только те читатели, которые знают, что KRC расшифровывается как "Kent Recursive Calculator" смогут оценить заголовок этой статьи).

Есть четыре языковых свойства, отсутствующих в Scheme и существующих в KRC/Miranda:


1. Сопоставление с образцом
2. Синтаксис, близкий к традиционной математической нотации
3. Статическая типизация и пользовательские типы
4. Ленивые вычисления



KRC и SASL не имеют статической типизации, так что пункт 3 относится только к Miranda, LML, и Orwell.

Эта статья - прежде всего рассуждения об относительной важности этих языковых свойств, а не просто сравнение достоинств двух типов языков. Но для удобства в этой статье "Lisp" и "Miranda" будут использоваться для различения двух семейств. (В ранних версиях этой статьи термин "функциональный" использовался для характеристики языков семейства Miranda, но только пункт 4 отражает тот факт, что эти языки функциональные).

Это статья по большей части основана на моем более чем двухлетнем опыте знакомства с двумя различными курсами: курсом для первокурсников, основанном на книге Абельсона и Сассмана и преподаваемом Joe Stoy, использующего Scheme (хотя на самом деле, использовался язык T, модифицированный так, чтобы выглядеть как Scheme); и курсе функционального программирования для магистров, преподаваемом Ричардом Бердом, использующего KRC.

Статья организована следующим образом. В первом разделе обсуждаются типы данных. В разделе 2 рассматриваются противорения между программами и данными. В разделе 3 обсуждаются программы, которые манипулируют программами. В разделе 4 - ленивые вычисления. И в разделе 5 подводится заключение.

1. Типы данных

1.1 Списки

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

СПИСОК это
или пусто(nil)
или ячейка(cons), которая содержит
голову, обозначаемую A
и хвост, который есть СПИСОК


Из описания типа, мы ясно видим структуру программы, которая оперирует такими списками. Например, вот программа на Miranda, подсчитывающая сумму списка из чисел:

sum [] = 0
sum (x:xs) = x + sum xs


Это определение состоит из двух высказываний, по одному на каждый пункт (nil и cons) в определении СПИСКА (В Miranda nil записывается как [], а cons с головой x и хвостом xs как x:xs.)

Вот подобная функция, записанная на Lisp:

(define (sum xs)
(if (null? xs)
0
(+ (car xs) (sum (cdr xs)))))


Такое определение более сложно для чтения, даже хотя оно имеет ту же структуру, что и предыдущее. Основная проблема - отсутствие сопоставления с образцом. Это определение также сложнее читать из-за синтаксиса (вернее, из-за отстутствия синтаксиса) Лиспа.

Более того, Lisp программа скрывает симметрию между двумя случаями. Вариант с nil проверяется явно, тогда как вариант с cons подразумевается в обратном случае. Симметрия может быть возвращена, таким вот описанием:

(define (sum xs)
(cond ((null? xs) 0)
((pair? xs) (+ (car xs) (sum (cdr xs))))))


Эта программа, возможно, еще более непонятна, чем предшествующая. Она также слегка неэффективна, так как производит два сравнения вместо одного.

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

В Miranda строгая типизация контролирует, что функция sum может быть применена только к списку чисел.

Т.к. Miranda использует вывод типов, программист может указать тип функции явно или оставить его для вывода компилятору. Другими словами, вывод типов означает, что типизация(typing of data) не приводит к дополнительным нажатиям пальцев (typing with fingers).

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

Во-вторых, компилятор (language system) гарантирует, что определенные типы ошибок не возникнут во время работы программы.

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

1.2 Доказательсто свойств программ

Допустим что мы хотим доказать что функция append - ассоциативна. Вот описание append (обозначенное ++) в стиле Miranda:


[] ++ ys = ys (1)
(x:xs) ++ ys = x:(xs ++ ys) (2)


Мы хотим доказать, что для всех списков xs, ys, и zs:

(xs ++ ys) ++ zs = xs ++ (ys ++ zs)


Доказательство проведем по индукции по xs

Базовый случай: Заменим xs на []

([] ++ ys) ++ zs
= ys ++ zs - раскрываем, пользуясь (1)
= [] ++ (ys ++ zs) - обратная операция (1)


Индукция: Заменяем xs на x:xs

((x:xs) ++ ys) ++ zs
= (x:(xs ++ ys)) ++ zs - раскрываем, пользуясь (2)
= x:((xs ++ ys) ++ zs) - раскрываем, пользуясь (2)
= x:(xs ++ (ys ++ zs)) - предположение индукции
= (x:xs) ++ (ys ++ zs) - обратная операция (2)


Доказательство завершено.

Теперь рассмотрим определение append на Lisp:

(define (append xs ys)
(if (null? xs)
ys
(cons (car xs) (append (cdr xs) ys))))


Выражение, которое должно быть доказано:

(append (append xs ys) zs) = (append xs (append ys zs))


Читателю предлагается описать доказательство в терминах Lisp'а. Обратите внимание на две определенные сложности.

Во-первых, в Miranda доказательство, прямые и обратные шаги могут быть объяснены как простые замены равного на равное. Аналогичное раскрытие в Lisp требует подстановки определения, а затем упрощения. Например, первый шаг базового случая, отвечающий раскрытию, использующему (1), запишется так:

(append nil (append ys zs))
= (if (null? nil)
(append ys zs)
(cons (car nil)
(append (cdr nil) (append ys zs))))
= (append ys zs)


Обратная операция еще более проблематична.

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

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

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

Некоторые люди могут возразить, что многие проблемы, описанные в этой статье, это "просто синтаксис".

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

1.3 Мобили

Вот часть упражнения 2-27 из Абелсона и Сассмана:

Бинарный мобиль состоит из двух ветвей, левой и правой. Каждая ветвь представляет
собой стержень о пределенной длины, с которого свисает либо гирька, либо еще один
бинарный мобиль. Мы можем представить бинарный мобиль в виде составных данных,
соединив две ветви (например, с помощью list):

(define (make-mobile left right)
(list left right))

Ветвь состоит из длины length (которая должна быть числом) и стуктуры structure,
которая может быть либо числом (представляющим простую гирьку), либо еще одним
мобилем:

(define (make-branch length structure)
(list length structure))

a. Напишите соответствующие селекторы left-branch и right-branch,
которые возвращают ветви мобиля, и branch-length и
branch-structure, которые возвращают компоненты ветви.

b. Используюя эти селекторы, определите процедуру total-weight,
которая возвращает общий вес мобиля.



Опытному программисту не составит труда найти ответ:


(define (left-branch struct) (car struct))
(define (right-branch struct) (cadr struct))
(define (branch-length branch) (car branch))
(define (branch-structure branch) (cadr branch))

(define (total-weight struct)
(if (atom? struct)
struct
(+ (total-weight-branch (left-branch struct))
(total-weight-branch (right-branch struct)))))

(define (total-weight-branch branch)
(total-weight (branch-structure branch)))


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

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

stucture ::= Weight num | Mobile branch branch
branch ::= Branch num structure


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

totalWeight (Weight w) = w
totalWeight (Mobile l r)
= totalWeightBranch l + totalWeightBranch r

totalWeightBranch (Branch d s) = totalWeight s


Программа на Miranda отражает структуру типов более прямолинейно, чем программа на Lisp, эта программа также проще для чтения. Более того, селектирующие функции вообще не используются.

1.4 Представление данных и абстрактные типы данных

Задача о мобилях продолжается следующим образом:

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

(define (make-mobile left right)
(cons left right))

(define (make-branch length structure)
(cons length structure))

Как много Вам нужно изменить в программах, чтобы перейти на новое
представление?


В Lisp мы должны перейти в селекторах right-branch и branch-structure на использование cdr вместо cadr. Для Miranda подобный вопрос не имеет значения, потому что здесь нет селекторов. Это указывает на некоторые преимущества, но также и на недостатки использования Miranda для обучения представлению данных.

Первое преимущество состоит в том, что для некоторых типов данных, называемых свободными типами данных, Miranda позволяет писать программы на более высоком уровне абстракции, где выбор представления не важен. Тип данных называется свободным, если два объекта этого типа эквивалентны тогда и только тогда, когда они сконструированы одинаковым способом. И списки, и мобили - свободные типы данных. Например, списки свободны, т.к. x:xs = y:ys тогда и только тогда, когда x = y и xs = ys. Пример несвободного типа данных - множество, потому что {x} U xs = {y} U {ys} не подразумевает что x=y и xs = ys.

В Lisp, по существу, один свободный тип данных - S-выражения. Если пользователь нуждается в другом свободном типе данных, например, списке или мобиле, тогда он или она должны выбрать представление этого типа в терминах S-выражений. Как мы видели на примере мобилей, существует более чем один вариант выбора. В Miranda пользователь может объявлять новые свободые типы данных явно. Здесь нет необходимости выбирать некоторое произвольное представление. Поэтому, для задачи о мобилях вопрос о смене представления неуместен, потому что мы решили задачу на более высоком уровне абстракции.

Второе преимущество заключается в том, что там, где выбор представления важен, Miranda предоставляет языковую особенность - абстрактные типы данных - для разделения использования типов от выбора из представления. Например, Абельсон и Суссман обсуждают несколько различных путей представления множеств. В разработке программ, классической способ для абстрагирования от произвольного выбора представления - это абстрактные типы данных. Хотя Абельсон и Суссман детально обсуждают абстракцию данных, они не говорят об абстрактных типах данных явно, потому что Lisp не содержит подходящих механизмов для скрытия. Такие языки как Miranda и LML поддерживают классический механизм абстрактных типов данных и поэтому, возможно, лучше подходят для обучения этой теме.

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

1.5 Послесловие об упражнении с мобилями

Напоследок хочу обратить внимание на один момент. Упражнение с мобилями, на самом деле, не очень хорошая модель для рассказа студентам о смене представления. Проблема в том, что хотя представления мобилей и ветвей скрыто за селекторами, представления обычной гирьки нет. Это не проблема в Lisp, т.к. в нем легко добавить необходимые конструкторы и селекторы:

(define (make-weight weight) weight)
(define (weight? struct) (atom? struct))
(define (weight struct) (struct))


Тогда исправленное определение total-weight выглядит так:

(define (total-weight struct)
(if (weight? struct)
(weight struct)
(+ (total-weight-branch (left-branch struct))
(total-weight-branch (right-branch struct)))))


2. Неразбериха между программой и данными

Важнейшее свойство Lisp, то что программа и данные имеют одно и тоже представление, называемое S-выражениями, и специальная форма "quote" служит для превращения программы в данные. Это приводит к удобному стилю для написания программ, которые манипулируют программами, такие как интерпретаторы. Это также делает Lisp языком, простым для расширения.

C другой стороны, новички путаются в отношениях между программами и данными.

В этом разделе описываются подобные случаи, которые я наблюдал у многих студентов на протяжении обучения. Более того, когда дело доходит до написания программ, которые манипулируют программами. Хотя Lisp отлично для этого подходит, Miranda нисколько не хуже.

2.1 Lisp списки не самоцитируемы (self-quoting)

В Lisp числа как данные самоцитируются, тогда как списки нет. Например, для включения числа 3 как данных в программу, мы просто пишем 3, тогда как для списка (1 2 3) как данных, мы пишем (quote (1 2 3)) (что часто сокращается до '(1 2 3))

Различие между (1 2 3) и (quote (1 2 3)) едва заметно, и неизбежно путает студентов. В частности, оно приводит к хаосу при рассмотрении подстановочной модели вычислений. Например, можно использовать подстановочную модель для объяснения вычисления (* (+ 3 4) 6) таким образом:

(* (+ 3 4) 6) ---> (* 7 6) ---> 42


Все три шага преобразования ((* (+ 3 6)), (* 7 6), 42) сами по себе - корректные Lisp выражения.

Теперь попробуем использовать подстановочную модель для объяснения вычисления выражения (list (list 1 2) nil):

(list (list 1 2) nil)
---> (list (1 2) nil)
---> (list (1 2) ())
---> ((1 2) ())


Промежуточные шаги - больше не корректные Lisp выражения. Мы должны помнить, какие части выражения уже были вычислены, а какие еще нет. Можно было бы избежать этого, написав:

(list (list 1 2) nil)
---> (list '(1 2) nil)
---> (list '(1 2) '())
---> '((1 2) ())


Но я считаю, что это слишком сложно объяснить.

С другой стороны, в Miranda мы просто пишем [[1,2], []]. Здесь просто нет никаких вычислений для объяснения.

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

[7*6, 5*9] ---> [42, 5*9] ---> [42, 54]


Каждый шаг преобразования является правильным Miranda выражением.

Речь здесь не о том, что вычисление (list (list 1 2) nil) нельзя объяснить. Конечно, можно. Но это займет больше времени, чемобъяснение Miranda выражения [[1,2], []]. Возможно, в этом случае можно позволить себе дополнительные усилия. Но проблема серьезно усугубляется, когда необходимо объяснить это в середине какого-нибудь другого вывода. Я сталкивался с подобным множество раз.

2.2 Еще больше путаницы с цитированием

Вот упражнение 2-30 из книги Абельсона и Суссмана:

Ева Лу Атор вводит при работе с интерпретатором выражение

(car ''abracadabra)

К ее удивлению, интерпретатор печатает quote. Объясните, что будет
напечатано в ответ на

(cdddr '(this list contains '(a quote)))


Ответ на первый вопрос: (car ''abracadabra) эквивалентно (car
(quote (quote abracadabra))). Поэтому при вычислении мы получаем:

(car (quote (quote abracadabra)))
---> (car (quote abracadabra))
---> quote


В этом случае отслеживания тех частей, которые еще не были вычислены, не
избежать.

Ответом на второй вопрос является то, что Lisp трансформирует при вводе данное выражение в:

(cddr (quote (this list contains (quote (a quote)))))


и результатом вычисления будет ((quote (a quote))).

Все это выглядит довольно мрачно.

В книге Абельсона и Сассмана, эквивалентность 'a и (quote a) объясняется только в сноске. Но для того, чтобы полностью понимать Lisp, вы должны понимать вещи такого рода. В языке без цитирования(quote), такого типа проблемы просто не возникают.

2.3 Вычисляя слишком мало, или слишком много

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

Какое значение у этого выражения?

(car (quote (a b)))


Правильный ответ, конечно, a. Однако, я встречал студентов, которые давали ответ quote, что является результатом слишком малого вычисления. Такая ошибка случается практически постоянно, после того, как они завершат вышеописанное упражнение с abracadabra.

Я также встречал студентов, дававших ответ -"значение переменной a", что является результатом слишком многих вычислений. Это потому, что студенты вначале вычисляют достаточно, чтобы получить правильный ответ "a", а затем вычисляют еще один шаг.

Студенты совершают эту ошибку даже если никакой переменной с именем a не упоминалось в связи с этой проблемой.

И опять, подобного типа проблемы не возникают в языках без цитирования(quote)

2.4. Путаница со списками

Есть еще пара сложных моментов, встречавшихся мне во время обучения студентов типу данных - СПИСОК. Эти сложности проистекают от самих списков и проявляются при обучении как на примере Lisp, так и на примере Miranda, потому что студенты уже страдают от путаницы между данными и программой.

Первая проблема в том, что студенты неизбежно путают список, содержащий один элемент x, с самим элементом x. Проблема тесно связана с Lisp, потому что в нем список из одного элемента записывается как (list x) или (x), в зависимости от того, было ли значение вычислено или нет. В Miranda всегда пишется [x]. Особенности синтаксиса Miranda также слегка помогают: студенты склонны отбрасывать круглые скобки, так что (x) превращается в x. В строготипизированном языках как Miranda, маловероятно что они будут превращать [x] в x, т.к. если x имеет тип t, тогда [x] имеет тип список с элементами типа t; и ошибка будет обнаружена средой при проверке типов.

Вторая проблема в том, что студенты путаются между cons и list. Опять же, эта проблема проявляется сильнее в Lisp, потому что (cons x y) и (list x y) выглядят так похоже, тогда как x:y и [x,y] выглядят достаточно различно. И, опять же, проблему проще объяснить и найти в строготипизированном языке.

2.5. Синтаксис

Наконец, сложно не упомянуть о знаменитом синтаксисе S-выражений в Lisp. У синтаксиса есть серьезные преимущества. Его просто изучить, и он дает студентам хорошее понимание нижележащей абстрактной структуры.

С другой стороны, как показано выше, Lisp программы более массивны, чем аналогичные программы на Miranda. Также, как замечено выше, S-нотация мешает рассуждениям об алгебраических свойствах, таких, как ассоциативность. Возможно, наиболее важно то, что непривычность Lisp синтаксиса может быть реальным препятствием на пути начинающих студентов.

Я помню случай, когда, рассказывыя небольшой группе студентов, пытался убедить их в великой силе и легкости использования Lisp. Объяснив, что 3 + 4 записывается как (+ 3 4), я стал писать несколько больших выражений. Одно из них было ((+ 3 4) = (+ 5 2)), которое заставило интерпретатор сообщить об ошибке. Я быстро исправил код, но я потерял почву под ногами в попытке объяснить студентам насколько "натурален" синтаксис S-выражений. Если даже я, опытный Lisp программист, совершаю такие ошибки, то хотел бы я знать, сколько неприятностей причиняет он студентам?

3. Программы которые манипулируют программами

Lisp известен легкостью, с которой на нем можно создавать программы, которые манипулируют программами, такие как интерпретаторы, компиляторы, и системы преобразования программ. Однако Miranda также имеет ряд преимуществ в дополнение к тем, что есть в Lisp, для создания подобных программ. В этом разделе сравниваются стили Lisp и Miranda для написания таких программ.

3.1. Простой интерпретатор на Miranda и Lisp

В качестве простого примера интерпретатора, возьмем вычислитель выражения лямбда исчисления. Существует три типа выражений: переменные(variables), лямбда абстракции и аппликации. Также еще один тип выражения - замыкание(closure), которое будет использоваться внутри интерпретатора.

Интерпретатор состоит из двух взаимно рекурсивных функций. Вызов (eval e t) вычисляет свободное выражение t в окружении e. Вызов (apply t0 t1) вычисляет аппликацию выражения t0 (которое должно быть замыканием) к терму t1. Miranda и Lisp версии интерпретатора показаны в листингах 1 и 2. Типы данных, использующиеся в этих программах, детально разбираются ниже.

3.2. Свободные типы данных для представления программ

В Miranda типы данных для выражений лямбда исчисления запишутся следующим образом:

term := Var var
| Lambda var term
| Apply term term
| Closure env var term

env == [(var, term)]
var == [char]


Выражение Closure e v t представляет собой замыкание в окружении e лямбда терма со связанной переменной v и телом t. Две последние строчки декларируют, что окружение представляется списоком пар переменная-выражение, и что имена переменных представляются списком символов.

В таком представлении, выражение:

(λx. (x x)) (λx. (x x))


записывается как:

(Apply (Lambda "x" (Apply (Var "x") (Var "x")))
(Lambda "x" (Apply (Var "x") (Var "x"))))


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

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

Часто можно сократить проблемы, введя немного дополнительных определений, делающие данные проше к введению. Например, мы можем определить:

lambda (var v) t = Lambda v t
app t0 t1 = Apply t0 t1
x = Var "x"


а затем записать:

app (lambda x (app x x)) (lambda x (app x x))


запись вполне приемлема, если даже не элегантна.

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

Естественно, это требует больше работы, но это также приносит больше выгоды. Парсеры сами по себе интересная задача, и важны для практических систем, работающих с программами как данными. Один из интересных подходов к созданию парсеров на функциональных языках описывается в [Wadler 1985c].

3.3 Представление программ с помощью почти абстрактного синтаксиса

В Lisp есть несколько способов представления лямбда-термов. Один из наиболее распространенных вариантов:

v - переменная
(lambda (v) t) - лямбда абстракция
(t0 t1) - аппликация
(closure e v t) - замыкание


В таком представлении исходное выражение запишется:

'((lambda (x) (x x)) (lambda (x) (x x)))


что менее громоздко, чем подобное Miranda выражение.

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

(var v) - переменная
(lambda v t) - лямбда абстракция
(apply t0 t1) - аппликация
(closure e v t) - замыкание


И теперь выражение запишется как:

'(apply (lambda x (apply (apply (var x) (var x))))
(lambda x (apply (apply (var x) (var x)))))


что также громоздко, как и в Miranda.

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

Манипулирование программами как данными выглядит проще в Miranda, но ввод данных проще в Lisp. В значительной степени это обусловлено принципом "почти абстрактного синтаксиса", нежели тем, что программы и данные представлены одинаково в Lisp.

Может ли подобный принцип быть каким-то образом добавлен в Miranda-подобный язык, например, добавив специальную нотацию для некоторых элементов данных?

Листинг 1: Вычислитель лямбда выражения на Miranda

|| data types

term ::= Var var
| Lambda var term
| Apply term term
| Closure env var term

env == [(var, term)]
var == [char]

|| evaluate and apply

eval e (var v) = lookup e v
eval e (Lambda v t) = Closure e v t
eval e (Apply t0 t1) = apply (eval e t0) (eval e t1)

apply (Closure e v t0) t1 = eval (extend e v t1) t0

|| environment manipulation

lookup ((v0,t):e v1 = t, if (v0 = v1)
= lookup e, v1, otherwise

extend e v t = (v,t):e
empty = []

Листинг 2: Вычислитель лямбда выражения на Lisp

;; evaluate term t in environment e

(define (eval e t)
(cond ((variable? t)
(lookup e (variable-name t)))
((lambda? t)
(make-closure e (lambda-var t) (lambda-body t)))
((apply? t)
(apply (eval e (apply-operator t))
(eval e (apply-operand t))))))


;; apply term t0 to term t1
(define (apply t0 t1)
(cond ((closure? t0)
(eval (extend (closure-env t0) (closure-var t0) t1)
(closure-body t0))))

;; environment manipulation

(define (lookup v e)
(cond ((pair? e)
(if (eq? v (caar e)) (cadr e) (lookup v (cdr e))))))

(define (extend e v t) (cons (cons v t) e))
(define empty nil)

;; crate and access terms

(define (make-var v) v)
(define (variable? t) (atom? t))
(define (variable-name t) t)

(define (make-lambda v t) (list 'lambda (list v) t))
(define (lambda? t) (and (not (atom? t)) (eq? (car t) 'lambda)))
(define (lambda-var t) (caadr t))
(define (lambda-body t) (caddr t)

(define (make-apply t0 t1) (list t0 t1))
(define (apply? t)
(and (not (atom? t)) (not eq? (car t) 'lambda)))
(define (apply-operator t) (car t))
(define (apply-operand t) (cadr t))

(define (make-closure e v t) (list 'closure e v t))
(define (closure? c) (and (not (atom? c)) (eq? (car c) 'closure)))
(define (closure-env c) (cadr c))
(define (closure-var (caddr c)))
(define (closure-body c) (cadddr c))



4. Ленивые вычисления

Мощь Miranda заключается в использовании ленивых вычислений. Некоторые аргументы в пользу ленивых вычислений содержатся в [Turner 82, Hughes 85, Wadler 85c].

Абельсон и Сассман признают важность ленивых вычислений и включили в книгу ограниченную версию ленивых вычислений, назвав ее потоками (streams). В разделе "Потоки" обсуждаются важные методы программирования с ленивыми вычислениями. Однако, как обычно, Lisp более громоздок, чем Miranda. Например, для нахождения суммы квадратов нечетных чисел от 1 до 100 мы пишем:


sum [i*i | i <- [1..100]; odd i]


в Miranda, а в Lisp


(sum-stream
(collect (* i i)
((i (enumerate-interval 1 100)))
(odd i)))


Несколько раздражает, что с двумя очень похожим типами - списками и потоками - приходится обращаться по-разному. Так, нам нужна sum для нахождения суммы списка чисел, и sum-stream для нахождения суммы числового потока.

Более коварная, и поэтому более серьезная проблема возникает при взаимодействии потоков и аппликативного порядка вычислений, используемого в Lisp. Например, достаточно полезная теорема

map f (xs ++ ys) = map f xs ++ map f ys
(функция map f xs применяет f к каждому элементу списка xs,
а xs ++ ys соединяет списки xs и ys)


к сожалению, не выполняется в Lisp! Например, вычисление

(head
(map sqrt
(append-stream (enumerate-interval 7 42)
(enumerate-interval -42 -7))))


возвращает квадратный корень из 7, тогда как вычисление

(head
(append-stream
(map sqrt (enumerate-interval 7 42))
(map sqrt (enumerate-interval -42 -7))))


сообщает об ошибке времени выполнения при попытке найти квадратный корень из -42. Проблема в том, что append-stream, как и все функции в Lisp, должен вычислить все свои аргументы.

(Конкретно этой проблемы можно избежать, если изменить потоки таким образом, чтобы заморозить вычисление головы потока так же, как заморожено вычисление хвоста. Однако, теорема все равно не будет выполняться, как вы можете увидеть, заменив (enumerate-interval -42 -7) на (bottom), где вычисление (bottom) приводит к бесконечному циклу.

Очевидно, проблемы, подобные этой, наносят ущерб представлению программирования как применения математического подхода.

Они также могут приводить к ошибкам в программе (например см упражнение 3-54 и его обсуждение в книге Абельсона и Сассмана).

Абельсон и Сассман обнаружили эти проблемы, и их обсуждение потоков включает объяснение, почему потоки наиболее хорошо подходят для языков с нормальным(ленивым) порядком вычислений. Они объясняют свой отказ от выбора нормального порядка вычислений тем, что это сделало бы присваивания сложными в использовании. Их выбор позволяет показать студентам два важных подхода к построению программ: присваивания и потоки; но в результате потоки не могут быть показаны во всей красе.

Я настаиваю на том, что преимущества ленивых вычислений перевешивают преимущества возможности обучения присваиваниям на первом курсе. Я верю, что основное преимущество ленивых вычислений в том, что можно отложить рассказ о присваиваниях до завершения первого курса (Абельсон и Сассман согласны с тем, что присваивания не должны преподаватся слишком рано, они отложили это вплоть до середины своей книги).

4.2. С ленивыми вычислениями специальные формы не нужны.

Вот упражнение 1-4 из Абельсона и Сассмана:

Алиса П. Хакер не понимает, почему if должно быть реализовано как
специальная форма: "Почему мы не можем определить if как обычную
процедуру с помощью cond?" Лизина подруга Ева Лу Атор утверждает, что,
разумеется, можно, и определяет новую версию if:

(define (new-if predocate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))

Обрадованная Лиза переписывает через new-if программу вычисления
квадратного корня:

(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))

Что получится, когда Лиза попытается использовать эту процедуру для
вычисления квадратных корней? Объясните.


Ответ, конечно, состоит в том, что sqrt-iter войдет в бесконечный цикл, потому что new-if всегда вычисляет все свои аргументы, тогда как специальная форма (if e1 e2 e3) вычисляет e2 только когда e1 есть nil, или e3 в противном случае.

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

В функциональном языке с ленивым порядком вычислений такая проблема просто не возникает. Можно определить функцию newIf:

newIf true x y = x
newIf false x y = y


и newIf будет вычислять только e2 или e3 в зависимости от значения e1. Нет необходимости в специальных формах. Следовательно, подстановочная модель вычисления становится более стройной и проще для объяснения.

5. Заключение

Книга Абельсона и Сассмана является прекрасным введением в программирование как инжененерную дисциплину. Мой опыт подсказывает, что такие языки, как KRC и Miranda значительно лучше подходят для этого, нежели Lisp.

В разделе 1 показано как сопоставление с образцом и определяемые пользователем типы предоставляют лучший подход к типам данных. В разделе 2 показано, что содержание программы и данных в одной форме приводит к неразберихе в Lisp, чего не происходит в KRC и Miranda. Иногда утверждается, что подобная неразбериха необходима длясоздания программ, которые манипулируют программами. В разделе 3 показано, что это не совсем верно, и что подходы как Lisp так и Miranda обладают определенными преимуществами. В разделе 4 показано, что с потоками легче работать в языке с ленивым порядком вычислений, и в них также не возникают некоторые проблемы со специальными формами. Плата за это - отложенное на последующий курс обучение присваиваниям.

Некоторые читатели могут сказать, что языки подобные KRC и Miranda "недостойны" использовться в обучении, т.к. они не используются в реальном мире. Верно, что первый курс, использующий KRC или Miranda, не достаточен для подготовки студентов к реальному миру, и тоже самое верно для первого курса, использующего Lisp. Цель первого курса - обучить основным принципам и развить правильный образ мыслей. В этой статье я объясняю, почему я верю, что такие языки, как KRC и Miranda хорошо подходят для этого. Дальнейшие курсы должны применять эти принципы к императивным языкам, таким как Pascal иди Modula, и, возможно, даже к другим языками для баз данных или распределенных вычислений. Then the student is prepared to program in Fortran or Cobol, if need be, and to agitate for the introduction of Pascal, Lisp, or Miranda where they are appropriate.

После этого студент готов к программированию на Fortran или Cobol, если потребуется, и применять Pascal, Lisp или Miranda в зависимости от задачи.

Я приступал к обучению Lisp, считая, что различия с KRC и Miranda будут вызывать, как максимум, небольшое раздражение. Основные концепции были теми же, и я не считал, что предубеждение перед синтаксисом Lisp'a будет большой преградой. Опыт убедил меня в обратном. Хотя каждая сложность сама по себе минимальна, общий эффект достаточно значителен.


Благодаря Абельсону и Сассману возник новый подход в обучении программированию. Я рассчитываю, что другие учителя последуют по этому пути, и с нетерпением жду нового поколения учебников, написанных с использованием KRC или Miranda.

Благодарности

Хэл Абельсон и Джерри Сассаман сделали множество подробных и тонких комментариев к черновику этой статьи. Комментарии от Ричарда Берда и Джо Стоя также очень помогли в написании этой статьи.