Велосипедостроение: старые новые идеи, о которых стоит знать

Ниже — конспект моего выступления на OSDN-2013, который может представлять интерес для разработчиков ПО.

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

Очевидность мейнстрима — это скорее постаприорная иллюзия. Что бы это проиллюстрировать, возьмем что-то простое — к примеру, базовые конструкции языков программирования, и посмотрим на альтернативные подходы, которые по каким-то причинам так и не стали мейнстримом, но вошли в золотой фонд техник разработки.

j: lol where r u romeo
r: wana come over?
j: cant
r: y?
j: idk parents
r: lets kill ourself
j: lol k
r: swag
j: swag

Узнали кратко изложенный сюжет Шекспировского «Ромео и Джульеты»?.. Наш рассказ будет соответствовать оригинальным техникам приблизительно как данный твит — к оригинальной пьесе, но это лучше, чем ничего.

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

Пример выражения:

int n = 10;
int s = 0;
for(int x = 1; x < n; ++x) {
   s+=x;
}

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

Хотя следующее представление программы:

на заре развития вычислительной техники выглядело более естественно.

(Здесь записано вычисление у-координаты шарика, который движется в замкнутом пространстве и отражается от стенок). Полностью пример приведен в www.analogmuseum.org/...​h/examples/bouncing_ball.

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

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

Конечно, у АВМ были и недостатки:
— не все задачи представимы в подобном виде;
— потери точности при масштабировании;
— программируя задачу, надо было физически перекоммутировать усилители (руками).

Пик развития аналоговых ЭВМ пришелся на 60-ые годы прошлого столетия, сейчас гибридные схемы также применяются в некоторых областях, связанных с робототехникой и квантовыми вычислениями.

Вернемся к нашему примеру:

int _ = 10;
int _ = 0;
for(int _ = 1; _ < _; ++x) {
   _ += _;
}

Тут знаком подчеркивания заменены вхождения переменных, которые соответствуют выделенным блокам памяти. Так ли они нужны? Как будет выглядеть программирование без переменных:

0 10  1  DO  i +   LOOP;

Это выражение, эквивалентное приведенному выше циклу, на языке Форт. Форт-предложение можно представить как функции над стековой машиной. Просто литерал кладет число в стек, операции берут аргументы из стека и кладут вместо них результат применения. Специальный оператор — «.» вынимает из стека верхний элемент и его печатает:

2 3 + .

напечатает нам 5.

Набор операций над стеком мы можем собрать в слова. Давайте посмотрим на чуть более сложный пример:

: sqrt-closer  (square guess -- square guess adjustment) 2dup / over - 2 / ;
: sqrt ( square -- root ) 1 begin sqrt-closer dup while + repeat drop nip ;

Это функция вычисления квадратного корня, которое соответствует алгоритму

Как видите, комментарии (они в круглых скобках) занимают столько же места, сколько и сам код.

Одна из особенностей подобного стиля программирования — он вынуждает писать эффективный код, то есть спагетти с дублированием операций на нем сделать практически невозможно. Автору Форта Чарльзу Х. Муру приписывают следующие слова: «если вам нужны локальные переменные, значит ваш код неэффективен».

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

Он основал фирму Green Arrays, которая производит специализированные форт-процессоры — на одном чипе находятся 144 независимых интерпретатора polyForth, реализованных аппаратно.

Вернемся в наш мейнстрим и посмотрим на еще одну очевидность:

int x = 1
int d = 1
while(d != 0) {
    d = (s/x - x)/2
    x = x+d
}

Нам кажется очевидным, что инструкции выполняются последовательно, то есть сначала выполнится строка 1, потом строка 2, а потом, в зависимости от условия в третей строке, мы перейдем либо к телу цикла, либо к следующему оператору за ним. Обязательно ли это? Можем ли мы как-то просто сказать компьютеру, что делать, а он уже сам как-то выберет последовательность команд? Как будет выглядеть программирование без последовательности исполнения?

sqrtd(s,x,0) -> x  
sqrtd(s,x,d) -> sqrt(s, x+d, (s/x - x)/2 ) 

sqrt(s)  ->  sqrtd(s,1,(s-1)/2)

При входе sqrt(4) это выражение будет переписываться до тех пор, пока возможны редукции (то есть найдутся применимые правила).

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

Самая древняя реализация, имеющая скорее историческую ценность — это язык Refal; в Киеве, в Институте кибернетики, в свое время был разработан язык переписывающих правил APS (algebraic programming language) [сейчас в интернете уже невозможно найти упоминание о нем], автор этих строк в свое время, во многом по мотивам APS, сделал реализацию системы переписывающих правил на Java TermWare, сейчас есть проект следующей версии с внутренним Scala DSL, который очень медленно разрабатывается в свободное от другой деятельности время. Лидером рынка, если можно так выразиться, сейчас является Maude — им уже иногда пользуются как языком программирования общего назначения.

Так что последовательное выполнение команд — это тоже необязательное свойство.

Вернемся обратно к нашему мейнстримному примеру:

int x = 1
int d = 1
while(d != 0) {
    d = (s/x - x)/2
    x = x+d
}

Мы привыкли к тому, что управляющие конструкции заданы на уровне синтаксиса языка. Давайте посмотрим на следующий пример:

set x 1 
do {
   set d [expr  ($s/$x - $x)/2] 
while { $d != 0 }

Это наше выражение на языке Tcl. Казалось бы, ничего необычного, но: выражения do-while в Tcl нет. Его можно определить в самом языке приблизительно так:

proc do {body whileword condition} {
    global errorInfor errorCode
    if {![string equal $whileword while]} {
        error "should be \"do body while condition\""
    }
    while {1} {
        set code [catch {uplevel 1 $body} message]
         if { !ok( $code) } {
              return handleBreak($code, $body, $message)
           }
        }
        if {![uplevel 1 [list expr $condition]]} {break}
    }
}

Идея простая — раз у нас есть интерпретатор, так давайте дадим программисту доступ к API, позволяющему управлять выполнением текущей прогрмаммы. В Tcl есть волшебная функция [uplevel n block], обозначающая выполнение блока кода, который работает с контекстом (то есть набором локальных переменных) не текущего стека, а уровнем выше. То есть [uplevel { set d .... } ] присваивает значение локальной переменной d в той функции, из которой do был вызван.

Кстати, Tcl был де факто стандартом как язык для встраивания скриптинга в другие приложения. (Сейчас эту нишу занимает скорее всего Lua). Если у вас на ноутбуке юникс — скорее всего, там живет несколько экземпляров интерпретатора Tcl, встроенных в прикладные пакеты.

А если у нас не интерпретатор, а компилятор? Тогда мы можем дать программисту доступ к API компилятора. Вот фрагмент из стандартной библиотеки Nemerle:

macro dowhile (cond, body)
  syntax ("do", body, "while", "(", cond, ")")
  {
    def loop = Nemerle.Macros.Symbol (Util.tmpname ("do_while"))
    <[
     (($("_N_break" : global) : {
        def $(loop : name) () : void {
          ($("_N_continue" : global) : { $body }) : void;
          when ($cond)
            $(loop : name) ();
        }
        $(loop : name) ()
      }) : void)
    ]>
  }

Здесь выражение внутри скобок <[ .. ]> - генерируется во время компиляции и вставляется в тело программы. Большинство управляющих структур в Nemerle определены как макросы.

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

Итого — очевидность мейнстрима обманчива. Это просто один из многих возможные способов разработки, принятый именно сейчас и во многом по случайным причинам. Если вы разрабатываете программное обеспечение и чувствуете потребность в расширении кругозора, то вам стоит ознакомиться с наиболее примечательными подходами, существующими вне мейнстрима. Это схемотехника, Forth, что-то основанное на переписывающих правилах, Tcl, что-то с макросами (Nemerle, Scala) — не обязательно для прямого использования, а скорее для понимания возможного спектра идей. После того, как вы прочитаете интерпретатор Tcl, вы не сможете смотреть на мир по-прежнему.