Введение в теорию программирования. Функциональный подход


Вступительная лекция - часть 4


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

Ключевым элементом реализации языков функционального программирования являются рекурсивные вычисления, т.е. вычисления, основанные на применении функции к самой себе как к аргументу.

Принципиальная реализуемость рекурсии средствами математической теории была доказана С. Клини (S.C. Kleene) еще в 30-х годах. При этом фундаментом рассуждений служило ламбда-исчисление.

В 50-х годах появилась комбинаторная логика Х. Карри – более приближенная к практике программирования формальная система с возможностью моделирования рекурсии.

Вскоре, в 60-х годах, Джоном Маккарти (John McCarthy) в ходе создания языка функционального программирования LISP, была исследована практическая применимость рекурсивных вычислений для символьной обработки и доказана возможность реализации рекурсии в программировании.

Абстрактная машина как формальная модель вычислительной системы является весьма важным объектом исследования в рамках настоящего курса.

Еще в 30-х годах А. Тьюрингом (Alan Mathison Turing) и Э. Постом (Emil Leon Post) независимо друг от друга были созданы эквивалентные по возможностям, но практически весьма сложные в реализации формализации, известные как абстрактные машины и получившие названия по именам своих авторов.

Комбинаторная логика Х. Карри позволяет моделировать вычисления в среде абстрактных машин, в значительной мере схожих с виртуальной машиной .NET.

В 60-х годах Д. Тернер (David Turner) предложил применять комбинаторы в качестве низкоуровневого кода для трансляторов языков функционального программирования, т.е. предвосхитил появление абстрактных машин, использующих в качестве инструкций комбинаторы.

Также в 60-х годах П. Лендин создал первую практически реализуемую абстрактную машину на основе расширенного ламбда-исчисления. Машина, получившая название SECD, формализовала вычисления на языке программирования ISWIM (If you See What I Mean), который впоследствии стал прообразом языка функционального программирования ML.


Начало  Назад  Вперед



Книжный магазин