Сейчас за это отвечает довольно сложный фрагмент кода. Но недавно я понял, что задача раскладывается на две части: 1) преобразование в диалект С--, позволяющий делать вызовы процедур, когда внутри одной процедуры можно вызвать другую, и 2) преобразование этого в подъязык без всяких вызовов, кроме хвостовых.
Затем главное понять, что здесь является типом данных. Что у нас в С--? Структура данных, представляющая императивную программу. Второй шаг - пройти по программе, смотря на каждый кусочек в отдельности. Ваше внимание идет по пути управляющей логики программы или, наоборот, откатывается назад через нее. Это удобно представлять через структуру данных под названием Zipper - полезная, чисто функциональная структура данных для того, чтобы окинуть взглядом чисто функциональную структуру данных.
Норман Рэмзи из Гарварда нашел способ использовать ее для перемещения по структурам данных, представляющим императивные управляющие графы. Мы с ним и Джоном Диасом с этой целью перепроектировали выходную часть GHC с применением этой технологии. И теперь мы можем использовать тот же самый бэкенд для других языков.
Многие споры шли на уровне типов. Норман говорил: "Вот API", - показывая сигнатуру типов, а я в ответ: "Зачем так сложно?" Он объяснял зачем, а я говорил: "Может быть, вот так будет проще". Так что мы довольно долго бились над описанием типов.
Но много времени уходило не на собственно программирование, а на определение самой идеи. Что мы хотим сделать с анализом потока данных? Надо было дать четкий ответ: что подразумевает такой-то шаг программы. Так что немало времени мы потратили на уточнение того, что у нас на входе и что на выходе, и какие у них типы данных. И всего лишь определив эти типы данных, мы довольно подробно описали работу программы. Даже удивительно, насколько подробно.
Сейбел: Как размышления над типом данных соотносятся с кодированием? Набросав типы, вы можете приниматься за код? Или, наоборот, написание кода помогает в понимании типов?
Пейтон-Джонс: Скорее последнее. Я сразу начинаю писать сигнатуры типов в файл. Даже скорее я начинаю писать код, работающий со значениями этих типов. Потом возвращаюсь к типам и изменяю их. Этот процесс не делится четко на два этапа, когда определил типы и садишься за код.
Пожалуй, в этом смысле мне не хватает дисциплины, так как я ни разу не работал в большой команде. Работая в одиночку, можно позволить себе делать вещи в расчете на то, что они помещаются в твоей голове, что, возможно, не получится в большой команде.
Сейбел: Вы говорили о том, что при последней перетряске кодов в GHC его компоненты стали намного более универсальными. GHC - большая программа, которая эволюционировала со временем, так что вы смогли воспользоваться универсальностью, но и заплатили за ее избыток. Что вы узнали о том, как балансировать между избытком и недостатком универсальности?
Пейтон-Джонс: Я предпочитаю вообще не писать чего-то очень универсального. Стараюсь сделать свои программы как можно более красивыми, но не обязательно универсальными. Это разные вещи. Я стараюсь, чтобы код выполнял свою задачу максимально ясным и четким способом. И лишь когда обнаруживаю, что уже писал этот код, то спохватываюсь: зачем делать это снова, достаточно сделать это в одном месте, добавив аргументы, чтобы параметризовать несовпадающие участки.
Сейбел: Какие среды и инструменты вы сейчас используете?
Пейтон-Джонс: О, ужасно примитивные. Работаю в Emacs, компилирую при помощи GHC. Вот и все. Есть профилирующие инструменты, поставляемые с нашим компилятором; люди часто пользуются ими, чтобы профилировать программы на Haskell. Мы применяем их для профилирования самого компилятора. GHC производит много промежуточной выходной информации, и мне видно, что там происходит.
Отладка для меня часто связана с тем, что компилятор порождает плохой код, и я изучаю состояние его внутренностей. Или вот: взять небольшую исходную программу, скомпилировать до такого-то места, посмотреть - вот что такое для меня отладка. Я редко прохожу программу пошагово, чаще всего гляжу на значения разных частей скомпилированного кода.
Я даже нечасто пользуюсь всеми хитростями Emacs, хотя некоторые любят этим заниматься. Также масса народу пользуется интегрированными средами разработки - Visual Studio, Eclipse. Мне кажется, неприятие языков функционального программирования отчасти связано с тем, что мы не выпустили свою интегрированную среду разработки. Опять проблема курицы и яйца. Сейчас напирают на курицу - идет всплеск интереса к функциональному программированию. Надеюсь, что и за яйцо тоже возьмутся. Интегрированная среда для Haskell потребует серьезной разработки. Даже при таких оболочках, как Visual Studio или Eclipse, предстоит большая работа над красивым плагином, который бы делал все как надо.
Сейбел: В GHC есть цикл REPL, GHCI. Вы предпочитаете работать с Haskell интерактивно?
Пейтон-Джонс: Ну, сам я сейчас в основном редактирую и компилирую. Но другие просто живут в GHCI.
Сейбел: Когда дело доходит до тестирования, у функциональных языков есть один плюс: если требуется протестировать небольшую функцию, сидящую в глубине программы, надо просто выяснить, что она принимает на входе.
Пейтон-Джонс: Думаю, если входные данные достаточно просты, проблем с моей программой быть не должно. Проблемы возникают, когда GHC пытается скомпилировать какую-нибудь непомерную входную программу и получает неверный ответ.
Тестирование необычайно важно для создания свойств. Очень полезна QuickCheck - библиотека Haskell, генерирующая случайные тесты для функции в зависимости от ее типа. И я старался понять, почему использую QuickCheck - очень приятный инструмент - меньше, чем мог бы. Видимо, потому, что меня беспокоят ситуации, когда трудно сгенерировать тестовые данные. Так или иначе, куча народу создает программы, от которых GHC просто воротит. Для этого у GHC и есть свой багтрекер.
Я обычно начинаю с чего-нибудь, что работает не так. Возможно, компилятор зависнет в каком-то месте, или откажется выполнять программу, которую должен выполнять, или станет генерировать неоптимальный код. Если он просто генерирует плохой код, я гляжу на него на разных стадиях компиляции и соображаю: "Здесь все в порядке, здесь тоже, а здесь нет - в чем дело?"
Сейбел: Как именно вы это делаете?
Пейтон-Джонс: В GHC есть флажки, которые позволяют выводить что-либо на печать.
Сейбел: Встроенные операторы печати для отладки?
Пейтон-Джонс: Да. Плюс к тому структура такая же, как у большинства компиляторов: на верхнем уровне есть конвейерная структура преобразований. Если что-то не так внутри какого-то из шагов, задача усложняется. Но я предпочитаю несложные методы отладки. Покажите мне программу до и после данного шага. Ага, я вижу, в чем ошибка! Если же не вижу, то могу использовать какой-нибудь из небезопасных операторов printf, чтобы понять, что происходит.
Есть разные отладчики для Haskell. Один из них, и просто отличный, написал в этом году студент летней школы, Пепе Иборра: это интерактивный отладчик, который теперь поставляется вместе с GHC. Я, правда, его мало использовал - он появился недавно, и, кроме того, не очень понятно, как пошагово проходить функциональную программу.
Были любопытные исследования насчет отладки функциональных программ. Жаль, что у нас нет простого и очевидного решения, но зато это интересная исследовательская проблема.
Я все это говорю, чтобы показать, что использую крайне примитивные техники отладки, например через небезопасные операторы printf. Тут нечем гордиться. Но долгое время ничего больше не было - по крайней мере, если брать GHC. Я выработал способы, которые делают для меня этот путь самым коротким.
Сейбел: Это как всегда. Зачем создавать новые отладчики, если люди довольствуются операторами печати?
Пейтон-Джонс: Это скорее культурное явление. Если перейти на отладчики платформы .NET, на которые потрачены десятки и сотни тысяч человекочасов, думаю, результат будет качественно иным. Вероятно, для хорошей работы отладчики требуют еще больше циклов разработки. Но зато в итоге получается образцово полезная вещь.
Возможно, вы разговаривали в основном с людьми академического склада и с теми, кто в силу возраста не привык к сложным отладчикам. Я бы не стал делать никаких общих выводов. И, конечно, не хочу принизить значение качественных отладчиков - особенно для сложных систем с множеством программных слоев. GHC очень прост сравнительно со средой .NET, где есть слои DOM и UML, и не знаю, что еще. Теперь вокруг столько примочек, что программная поддержка становится действительно важной.
Сейбел: Еще один способ создавать правильные программы - формальные доказательства. Что вы думаете об их полезности?
Пейтон-Джонс: Представьте, что ваша цель - иметь для всего автоматическую проверку правильности. Что это будет означать? Проверка по сравнению с чем? По сравнению с некоей спецификацией. Что за спецификация? Она должна описывать все, что делает программа, иначе проверка невозможна. Итак, должна быть формальная спецификация для каждого действия программы. Как написать такую спецификацию? Допустим, вы пользуетесь функциональным языком. Тогда, может быть, ваша спецификация - это и есть ваша программа?
Я тут немного хитрю, ведь в спецификации вы можете сказать то, чего не скажете в программе. Например, "результатом функции является такое у, что при возведении в квадрат дает х*. Это хорошая спецификация для функции квадратного уравнения, но ее особенно не выполнишь. Но все равно, думаю, при попытке написать спецификацию на все действия программы она выходит чрезмерно сложной, и вы больше не уверены, что в ней сказаны все нужные вам вещи.
Более продуктивным для практических целей будет описание некоторых свойств, которыми должна обладать программа. К примеру, вы пишете: "Клапан 1 никогда не должен закрываться одновременно с клапаном 2. Это дерево всегда должно быть сбалансировано. Эта функция всегда должна иметь результат больше нуля". Это небольшие частичные спецификации, не полные. Это просто утверждения, в которых вы хотите быть уверены.
Как их написать? Функциональные языки неплохо приспособлены для этого. Именно это и происходит, если писать спецификацию в Quick-Check - свойства получаются функциями языка Haskell. Допустим, мы хотим проверить, что функция reverse является своей противоположностью, тогда мы напишем check reverse с типом список из А -> булевское значение. Итак, checkreverse от xs будет: reverse от reverse xs равно xs. Это функция, которая всегда оказывается верной. Функция-свойство. Но она написана на том же самом языке, и это здорово.
Теперь можно думать о статических проверках этого. Это может быть трудно, а может и легко. Но все равно, если свойство записано по всем правилам, это большое облегчение. Можно проверить его путем генерирования тестовых данных - именно это делает QuickCheck.
По-моему, писать частичные спецификации гораздо плодотворнее, чем одну спецификацию на все, что делает программа. Возможно, их придется писать много и потом подвергать статической либо динамической проверке. Вы не докажете, что ваша программа правильна, но ваша уверенность в этом возрастет. Думаю, только это мы и можем сделать.
Сейбел: Вы определяете много свойств для всех важных, по-вашему, вещей. Потом по возможности проводится статическая либо динамическая проверка. Ведь мы не сможем устроить статическую проверку для них всех?
Пейтон-Джонс: Правильно. Но в функциональном мире у вас больше шансов. Однако мы все равно слишком долго раскачиваемся, чтобы продемонстрировать это. Так или иначе, первое - это записать свойства.
Мне кажется очень важным уйти от этого глобального подхода, "все или ничего", в сторону очень полезного статического и динамического тестирования частичных спецификаций. Это повысит вашу уверенность в правильности программы, а на большее рассчитывать нельзя. Даже так называемые полные спецификации не учитывают вещи вроде того, что программа должна работать за 0,1 с или занимать не более 10 Кбайт памяти. Часто в них ничего не говорится о ресурсах, о времени. Даже если программа формально отвечает спецификации, из-за этих мелочей она может работать не так, как нужно. Думаю, мы обманываем себя, когда говорим, что проверили программу и все в порядке. Лучше честно сказать, что мы повышаем свою уверенность в ней. Тут все может начинаться скромно - вы повышаете уверенность на 75%, прикладывая всего 5% от общего количества усилий. Это хороший показатель.
Сейбел: Поговорим о параллелизме. Гай Стил поручил мне задать вам вопрос о транзакционной памяти - спасет она мир или все же нет?
Пейтон-Джонс: Нет, конечно. Сама по себе - нет. Параллелизм - многоголовый зверь, которого не убьешь одной пулей. Если речь заходит о параллелизме, то я за различные подходы.
Соблазнительно думать, что можно использовать одну программную парадигму для написания параллельных программ и затем реализо-вывать ее. Тогда для всех программ применялась бы одна парадигма. Но я в это не верю. Я считаю, что для одних стилей программирования больше подходит обмен сообщениями, для других - транзакционная память, для третьих - параллелизм данных. Программисту может потребоваться не один подход, а несколько.
Но если вы меня спросите, лучше ли транзакционная память, чем блокировка и переменные условия? Вот это уже сравнение подобного. Мой ответ - да. Мне кажется, транзакционная память заставит забыть и о том, и о другом. Для всяческих счетчиков, многопоточности с разделяемой памятью на многоядерном процессоре - транзакционная память. Но это, разумеется, не единственный способ справляться с параллельными программами.
Сейбел: Я слышал в ее адрес критику такого рода: оптимистический параллелизм не обеспечивает того уровня параллелизма, на который можно рассчитывать. Утверждается, что легко можно оказаться в ситуации, когда выполнение перестает двигаться вперед.
Пейтон-Джонс: Да, нужно заботиться о зависаниях. Вот мой любимый пример: большая транзакция, которая не фиксируется, потому что в этом месте первой совершается другая, маленькая. Аналогией может быть библиотекарь, который наводит порядок в своей библиотеке. Начинается оптимистическая реорганизация. Две трети работы сделано, тут приходит студент и берет книгу. Он успешно фиксирует свою транзакцию, ведь реорганизация библиотеки еще не зафиксирована. Библиотекарь доходит до конца, обнаруживает отсутствие книги: библиотека изменилась за время реорганизации, структура данных неверна, значит, надо начинать все сначала.
Сейбел: Если есть блокировка и переменные условия, все по-другому - библиотекарь запирает библиотеку, и никто не может взять книгу до полной реорганизации. Поглядев на эту схему, вы немедленно сказали бы: "Мы не можем запереть библиотеку, пока не закончим", - запретив выдачу книг, так что пришлось бы изобретать более сложную схему блокировки.
Пейтон-Джонс: Верно. Надо создать маленькую подбиблиотеку или что-нибудь в этом духе, куда поместить самые ходовые книги, чтобы студенты могли брать их во время реорганизации основной библиотеки. Надо подумать о стратегии решения конкретной задачи и о том, в каком виде ее выразить. Проблема одна и та же в обоих случаях: как реорганизовать библиотеку, не прекращая полностью выдачу книг. После трудной части - придумывания того, как это сделать, - вы думаете о том, как это выразить. И здесь транзакционная память - абсолютный чемпион. Она превосходит и блокировку, и переменные условия для выполнения параллельных программ.
Сейбел: А если я не хочу допускать, чтобы кто-то пришел ко мне за двадцать первым экземпляром самой ходовой книги и оказался запертым? В физическом мире можно представить, что если кто-то приходит за книгой, мы заменяем ее некой заглушкой, которую библиотекарь использует в реорганизации, и когда книга приходит назад, мы возвращаем ее на место заглушки. Но если реорганизовывать библиотеку в мире с транзакционной памятью, придется повторять транзакцию.
Пейтон-Джонс: Но кое-что остается неизменным - шифр книги, верно? Есть несколько способов решить задачу. Например, вы можете сказать, что при работе с заглушкой сама библиотека не меняется, меняется только сама книга. Вы не изменяете ее ключевое поле - только значение, где книга в данный момент находится. И теперь каталог может меняться, где бы книга ни была. Это прекрасно и поддается выражению естественным способом.
В случае транзакционной памяти библиотекарь просматривает все места в памяти, которые считывал, и проверяет, содержат ли они те самые значения, что и при последнем заходе. Поэтому посещенные им ячейки памяти должны содержать ключевое поле книги, определяющее, куда ее положили. Но библиотекарь не читает содержание книги. Он всего лишь проверяет, содержит ли ключевое поле, скажем, число 73.
Но не буду преуменьшать проблему зависания - она довольно коварна. Нужны хорошие профилирующие инструменты, которые указывают, что транзакция не фиксируется, поскольку сталкивается с другой транзакцией. Нужно, чтобы программа не просто втихомолку подвиса-ла, - нужна обратная связь с ней. То же верно и для системы блокировки. Ненавижу эти часики на экране.
Сейбел: Мне кажется, что в программах с блокировкой мы научились снимать ее так быстро, как только возможно, чтобы минимизировать потери от простоев.
Пейтон-Джонс: Да. Но программировать в этом случае сложнее - мелкомодульную блокировку сложно настроить. Мне кажется, одно из больших преимуществ транзакционной памяти в том, что она работает с точностью чрезвычайно мелкомодульной блокировки на основе очень простых принципов.
Вот один из них - в системах с блокировкой этого нет. Я определяю высокоуровневые инварианты: у меня несколько банковских счетов, общая сумма денег на них равна N. Деньги перемещаются со счета на счет. Вот мой инвариант. Любая транзакция предполагает этот инвариант в начале и восстанавливает его в конце. Как вы определяете, что она это делает? Мы смотрим на любую транзакцию вида "Возьмите три из этого места и переместите их вон в то". Инвариант сохранен. Каково мое умозаключение в данном случае? Чисто последовательное. Определив высокоуровневые инварианты, я могу делать последовательные умозаключения о каждой транзакции отдельно.
Сейбел: Поскольку транзакции изолированы друг от друга.