Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1110798), страница 20
Текст из файла (страница 20)
Затем вычисляетсяусловие окончания p, и если его значение отлично от NIL, топоследовательно вычисляются формы t1 ... tk, и значение последней ихних возвращается как значение обращения к do. В ином случаепоследовательно вычисляются выражения тела цикла е1 e2 ... еn, иначинается выполняться следующий шаг цикла.На каждом следующем шаге цикла сначала переменным циклаодновременно присваиваются значения форм следующее_значение,вычисляемых в текущем контексте; если же для некоторой переменной этаформа не задана, то её значение не меняется.
Затем вновь проверяетсяусловие окончания p и так далее. Цикл заканчивается, когда значение pстанет неравным NIL.Заметим, что в случае k=0 значением функции do будет NIL.В качестве примера цикла do приведём определение функцииReverseDo, меняющей порядок элементов верхнего уровня списка напротивоположный.(defun ReverseDo1 (L)(do ((Rez NIL)) ;переменная цикла((null L) Rez) ; условие окончания(setq Rez (cons (car L) Rez))(setq L (cdr L))))Эту функцию можно определить иначе:(defun ReverseDo (L)(do ((Lst L (cdr Lst));нач.установка и пересчет Lst(Rez NIL (cons(car Lst) Rez)) ) ;пересчёт Rez((null Lst) Rez))) ;условие окончанияВо втором варианте определения функции ReverseDo тело циклапусто, пересчёт значений переменных цикла происходит при переходе кследующему его шагу.101Ещё одна встроенная в Common Lisp функция для программированияциклов – это функция do*.
Она отличается от do тем, что вычисление иприсваивание значений переменным цикла происходит последовательно:сначала вычисляется и присваивается значение первой переменной, затемвторой и т.д. Тем самым в выражении для вычисления значения очереднойпеременной можно использовать уже установленные значенияпредшествующих переменных.В диалекте MuLisp функции do и do* не являются встроенными, ихможно использовать только после загрузки файла common.lsp.Встроенной функцией MuLisp для программирования цикловявляется функция loop с обращением(loop s1 … sn) , n≥1.Она последовательно вычисляет выражения s1 … sn, переходя послевычисления sn к s1, пока не сработает условие выхода из цикла.Выражение si может быть обычной лисповской формой, либо выражениемвида (p e1 e2 … ek), k≥0, где p – условие выхода из цикла.По сути, si в последнем случае – это ветвь условного выраженияcond, и при её вычислении сначала вычисляется условие p.
Если значениеp равно NIL, то далее продолжается последовательное вычислениевыражений, стоящих после si. Если же значение p отлично от NIL, товычисляются формы e1, e2, … ek и выполнение цикла завершается, азначением функции loop становится значение последнего выражения ek.Заметим, что среди s1 … sn может быть несколько таких условныхвыражений для выхода из цикла loop.В качестве примера применения loop приведём очередноеопределение функции Reverse:(defun ReverseLoop (L)(let ((Res NIL)) ; локальная переменная(loop ((null L) Res) ;условие окончания цикла(setq Res (cons (car L) Res)(setq L (cdr L)))))Во многих диалектах Лиспа есть следующие блочные конструкции (вMuLisp встроенными являются только prog1 и progN):(prog1 e1 e2 … eN) , N≥1(prog2 e1 e2 … eN) , N≥2(progN e1 e2 … eN) , N≥1102Все эти функции осуществляют последовательное вычисление формe1 e2 … eN, а в качестве результата своего вычисления функция prog1возвращает значение e1, prog2 – значение e2, а progN – значение eN.Ещё одна блочная конструкция prog, встроенная в Common Lisp,служит для программирования в операторном стиле с использованиемпередачи управления.
Структура этой формы prog следующая:(prog (v1 … vk) e1 e2 ... en ) , k≥0, n≥0.В начале блока задаётся список локальных переменных v1 … vk (онможет быть пустым), все переменные инициализируются значением NIL.Любое выражение ei является либо вычислимой формой, либо меткой. Вкачестве метки может использоваться символьный атом или целое число.Выражения e1 e2 ...
en блока вычисляются последовательно, приэтом метки игнорируются. Такое последовательное вычисление можетбыть нарушено функциями-операторами go и return, которые могутвстретиться среди выражений блока.При вычислении особой функции (go метка) происходит переходна заданную метку (аргумент функции go не вычисляется), после которогобудет вычисляться выражение блока, следующее за этой меткой.Функция return служит для выхода из блока.
При вычисленииобращения к ней (return e) вычисляется выражение-форма e, далеевыполнение блока прекращается, и в качестве значения функции progвозвращается значение e.Если же во время вычисления блока оператор return не встретился,значением функции prog после вычисления последнего выражения enстанет значение NIL.В качестве примера использования prog приведём ещё одноопределение функции Reverse:(defun ReverseProg (L)(prog (Res)C;метка перехода(cond((null L)(return Res))) ;выход из блока(setq Res (cons (car L) Res))(setq L (cdr L))(go C) )) ; переход по метке1035.
Задания практикумаЗадания практикума были разработаны в поддержку теоретическогоизучения языка Лисп и предполагают составление лисп-программ решениятипичных задач анализа и обработки символьных данных.Отождествление рефал-выраженийРеализовать алгоритм отождествления выражений языка Рефал ввиде лисповской функции (Мatch P L), где L – произвольный список,Р – список-образец, в состав которого кроме обычных атомов входятатомы-переменные вида SX, WX, EX и VX . Буква E, W, V или Sобозначает тип переменной (множество ее допустимых значений). Буква Xиграет роль имени переменной; в качестве имени может быть взята любаялатинская буква или десятичная цифра.Функция Мatch производит сопоставление (отождествление)списка L с образцом P по правилам языка Рефал, рассматривая лисповскиескобки как структурные рефальские скобки.
Функция вырабатываетзначение T или NIL в зависимости от успешности сопоставления. В случаеудачного сопоставления переменные образца получают соответствующиезначения: значением переменной вида SX может быть лисповский атом, азначением переменной вида WX – лисповское выражение (атом илисписок). Переменная вида EX или VX может быть сопоставленасоответственно произвольной или непустой последовательности лиспвыражений, при этом её значением является список из этих выражений.Пример успешного сопоставления:(Match '(WA (С1 SB) EX) '(DO (С1 2) 5 ON)) ⇒ T,при этом: WA => DO, SB => 2, EX => (5 ON).Набор тестов для функции Мatch должен включать тесты,демонстрирующие её применение для распознавания структурыалгебраических выражений.Преобразование алгебраического выраженияПреобразовать в приведённый полином заданное алгебраическоевыражение, в котором используются операции сложения, вычитания,умножения, возведения в степень, целые числа, однобуквенныепеременные, а также круглые скобки, задающие нужный порядоквычисления операций.Полином представляет собой сумму или разность несколькиходночленов.
Одночленом может быть целое число, а также произведениецелого числа и нескольких множителей – целых положительных степенейпеременных (степень, равная единице, не записывается). Знак104произведения в записи полинома опускается. Например, полиномомявляется запись X+XY-15Y↑3+2.Полином называется приведённым, если в нём нет подобныходночленов, а в каждом его одночлене любая из переменных невстречается более одного раза. Приведённым является полиномX+XY-15Y↑3+2, полиномы же 46ZYZ и X+X-7+3XY+2 не являютсяприведёнными.В упрощённом решении этой задачи при записи исходногоалгебраического выражения знаки арифметических операций, числа ипеременные разделяются пробелами, а само выражение заключается вкруглые скобки (чтобы сделать его лисповским списком и тем самымоблегчить его ввод и обработку).
В полном решении задачи на входпрограммы подаётся текст алгебраического выражения, которое обычно несодержит объемлющих скобок и в котором знаки операций, именапеременных и числа могут быть записаны слитно.Суммирование рациональных выраженийРеализовать символьное вычисление суммы двух заданныхрациональных выражений. Полученное рациональное выражение должносостоять только из приведённых многочленов.Рациональное выражение представляет собой дробь, в числителе изнаменателе которой стоят полиномы от одной однобуквеннойпеременной. Полиномы являются в свою очередь суммой или разностьюнескольких одночленов.
Одночленом может быть целое число, а такжепроизведение целого числа и целой положительной степени переменной(степень, равная единице, не записывается). Знак операции умножения взаписи одночлена опускается. Например, полиномом является записьX-15X↑3+2. Указанный полином не содержит подобных одночленов,такие полиномы называются приведёнными.В упрощённом решении задачи при записи исходных рациональныхвыражений можно заключить их в скобки, а знаки арифметическихопераций, числа и переменные разделять пробелами (чтобы упроститьввод и обработку выражений). Например, выражения можно задать так:((7 + 15 - 3 X) / X)+(X /(5 X ↑ 8)), и в результате будетвычислено выражение(110 X ↑ 8 – 15 X ↑ 9 + X ↑ 2) / (5 X ↑ 9) , илис учётом упрощения: (110 X ↑ 6 – 15 X ↑ 7 + 1) / (5 X ↑ 7)В полном решении задачи на вход программы поступают текстырациональных выражений без лишних скобок, а числа, буквы переменныхи знаки операций могут не разделяться пробелом, например: X/5X↑8.105Преобразование формулы алгебры логики в ДНФПреобразовать в сокращенную дизъюнктивную нормальную формупроизвольную формулу алгебры логики, в которой используютсялогические константы, однобуквенные переменные и операциилогического отрицания, конъюнкции, дизъюнкции и импликации.Результирующая дизъюнктивная нормальная форма должна бытьправильной, т.е.
каждая её элементарная конъюнкция не должна содержатьповторных вхождений переменных, и все конъюнкции должны бытьразличными. Полученная формула не должна содержать избыточныхскобок.Например,формула(¬A∨D∨FALSE)⊃¬(B&¬C∨D)преобразуется к виду A&¬D∨¬B&¬D∨C&¬D .В упрощённом решении задачи при записи исходной логическойформулы знаки логических операций, константы и переменныеразделяются пробелами (если только между ними не стоит другойразделитель – круглая скобка), а сама формула заключается в объемлющиескобки (чтобы сделать её лисповским списком и упростить её ввод ипреобразование), например: (A ⊃ (B & ¬ C ∨ D))В полном решении задачи на вход программы поступает текстформулы, который обычно не содержит объемлющих скобок и в которомвсе символы могут быть записаны слитно.Построение по ДНФ равносильной ей КНФПо заданной дизъюнктивной нормальной форме некоторойбулевской функции построить ее совершенную конъюнктивнуюнормальную форму, а также сокращенную конъюнктивную нормальнуюформу.
Как исходная дизъюнктивная нормальная форма, так ирезультирующие конъюнктивные нормальные формы предполагаютсяправильными, т.е. все переменные, встречающиеся в каждой элементарнойконъюнкции/дизъюнкции, различны, а также нет одинаковыхэлементарных конъюнкций/дизъюнкций. В совершенной КНФ каждаяэлементарная дизъюнкция содержит вхождения всех переменныхбулевской функции, в сокращённой форме это не требуется.В исходной ДНФ используются только однобуквенные переменные.Построенные КНФ не должны содержать избыточных скобок. Например,для ДНФ A∨B&¬C получается сокращённая КНФ (A∨B)&(A∨¬C) исовершенная КНФ (A∨B∨C)&(A∨B∨¬C)&(A∨¬B∨¬C).В упрощённом решении задачи при записи исходной ДНФ знакилогических операций и переменные разделяются пробелами, а сама ДНФзаключается в объемлющие скобки (чтобы сделать её списком и упроститьеё ввод и обработку).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
