 |
Организация вычислений в языке функционального программирования
|
|
|
|
Парадигмы программирования
Парадигма программирования — это система идей и понятий, определяющих стиль написания компьютерных программ. Все парадигмы – всего лишь различные инструменты, которые можно использовать при программировании. Выделяют программирование:
· императивное (процедурное)
o операциональное (ассемблер, фортран, basic);
o структурное (Pascal, Modula);
· непроцедурное:
o декларативное;
§ функциональное(Lisp, Haskell);
§ логическое (Prolog);
· объектное (объектно-ориентированное) (C++, SmallTalk, Delphi, VB).
Императивное программирование – описывает процесс вычисления в виде инструкций, изменяющих состояние программы. Императивная программа – это последовательность команд, которые должен выполнить компьютер. При императивном программировании состоянием вычислительного устройства будут указатель текущей инструкции, значения всех используемых программой ячеек памяти, и состояние стека возвратов из подпрограмм. Исполнение каждого оператора тривиальным образом записывается как изменение этого "состояния вычислителя".
Объектное (объектно-ориентированное) программирование – парадигма программирования, в которой основными концепциями являются понятия объектов и классов. В ООП все (процессы, данные, события) является объектами. Все объекты располагают собственными данными, представленными как ссылки на другие объекты. Объекты могут обмениваться между собой сообщениями. При получении объектом сообщения запускается соответствующий ему обработчик, иначе называемый методом. У объекта есть объект-предок. Если метод для обработки сообщения не найден, сообщение будет перенаправлено объекту-предку. Эту структуру в целом (таблица обработчиков + предки) выделяют в класс объекта. У самого объекта будет ссылка на объект, представляющий его класс. Объект по отношению к своему классу является экземпляром. Так как классы тоже представлены, как объекты, существует класс, определяющий поведение, общее для всех классов. Такой класс принято называть метаклассом.
|
|
|
1. Объекты не могут непосредственно работать с собственными данными другими объектами ине могут нарушить их внутреннюю согласованность. Это свойство (сокрытие данных) принято называть инкапсуляцией.
2. Объекты взаимодействуют исключительно засчет обмена сообщениями и не могут ничего не знать о реализации обработчиков сообщений друг у друга. Взаимодействие происходит исключительно в терминах сообщений/событий, которые достаточно легко привязать к предметной области. Это свойство (описание взаимодействия исключительно в терминах предметной области) называют абстракцией.
3. Если в каком-либо сценарии взаимодействия объектов заменить произвольный объект другим, способным обрабатывать те же сообщения, сценарий так же будет реализуем. Это свойство (возможность подмены объекта другим объектом со сходной структурой класса) называется полиморфизмом.
Отношение "потомок-предок" на классах принято называть наследованием.
Функциональное программирование – парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в их математическом понимании (в отличие от функций как подпрограмм в процедурном программировании).
Функциональное программирование предполагает обходиться вычислением результатов функций от исходных данных и результатов других функций, и не предполагает явного хранения состояния программы. В функциональном программировании понятие времени отсутствует. Программы являются выражениями, исполнение программ заключается в вычислении этих выражений. Функциональное программирование основано на лямбда-исчислении Черча. Константами в лямбда-исчислении могут быть числа, кортежи, списки, имена предопределенных функций, и так далее.
|
|
|
Функциональное программирование обладает следующими двумя примечательными свойствами:
1. аппликативность: программа есть выражение, составленное из применения функций к аргументам;
2. настраиваемость: так как программа и любой программный объект (в идеале) является выражением, можно легко порождать новые программные объекты по образцу, как значения соответствующих выражений.
Порядок вычисления подвыражений не имеет значения (т.к. нет понятия «состояния»), функциональное программирование может быть естественным образом реализовано на платформах, поддерживающих параллелизм. Функциональное программирование, как и другие модели "неимперативного" программирования, обычно применяется для решения задач, которые трудно сформулировать в терминах последовательных операций. Практически все задачи, связанные с искусственным интеллектом, попадают в эту категорию. Среди них следует отметить задачи распознавания образов, общение с пользователем на естественном языке, реализацию экспертных систем, автоматизированное доказательство теорем, символьные вычисления.
Логическое программирование – парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.В логическом программировании программа представляет из себя некоторую теорию (описанную на достаточно ограниченном языке), и утверждение, которое нужно доказать. В доказательстве этого утверждения и будет заключаться исполнение программы.Логическое программирование эффективно в реализации задач искусственного интеллекта. Логическое программирование является достаточно выразительным средством для описания сложных систем (диспетчерская система лондонского аэропорта Хитроу в настоящий момент переписывается на Прологе).
|
|
|
Организация вычислений в языке функционального программирования
Функциональное программирование объединяет разные подходы к определению процессов вычисления на основе достаточно строгих абстрактных понятий и методов символьной обработки данных. Функция рассматривается как общее базовое понятие, к которому достаточно естественно могут быть сведены все другие понятия, возникающие при программировании. Функциональное программирование предполагает обходиться вычислением результатов функций от исходных данных и результатов других функций, и не предполагает явного хранения состояния программы. Не предполагает оно и изменяемость этого состояния (в отличие от императивного, где одной из базовых концепций является переменная, хранящая своё значение и позволяющая менять его по мере выполнения алгоритма).
Отличие математической функции от понятия «функции» в императивном программировании заключается в том, что императивные функции могут опираться не только на аргументы, но и на состояние внешних по отношению к функции переменных, а также иметь побочные эффекты и менять состояние внешних переменных. В императивном программировании при вызове одной и той же функции с одинаковыми параметрами, но на разных этапах выполнения алгоритма, можно получить разные данные на выходе из-за влияния на функцию состояния переменных. В функциональном языке при вызове функции с одними и теми же аргументами мы всегда получим одинаковый результат: выходные данные зависят только от входных. Это позволяет средам выполнения программ на функциональных языках кешировать результаты функций и вызывать их в порядке, не определяемом алгоритмом и распараллеливать их без каких-либо дополнительных действий со стороны программиста.
Функция в математике не может изменить вызывающее её окружение и запомнить результаты своей работы, а только предоставляет результат вычисления функции. Программирование с использованием математического понятия функции вызывает некоторые трудности. Дополнительное отличие от императивных языков программирования заключается в декларативности описаний функций. Тексты программ на функциональных языках программирования описывают «как решить задачу», но не предписывают последовательность действий для решения.
|
|
|
В качестве основных свойств функциональных языков программирования обычно рассматриваются следующие:
· краткость и простота – программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языка;
· модульность – разделение программ на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними;
· функции — объекты вычисления;
· чистота (отсутствие побочных эффектов) – оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путем декомпозиции и синтеза существующих;
· 
отложенные (ленивые) вычисления – какой-либо аргумент вычисляется, только если он нужен для вычисления результата.
|
|
|
