4.4. Функціональне програмування: мова lisp

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

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

Інтерес до штучного інтелекту почав з'являтися в середині 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 використовувався для доказу теорем в області планіметрії, яку тоді розглядали як найпростішу область для механічного доказу теорем.

4.4.2. Процес розробки мови 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 описана в наступному розділі.