Страница:
степень второго выражения. Второе выражение должно быть
целым. Если a - это точность левого выражения, а b -
абсолютное значение правого выражения (показателя сте-
пени), то точность результата вычисляется по формуле
min(a*b,max(scale,a))
2.9.3.4. Операции группы умножения
Операции *, /, % выолняются слева направо.
выражение*выражение
Результатом является произведение двух выражений. Если
a и b - точности обоих выражений, то точность резуль-
тата вычисляется по формуле
min(a+b,max(scale,a,b))
выражение/выражение
Результатом является частное от деления двух выражений.
Точность результата - значение scale.
выражение%выражение
Операция % вырабатывает остаток от деления двух выраже-
ний. Более точно, a%b - это a-a/b*b. Точность резуль-
тата - это сумма точности делителя и значения scale.
2.9.3.5. Операции группы сложения
Операции группы сложения выполняются слева направо.
выражение+выражение
Результатом является сумма двух выражений. Точность
результата - это максимальная из точностей обоих выра-
жений.
выражение-выражение
Результатом является разность двух выражений. Точность
результата - это максимальная из точностей обоих выра-
жений.
- 16 -
2.9.3.6. Операторы присваивания
Операторы присваивания выполняются справа налево.
именованное_выражение=выражение
Это выражение присваивает значение выражения справа
именованному выражению слева.
именованное_выражение=+выражение
именованное_выражение=-выражение
именованное_выражение=*выражение
именованное_выражение=/выражение
именованное_выражение=%выражение
именованное_выражение=^выражение
Результат указанных выше выражений эквивалентен
именов. выр.=именов. выр. ОП выр.
где ОП - знак операции после знака =.
2.9.4. Отношения
В отличие от других операций, операции отношения допус-
тимы только, как объекты операторов if, while или внутри
оператора for.
выражение<выражение
выражение>выражение
выражение<=выражение
выражение>=выражение
выражение==выражение
выражение!=выражение
2.9.5. Классы памяти
В bc имеется только два класса памяти - глобальный и
автоматический (локальный). Командой auto требуется описы-
вать только те идентификаторы, которые являются локальными
для функций. Аргументы функций являются для них локальными.
Все другие идентификаторы подразумеваются глобальными и дос-
тупны для всех функций. Все идентификаторы - глобальные и
локальные - имеют нулевое начальное значение.
- 17 -
Идентификаторы, описанные как auto, размещаются в памяти при
входе в функцию и освобождаются при выходе из нее. Поэтому,
они не сохраняют свое значение между двумя вызовами функции.
Автоматические массивы определяются именем массива, за кото-
рым следуют пустые квадратные скобки.
2.9.6. Операторы
Операторы должны разделяться точкой с запятой или сим-
волом новой строки. Операторы выполняются последовательно,
за исключением тех случаев, где порядок указывается управля-
ющими операторами.
Операторы выражений
Когда оператор есть выражение, если главный (внешний)
оператор выражения не есть оператор присваивания, то
печатается значение выражения, а за ним символ новой
строки.
Составные операторы
Операторы могут быть объединены вместе, когда они окру-
жены фигурными скобками {}.
Строковые операторы, заключенные в кавычки
"любая_строка"
Этот оператор печатает то, что заключено в кавычки.
Оператор if
if(условие)оператор
Если условие верно, то выполняется оператор.
Оператор while
while(условие)оператор
Оператор выполняется до тех пор, пока условие истинно.
Проверка условия осуществляется перед каждым выполне-
нием оператора.
Оператор for
for(выраж.;условие;выраж.)оператор
Оператор for выполняет те же действия, что и последова-
тельность
- 18 -
первое_выражение
while(условие){
оператор
последнее_выражение
}
Все три выражения должны обязательно присутствовать.
Оператор break
break
break вызвает прерывание выполнения операторов while
или for
Оператор auto
auto идентификатор[,идентификатор]
Оператор auto вызывает заведение значений идентификато-
ров в стеке. Идентификаторы могут быть обычными иден-
тификаторами или идентификаторами массива. Идентифика-
тор массива определяется тем, что за именем массива
следуют пустые квадратные скобки. Оператор auto должен
быть первым оператором в определении функции.
Оператор define
define([параметр[,параметр...]]){
операторы}
Оператор define определяет функцию. Параметры могут
быть простыми идентификаторами или именами массивов.
За именами массивов должны следовать пустые квадратные
скобки.
Оператор return
return
return(выражение)
Оператор return вызывает окончание работы функции, изв-
лечение из стека ее автоматических переменных и опреде-
ление результата функции. Первая форма эквивалентна
return(0). Результатом функции является результат выра-
жения в скобках.
Окончание работы
Оператор quit останавливает выполнение программы bc и
возвращает управление системе ДЕМОС в тот момент, когда
он появляется. Оператор quit не может использоваться в
определениях функций или в операторах if, for или
- 19 -
while.
2. ИНТЕРАКТИВНЫЙ СТЕКОВЫЙ КАЛЬКУЛЯТОР dc
2.1. Описание синтаксиса
В данной главе описываются команды dc, которые предназ-
начены для использования людьми. Дополнительные команды,
которые предназначены для вызова компилятром, описаны в
"Детальном описании".
На строке допускается любое количество команд. Символы
пробелов и новой строки игнорируются, исключая мест внутри
чисел и тех мест, где ожидается имя регистра.
Воспринимаются следующие конструкции:
число
Значение числа помещается в стек. Число - это непрерывае-
мая цепочка цифр 0-9 и больших латинских букв A-F, которые
рассматриваются как значения цифр 10-15, соответственно.
Для обозначения отрицательного числа используется знак
подчерк (_), который должен предшествовать числу. Числа
могут содержать десятичную точку.
+ - * / % ^
Верхние два значения стека складываются (+), вычитаются
(-), умножаются (*), делятся (/), ищется остаток от деле-
ния первого на второе (%) или возводятся в степень (^).
Два элемента извлекаются из стека, результат помещается
обратно в стек, в его верхушку. Результат деления усека-
ется до целого отбрасыванием дробной части. При возведе-
нии в степень показатель степени должен быть целым. В
детальном описании описывается, как работать с числами с
десятичной точкой.
sx
Верхушка основного стека извлекается и запоминается в
регистре с именем x, где x может быть любым символом.
Если s - прописная буква, то x воспринимается как стек, и
значение помещается в него. В имени регистра допускаются
любые символы, даже пробелы или символы новой строки.
- 20 -
lx
Значение регистра x заносится в стек. Значение регистра
не изменяется. Если l - прописная буква, то x воспринима-
ется как стек, и его верхнее значение извлекается и поме-
щается в основной стек.
Все регистры имеют начальное пустое значение, которое
воспринимается как нулевое командой l и как ошибочное коман-
дой L.
d
Дублируется значение верхушки стека.
p
Печатается верхнее значение стека. Верхушка остается без
изменений.
f
Печатаются все значения в стеке и в регистрах.
х
Верхний элемент стека рассматривается как цепочка симво-
лов, извлекается из стека и выполняется, как командная
строка dc.
[...]
Помещает цепочку символов, заключенную в квадратные скобки
в верхушку стека.
q
Выход из программы. Если q встретилось при выполнении
цепочки, то уровень рекурсии уменьшается на два. Если q -
прописная буква, то уровень вложенности стека уменьшается
на величину верхушки стека.
<<х >>х =х !<<х !>>х !=х
Извлекаются и сравниваются два верхних элемента стека.
Если установленное отношение справедливо, выполняется
регистр х, Восклицательный знак означает отрицание.
v
Заменяется верхнее значение стека на его квадратный
корень. Квадратный корень целого числа усекается до
целого. Обработка чисел с десятичной точкой описывается в
- 21 -
детальном описании.
!
Оставшаяся часть строки интерпретирутеся как команда
ДЕМОС. Управление возвращается в программу dc, когда
команда завершится.
c
Извлекаются все значения стека; стек очищается.
i
Извлекается верхнее знчение стека, которое рассматривается
как основание системы счисления для последующих вводимых
чисел. Если i - прописная буква, то значение основания
системы счисления вводимых чисел заносится в стек. Осно-
вания систем счисления меньше единицы и больше 16 не под-
держиваются.
o
Извлекается верхнее значение стека, которое рассматрива-
ется как основание системы счисления для последующих выво-
димых чисел. Если o - прописная буква, то значение осно-
вания системы счисления выводимых чисел заносится в стек.
k
Извлекается верхнее значение стека, и это значение исполь-
зуется как точность вычислений, которая является количест-
вом цифр после запятой при выполнении умножения, деления и
возведения в степень. Точность должна быть больше либо
равна нулю и меньше 100. Если k - прописная буква, то зна-
чение точности заносится в стек.
z
Значение глубины стека заносится в стек.
?
Строка ввода берется из исходного ввода (обычно консоль) и
выполняется.
2.2. Детальное описание
2.2.1. Внутреннее представление чисел
Числа запоминаются внутри, используя динамический расп-
ределитель памяти. Числа хранятся в форме цепочек цифр в
системе счисления с основанием 100 по одной цифре на байт
- 22 -
(сторичная цифра). Числа хранятся в порядке от младших цифр
к старшим. Например, число 1234 имеет представление
"34 12". После любой арифметической операции над числом
тщательно проверяется, чтобы все цифры находились в интер-
вале от 0 до 99 и не было лидирующих нулей. Число ноль
представляется пустой цепочкой.
Отрицательные числа представлены записью сторичного
дополнения (цифры представлены как разность между 100 и
соответствующей цифрой), которое аналогично записи двоичного
дополнения для двоичных чисел. Самая старшая цифра отрица-
тельного числа всегда -1, а все другие цифры в интервале
0-99. Цифра, предшествующая самой старшей цифре -1, никогда
не может быть 99. Представление числа -157 во внутренней
форме: "43 98 -1". Мы назовем эту форму канонической формой
числа. Преимуществом этого представления является легкость
сложения отрицательных чисел. Когда сложение выполняется
цифра за цифрой, результат формально корректен. Результат
только требует модификации, если необходимо, для перевода в
каноническую форму.
Так как наибольшее допустимое число 99, а в байте можно
представлять вдвое большие числа, то сложение может выпол-
няться с переносом.
За самой старшей цифрой хранится дополнительный байт,
показывающий число допустимых десятичных цифр после запятой.
Представление числа .001: 1,3; число после запятой, показы-
вает, что это число не есть значащая цифра. Значение этого
дополнительного числа называется точностью числа.
2.2.2. Распределитель памяти
Для внутреннего хранения чисел, команд и др. dc исполь-
зует динамический распределитель памяти цепочек. Все считы-
ваемые и записываемые числа проходят через этот распредели-
тель. Взаимодействие с каждой цепочкой в распределителе
происходит через четырехсловный заголовок, содержащий указа-
тели на начало цепочки, ее конец, следующее место для записи
и следующее место для чтения. Связь между распределителем и
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, командами
проверки <<, >>, =, !<<, !>>, != Команда x рассматривает вер-
хушку стека как команду программы dc и выполняет ее.
Команды проверки сравнивают два верхних элемента стека, и,
если условие справедливо, то выполняется регистр x, который
следует за операцией отношения. Например, для того, чтобы
напечатать числа 0-9, надо набрать следующую программу:
[lip1+ si li10>>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. Выбор решений
Основной причиной использования распределителя динами-
ческой памяти было то, что программа общего назначения могла
быть (и была на самом деле) использована для множества дру-
целым. Если a - это точность левого выражения, а b -
абсолютное значение правого выражения (показателя сте-
пени), то точность результата вычисляется по формуле
min(a*b,max(scale,a))
2.9.3.4. Операции группы умножения
Операции *, /, % выолняются слева направо.
выражение*выражение
Результатом является произведение двух выражений. Если
a и b - точности обоих выражений, то точность резуль-
тата вычисляется по формуле
min(a+b,max(scale,a,b))
выражение/выражение
Результатом является частное от деления двух выражений.
Точность результата - значение scale.
выражение%выражение
Операция % вырабатывает остаток от деления двух выраже-
ний. Более точно, a%b - это a-a/b*b. Точность резуль-
тата - это сумма точности делителя и значения scale.
2.9.3.5. Операции группы сложения
Операции группы сложения выполняются слева направо.
выражение+выражение
Результатом является сумма двух выражений. Точность
результата - это максимальная из точностей обоих выра-
жений.
выражение-выражение
Результатом является разность двух выражений. Точность
результата - это максимальная из точностей обоих выра-
жений.
- 16 -
2.9.3.6. Операторы присваивания
Операторы присваивания выполняются справа налево.
именованное_выражение=выражение
Это выражение присваивает значение выражения справа
именованному выражению слева.
именованное_выражение=+выражение
именованное_выражение=-выражение
именованное_выражение=*выражение
именованное_выражение=/выражение
именованное_выражение=%выражение
именованное_выражение=^выражение
Результат указанных выше выражений эквивалентен
именов. выр.=именов. выр. ОП выр.
где ОП - знак операции после знака =.
2.9.4. Отношения
В отличие от других операций, операции отношения допус-
тимы только, как объекты операторов if, while или внутри
оператора for.
выражение<выражение
выражение>выражение
выражение<=выражение
выражение>=выражение
выражение==выражение
выражение!=выражение
2.9.5. Классы памяти
В bc имеется только два класса памяти - глобальный и
автоматический (локальный). Командой auto требуется описы-
вать только те идентификаторы, которые являются локальными
для функций. Аргументы функций являются для них локальными.
Все другие идентификаторы подразумеваются глобальными и дос-
тупны для всех функций. Все идентификаторы - глобальные и
локальные - имеют нулевое начальное значение.
- 17 -
Идентификаторы, описанные как auto, размещаются в памяти при
входе в функцию и освобождаются при выходе из нее. Поэтому,
они не сохраняют свое значение между двумя вызовами функции.
Автоматические массивы определяются именем массива, за кото-
рым следуют пустые квадратные скобки.
2.9.6. Операторы
Операторы должны разделяться точкой с запятой или сим-
волом новой строки. Операторы выполняются последовательно,
за исключением тех случаев, где порядок указывается управля-
ющими операторами.
Операторы выражений
Когда оператор есть выражение, если главный (внешний)
оператор выражения не есть оператор присваивания, то
печатается значение выражения, а за ним символ новой
строки.
Составные операторы
Операторы могут быть объединены вместе, когда они окру-
жены фигурными скобками {}.
Строковые операторы, заключенные в кавычки
"любая_строка"
Этот оператор печатает то, что заключено в кавычки.
Оператор if
if(условие)оператор
Если условие верно, то выполняется оператор.
Оператор while
while(условие)оператор
Оператор выполняется до тех пор, пока условие истинно.
Проверка условия осуществляется перед каждым выполне-
нием оператора.
Оператор for
for(выраж.;условие;выраж.)оператор
Оператор for выполняет те же действия, что и последова-
тельность
- 18 -
первое_выражение
while(условие){
оператор
последнее_выражение
}
Все три выражения должны обязательно присутствовать.
Оператор break
break
break вызвает прерывание выполнения операторов while
или for
Оператор auto
auto идентификатор[,идентификатор]
Оператор auto вызывает заведение значений идентификато-
ров в стеке. Идентификаторы могут быть обычными иден-
тификаторами или идентификаторами массива. Идентифика-
тор массива определяется тем, что за именем массива
следуют пустые квадратные скобки. Оператор auto должен
быть первым оператором в определении функции.
Оператор define
define([параметр[,параметр...]]){
операторы}
Оператор define определяет функцию. Параметры могут
быть простыми идентификаторами или именами массивов.
За именами массивов должны следовать пустые квадратные
скобки.
Оператор return
return
return(выражение)
Оператор return вызывает окончание работы функции, изв-
лечение из стека ее автоматических переменных и опреде-
ление результата функции. Первая форма эквивалентна
return(0). Результатом функции является результат выра-
жения в скобках.
Окончание работы
Оператор quit останавливает выполнение программы bc и
возвращает управление системе ДЕМОС в тот момент, когда
он появляется. Оператор quit не может использоваться в
определениях функций или в операторах if, for или
- 19 -
while.
2. ИНТЕРАКТИВНЫЙ СТЕКОВЫЙ КАЛЬКУЛЯТОР dc
2.1. Описание синтаксиса
В данной главе описываются команды dc, которые предназ-
начены для использования людьми. Дополнительные команды,
которые предназначены для вызова компилятром, описаны в
"Детальном описании".
На строке допускается любое количество команд. Символы
пробелов и новой строки игнорируются, исключая мест внутри
чисел и тех мест, где ожидается имя регистра.
Воспринимаются следующие конструкции:
число
Значение числа помещается в стек. Число - это непрерывае-
мая цепочка цифр 0-9 и больших латинских букв A-F, которые
рассматриваются как значения цифр 10-15, соответственно.
Для обозначения отрицательного числа используется знак
подчерк (_), который должен предшествовать числу. Числа
могут содержать десятичную точку.
+ - * / % ^
Верхние два значения стека складываются (+), вычитаются
(-), умножаются (*), делятся (/), ищется остаток от деле-
ния первого на второе (%) или возводятся в степень (^).
Два элемента извлекаются из стека, результат помещается
обратно в стек, в его верхушку. Результат деления усека-
ется до целого отбрасыванием дробной части. При возведе-
нии в степень показатель степени должен быть целым. В
детальном описании описывается, как работать с числами с
десятичной точкой.
sx
Верхушка основного стека извлекается и запоминается в
регистре с именем x, где x может быть любым символом.
Если s - прописная буква, то x воспринимается как стек, и
значение помещается в него. В имени регистра допускаются
любые символы, даже пробелы или символы новой строки.
- 20 -
lx
Значение регистра x заносится в стек. Значение регистра
не изменяется. Если l - прописная буква, то x воспринима-
ется как стек, и его верхнее значение извлекается и поме-
щается в основной стек.
Все регистры имеют начальное пустое значение, которое
воспринимается как нулевое командой l и как ошибочное коман-
дой L.
d
Дублируется значение верхушки стека.
p
Печатается верхнее значение стека. Верхушка остается без
изменений.
f
Печатаются все значения в стеке и в регистрах.
х
Верхний элемент стека рассматривается как цепочка симво-
лов, извлекается из стека и выполняется, как командная
строка dc.
[...]
Помещает цепочку символов, заключенную в квадратные скобки
в верхушку стека.
q
Выход из программы. Если q встретилось при выполнении
цепочки, то уровень рекурсии уменьшается на два. Если q -
прописная буква, то уровень вложенности стека уменьшается
на величину верхушки стека.
<<х >>х =х !<<х !>>х !=х
Извлекаются и сравниваются два верхних элемента стека.
Если установленное отношение справедливо, выполняется
регистр х, Восклицательный знак означает отрицание.
v
Заменяется верхнее значение стека на его квадратный
корень. Квадратный корень целого числа усекается до
целого. Обработка чисел с десятичной точкой описывается в
- 21 -
детальном описании.
!
Оставшаяся часть строки интерпретирутеся как команда
ДЕМОС. Управление возвращается в программу dc, когда
команда завершится.
c
Извлекаются все значения стека; стек очищается.
i
Извлекается верхнее знчение стека, которое рассматривается
как основание системы счисления для последующих вводимых
чисел. Если i - прописная буква, то значение основания
системы счисления вводимых чисел заносится в стек. Осно-
вания систем счисления меньше единицы и больше 16 не под-
держиваются.
o
Извлекается верхнее значение стека, которое рассматрива-
ется как основание системы счисления для последующих выво-
димых чисел. Если o - прописная буква, то значение осно-
вания системы счисления выводимых чисел заносится в стек.
k
Извлекается верхнее значение стека, и это значение исполь-
зуется как точность вычислений, которая является количест-
вом цифр после запятой при выполнении умножения, деления и
возведения в степень. Точность должна быть больше либо
равна нулю и меньше 100. Если k - прописная буква, то зна-
чение точности заносится в стек.
z
Значение глубины стека заносится в стек.
?
Строка ввода берется из исходного ввода (обычно консоль) и
выполняется.
2.2. Детальное описание
2.2.1. Внутреннее представление чисел
Числа запоминаются внутри, используя динамический расп-
ределитель памяти. Числа хранятся в форме цепочек цифр в
системе счисления с основанием 100 по одной цифре на байт
- 22 -
(сторичная цифра). Числа хранятся в порядке от младших цифр
к старшим. Например, число 1234 имеет представление
"34 12". После любой арифметической операции над числом
тщательно проверяется, чтобы все цифры находились в интер-
вале от 0 до 99 и не было лидирующих нулей. Число ноль
представляется пустой цепочкой.
Отрицательные числа представлены записью сторичного
дополнения (цифры представлены как разность между 100 и
соответствующей цифрой), которое аналогично записи двоичного
дополнения для двоичных чисел. Самая старшая цифра отрица-
тельного числа всегда -1, а все другие цифры в интервале
0-99. Цифра, предшествующая самой старшей цифре -1, никогда
не может быть 99. Представление числа -157 во внутренней
форме: "43 98 -1". Мы назовем эту форму канонической формой
числа. Преимуществом этого представления является легкость
сложения отрицательных чисел. Когда сложение выполняется
цифра за цифрой, результат формально корректен. Результат
только требует модификации, если необходимо, для перевода в
каноническую форму.
Так как наибольшее допустимое число 99, а в байте можно
представлять вдвое большие числа, то сложение может выпол-
няться с переносом.
За самой старшей цифрой хранится дополнительный байт,
показывающий число допустимых десятичных цифр после запятой.
Представление числа .001: 1,3; число после запятой, показы-
вает, что это число не есть значащая цифра. Значение этого
дополнительного числа называется точностью числа.
2.2.2. Распределитель памяти
Для внутреннего хранения чисел, команд и др. dc исполь-
зует динамический распределитель памяти цепочек. Все считы-
ваемые и записываемые числа проходят через этот распредели-
тель. Взаимодействие с каждой цепочкой в распределителе
происходит через четырехсловный заголовок, содержащий указа-
тели на начало цепочки, ее конец, следующее место для записи
и следующее место для чтения. Связь между распределителем и
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, командами
проверки <<, >>, =, !<<, !>>, != Команда x рассматривает вер-
хушку стека как команду программы dc и выполняет ее.
Команды проверки сравнивают два верхних элемента стека, и,
если условие справедливо, то выполняется регистр x, который
следует за операцией отношения. Например, для того, чтобы
напечатать числа 0-9, надо набрать следующую программу:
[lip1+ si li10>>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. Выбор решений
Основной причиной использования распределителя динами-
ческой памяти было то, что программа общего назначения могла
быть (и была на самом деле) использована для множества дру-