1. История функционального программирования. Основные свойства функциональных языков



Скачать 208.29 Kb.
Дата09.05.2013
Размер208.29 Kb.
ТипДокументы
1. История функционального программирования. Основные свойства функциональных языков. Некоторые языки функционального программирования
Как известно, теоретические основы императивного программирования были заложены ещё в 1930-х годах Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Мозеса Шёнфинкеля и Хаскелла Карри, разработавших комбинаторную логику, и Алонзо Чёрча, создателя λ-исчисления. λ-возникло как из подходов формализации понятия алгоритма через бесчисленные функции и рекурсивные вызовы.Поэтому функциональные языки обращаются с вычислительными процессами как с обычными математич функциями. Теория так и оставалась теорией, пока в начале 1950-х годов Джон Маккарти не разработал язык Лисп, который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется (также как и Фортран), после многих лет эволюции он удовлетворяет современным запросам, которые заставляют разработчиков программ взваливать как можно бо́льшую но́шу на компилятор, облегчив так свой труд. Нужда в этом возникла из-за всё более возрастающей сложности программного обеспечения. Большинство функциональных языков программирования реализуются как интерпретируемые, следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в машинный код). Таковые удобны для быстрой отладки программ, исключая длительную фазу компиляции, укорачивая обычный цикл разработки. С другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, Objective Caml) или код на Си/Си++ (например, Glasgow Haskell Compiler). Что показательно, практически каждый компилятор с функционального языка реализован на этом же са́мом языке. использование функционального подхода всегда наделяет программу следующими свойствами: 1.локаничность кода (то что на процедурн яз код в пол страницы,на функциональном в 1 строчку) 2. возможность более гибкой модификации программ. 3. способность воспринемать данные как программу. 4. принципиальная возможность распараллеливания вычислений. 5. возможность "ленивых" вычислений ( для объяснения что такое ленивые вычисления рассмотрим ситуацию, когда в программе производится манипуляция с бесконечн суммой чисел. В обычном сл прежде чем подставлять бесконеч сумму в к-либо выражение, программа пытается ее упростить- вычислить, но с бесконечн суммой этого сделать нельзя, а значит подставить ее куда-либо не удается, но мы можем отложить вычисления до требуемого момента- это и есть ленивые вычисления.В λ- исчислении "ленивые" вычисления инициируются так называемым нормальным порядком редукции, вычисления с макс упрощен перед подстановкой наз аппликативным порядком редукции ) .6.
отсутствие побочных эффектов.(побочный эффект функции - возможность в процессе выполнения своих вычислений: - чтение и модификация значения глобальных переменных; -осуществление операций ввода/вывода; - реагирование на исключительные ситуации и вызова их обработчика). Некоторые языки функционального программирования: в настоящее время распространены след яз фун программирования:1. Haskell-явл одним из самых распространенных нестрогих яз пр-ия. имеет развитую систему типизации. Последний стандарт Haskell98 стал стандартом фун программирования. 2. Meta Language- семейство строгих фун пр-я с развитой системой типов. 3. O Caml- современ о-о яз фун пр-я. разрабатыв исходя из особого внимания безопасности исполнения и надежности программ. 4. Erland- функциональный язык, позвол писать программы для разного рода распределенных систем,разраб и поддержив компанией Ericsson. 5. LISP- переводится как обработка списков. Семейство языков программирования основанное на представлении программы системой линейных списков символов, кот явл осн структурой данных яз. Традиционный Lisp имеет строгуюю динамическую систему типов, содерж императивные свойства, но в общем поощряет функцион порадигму программирования. lisp явл о-о яз кот заложен в платформе CLOS.lisp прошел процесс фундаментальной стандартизации, в результате чего появился стандарт ANSI Common lisp. В lisp сущ яд диалектов: Scheme, Common Lisp, Emacs lusp, auto lisp.
2. S-выражения как основные типы данных в языке Лисп. Списки. Рекурсивное определение списка. Базовые функции обработки S-выражений CAR, CDR, CONS, ATOM, EQ, COND
Основу лиспа составляют символьные выражения, которые называются S-выражениями и образуют область определения для функциональных программ. S-выражение - основная структура данных в лиспе. S-выражения: (ДЖОН СМИТ 33 ГОДА), ((МАША 21) (ВАСЯ 24) (ПЕТЯ 1)). S-выражение - это либо атом, либо список. В ЛИСПЕ список это последовательность элементов (list). Элементами являются или атомы или списки. Списки заключаются в скобки, элементы списка разделяются пробелами. (банан) – 1 атом (б а н а н) – 5 атомов (a b (c d) e) – 4 элемента. Таким образом список – это многоуровневая или иерархическая структура данных, в которой открывающиеся и закрывающиеся скобки находятся в строгом соответствии. (+ 2 3) – 3 атома (((((первый) 2) второй) 4) 5) – 2 элемента. Список, в котором нет ни одного элемента, называется пустым списком и обозначается "()" или символом NIL. NIL – это и список и атом одновременно. Пустой список играет такую же важную роль в работе со списками, что и ноль в арифметике. Любой язык для манипулирования данных должен быть наделен 3 возможностями:1. из данных составлять более сложные данные-конструкторы; 2. селекторы- разбирать данные на части; 3. предикат- определять тип данного. В яз lisp 2 функции селекторов: CAR- возвращает в кач-ве результата 1-ый элемент списка, кот наз головой списка; CDR- возвращает в кач-ве результата значение хвостов( часть списка без 1-го элемента) Функции конструктора: CONS- позволяет строить нов список из представленных ей в качестве элементов головы и хвоста.1-ый аргумент добавляет в качестве головы, а 2-ая -хвоста. Функции предиката: предикат- функция, которая определяет обладает ли аргумент определенным свойством и возвращает в качестве значения T или NIL. -ATOM- проверяет явл ли элемент атомом (аргумнт-любое S-выражение) -EQL-сравнивает числа одинаковых типов( если одинаков то T,если нет, то NIL) EQ-сравнивает 2 символа и возвращает значение T, если они идентичны. не предикатом EQ не EQL нельзя сравнивает списки. EQUAL- работает как EQL, но позволяет также сравнивать списки.

(cond (p1 e1) (p2 e2) … (pn en) (t en+1)) – условная конструкция общего вида

3.Понятие списка как основной структуры данных языка Лисп. Графическое представление списочной структуры. Реализация на базе основных функций CAR, CDR, CONS других функций: Append (слияние двух списков), Length (определение длины списка), Reverse (реверсирование списка)
В ЛИСПЕ список это последовательность элементов (list). Элементами являются или атомы или списки. Списки заключаются в скобки, элементы списка разделяются пробелами. (банан) – 1 атом (б а н а н) – 5 атомов (a b (c d) e) – 4 элемента. Таким образом список – это многоуровневая или иерархическая структура данных, в которой открывающиеся и закрывающиеся скобки находятся в строгом соответствии. (+ 2 3) – 3 атома (((((первый) 2) второй) 4) 5) – 2 элемента. Список, в котором нет ни одного элемента, называется пустым списком и обозначается "()" или символом NIL. NIL – это и список и атом одновременно. Пустой список играет такую же важную роль в работе со списками, что и ноль в арифметике. Графическое представление списочной структуры [a1, [a2, a3, [a4]], a5].
(defun append1 (a b) (if (= 0 (length a)) b ( cons (car a) ( append1 (cdr a) b))))

(defun LEN (s) (if (eql s nil) 0 (+1 (LEN (cdr s)))))

(defun reverse1 (s) (if (Null s) s (append (reverse1 (cdr s)) (list (car s)))))
4.Накапливающий параметр – аккумулятор. Примеры использования накапливающего параметра.
Бывает так, что при выполнении функции исключительно сёрьезно встаёт проблема расхода памяти. Эту проблему можно пояснить на примере функции, вычисляющей факториал числа:

(defun Factorial(n)

(if (= n 0) 1 (* n (factorial (-n 1)))))
Если провести пример вычисления этой функции с аргументом 3, то можно будет увидеть подстановочная модель:

Factorial(3);

>3*Factorial(2);

>3*2*Factorial(1);

>3*2*1*Factorial(0);

>3*2*1*1;

>3*2*1;

>3*2; >6. На примере этого вычисления наглядно видно, что при рекурсивных вызовах функций очень сильно используется память. В данном случае количество памяти пропорционально значению аргумента, но аргументов может быть большее число. Возникает резонный вопрос: можно ли так написать функцию вычисления факториала (и ей подобные), чтобы память использовалась минимально? Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример: Пример . Функция вычисления факториала с аккумулятором.

(defun factorial (n)

(fact-iter 1 1 n))

(defun fact-iter (product caunter max_count)

(if (>counter max_count)

product

(fact-iter (* counter product)

(+ counter 1) max_count)))

В этом примере product выполняет роль аккумулирующей переменной(накапливающий параметр) Принципы построения определений с накапливающим параметром. - Вводится новая функция с дополнительным аргументом (аккумулятором), в котором накапливаются результаты вычислений. - Начальное значение аккумулирующего аргумента задается в равенстве, связывающем старую и новую функции. - Те равенства исходной функции, которые соответствуют выходу из рекурсии, заменяются возвращением аккумулятора. - Равенства, соответствующие рекурсивному определению, выглядят как обращения к новой функции, в котором аккумулятор получает то значение, которое возвращается исходной функцией. Возникает вопрос: любую ли функцию можно преобразовать для вычисления с аккумулятором? Очевидно, что ответ на этот вопрос отрицателен. Построение функций с накапливающим параметром — приём не универсальный, и он не гарантирует получения хвостовой рекурсии. С другой стороны, построение определений с накапливающим параметром является делом творческим. В этом процессе необходимы некоторые эвристики.

5.Понятие побочного эффекта в Лиспе. Функции SET, SETQ, SETF. Управляющие структуры языка Лисп: работа с контекстом, последовательное исполнение, разветвление вычислений, итерации.
Побочный эффект функции - возможность в процессе выполнения своих вычислений: - чтение и модификация значения глобальных переменных; -осуществление операций ввода/вывода; - реагирование на исключительные ситуации и вызова их обработчика. SET -реализует присвоение переменной заданного значения те При помощи функции SET символу можно присвоить или связать с ним некоторое значение.(пример (set a b)- присваив значению выраж а значение b) У функции SET есть разновидность SETQ. В отличии от SET в функции SETQ вычисляется только 2-ой аргумент, 1-ый аргумент блокирован. Для присваивания существует обобщенная функция обновления данных SETF, которая записывает в ячейку памяти новое значение: (SETF ячейка-памяти значение) Через функцию SETF можно представить описанные нами ранее функции SET и SETQ. Управляющие структуры Лиспа являются формами.. Работа с контекстом: QUOTE или блокировка вычисления; вызов функции и лямбда-вызов; предложения LET.

(let ((x1 a1) (x2 a2) … (xn an)) форма1 форма2 …)

let* - последовательное присвоение значений

Последовательное исполнение: предложения PROG1, PROG2 и PROGN. Разветвление вычислений: условные предложения COND, IF, WHEN, UNLESS; выбирающее предложение CASE.

(when test form1 form2 ... ) Если test равен NIL, то form не выполняется и возвращается NIL.

(unless test form1 form2 ... ) Если test отличен от NIL, то формы form не оцениваются, и возвращается NIL.

Форма case представляет собой кондиционал, который выбирает для выполнения один из вариантов путем сравнения значения формы keyform с различными константами key, которые обычно представляют собой ключевые слова, числа или символы, но можно, вообще говоря, использовать произвольные объекты Лиспа. Формат этой формы следующий:

(case keyform

( keylist-1 consequent-1-1 consequent-1-2 ...)

( keylist-2 consequent-2-1 ...)

( keylist-3 consequent-3-1 ...)

...)

Итерации:

циклические предложения DO, LOOP, DOTIMES, DOUNTIL.
loop ,form* Выполнение ее можно прервать только с помощью явной команды, такой как, например, return или throw.
6. Понятие функционала в языке функционального программирования Лисп. Применяющие функционалы FUNCALL, APPLY; отображающие функционалы MAPCAR, MAPLIST
Функционалом называют функцию, которая имеет в качестве аргумента некоторую другую функцию в частном сл саму себя. Различия между функциональным аргументом и обычным состоит в том, что обычный аргумент используется лишь как объект, участвующий в вычислении, а функциональный используется как средство определяющее вычисл, которое применяется к др аргументам. Если функция в качестве своего значения возвращает др функцию, то такая функция наз функцией с функциональным значением. Функционалы и функции с функциональн значение наз функциями высшего порядка. Различают 2 вида функционалов: применяющие и отображающие.Применяющие функционалы -это фукционалы применяющие функциональный аргумент к своим другим аргументам. Аpply является (в своей исходной форме) функцией двух аргументов, из которых первый аргумент представляет собой функцию, которая применяется к элементам списка, составляющим второй аргумент функции Аpply. следующая разновидность применяющих функционалов это funcall- применяет функцию не к списку, а набору аргументов. funcall и apply позволяют задавать вычисления (функцию) произвольной формой, например, как в вызове функции, или символом, значением которого является функциональный объект. Поскольку второй аргумент функционала funcall вычисляется по обыкновенным правилам, то на его месте должно стоять выражение, значением которого будет символ или лямбда-выражение. Отображающие функционалы- применяют функцию зараенее неизвестную к списку своих аргументов. MAPCAR. Значение этой функции вычисляется путем применения функции fn к последовательным элементам xi списка, являющегося вторым аргументом функции. Например в случае одного списка получается следующее выражение: (MAPCAR fn ‘(x1 x2 ... xn)) . В качестве значения функционала возвращается список, построенный из результатов вызовов функционального аргумента MAPCAR.

MAPLIST. MAPLIST действует подобно MAPCAR, но действия осуществляет не над элементами списка, а над последовательными CDR этого списка. Функционалы MAPCAR и MAPLIST используются для программирования циклов специального вида и в определении других функций, поскольку с их помощью можно сократить запись повторяющихся вычислений.
7.Понятие макроса в Лиспе. Порядок вычисления макроса: этапы расширения, вычисления. Определение новых синтаксических форм с помощью макросов. Тестирование макросов с помощью MACROEXPAND
Макросы позволяют вводить в лисп нов синтаксические конструкции, которые по сути изменяют синтаксис интерпритатора lisp то яз лисп становится перепрограммируемым.

Синтаксис определения макроса выглядит также как синтаксис исполняемой при определении функции defun. (defmacro имя_макроса (аргументы) (тело_макроса)). Отличие состоит том что вместо служебного слова defun стоит defmacro. На самом деле отличие глубже. Вычисление макроса состоит из 2х этапов: - раскрытие макроса. Формируется выражение которое потом будет вычисляться. – вычисляется полученное выражение. На первом этапе фактически откладывается вычисление и можно заставить писать программу саму для себя. В этом случае стирается грань между данными для программы и самой программы.
(defun fnil (var) (setq var 0))

(defmacro mnil (var) (list 'setq var 0))

При определении макросов используется символ обратной блокировки `. Заблокированное выражение воспринимается просто как последовательност символов. Обратная блокировка позволяет разблокировать вычисление выражения. Для этого преред выражением ставится запятая.

(defmacro !nil (var) `(setq ,var 0))

Если FORMA является макровызовом, то функция (MACROEXPAND FORMA) повторно расширяет FORMA до тех пор, пока результат расширения не будет макровызовом. Функция MACROEXPAND возвращает результат последнего расширения. Хотя интерпретатор LISP автоматически расширяет макровызовы во время выполнения (когда функция вычисляется), обычно удобнее осуществлять расширение макросов только один раз - во время компиляции. Для осуществления макрорасширения во время компиляции макрос должен быть определен перед определением функции, содержащей макровызов, а управляющая переменная MACROEXPAND должна иметь значение не NIL. Если управляющая переменная MACROEXPAND не равна NIL, то макровызовы расширяются так же, как и функцией MACROEXPAND во время компиляции (когда функция определяется с помощью DEFUN или PUTD). Если управляющая переменная MACROEXPAND есть NIL, то макровызовы не расширяются во время компиляции.

(macroexpand '(macros))
8.Блокировка вычислений в Лиспе QUOTE, вычисление значений EVAL. Обратная блокировка при записи макросов. Понятие свойства символа. Задание и получение свойства символа. Функциональная блокировка. Лексические замыкания.
Апостроф перед выражением - это на самом деле сокращение лисповской формы QUOTE, записываемой в единообразной для Лиспа префиксной нотации: 'выражение = (QUOTE выражение). QUOTE можно рассматривать как специальную функ­цию с одним аргументом, которая ничего с ним не делает, даже не вычисляет его значение, а возвращает в качестве значения вызова сам этот аргумент. Интерпретатор Лиспа, считывая начинающееся с апострофа выражение, автоматически преобразует его в соответствующий вызов функции QUOTE. EVAL- это универсальная функция Лиспа, которая может вычислить любое правильно составленное лисповское выражение. EVAL определяет семантику лисповских форм, т.е. определяет, какие символы и формы совместно с чем и что означают и какие выражения имеют значение. QUOTE и EVAL действуют во взаимно противополож­ных направлениях и аннулируют эффект друг друга. Для облегчения написания макросов в Лиспе принят специальный механизм блокировки вычисле­ний, который называют обратной блокировкой и который помечается в отличие от обычной блокировки (quote) наклоненным в другую сторону (обратным) апострофом(back quote). Внутри обратно блокированного выражения можно по желанию локально отменять блокировку вычислений, иными словами внутри некоторого подвыражения опять осуществлять вычис­ления. Отсюда происходит и название обратной блокировки. Отмена блокировки помечается запятой (,) перед каждым предназначенным для вычисления подвы­ражением. Запятая дает возможность на время переключиться в нормальное состояние вычислений. Свойства символа. В Лиспе с символом можно связать именованные свойства. Свойства символа записываются в хранимый вместе с символом список свойств. Свойство имеет имя и значение. Список свойств может быть пуст. Его можно изменять или удалять без ограничений. Свойства символов независимо от их значений доступны из всех контекстов пока не будут явно изменены или удалены. Изменение значения символа не влияет на другие свойства. Свойства символа передаются другому символу с помощью функции SETQ. Для присваивания символу свойств отдельной функции нет. Для этого используются уже известные нам функции: (SETF (GET символ свойство) значение);(SETF (GET ‘студент ’группа) ’РВ-90-1) (get 'студент 'группа).

Функциональный аргумент можно пометить с помщью специальной формы function, предотвращающей его вычисление. У функции function есть синтаксический сахар - # '.

Чтобы создать объект с внутренним состоянием (с сохранением контекста) используют механизм замыканий.. Для этого сипользуют функциональную блокировку для выражения со свободной переменной:

Реализуем объект — банковский счет:

(defun make_count (N) #'(lambda (x) (if (>= N x) (setq N (- N x)) “Недостаточно денег на счете”)))

>(setq a1 (make_count 100))

>(funcall a1 9)

91

>(funcall a1 9)

82

Замыкание можно трактовать как функцию, вычисленную частично. Окночательное выч-е ф-ции отложено на момент ее вызова. При создании замыкания из определения ф-ции формируется частично вычисленный контекстный объект. Для окночательног овычисления ему нужно передать недостающие параметры.
9. Построение системы аналитического дифференцирования алгебраических выражений в Лисп
defun diff+ (l x) (list '+ (diff (first l) x) (diff (second l) x)))
(defun diff- (l x) (list '- (diff (first l) x) (diff (second l) x)))
(defun diff* (l x)

(list '+ (list '* (diff (first l) x) (second l))

(list '* (first l) (diff (second l) x))))
(defun diff/ (l x)

(list '/ (list '- (list '* (diff (first l) x) (second l))

(list '* (first l) (diff (second l) x))) (list '* (second l) (second l))))
(defun diffcos (l x)

(list '* (list '- (cons 'sin l)) (diff (first l) x))
(defun diffsin (l x)

(list '* (cons 'cos l) (diff (first l) x)))
(defun ^ (x n)

(expt x n))
(defun diff^ (l x)

(list '* (list '^ (first l) (second l))

(list '+ (list '* (diff (second l) x)

(list 'log (first l)))

(list '* (list '/ (second l) (first l))

(diff (first l) x)))))
(defun difflog (l x)

(cons '/ (cons (diff (first l) x) l)))
(defun difftan (l x)

(list '* (list '^ (cons 'cos l) '-2)

(diff (first l) x)))
(setf (get '+ 'prozvod) 'diff+)

(setf (get '- 'prozvod) 'diff-)

...
(defun diff (l x)

(cond

((atom l) (if (eq l x) 1 0))

(t (funcall (get (first l) 'prozvod)

(cdr l) x))))
(defun simple (l)

(cond

((atom l) l)

((and (equal (first l) '+) (numberp (second l)) (numberp (third l)))

(+ (second l) (third l)))

...

((and (equal (first l) '/) (numberp (second l)) (numberp (third l)))

(if (equal (third l) 0) "Деление на ноль"

(/ (second l) (third l))))

((and (equal (first l) 'sin) (numberp (second l)))

(sin (second l)))

...

((equal (first l) '+)

(list '+ (simple (second l)) (simple (third l))))

...

((equal (first l) 'sin)

(list 'sin (simple (second l))))

...

(t l)))

10.Рекурсия. Понятие подстановочной модели, виды рекурсии. Рекурсивный процесс, виды рекурсивных процессов, итеративный процесс. Использование блочной структуры в Лиспе.
Рекурсия — способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить самоподобие задачи. В программировании на Лиспе рекурсия используется для организации повторяющихся вычислений. Рекурсия в Лиспе представляет собой не только организацию вычислений - это образ мыслей и методология решения задач. Функция называется рекурсивной если в ее определении содержится вызов этой функции. Выделяют след способы организации рекурсии: - простая (если вызов ф-ии самой себя встречается в некоторой ветви лишь 1раз); - параллельная (тело определения ф-ии f содержит вызов ф-ии g несколько аргументов которой является f); - взаимная(определение ф-ии f содержит вызов g которая в свою очередь содержит f). О рекурсии высоких порядков говорят тогда когда ф-ия определяется через саму себя а внутри некоторых своих аргументов так же вызывает саму себя. Подстановочная модель показывает сначала серию расширений, а затем сжатие. Расширение происходит по мере того, как процесс строит цепочку отложенных операций. Сжатие происходит тогда, когда выполняются эти отложения операции, такой процесс называется рекурсивным процессом.

(defun Factorial(n)

(if (= n 0) 1 (* n (factorial (-n 1)))))
Если провести пример вычисления этой функции с аргументом 3, то можно будет увидеть подстановочная модель:

Factorial(3);

>3*Factorial(2);

>3*2*Factorial(1);

>3*2*1*Factorial(0);

>3*2*1*1;

>3*2*1;

>3*2; >6. На примере этого вычисления наглядно видно, что при рекурсивных вызовах функций очень сильно используется память. В данном случае количество памяти пропорционально значению аргумента, но аргументов может быть большее число. Возникает резонный вопрос: можно ли так написать функцию вычисления факториала (и ей подобные), чтобы память использовалась минимально? Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример: Пример . Функция вычисления факториала с аккумулятором.

(defun factorial (n)

(fact-iter 1 1 n))

(defun fact-iter (product caunter max_count)

(if (>counter max_count)

product

(fact-iter (* counter product)

(+ counter 1) max_count)))

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

11.История возникновения и развития языка логического программирования Пролог. Преимущества и недостатки. Область применения. Базовые понятия языка Пролог: предикат, предложение (факт, правило), процедура.
В истории возникновения и развития языка Пролог можно выделить следующие этапы. В 1965 году в работе "A machine oriented logic based on the resolution principle", опубликованной в 12 номере журнала "Journal of the ACM", Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название "принцип резолюции". В 1973 году "группа искусственного интеллекта" во главе с Аланом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. В 1976 г. Ковальский вместе с его коллегой Маартеном ван Эмденом предложил два подхода к прочтению текстов логических программ: процедурный и декларативный. Об этих подходах речь пойдет в третьей лекции. В 1977 году в Эдинбурге Уоррен и Перейра создали очень эффективный компилятор языка Пролог для ЭВМ DEC–10, который послужил прототипом для многих последующих реализаций Пролога. В 1980 году Кларк и Маккейб в Великобритании разработали версию Пролога для персональных ЭВМ. В 1981 году стартовал вышеупомянутый проект Института по разработке методов создания компьютеров нового поколения. В нашей стране были разработаны такие версии Пролога как Пролог-Д (Сергей Григорьев), Акторный Пролог (Алексей Морозов), а также Флэнг (А Манцивода, Вячеслав Петухин). Основное из этих преимуществ - возможность создания программы в терминах решаемой задачи. Бухучет - вы оперируете терминами проводка, сальдо, актив/пассив, квартальный/годовой баланс, а не абстрактными операторами if, new и goto. Синтаксический разбор запросов на естественном языке - вы работаете с предложениями, словами и лексемами, а не организовываете циклы для посимвольного анализа строки. Применение языка пролог во многих областях искусственного интеллекта, включая решение задач и эвристический поиск, программирование в ограничениях, представление знаний и экспертные системы, планирование, машинное обучение, качественные рассуждения, обработка текста на различных языках и ведение игр.

Программа на Прологе (база знаний) состоит из предложений. Каждое прежложение оканчивается точкой.

A:-B1,B2,...,BN. - общий вид предложений (А — заголовок, В - тело)

Предикат – некоторое отношение между переменными являются истинным или ложным в зависимости от интерпритации.

Факт представляет собой безусловно истиное выражение.

Правило – предложение истинность которого зависит от истинности одного или нескольких предложений. В прологе предложения с одним и тем же предикатом в заголовке должны идти друг за другом. Такая совокупность предложений называется процедура.
12.Переменные в Прологе: свободные, связанные, анонимные. Понятие отсечения, порядок использования отсечений в программе, «зеленые» и «красные» отсечения. Понятие цель, внутренняя, внешняя цели
Переменная в Прологе означает объект, а не область памяти. Пролог не подерживает изменение значения инициализированных переменных.

Свободная переменная - это переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными. Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной. Переменная, состоящая только из символа подчеркивания, называется анонимной и используется в том случае, если имя переменной несущественно. Отсечением в ПроЛоге называется механизм, который запрещает перебор правил данного предиката находящихся ниже текущего правила и запрещает механизм отката. Отсечение обозначается знаком "!". Зелеными называются те из них, при отбрасывании которых программа продолжает выдавать те же решения, что и при наличии отсечения. Если же при устранении отсечений программа начинает выдавать неправильные решения, то такие отсечения называются красными. 3-м специфичным предложением в пролога можно считать вопросы. Вопрос состоит только из тела и исп-ся для выяснения выполнимости некоторого отношения между описанными в проге объектами. Система рассматривает вопрос как цель к которой надо стремиться. Прога на прологе может содержать в себе вопрос. Так называется внутренняя цель. Если цели нет то после запуска система переходит в режим диалога и ожидает ввода внешней цели.

13.Рекурсия как основное средство программирования в Прологе. Шаг рекурсии, базис рекурсии. Достоинства и недостатки, примеры использования, хвостовая рекурсия.
В отличие от традиционных языков программирования, в которых основным средством организации повторяющихся действий являются циклы, в Прологе для этого используются процедура поиска с возвратом (откат) и рекурсия. Откат дает возможность получить много решений в одном вопросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого. Для Пролога, в отличие от императивных языков, рекурсия является основным приемом программирования. Более того, Пролог позволяет определять рекурсивные структуры данных. Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле. Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии. Так называемая хвостовая или правая рекурсия. Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила.

fact(1,1). /* факториал единицы равен единице */

fact(N,F):-

N1=N-1,

fact(N1,F1), /* F1 равен факториалу числа

на единицу меньшего исходного

числа */

F=F1*N. /* факториал исходного числа равен

произведению F1 на само число */

fib(1,1):-!. /* первое число Фибоначчи равно единице */

fib(2,1):-!. /* второе число Фибоначчи равно единице */

fib(N,F) :-

N1=N-1, fib(N1,F1), /* F1 это N-1-е число

Фибоначчи */

N2=N-2, fib(N2,F2), /* F2 это N-2-е число

Фибоначчи */

F=F1+F2. /* N-е число Фибоначчи равно сумме

N-1-го и N-2-го чисел Фибоначчи */

Рекурсивные алгоритмы, как правило, намного проще с логической точки зрения, чем итерационные. Некоторые алгоритмы удобно записывать именно рекурсивно.

С другой стороны, рекурсия имеет большой недостаток: ей, вообще говоря, может не хватать для работы стека.

Есть, правда, один вариант рекурсии, который использует практически столько же оперативной памяти, сколько итерация в императивных языках программирования. Это так называемая хвостовая или правая рекурсия.

14.Структура программы на Visual-Прологе. Разделы и их назначение. Домены: стандартные, списковые, составные в языке Пролог. Стандартные предикаты. Задание арифметических, логических операций, математических функций, работа с символами в Прологе, оформление комментариев.
Структура программы на Прологе отличается от структуры программы, написанной на процедурном языке. Пролог-программа является собранием правил и фактов. Решение задачи достигается интерпретаций этих правил и фактов. При этом пользователю не требуется обеспечивать детальную последовательность инструкций, чтобы указать каким образом осуществляется управление ходом вычислений на пути к результату. Вместо этого он только определяет возможные решения задачи и обеспечивает программу фактами и правилами, которые позволяет ей отыскать требуемое решение. Разделы: Constants – описание констант; Domains – описание доменов; Database – описание предикатов внутренней БД; Predicates – описание предикатов; Clauses – описание предложений; Goal – описание цели. В разделе описания констант в качестве имени может быть заглывн буквы( в начале 1-ый символ) поскольку в этом разделе прописные и строчные буквы не различ однако в основном коде константы должна быть с маленькой буквы. любая константа должна быть объявлена до ее использования. Раздел описания доменов явл аналогом разделов описания типов обычных яз програм.начинается с ключевого слова domains. в этом разделе объявляются любые нестандартные домены, которые использ в качестве аргументов предиката.объявление доменов имеет вид: <имя домена>=<определение домена> Database- предназнач для описания предикатов внутри БД,кот можно в процессе выполнения программы туда добавлять или удалять оттуда. В разделе Predicates- содержится описание определяемых пользователем предиката. В традицион яз пр-я подобными разделами явл разделы описания заголовков процедур и функций. Один предикат может иметь несколько описаний. Это удобно тогда, когда предикат должен работать с аргументом различной природы. Сама реализыция данной функции будет одна, описан в разделе описания предложений. При описание предиката можно указать будет ли он детерминорованным или недетерминированным. Детерминир- возвращ только одно решение. Недетерминиров может давать много решений. Детерминир предикаты выполняются быстрее. Для того, чтобы указать что предикат явл детерминир перед его именем записыв слово determ, для недерминиров- nondeterm, если не записанно то по умолчанию считать что детерминир. Внутри раздела Clauses содержится факты и правила, реализующие пользовательские предикаты. Данный раздел реализует осн тело программы. Goal описание внутренней цели программы. Стандартные домены: integer; char; string; sumbal. Стандартные предикаты: readint (переменная)- для ввода целочисленных данных; readreal (переменная)- для ввода вещественных данных; readchar (переменная)- для ввода символьных данных readln (переменная)- для ввода строковых данных. Для вывода результатов используется write (список переменных) nl переводит курсор па новую строку.%- коментарий.

+ - * / div mod < > <= >= <> ln log sqrt abs exp sin cos tan arctan trunc round true fail /*comment*/

15.Задание списка в Прологе. Пустой список, порядок разделения списка на хвост и голову. Примеры операций над списками в языке Пролог: длина списка, принадлежность элемента списку, объединение двух списков, нахождение последнего элемента списка, реверсирование списка.
[1,2,3,4]

[“понедельник”, «вторник»]

['п','в']

[] - пустой список
DOMAINS

<имя спискового домена> = <имя домена элементов спсика>*

listInt = integer*

listlistInt = listInt* %список списков [[1,2,3],[],[4,5]]

Для выделения головного элемента исп-ся символ |

[H|T] – H — голова, T — хвост
% нахождение длины списка

domains

listInt=integer*

predicates

length(listInt,integer)

clauses

length([],0):-!.

length([_|T],X):-

length(T,Y),

X=Y+1.

goal

length([1,2,3,4],L).
% проверяет элемент на принадлежность списку

member([H|_],H):-!.

member([_|T],E):- member(T,E).

% объединяет два списка в один

conc([],L2,L2):-!.

conc([H|T], L, [H|T1]):- conc(T,L,T1).

% находит последний элемент списка

last([H|[]],H):-!.

last([_|T],E):-last(T,E).

% реверсирует список

reverse([],[]):-!.

reverse([H|T],L):-

reverse(T,L1),

conc(L1,[H],L).
16.Использование рекурсивного программирования на примере бинарных деревьев
17.Использование рекурсивного программирования на примере булевой алгебры.

18.С использованием макросов постройте циклические конструкции LOOP, FOR ..TO...DO, WHILE

(defmacro loop1 (&rest body)

`(if (equal (progn ,@body) 'ret) 'ok

(loop1 ,@body)))
(setq = '=)

(setq do 'do)

(setq to 'to)

(defmacro for ( I = n1 to n2 do &rest body)

`(if (and (equal '= ,=) (equal 'to ,to) (equal 'do ,do))

(let (,i ,n1)

(loop1 ,@body

(setq ,i (+1 ,i))

(if (> ,i ,n2) 'ret)))

(print 'ошибка)))
(defmacro while (&rest body)

`(if (not (prog1 ,@body))

'OK

(while ,@body)))

Похожие:

1. История функционального программирования. Основные свойства функциональных языков iconВопросы к междисциплинарному экзамену
Математические основы функционального программирования: лямбда-исчисление А. Черча и теория рекурсивных функций: основные понятия...
1. История функционального программирования. Основные свойства функциональных языков iconКонспект лекций Рыбинск 2010 Содержание 1 История функционального программирования 4
Число таких переключений достигало порядка нескольких сотен и росло с усложнением программ. Потому следующим шагом развития программирования...
1. История функционального программирования. Основные свойства функциональных языков iconВведение в лямбда-исчисление
Математические основы функционального программирования: лямбда-исчисление А. Черча и теория рекурсивных функций: основные понятия...
1. История функционального программирования. Основные свойства функциональных языков iconФорум «функциональные языки»
Единого мнения на тему точного определения функционального языка не существует, в том числе и среди сообщества функционального программирования....
1. История функционального программирования. Основные свойства функциональных языков icon«Применение функциональных языков программирования к проблеме разбора грамматики»
Тема: «Применение функциональных языков программирования к проблеме разбора грамматики»
1. История функционального программирования. Основные свойства функциональных языков iconПлан-проспект спецкурса "Математические основы функционального программирования"
Целью курса является приобретение фундаментальных знаний в области построения программных систем с использованием современных языков...
1. История функционального программирования. Основные свойства функциональных языков iconФункциональное и логичеcкое программирование
Целью дисциплины является освоение студентами теоретических основ функционального (ФП) и логического программирования (ЛП) и приобретение...
1. История функционального программирования. Основные свойства функциональных языков iconЭкзаменационные вопросы по информатике
Парадигмы программирования. Основные подходы программирования. Типизация языков. Классификация c и С++ с точки зрения парадигм, подходов...
1. История функционального программирования. Основные свойства функциональных языков iconУчебная программа Дисциплины б8 «Языки программирования»
Правила и приемы использования языков программирования, рассмотренные в лекционном курсе, используются в рамках лабораторных занятий...
1. История функционального программирования. Основные свойства функциональных языков icon3 История развития программирования 5 Глава основные элементы программирования

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org