твие с каждой цепочкой в распределителе происходит через четырехсловный заголовок, содержащий указа- тели на начало цепочки, ее конец, следующее место для записи и следующее место для чтения. Связь между распределителем и dc осуществляется через указатели к этим заголовкам. Распределитель первоначально имеет одну большую цепочку в списке свободных цепочек. Все заголовки, исключая один, указывающий на эту цепочку, имеются в списке свободных заго- ловков. Запросы на цепочки выполняются по размеру. Размер фактически выделяемой цепочки, есть ближайшая следующая сте- пень двойки. Когда выполняется запрос на цепочку, распреде- литель сперва проверяет свободный список, чтобы увидеть, есть ли там цепочка нужного размера. Если ничего не найдено, распределитель ищет более длинную цепочку и расщепляет ее до тех пор, пока не получится цепочка нужного размера. Оставша- яся часть цепочки помещается в свободный список. Если не - 23 - имеется цепочек большего размера, распределитель пытается объединить свободные цепочки меньшего размера в одну боль- шую. Так как все цепочки являются результатом расщепления больших цепочек, каждая цепочка имеет соседнюю с ней в памяти и, если соседняя цепочка свободна, то, чтобы увели- чить цепочку, можно требуемую цепочку объединить с соседней. При безуспешной попытке найти цепочку подходящей длины после объединения, распределитель запрашивает у системы сво- бодное место. Количество памяти в системе является единст- венным ограничением на размер и количество цепочек в dc. В распределителе имеются программы для чтения, записи, копирования цепочек, сдвига в начало, сдвига вперед на шаг и сдвига назад на шаг по цепочкам. Все манипуляции с цепоч- ками выполняются, используя эти программы. Программы чтения и записи увеличивают указатель чтения или указатель записи так, что символы цепочки читаются или пишутся подряд сериями вызовов чтения или записи. Указатель записи является, по существу, указателем на конец содержащей информацию части цепочки и при попытке прочитать информацию, находящуюся за этим указателем, чтение окажется безуспешным, а программа чтения в качестве ответа вернет признак конца цепочки. Попытка записать за конец цепочки вынудит распреде- литель запросить большее пространство и затем скопировать старую цепочку в больший блок. 2.2.3. Внутренняя арифметика Все арифметические действия выполняются в целых числах. Операнды (или операнд), требующиеся для выполнения действия извлекаются из главного стека и у них отбрасывается точ- ность, хранящаяся вместе с числом. Для того, чтобы получить результат выполнения программ внутренней арифметики с подхо- дящей точностью, к операндам добавляются нули или отбрасыва- ются лишние цифры. Например, если точность операндов раз- лична, и требуется выравнивание, как это бывает при сложе- нии, к операнду с меньшей точностью добавляются нули. После выполнения требуемой арифметической операции перед тем, как занести результат в стек, в конец числа добавляется значение его точности Регистр, называемый scale, используется в большинстве арифметических операций; scale определяет количество деся- тичных цифр в арифметических вычислениях. Значение scale может быть установлено в величину, расположенную в верхушке стека, с помощью команды k. Для того, чтобы занести значение scale в стек, используется команда K. scale должно быть не меньше нуля и меньше 100. При описании каждой арифметической операции будет показано точное влияние scale на вычисления. - 24 - 2.2.4. Сложение и вычитание Точности представления двух чисел сравниваются, и к числу с меньшей точностью добавляются последующие нули для того, чтобы уравнять точости обоих чисел. Если разница точ- ностей нечетна, то число с меньшей точностью умножается на 10. Точность результата устанавливается затем в величину, равную большей из двух точностей. Вычитание производится инвертированием знака числа для того, чтобы вычитание заменить на сложение. Сложение выполняется цифра за цифрой, начиная с младших разрядов к старшим. Перенос распространяется обычным спосо- бом. Результирующее число берется в канонической форме, при которой может потребоваться убрать лидирующие нули или, для отрицательных чисел, заменить старшие цифры "99 -1" на "-1". В любом случае цифры, которые не попадают в интервал 0-99, должны быть приведены в этот интервал, путем распространения переноса или заимствования из других разрядов. 2.2.5. Умножение Точности двух операндов запоминаются и отбрасываются. Оба операнда делаются положительными. Затем выполняется умножение способом цифра за цифрой. Первое число умножается на каждую цифру второго числа, начиная с младшего разряда. Промежуточные результаты накапливаются в частные суммы, сум- мирование которых дает окончательный результат. Результат заносится в канонической форме, а его знак определяется из знаков операндов. Точность результата устанавливается равной сумме точ- ностей двух операндов. Если эта точность больше, чем значе- ние внутреннего регистра scale, а также больше, чем точности обоих операндов, то точность результата устанавливается в максимальное из этих трех значений. 2.2.6. Деление Точности обоих операндов отбрасываются. У делимого отб- расываются лишние цифры или добавляются недостающие нули, чтобы сделать точость результата целого деления равной зна- чению внутренней переменной scale. Знаки запоминаются и отбрасываются. Деление выполняется также, как если бы оно выполнялось вручную. Вычисляется разница длин обоих чисел. Если дели- тель длиннее делимого, возвращается значение ноль. В против- ном случае две старшие цифры делимого делятся на старшую цифру делителя. Результат этого действия используется как первая (старшая) цифра частного. Пробная цифра умножается на делитель, и результат вычитается из делимого, и для - 25 - получения очередной цифры частного процесс повторяется до тех пор, пока остаток делимого не станет меньше делителя. В конце процесса цифры частного переводятся в каноническую форму и, если это необходимо, происходит распространение переноса. Знак определяется из знаков обоих операндов. 2.2.7. Нахождение остатка Для нахождения остатка вызывается программа деления, и выполняется деление так, как это было описано в предыдущем разделе. Возвращаемый результат - есть остаток от деления после завершения процесса деления. Знак остатка имеет такой же знак, что и делимое. Точность остатка устанавливается в максимальную из величин точности делимого и точности част- ного плюс точность делителя. 2.2.8. Вычисление квадратного корня Из операнда убирается точность. Если необходимо, дoбавляются нули для того, чтобы получить в результате тре- буемую точность. Для вычисления используется метод Ньютона с последующей апроксимацией по правилу: x[n+1] = 1/2 (x[n] + y / x[n]) Начальное предположение берется из расчета, что квадратный корень равен старшим двум цифрам. 2.2.9. Возведение в степень Разрешается возведение в степень только с целым показа- телем степени. Если показатель степени равен нулю, то результат равен единице. Если показатель степени отрицате- лен, то он делается положительным, а на основание делится единица. Шкала результата отбрасывается. Целый показатель степени рассматривается как двоичное число. Основание последовательно возводится в квадрат, а результат получается как произведение результатов этих воз- ведений основания, которые соответствуют позициям в двоичном представлении показателя степени. Чтобы сделать точность результата такой же, как и при умножении (которое на самом деле и выполнялось), отбрасывается необходимое количество цифр. 2.2.10. Перевод вводных чисел и входная система счисления Числа преобразуются во внутреннее представление по мере их считывания. Точность хранится с числом и является коли- чеством десятичных цифр после запятой. Перед отрицательными числами ставится знак "_" (подчерк). Шестнадцатиричные цифры A-F соответствуют числам 10-15, независимо от входного основания системы счисления. Для изменения основания системы счисления вводимых чисел используется команда i. Эта - 26 - команда извлекает из стека, усекает результирующее число до целого и использует его как основание системы счисления для последующего ввода чисел. Первоначально входная система счисления - десятичная. Команда I заносит значение основа- ния системы счисления вводных чисел в стек. 2.2.11. Выводные команды Команда p вызывает печать верхушки стека. При этом вер- хушка стека не извлекается. Для того, чтобы вывести содержи- мое всех внутренних регистров и всего стека, используется команда f. Для того, чтобы изменить основание системы счис- ления выводных чисел, используется команда o. По этой команде извлекается верхушка стека, усекается до целого и это значение используется в дальнейшем как основание системы счисления для выводных чисел. Система счисления для вывод- ных чисел первоначально установлена в десятичную. Команда О заносит значение основания системы счисления для выводных чисел в стек. 2.2.12. Выходной формат и выходная система счисления Входная и выходная системы счислений влияют только на интерпретацию чисел при вводе и выводе, но не влияют на арифметические вычисления. Большие числа выводятся по 70 цифр на строке. Если строка имеет продолжение, то на это указывает знак \ (обратная косая черта) в конце строки. Можно работать с любыми системами счисления, хотя не все достаточно целесообразны. В частности, например, полезна система счисления с основанием 1000, при которой выводимые числа печатаются группами по три цифры. Восьмеричная и шестнадцатиричная системы счисления используются для пере- вода в и из этих систем счисления. 2.2.13. Внутренние регистры Числа или цепочки могут быть запомнены во внутренних регистрах или загружены в стек из регистров, используя команды s и l. По команде sx происходит извлечение зачения верхушки стека и запоминание его в регистре x. x может быть любым символом. По команде lx происходит запись значения регистра x в верхушку стека. Команда l не изменяет содержи- мое регистра, а команда s его изменяет. 2.2.14. Стековые команды Команда c чистит стек. Команда d дублирует число в вер- хушке стека. Команда z заносит в стек длину стека. Команда X заменяет число в верхушке стека его точностью. Команда Z заменяет верхушку стека его длиной. - 27 - 2.2.15. Описания и вызовы функций Строка из символов в коде КОИ-8, заключенная в квадрат- ные скобки, заносится в стек. Команда q прекращает работу или, при выполнении по строке, уменьшает уровень вложенности на два. 2.2.16. Внутренние регистры - программирование на dc Для того, чтобы программировать, работая с программой dc, можно пользоваться командами загрузки и запоминания l и s, запоминания строк "[]", командой выполнения x, командами проверки <&lt;, >&gt;, =, !<&lt;, !>&gt;, != Команда x рассматривает вер- хушку стека как команду программы dc и выполняет ее. Команды проверки сравнивают два верхних элемента стека, и, если условие справедливо, то выполняется регистр x, который следует за операцией отношения. Например, для того, чтобы напечатать числа 0-9, надо набрать следующую программу: [lip1+ si li10>&gt;a]sa 0si lax 2.2.17. Стековые регистры и массивы Следующие команды были разработаны для использования не людьми, а компилятором. Они охватывают стековые регистры и массивы. Кроме стека, с которым работают команды, dc имеет также несколько индивидуальных стеков для каждого регистра. Эти регистры оперируют с командами S и L. Sx заносит верхнее значение главного стека в стек для регистра x. Lx извлекает значение из стека регистра x и заносит результат в основной стек. Команды s и l также работают с регистрами, но не как со стеками. l не изменяет верхушку регистрового стека, а s разрушает то, что там находилось ранее. К командам для работы с массивами относятся : и ;. :x извлекает значение стека и использует его как индекс к мас- сиву x. Следующий элемент стека запоминается в элементе мас- сива x с этим индексом. Индекс должен быть больше нуля и меньше 2047. ; - это команда для загрузки основного стека из массива x. Значение верхушки стека - это индекс в массиве x, откуда должна произойти загрузка. 2.2.18. Прочие команды Команда ! интерпртирует остаток строки как команду ДЕМОС и передает ее системе для выполнения. Другая команда компилятора - Q. Эта команда использует верхушку стека как число уровней рекурсии, которое надо пропустить. - 28 - 2.3. Выбор решений Основной причиной использования распределителя динами- ческой памяти было то, что программа общего назначения могла быть (и была на самом деле) использована для множества дру- гих задач. Если заранее не известно, какова будет длина цепочки, распределитель принимает значение для ввода и ком- пиляции (т.е. команды, заключенные в квадратные скобки [...]). Результат был таков, что при скромной стоимости во время выполнения все соображения по поводу распределения цепочек и размеров цепочек были удалены из оставшейся части программы, и отладка стала более легкой. Используемый метод тратил примерно 25% доступной памяти. Выбор числа 100 как основания системы счсления для внутренней арифметики по-видимому не имеет явного преиму- щества. Кроме того, основание системы счисления не должно превышать 127 из-за аппаратных ограничений; и при стоимости 5% памяти отладка стала много легче, а десятичный вывод существенно быстрее. Причина создания арифметики стекового типа - дать воз- можность всем командам dc от сложения до выполнения подпрог- рамм по-существу выполняться одинаково. Результатом явилось значительноя степень логического разделения конечной прог- раммы на модули с очень маленькой связью между ними. Из-за недостатка взаимодействия между шкалой и основа- ниями систем счисления разумным было обеспечить понимаемость способа выполнения после изменения шкалы или основания, когда числа уже были введены. Ранняя версия, которая имела глбальные понятия шкалы и основания системы счисления, не была хорошо разработана. Если значение scale интерпретирова- лось в текущей вводной или выводной системе счисления, то изменение системы счисления или шкалы в середине вычисления мог вызвать неправильную интерпретацию результатов. Текущая схема имеет то преимущество, что значение входного и выход- ного оснований систем счисления используется только для вводы и вывода соответственно, и игнорируется во всех других действиях. Значение шкалы не используется для любых сущест- венных целей в любой части программы, а используется только для того, чтобы предотвратить увеличение количества десятич- ных знаков за границы текущей точности. Разумным решением выбора шкалы результатов арифметичес- ких действий было бы то, что при явном указании пользователя ни одна значащая цифра не должна быть отброшена. Действи- тельно, если пользователь хочет сложить числа 2.5 и 3.1415, то кажется разумным дать ему результат 5.6415, поскольку в остальных значащих цифрах нет необходимости. С другой стороны, при умножении и возведении в степень вырабатывается результат с количеством цифр большим, чем у - 29 - операндов, и кажется разумным дать как мимнимум количество цифр в операндах, а не больше, если только пользователь не укажет явно количество цифр, определив значение scale. Квадратный корень может быть вычислен так же, как и умноже- ние. Вполнение деления дает произвольное количество цифр, и не так просто предположить пожелания пользователя относи- тельно количества цифр. В этом случае пользователь должен определить значение scale. Шкала остатка выбрана для того, чтобы можно было восстановить делимое из частного и остатка. Это легко выполнить: ни одна цифра не отбрасывалась. - 30 - СОДЕРЖАНИЕ АННОТАЦИЯ ......................................... 2 1. ВВЕДЕНИЕ .......................................... 2 2. ИНТЕРАКТИВНЫЙ КАЛЬКУЛЯТОР bc ...................... 3 2.1. Простые действия с целыми числами ............... 3 2.2. Основания систем счисления ...................... 4 2.3. Масштабирование ................................. 6 2.4. Функции ......................................... 7 2.5. Индексированные переменные ...................... 8 2.6. Управляющие операторы ........................... 9 2.7. Некоторые детали ................................ 11 2.8. Три важные вещи ................................. 12 2.9. Детальное описание .............................. 13 2.9.1. Обозначения ................................... 13 2.9.2. Знаки ......................................... 13 2.9.2.1. Комментарии ................................. 13 2.9.2.2. Идентификаторы .............................. 13 2.9.2.3. Ключевые слова .............................. 13 2.9.2.4. Константы ................................... 14 2.9.3. Выражения ..................................... 14 2.9.3.1. Простые выражения ........................... 14 2.9.3.1.1. Именованные выражения ..................... 14 2.9.3.1.2. Вызовы функций ............................ 14 2.9.3.1.3. Константы ................................. 15 2.9.3.1.4. Круглые скобки ............................ 15 2.9.3.2. Унарные операции ............................ 15 2.9.3.3. Операция возведения в степень ............... 16 2.9.3.4. Операции группы умножения ................... 16 2.9.3.5. Операции группы сложения .................... 16 2.9.3.6. Операторы присваивания ...................... 17 2.9.4. Отношения ..................................... 17 2.9.5. Классы памяти ................................. 17 2.9.6. Операторы ..................................... 18 2. ИНТЕРАКТИВНЫЙ СТЕКОВЫЙ КАЛЬКУЛЯТОР dc ............. 20 2.1. Описание синтаксиса ............................. 20 2.2. Детальное описание .............................. 22 2.2.1. Внутреннее представление чисел ................ 22 2.2.2. Распределитель памяти ......................... 23 2.2.3. Внутренняя арифметика ......................... 24 2.2.4. Сложение и вычитание .......................... 25 2.2.5. Умножение ..................................... 25 2.2.6. Деление ....................................... 25 2.2.7. Нахождение остатка ............................ 26 2.2.8. Вычисление квадратного корня .................. 26 2.2.9. Возведение в степень .......................... 26 2.2.10. Перевод вводных чисел и входная система счисле- ния ........................................... 26 - 31 - 2.2.11. Выводные команды .............................. 27 2.2.12. Выходной формат и выходная система счисления .. 27 2.2.13. Внутренние регистры ........................... 27 2.2.14. Стековые команды .............................. 27 2.2.15. Описания и вызовы функций ..................... 28 2.2.16. Внутренние регистры - программирование на dc .. 28 2.2.17. Стековые регистры и массивы ................... 28 2.2.18. Прочие команды ................................ 28 2.3. Выбор решений ................................... 29 - 32 -