3.6. Алгебраїчна парадигма

Дані представляються за допомогою термів або позначених графів, а алгоритми - системами правил переписування (орієнтованих рівностей чи умовних рівностей, співвідношень алгебри даних). Об’єкт, який визначається системою рівностей, за допомогою яких виражаються правила переписування, є відношенням конгруентності на множині всіх термів абсолютно вільної алгебри термів, що породжується константами. Це відношення визначається як конгруентне замикання співвідношень переписування, які розглядаються як тотожності алгебри термів.

Елементарним кроком обчислень в алгебраїчній парадигмі є мeтчінг (відповідність зразку), перевірка умов і підстановка. Стратегія переписування визначає, в якому порядку застосовуються правила переписування і підтерми (підвирази) поточного терма для співставлення з лівими частинами співвідношень. Для канонічних систем правил переписування результат не залежить від стратегії. Якщо система правил не є канонічною, то стратегія визначає не тільки час переписування, але й результат. В будь-якому випадку результат переписування, за умови закінчення обчислень, є термом, який еквівалентний висхідному термові за відношенням конгруен­тності, що визначається системою правил переписування. Тобто, стратегія вибирає результат в класі конгруентних термін. Відповідна алгебраїчна програма обчислення НСД наведена нижче.

RS(х,у) (

(x, х) = x,

(х > у) ((x, у) = (х - у, у)),

(x < у) ((x у) = (x, у - х))

).

Висновок

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

алгоритм = означення + стратегія обчислень,

яку можна доповнити відомою формулою Вірта

програма = алгоритм + структури даних.

Лекція 4. Огляд основних мов програмування

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

4.1. Мова Picmkalkul Конрада Цузе

Перша з мов обговорення у деякій мірі досить незвичайна. По-перше, вона ніколи не була реалізована. Більш того, хоча вона була розроблена у 1945 році, її опис не публікувався аж до 1972 року. Через загальне ігнорування мови Plankalktll деякі її можливості не використовувалися в інших мовах програмування протягом 15 років після її розробки.

4.1.1. Історичні передумови

Між 1936 і 1945 роками німецький учений Конрад Цузе (Konrad Zuse) на основі електромеханічних реле створив ряд складних і витончених комп'ютерів. До 1945 року війна призвела до руйнування всіх цих комп'ютерів, за винятком однієї з останніх моделей— комп'ютера Z4. Цузе відправився у віддалене баварське селище Хинтерштейн (Hinterstein), а інші члени його дослідницької групи роз'їхалися в різні сторони.

Працюючи самостійно, Цузе направив свої зусилля на розробку мови для вираження обчислень, продовживши проект, початий ним у 1943 році з метою написання докторської дисертації. Нову мову він назвав Plankalkul, що означає "програмне числення". В об'ємному рукописі, датованому 1945 роком, але не опублікуваній до 1972 року (Zuse, 1972), Цузе дав визначення мови Plankalkul і використовував цю мову для написання алгоритмів розв’язку безлічі задач.