Велосипедостроєнія : старі нові ідеї , про які варто знати

Нижче - конспект мого виступу на 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

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

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

на зорі розвитку обчислювальної техніки виглядало більш природно.

( Тут записано обчислення у- координати кульки, яка рухається в замкнутому просторі і відбивається від стінок ) . Повністю приклад наведено у .

Мало не будь-яка фізична явище може бути записано як набір диференціальних рівнянь в приватних похідних - і ми можемо скласти електричну схему , яка буде ці диференціальне рівняння відтворювати . У якійсь мірі таке подання програм більш високорівневих - тут не обчислюються значення одних змінних на основі інших , а відразу задається зв'язок . Зміна одного параметра призводить до автоматичної зміни залежних значень .

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

Звичайно, у АВМ були й недоліки :
- не всі завдання представіми в подібному вигляді ;
- втрати точності при масштабуванні ;
- програмуючи завдання, треба було фізично перекомутувати підсилювачі ( руками).

Пік розвитку аналогових ЕОМ припав на 60 -ті роки минулого сторіччя , зараз гібридні схеми також застосовуються в деяких областях , пов'язаних з робототехнікою і квантовими обчисленнями.

Повернемося до нашого прикладу :

int _ = 10 ; int _ = 0 ; for ( int _ = 1 ; _

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

0 10 1 DO i + LOOP ;

Це вираз , еквівалентний наведеному вище циклу , на мові Форт . Форт - пропозицію можна представити як функції над стекової машиною. Просто літерал кладе число в стек , операції беруть аргументи з стека і кладуть замість них результат застосування . Спеціальний оператор - « . » Виймає з стека верхній елемент і його друкує :

2 березень + .

надрукує нам 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 компілятора. Ось фрагмент із стандартної бібліотеки :

macro dowhile ( cond , body )
  syntax ( " do " , body , " while " , "(" , cond , " ) " )
  {
    def loop = Nemerle.Macros.Symbol ( Util.tmpname ( " do_while " ))
    
  }

Тут вираз всередині дужок - генерується під час компіляції і вставляється в тіло програми . Більшість керуючих структур в Nemerle визначені як макроси.

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

Разом - очевидність мейнстріму оманлива. Це просто один з багатьох можливих способів розробки , прийнятий саме зараз і в чому з випадкових причин . Якщо ви розробляєте програмне забезпечення і відчуваєте потребу у розширенні кругозору , то вам варто ознайомитися з найбільш примітними підходами , існуючими поза мейнстріму. Це схемотехніка , Forth , щось засноване на переписувальних правилах , Tcl , щось з макросами ( Nemerle , Scala ) - не обов'язково для прямого використання , а скоріше для розуміння можливого спектру ідей. Після того , як ви прочитаєте інтерпретатор Tcl , ви не зможете дивитися на світ як і раніше .

Опубліковано: 11/10/13 @ 11:42
Розділ Різне

SEO Блог

Велосипедостроєнія : старі нові ідеї , про які варто знати

Рекомендуємо: