×Закрыть

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

Ниже — конспект моего выступления на 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, вы не сможете смотреть на мир по-прежнему.

LinkedIn

28 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.
int _ = 10;
int _ = 0;
for(int _ = 1; _ < _; ++x) {
   _ += _;
}
Одно вхождение х специально оставлено?
Хотя следующее представление программы:
на заре развития вычислительной техники выглядело более естественно.
ни в коем случае

хех, слишком радикальные вещи для неокрепшего разума.
я рассчитывал, будут отдельные концепции типа сигналов или аннотаций(которые были задолго до Java 1.5), а тут хардовые переменные да управление компилятором.
хорошо, хоть в очередном примере признал предикаты Пролога :)

На счет стековых машин — на Forth не писал, но не уверен, что это абстракция достаточно высокого уровня для написания промышленного кода.
Скажем, JVM — в своей основе стековая машина, но большинство языков под JVM предлагают что-то более высокоуровневое (объекты + классы + отношение наследования между классами), т.е. вручную скрывают «стековость».
.
На счет макросов Scala, доступа к Compiler API у Nemerle и трюков с Tcl — мое мнение, что доопределение синтаксиса языка — это путь к уникальности экосистемы у каждой команды. Что не хорошо, для промышленности, но приятно для старых программистов и болезненно для новых на проекте.
Как у каждой команды фактически свой диалект С++ (следствие мультипарадигменности в терминах Страуструпа), так сейчас у каждой команды свой диалект Scala. Думаю, для потенциального мейнстрима — это минус. Хотя, для развития мозга программиста — это плюс.
.
За примеры на Tcl/Forth/Nemerle — отдельное спасибо:).

Ну про forth мне тоже кажется, что каким-то образом что-то в него компилировать будет проще чем обучить мир на нем писать. Однако представим себе что какие-то числодробильные задачи (типа кластеризации на основе потоковых данных) можно будет решать на 10 машинках вместо 1000 — хм, вобще-то можно и выучить.

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

Хотя фрагментация тоже есть — в tcl долгое врем рядом жили incrTcl и XOTcl (и так как там свою объектно-ориентированную настройку сделать легко — с десяток известных пакетов определял еще свою собственную) — и вот только сейчас в 8.6 OOTcl внесли в core a incrTcl надстройку — в стандартную библиотеку. Возможно это замедлило распостранение языка когда все стало объектно ориентированным: ответ на вопрос — «есть ли в tcl объекты» не укладывался в «да/нет» а требовал «развернутого ответа» который часто не помещался в умы пользователей. apple-style языкам в этом смысле легче ;)

Спасибо за статью. Но позволю себе критику.

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

Да. Вы правы. Если пытаться быть точным — то надо сказать что-то вроде: «а некоторое подмножество систем уравнений в частных производных можно апрокисимировать системой обычных дифференциальных уравнений» а их уже в свою очередь можно составить из набора решающих элементов

> вхождения переменных, которые соответствуют выделенным блокам памяти
И давно локальные переменные живут не в стеке а в хипе?

Это ж как надо читать, чтобы найти понятие хипа в этой цитате... ;(

Тут наверное что-бы исключить такое понимание надо было написать «выделенные области памяти». То есть речь идет не о выделенном (как результате процесса выделения) блоке в хипе, а просто о выделенном = (отдельном от другим) области памяти где зранится переменная

Ох как вы подтверждаете всю тему статьи: scope переменной и ее allocation — вообще ортогональные вещи. И может быть по-всякому. В «мейнстриме» — в стеке, хотя я бы сказал, что чаще в регистрах, а в стеке — только, когда в регистрах никак.

PS. Еще уместно вспомнить про отличие variable и binding ...

Последний абзац колонки напомнил «The Future of Programming».

Все эти языки это конечно круто и они гораздо мощнее чем жава/с#/js, но заработать много-много денег легче на певрых. Возможно для каких-то очень специфичных исследовательских задач (или какого-нибудь сложного софта для железяк) форт и лисп сгодятся.

Очевидность этого утверждения также обманчива, как и описанная очевидность мейнстрима. По той же самой причине.

Если много-много денег — то точно не на java/c# Тут либо аутсорсинг [маржа небольшая но стабильная] либо зарабатывание денег на другом бизнесе, где ПО — не самая главная операционная составляющая. А именно много денег (или совсем ничего) — это как раз вне массовки. Пользуясь лексикой Талеба, можно сказать что массовые языки — это среднестан (где все понятно и зависимость денег от языка, опыта итд — описывается распределением Гаусса с коротким хвостом около стеклянного потолка) а остальное — дикий крайнестан, где чаще встречается что-то типа распределения Коши

дикий крайнестан, где чаще встречается что-то типа распределения Коши
Нихрена подобного, ты хоть и взрослый дядька, а мечататель еще тот, где продукты/приложения на форте/лиспе/tcl/хаскелль которые перевернули мир? Я спрашиваю, где?
Вот unix написанный на C мир перевернул, Ruby on Rails перевернул, современные комппютерные игры с таким крутым графоном появились благодоря С++. Да и джава, которой ты пользуешься каждый раз когда звонишь ( на симках), гуглишь что-либо, проводишь платежи, снимаешь деньги с банкомата, тоже перевернула мир. Даже PHP и тот оказал очень весомое влияние на мир. А почему?
А потому что все равно на чем написанно приложение, главное идея которое оно воплощает.

Слушайте, ну автор написал статью, сделал доброе дело, зачем же сразу впадать в такой низкий стиль

Нихрена подобного
хоть и взрослый дядька
Я спрашиваю, где?
?

Слишком уж категоричный автор. Но да, я наверное погорячился.

Все правильно, кому нужны булгаковы с достоевскими, когда есть «Дом-2» и «Менты».

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

Вот это поворот! ©

Все эти языки это конечно круто и они гораздо мощнее чем жава/с#/js, но заработать много-много денег легче на певрых.
В тех примерах, который я видел в Харькове, за Scala платят ровно столько, сколько и за Java.

Спасибо, Руслан, интересная статья. Вы на Forth писали? Интересно ваше мнение в отношении Factor, почему многообещающий современный гибрид Lisp и Forth застыл в разработке?

А Слава нынче в гугле пилит всякие драйвера, на фактор ведь время нужно...

Еще APL. Чтение исходников интерпретатора J (www.jsoftware.com/source.htm) меняет мир не хуже приема LSD.

Во всяком случае, приведенный пример

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

на J — это просто:

+/i.10

Кратко, и, тк скзть, со вкусом.

Странно, что во всей этой статье нет ни одного упоминания лиспов.

Lisp, Scheme, Clojure

FTFY.

Да, за кадром остались многое, для обзора хотя-бы частично претендующего на полноту — надо еще о Lisp с товарищам, Prolog, Smalltalk и .... наверное Simula — еще надо бы о ATD .. — тогда начать бы с МL .... (сейчас остался OCaml) .. — ну короче понятно что тут маленькая выборка ...

Подписаться на комментарии