Текст книги "Давайте создадим компилятор!"

Деление

Случай с делением совсем не так симметричен. У меня также есть для вас некоторые плохие новости:

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

Они вам лгут!!!

Если вы не верите в это, попробуйте разделить любое большое 32-разрядное число (это означает, что оно имеет ненулевые биты в старших 16 разрядах) на целое число 1. Вы гарантированно получите исключение переполнения.

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

С начала времен (ну во всяком случае компьютерных) архитекторы ЦПУ предусматривали этот маленький подводный камень в схеме деления. Это обеспечивает некоторую симметрию, так как это своего рода инверсия способа каким работает умножение. Но так как единица – это совершенно допустимое (и довольно частое) число для использования в качестве делителя, делению, реализованному аппаратно, требуется некоторая помощь от программистов.

Подразумевает следующее:

Тип частного всегда должен быть того же самого типа, что и делимое. Он независим от делителя.

Несмотря на то, что ЦПУ поддерживает деление длинного слова, аппаратно предоставленной инструкции можно доверить только делимые байт и слово. Для делимых типа длинное слово нам необходима другая библиотечная подпрограмма, которая может возвращать длинный результат.

Это похоже на работу для другой таблицы, для суммирования требуемых действий:

T1

T2 B W L

B Преобразовать D0 в W

Преобразовать D7 в L

DIVS

Result = B Преобразовать D0 в W

Преобразовать D7 в L

DIVS

Result = W Преобразовать D0 в L

JSR DIV32

Result = L

W Преобразовать D7 в L

DIVS

Result = B Преобразовать D7 в L

DIVS

Result = W Преобразовать D0 в L

JSR DIV32

Result = L

L Преобразовать D7 в L

JSR DIV32

Result = B Преобразовать D7 в L

JSR DIV32

Result = W JSR DIV32

Result = L

(Вы можете задаться вопросом, почему необходимо выполнять 32-разрядное деление, когда делимое, скажем, всего лишь байт. Так как число битов в результате может быть только столько, сколько и в делимом, зачем беспокоиться? Причина в том, что если делитель – длинное слово и в нем есть какие-либо установленные старшие разряды, результат деления должен быть равен нулю. Мы не смогли бы получить его, если мы используем только младшее слово делителя)

Следующий код предоставляет корректную функцию для PopDiv:

{–}

{ Generate Code to Divide Stack by the Primary }

function PopDiv(T1, T2: char): char;

begin

Pop(T1);

Convert(T1, 'L', 'D7');

if (T1 = 'L') or (T2 = 'L') then begin

Convert(T2, 'L', 'D0');

GenLongDiv;

PopDiv := 'L';

end

else begin

Convert(T2, 'W', 'D0');

GenDiv;

PopDiv := T1;

end;

end;

{–}

Две подпрограммы генерации кода:

{–}

{ Divide Top of Stack by Primary (Word) }

procedure GenDiv;

begin

EmitLn('DIVS D0,D7');

Move('W', 'D7', 'D0');

end;

{–}

{ Divide Top of Stack by Primary (Long) }

procedure GenLongDiv;

begin

EmitLn('JSR DIV32');

end;

{–}

Обратите внимание, мы предполагаем, что DIV32 оставляет результат (длинное слово) в D0.

ОК, установите новые процедуры деления. Сейчас у вас должна быть возможность генерировать код для любого вида арифметических выражений. Погоняйте ее!

Завершение

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

Основная идея, которая облегчила нам жизнь, – идея преобразования процедур типа Expression в функции, возвращающие тип результата. Как только это было сделано, мы смогли сохранить ту же самую общую структуру компилятора.

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

Я так же игнорировал логические операторы And, Or и т.д. Оказывается, их довольно легко обрабатывать. Все логические операторы – побитовые операции, так что они симметричны и, следовательно, работают в том же самом режиме, что и PopAdd. Однако, имеется одно отличие: если необходимо расширить длину слова для логической переменной, расширение должно быть сделано как число без знака. Числа с плавающей точкой, снова, являются простыми для обработки… просто еще несколько процедур, которые будут добавлены в run-time библиотеку или, возможно, инструкции для математического сопроцессора.

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

Снова, в действительности в этом случае нет никаких новых проблем для рассмотрения. Мы уже проверяем типы двух операндов… в основном эти проверки выполняются в процедурах типа SameType. Довольно просто включить вызов обработчика ошибок если типы двух операндов несовместимы.

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

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

Приводить или не приводить

В случае, если до вас еще не дошло, уверен дойдет, что TINY и KISS возможно не будут строго типизированными языками, так как я разрешил автоматическое смешивание и преобразование почти любых типов. Что поднимает следующий вопрос:

Это действительно то, что мы хотим сделать?

Ответ зависит от того, какого рода язык вам нужен и как вы хотели чтобы он себя вел. Мы не обращались к проблеме того, когда разрешить или когда запретить использование операций, включающих различные типы данных. Другими словами, какова должна быть семантика нашего компилятора? Хотим ли мы выполнять автоматическое преобразование типов для всех случаев, в некоторых случаях или не выполнять совсем?

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

Fortran II поддерживал только два простых типа данных: Integer и Real. Он разрешал неявное преобразование типов между real и integer типами во время присваивания, но не в выражениях. Все элементы данных (включая литеральные константы) справа оператора присваивания должны были быть одинакового типа. Это довольно сильно облегчало дела… гораздо проще, чем то, что мы делали здесь.

Это было изменено в Fortran IV для поддержки «смешанной» арифметики. Если выражение имело любые real элементы, все они преобразовывались в real и само выражение было real. Для полноты, предоставлялись функции для явного преобразования из одного типа в другой, чтобы вы могли привести выражение в любой тип.

Это вело к двум вещам: код, который был проще для написания и код, который был менее эффективен. Из-за это неаккуратные программисты должны были писать выражения с простыми константами типа 0 и 1, которые компилятор должен был покорно компилировать для преобразования во время выполнения. Однако, система работала довольно хорошо, что показывало что неявное преобразование типов – Хорошая Вещъ.

Си – также слабо типизированный язык, хотя он поддерживает большее количество типов. C не будет жаловаться, если вы например попытаетесь прибавить символ к целому числу. Частично, в этом помогает соглашение Си о переводе каждого символа в число когда оно загружается или передается в списке параметров. Это совсем немного упрощает преобразование. Фактически, в подмножестве компиляторов Си, которые не поддерживают длинные или с плавающей точкой числа мы возвращаемся к нашей первой нехитрой попытке: каждая переменная получает одинаковое представление как только загружается в регистр. Жизнь становится значительно проще!

Предельным языком в направлении автоматического преобразования типов является PL/I. Этот язык поддерживает большое количество типов данных, и вы можете свободно смешивать их все. Если неявное преобразование Fortran казалось хорошим, то таковое в PL/I было бы Небесами, но оно скорее оказалось Адом! Проблема состояла в том, что с таким большим количеством типов данных должно сущестовать большое количество различных преобразований и, соответственно, большое количество правил того, как смешиваемые операнды должны преобразовываться. Эти правила стали настолько сложными, что никто не мог запомнить какие они! Множество ошибок в программах на PL/I имели отношение к непредвиденным и нежелательным преобразованиям типов. Слишком хорошо тоже нехорошо!

Паскаль, с другой стороны, является языком, который «строго типизирован», что означает, что вы вообще не можете смешивать типы даже если они отличаются только именем, хотя они и имеют тот же самый базовый тип! Никлаус Вирт сделал Паскаль строго типизированным чтобы помочь программисту избежать проблем и эти ограничения действительно защитили многих программистов от самих себя, потому что компилятор предохранял его от глупых ошибок. Лучше находить ошибки при компиляции, чем на этапе отладки. Те же самые ограничения могут также вызвать расстройства когда вам действительно нужно смешивать типы и они заставляют бывших C-программистов лезть на стену.

Даже в этом случае, Паскаль разрешает некоторые неявные преобразования. Вы можете присвоить целое значение вещественному. Вы можете также смешивать целые и вещественные типы в выражениях типа Real. Целые числа будут автоматически приведены к вещественным, как и в Fortran. (и с теми же самыми скрытыми накладными расходами во время выполнения).

Вы не можете, однако, преобразовывать наоборот из вещественного в целое без применения явной функции преобразования Trunc. Теория здесь в том, что так как числовое значение вещественного числа обязательно будет изменено при преобразованиии (дробная часть будет потеряна), это не должно быть сделано в «секрете» от вас.

В духе строгого контроля типов Паскаль не позволит вам смешивать Char и Integer переменные без применения явных функций приведения Chr и Ord.

Turbo Pascal также включает типы Byte, Word и LongInt. Первые два в основном то же самое, что и беззнаковое целое. В Turbo они могут быть свободно смешаны с переменными типа Integer и Turbo автоматически выполнит преобразование. Однако существуют проверки времени выполнения, предохряняющие вас от переполнения или иного способа получения неправильного ответа. Заметьте, что вы все еще не можете смешивать типы Byte и Char, даже при том, что они имеют то же самое внутреннее представление.

Пределом среди строго типизированных языков является Ada, который не рязрешает никаких невных преобразований типов вообще, и также не разрешает смешанную арифметику. Позиция Jean Ichbiah в том, что преобразования стоят времени выполнения и вам нельзя позволить платить такую цену на скрытый манер. Вынуждая программиста явно запрашивать преобразование типов вы делаете более очевидным то, что здесь могут быть вовлечены затраты.

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

Такой подход имеет некоторые преимущества: компилятор никогда не должен предполагать, что делать: программист всегда говорит ему точно, что он хочет. В результате, появляется почти однозначное соответствие между исходным кодом и компилированным кодом, и компилятор Джона производил очень компактный код.

С другой стороны, я иногда находил явные преобразования болезненными. Если я хочу, например, прибавить единицу к символу, или сложить ее с маской, необходимо выполнить массу преобразований. Если я сделаю это неправильно единственным сообщением об ошибке будет «Типы не совместимы». Как это случается, специфическая реализация Джоном этого языка в его компиляторе не сообщает вам точно, какие типы несовместимы… он только сообщает вам, в какой строке произошла ошибка.

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

Так что мы должны сделать в TINY и KISS? Для первого я имею ответ: TINY будет поддерживать только типы Char и Integer и мы будем использовать прием C непосредственно переводя Char в Integer. Это означает, что компилятор TINY будет значительно проще, чем то, что мы уже сделали. Необходимость преобразования типов в выражении спорна, так как ни одно из них не требуется! Так как длинное слово не будет поддерживаться, нам также будут не нужны подпрограммы MUL32 и DIV32, ни логики для выяснения когда их вызывать. Мне это нравится!

KISS, с другой стороны будет поддерживать тип Long.

Должен ли он поддерживать и знаковую и беззнаковую арифметику? Ради простоты я предпочел бы нет. Это добавляет совсем немного сложности в преобразования типов. Даже Никлаус Вирт удалили беззнаковые числа (Cardinal) из его нового языка Оберон, с тем аргументом, что 32-разрядного целого числа в любом случае должно быть достаточно всем.

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

Заключение

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

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

Увидимся.

Назад в будущее

Введение

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

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

Новое начало, старое направление

Подобно многим другим вещам, языки программирования и стили програмирования изменяются со временем. В 1994 году кажется немного анахроничным программировать на Turbo Pascal, когда остальной мир кажется сходит с ума по C++. Также кажется немного странным программировать в классическом стиле, когда остальной мир переключился на объектно-ориентированные методы. Однако, несмотря на четырехлетнюю паузу, было бы слишком тяжело сейчас переключиться, скажем, на C++ с объектной ориентацией. Во всяком случае, Pascal все еще не только мощный язык программирования (фактически больше, чем когда либо), но это и замечательная среда для обучения. Си – известно трудный для чтения язык… он часто был обвиняем, наряду с Forth, как «язык только для записи». Когда я программирую на C++ я трачу по крайней мере 50% своего времени на борьбу с синтаксисом языка а не с концепциями. Сбивающие с толку «&» или "*" могут не только изменить функционирование программы, но также и ее правильность. Наоборот, код Паскаля обычно совершенно ясен и прост для чтения даже если вы не знаете языка. Что вы видите, то вы почти всегда и получите, и мы можем сконцентрироваться на концепциях, а не тонкостях реализации. Я сказал в начале, что целью этой обучающей серии была не генерация самого быстрого в мире компилятора, а изучение основ технологии компиляции, с наименьшими затратами времени на борьбу с синтаксисом языка или другими аспектами реализации программного обеспечения. Наконец, так как многое из того, что мы делаем в этом курсе, составляет программное экспериментирование, важно иметь компилятор и связанную с ним среду, который компилирует быстро и без суеты. По моему мнению наиболее значимым мерилом времени при разработке программного обеспечения является скорость цикла редактирование/компиляция/тестирование. В этом отделе Turbo Pascal – король. Скорость компиляции блестяще быстрая, и продолжает становиться быстрее с каждым выпуском (как им это удается?). Несмотря на крупные усовершенствования в быстродействии компиляции C за последние годы, даже Borland-овский самый быстрый компилятор C/C++ все еще не сравним с Turbo Pascal. Далее, редактор, встроенный в его IDE, средство make, и даже их превосходный умный компоновщик, все дополняют друг друга чтобы получить замечательную среду для быстрой разработки. По всем этим причинам, я собираюсь придерживаться Паскаля в продолжении этой серии. Мы будем использовать Turbo Pascal for Windows, один из компиляторов, предоставляемый Borland Pascal with Objects, версия 7.0. Если у вас нет этого компилятора не волнуйтесь… ничего из того, что мы делаем здесь не будет рассчитано на то, что вы имеете последнюю версию. Использование Windows версии сильно помогает мне, позволяя использовать Clipboard для копирования кода из редактора компилятора в эти документы. Она также должна помочь вам по крайней мере копировать код в обратном направлении.

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

Так что теперь, по крайней мере, я определился продолжать классический стиль в Pascal, хотя мы действительно могли бы обсуждать объекты и объектную ориентацию по ходу дела. Аналогично, целевой машиной останется семейство Motorola 68000. Из всех решений, которые буду приняты здесь, это было самым простым. Хотя я знаю, что многие из вас хотели бы видеть код для 80x86, 68000 является, вообще-то, даже более популярным как платформа для встроенных систем, и это то применение ради которого это все изначально и начиналось. Компилируя для PC, платформы MSDOS, мы должны были бы иметь дело со всеми проблемами системных вызовов DOS, форматов компоновщика DOS, файловой системы PC и аппаратными средствами и всеми другие осложнениями среды DOS. Встроенная система, с другой стороны, должна выполняться автономно и я всегда представлял, что для такого вида применений, как альтернатива ассемблеру, язык подобный KISS процветал бы. В любом случае, кто хочет иметь дело с архитектурой 80x86 если они не должны?

Одна из возможностей Turbo Pascal которую я собираюсь серьезно использовать это модули. В прошлом мы должны были делать компромиссы между размером кода, сложностью и функциональными возможностями программы. Многое из нашей работы было по природе компьютерным экспериментированием, рассматриванием только одного аспекта технологии компиляции в один момент времени. Мы делали это чтобы избежать возни с большими программами, исследуя только простые понятия. В процессе, мы заново изобретали колесо и заново программировали те же самые функции больше раз, чем я могу сосчитать. Модули Turbo предоставляют замечательный способ получить функциональность и простоту одновременно: вы пишете многократно используемый код и вызываете его в одной строке. Ваша тестовая программа остается маленькой, но она может делать мощные вещи.

Одна из возможностей модулей Turbo Pascal – их блок инициализации. Как в пакете Ada, любой код в основном блоке begin-end модуля выполняется когда программа инициализирована. Как вы увидите позже, это иногда дает нам хорошее упрощение кода. Наша процедура Init, которая была с нами начиная с Главы 1, полностью исчезает когда мы используем модули. Различные подпрограммы в Cradle, другие ключевые возможности нашего подхода, будут распределены по модулям.

Концепция модулей, конечно, ничем не отличается от модулей Си. Однако в C (и C++) интерфейс между модулями происходит через операторы include препроцессора и заголовочные файлы. Как кто-то, кто читал множество прогрограмм других людей на C, я всегда находил это довольно сбивающим с толку. Всегда кажется, что любая структура данных, о который вы бы хотели знать, находится в каком-то другом файле. Модули Turbo проще по той причине, за которую они критикуются некоторыми: интерфейсы функций и их реализации включены в тот же самый файл. В то время, когда эта организация может создать проблемы с защитой кода, она также уменьшает количество файлов наполовину, что не в два раза хуже. Связывание объектных файлов также просто, потому что компилятор Turbo заботится об этом без необходимости в файлах типа make или других механизмах.