λ-Абстракции
В некоторых случаях осознанное усвоение концепций даже на самом низком уровне нереально без базовых теоретических сведений. А знакомство с таким базисом, в свою очередь, стимулирует значительно более глубокий интерес к теории и способствует пониманию того, что на высшие уровни знаний и умений не подняться без овладения теорией.
Теоретической основой языка LISP является логика функциональности: комбинаторная логика или (по наименованию одного из основных понятий в наиболее популярной из нынешних ее формализаций) λ-исчисление.
В λ-исчислении выразительные средства, на первый взгляд, крайне скупы. Имеются две базисные операции: применение функции к аргументу (λx) и квантор образования функции по выражению λx t[x]. В терминах λ-исчисления функция возведения числа в квадрат записывается как λx (sqrx) или, если быть ближе к обычным математическим обозначениям, λx x2.
Основная операция - символьное вычисление применения функции к аргументу: (λx t[x] u) преобразуется в t[u]. Но эта операция может применяться в любом месте выражения, так что никакая конкретная дисциплина вычислений не фиксируется. Более того, функции могут вычисляться точно так же, как аргументы. Уже эта маленькая тонкость приводит к принципиальному расширению возможностей λ-исчисления по сравнению с обычными вызовами процедур. Если мы желаем ограничиться лишь ею, рассматривается типизированное λ-исчисление, в котором, как принято в большинстве современных систем программирования, значения строго разделены по типам. В типизированном λ-исчислении есть только типы функций, но этого хватает, поскольку функции могут принимать в качестве параметров и выдавать функции.
Но в исходной своей форме λ-исчисление является нетипизированным, любой объект может быть и функцией, и аргументом, и, более того, функция может применяться к самой себе. Конечно же, при этом появляется возможность зацикливания, но без нее не обойдется ни одна алгоритмическая система. Например, выражение
(λx (xx) λx (xx))
вычисляется бесконечно, а чуть более сложное выражение
((λx λy x a) (λx (xx) λx (xx)))
может либо дать a, либо зациклиться, в зависимости от выбора порядка его вычисления. Но все равно, если мы приходим к результату, то он определяется однозначно. Так что совместность вычислений не портит однозначности, если язык хорошо сконструирован.
Дж. Маккарти перенес идеи λ-исчисления в программирование, не потеряв практически ничего из исходных концепций. Далее, он заметил, что в рудиментарном виде в λ-исчислении появилось понятие списка, и перенес списки в качестве основных структур данных в свой язык. λ-исчислением было навеяно и соглашение языка LISP о том, что первый член списка трактуется как функция, применяемая к остальным.
