Олин Шиверс

T был одной из лучших реализаций языка программирования Lisp и установил стандарт лаконичного дизайна, который был превзойдён лишь немногими более новыми диалектами. В этой статье Олин Шиверс вспоминает историю T.

Примерно в 1981-1982 годах на факультет компьютерных наук Йельского университета, в котором работала сильная группа разработчиков искусственного интеллекта под руководством Роджера Шанка, был нанят студент-бакалавр Джонатан Рис с целью разработки нового диалекта Lisp для программирования их исследований. Я, Джонатан и Дэн Уэлд (ныне профессор в Университете Вашингтона) были тремя людьми в Йеле, открывшими для себя ранние работы Сассмана и Стила о лямбда-исчислении, включая основополагающую магистерскую диссертацию Гая о Rabbit, первом компиляторе Scheme. Дэн был старшекурсником, а мы с Джонатаном были младшекурсниками. Алан Перлис, душа кафедры, только что открыл для себя функциональное программирование и проводил семинар для аспирантов, где рассматривались ранние ФП-языки, такие как Hope, Miranda и Scheme. Мы трое смогли проскользнуть в этот аспирантский класс, где встретили друг друга.

Немного контекста: Common Lisp еще не существовал (инициатива его стандартизации только начиналась). MIT Scheme не существовало. Scheme представлял собой несколько технических отчетов и магистерскую диссертацию. Речь идёт о крошечном зародыше. В сообществе Lisp было накоплено огромное количество опыта в оптимизации компилирующих реализаций языков с динамической областью видимости. Доходило до того, что в то время было широко распространено мнение, что "лексическая область видимости интересна теоретически, но неэффективна в реализации; динамическая область видимости — выбор для скорости". Я не шучу. В качестве примера, я слышал это от Ричарда Столлмана (автора и разработчика Emacs Lisp) и Ричарда Фейтмана (профессора в Беркли и главного инициатора Franz Lisp, безусловно, самой важной реализации Lisp, созданной в эру ранних Vax — важной потому, что она была выпущена и работала). Я спросил Ричарда Столлмана, когда он разрабатывал Emacs Lisp, почему он выбрал динамическую область видимости, и его ответ был в точности таким: лексическая область видимости слишком неэффективна. Итак, мой посыл здесь в том, что даже для людей, которые являлись экспертами в области реализации Lisp в 1982 году (и в течение нескольких последующих лет), Scheme был радикальной и непризнанной идеей. А вне сообщества Lisp/AI… ну, языки с сборкой мусора были определенно неприемлемы. (В отличие от эпохи Perl и Java, в которой мы живем. Не преувеличивая, благодаря Perl можно сказать, что в мире развернуто сервисов на миллиарды долларов на основе языков со сборкой мусора.)

Джонатан провел предыдущий год в отпуске от Йельского университета, работая в MIT. Важным событием, имевшим место, было появление 32-битных машин с 32-битными адресными пространствами — большими адресными пространствами. Большая часть существовавших технологий языков программирования в сообществе разработчиков искусственного интеллекта была разработана для PDP-11 (16-битная машина) и, что еще важнее, для рабочих лошадок PDP-10 и -20. Я, кстати, обожал "десятку". Она имела набор инструкций, который помещался на одной странице крупным шрифтом, и была просто крутой. Тот набор инструкций был мечтой хакера; с ним можно было играть во все виды интересных игр. Например, существовал знаменитый хак, который позволял (1) извлечь cons-ячейку из списка свободных ячеек, (2) обновить список свободных ячеек и (3) перейти к сборщику мусора, если список свободных ячеек исчерпан… посредством одной инструкции. PDP-10 была 36-битной машиной с адресным пространством, адресуемым словами длиной 18 бит. Обратите внимание на то, что это означает: cons-ячейка помещалась в одно слово. Многие утверждают, что "десятка" была первой в мире Lisp-машиной. Я согласен с ними.

PDP-10
PDP-10

Для "десятки" существовали две чрезвычайно хороших, зрелых и высокооптимизированных реализации Lisp: одна с "Восточного побережья" (Maclisp из MIT) и одна с "Западного побережья" (Interlisp из Стэнфорда и Xerox PARC). Также на "десятке" можно было программировать на прекрасном языке от CMU, называемом Bliss, примерно на уровне Си. До сих пор вижу Си и вспоминаю Bliss, аж на слёзы пробивает.

Проблемой было ограниченное 18-битное адресное пространство PDP-10. Программисты его переполняли. Когда DEC выпустила Vax и начали появляться рабочие станции Sun и Apollo на базе Motorola 68000, люди осознали, что 32-битное адресное пространство этих архитектур представляет собой скачкообразный сдвиг в технологии, и реализация языков программирования на этих машинах также будет новым скачком. Например, с таким большим адресным пространством сразу хочется существенно изменить технологию сборки мусора и представления данных.

Беркли был крупным игроком, который способствовал внедрению Vax в университетах, получив контракт ARPA на разработку Berkeley Unix для Vax (который затем привел к созданию Sun, благодаря Биллу Джою). В рамках этого проекта был создан Lisp для Vax под руководством Фейтмана — Franz Lisp. Реализация Franz была ближе к Maclisp, чем к Interlisp, настолько, что позволила портировать Macsyma (интересовавшую Фейтмана) на Vax. Franz также несёт на себе следы фундаментального влияния малоизвестного Lisp, созданного в Гарварде.

MIT отреагировал на появление Vax, начав проект NIL. NIL означал "New Implementation of Lisp" (новая реализация Lisp). Джонатан был частью этого проекта во время своего отпуска от Йельского университета. Это был действительно хороший труд, но в конце концов проект был ослаблен преждевременной оптимизацией — он был очень большим, очень агрессивным, очень сложным. Например, они назначали людей для написания тщательно написанного вручную ассемблерного кода для пакета bignum до написания общего компилятора. Проект NIL создавался лучшими специалистами (гм… помню, что Джонл Уайт и Джордж Каррет были ключевыми фигурами). Но его так и не выпустили. Он был завершен годами позже запланированного срока, и к тому времени был по большому счёту неактуален. (Такое случалось со мной. Это горький, горький опыт. В колледже я модно преуменьшал вред преждевременной оптимизации, не совсем понимая его, пока однажды не совершил акт ужасной преждевременной оптимизации, после которого я теперь могу предсказывать дождь по ощущениям в оставшейся рубцовой ткани. Теперь я понимаю вред преждевременной оптимизации.) Зарождение и последующий провал таких проектов всегда ясно видны (задним умом) в типичных фразах ранних обсуждений. Одна из таких ключевых фраз всегда имеет форму "Мы выбросим весь старый хлам, начнем с чистого листа и просто Сделаем Всё Правильно." (К сожалению, это не очень полезное наблюдение, потому что такая стратегия иногда приводит к потрясающим результатам. Она просто очень рискованная).

Джонатан работал над NIL в течение года, затем вернулся в Йель для завершения последнего курса, где его нанял факультет компьютерных наук для реализации нового Lisp. Он принял радикальное решение: создать оптимизирующую систему языка Scheme с нативным кодом. Он решил назвать ее T. Это было отличное имя по нескольким причинам. Конечно, оно было коротким и простым. Оно соответствовало культуре Йельского факультета компьютерных наук, так как там была история программ с однобуквенными именами: e, c, z и u. (Это было семейство локально разработанных продвинутых экранных редакторов, которые примерно соответствовали Emacs, но были совершенно другими.) Наконец, если вы Lisp-хакер, то вы знаете, что NIL — это константа булевской лжи в Lisp… а T — константа истины. Так что "T это не NIL".

Позвольте мне повторить, насколько радикальным было решение построить Scheme. Единственная реализация Scheme, которая когда-либо была создана на тот момент, была исследовательским прототипом, сделанным Стилом для его магистерской диссертации. Все серьезные Lisp'ы, находившиеся в продакшене на тот момент, использовали динамическую область видимости. Никто из людей, не прочитавших внимательным образом диссертацию о Rabbit, не верил, что лексическая область видимости будет работать; даже несколько людей, которые таки прочитали её, делали шаг в неизвестность, когда верили, что это будет работать в серьёзном продакшене — разница между теорией и практикой, гм, больше на практике, чем в теории.

Гай Стил, автор Scheme

(Например, другой большой проект реализации из MIT, Zetalisp для Lisp Machine, сохранял динамическую область видимости, но позволял компилятору в некоторой степени нарушать семантику, а затем, в ответ на Scheme, в него добавили лексические замыкания в качестве довольно неуклюжей особой формы.)

(Европейцы, работающие над ранними системами, такими как ML в Эдинбурге, наверняка находят всю эту американскую путаницу и непонимание дисциплин областей видимости и стратегий реализации довольно бестолковыми. Прошу прощения за это.)

Помимо Роджера Шанка, еще одним человеком, который вложил ресурсы в найм Джонатана для разработки T, был Джон О'Доннелл, который позднее стал ключевым сотрудником Multiflow, компании, коммерциализировавшей технологию VLIW-архитектуры/компилятора, созданную Джошуа Фишером в Йельском университете в 1983 году. Я предполагаю, что Алан Перлис, вероятно, тоже имел свое слово в этом решении, хотя я не уверен. Выделять средства, чтобы позволить Джонатану приступить к (попытке) создания реализации Scheme продакшен-качества было довольно смело, наравне с самим решением Джонатана попробовать это сделать.

Из проекта NIL Джонатан принёс обширный набор действительно отличных технологий реализации — прежде всего фундаментальные представления данных, которые были тщательно отточены для новых поколений архитектур машин с сохранением тегов типов в младших битах данных. Например, если сделать битами тега для fixnum "000", то можно складывать и вычитать fixnum'ы одной инструкцией без накладных расходов на обработку тегов; умножение можно производить с однократным предварительным сдвигом, а деление — с однократным последующим сдвигом. Это было значительным улучшением по сравнению с необходимостью упаковки fixnum'ов в Maclisp и сопутствующими примочками, которые делали всю эту работу (на мой взгляд). Кроме того, поскольку Vax адресуется байтами, вы могли удалить тег типа из данных cons-ячейки, просто изменив постоянное смещение в режиме адресации. Иначе говоря, cons-ячейки представлялись выровненным на два слова адресом блока памяти, где находились поля car и cdr ячейки. Выравнивание памяти на два слова означает, что младшие три бита его адреса всегда равны нулю, то есть не используются. Таким образом, три младших бита адреса использовались для меток типов. Предположим, мы используем "010" (десятичное число 2) для тега типа. Вы могли бы получить cdr пары в регистре r7 с помощью одной инструкции: load r8, r7[4-2], где "4" позволяет получить 1 слово (4 байта) из пары (поле cdr), а "-2" компенсирует метку типа. Таким образом, вы могли бы удалить тег типа без временны́х затрат. Шикарно! Представления для замыканий и стековых фреймов также были весьма изощренными.

Джонатан был разочарован неудачным завершением проекта NIL, поэтому он был очень осторожен c преждевременной оптимизацией. По этой причине он создал быструю и некрасивую прототипную реализацию просто для запуска чего-то. (Кажется, он написал ее на Maclisp, и, как я помню, назвал ее "cheapy"). После этого вся разработка будущих версий осуществлялась на самом T — T2 был реализован с помощью T1.

T2 была первой действительно хорошей реализацией со всеми вышеупомянутыми фишками. Она работала на Vax и 68000, которые тоже только появились. Она была достаточно надежной, чтобы быть серьезной системой, от которой зависели реальные клиенты.

VAX 11/780

Примерно в это же время группа Сассмана начала разработку, которая в конечном итоге привела к MIT Scheme, а также учебный курс, который привел к появлению книги Сассмана и Абельсона Структура и интерпретация компьютерных программ. Усилия, связанные с Lisp Machine, также привели к появлению Symbolics и LMI, что вызвало создание Zetalisp и Flavors на основе Maclisp, что, в свою очередь, оказало значительное влияние на Common Lisp и объектную систему Common Lisp, CLOS. Но я отклоняюсь от темы. Возвращаемся к Йельскому университету.

T также использовала довольно интересную систему сборки мусора. Maclisp на PDP-10 использовала алгоритм mark & sweep (одна из версий этой системы "работала в регистровом наборе", хотя это уже другая история), кодируя информацию о типах с помощью схемы "BIBOP" — все объекты были обёрточными и разделены по своим типам на страницы. Таким образом, старшие биты адреса объекта могли использоваться для индексации по таблице страниц и определения типа объекта, находящегося на этой странице. Это было хорошо настроено для систем с ограниченной памятью, таких как "десятка". Однако при использовании больших адресных пространств вы хотите использовать схему stop & copy, потому что в этом случае вы платите только за копирование активных данных, а не за мусор. Это хорошо подходит для больших куч, которые можно аллоцировать на 32-разрядной машине. Большинство stop & copy сборщиков почти всегда реализуют алгоритм Чейни, который выполняет поиск в ширину в куче. Но поиск в ширину не очень хорош для локальности памяти — он разбрасывает топологически близкие структуры данных по всей куче при копировании. Не очень здорово. T использовала малоизвестный (но довольно простой — описание алгоритма в статье занимает около 2 страниц) алгоритм Кларка, который реализует поиск в глубину. (Точно так же, как алгоритм Чейни умно использует существующие структуры данных в куче для предоставления очереди поиска в обходе в ширину, алгоритм Кларка использует кучу для предоставления стека поиска.) Поиск в глубину означает, что если вы выполняете сборку мусора для связного списка, GC спускается вдоль хребта списка, прежде чем обратить свое внимание на сами элементы списка, поэтому эти "хребтовые" ячейки размещаются последовательно в памяти. Ваш список превращается в вектор! (типа) Это превосходно для локальности памяти. Однако,

T отошла от этого алгоритма в конце 80-х годов в пользу классического алгоритма на основе поиска в ширину. Дэвид Кранц (который вскоре появится в этой истории) рассказал мне, что он сделал этот выбор, потому что фаза копирования BFS-алгоритма имела немного более быстрые константные множители.
Та стандартная религия, описанная выше, о том, что "stop & copy платит только за хорошее, а в mark & sweep вы должны платить также и за мусор", не совсем верна. Мы все верили в это десятилетиями. Но Норман Рэмси в Гарварде умно ́ показал, что вы можете реализовать mark & sweep с точно такими же асимптотическими затратами, как у stop & copy. Это хорошая новость, особенно для систем с ограниченной памятью с гомогенными данными на куче. Наблюдение Нормана действительно очевидно и просто; оно не кажется впечатляющим результатом на первый взгляд. Ну если не учитывать, что оно ускользало от всех в течение десятилетий. И не потому, что людям было все равно; сборка мусора широко исследовалась. В этом есть ценный урок.

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

(Это не так просто, как кажется. Это вам не просто написать код и никогда не вызывать malloc или использовать new. Проблема неразрывно связана с обработкой лямбда-выражений. Хорошие компиляторы Scheme используют различные реализации для лямбд в программе, в зависимости от того, что они могут выяснить о лямбда-выражениях на этапе компиляции — как они используются, куда передаются, отношение между использованием и местом определения и т. д. Некоторые лямбды просто исчезают. Некоторые лямбды превращаются в точки слияния потока управления с соответствующими регистрами/переменными. Некоторые лямбды превращаются в стековые фреймы. Но некоторые лямбды приводят к выделению памяти для создания обычных замыканий. Поэтому необходимо понимать, как компилятор будет обрабатывать каждое лямбда-выражение, которое вы пишете. А фундаментальный каркас программы на Scheme строится из лямбда-выражений.)

Еще одним достижением T было то, что он позволял прерывания между любыми двумя инструкциями пользовательского кода. Это создавало достаточно большую нагрузку на компилятор, настолько большую, что из всех реализаций Scheme, о которых я знаю, T в этом отношении уникален. Чтобы понять, почему это сложно в присутствии сборки мусора, вы можете прочитать мою статью на эту тему, написанную десять лет спустя, "Atomic heap transactions and fine-grain interrupts", которую можно найти по адресу https://www.ccs.neu.edu/home/shivers/papers/heap.pdf (не нужно быть экспертом по лямбда-исчислению, чтобы прочитать эту статью; она написана так, чтобы ее мог понять широкий круг разработчиков.) Кроме того, T позволял писать обработчики прерываний (сигналов Unix) на T, что было довольно удобно.

Помимо технологий реализации, в T также было много красивого языкового дизайна. Джонатан воспользовался возможностью полностью сломать обратную совместимость в отношении библиотеки времени выполнения и даже выбора имен. Где-то во время работы над T2, Кент Питман, еще один эксперт по Lisp, приехал в Йель из MIT. Они с Джонатаном вложили огромное количество усилий в проектирование языка, и результат был просто очень, очень минималистичным. Маленькие (но сложные) вещи: они выбрали стандартный набор лексем и регулярный способ сборки их в имена стандартных процедур, чтобы вам было легко запоминать или реконструировать имена при написании кода. (Я следовал этому примеру при разработке SRFI для сообщества Scheme. Это непростая задача.)

Более крупные и глубокие вещи: они разработали красивую систему объектов, которая была интегрирована в механизм присваивания. Точно так же, как в Common Lisp с помощью SETF вы можете присваивать с использованием аксессоров, например, в Common Lisp (setf (car x) y) эквивалентно (rplaca x y), в T (set! (car x) y) было сокращением для ((setter car) x y). Функции-аксессоры, такие как CAR, обрабатывали "обобщённые функции" или "сообщения" типа SETTER: CAR возвращал процедуру SET-CAR! при отправке сообщения SETTER. Компилятор был способен оптимизировать такой код до единственной инструкции сохранения Vax, реализующей операцию SET-CAR!, но семантический механизм был полностью унифицированным — вы могли определить собственные процедуры-аксессоры, назначить им методы SETTER и затем использовать их в формах SET!.

(Это оказалось очень удобным в фактической реализации компилятора. Абстрактное синтаксическое дерево было деревом объектов, связанных между собой в обоих направлениях: родители знали своих потомков, а у потомков также были ссылки на родителей. Если оптимизатор изменял ветку else у if-узла N на что-то вроде (set! (if-node:else n) new-child), что на самом деле было ((setter if-node:else) n new-child), метод SETTER у if-node:else делал для вас много работы — он отсоединял старого потомка, устанавливал NEW-CHILD в поле else у N и устанавливал родительское поле NEW-CHILD равным N. Таким образом, вы не могли забыть поддерживать все ссылки согласованными; все это обрабатывалось за вас одним-единственным присваиванием SET!.)

Примерно в то время, когда Кент вернулся в MIT, новый аспирант Норман Адамс присоединился к Джонатану. T2 и его компилятор TC были созданы после примерно года тяжелой, целенаправленной работы Джонатана, Кента и Нормана. Я закончил учебу в Йельском университете и отправился в CMU, чтобы стать аспирантом в области искусственного интеллекта. Джонатан начал размышлять о следующем компиляторе.

Во время моего первого года аспирантуры Джонатан познакомился с Форрестом Баскеттом, который был директором одной из ведущих промышленных лабораторий по компьютерным наукам, Западной лаборатории исследований DEC, где проводилась много важной работы по RISC (например, можно утверждать, что работа Дэвида Уолла по межпроцедурному распределению регистров там убила архитектурную особенность перекрывающихся стеков регистровых наборов, разработанную в Беркли и попавшую в SPARC). Форресту понравился Джонатан, и он пригласил его с командой в лабораторию на лето для реализации T на разрабатываемой ими машине (уникальный для того времени RISC под названием Titan). В команду Джонатана входили сам Джонатан, Норман, Джим Филбин, Дэвид Кранц, Ричард Келси, Джон Лампинг и я. Лампинг учился в Стэнфорде, я был в CMU, остальные были аспирантами в Йельском университете (кроме Джонатана, который был сотрудником Йельского университета).

Итак, лето 1984 года. Наша миссия заключалась в создании самого высокооптимизированного компилятора Scheme в мире. Мы хотели конкурировать с C и Fortran. Новая система называлась T3, а компилятор должен был называться Orbit. Мы все прибыли в Западную лабораторию и разделили зоны ответственности за компилятор. Норман должен был заниматься ассемблером. Филбин, насколько я помню, брался за библиотеку времени выполнения. Джонатан был руководителем проекта и, кажется, написал линкер. Кранц должен был заниматься бэкендом, а Келси — фронтендом. Я успешно прошел предыдущий семестр в CMU, став экспертом в области анализа потока данных, теме, в которой я в полной мере нашёл свою волну. Все современные компиляторы используют анализ потока данных. Он необходим для всех действительно крутых оптимизаций, таких как вынос инвариантных циклу операций, глобальное распределение регистров, глобальная устранение общих подвыражений, распространение копий и устранение индуктивных переменных. Я знал, что ни один компилятор Scheme или Lisp никогда не предоставлял эти крутые оптимизации. Мне не терпелось стать первопроходцем. Я писал код трехмерной графики на T и действительно хотел, чтобы мои операции с плавающей запятой с матрицами использовали полный набор оптимизаций анализа потока данных. Создание модуля анализа потока данных для T, без сомнения, отличило бы нас от остальных. Поэтому, когда мы разделили обязанности по компилятору, я сказал всем остальным посторониться и громко заявил, что возьму на себя анализ потока данных. Хорошо, ответили они, ты займешься модулем анализа потока данных. Лампинг присоединился ко мне, чтобы помочь.

Лампинг и я провели остаток лета, встречая неудачи на каждом шагу. Мы совершали поездки в библиотеку Стэнфорда, чтобы искать статьи. Прикидывали варианты на досках. Невидящим взором смотрели перед собой. Писали небольшие фрагменты экспериментального кода. Терпели неудачи. Узнавали, почему никто никогда не реализовывал оптимизации анализа потока данных для Scheme. Вкратце, фундаментальный элемент, необходимый для работы классических алгоритмов анализа потока данных, в программе Scheme недоступен. Это действительно угнетало. Я зарабатывал больше денег, чем когда-либо в своей жизни (600 долларов в неделю). Я работал с отличными ребятами над интересным проектом. Я никогда раньше не был в Калифорнии, поэтому открывал для себя Сан-Франциско, мой любимый город в США и второй любимый город в мире. Силиконовая Долина в 1984 году была красивой, не такой, как сегодня — переполненной торговыми центрами и шоссе. Каждый день, когда я ехал на работу на велосипеде, был идеальным и прекрасным. Я встретился с прекрасной рыжеволосой девушкой. И каждый день я приходил в лабораторию, терпел неудачи в течение 8 часов, а затем уходил домой.

Это лето было неудачным.

В конце лета я вернулся в CMU с понурой физиономией, не внесши ни строчки кода в Orbit.

Однако все остальные выполнили свои задачи. Компилятор не был готов к концу лета, но он был доделан в следующем году в Йельском университете. И это был самый высокооптимизирующий компилятор Scheme в мире (хотя он и не выполнял анализ потока данных), рекорд, который он удерживал в течение долгого времени — возможно, около десяти лет.

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

Дэвид Кранц взял свою работу над бекендом, который представлял собой очень сложный код, выполняющий множество продвинутого анализа представлений данных, выделения регистров и, в частности, работы с лямбда-функциями, и превратил ее в свою кандидатскую диссертацию. Orbit генерировал код, который фактически обходил реализацию на Pascal, используемую компанией Apollo (производителем рабочих станций класса Sun) для реализации операционной системы на этой рабочей станции; это был огромный успех. Затем Дэвид поступил в MIT, где применил свою технологию компиляции в проекте параллельного Lisp под руководством Берта Хэлстеда, прежде чем присоединиться к Стиву Уорду для работы над исследовательским проектом, который превратился в Curl. Когда Уорд основал компанию Curl, Хэлстед и Кранц стали там старшими техническими специалистами.

Apollo dn330

Давайте назовем диссертацию Кранца "PhD #1". Она называлась Оптимизирующий компилятор для Scheme, что я понял как отсылку к классическому компилятору Bliss Уильяма Вулфа, описанному в книге (моя копия подписана), озаглавленной попросту Проектирование оптимизирующего компилятора. Компилятор Bliss Вулфа был образцом, к которому мы все стремились — он некоторое время был "самым высокооптимизирующим компилятором в мире".

(Помните Bliss? Просто для дополнительных отсылок: Вулф покинул CMU примерно в то время и создал компанию Tartan Labs для коммерциализации этой технологии компиляции для языка C. Он взял с собой Гая Стила, который только что завершил работу над определением Common Lisp, будучи преподавателем в CMU. Tartan потерпел неудачу, Вулф перебрался на руководящую должность в Университете Вирджинии и сейчас является влиятельным лицом на национальном уровне в области научно-технической политики, например, возглавляя исследования Национальной Академии по вопросам технологий противодействия терроризму. Стил перешел в Thinking Machines, а затем привнёс свои навыки разработки языков в разработку Java в Sun.)

Диссертация Кранца является техническим отчетом отдела компьютерных наук Йельского университета. Я бы сказал, что это обязательное чтение для всех, кто интересуется серьезной технологией компиляции для функциональных языков программирования. Вы, вероятно, можете заказать или скачать ее с веб-страницы по адресу https://cpsc.yale.edu/sites/default/files/files/tr445.pdf

Ричард Келси взял свой фронтенд, который был очень агрессивным оптимизатором на основе CPS, и расширил его до конца, чтобы создать полноценный второй компилятор, который он назвал "TC" (Transformational Compiler). Его подход заключался попросту в том, чтобы продолжать преобразовывать программу из одного простого лямбда-языка на основе CPS в еще более простой, пока язык не станет настолько простым, что будет иметь всего 16 переменных… от r1 до r15, после чего можно просто удалить лямбды и назвать это ассемблером. Это красивая работа, которую, подобно диссертации Кранца, стоит прочитать всем, кто хочет заниматься компиляторами для функциональных языков программирования. Она оказала большое влияние на Эндрю Аппеля в Принстоне, который впоследствии вместе с группой Дэйва МакКуина из Bell Labs создал компилятор SML/NJ для SML, в котором было использовано много идей из этой работы. Эндрю описывает этот факт в книге, которую он впоследствии написал об этом компиляторе, Компиляция с продолжениями. Однако, в отличие от компилятора SML/NJ, компилятор на основе CPS Келси порождал код, который использовал стек времени выполнения для вызовов процедур. Фактически в своей диссертации он описывает фронтенды для стандартных процедурных "не-лямбда" языков, таких как Basic.

Таким образом, происхождение тезиса о CPS в качестве промежуточного представления компилятора идет от компилятора Rabbit Стила через Orbit в T и далее к SML/NJ. В этот момент Сабри и Феллейзен из Университета Райса опубликовали серию очень серьезных статей, в которых была высказана критика CPS в качестве представления и предложена альтернатива под названием A-Normal Form (ANF). ANF было модным представлением примерно десять лет; CPS вышло из моды. Затем эта тема как бы переходит в сообщество ML в CMU, где она получает важное продолжение, связанное с типизированным промежуточным языком, и направляется в Корнелл и Йель, но я не буду туда вдаваться. Однако, чтобы выразить свою позицию по этому вопросу, скажу, что весь переход от CPS к ANF мне кажется плохой идеей (хотя технические наблюдения и математика Сабри и Феллейзена настолько прочны, насколько можно ожидать от таких высококлассных ученых).

Давайте назовем диссертацию Келси "PhD #2".

После этого Келси некоторое время проработал преподавателем в Северо-Восточном университете, а затем перешел в престижную лабораторию NEC в Принстоне, где работал над распределенной системой Kali. Он также записал на бумаге то, что все люди, занимающиеся CPS, на интуитивном уровне знали: что вся "революция SSA" в классическом сообществе компиляторов по существу является повторным открытием CPS (Хах). NEC в Принстоне собрала впечатляющую коллекцию хакеров Scheme/ML: Стивена Уикса и Эндрю Райта из Райса, Кевина Лэнга (который создал малоизвестный, но очень красивый, изящный, бесплатный и переносимый объектно-ориентированный Scheme под названием Oaklisp), Келси, Джима Филбина, Генри Цетджина и Джеффа Сискинда. Когда NEC в Принстоне превратился в безумное токсичное место, Келси, как и почти все остальные в предыдущем списке, ушел в мир стартапов, где он основал стартап с Рисом и выпускником MIT Патриком Собальварро, который добился некоторой известности благодаря работе над сборщиками мусора. Этот стартап провалился в хаосе пузыря доткомов в прошлом году, и сейчас Келси находится в своем втором стартапе.

Норман Адамс превратил свой ассемблер в магистерскую диссертацию. Это также была крутая программа. Его ассемблер не принимал линейный текстовый поток; компилятор предоставлял ему графовую структуру. Он самостоятельно сериализовывал граф, чтобы минимизировать расстояние прыжков, и имел другие интересные функции (например, на самом деле это был переносимый фреймворк для построения ассемблеров). Затем он взял свою степень магистра и ушел работать в Tektronix, где разработал высокопроизводительную реализацию Scheme для процессора Motorola 88000 под названием "screme", а затем перешел в Xerox PARC, где работал над повсеместными вычислениями и реализацией Scheme под названием SchemeXeroX (игра слов c "Team Xerox") с Павлом Кертисом. Он покинул Xerox в начале бума доткомов и рано вошел в стартап-компанию Ariba, поэтому (1) у крупного продукта Ariba была система конфигурации, основанная на Scheme, встроенной в Java, и (2) он теперь богатый парень.

История Лэмпинга, пожалуй, самая странная. Он вернулся в Стэнфорд и столкнулся с очень эзотерической теоретической проблемой, называемой оптимальной лямбда-редукцией, которую он полностью решил в рамках своей кандидатской диссертации. Это достижение заслуживает особого внимания, потому что узколобые теоретики семантики из Европы боролась с этой проблемой уже очень долгое время. Они боролись настолько упорно, что когда этот хакер из Стэнфорда просто сел и решил проблему, они, похоже, были… раздражены. Джон казался совершенно неспособным решить эту проблему, внеся в нее только свои мозги. Например, была опубликована надменная французская статья, в которой от Лэмпинга как бы отмахивались, называя его "самоучкой", перед тем как продолжить надстройку (будьте внимательны, заслуженное признание Лэмпингу) над его работой. Так что Лэмпингу теперь всегда припоминают этот забавный титул/термин те, кто знает и любит его. Он никогда не сможет от него избавиться. Джон Лэмпинг, самоучка.

Затем Джон перешел в Xerox PARC, где он вместе с Грегором Кичалесом занимался широким спектром интересных проблем в области языков программирования, среди которых наиболее известны "Аспектно-ориентированное программирование". Опять же, история здесь уходит от проекта T, поэтому я не буду её рассказывать. По той же причине мы не будем называть диссертацию Джона "PhD #3" — она не была связана с его работой над проектом T.

Примерно через три года после лета в Западной лаборатории я наконец-то разобрался, как выполнять анализ потока данных для Scheme, что по��ожило конец долгому и довольно неприятному периоду в моей жизни. Я официально переключился с обучения в области искусственного интеллекта на обучение в области языков программирования, привлек Питера Ли в качестве со-руководителя (поскольку мой изначальный научный руководитель, Аллен Ньюэлл, не был специалистом по языкам программирования, хотя, безусловно, был самым великим ученым, которого я когда-либо знал лично), и все это описал в своей диссертации. Давайте назовем ее "PhD #3".

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

Джим Филбин, как и Келси, также пошел в NEC, где он создал операционную систему, приспособленную для функциональных языков программирования, STING (или, возможно, она записывалась как "STNG", но в любом случае произносилась как "sting"). Конечно, он создал ее на основе T, и можно было увидеть, что она имела свои корни в его работе над T3. (В некотором смысле реализация среды выполнения для функционального языка требует создания небольшой виртуальной операционной системы поверх настроящей базовой ОС.) Назовем эту работу PhD #4. После этого Джим покинул Scheme, чтобы заниматься работой с параллельными процессорами и системами вместе с Кай Ли в Принстоне.

Джонатан поступил в MIT в качестве аспиранта, где работал с Герри Сассманом и Дэвидом Гиффордом. После работы над рядом интересных проблем Джонатан также написал свою диссертацию по операционной системе для функциональных языков, где основным механизмом защиты была безопасность языка. Назовем это PhD #5. Затем его заинтересовали жуки (насекомые, я имею в виду — настоящие насекомые, а не компьютерные ошибки), он закончил постдокторантуру в Европе, затем вернулся в США и, можно сказать, перебирался между исследовательскими темами, такими же радикальными и необычными, каким T был в 1982 году, и стартап-компаниями.

(Джонатан также написал свою диссертацию на Scheme и о Scheme. Он создал небольшой текстовый процессор для своей диссертации на Scheme, называемый "markup", который позволял писать стандартный текст, прерывая его командами, заключенными в фигурные скобки. (Хмм. Текст и команды в фигурных скобках. Звучит знакомо?) Команды определялись на Scheme; процессор разметки имел несколько вариантов использования, таких как HTML и PostScript. Позднее Скотт Дрэйвс расширил markup для своей диссертации по частичным вычислениям и высокопроизводительному графическому рендерингу в CMU.)

Я думаю, это вся команда T. Интересно отметить, что пять кандидатских диссертаций (и одна магистерская) произошли из одного летнего проекта.

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

Когда произошла революция RISC, Orbit был портирован на RISC-процессоры конца 80-х годов, MIPS и SPARC. В этот момент был удален сборщик мусора Кларка и заменен на сборщик Чейни. В CMU я портировал Orbit на предшественника архитектуры POWER компании IBM, называемого ROMP или RT/PC.

Одним из ограничивающих факторов Orbit была сложность бэкeнда. Он был очень хорошо задокументирован в диссертации Кранца и был очень продвинутым, но также был большой кучей кода. В ответ на эту сложность родился Scheme 48. Когда Келси пришел в Нортеастерн в качестве профессора, Джонатан все еще был в MIT, и они с Джонатаном совместно создали Scheme 48. Его первое использование произошло в автономной робототехнической системе, к которой Джонатан приобщился в Корнелле. Название было задумано для отражения идеи, что реализация должна быть настолько понятной и простой, что можно было бы поверить, что система могла быть написана за 48 часов (или, возможно, когда S48 стал достаточно сложным, это было изменено на "могла быть прочитана за 48 часов"). Scheme 48 практически не пересекался с T3 и Orbit с технической точки зрения — в нем не было нативного компилятора, системы объектов или CPS IR. Его новации заключались в модульной системе, языке, на котором была определена его виртуальная машина ("pre-scheme") и его технологии управления стеком. Все эти вещи были интересными техническими составляющими. Стек управлялся не с помощью push и pop, а с помощью push и поколенческого сборщика мусора. Я думаю, Келси написал на эту тему статью, в которой описал её преимущества. Модульная система была несколько похожа на систему SML, но позволяла создавать модулярные макросы и имела еще одну довольно интересную особенность: при определении модуля можно было указать, какие файлы содержат исходный код модуля. Но другие разделы позволяли указать, какую "читающую" процедуру использовать для преобразования потока символов в файлах в дерево s-выражений, передаваемое компилятору. Таким образом, вы могли работать с файлами с разным конкретным синтаксисом — синтаксисом R5RS, синтаксисом scsh, синтаксисом S48, синтаксисом PLT Scheme, синтаксисом guile, возможно, с инфиксным синтаксисом (так как он часто обсуждается). Это устраняло раздражающий, низкоуровневый, но постоянно существующий барьер для обмена кодом между разными реализациями Scheme.

Pre-scheme был довольно интересным. Келси, по-моему, также опубликовал на эту тему статью. Это был Scheme в том смысле, что его можно было загрузить в систему Scheme и выполнять код. Но он был ограниченным — требовалось писать в таком стиле, который позволял полное статическое выведение типов по Хиндли-Милнеру, и все процедуры высшего порядка подменялись бета-редукцией во время компиляции, что означало, что вы могли прямолинейно перевести программу на pre-scheme в "естественный" код на языке C с эффективностью на уровне C. То есть, pre-scheme можно было рассматривать как действительно приятную альтернативу языку C для низкоуровневого кода. И вы могли отлаживать свои программы на pre-scheme в интерактивной среде разработки Scheme по вашему выбору, прежде чем щёлкнуть выключателем и оттранслировать код на язык C, потому что pre-scheme была просто ограниченной Scheme. Интерпретатор байт-кода Scheme 48 был написан на pre-scheme. Pre-scheme, по сути, умерла — помимо академической статьи, написанной Келси, у него никогда не было времени продокументировать ее и превратить в отдельный инструмент, которым могли бы пользоваться другие люди (группа Иэна Хорсвиля в Северо-Западном университете — исключение из этого утверждения, они использовали pre-scheme для интересных исследований). Однако в ней есть идеи, которые можно использовать.

Позднее, в 1992 году, я начал использовать Scheme 48 для создания scsh, но мы начинаем отклоняться от темы T, поэтому не будем углубляться туда.

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

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

Вот некоторые ссылки на упомянутые мной статьи.

Первая статья, опубликованная о T, основанная на T2: Jonathan A. Rees and Norman I. Adams IV. T: A dialect of Lisp or, Lambda: The ultimate software tool. In Conference Record of the 1982 ACM Symposium on LISP and Functional Programming, pages 114-122, August 1982.
Обзор T3 компилятора Orbit: ORBIT: An optimizing compiler for Scheme. In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, published as SIGPLAN Notices 21(7), pages 219-233. Association for Computing Machinery, July 1986.
Существует позднее третье исследование, написанное Джонатаном и Норманом, посвященное системам объектов в целом и системе T в частности. У меня нет ссылки на него.
Руководство по использованию T также представляет интерес для изучения возможностей языка: Jonathan A.Rees, Norman I.Adams IV and James R. Meehan. The T Manual. 4th edition, Yale University, Department of Computer Science, January 1984.
Диссертация Келси: Compilation by Program Transformation. Ph.D.dissertation, Yale University, May 1989. Research Report 702, Department of Computer Science.
Диссертация Кранца: David Kranz. ORBIT: An Optimizing Compiler for Scheme. Ph.D. dissertation, Yale University, February 1988. Research Report 632, Department of Computer Science.

Прим. перев.

Если вас интересуют Lisp-подобные языки программирования, приглашаю вас на онлайн-митап русскоязычного Lisp-сообщества, который пройдёт уже в эту субботу, 1 июля 2023, в 18:00 по UTC+3. Трансляция будет проходить на моём Youtube-канале, а ссылка на видео будет опубликована в телеграм-группе нашего сообщества и моём телеграм-канале, подписывайтесь, чтобы не пропустить, и до встречи!

История T