Основы логического и функционального программирования.prn. Основы логического и функционального программирования
 Скачать 410 Kb.
|
|
Строки PDC Prolog поддерживает различные стандартные предикаты для обработки строк. Основными предикатами для работы со строками можно назвать предикат frontchar (String, Char, StringRest), позволяющий разделить строку String на первый символ Char и остаток строки StringRest и предикат fronttoken (String, Lexeme, StringRest), который работает аналогично предикату frontchar, но только отделяет от строки String лексему Lexeme. Лексемой называется последовательность символов, удовлетворяющая следующим условиям: имя в соответствии с синтаксисом Prolog’а, число или отличный от пробела символ. Пример: преобразование строки в список символов (Два варианта. Варианты отличаются друг от друга граничным условием рекурсии. В первом варианте остановка рекурсии происходит, когда от строки будет отделен последний символ и строка станет пустой строкой. Во втором варианте остановка рекурсии происходит в момент попытки отделения от пустой строки очередного символа, что сделать не удается, и происходит откат ко второму предложению). %1 вариант DOMAINS charlist=char* PREDICATES string2charlist (string, charlist) CLAUSES string2charlist (“”, [ ]):- !. string2charlist (Str, [H|T]):- frontchar (Str, H, Str_Rest), string2charlist (Str_Rest, T). GOAL string2charlist (“abcde”, List), write (“List=”, List). %2 вариант DOMAINS charlist=char* PREDICATES string2charlist (string, charlist) CLAUSES string2charlist (Str, [H|T]):- frontchar (Str, H, Str_Rest), !, string2charlist (Str_Rest, T). string2charlist (_, [ ]). GOAL string2charlist (“abcde”, List), write (“List=”, List). Результат работы программы: List=[‘a’, ‘b’, ‘c’, ‘d’, ‘e’] Более подробно стандартные предикаты для работы со строками можно посмотреть в файле Prolog.hlp в разделах “STRING HANDLING” и “CONVERSIONS”. Динамические базы данных PDC Prolog поддерживает различные стандартные предикаты для обработки строк. Основными предикатами для работы со строками можно назвать предикат frontchar (String, Char, StringRest), позволяющий разделить строку String на первый символ Char и остаток строки StringRest и предикат fronttoken (String, Lexeme, StringRest), который работает аналогично предикату frontchar, но только отделяет от строки String лексему Lexeme. Лексемой называется последовательность символов, удовлетворяющая следующим условиям: имя в соответствии с синтаксисом Prolog’а, число или отличный от пробела символ. Пример: преобразование строки в список символов (Два варианта. Варианты отличаются друг от друга граничным условием рекурсии. В первом варианте остановка рекурсии происходит, когда от строки будет отделен последний символ и строка станет пустой строкой. Во втором варианте остановка рекурсии происходит в момент попытки отделения от пустой строки очередного символа, что сделать не удается, и происходит откат ко второму предложению). %1 вариант DOMAINS charlist=char* PREDICATES string2charlist (string, charlist) CLAUSES string2charlist (“”, [ ]):- !. string2charlist (Str, [H|T]):- frontchar (Str, H, Str_Rest), string2charlist (Str_Rest, T). GOAL string2charlist (“abcde”, List), write (“List=”, List). %2 вариант DOMAINS charlist=char* PREDICATES string2charlist (string, charlist) CLAUSES string2charlist (Str, [H|T]):- frontchar (Str, H, Str_Rest), !, string2charlist (Str_Rest, T). string2charlist (_, [ ]). GOAL string2charlist (“abcde”, List), write (“List=”, List). Результат работы программы: List=[‘a’, ‘b’, ‘c’, ‘d’, ‘e’] Более подробно стандартные предикаты для работы со строками можно посмотреть в файле Prolog.hlp в разделах “STRING HANDLING” и “CONVERSIONS”. Основы функционального программирования Введение Язык Lisp является языком функционального программирования. В Lisp’е как программы, так и данные, представляются одинаково – в виде списков. Например, запись (+ 1 2) может толковаться, в зависимости от контекста, как список, состоящий из трех элементов (данные), или как вызов функции суммирования с двумя аргументами (программа). О такой особенности Lisp’а говорит и название языка, ведь аббревиатура Lisp произведена от слов LISt Processing (обработка списков). То есть, программы, написанные на Lisp’е, могут обрабатывать и преобразовывать как другие программы, так и самих себя. Символьные выражения При написании программ на Lisp’е используются символы и создаваемые на основе символов символьные выражения. Символ в Lisp’е аналогичен переменной в традиционном языке программирования – это имя, состоящее из букв латиницы, цифр и некоторых специальных литер. Символ, как и переменная, может иметь какое-либо значение, то есть представлять какой-либо объект. Наряду с символами, в Lisp’е используются также: числа, целые и вещественные; специальные константы t и nil, обозначающие логические значения true (истина) и false (ложь); списки. Символы, числа и специальные константы представляют простейшие объекты, на основе которых строятся все прочие объекты данных. Поэтому для них используется обобщающее название – атомы. Все вышеперечисленные объекты (атомы и списки) называют символьными выражениями. Отношения между различными символьными выражениями можно представить следующим образом:  Списки Список – это основной тип данных в Lisp. Список заключается в круглые скобки, элементы списка разделяются пробелами. Пустой список обозначается парой скобок – (). Для обозначения пустого списка используется также специальная константа nil. Примеры списков: ;пятиэлементный список (1 2 3 4 5) ;четырехэлементный список (1 2 ((3) 4) 5) ;одноэлементный список ((1 2 3 4 5)) Первый элемент списка называется головой списка, все прочие элементы, кроме первого, представленные как список, называются хвостом списка. Примеры разделения списка на голову и хвост:
Функции В Lisp’е для вызова функции принята единообразная префиксная форма записи, при которой как имя функции, так и ее аргументы записываются в виде элементов списка, причем имя функции – это всегда первый элемент списка. В Lisp’е передача параметров в функцию осуществляется по значению. Параметры используются для того, чтобы передать данные в функцию, а результат функции возвращается как ее значение, а не как значение параметра, передаваемого по ссылке. Например: ;возвращаемое значение 8 (+ 3 5) ;возвращаемое значение 12 (* (+ 1 2) (+ 3 4)) ;возвращаемое значение 0 (sin 3.14) Список может рассматриваться и не как вызов функции, а как перечень равноправных элементов. Для блокирования вызова функции используется, в свою очередь, функция quote. Например, список (+ 3 5) будет восприниматься как вызов функции суммирования с аргументами 3 и 5. Если же использовать данный список в качестве аргумента функции quote (quote (+ 3 5)) то список воспринимается именно как список. То есть применение функции quote блокирует вызов функции и ее имя воспринимается как обычный элемент списка. Или, иначе говоря, если список является аргументом функции quote, то первый элемент списка не считается именем функции, а все прочие элементы не считаются аргументами функции. Для функции quote существует сокращенная форма записи, вместо имени функции quote используется апостроф перед открывающейся скобкой списка. Например: ‘(+ 3 5) Если предложить интерпретатору следующие примеры, он вернет соответствующие значения (значение, возвращаемое интерпретатором, написано прописными символами): > (+ 3 5)) 8 > (quote (+ 3 5)) (+ 3 5) > ‘(+ 3 5) (+ 3 5) > (quote (quote (+ 3 5))) (QUOTE (+ 3 5)) Для выполнения операции присваивания используется функция set. Формат функции (set variable value). Причем, если не требуется вычисления аргументов, их нужно предварить апострофами. Например: > (set ‘x 5) 5 > x 5 > (set ‘y (+ 6 12)) 18 > y 18 > (set 'a 'b) B > (set a 'c) C > a B > b C > c error: unbound variable - C Вместо функции set можно использовать функцию setq, также выполняющую присваивание, но при ее использовании нет необходимости предварять первый аргумент апострофом. Для первого аргумента блокировка вычисления выполняется автоматически. > (setq x 5) 5 > x 5 > (setq y (+6 12)) 18 > y 18 Функцию, которая в качестве значения возвращает только константы nil или t, называют предикатом. Для определения собственной функции можно воспользоваться стандартной функцией defun (сокращение от DEfine FUNction). Эта стандартная функция позволяет создавать собственные функции, причем не запрещается переопределять стандартные функции, то есть в качестве имени собственной функции использовать имя стандартной функции. Функция defun выглядит следующим образом: (defun name (fp1 fp2 … fpN) (form1 form1 … formN)). Name – это имя новой функции, (fp1 fp2 … fpN) – список формальных параметров, а (form1 form1 … formN) – тело функции, то есть последовательность действий, выполняемых при вызове функции. Пример – функция для вычисления суммы квадратов: (defun squaresum (x y) (+ (* x x) (* y y))) Результат работы: >(squaresum 3 4) 25 >(squaresum -2 -4) 20 Еще один пример: функция deftype, определяющая тип выражения (пустой список, атом или список). (defun deftype(arg) (cond ((null arg) ‘emptylist) ((atom arg) ‘atom) (t ‘list) ) ) Результат работы: >(deftype ()) EMPTYLIST >(deftype 'abc) ATOM >(deftype '(a b c)) LIST Базовые функции В Lisp’е существует пять основных функций, называемых базовыми: (car list) – отделяет голову списка (первый элемент списка); (cdr list) – отделяет хвост списка (все элементы, кроме первого, представленные в виде списка); (cons head tail) – соединяет элемент и список в новый список, где присоединенный элемент становится головой нового списка; (equal object1 object2) – проверяет объекты на равенство; (atom object) – проверяет, является ли объект атомом. Так как функции equal и atom возвращают значения nil или t, их можно назвать базовыми предикатами. Рассмотрим примеры для перечисленных функций: > (car ‘(one two three)) ONE > (car ‘(one)) ONE > (car ‘()) NIL > (cdr ‘(first second third)) (SECOND THIRD) > (cdr ‘(first)) NIL > (cdr ‘()) NIL > (cons 1 ‘(2 3)) (1 2 3) > (cons 1 nil) (1) > (cons nil nil) (NIL) > (equal ‘(1 2 3) ‘(1 2 3)) T > (equal ‘(1 2 3) ‘(3 2 1)) NIL > (equal ‘one ‘two) NIL > (atom ‘one) T > (atom 1) T > (atom (1)) NIL Управляющие структуры (предложения) Для организации различных видов программ в Lisp’е служат разнообразные управляющие структуры, которые позволяют организовывать ветвление, циклы, последовательные вычисления. Перечислим их: предложение let – служит для одновременного присваивания значений нескольким символам; предложения prog1, prog2, prong – используются для организации последовательных вычислений; предложение cond – используется для организации ветвления, и, следовательно, очень важно для организации рекурсии; предложение do – традиционный цикл. Рассмотрим перечисленные предложения подробнее. Предложение let служит для одновременного присваивания значений нескольким переменным. Формат предложения let: (let ((var_1 value_1) (var_2 value_2) … (var_n value_n)) form_1 form_2 … form_m) Работает предложение следующим образом: переменным var_1, var_2, … var_n присваиваются (параллельно!) значения value_1, value_2, … value_n, а затем вычисляются (последовательно!) значения форм form_1 form_2 … form_m. В качестве значения всего предложения let возвращается значение последней вычисленной формы form_m. > (let ((x 3) (y 4)) (sqrt (+ (* x x) (* y y)))) 5.0 Так как присваивание значений переменным выполняется параллельно, то в следующем примере будет выдано сообщение об ошибке. > (let ((x 3) (y (+ 1 x))) (sqrt (+ (* x x) (* y y)))) error: unbound variable - X После завершения выполнения предложения let переменные var_1, var_2, … var_n получают значения, которые они имели до использования в этом предложении, то есть предложение let выполняет локальные присваивания. > (setq x ‘three) THREE > (setq y ‘four) FOUR > (let ((x 3) (y 4)) (sqrt (+ (* x x) (* y y)))) 5.0 > x THREE > y FOUR Для выполнения последовательных действий можно использовать предложения prog1, prog2, prong. Их общий формат: (prog* form_1 form_2 … form_n) Все три предложения работают одинаково, последовательно вычисляются значения форм form_1, form_2, …, form_n. Различие между предложениями проявляется только в тех значениях, которые они возвращают: предложение prog1 возвратит значение первой формы form_1, предложение prog2 возвратит значение второй формы form_2, а предложение progn возвратит значение последней формы form_n. Во всем остальном эти предложения ничем не отличаются. > (prog1 (setq x 2) (setq x (* x 2)) (setq x (* x 2)) (setq x (* x 2))) 2 > (prog2 (setq x 2) (setq x (* x 2)) (setq x (* x 2)) (setq x (* x 2))) 4 > (progn (setq x 2) (setq x (* x 2)) (setq x (* x 2)) (setq x (* x 2))) 16 Предложение cond предназначено для организации ветвления (это предложение является аналогом оператора выбора – переключателя switch в языке C). Формат предложения cond выглядит следующим образом: (cond (predicate1 form1) (predicate2 form21 form22 … form2M) (predicate3) … (predicateN formN) ) При выполнении предложения cond последовательно вычисляются значения предикатов, обозначенных как predicate. Если предикат возвращает значение t, тогда вычисляется значение вычислимой формы form и полученное значение возвращается в качестве значения всего предложения cond. Другими словами, идет последовательный перебор предикатов до тех пор, пока не встретиться предикат, который будет истинен. Для некоторого предиката может отсутствовать вычислимая форма. В таком случае предложение cond возвратит значение самого предиката. Для некоторого предиката вычислимых форм может быть несколько. В таком случае формы будут вычислены последовательно, и значение последней формы будет возвращено как значение всего предложения cond. Пример для предложения cond – определение отрицательного, равного нулю или положительного числа (в этом примере предложения cond вложены одно в другое): (defun snumberp (num) (cond ((numberp num) (cond ((< num 0) ‘neg_number) ((= num 0) ‘zero) ((> num 0) ‘pos_number) )) (t ‘not_number) ) ) Результат работы программы: > (snumberp 1) POS_NUMBER > (snumberp -1) NEG_NUMBER >(snumberp 0) ZERO > (snumberp 'a) NOT_NUMBER Как быть в случае, если ни один из предикатов predicate в предложении cond не вернет значение, отличное от nil? Тогда используется прием, как в последнем примере. В качестве последнего предиката predicate используется константа t, что гарантирует выход из предложения cond с помощью последней ветви (использование константы t в качестве предиката predicate аналогично использованию метки default в переключателе switch). Предложение do, также как и предложение cond, является аналогом оператора цикла for в языке C. Формат предложения do: (do ((var_1 value_1) (var_2 value_2) … (var_n value_n)) (condition form_yes_1 form_yes_2 … form_yes_m) form_no_1 form_no_2 … form_yes_k ) Предложение do работает следующим образом: первоначально переменным var_1, var_2, …, var_n присваиваются значения value_1, value_2, …, value_n (параллельно, как в предложении let). Затем проверяется условие выхода из цикла condition. Если условие выполняется, последовательно вычисляются формы form_yes_1, form_yes_2, …, form_yes_m, и значение последней вычисленной формы form_yes_m возвращается в качестве значения всего предложения do. Если же условие condition не выполняется, последовательно вычисляются формы form_no_1, form_no_2, …, form_yes_k, и вновь выполняется переход в проверке условия выхода из цикла condition. Пример использования предложения do: для возведения x в степень n с помощью умножения определена функция power с двумя аргументами x и n: x – основание степени, n – показатель степени. > (defun power (x n) (do ;присваивание начального значения переменной result ((result 1)) ;условие выхода их цикла ((= n 0) result) ;повторяющиеся действия (setq result (* result x)) (setq n (- n 1)))) POWER > (power 2 3) 8 |