An Algebraic Language for the Manipulation of Symbolic Expressions (1958) [pdf]
Эта работа представляет спецификацию алгебраического языка для манипуляции символьными выражениями, разработанного Джоном Маккарти. Язык предназначен для программирования формальных математических процессов (алгебраическое упрощение, дифференцирование, интегрирование), написания компиляторов (кроме ввода/вывода) и эвристических программ, где удобно представлять деревья альтернативных действий. Он особенно эффективен для работы с выражениями переменной длины и структуры, имеющими подобподвыражения, но менее удобен для списков фиксированной длины.
Выражения в языке представляются списками, где каждый элемент занимает машинное слово, содержащее данные и адрес следующего элемента. Маккарти отмечает, что удобство алгебраической нотации связано с возможностью композиции функций без именования промежуточных результатов и построения сложных структур путем вложения вызовов функций, формирующих списки. Ключевыми особенностями языка являются поддержка рекурсии с автоматическим сохранением промежуточных результатов в структурах списков и мощные условные выражения, решающие проблему выбора операций на основе результатов тестов. Маккарти ссылается на ранние работы Ньюэлла, Саймона и Шоу по эвристическому программированию и Гелентера в геометрической программе как предшественников.