Обзор парадигм программирования

План 1. Структурное программирование 2. Объектно-ориентированное программирование 3. Функциональное программирование 4. Логическое программирование 5. Стековое программирование

Математические модели вычислений Что можно посчитать имея вычислительную машину неограниченной мощности? Формальные модели вычислений: Машина Тьюринга λ-исчисление Чёрча Тезис Чёрча: «Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.»

Архитектура фон Неймана

1. Структурное программирование Пришло на смену неструктурированному программированию в начале 70-х Любая программа может быть представлена как комбинация последовательно исполняемых операторов ветвлений итераций Статья Дейкстры «Go To Statement Considered Harmful» (1968г)

Языки-представители Алгол Паскаль C Модула-2 Ада

Подробнее: Ада Разработан в начале 80-х по заказу минобороны США Особенности: Строгая типизация Минимум автоматических преобразований типов Встроенная поддержка параллелизма Реализация: GNAT (

2. Объектно-ориентированное программирование Первый ОО-язык – Симула-67, были и более ранние разработки Популярной методология стала только в середине 90-х Развитие связано с широким распространением графических интерфейсов и компьютерных игр

Основные концепции Программа представляет собой набор объектов Объекты взаимодействуют путём посылки сообщений по строго определённым интерфейсам Объекты имеют своё состояние и поведение Каждый объект является экземпляром некоего класса

Основные концепции (инкапсуляция) Инкапсуляция – сокрытие реализации от пользователя. Пользователь может взаимодействовать с объектом только через интерфейс. Позволяет менять реализацию объекта, не модифицируя код, который этот объект использует

Основные концепции (наследование) Наследование позволяет описать новый класс на основе существующего, наследуя его свойства и функциональность Наследование – отношение «является» между классами, с классом-наследником можно обращаться так же, как с классом- предком

Основные концепции (полиморфизм) Полиморфизм – классы-потомки могут изменять реализацию методов класса-предка, сохраняя их сигнатуру Клиенты могут работать с объектами класса- родителя, но вызываться будут методы класса-потомка (позднее связывание)

Пример кода class Animal { public: Animal(const string& _name) { name = _name; } virtual string talk() = 0; void rename(string newName); private: const string name; };

Пример кода (2) class Cat : public Animal { public: Cat(const string& name) : Animal(name) {} string talk() { return "Meow!"; } }; class Dog : public Animal { public: Dog(const string& name) : Animal(name) {} string talk() { return "Arf! Arf!"; } };

Языки-представители Java C++ Object Pascal / Delphi language Smalltalk

3. Функциональное программирование Вычисления рассматриваются как вычисления значения функций в математическом понимании (без побочных эффектов) Основано на λ-исчислении

λ-исчисление λ-исчисление основано на функциях λx.2*x+1 – функция x -> 2*x+1 Функции могут принимать функции в качестве параметров и возвращать функции в качестве результата Функция от n переменных может быть представлена, как функция от одной переменной, возвращающая функцию от n-1 переменной (карринг)

Языки-представители Лисп (LIst PRocessing) ML (OCaml) Haskell Erlang

Особенности Программы не имеют состояния и не имеют побочных эффектов Порядок вычислений не важен Циклы выражаются через рекурсию «Ленивые» вычисления Формальные преобразования программ по математическим законам

Что даёт ФП? Тестирование Отладка Параллелизм Горячая замена кода Машинные доказательства Оптимизация Ленивые вычисления

Примеры на языке Haskell Факториал: fact :: Integer -> Integer fact 0 = 1 fact n | n > 0 = n * fact (n - 1) QSort: sort [] = [] sort (pivot:rest) = sort [y | y

4. Логическое программирование Программа представляет собой набор фактов и правил, система сама строит решение с использованием правил логики Создавалось в 60-х для решения задач искусственного интеллекта и экспертных систем

Пролог Появился в 1972 г. как научная разработка Реализации: SWI-Prolog ( Amzi Prolog ( Turbo Prolog

Пример программы sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y). parent_child(X, Y) :- father_child(X, Y). parent_child(X, Y) :- mother_child(X, Y). mother_child(trude, sally). father_child(tom, sally). father_child(tom, erica). father_child(mike, tom).

Пример запроса ?- sibling(sally, erica). Yes ?- father_child(Father, Child).

Пример: быстрая сортировка partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs) :- ( Smalls = [X|Rest], partition(Xs, Pivot, Rest, Bigs) ; Bigs = [X|Rest], partition(Xs, Pivot, Smalls, Rest) ). quicksort([]) --> []. quicksort([X|Xs]) --> { partition(Xs, X, Smaller, Bigger) }, quicksort(Smaller), [X], quicksort(Bigger).

5. Стековое программирование Форт Разработан в 60-х Чарльзом Муром «для себя» Широко распространён для программирования встроенных систем и задач, естественным образом выражающихся в терминах стеков

Форт: подробнее Основной элемент программы: слово Форт-система состоит из словаря (набора слов) и стеков – арифметического и командного (с их помощью производятся вычисления) Используется обратная польская нотация

Примеры * Вывод: 300 ok : FLOOR5 ( n -- n' ) DUP 6 < IF DROP 5 ELSE 1 - THEN ; - то же самое на С++: int floor5(int v) { return v < 6 ? 5 : v - 1; } - более красиво на Форте: : FLOOR5 ( n -- n' ) 1- 5 MAX ; : HELLO ( -- ) CR." Hello, world!" ;

Реализации СП-Форт ( GP-Forth ( Огромное количество других реализаций ( Книга для знакомства с Фортом: Броуди Л. «Начальный курс программирования на Форте»