Язык программирования Форт

         

Стек в арифметических операциях


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

3 + 5 .

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

3 5 + .

теперь вы получите

8 ok

т.е. правильный результат. Как вы уже знаете из , Форт использует не такую математическую нотацию, как другие языки. Существуют три наиболее распространенные нотации для представления действий с числами. Префиксная нотация записывается так: " + 3 5 ". Хотя она не получила распространения в арифметике, фактически это самая обычная нотация, поскольку ее применяют в повседневной речи. Когда вы говорите "сложите 3 и 5", вы фактически применяете префиксную нотацию. При префиксной, нотации оператор стоит перед числами (операндами). (Оператор -- это символ или инструкция, которая определяет операцию над одним или более числами, например, +, -, х, "сложить", sin и log -- это все операторы.)

Инфиксная нотация записывается так: " 3 + 5 ". Это наиболее употребительная алгебраическая нотация, при которой оператор располагается между числами-операндами. В языке Форт используется постфиксная нотация. Например, в выражении " 3 5 + " оператор стоит на последнем месте после чисел-операндов. Префиксная нотация называется иногда польской, в честь польского математика Лукашевича, который предложил ее для формальной логики. Постфиксная нотация обычно называется обратной польской записью (поскольку она обратив префиксной нотации). Она используется в калькуляторах фирмы Hewlett-Packard и некоторых других.
Инженеры и ученые обычно предпочитают такие калькуляторы, потому что, как мы далее увидим, не нужно беспокоиться о скобках, как при инфиксной нотации. Если вы привыкли к алгебре, постфиксная нотация поначалу вам покажется странной. На самом деле в ней нет ничего странного. В школе вас, наверное, приучили к решению задач на сложение в такой форме:

3 5 + --- 8

Но ведь это то же самое, что

3 5 + . 8 ok



Хотя учитель, возможно, читал это выражение как "три плюс пять равно восемь", запись говорит вам другое: возьми 3 и 5, сложи их, получишь 8. Действительно это одна из форм стековой нотации, причем числа 3 и 5 заменяются на 8. Стековая природа становится еще более очевидной для скользящего итога, например:

5 2 + ----- 7 3 - ----- 4

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

Может быть, это и очевидно, но вот что происходит в примере со скользящим итогом на языке Форт. Когда вы ввели

5 2 + 3 - .

интерпретатор поместил 5 и 2 в стек. Знак + снимает оба числа из стека, вычисляет их сумму и помещает в стек 7. Затем число 3 из стека помещается сверху числа 7, а оператор - вынимает из стека числа 7 и 3, производит вычитание и помещает в стек 4. Наконец оператор . (точка) вынимает из стека число 4 и представляет его на экране. (Отметьте себе, что в дальнейшем мы не будем говорить вам, когда нажать клавишу , означающую ввод, если это очевидно.) Другой способ выполнить последний пример состоит в том, чтобы ввести

5 2 3 - +

Вы должны проделать все, что делает интерпретатор, и проследить, что получится в стеке, чтобы понять, почему в обоих случаях получается одинаковый результат. Можете ли вы перестроить числа и операторы в стеке по-другому, чтобы получился тот же самый результат ?

Какой бы ни была простой и изящной постфиксная запись на языке Форт, она может использоваться в контексте с алгебраической записью.


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

Экономия места и памяти переходят в мощность ЭВМ. Вот пример неопределенности в алгебраической записи. Пусть имеется такая запись :

2х3+4х5=?

Возможно несколько ответов в зависимости от порядка, в котором выполняются операции умножения и сложения. Можно избежать неопределенности двумя способами: используя скобки или приписывая операторам порядок следования. На бумаге можно использовать скобки, например:

(2 х 3) + (4 х 5 ) = 26

или

(2 x 3 + 4 ) x 5 = 50

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


Содержание раздела