Огляд мови. У чистій мові 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.

4.4.4. Оцінка

Мова 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))