Автор статьи сразу же уточняет, что советы его имеют субъективный характер: «пост состоит из некоторых полезных советов, которые я хотел бы услышать, когда мне было 18 лет». Поэтому критиковать положения из статьи стоит умеренно. В конце концов, если вы не последуете этим советам, то не станете преподавателем компьютерных наук, а вашу книгу по низкоуровневому программированию не будут рекламировать на Amazon. Только и всего. К счастью в информатике довольно широких дорог и узких тропинок для всех. Но лично мне интересен опыт автора и его путь в программировании.
Видно, что автор находится в стадии очарования функциональным и доказательным программированием. Ни вижу в этом ничего плохого. Но вот интересный момент: что предлагается выбрать в качестве первого языка. Scheme/Smalltalk — это языки компьютерных первопроходцев-экспериментаторов. Они олицетворяют тот подход в программировании, который позволяет эволюционно и итеративно разрабатывать программы. Эти языки не сковывают программиста правилами, а дают возможность уточнять задачу и алгоритмы прямо в процессе реализации. Совсем другое дело — Eiffel и ML. Замечательные языки, но нацелены они на совсем иной подход к разработке ПО. Предполагается, что в уме у нас уже есть формализованная модель задачи и мы описываем ее со всеми необходимыми ограничениями, которые не позволят получить некорректный результат. На мой взгляд, начинающему лучше иметь дело с языками Scheme/Smalltalk, которые не будут к нему и его не до конца оформленным идеям слишком строги. Другой вариант — какой-то язык с постепенной типизацией.
При всей моей приязни к Питону я вынужден согласиться с автором — язык действительно неважно спроектирован. Еще более существенно в контексте программирования для начинающих то, что Питон никак не побуждает программиста писать изящные, хорошие программы. Для Питона, увы, нет эквивалента SICP.
Полностью разделяю призыв автора знакомиться с разными подходами к программированию, с разными языками. Тут можно привести известные слова А. Перлиса: «A language that doesn't affect the way you think about programming, is not worth knowing».
Приятно, что упомянут и пункт по конструированию DSL — очень близкая мне тема. Вот только с выбором конструкторов не могу согласиться (JetBrains MPS, XText). Я бы предложил в первую очередь Stratego/XT.
И последнее. Автор неслучайно говорит о страсти к программированию. Страсть, любовь к написанию программ это те факторы, которые позволяют мириться с рутиной, которой в нашей профессии хоть отбавляй. Если вы думаете заняться программированием только лишь ради популярности профессии, ради заработка, то… есть способы заработать проще. Высиживать перед экраном долгие часы, пребывать в угнетенном состоянии, когда что-то не работает или снова нужно изучать новые подходы и технологии — все это легко преодолевается, только если у вас есть страсть, если вы действительно любите разрабатывать программы.
Да, это хорошее руководство. Кстати, для любого интересующегося программиста посоветую полезное упражнение: реализовать META II на вашем любимом языке. Так, чтобы код системой порождался для вашего же языка.
Ian Piumarta — один из разработчиков, участвовавших в проекте STEPS Алана Кэя. И его система из статьи мне нравится своим изяществом значительно больше, чем известная oMeta.
Кстати, один из вариантов META II использовался для создания знаменитой «The Mother of All Demos» (1968). И примечателен сам подход: создание сложной системы в нотациях множества DSL. Только в те времена их называли SPL — special purpose languages. Воистину, новое — хорошо забытое старое.
Да, причем некоторые из этих древних техник до сих пор недоступны в рамках стандартного Си. В частности, в рамках интерпретатора шитого кода можно было бы избавиться от конструкции switch с применением вычислимого goto. Но такой вариант является использованием нестандартного gcc-расширения.
Поделюсь еще одной малоизвестной статьей. На сей раз достаточно свежей. Ее автор, В. Макаров (известный разработчик в gcc-сообществе) сравнивает регистровые и стековые ВМ, пишет о шитом коде и т.д. уже с современных позиций: arxiv.org/pdf/1604.01290.pdf
А знакомы ли Вы с системой META II (1964)? Такие известные личности, как Д. Кнут, А. Кэй или Д. Армстронг (автор Erlang) отзывались о META II очень положительно.
META II это генератор компиляторов, который написан на себе самом и порождает код для стековой VM. Оригинальная статья о META II в числе моих самых любимых: www.ibm-1401.info/Meta-II-schorre.pdf
P.S. Когда-то у меня была идея написать краткий вводный курс по компиляторам-интерпретаторам с разбором всего двух систем: META II и Forth.
«С презентации Java Virtual Machine во второй половине 90-х прошло уже достаточно много времени, и можно с уверенностью сказать, что интерпретаторы байт-кодов — не будущее, а настоящее»
Словно бы мы говорим не о 90-х, а о 60-х годах! В 60-е годы языковые ВМ только развивались и за их использование еще нужно было кого-то агитировать. К середине 70-х такие решения уже окончательно стали частью арсенала рядовых разработчиков. Можно вспомнить, например, статью J. Bell «Threaded Code» (1973) или учебник Вирта «Алгоритмы + структуры данных = программы» (1976), где был описан интерпретатор ВМ PL/0.
Вспомните также многочисленные игры конца 70-х и начала 80-х со встроенным интерпретатором байткода. Вспомните опередившую свое время систему Visi On. А уже в 80-х использованием языковой ВМ уже никого нельзя было удивить.
Вопрос по поводу реализации сопоставления с образцом «из подручных средств» мне тоже весьма близок. Для решения сложных задач внутри компилятора не хватает возможностей и в тех языках, где эта конструкция имеется (да, даже в Haskell). Кстати, в этом смысле любопытно представить, что в идеальном мире разработчики с конца 70-х годов компиляторы пишут на Пролог-подобном языке. Есть совершенно замечательная статья как раз на эту тему: sovietov.com/tmp/warren1980.pdf
Впрочем, и здесь только лишь встроенных в язык возможностей все еще недостаточно.
И еще отдельная интересная тема — сопоставление на произвольных графах.
Отрадно, что в интервью оказалась затронута и техническая составляющая. Прокомментирую пару тезисов с точки зрения академической разработки компиляторов.
1. «А про синтаксис понятно, синтаксис — это просто». Действительно, в современном учебнике по компиляторам теме синт. разбора (должно быть) отведено от силы 10-15% материала. Остальное-то, как раз, и есть самое сложное, интересное и плохо формализованное. Впрочем, понятно, что для пользователей языка это самое «остальное» не столь заметно, как синтаксис.
2. «Например, нам бы в компиляторе очень пригодились некоторые языковые фичи, которые больше никому не нужны». Вот этот момент по поводу использования конструкции сопоставления с образом для меня является очень важным. Потому что во многих даже очень солидных современных компиляторах все еще применяют неуклюжий шаблон Visitor (родом из корпоративной/ООП-культуры разработки) для обхода и трансформаций AST/IR. При этом, опять же, в хорошем учебнике по компиляторам вы «посетителей» не встретите. Вместо них используются функции высших порядков и сопоставление с образцом на деревьях/термах. На эту тему высказывались и Питер Норвиг (https://norvig.com/design-patterns/ ), Мартин Одерски (https://www.artima.com/weblogs/viewpost.jsp?thread=166742 ). В связи с этим приятно, что автор Kotlin думает о том, как переписать компилятор в более изящном, декларативном духе.
Физики, которых Вы упомянули, безусловно внесли свой вклад в развитие микроэлектроники. Мид отличается от них тем, что он не только физик. Первый учебник по СБИС, первые инструменты автоматизации их проектирования (включая подход кремниевой компиляции) — это тоже он.
Я написал свое сообщение с целю стимулировать поиск информации читателей о Миде. Возможно, кто-нибудь напишет и заметку в контексте истории и перспектив СБИС-технологий. Ведь знание соотв. истории важнее, чем часто себе представляют. Оно расширяет горизонты, дает возможность ввести в оборот множество забытых идей, не позволяет превратиться в узколобого профессионала, который «все знает». Лучше держаться подальше от подобных знаек!
То, что Вы описываете, в СССР 60-х называлось однородными вычислительными структурами и моделью коллектива вычислителей. Здесь уже было все: децентрализация, асинхронность, близкодействие… А в конце 70-х знаменитый ученый Карвер Мид (один из тех, о ком почему-то не пишут на хабре) указал на матричный подход для борьбы со сложностью в рамках СБИС-технологий. Далее были систолические массивы, массивы волнового фронта. Синхронные и асинхронные варианты… Вплоть до проектов AsAP и SEAforth, с коллективами которых Вашему покорному слуге когда-то пришлось иметь дело :) Сегодня этот подход снова популярен в виде реконфигурируемых/dataflow крупноблочных структур. Подобные проекты есть у Xilinx, Google, Intel.
К сожалению, «определенной новизны» я в тексте не увидел. Метапрограммирование, генераторы программ, графическое программирование, DSL...— все это известно давно, согласитесь.
В этом смысле обзор аналогов, от которого Вы отказались, был бы весьма кстати. Комментаторы справедливо указывают, что четких терминов, которые можно легко нагуглить, у Вас практически нет. Вашу «прямую задачу» в настоящее время связывают с направлением program synthesis (superoptimization и другие подходы «на примерах»). К «обратной задаче» относится направление automatic algorithm recognition (в этом контексте постановка задачи автораспараллеливания как раз весьма и весьма уместна). Оба этих направления чрезвычайно перспективны и по ним уже накоплен определённый объём серьезных результатов.
Спасибо за ссылку на проект и за перевод. Я стараюсь отслеживать появление ресурсов по разработке компиляторов для начинающих, но этот проект по какой-то причине упустил из виду. Позволю себе небольшую критику английского варианта.
На мой взгляд, разумно начать с причин, по которым с построением компиляторов важно знакомиться неспециалистам. Причины эти сегодня не так уж очевидны, помимо совсем уж тривиального — “изучение устройства инструмента может помочь в практической с ним работе”. Казалось бы, языков и компиляторов уже и так существует великое множество. А для исключительных случаев есть перенацеливаемые системы gcc и LLVM.
Подробный ответ включал бы в себя DSL и порождение кода для экзотических архитектур (бытует расхожее мнение, что архитектура команд это нечто неизменное, и если хочется нового — следует брать RISCV, созданную специалистами мирового класса. В качестве возражения можно привести подходы с синтезируемой системой команд, ASIP, CGRA, HLS).
Новые подходы к компиляции часто требуют перестройки архитектуры существующего компилятора. Так произошло, например, с популяризацией SSA. И, скорее всего, именно по такой причине в gcc и LLVM до сих пор отсутствует работа с графовым представлением, подобным sea of nodes, не говоря уже о более нишевых и более современных представлениях программы. Реализации современных подходов, и пусть это не кажется теперь странным, чаще можно найти в небольшом DSL-компиляторе.
В коде данного проекта учебного компилятора можно встретить visitors. На мой взгляд, это неоднозначный выбор. Разумеется, использование данного шаблона проектирования — данность, обусловленная, во многом, преподаванием ООП/Java. Более того, visitors до сих пор можно встретить в реализациях некоторых “промышленных” компиляторов. Но начинающим, и это мое убеждение, следует демонстрировать вещи в наиболее прозрачной и естественной для соответствующего предмета изучения нотации. В хорошем учебнике по компиляторам вы не найдёте visitors. Сопоставление с образцом, которое этот шаблон с успехом заменяет, используется в наши дни даже в таких популярных и практичных языках, как Scala.
Любопытно, что автор так и не воспользовался в своей реализации visitors методом exit, который соответствует обходу дерева снизу вверх. А ведь именно такой порядок обхода используется в проекте для реализации генератора кода. Здесь автор обошёлся лишь рекурсией и switch. Почему же не сделать того же и в остальных частях программы?
Комментарий получается слишком пространным, но мне все еще не даёт покоя вопрос: а где же подобные введения на русском языке, оригиналы, а не переводы? Ведь предположение о том, что русскоязычные разработчики менее компетентны в области компиляторов, чем автор рассмотренного учебного компилятора, является абсолютно несостоятельным…
Ссылку на статью Норвига приходится давать регулярно, свежий перевод будет весьма кстати, спасибо за него. Одно замечание: учебник по Mozart/Oz действительно очень хороший. Но к легкому чтению я бы его не отнёс. Это текст, скорее, для программистов-теоретиков, которые имеют склонность к разработке языков программирования. Поэтому, очевидно, его редко советуют в блогах. При этом в книге имеется действительно масса интересных идей и концепций, которые все еще ждут более доступного изложения и соответствующего инструментального ПО.
Еще вспомнилось:
Он говорил, что знает языки программирования и операционные системы, хотя не имел о них ни малейшего представления, всего лишь прочитав книгу о предмете за несколько часов до интервью. И он умудрялся добиваться места, вешая лапшу на уши.
«Нам нужны специалисты, которые программируют на BAL», — могли сказать ему, упоминая какой-то таинственный язык программирования, а он мог саркастически рассмеяться:
«BAL? Да я программирую на BAL последние три года!»
Затем он немедленно бежал за книгами, потому что он никогда раньше не слышал ни о каком BALe. Но к тому времени когда начиналась реальная работа, он уже доставал всю нужную документацию, обычно представленную в виде тонких, отпечатанных на дешевой бумаге и плохо переплетенных книг, которая была фальшивым доказательством его опыта с BAL, или, по крайней мере, он выигрывал время, до тех пор пока он не добирался до машины и не выяснял что из себя представляет этот BAL.
Предположу, что книга «Как стать гением» разочаровала Вас отсутствием конкретных технических рецептов и методик. На мой взгляд, специально избегать ее совершенно излишне. Текст, конечно, чисто художественный, но, в отличие от современных абстрактно-мотивирующих книг, способен побудить читателя заниматься серьезной научно-технической деятельностью. Любопытно, что многое у Альтшуллера перекликается с высказываниями Алана Кэя, в духе, например, «If you don't fail at least 90 percent of the time, you're not aiming high enough». Не знаю, знаком ли сам Кэй с ТРИЗ, но вот у Брета Виктора на книжной полке имеется And Suddenly the Inventor Appeared – Genrich Altshuller.
Автор статьи поднял интересную тему. Любопытно проанализировать процесс построения известных языков программирования и попытаться найти здесь сходство с принципами ТРИЗ. Я просто упомяну еще раз А. Кэя, Ч. Хоара (см. тьюринговскую лекцию) и таких известных архитекторов-минималистов, как Н. Вирт и Ч. Мур. Надо сказать, в языке Форт, стараниями Мура и Броуди, зародилась сходная с ТРИЗ «теория решения программистских задач».
Спасибо за Вашу статью, но в одном моменте позиция автора не совсем мне понятна. Давайте отвлечемся от геополитических соображений. Разумно ли некоторой fabless-компании вообще связываться с разработкой собственных архитектур уже по чисто экономическим соображениям? Кстати говоря, хороший ответ на этот вопрос дает лекция тьюринговских лауреатов Хеннесси и Паттерсона.
А вот это интересный для меня вопрос по компьютерной истории. Кто в современной России первым разработал микропроцессоры/СнК именно для коммерческих/частных применений? Пока что ответ я для себя нашел довольно неожиданный. Микросхема R100-XP для незабвенных телефонов «Русь», 2003 год.
«Я все еще люблю книги. Компьютер не сравнится с книгой. Вы не сможете в буквальном смысле втиснуть книгу в интернет. Три компании предлагали выложить мои книги в интернет и я ответил им: „если вы сможете сделать нечто такое, что имеет приятную обложку, приятную бумагу с приятным запахом, то тогда мы сможем поговорить“. Все, на что способен компьютер, это выдать вам черновик. Люди не хотят читать рукописи. Они хотят читать книги. Книги хорошо пахнут. Они хорошо выглядят. Вы можете прижать их к своей груди. Вы можете носить их в кармане.»
Не стоит спешить спорить с наивными высказваниями Р. Брэдбери. Он был не противником технологий. Но он желал иметь технологии, которые не отрицают культуру, накопленный человечеством опыт и саму человеческую природу. Так ли уж хороши современные «картинки под стеклом»? Можно ли поставить задачу сделать электронные книги, которые бы понравились даже самому заядлому собирателю библиотек?
Спасибо автору заметки за упоминание писателя Д. Хэрриота. А еще были С. Томпсон, Д. Кервуд и многие, многие другие. Замечательное издательство «Мир»!.. Ему я обязан не только знакомством с превосходной переводной худ. литературой, но и с научно-технической. Отлично изданная книга «Язык компьютера» оказалась в свое время для меня введением в мир языков и стилей программирования. В 90-е я провел много времени в букинистических магазинах, покупая фундаментальные книги по компьютерной тематике. Эти книги до сих пор не утратили своей актуальности и стоят, но отнюдь не пылятся в моей библиотеке.
Так, собственно, у меня и повелось: фундаментальные книги остались в бумажной библиотеке, а все остальное, современное и сиюминутное я читаю с помощью последней модели ipad (ничего лучше для глаз и для чтения pdf для себя так и не нашел).
На мой взгляд, разграничение вполне логичное и оно проходит не в области парадигм, а в области архитектуры приложения. Нижнему уровню в большинстве случаев и полагается быть императивным. Собственно, примеров, когда интерпретатор Лиспа встроен в большую программную систему для расширения возможностей последней — масса. Даже в старых компьютерных играх такое вполне практиковалось, можно вспомнить древний Zork, где использовался далект Лиспа под названием MDL или более позднюю Abuse. Я уже не говорю про Autocad, Cakewalk и проч.
С другой стороны, сейчас для встраивания в приложения существуют Tcl, Python, Lua и многие-многие другие. Поэтому, кстати говоря, я призываю к критической, объективной оценке того, где действительно целесообразно применять Лисп. Ниже привожу несколько возможных вариантов.
1. Универсальное текстовое представление вычислений и данных для обмена между программными модулями. Здесь фигурирует, вообще говоря, не совсем Лисп, а его существенный элемент под названием S-выражения. В каких-то случаях S-выражения могут быть предназначены и для редактирования пользователями. Например, можно реализовать синтаксис ассемблера для какой-то экзотической архитектуры в форме Лисп-подобной нотации. В большинстве случаев ассемблерный код будет порожден компилятором, но можно учесть и вариант, когда на Лисп-подобном ассемблере придется писать человеку.
2. Миниатюрный диалоговый язык для удаленного управления скромным по ресурсам микроконтроллером. Существуют Лисп-подобные реализации, которые выгоднее использовать в таких условиях, чем даже Lua.
3. Средство для метапрограммирования и программных трансформаций. Тот, достаточно редкий, случай, когда важнейшим свойством Лиспа программа=данные действительно необходимо воспользоваться. Например, если требуется какая-то совершенно экзотическая программная конструкция, поддержки которой еще нет ни у Google, ни у Microsoft. «Нам совершенно необходим встроенный движок для программирования в ограничениях!» Здесь, однако, нужно серьезно поразмыслить, а нужно ли все это городить именно в рамках Лиспа.
Как можно видеть, использование Common Lisp не слишком-то увязывается с описанными выше пунктами. К CL у работодателя могут возникнуть резонные вопросы на тему того, кто будет поддерживать систему после Вас, стоит ли в целом овчинка выделки. В этом смысле показательны примеры игровой компании Naughty Dog и Пола Грэма с Yahoo. Другое дело, что если просто _нравится_ писать на CL, да и условия позволяют — почему бы и нет :)
Скобки здесь при том, что это синтаксический рудимент Лиспа, который просочился в нотацию нашего DSL. Спасибо за пример. Заранее прошу не принимать мою критику в штыки. Заслуживает уважения уже то, что Вы выбрали Лисп в качестве инструмента разработки.
В коде обращает внимание использование известного макро loop, которое является частью стандарта CL. Это действительно специализированная конструкция со своим особым синтаксисом. А вот макро defmain вполне заурядно. На обычном языке, который поддерживает замыкания, можно было бы сделать аналогичный комбинатор, который развернется в нечто подобное тому, что Вы привели.
А примером языка, поддерживающего конструирование DSL, является Rebol с его диалектами.
Видно, что автор находится в стадии очарования функциональным и доказательным программированием. Ни вижу в этом ничего плохого. Но вот интересный момент: что предлагается выбрать в качестве первого языка. Scheme/Smalltalk — это языки компьютерных первопроходцев-экспериментаторов. Они олицетворяют тот подход в программировании, который позволяет эволюционно и итеративно разрабатывать программы. Эти языки не сковывают программиста правилами, а дают возможность уточнять задачу и алгоритмы прямо в процессе реализации. Совсем другое дело — Eiffel и ML. Замечательные языки, но нацелены они на совсем иной подход к разработке ПО. Предполагается, что в уме у нас уже есть формализованная модель задачи и мы описываем ее со всеми необходимыми ограничениями, которые не позволят получить некорректный результат. На мой взгляд, начинающему лучше иметь дело с языками Scheme/Smalltalk, которые не будут к нему и его не до конца оформленным идеям слишком строги. Другой вариант — какой-то язык с постепенной типизацией.
При всей моей приязни к Питону я вынужден согласиться с автором — язык действительно неважно спроектирован. Еще более существенно в контексте программирования для начинающих то, что Питон никак не побуждает программиста писать изящные, хорошие программы. Для Питона, увы, нет эквивалента SICP.
Полностью разделяю призыв автора знакомиться с разными подходами к программированию, с разными языками. Тут можно привести известные слова А. Перлиса: «A language that doesn't affect the way you think about programming, is not worth knowing».
Приятно, что упомянут и пункт по конструированию DSL — очень близкая мне тема. Вот только с выбором конструкторов не могу согласиться (JetBrains MPS, XText). Я бы предложил в первую очередь Stratego/XT.
И последнее. Автор неслучайно говорит о страсти к программированию. Страсть, любовь к написанию программ это те факторы, которые позволяют мириться с рутиной, которой в нашей профессии хоть отбавляй. Если вы думаете заняться программированием только лишь ради популярности профессии, ради заработка, то… есть способы заработать проще. Высиживать перед экраном долгие часы, пребывать в угнетенном состоянии, когда что-то не работает или снова нужно изучать новые подходы и технологии — все это легко преодолевается, только если у вас есть страсть, если вы действительно любите разрабатывать программы.
А вот еще замечательная статья, которую Вы, возможно, не видели: www.vpri.org/pdf/tr2010003_PEG.pdf
Ian Piumarta — один из разработчиков, участвовавших в проекте STEPS Алана Кэя. И его система из статьи мне нравится своим изяществом значительно больше, чем известная oMeta.
Кстати, один из вариантов META II использовался для создания знаменитой «The Mother of All Demos» (1968). И примечателен сам подход: создание сложной системы в нотациях множества DSL. Только в те времена их называли SPL — special purpose languages. Воистину, новое — хорошо забытое старое.
Поделюсь еще одной малоизвестной статьей. На сей раз достаточно свежей. Ее автор, В. Макаров (известный разработчик в gcc-сообществе) сравнивает регистровые и стековые ВМ, пишет о шитом коде и т.д. уже с современных позиций: arxiv.org/pdf/1604.01290.pdf
META II это генератор компиляторов, который написан на себе самом и порождает код для стековой VM. Оригинальная статья о META II в числе моих самых любимых: www.ibm-1401.info/Meta-II-schorre.pdf
P.S. Когда-то у меня была идея написать краткий вводный курс по компиляторам-интерпретаторам с разбором всего двух систем: META II и Forth.
Словно бы мы говорим не о 90-х, а о 60-х годах! В 60-е годы языковые ВМ только развивались и за их использование еще нужно было кого-то агитировать. К середине 70-х такие решения уже окончательно стали частью арсенала рядовых разработчиков. Можно вспомнить, например, статью J. Bell «Threaded Code» (1973) или учебник Вирта «Алгоритмы + структуры данных = программы» (1976), где был описан интерпретатор ВМ PL/0.
Вспомните также многочисленные игры конца 70-х и начала 80-х со встроенным интерпретатором байткода. Вспомните опередившую свое время систему Visi On. А уже в 80-х использованием языковой ВМ уже никого нельзя было удивить.
Исторический контекст важно учитывать и если у этой заметки будет продолжение на тему JIT, то нелишне будет и ознакомиться со статьей «A Brief History of Just-In-Time»: eecs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/JustInTimeCompilation.pdf
В первую очередь вспоминается LLVM-код: llvm.org/doxygen/PatternMatch_8h_source.html
Вопрос по поводу реализации сопоставления с образцом «из подручных средств» мне тоже весьма близок. Для решения сложных задач внутри компилятора не хватает возможностей и в тех языках, где эта конструкция имеется (да, даже в Haskell). Кстати, в этом смысле любопытно представить, что в идеальном мире разработчики с конца 70-х годов компиляторы пишут на Пролог-подобном языке. Есть совершенно замечательная статья как раз на эту тему:
sovietov.com/tmp/warren1980.pdf
Впрочем, и здесь только лишь встроенных в язык возможностей все еще недостаточно.
И еще отдельная интересная тема — сопоставление на произвольных графах.
1. «А про синтаксис понятно, синтаксис — это просто». Действительно, в современном учебнике по компиляторам теме синт. разбора (должно быть) отведено от силы 10-15% материала. Остальное-то, как раз, и есть самое сложное, интересное и плохо формализованное. Впрочем, понятно, что для пользователей языка это самое «остальное» не столь заметно, как синтаксис.
2. «Например, нам бы в компиляторе очень пригодились некоторые языковые фичи, которые больше никому не нужны». Вот этот момент по поводу использования конструкции сопоставления с образом для меня является очень важным. Потому что во многих даже очень солидных современных компиляторах все еще применяют неуклюжий шаблон Visitor (родом из корпоративной/ООП-культуры разработки) для обхода и трансформаций AST/IR. При этом, опять же, в хорошем учебнике по компиляторам вы «посетителей» не встретите. Вместо них используются функции высших порядков и сопоставление с образцом на деревьях/термах. На эту тему высказывались и Питер Норвиг (https://norvig.com/design-patterns/ ), Мартин Одерски (https://www.artima.com/weblogs/viewpost.jsp?thread=166742 ). В связи с этим приятно, что автор Kotlin думает о том, как переписать компилятор в более изящном, декларативном духе.
Здесь можно посмотреть его послужной список: www.carvermead.caltech.edu/research.html
Обратите также внимание на эту статью 77 года: ai.eecs.umich.edu/people/conway/VLSI/BackgroundContext/Sciam/SM.SciAm77.pdf
На мой взгляд многие ее положения актуальны до сих пор.
А с какой целью написали сообщение Вы?
В этом смысле обзор аналогов, от которого Вы отказались, был бы весьма кстати. Комментаторы справедливо указывают, что четких терминов, которые можно легко нагуглить, у Вас практически нет. Вашу «прямую задачу» в настоящее время связывают с направлением program synthesis (superoptimization и другие подходы «на примерах»). К «обратной задаче» относится направление automatic algorithm recognition (в этом контексте постановка задачи автораспараллеливания как раз весьма и весьма уместна). Оба этих направления чрезвычайно перспективны и по ним уже накоплен определённый объём серьезных результатов.
На мой взгляд, разумно начать с причин, по которым с построением компиляторов важно знакомиться неспециалистам. Причины эти сегодня не так уж очевидны, помимо совсем уж тривиального — “изучение устройства инструмента может помочь в практической с ним работе”. Казалось бы, языков и компиляторов уже и так существует великое множество. А для исключительных случаев есть перенацеливаемые системы gcc и LLVM.
Подробный ответ включал бы в себя DSL и порождение кода для экзотических архитектур (бытует расхожее мнение, что архитектура команд это нечто неизменное, и если хочется нового — следует брать RISCV, созданную специалистами мирового класса. В качестве возражения можно привести подходы с синтезируемой системой команд, ASIP, CGRA, HLS).
Новые подходы к компиляции часто требуют перестройки архитектуры существующего компилятора. Так произошло, например, с популяризацией SSA. И, скорее всего, именно по такой причине в gcc и LLVM до сих пор отсутствует работа с графовым представлением, подобным sea of nodes, не говоря уже о более нишевых и более современных представлениях программы. Реализации современных подходов, и пусть это не кажется теперь странным, чаще можно найти в небольшом DSL-компиляторе.
В коде данного проекта учебного компилятора можно встретить visitors. На мой взгляд, это неоднозначный выбор. Разумеется, использование данного шаблона проектирования — данность, обусловленная, во многом, преподаванием ООП/Java. Более того, visitors до сих пор можно встретить в реализациях некоторых “промышленных” компиляторов. Но начинающим, и это мое убеждение, следует демонстрировать вещи в наиболее прозрачной и естественной для соответствующего предмета изучения нотации. В хорошем учебнике по компиляторам вы не найдёте visitors. Сопоставление с образцом, которое этот шаблон с успехом заменяет, используется в наши дни даже в таких популярных и практичных языках, как Scala.
Любопытно, что автор так и не воспользовался в своей реализации visitors методом exit, который соответствует обходу дерева снизу вверх. А ведь именно такой порядок обхода используется в проекте для реализации генератора кода. Здесь автор обошёлся лишь рекурсией и switch. Почему же не сделать того же и в остальных частях программы?
Для знакомых с Лисп-подобными языками в качестве возможной альтернативы данному проекту я бы посоветовал очень хорошее введение Essentials of Compilation An Incremental Approach (https://jeapostrophe.github.io/courses/2017/spring/406/notes/book.pdf ). Не теряют актуальности и сегодня известные учебники Вирта (https://www.ozon.ru/context/detail/id/4803779/ ) и Эппеля (https://www.cs.princeton.edu/~appel/modern/ml/ ).
Комментарий получается слишком пространным, но мне все еще не даёт покоя вопрос: а где же подобные введения на русском языке, оригиналы, а не переводы? Ведь предположение о том, что русскоязычные разработчики менее компетентны в области компиляторов, чем автор рассмотренного учебного компилятора, является абсолютно несостоятельным…
Глава о Кене Вильямсе и Sierra.
Еще вспомнилось:
Автор статьи поднял интересную тему. Любопытно проанализировать процесс построения известных языков программирования и попытаться найти здесь сходство с принципами ТРИЗ. Я просто упомяну еще раз А. Кэя, Ч. Хоара (см. тьюринговскую лекцию) и таких известных архитекторов-минималистов, как Н. Вирт и Ч. Мур. Надо сказать, в языке Форт, стараниями Мура и Броуди, зародилась сходная с ТРИЗ «теория решения программистских задач».
Не стоит спешить спорить с наивными высказваниями Р. Брэдбери. Он был не противником технологий. Но он желал иметь технологии, которые не отрицают культуру, накопленный человечеством опыт и саму человеческую природу. Так ли уж хороши современные «картинки под стеклом»? Можно ли поставить задачу сделать электронные книги, которые бы понравились даже самому заядлому собирателю библиотек?
Спасибо автору заметки за упоминание писателя Д. Хэрриота. А еще были С. Томпсон, Д. Кервуд и многие, многие другие. Замечательное издательство «Мир»!.. Ему я обязан не только знакомством с превосходной переводной худ. литературой, но и с научно-технической. Отлично изданная книга «Язык компьютера» оказалась в свое время для меня введением в мир языков и стилей программирования. В 90-е я провел много времени в букинистических магазинах, покупая фундаментальные книги по компьютерной тематике. Эти книги до сих пор не утратили своей актуальности и стоят, но отнюдь не пылятся в моей библиотеке.
Так, собственно, у меня и повелось: фундаментальные книги остались в бумажной библиотеке, а все остальное, современное и сиюминутное я читаю с помощью последней модели ipad (ничего лучше для глаз и для чтения pdf для себя так и не нашел).
С другой стороны, сейчас для встраивания в приложения существуют Tcl, Python, Lua и многие-многие другие. Поэтому, кстати говоря, я призываю к критической, объективной оценке того, где действительно целесообразно применять Лисп. Ниже привожу несколько возможных вариантов.
1. Универсальное текстовое представление вычислений и данных для обмена между программными модулями. Здесь фигурирует, вообще говоря, не совсем Лисп, а его существенный элемент под названием S-выражения. В каких-то случаях S-выражения могут быть предназначены и для редактирования пользователями. Например, можно реализовать синтаксис ассемблера для какой-то экзотической архитектуры в форме Лисп-подобной нотации. В большинстве случаев ассемблерный код будет порожден компилятором, но можно учесть и вариант, когда на Лисп-подобном ассемблере придется писать человеку.
2. Миниатюрный диалоговый язык для удаленного управления скромным по ресурсам микроконтроллером. Существуют Лисп-подобные реализации, которые выгоднее использовать в таких условиях, чем даже Lua.
3. Средство для метапрограммирования и программных трансформаций. Тот, достаточно редкий, случай, когда важнейшим свойством Лиспа программа=данные действительно необходимо воспользоваться. Например, если требуется какая-то совершенно экзотическая программная конструкция, поддержки которой еще нет ни у Google, ни у Microsoft. «Нам совершенно необходим встроенный движок для программирования в ограничениях!» Здесь, однако, нужно серьезно поразмыслить, а нужно ли все это городить именно в рамках Лиспа.
Как можно видеть, использование Common Lisp не слишком-то увязывается с описанными выше пунктами. К CL у работодателя могут возникнуть резонные вопросы на тему того, кто будет поддерживать систему после Вас, стоит ли в целом овчинка выделки. В этом смысле показательны примеры игровой компании Naughty Dog и Пола Грэма с Yahoo. Другое дело, что если просто _нравится_ писать на CL, да и условия позволяют — почему бы и нет :)
В коде обращает внимание использование известного макро loop, которое является частью стандарта CL. Это действительно специализированная конструкция со своим особым синтаксисом. А вот макро defmain вполне заурядно. На обычном языке, который поддерживает замыкания, можно было бы сделать аналогичный комбинатор, который развернется в нечто подобное тому, что Вы привели.
А примером языка, поддерживающего конструирование DSL, является Rebol с его диалектами.