Истоки
Несколько лет назад я написал компилятор Паскаля. Мотивация была простой: в юности я узнал из своих первых книжек по программированию, что компилятор — вещь чрезвычайно сложная. Это утверждение засело занозой в мозгу и в конце концов потребовало проверки на опыте.
ha.art.pl
Сперва родился простейший компилятор PL/0, а из него постепенно вырос почти полнофункциональный компилятор Паскаля для MS-DOS. Вдохновением мне служила книга Compiler Construction, написанная создателем языка Паскаль Никлаусом Виртом. И пусть взгляды Вирта уже устарели и утратили всякую связь с реалиями ИТ, а компиляторы делают совсем не так, как учил Вирт. Однако его методы по-прежнему просты, изящны, а главное — приносят радость, ведь самостоятельно разобрать текст программы рекурсивным спуском и сгенерировать машинный код намного заманчивее, чем призывать на помощь яков, бизонов и всех их преемников.
Судьба моего компилятора оказалась не самой тривиальной. Он прожил две жизни: первую — в моих руках, вторую — в руках польских ценителей компьютерных древностей.
XD Pascal
Мой свежеиспечённый компилятор получил название XD Pascal. Он поддерживал все операторы Паскаля, кроме
goto и with. Первый показался мне трудным для реализации, поскольку разрушал идеально иерархичную структуру программы. Второй — создавал путаницу с областями видимости имён.Поддерживались и все основные типы данных. За рамками остались только беззнаковые целые числа, множества, перечисления и вариантные записи — однако всё это явно не предметы первой необходимости. Тем не менее, я не мог отказать себе в удовольствии от чисел с плавающей точкой и их арифметики на сопроцессоре 8087 — тут сказалась профессиональная склонность к инженерным расчётам.
При реализации процедур и функций я опасался, что большой проблемой окажутся рекурсия и хранение локальных переменных в стеке. Однако настоящая трудность, специфичная для Паскаля, подстерегала совсем в другом месте — в работе с вложенными процедурами. Может возникнуть совершенно невинная надобность обратиться к локальной переменной внешней процедуры из внутренней. Однако во внутренней процедуре нет адреса стекового кадра внешней процедуры — внутренняя процедура не знает, от чего отсчитывать адрес искомой переменной. Этот адрес приходится всякий раз передавать во внутреннюю процедуру через дополнительный скрытый параметр. Подозреваю, что именно это осложнение заставило разработчиков C вовсе отказаться от вложения функций. Однако в Паскале они есть, и с этим приходится считаться.
Генератор кода создавал самые простые исполняемые файлы COM для реального режима MS-DOS. Машинный код генерировался напрямую, без помощи внешнего ассемблера или компоновщика. Для данных я использовал 32-битные регистры архитектуры 80386, а адресация осталась 16-битной, в виде пары сегмент-смещение.
Модель памяти примерно соответствовала «малой» (если кто-то ещё помнит эту терминологию 16-битной эпохи): для кода, глобальных данных и стека выделялось по одному сегменту размером 64 кб.
Использование памяти
Генерация файлов EXE и переключение сегментов на лету казались чересчур сложным делом, и тесные рамки «малой» модели заставили меня распрощаться с идеей самокомпиляции. Конечно, мне встречались самокомпилируемые компиляторы, код которых целиком умещался в одном сегменте (например, Context). Однако они редко умели делать хоть что-то полезное кроме этой самокомпиляции. Я же хотел сделать свой компилятор хоть немного пригодным для численных расчётов и вывода графики. Поэтому среди примеров программ появились фракталы, решение линейных уравнений по Гауссу, быстрое преобразование Фурье и даже оценивание фильтром Калмана ошибок инерциальной навигационной системы.
Фрагмент множества Мандельброта
Быстрое преобразование Фурье
Оценивание погрешностей инерциальной навигационной системы
То, что у меня получилось в итоге, больше всего напоминало древний как мир Turbo Pascal 3.0 (ещё без ООП) и любительский BeRo Tiny Pascal. Автор последнего совладал с самокомпиляцией под Windows, однако пожертвовал арифметикой с плавающей точкой и многими тонкостями грамматики, которые мне хотелось соблюсти. Из более современных особенностей в моём XD Pascal появились позаимствованные из Delphi однострочные комментарии (
//) и автопеременная Result.Впрочем, ещё с самого своего рождения мой компилятор был отмечен печатью смерти. Паскаль уже необратимо выходил из моды, а MS-DOS давно стал архаикой. В тот день, когда я перешёл с 32-битной Windows XP на 64-битную Windows 7 без виртуальной машины DOS, я мысленно похоронил свой проект.
Возрождение
Затем произошло странное. После трёх лет полного забвения некая группа польских энтузиастов ретрокомпьютинга и любителей Atari отыскала мой компилятор. Судя по всему, абстрактные проблемы самокомпилируемости и строгости реализации грамматики их волновали мало. Им просто нужен был удобный инструмент программирования их любимой машины. Из моего проекта они сделали собственный компилятор Mad Pascal для архитектуры 6502. Грамматика языка разрослась, появилась поддержка модулей с секциями интерфейса и реализации, оператора
goto, беззнаковых целых чисел, множеств и перечислений, ассемблерных вставок. Вместо машинного кода теперь генерировался ассемблерный код. Его финальная трансляция делалась ассемблером собственной разработки.Внешне язык стал заметно ближе к фактическому стандарту Паскаля. Внутри компилятор выглядит несколько устрашающе, зарезервированные слова перемешаны с именами стандартных процедур, однако это авторов нисколько не смущает. Как бы оно ни выглядело, но дело оказалось на удивление живучим: вот уже три года Mad Pascal регулярно обновляется, на нём написано немало игр, авторы ежегодно выступают на ретроконференции Silly Venture (ссылка требует VPN). Возникает ощущение, что в Польше вообще очень сильны традиции почитания Atari.
Весной 2018 года произошло событие, весьма примечательное для польской тусовки поклонников Atari: вышла книга «Robbo. Solucja» («Роббо. Прохождение») в жанре экспериментальной литературы. Здесь надо сказать, что сама игра Robbo для Atari, изданная 30 лет назад, до сих пор волнует сердца поляков старшего поколения и наполняет их патриотическим восторгом. В общем, неудивительно, что появилась посвящённая игре книжка. Забавно лишь то, что она, по словам авторов, на 60 % состоит из инструкций по прохождению игры, сгенерированных самим компьютером Atari. Программа генерации написана на том самом Mad Pascal.
graczpospolita.pl
И кажется, некоторые восприняли книгу как достойный образец современного искусства:
Было бы неверно относиться к книге только как к предмету коллекционирования для поклонников Robbo или, в более общем смысле, для поклонников Atari. Нам приходится иметь дело с редким случаем столкновения культуры видеоигр с литературой (в данном случае электронной), когда отправной точкой является «игра», а не «литература». Для некоторых это бессмысленное искусство ради искусства. Для других подобное скрещивание несёт совершенно новые возможности и опыт. Ничто не мешает вам создать версию Robbo, которую вы можете закончить с помощью «прохождения» из книги. Книга хорошо согласуется с моим взглядом на игры как на искусство. Искусство, в котором игрок может быть как воспринимающим, так и творящим — если во время «игры» присутствует «аудитория», наблюдающая за игроком, создающим свою собственную историю «игры». Содержание книги можно адаптировать для перформанса с игроком, проходящим Robbo, используя элементы «пошаговых инструкций» из книги. Чтобы не оставаться голословным: перформанс по мотивам «Robbo. Solucja» состоялся 11 мая 2018 года в галерее современного искусства «Бункер» в Кракове, во время презентации книги в рамках выставки «Неисчерпаемость».Перформанс в Кракове. Ради этого стоило написать компилятор.
Комментарии (87)
Anton23
19.01.2019 13:48А про вас что нибудь где нибудь написано?
Tereshkov Автор
19.01.2019 14:00Вы имеете в виду какие-то ещё публикации о моих упражнениях с компиляторами? Нет, сам не писал и чужих не встречал. Я не профессиональный программист, все упоминания меня в Гугле касаются совсем других предметов. В польской тусовке, о которой я пишу, ссылаются на мою разработку, но сама тусовка довольно закрытая (может быть, оттого, что там всё публикуется на польском).
nickavery
19.01.2019 15:48Не профессиональный программист, создающий компилятор? Восхитительно.
Tereshkov Автор
19.01.2019 15:54На самом деле, любительских проектов компиляторов довольно много. Но конечно, если речь идёт о высокой степени оптимизации кода, о полном соответствии стандарту языка и т.п., то нужен труд профессионалов. Всё согласно старому правилу: 80 % результата требуют 20 % усилий, оставшиеся 20 % результата — 80 % усилий.
rozhik
21.01.2019 01:44Компилятор не такая уж и сложная штука. На первом курсе(в 92) (не зная о BNC, lexx....) написал свой для игры война программ. Совершенно другая штука — это тонкости, то есть вполне нормально, когда реализация upvalue сложнее остального компилятора.
mistergrim
19.01.2019 15:51Модель памяти примерно соответствовала «малой» (если кто-то ещё помнит эту терминологию 16-битной эпохи): для кода, глобальных данных и стека выделялось по одному сегменту размером 64 кб.
Позанудствую: это tiny-model. «Малая» модель это 64 кб для кода отдельно, и для данных 64 кб отдельно.
Tereshkov Автор
19.01.2019 15:59Возражу. Именно так у меня и было: отдельные сегменты кода и данных (см. рис.). Потому я написал: «по одному сегменту», а не «один сегмент». Отличие от строгой «малой» модели в том, что у меня был ещё и отдельный сегмент стека, а эта модель обычно предполагала DS = SS.
pfemidi
19.01.2019 16:15+1Однако во внутренней процедуре нет адреса стекового кадра внешней процедуры — внутренняя процедура не знает, от чего отсчитывать адрес искомой переменной. Этот адрес приходится всякий раз передавать во внутреннюю процедуру через дополнительный скрытый параметр.
А как же неиспользуемая из-за её тормознутости (но однако тем не менее существующая) инструкция ENTER? Для этого в принципе и была создана.Tereshkov Автор
19.01.2019 22:27+1Точно, была такая! Но я по сути воспроизвёл то, что делал в таких случаях Turbo Pascal. Там ENTER тоже не использовалась.
pfemidi
19.01.2019 22:54+1Потому и не использовалась что выполнялась гораздо медленнее чем последовательность
push bp
mov bp,sp,
sub sp,local_size
или с сохранением ещё адресов предыдущих фреймов в зависимости от уровня вложенности. Вот в Turbo C 2.0 (или даже ещё в Turbo C 1.5, за давностью лет не помню) если в установках компилятора выставить процессор выше чем чем x86 использовалась. В Borland C++ 3.1 AFAIR эта инструкция уже не применялась, leave остался, а вот enter уже не использовался. А leave используют до сих пор. В принципе инструкции хорошие, годные, вот если бы они такое бешеное количество тактов не занимали по сравнению с последовательностью обычных команд, получилось бы вполне православно. Но как говорил Черномырдин: «Хотели как лучше, а вышло как всегда» :-)
Kemet
19.01.2019 16:58+2пусть взгляды Вирта уже устарели и утратили всякую связь с реалиями ИТ, а компиляторы делают совсем не так, как учил Вирт.
Серьёзнааа???? Да вроде ничего не изменилось. А взгляды Вирта вполне себе живут и здравствуют. Хотя, возможно, мы о разном. Так что там за взгляды, в чём они устарели, и почему они «утратили связь с реалиями ИТ»?true-grue
19.01.2019 17:04+1Очевидно, вот эти, из знаменитой статьи «A Plea for Lean Software»: cr.yp.to/bib/1995/wirth.pdf
JekaMas
19.01.2019 20:21-2Как гошник поддерживаю вопрос тоже!
Kemet
20.01.2019 09:17Это да, достаточно посмотреть GopherCon 2015: Robert Griesemer — The Evolution of Go( есть русские субтитры ), чтобы понять простые вещи.
Yuuri
20.01.2019 12:10Подход Go (да и оберона, наверное) – это простота, которая хуже воровства. Наличие только простых конструкций вынуждает для решения мало-мальски нетривиальных вещей писать огромные простыни кода, в которых каждая строчка, конечно, проста и понятна, а вот что они делают вместе...
pfemidi
20.01.2019 12:45Грубо говоря это как процессоры CISC которые умеют практически всё и RISC которые умеют только байты в памяти двигать и простыня инструкций RISC делает то, что на CISC выполняется за одну инструкцию. Но те же RISC процессоры ARM дешёвые и используются даже в мобильных телефонах, а AMD и Intel зато умеют за одну инструкцию выполнить шифрование Rijndael (AES-NI)
JekaMas
20.01.2019 13:05Как бы оценки тут не давались, просто сказал, что эти подходы живы.
Или "вы хотите поговорить об этом"?
Kemet
20.01.2019 13:33а что это за «сложные конструкции», которых тебе так не хватает для «решения мало-мальски нетривиальных задач»? С учетом, что и на Го и на Обероне пишут и операционные системы, и прикладные решения.
rogoz
20.01.2019 17:48Аргумент так себе.
На ассемблере пишут и операционные системы, и прикладные решения.
vvmtutby
20.01.2019 18:16Имеется в виду, что написание системного ПО на чистом Паскале 70-х проблематично без ассемблерных вставок. См. здесь же на чём написан, например Turbo Pascal.
Начиная с Modula ( т.е. ещё до Modula-2 на котором была написана AS/400, первоначально ) был взят курс на создание модуля SYSTEM с функциями ADDRESS(), SIZE() и т.п.
Как итог, на Алголах стало возможно программировать и ОС, и прикладное ПО.
Kemet
21.01.2019 06:17Во-первых, это не аргумент, а вопрос, во-вторых, да, пишут, ну так и в машкодах пишут. Другое дело, что это не целесообразно, и очень затратно, да и количество трудноуловимых ошибок возрастает на пару порядков. Но дело даже не в этом, в ассемблере отсутствуют «сложные конструкции», которых так не хватает Yuuri. Очевидно, что в Си ему тоже будет не хватать конструкций, потому что Оберон и Си находятся, примерно, на одном уровне. Однако, например, разработчикам Линукса там всего хватает. Может проблема, всё-таки, не в языке программирования?
math_coder
19.01.2019 20:54+3Вирт учил делать LL-компиляторы, а сейчас считается, что хороший компилятор должен быть LR — он генерирует более адекватные сообщения об ошибках. Не знаю точно, учил ли Вирт, что компилятор должен прекращать компиляцию после первой же ошибки, но скорее всего так и есть. Сейчас же, наоборот, общепризнано, что хороший компилятор должен уметь делать качественное восстановление после ошибки.
true-grue
20.01.2019 01:16+3Рекурсивный спуск используется не только у Вирта, но и в большинстве современных компиляторов. В том числе в Clang и в Rust. И одна из важнейших причин использования этого подхода — хорошая обработка ошибок.
По поводу восстановления после ошибок. Цитирую Compiler Construction Вирта, раздел «7.3. Coping with syntactic errors».
1. As many errors as possible must be detected in a single scan through the text.
2. As few additional assumptions as possible about the language are to be made.
3. Error handling features should not slow down the parser appreciably.
4. The parser program should not grow in size significantly
Kemet
20.01.2019 09:27Вирт не учил «делать LL-компиляторы», он учил решать задачи, выбирая наиболее эффективные, и в то же время, достаточно простые и обозримые, инструменты. И студенты, прошедшие «школу Вирта», сейчас более чем успешно работают в мейнстриме.
Что касается конкретного компилятора — то это простой однопроходной компилятор, написанный собственными «руками и мозгами». Он сознательно сделан таким — чтобы студенты могли понять и воспроизвести нечто подобное за отведенное время. В данном случае, смысла в использовании различных генераторов нет — там нечему учиться, «нажми на кнопку и получишь результат...». Описанное тобой относится именно к генераторам, вручную написанный парсер не имеет таких проблем.
Tereshkov Автор
19.01.2019 22:38+3Уточню, что я имел в виду: Вирт всегда был и остаётся сторонником экстремальной простоты. Сравните два пути развития Паскаля. Первый — по Вирту: Паскаль — Модула-2 — Оберон. Второй — по Borland: Паскаль — Турбо-Паскаль — Дельфи. Первый путь — путь упрощения, второй — путь усложнения. Индустрия однозначно предпочла второй путь, а Оберон так и остался маргинальным академическим проектом. Мне чрезвычайно симпатичны взгляды Вирта, но спрос на них сейчас крайне невелик. Видимо, его основной заслугой так и останется то, что в далёкие 70-е он придал верный импульс Алголу-60, создав Паскаль.
true-grue
20.01.2019 01:39+7Вирт, прежде всего, это ученый и учитель. В этом смысле не так важно, какой путь избрала индустрия. Можно критиковать тот же «Проект Оберон» за непрактичность и проч., и большая часть критики будет справедлива. Но, важное уточнение, ведь это учебный проект. И, как мне кажется, будет очень хорошо, если вчерашний студент придет в индустрию, имея в том числе, опыт работы на 1-2 курсе над чем-то подобным «проекту Оберон».
В целом ведь дело не в самодовлеющей простоте и минималистичности. Помните виртовский метод пошагового уточнения/улучшения программы? Это применимо и к языкам. Представьте себе язык программирования, стандарт на который с каждой версией становится все тоньше, все яснее. На каждой итерации выделяются более мощные, общие языковые механизмы, а все не нужное отсекается. В этом смысле Оберон хорош даже не как конкретный ЯП, а как идея подхода к разработке ЯП.
Виртовский учебник лично Вас научил технологии создания простых компиляторов. И не только Вас — эту небольшую книгу можно рекомендовать в качестве начального введения в предмет. Ничего более краткого и доходчивого, по большому счету, до сих пор не написали.
Kemet
20.01.2019 09:37+1Вирт просто затачивает инструмент под конкретное применение, отсекая лишнее. Это не экстремальная простота — это умение выделить главное и реализовать это максимально эффективно. Его работы нацелены на решение конкретной задачи и упрекать его за то что где-то нет фичи a, b, c..., совершенно бессмысленно — не нужны они там. Тот же Оберон — это ядро, над которым делаются различныен надстройки. В результате получаются другие инструменты.
Такой же точно подход применили разработчики языка Go. Та же самая простота. И не удивительно, одним и разработчиков был ученик, прошедший школу Вирта.JekaMas
20.01.2019 11:15+1Если не ошибусь, то даже не один, а несколько пересекались с Виртом. И его влияние в го точно чувствуется.
vvmtutby
20.01.2019 14:21Оберон так и остался… академическим проектом.
На нём разрабатывают промышленное ПО. Вы, скорее всего, ещё не успели прочитать статьи от Kemet?
Если не нравятся спорные моменты, как то, отсутствие беззнаковых целых, то давайте посмотрим на современные Modula-2 ( их разработчики, кстати, называют их Modula-2(Oberon-2), так как синтаксис объекто-ориентированного программирования в стиле Н.Вирта).
Давайте возьмём Modula-3 ( проект, кстати, «скорее жив чем мёртв», сегодня было многообещающее, в практическом плане, сообщение в списке рассылки).Kemet
20.01.2019 16:17Беззнаковые целые есть, как минимум, в Активном Обероне. Есть ещё дальнейшее развитие Активного Оберона — Active Cells. Предназначен для разработки на ПЛИС.
Оберон-технологии используются в различных промышленных системах, scada, медицинских приборах, дронах, управляющем по и тд.
В октябре 2018 в Орле прошел День Оберона. В теме есть ссылки на видео докладов, в том числе доклад Юрга Гуткнехта из ETHZ.
Так же полезно почитать Igor Schagaev · Thomas Kaegi-Trachsel. Software Design for Resilient Computer Systems, ISBN-978-3-319-29463-6vvmtutby
20.01.2019 16:51У Oberon много диалектов(?). Мне рассказывали про отсутствие беззнаковых, как о «фирменной особенности».
Если, как и цикл FOR, вернули в современные Oberon-ы, то я только «за»Kemet
21.01.2019 06:23В компиляторах от Вирта( да и во многих других реализациях ) беззнаковые не поддерживаются. Это тоже был сознательный отказ. Учитывая назначение языка/компилятора и время разработки, беззнаковые не шибко то и нужны были, даже для адресации памяти. А учитывая страсть отдельных индивидов смешивать в выражении знаковые и беззнаковые, что приводит к странным, для них, артефактам…
vvmtutby
20.01.2019 21:24основной заслугой (Н.Вирта) так и останется то, что в далёкие 70-е он придал верный импульс Алголу-60, создав Паскаль.
Я бы поставил на первое место Modula-2:
решение проблемы блоков BEGIN END в IF ( ELSIF), циклах;
приход Алголов в системное программирование и т.д.
Уточню, что я имел в виду: Вирт всегда был и остаётся сторонником экстремальной простоты. Сравните два пути развития Паскаля. Первый — по Вирту: Паскаль — Модула-2 — Оберон. Второй — по Borland: Паскаль — Турбо-Паскаль — Дельфи. Первый путь — путь упрощения, второй — путь усложнения. Индустрия однозначно предпочла второй путь
Во-первых сложно подсчитать объективно: «допинг» применяли обе стороны — Н.Вирт «выкидывал» цикл FOR и беззнаковые целые, его ученики-коммерсанты придумывали вместо RECORD с указателями на процедуры новые ключевое слово OBJECT
Во-вторых владельцы Delphi не смогли ( скорее, решили съэкономить) и просто лицензировали(?) разработки комады FPC для x64.
Т.е. путь усложнения имеет и отрицательные стороны.
Ну и финальный аккорд:
Во времена холодной войны ( с этапами оттепелей а-яля «Союз-Апполон») обе стороны
очень внимательно отслеживали состояние дел «по ту сторону окена».
Не только аэродинамику советских мини-челноков 60-70x, но и системы управления.
В частности, Э.Дейкстра ( если читать оригнал) говорил не о запрете BASIC в средних школах. Речь шла о Сибирском отделении Академии Наук СССР.
Теперь внимание: Н.Вирт был зван и тепло принят в Новосибирске.
Его ученик бизнесмен-саксофонист «срубивший бабла» и ушедший на пенсион раньше своего технологичекского гуру — я как-то сомневаюсь
Не став развивать Borland Modula-2 ( был для CP/M) и предоставив бороться не компиляторам, а благим пожеланиям от MISRA, с «парными фигурными скобочками»
выше упомянутый бизнесмен de-facto соучастник Тойота скандала с анти-тормозами в легковых автомобилях.
ianzag
19.01.2019 18:29> Из более современных особенностей в моём XD Pascal появились позаимствованные из Delphi однострочные комментарии (//) и автопеременная Result.
уже почти 20ть лет прошло, а я до сих пор часто использую именование result :)
vvmtutby
19.01.2019 19:07В тот день, когда я перешёл с 32-битной Windows XP на 64-битную Windows 7 без виртуальной машины DOS, я мысленно похоронил свой проект.
Реинкарнируйте в DosBOX
Однако настоящая трудность, специфичная для Паскаля, подстерегала совсем в другом месте — в работе с вложенными процедурами. Может возникнуть совершенно невинная надобность обратиться к локальной переменной внешней процедуры из внутренней. Однако во внутренней процедуре нет адреса стекового кадра внешней процедуры — внутренняя процедура не знает, от чего отсчитывать адрес искомой переменной. Этот адрес приходится всякий раз передавать во внутреннюю процедуру через дополнительный скрытый параметр. Подозреваю, что именно это осложнение заставило разработчиков C вовсе отказаться от вложения функций. Однако в Паскале они есть, и с этим приходится считаться.
Вот что получается: Н.Вирт ( и Вы) смогли осилить, а те кто якобы не «утратили всякую связь с реалиями ИТ» — как в анекдоте N13 «не смогли, или не захотели»
А потом «почему-то» новейшие автомобили при нажатии на педаль тормоза...
P.S. см. Глава 5. Компиляторы
в книге
Л. Бек Введение в системное программирование
Заголовок спойлераSystem Software
An introduction to systems programming
Leland L. Beck
San Diego State University
Addison-Wesley Publishing Company Reading, Massachusetts Menlo Park, California Don Mills, Ontario Wokingham, England Amsterdam Sydney Singapore Tokyo Mexico City Bogota Santiago San Juan
Л. Бек
Введение в системное программирование
Перевод с английского Н.А. Богомолова, В.М. Вязовского и С.Е. Морковина под редакцией Л.Н. Королева
Москва «Мир» 1988
ББК 32.973
Б42
УДК 681.142
Бек Л. Введение в системное программирование: Перевод с английского. — М.: Мир, 1988. — 448 с., ил.
ISBN 5-03-000011-9
Монография учебного характера, написанная американским специалистом. В ней изложены все основные компоненты системного программного обеспечения. Особое внимание уделено их взаимосвязи с архитектурой вычислительных комплексов. Конкретные реализации компонентов обсуждаются на примере трех современных вычислительных систем: IBM/370, VAX, CYBER.
Для системных программистов, аспирантов, студентов вузов.
ББК 32.973
КРАТКОЕ ОГЛАВЛЕНИЕ:
От редактора перевода (5).
Предисловие (7).
Глава 1. Основные понятия (11).
Глава 2. Ассемблеры (38).
Глава 3. Загрузчики и программы связывания (122).
Глава 4. Макропроцессоры (178).
Глава 5. Компиляторы (222).
Глава 6. Операционные системы (312).
Глава 7. Другие компоненты системного программного обеспечения (399).
Приложения (430).
Литература (437).
Предметный указатель (440).
Редакция литературы по математическим наукам
Учебное издание
Леланд Л. Бек
ВВЕДЕНИЕ В СИСТЕМНОЕ ПРОГРАММИРОВАНИЕFForth
19.01.2019 19:55Тема обсуждения D2lang языка сделанного на идеях разных языков
forum.sources.ru/index.php?showtopic=8810
P.S. Больше всего выглядит как Паскаль, но внутреннее построение оригинальное.
Tereshkov Автор
19.01.2019 23:01Реинкарнируйте в DosBOX
Именно это я и сделал ради скриншотов для поста. Однако запуск в DOSBox всегда оставляет ощущение искусственности происходящего.
Вот что получается: Н.Вирт ( и Вы) смогли осилить, а те кто якобы не «утратили всякую связь с реалиями ИТ» — как в анекдоте N13 «не смогли, или не захотели»
Насколько я знаю, для вложения процедур у Вирта была и вполне прагматическая причина — сведение косвенной рекурсии к прямой. Опережающих описаний в оригинальном Паскале не было. Если они в языке есть, то вложенные процедуры не слишком нужны. Да и, откровенно говоря, они не самый лучший способ структурирования кода.vvmtutby
20.01.2019 17:12для вложения процедур у Вирта была и вполне прагматическая причина — сведение косвенной рекурсии к прямой
Охотно допускаю ( хотя и верится с трудом — уже на 1989 опережающие описания процедур были «всегда» т.е. в «древних» 70-х «уже были») что ради рекурсии.
Рекурсия — фирменная «фишка» Алголов и предмет законной гордости европейской школы.
В американских компиляторах той поры просто не было стека ( вообще).
Не было простой реентерабельности, т.к. было принято менять код программы прямо на ходу. Причём не для чего либо экзотического типа ИИ, а в совершенно тривиальных конструкциях.
( Перечитываю переводную классику издательства «Мир» )
vvmtutby
20.01.2019 18:30вложенные процедуры не слишком нужны. Да и, откровенно говоря, они не самый лучший способ структурирования кода.
Есть и другая точка зрения: как ни странно, именно вложенные процедуры считают способом построения иерархической структуры программы. И наоборот, модули обеспечивают только плоскую структуру. Самое удивительное, что это преподносилось, как один из немногих плюсов наследников Pascal. Ещё более удивительно, что автор этого построения занимается «не Паскалем».
vvmtutby
20.01.2019 18:45вложенные процедуры не слишком нужны.
Как известно, практика критерий истины.
Буквально на днях видел вложенные процедуры в исходном коде, если не самого компилятора Modula-3, то в коде стандартной библиотеки.
Выглядело органично даже в 20-тистрочной подпрограмме.
Настолько же естественным путём вложенные процедуры потребуются при доказательном программировании ( см. ADA SPARK, Frama-C) из практических соображений, так как выход из середины циклов становится недопустим.
vvmtutby
20.01.2019 19:21Однако настоящая трудность, специфичная для Паскаля, подстерегала совсем в другом месте — в работе с вложенными процедурами.
Кстати, в Clarion изящно обошли Вашу проблему с необходимостью стека фреймов(?), работы с ним с помощью регистра BX(?) и т.п. Просто вложенные процедуры сделаны без параметров и без собственных локальных переменных.
А уж во чтобы превратилась структура программы без этих routines я просто боюсь представить: их штук 20-40 в темплайте для генерации исходного кода для процедур отображения на экране файла базы данных в виде таблицы и в другом template для построения reports их не меньше.
Дело в мультипликации: файлов БД при реляционной схеме даже для относительно простого ПО требуется несколько десятков, для каждого файла нужны минимум по одной процедуре указанных выше темплейтов ( а обычно не одной, а несколько) и ещё по одной процедуре основанной на темплайте Forms.
Kemet
21.01.2019 06:28Назначение вложенных процедур( они, так же, называются локальные — инкапсуляция.
third112
19.01.2019 22:33+1Сперва родился простейший компилятор PL/0, а из него постепенно вырос почти полнофункциональный компилятор Паскаля для MS-DOS.
У Вирта в «Algorithms + Data Structures = Programs» (по Вашей ссылке на Вики) приведен листинг интерпретатора PL/0. Вашу фразу понимать, что на основе этого листинга Вы сделали компилятор PL/0? И потом Вы сделали из него компилятор Паскаля? Если так, то ИМХО это не лучший путь. У Вирта есть публикации его трансляторов Паскаля. Нпр, PascalS (о котором недавно упоминал). А еще лучше ИМХО взять полноценный, нпр., Pascal P5 — я так сделал для специализированного скриптового языка игрового бота (написал к интерпретатору IDE). ИМХО не надо изобретать велосипеды, а свою энергию употребить на доработку, расширение, генерацию и оптимизацию кода. Такая работа позволит полностью прочувствовать транслятор изнутри, но не по собственному переделанному коду, а по сделанному хорошими спецами. И стоило использовать ассемблер:
Машинный код генерировался напрямую, без помощи внешнего ассемблера или компоновщика.
— Время на отладке сохранить и exe вместо com получить на выходе.
Все выше сказано не для умаления работы, а для читателя, который может захотеть сделать что-то подобное — пусть знает, что м.б. и другой путь. Спасибо за статью. Успехов!
PS yacc подходит для создания модели при испытании нового ЯП, его демонстрации, а хороший код на нем сделать проблематично.pfemidi
19.01.2019 23:06+1Виталий Мирянов в своё время написал полный аналог Turbo Pascal под названием Virtual Pascal именно на ассемблере. Но изначально для OS/2. Потому что для DOS Turbo Pascal был, для Windows Turbo Pascal был, а для OS/2 не было, вот он и сделал.
Tereshkov Автор
19.01.2019 23:35+2Был ещё замечательный проект TPC16 — полный клон Turbo Pascal, написанный на самом Turbo Pascal. Правда, если мне не изменяет память, автор хотел немалые деньги за исходники. Теперь следы этого проекта как-то затерялись.
third112
19.01.2019 23:52Забавно! А в Борланд он не предлагал? Чем клон был лучше прототипа?
Tereshkov Автор
19.01.2019 23:59А в Борланд он не предлагал?
Дело было уже в 2000-е, Borland не занимался Турбо-Паскалем.
Чем клон был лучше прототипа?
Видимо, как раз наличием удобочитаемых исходников. Настоящий Турбо-Паскаль был на ассемблере (не уверен насчёт 7-й версии, но 3-я точно).third112
20.01.2019 00:04Дело было уже в 2000-е
А какую версию клонировал? Неужели 3-ю?Tereshkov Автор
20.01.2019 00:10Нет, 7-ю.
third112
20.01.2019 00:33Про эту версию Вы сказали:
не уверен насчёт 7-й версии
Т.о. м.б. она уже была на Паскале (м.б. на С или С++ :) Но в любом случае — Внушает! Автору бы сейчас выложить свой исх.код на sourceforge.net, нпр. Денег никто не даст, но PR возможен.
PS И на Хабре статью про этот клон было бы интересно почитать :)Tereshkov Автор
20.01.2019 00:43Вот только что коллега pfemidi подтвердил, что и 7-я была на ассемблере.
pfemidi
20.01.2019 12:00Решил вспомнить былое, достал свои дискеты 5.25" с дистрибутивом Turbo Pascal 7.0 (у меня ещё и дистрибутив Borland C++ 3.1 имеется, тоже официально купленный в своё время и тоже, увы, на дискетах 3.5", но о каких CD в то время речи не было, а флешек вообще не существовало в природе), посмотрел на них грустно — читать их мне давно уже не на чем, нет у меня дисководов и скачал дистрибутив Turbo Pascal 7.0 из интернета. Загрузил в IDA сначала tpc.exe. Тут (и если смотреть далее) невооружённым взглядом видно что это именно ассемблер, ни один компилятор такой код не сделает, это явно творение рук человеческих:
После загрузил в IDA turbo.exe. Тут уже не чистый ассемблер:
Правда если дальше углубиться/посмотреть то становиться ясно что тут больше не ассемблерные вставки в HLL на Паскале, а паскальные вставки в программу на ассемблере. IDA даже честно нашла стандартные функции из RTL всё того же Turbo Pascal. Как я и предполагал сам компиляторный движок такой же как в tpc.exe, отладчик на ассемблере, а на Паскале написан только UI. Вот что говорит по этому поводу википедия:
Начиная с 6-й версии в поставку TP/BP включалась объектная библиотека Turbo Vision, представляющая собой полноценную инфраструктуру (англ. framework) для создания оконных приложений, работающих в текстовом режиме. В частности, интерфейс самой среды разработки TP/BP был реализован средствами этой библиотеки.
Похоже что сначала был написан на ассемблере строчный компилятор tpc.exe, а после был написан уже turbo.exe, который был скомпилирован уже при помощи имеющегося tpc.exe ну tasm.exe само собой :-)
pfemidi
20.01.2019 00:24+3Строчный компилятор tpc.exe точно был на ассемблере, а вот IDE turbo.exe уже на самом паскале, во всяком случае весь UI в нём был на основе Turbo Vision из этого самого паскаля. Хотя backend занимающийся не междумордием, а именно компиляцией, вполне мог быть и тот же, который был в tpc.exe, то есть ассемблерный. Не знаю, turbo.exe я не смотрел, но внутри tpc.exe в своё время покопался. Привлекло именно то, что не использовались никакие yacc или bison, всё чистый ассемблер. Поэтому [бинарный] код читался лёгко и непринуждённо.
FForth
21.01.2019 04:15Virtual Pascal устанавливается и работает и в Win10.
Скомпилировал пару демо программ для Win32 входящих в его примеры, одна из них с OpenGL (всё бодренько и FPS ~174 в примере)
P.S. Взял Virtual Pascal здесь old-dos.ru/index.php?page=files&mode=files&do=show&id=1436pfemidi
21.01.2019 08:26Изначально Virttual Pascal делался для OS/2, уже позже он был портирован для Windows. Я знаю, я с Миряновым переписывался ещё в то время когда он в Киеве жил и в Британию для работы на fPrint UK Ltd не уехал.
Tereshkov Автор
19.01.2019 23:27Вашу фразу понимать, что на основе этого листинга Вы сделали компилятор PL/0? И потом Вы сделали из него компилятор Паскаля? Если так, то ИМХО это не лучший путь. У Вирта есть публикации его трансляторов Паскаля. Нпр, PascalS (о котором недавно упоминал).
Листинга я тогда не видел, а видел только грамматику в Википедии. На её основе и писал компилятор с чистого листа. На полноценный Паскаль не замахивался, поскольку в глубине души считал серьёзный компилятор неподъёмной для себя задачей. Когда удался PL/0 — возросли и мои аппетиты: добавил указатели, затем массивы, затем функции, затем действительные числа с фиксированной точкой, которую заменил на плавающую, и т.д. Так и вырос Паскаль. Эталонной грамматикой на этом этапе служила именно грамматика Pascal-S.third112
19.01.2019 23:45Листинга я тогда не видел, а видел только грамматику в Википедии
Интересно: почему? Разве эта книга Вирта редкая? (Там не только листинг, но целая глава про него). М.б. посмотреть в книгу казалось не спортивным? Всё самому сделать? ;)Tereshkov Автор
19.01.2019 23:52Именно спортивный интерес :)
third112
19.01.2019 23:56Ok :) Дело Ваше, но ИМХО вредный пример для начинающих — студентов (и не только в IT) прежде, чем делать курсовую, учат собирать литературу. Часто курсовую требуют начинать с лит.обзора.
Tereshkov Автор
20.01.2019 00:09+1Согласен. Но когда речь идёт о такой разработанной области, как компиляторы, можно найти что угодно и в любой степени готовности: хоть грамматику, хоть листинг, хоть генератор фронтенда/бэкенда, хоть готовый компилятор со всеми исходниками и тестами. Так что где-то в заимствовании нужно остановиться. Челлендж для меня был именно в том, чтобы сделать максимально самостоятельно. Правда, без готовой грамматики я обойтись не мог: я попросту не знал, что бывают такие грамматики! И именно когда увидел EBNF для PL/0, поразился: это же так просто! Все мои муки с вложением операторов, порядком действий в выражениях мгновенно разрешились.
third112
20.01.2019 00:53Ok, но сейчас можете сравнить свой код с книгой? Интересно: какой будет результат сравнения? ;)
Tereshkov Автор
20.01.2019 01:29Хоть я плохо помню свой код компилятора PL/0, но, конечно, концептуально синтаксический анализатор был похож на то, что я вижу в книге (с тем отличием, что в книге косвенная рекурсия сведена к прямой).
DmLam
19.01.2019 23:03Хе. А я думал, я один такой :) Тоже лет 20 назад стал писать компилятор паскаля (да, LL-конечно :) в качестве pet-project. Только на Delphi и под Windows. Потом забросил, потом снова пописАл, забросил. Периодически вспоминал, чего-нибудь дописывал :) Но библиотеки было писать лень, потому что это не так интересно и RTL ничтоже сумняшеся взял из Delphi во многом :) В итоге он содержит большую часть языка Delphi 2007, но ввод вывод только консоль (можно и оконные приложения писать, но на чистом API). Модули, классы, варианты, вариантные записи и методы записей, встроенный ассемблер. With и goto тоже реализовал :) Есть даже IDE с подсветкой синтаксиса и отладчиком как в Delphi (только более глючным). Сам себя компилирует и более того, результат компиляции тоже сам себя компилирует и все тесты проходит :) Но нигде не выкладывал, ибо библиотеки в общем-то украденные :)
Tereshkov Автор
19.01.2019 23:13Мои мечты о компиляторе для Windows тоже натолкнулись на мороку с написанием библиотек. А компоновщик у вас был внешний? Или вы, как я и BeRo, сразу генерировали машинный код вместе со всеми заголовками исполняемого файла?
DmLam
20.01.2019 09:00Да, я сделал кодогенератор и сразу получал исполняемый модуль — exe или dll. Вообще-то, справедливости ради, я не с нуля начал — натолкнулся случайно на вот этот проект other.jrsoftware.org/ip и стало интересно доработать. Там был уже сделан внутренний компоновщик (поэтому изучение структуры PE-файла можно было отложить :) и совсем простенький отладчик, который, тем не менее, позволял пройти программу пошагово и из которого было понятно как устроены отладчики под Windows. Но в языке не было почти ничего еще, код генерировался по мере разбора сразу командами, никакого промежуточного представления — с кодогенератора тогда и начал.
barbaris76
19.01.2019 23:53-1Наверное, это тупой комментарий, но при виде фразы «современное польское искусство» сразу вспоминается незабвенное курва, я пьердоле ))
MacIn
20.01.2019 00:54Интересно почитать про генератор кода. Распределение регистров, внутреннее представление и пр.
Tereshkov Автор
20.01.2019 01:01Должен вас разочаровать: генератор максимально простой. Регистровых переменных нет вовсе, кроме неявных счётчиков при присвоении записей и т.п. Промежуточного представления кода тоже нет. Единственный вид оптимизации — удаление невызываемых процедур, если разрешена двухпроходная компиляция.
litwr2
20.01.2019 18:34Вспомнилась история, близкая к теме. Будучи студентом ВМК МГУ подрабатывал в 1990 в ЦНТТМ Университет и там встретился с молодым человеком, который с его слов сделал портирование турбо-паскаля для MS-DOS версии 4.0 на отечественный компьютер Корвет на базе процессора Intel 8080. Работа по моим представлениям более чем колоссальная. И он хотел за свою работу некоторый гонорар, в чём, подозреваю, не преуспел. К сожалению, похоже эта работа так нигде до сих пор и не представлена. :(
LorHobbit
20.01.2019 19:39Спасибо, интересно! Особенно история с локальными процедурами — сегодня многие вообще не подозревают про такую фичу. А мне, когда я много лет назад переползал с объектного паскаля на С++, их очень не хватало. Иногда даже приходилось вместо замены оных целый класс создавать.
Немного странно, что в комментариях не вспомнили fpc — самый, вероятно, на сегодня актуальный компилятор паскаля, к тому же с открытыми исходниками. Да, он как раз из другого направления, из тех, что развивались больше «в сторону усложнения», с оглядкой на Delphi и др.
Автор, Вы не делали попыток посмотреть, что и как сделано в fpc и сравнить со своим проектом?Tereshkov Автор
20.01.2019 22:30Увы, не смотрел. Когда начинал свой проект, FPC был уже слишком огромен и сложен. Я бы не рискнул сравнивать свой проект с ним.
sshikov
>яков, бизонов и всех их преемников.
Вот зря вы их всех в одну кучу. Разница между этими двумя, и условным ANTLR — огромная. Примерно такая же, как между вашим способом написать рекурсивный спуск вручную, и самим yacc.
Tereshkov Автор
Спасибо. С ANTLR я не работал. Но если я правильно вас понял, то он ещё сильнее отдаляет от понимания внутренностей компилятора. И тогда для новичка тайное останется тайным.
Cobolorum
ANTLR не отдаляет, а заставляет придерживаться формального похода. Реализуя свой язык под ANTLR находишь ошибки в самой постановки техзадания для своего языка. Или находить ошибки в легаси коде.
Но в общем ANTLR позволяет сосредоточиться именн на сути своего языка, а не размениваться на мелочи.
MooNDeaR
Не ведь самостоятельное написание компилятора, прежде всего, это радость от мелочей) Ты ж пишешь для себя. Пишешь компилятор, чтобы написать компилятор, а не ради того, чтобы им кто-то пользовался)