Введение

С момента своего возникновения комбинаторная логика и ламбда-исчисление были отнесены к “неклассическим” логиками. Дело заключается в том, что комбинаторная логика возникла в 1920-х гг., а ламбда-исчисление (λ-исчисление) – в 1940-х гг. как ветвь метаматематики с достаточно очерченным предназначением – дать основания математике (см. [8]). Это означает, что сконструировав требуемую ‘прикладную’ математическую теорию – предметную теорию, – которая отражает процессы или явления в реальной внешней среде, можно воспользоваться ‘чистой’ метатеорией как оболочкой для выяснения возможностей и свойств предметной теории.

Комбинаторная логика и ламбда-исчисление – это такие формальные системы, в которых центральной разрабатываемой сущностью является представление об объекте. В первой из них – комбинаторной логике, – механизм связывания переменных в явном виде отсутствует, а во второй он имеется. Наличие явного механизма связывания предполагает и наличие связанных переменных, но тогда есть и свободные переменные, а также механизмы замещения формальных параметров – связанных переменных, – на фактические параметры, то есть подстановка.

Изначальным назначением комбинаторной логики был именно анализ процесса подстановки. В качестве ее сущностей планировалось использовать объекты в виде комбинаций констант. Ламбда-исчислению отводилась роль средства уточнения представлений об алгоритме и вычислимости. Как следствие, комбинаторная логика дает в руки инструмент для анализа процесса подстановки. Через короткий промежуток времени оказалось, что обе эти системы можно рассматривать как языки программирования (см. [1], [9], а также книгу [4] и библиографию к ней).

В обеих системах исчисляются объекты, они являются исчислениями или языками высших порядков, то есть имеются средства описания отображений или операторов, которые определяются на отображениях или операторах, а в качестве результата вырабатывают также отображения или операторы. Самое существенное, что именно отображение считается объектом. В этом их принципиальное отличие от всего многообразия других систем, в которых первичной сущностью обычно считают представление о множестве и его элементах.

К настоящему времени оба эти языка не только стали основой для всей массы исследований в области computer science, но и широко используются в теории программирования. Развитие вычислительной мощности компьютеров привело к автоматизации значительной части теоретического – логического и математического, – знания, а комбинаторная логика вместе с ламбда-исчислением признаются основой для рассуждений в терминах объектов (см. [6], [7]).

Без овладения их методами нельзя полноценно развить базовую технику вычислений с объектами, поскольку все еще распространенный в объектных языках программирования и проектирования теоретико-множественный стиль заставляет вязнуть в обилии второстепенных деталей, упуская из виду действительно существенные моменты взаимодействия объектов.