Витоки робіт в області штучного інтелекту та обробка списків

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

Концепція обробки списків була розроблена Алленом Ньюелом (Allen Newell), Дж. Шоу (J. С. Shaw) і Гербертом Саймоном (Herbert Simon). Вперше вона була опублікована в класичній роботі, яка описувала одну з перших програм штучного інтелекту, програму Logical Theorist, а також мову, якою вона могла б бути реалізована (Newell and Simon, 1956). Мова, названа IPL-I (Information Processing Language — мова обробки інформації), ніколи не була впроваджена. Наступна версія цієї мови IPL-II була реалізована на комп'ютері Johnniac корпорації Rand Corporation. Розвиток мови IPL продовжувався до 1960 року, коли був опублікований опис мови IPL-V (Newell and Tonge, 1960). Широкому поширенню мов сімейства IPL заважав їхній низький рівень. Для гіпотетичного комп'ютера, реалізованого за допомогою інтерпретаторів, з включеними в нього командами обробки списків, ці мови фактично були мовами ассемблера. Перша їхня реалізація була виконана на нічим не примітній машині Johnniac, що також не дуже сприяло поширенню мов сімейства IPL.

Внеском мов сімейства IPL у розвиток мов програмування були їхні спискові структури і наочна демонстрація того, що обробка списків цілком можлива і корисна.

Корпорація IBM зацікавилася штучним інтелектом у середині 1950-х років і як демонстраційну область вибрала доказ теорем. У той час повним ходом йшла розробка мови FORTRAN. Висока вартість компілятора мови FORTRAN I переконала корпорацію IBM у тім, що обробку списків простіше приєднати до мови FORTRAN, ніж виділяти її в окрему мову. Так і виникла мова FLTP (FORTRAN List Processing Language — мова обробки списків на базі мови FORTRAN), розроблена і реалізована як розширення мови FORTRAN. Мова FLPL використовувався для доказу теорем в області планіметрії, яку тоді розглядали як найпростішу область для механічного доказу теорем.

Процес розробки мови LISP

Улітку 1958 року відділом інформаційних досліджень корпорації IBM (IBM Information Research Department) був найнятий Джон Мак-Карті (John McCarthy) з інституту MIT. Його метою на це літо було дослідження символьних обчислень і розробка конструктивних вимог для проведення подібних обчислень. Пробною проблемною областю він вибрав диференціювання алгебраїчних виразів. Під час вивчення цієї області з'явився набір вимог до мови. Серед них були методи керування виконанням математичних функцій: рекурсія й умовні вирази. Мова FORTRAN I, єдина на той час мова високого рівня, не мала жодної з цих функцій.

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

Оскільки мова FLPL не підтримувала рекурсію, умовні вирази, динамічне виділення пам'яті чи неявне її звільнення, Мак-Карті зрозумів, що потрібна нова мова.

Коли восени 1958 року Мак-Карті повернувся в інститут MIT, він разом з Марвіном Мінскі (Marvin Minsky) заснував проект, присвячений штучному інтелекту, MIT AI Project, що фінансувався Дослідницькою електротехнічною лабораторією (Research Laboratory for Electronics). Першою важливою роботою нового проекту було створення системи обробки списків. Її планувалося використовувати для первісної реалізації програми під назвою Advice Taker, яку запропонував Мак-Карті. Цей додаток став стимулом до розвитку мови обробки списків LISP. Першу версію цієї мови іноді називають чистою мовою LISP, оскільки вона є мовою функціонального програмування в чистому вигляді. Еволюція чистої мови LISP описана в наступному розділі.

Огляд мови

4.4.3.1. Структури даних

У чистій мові LISP існувало тільки два типи структур даних: атоми і списки. Атоми могли бути або символами, що приймали форму ідентифікаторів, або числовими константами. Природно використовувати для збереження символьної інформації зв'язні списки, що і було зроблено в мові IPL-II. Подібні структури дозволяють вставки і видалення в будь-якому місці (операції, що тоді вважалися невід'ємною частиною обробки списків). Правда, зрештою було виявлено, що подібні речі в мові LISP потрібні дуже рідко.

Списки визначалися шляхом розмежування складових їхніх елементів круглими дужками. Прості списки, у яких елементи розділені на атоми, мають наступну форму:

(А В С D)

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

(A (B C) D (E (F G)))

складається з чотирьох елементів. Перший ‑ це атом А, другий ‑ підсписок (B C), третій ‑ атом D, а четвертий ‑ підсписок (Е (F G)), що містить як другий елемент підсписок (F G).

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

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

4.4.3.2. Процеси у функціональному програмуванні

Мова LISP створювалася як мова функціонального програмування. Всі обчислення у функціональній програмі виконуюються шляхом застосування функцій до аргументів. Ні оператори присвоєння, ні змінні, з надлишком наявні в імперативних мовах програмування, не потрібні в програмах, написаних на мовах функціонального програмування. Більш того, ітеративні процеси можуть визначатися за допомогою рекурсивних викликів функцій, що робить непотрібними цикли. Ці основні концепції функціонального програмування відрізняють його від програмування на імперативних мовах.

4.4.3.3. Синтаксис мови LISP

Мова LISP значно відрізняється від імперативних мов через те, що вона, по-перше, є функціональною мовою, по-друге, через те, що програми, написані цією мовою, виглядають зовсім інакше, ніж програми, написані на таких мовах, як FORTRAN чи C. Синтаксис мови C, наприклад, є складною сумішшю англійської та алгебри, тоді як синтаксис мови LIST — еталон простоти. Розглянемо знову список

(А В С D)

Якщо інтерпретувати його в термінах даних, то це— список з чотирьох елементів. Якщо ж розглядати його як програму, то це значить, що функція А застосовується до трьох параметрів: B, С і D.

Оцінка

Мова LISP повністю домінувала у сфері штучного інтелекту чверть сторіччя, і усе ще залишається найбільш розповсюдженою мовою в цій області. Більшість моментів, що створили мові LISP репутацію неефективної, були виправлені. Скомпільовано багато сучасних реалізацій, і результуючі програми виконуються значно швидше, ніж інтерпретація їхнього вихідного коду. Крім успіхів в області штучного інтелекту, мова LISP виявилась піонером функціонального програмування, яке довело свою життєздатність як область дослідження мов програмування. Як вказувалося в главі 1, багато дослідників мов програмування думають, що функціональне програмування значно краще підходить для розробки програмного забезпечення, ніж використання імперативних мов.

Протягом 1970-х і на початку 1980-х років було розроблено і використовувалось безліч різних діалектів мови LISP. Це привело до знайомої проблеми перенесення. Для виправлення такої ситуації була створена стандартна версія мови, названа COMMON LISP (Steele, 1984).

Докладно мова Scheme (діалект мови LISP) і функціональне програмування в цілому розглянуті в главі 14. Розглянемо приклад функції мови LISP

Наступна програма визначає предикативну функцію мови LISP, аргументами якої є два списки. Функція повертає значення TRUE, якщо обидва списки ідентичні, і значення NIL (FALSE) в іншому випадку

(DEFUN equal_list (lisl lis2) (COND

((ATOM lis1)' (EQ lis1 lis2))

((ATOM lis2) NIL)

((equal_list (CAR lis1) (CAR lis2))

(equal_list (CDR lis1) (CDR lis2)))

(T NIL))

Два нащадки мови LISP

У наш час широко використовуються два діалекти мови LISP — мова COMMON LISP і мова Scheme. Обидві коротко розглянуті в наступних підрозділах.

4.4.5.1. Мова Scheme

Мова Scheme була розроблена в інституті MIT у середині 1970-х років (Sussman and Steele, 1975). Для неї характерний невеликий розмір, використання винятково статичного огляду даних (розглянутого в главі 4), а також обробка функцій як об'єктів першого класу. Таким чином, функції мови Scheme можуть бути значеннями виразів і елементами в списках, присвоюватись змінним, передаватися як параметри і повертатися як результат застосування функції до своїх аргументів. У ранніх версіях мови LISP усіх цих можливостей не було, крім того, у них не використовувався статичний огляд даних.

Як невелика мова з простими синтаксисом і семантикою мова Scheme цілком придатна для таких навчальних додатків, як курси функціонального програмування і загальні вступні курси програмування. Докладніше мова Scheme описується в главі 14.

4.4.5.2. Мова COMMON LISP

Мова COMMON LISP (Steele, 1984) була створена у спробі об'єднати в одній мові властивості декількох діалектів мови LISP, розроблених на початку 1980-х років, у тому числі і мови Scheme. Будучи такою комбінацією, мова COMMON LISP являє собою велику і складну структуру. Проте його основою є чиста мова LISP, так що його синтаксис, основні функції і принципова природа походять від цієї мови.

Визнавши гнучкість, забезпечувану динамічним оглядом даних, і простоту, надану статичним оглядом, розробники мови COMMON LISP використовували обидва способи. За замовчуванням використовується статичний огляд змінних, але якщо оголосити змінну як special, її область видимості стає динамічною.

Мова COMMON LISP містить велику кількість типів і структур даних, серед яких записи, масиви, комплексні числа і рядки символів. Також у ній є форма пакетів, яка використовується, щоб зібрати в єдине ціле набору функцій і даних, яка забезпечує, таким чином, керування доступом.

До мови COMMON LISP ми ще повернемося в главі 14.

Споріднені мови

Мова ML (Metalanguage) була створена у 1980-х роках Робіном Мілнером (Robin Milner) у Единбурзькому університеті як метамова для системи верифікації програм, що називалася Logic for Computable Function (LCF) (Milner at al., 1990). Головним чином, мова ML — це мова функціонального програмування, але вона підтримує також імперативне програмування. У мові ML функції є більш загальними, ніж в імперативних мовах: вони передаються між підпрограмами як параметри, можуть бути поліморфними, що означає можливість одержання параметрів різних типів при різних викликах. На відміну від мов LISP і Scheme, тип кожної змінний і кожного виразу мови ML може визначатися в процесі компіляції. Типи зв'язуються з об'єктами, а не з іменами. Типи виразів логічно виводяться з контексту виразів, як це показано в главі 6.

На відміну від мов LISP і Scheme, мова ML не використовує функціональний синтаксис з дужками, який виник разом з лямбда-виразами. Синтаксис мови ML скоріше схожий на синтаксис таких імперативних мов, як Pascal і C.

Мова Miranda була розроблена Девідом Тернером (David Turner) в Університеті Кента в Кентербері, Великобританія (University of Kent in Canterbury), на початку 1980-x (Turner, 1986). Ця мова частково основана на мовах ML, SASL і KRC. Мова Miranda значною мірою стала базою для створення мови Haskell (Hudak and Fasel, 1992), яка подібно мові Miranda, є чисто функціональною мовою, тобто не містить ні змінних, ні операторів присвоєння. Ще однією характерною рисою мови Haskell є використання "ледачого" обчислення. Жоден вираз не обчислюється доти, поки не буде потрібно його значення, що веде до декількох несподіваних можливостей мови.

Мови ML і Haskell коротко описуються в главі 14.