Стековое программирование с человеческим лицом

в 15:32, , рубрики: forth, ненормальное программирование

Думаю, многие из вас находили в интернете статьи и книги о стековом программировании и языке Forth. Сперва волна энтузиазма: как всё просто, логично, понятно и мощно! И почему же эти идеи имеют такое незначительное распространение? Почему так мало программистов реально используют языки вроде Форта? Через какое-то время подступает волна разочарования: да, интересная мысль, но как же тяжело читать исходный код, как же муторно ведётся работа с переменными, строками и дробными числами! Интересная игрушка, полезная группе байтослесарей, не более.

image

Часто на этом всё и заканчивается. Но лично я никак не мог примириться с мыслью о том, что изящное конкатенативное программирование так и останется в тени других идей. Да, трудности с чтением исходного кода. Да, синдром одной строки. Да, каждый раз для понимания алгоритма приходится в воображении транслировать программу и представлять себе стек, читая исходный код. Но неужели это те недостатки, которые обязательно присущи стековым языкам и без которых стековое программирование перестало бы быть стековым? Неужели никак нельзя хотя бы сгладить подобные недостатки и облегчить жизнь программистам? Оказывается, можно и нужно!

Проблема первая: синдром одной строки

Словосочетание «синдром одной строки» я впервые нашёл у Баррона во «Введении в языки программирования». И хотя термин не получил широкого распространения, он очень выразительно характеризует многие языки.

Синдром одной строки характерен для тех языков, которые допускают вольную структуру исходного кода программы и имеют короткие, а иногда и вовсе односимвольные ключевые слова. Программист пытается «запихать» в одну строку как можно больше ключевых слов, из-за чего программы выглядят не слишком удобочитаемыми. Особенно ярко этот синдром проявляется в APL и его потомках, в Brainfuck и, конечно, в Форте. Посмотрите ещё раз на иллюстрацию в начале поста и посчитайте, сколько на одной строке в среднем слов.

Но это решаемая проблема. В Форте синдром одной строки появился благодаря пристрастиям Мура, который очень любит короткие и осмысленные английские слова. К сожалению, такие слова быстро заканчиваются, а суффиксы и префиксы (т.н. пространства имён на коленке) Мур не любит. Поэтому теперь весь мир наслаждается лаконичными иероглифами в духе "@! C@ C! /MOD CR S P", налепленными в одну строку. Проблема элементарно решается подбором более удачных слов. Зачем писать:

: FOR-EXAMPLE OVER OVER + ROT ROT - * ;

Если можно:

define for-exemple (a b -- {a+b}*{a-b})
    over over
    (a b -- a b a b)
    +
    (a b -- a b a+b=c)
    rot rot
    (a b c -- c a b)
    - *
end

А ещё лучше:

define for-exemple [a b -- r]
    [a b -> a b a b]
    +
    [a b c (=a+b) -> c a b]
    - /
end

Но о такой записи будет сказано ниже.

Проблема вторая: код наизнанку

Другая сложность — структуры управления наизнанку. Они, конечно, изящны с точки зрения идеи и реализации, но как же такой код трудно читать:

: sign-test ( n -- )
    dup 0 < [
        drop "отрицательное"
    ] [
        zero? [ "ноль" ] [ "положительное" ] if
    ] if print ;

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

На помощь спешат самые обычные if и while из императивного программирования:

define sign-test [x]
   [x -> x x]
   0 > if
     "Больше нуля"
    else
     "Меньше или равно нулю"
   end-ifprint-string
end

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

Что же касается Форта, то у него с этим другая проблема: всё те же слова. Мур не хотел добавлять в сложные конструкции одинаковые завершающие слова вроде END, поэтому IF, DO и другие слова должны закрываться своими уникальными словами. Поэтому мы и видим все эти IF ELSE THEN, которые вводят даже бывалых программистов в тупик. Если уж так не хочется усложнять парсер и механизм слов, почему бы не ввести слова вроде END-IF? Тут сказывается нелюбовь Мура к суффиксам и префиксам. Но, подобно первой проблеме, этот момент тоже легко решается и не является специфическим недостатком стековых языков.

Проблема третья: интерпретация в голове

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

Конечно, избавиться от этого недостатка невозможно, но есть пути, которые позволяют значительно облегчить труд программиста по чтению исходного кода. И самое главное: первые шаги уже сделаны. Действительно, Форт-программисты приняли определённую нотацию для облегчения чтения исходного кода:

( до -- после )

Такие комментарии облегчают представление о числах на стеке, их количестве и порядке следования. Не нужно каждый раз напрягать воображение, чтобы понять, сколько чисел и в какой последовательности нужно поместить на стек перед вызовом функции и сколько чисел на стеке останется в результате вычислений. Но вот загадка: если такие комментарии очень наглядны и полезны, почему Форт-программисты их пишут только в начале определения слова, да и то не всегда? Какая религия мешает после кучи drop dup swap rot написать такой поясняющий комментарий?

Вернёмся ко второму примеру кода. Конечно, это случай в вакууме, но в реальных сложных программах такие комментарии будут к месту:

define for-exemple (a b -- {a+b}/{a-b})
    over over
    (a b -- a b a b)
    +
    (a b -- a b a+b=c)
    rot rot
    (a b c -- c a b)
    - /
end

Программисту нет нужды каждый раз после всех этих swap, rot и + моделировать в голове порядок чисел в стеке. Нужно лишь пробежать глазами по комментариям. Но вот новая проблема: записи

(a b -- a b a b)

И

over over

аналогичны. Просто первая запись сделана в декларативном стиле, а вторая — в императивном. То есть строки в программе постоянно дублируются. С таким же успехом можно говорить об удобстве ассемблера: слева писать код с кучей mov и ret, а справа в комментариях a=a+1, а потом говорить об удобстве чтения. Ну да, чтения комментариев. Но их можно изловчиться писать так, что они при использовании любого языка программирования будут читаться очень легко и ясно. Из этого, конечно, не следует, что такие языки удобны. Они могут быть как угодно плохи с точки зрения чтения исходного кода.

Возникает естественное желание объединить (a b — a b a b) и over over. Действительно, если писать комментарии в определённой нотации, то их может разбирать компилятор и вручную добавлять нужные слова для перестановки элементов стека. Комментарии в круглых скобках полностью игнорируются и предназначаются только для человека. Комментарии же в квадратных скобках нужны как человеку, так и транслятору. Транслятор анализирует такие комментарии, в которых человек пишет то, что ему нужно, а не то, как прийти к такому результату. То есть со стеком можно работать и в декларативном стиле.

Рассмотрим основные, так сказать, сорта подобных выражений:
1. define foo [b a r] или [b a r — f o o]
После имени новой функции в квадратных скобках нужно указать количество аргументов, которые должны быть на вершине стека. Если при вызове какой-либо функции, которая требует три аргумента, на стеке будет лишь два аргумента, то традиционная Форт-система выдаст ошибку: стек пуст. Но с такими комментариями транслятор сможет «заглянуть» в комментарий и определить имена недостающих аргументов: ага, тут не хватает аргумента r при вызове функции foo. Согласитесь, это намного информативнее, чем постное «стек пуст». Естественно, всё сказанное относится только к работе в интерактивном режиме, когда доступен исходный код. После компиляции эти комментарии пропадут, они нужны лишь для отладки и чтения исходного кода. Для сравнения, вывод ошибки в gforth:

: add-x-y ( x y -- x+y )  compiled
          + ;  ok
4 5 add-x-y . 9  ok
4 add-x-y . 
:6: Stack underflow
4 >>>add-x-y<<< .
Backtrace:
$7FF17383C310 + 
  ok

2. [a b -> a]
Следующие виды выражений отличаются от чисто описательных словом ->, которое аналогично слову — в классических комментариях. Если количество элементов слева больше количества элементов справа, то транслятор приходит к выводу: некоторые элементы нужно выбросить, они больше не нужны. Если элемент находится на вершине стека, то такая конструкция преобразуется в drop, но если это не так, транслятор вначале осуществляет перестановку элементов стека, чтобы мусор очутился на вершине стека, после чего будет применён drop. Надо ли говорить, как такая запись облегчает жизнь программисту в том случае, если нужно удалить, скажем, два элемента из середины стека. Пусть транслятор сам решает, как это лучше сделать, программист лишь описывает то, что ему нужно.
3. [a b -> b a]
Такие выражения означают перестановку элементов: количество элементов слева и справа от слова -> одинаково и сами элементы одни и те же. Остаётся лишь подобрать оптимальную схему перестановки. Пусть это делает машина, люди уж так устроены, что длинные цепочки over swap drop rot вводят их в ступор.
4. [a b -> a a b b]
Число элементов слева меньше числа элементов справа. Это говорит о том, что некоторые элементы нужно дублировать. А вот что это за элементы и в каком порядке они должны располагаться, пусть решает транслятор. Человеку мыслить в терминах swap dup rot dup неудобно.
5. [a b -> a b]
Ничего не изменилось, чисто описательная конструкция. Пример применения дан ниже.

Естественно, в таких декларативных выражениях можно использовать и обычные комментарии:

dup rot +
[a b -> a b (a + b)]

Опишем некоторые слова Форта в новой форме:

define dup [x]
    [x -> x x]
end

define drop [x]
    [x -> ]
end

define swap [x y]
    [x y -> y x]
end

define over [x y z]
    [x y -> x y x]
end

define rot [x y z]
    [x y z -> y z x]
end

Проблема четвёртая: числа с плавающей запятой

Представим себе стек, состоящий из 32-битных ячеек, в которых хранятся целые числа. Всем такой стек хорош: и скоростью арифметических операций, и удобством работы с адресами переменных. Но если нам нужно умножить 3.14 на 4? Куда поместить дробное число? Если организовать стек как совокупность 64-разрядных ячеек, в которых хранятся числа с плавающей запятой и хранить целые числа как дробные с нулевой дробной частью, то сразу же испаряются такие достоинства, как скорость арифметических операций.

Введём второй стек для чисел с плавающей запятой. Ячейки в нём будут, скажем, 64-разрядные, но их будет меньше. Все числа без точки кладутся на вершин целочисленного (integer) стека, а все числа с точкой (пусть и с нулевой дробной частью) хранятся в дробном (float) стеке. То есть мы можем умножить упоминаемые числа следующим образом:

4.0 3.14 *f

где *f умножает дробные числа (аналогично +f, -f и так далее).

Введём также новое декларативное выражение:
[стек: a b c -> стек: a b c]
Которое берёт элементы из одного стека и помещает их в другой:

4 5
[integer: z1 z2 -> float: z1 z2]
2 times print-float end-times

В дробном стеке появятся числа 4.0 и 5.0. Обратная операция «обрубает» дробную часть.
Определим новые слова:

define integer->float [x]
    [integer: x -> float: x]
end

define float->integer [x]
    [float: x -> intger: x]
end

Аналогично и со стеком возвратов (return stack).

Пост получился довольно объёмным и местами спорным, поэтому значительная часть материала будет во второй части. Опять же таки, идеи и критика из обсуждения скорректируют план написания.

Автор: kedoki

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js