Абстракция n Абстракция основана на u обобщении посредством введения имени вместо значения и u уточнении (конкретизации) посредством подстановки другого значения вместо данного имени n Абстрагирующее имя явно или неявно привязано к определенному типу значений. n Примеры: x:

Абстракция в императивных языках программирования n Переменная в ИП – синоним ячейки памяти n Компилятор абстрагирует связь имя-значение от конкретной ячейки памяти. n Типы данных контролируют корректность связи имя-значение. n Компилятор контролирует корректность размещения значения в той или иной ячейке памяти (выравнивание, тип выделяемой памяти)

Абстракция в императивных языках высокого уровня n Абстрактный тип данных u Представление данных скрыто от пользователя и может быть заменено альтернативным. u Любое из этих представлений должно реализовывать методы доступа к данным. u Эти методы доступа должны удовлетворять определенным инвариантам («законам»). n Пример: u «Маршрут» как АТД в системе управления транспортом: getStartingPoint, getEndingPoint, getDistance, … u Метод getDistance для составного маршрута должен удовлетворять неравенству треугольника

Абстракция в императивных языках высокого уровня n Модули n ООП u Инкапсуляция n Задание: u Придумать и написать на С++ заголовочный файл, реализующий абстрактный тип данных

Лямбда-исчисление n Алонсо Черч, 1930 г. n Модель «единицы вычислимости» n Представляет собой язык, основанный на «чистой» абстракции n Математическая модель абстракции u Сама абстракция становится объектом

Лямбда-выражение n Используем «форму Бэкуса» для задания синтаксиса u ::= | | n Имя – произвольный набор символов (не только «идентификатор») u фред u x1 u 12z u

Функция n Абстракция над лямбда-выражением u ::= λ. u ::= n Примеры: λx.x λfirst.λsecond.first λf.λa.(f a) n называется «связанной переменной». n Похоже на «формальный параметр» ИП n - произвольное лямбда-выражение, в т.ч. и другая функция. n Функция – безымянна!

n Применение функции к выражению n ::= ( ) n Примеры: n Терминология: u (Ф А) – «связанная пара» или «Ф применяется к А» Аппликация

Вычисление аппликации n ::= ( ) n 1. В функциональном выражении проводятся вычисления всех аппликаций, результат должен быть функцией n 2. В теле функции связанная переменная заменяется на u Результат вычисления выражения-аргумента u Само выражение-аргумент в «текстуальной» форме n Первый способ называется «аппликативный порядок» n Второй способ называется «нормальный порядок»

Тождественная функция n x слева – связанная переменная (имя, играющее роль связанной переменной) n x справа – имя n Аппликация тождественной функции возвращает выражение-аргумент. n При нормальном порядке вычисления аргумент возвращается невычисленным.

Каррирование функций n Рассмотрим пример: n Аппликация n дает n Функция многих переменных представляется как суперпозиция лямбда-функций. n «Каррирование» (currying) – в честь Хаскеля Карри (хотя придумал Шенфинкель).