согласования типов аргументов. Что же касается отсутствия процедур ,
то известно , что любую процедуру можно определить посредством соответствующей эквивалентной функции .
Упражнения к разделу.
Запрограммировать следующие функции :
1) инвертирование списка ( например , (a,b,c,d, e ) => (e,d,c,b,a) );
2) преобразование структурного списка в линейный, т.е. удаление
из списка всех внутренних скобок ( например , ( (a,b) ,c, (d, e) ) =>
=>(a,b,c,d, e ) ) ;
3) удаление из списка первых n-элементов (если n ³ числа элементов
списка , результат - nil ) ;
4) удаление из списка последних n-элементов (если n ³ числа
элементов списка , результат - nil ) ;
5) ìtrue , если s=t
Iseq(s,t)= í
îfalse , в противном случае , где s и t - списки .
2.3.2.3.Дополнительные средства функционального программирования.
Кроме перечисленных в предыдущих разделах средств , при
составлении функциональных программ нам необходимы средства
ввода -вывода , присваивания и т.п.. Эти средства представлены
следующими функциями :
1) input(s) - ввод переменной , получаемой в результате вычисления выражения s (s¹ nil) ;
2) output(s) - вывод результата вычисления выражения s ;
3) setq(s1,s2) - присвоение результата вычисления выражения s2
переменной , которая получается в результате вычисления
выражения s1 ( s1¹ nil ) ;
4) apply(f,s) - применение функции с именем , получаемым в результате
вычисления выражения f , к списку аргументов , который является
результатом вычисления выражения s ;
5) quote(s) - значением этой функции является само выражение s
(содержательно эта функция задерживает вычисление выражения s ,
которое в данном случае рассматривается как константа ) ;
6) eval(s) - значением этой функции является результат вычисления
выражения s ( в частности , если вычисление выражения было
задержано функцией quote , функция eval позволяет отменить
задержку и вычислить значение соответствующего выражения ) ;
7) list(s,t) - значением этой функции является список (s,t) .
При использовании средств функционального программирования
следует учитывать , что функциональные программы , в свою очередь ,
представляются в виде списков. Как уже было отмечено в р. 2.3.1 ,
функциональная программа вида F( x,y,…) , где F - имя функции ,
x,y,… -аргументы функции , представляется в виде списка (F , x,y,…) .
Поэтому в необходимых случаях функциональные программы можно
рассматривать как данные , являющиеся объектом преобразования и обработки.Это свойство , сводящееся по сути к возможности
динамического изменения программы в процессе ее выполнения ,
является весьма привлекательным с точки зрения создания
интеллектуальных программ .
Однако , с точки зрения технологии программирования использование
этой возможности является "правилом дурного тона " , посколько может привести к серьезным затруднениям при тестировании и отладке
программ .
Примеры.
1) Пусть s=(x,y) , тогда :
а) input(head(s))=input(x) - ввод переменной x ;
б) output(head(tail(s)))=output(y) -вывод переменной y ;
в) setq(head(s), head(tail(s)))= setq(x,y) - переменной x присваивается
значение переменной y ;
г) list(input(head(s)), setq(x,y)) = list(input(x) , setq(y,x)) - сначала
вводится значение переменной x , затем переменной y
присваивается значение переменной x ( функция list играет в этом
примере лишь вспомогательную роль , обеспечивая
соответствующую последовательность действий ) .
2) Пусть s=(cons, x, y ) и t= ("b","c") , тогда :
а) apply(quote(head(s)),("a",t)) =apply(quote(cons) , ("a",t))=cons("a",t)=
=cons("a",("b","c")) = ("a","b","c") ;
б) cons("a",(t)) = cons("a",(("b","c")))= ("a",("b","c")) ;
в) list("a",quote(t)) = ("a" , t) ;
г) list("a",t) = ("a" , ("b","c")) .
Упражнения к разделу.Запрограммировать следующие операции над полиномами :
1) умножение полинома на одночлен ;
2) умножение полинома на полином ;
3) приведение подобных членов .
Указание: полином С1x1+ С2x2+…+Cnxn представляется в виде
списка : ((С1,1),( С2,x2),…,( Cn,xn)) .
2.4. Спецификация , верификация и синтез программ. Основные понятия.
Процессу разработки любой программы всегда предшествует этап
постановки задачи на программирование.Успех разработки и
последующего внедрения программы во многом зависит от того ,
насколько точно и хорошо было сделано описание соответствующей
задачи . Такое описание называют спецификацией задачи . Так как саму программу также можно рассматривать в качестве описания задачи , для решения которой она создана , возникает вопрос , чем же спецификация отличается от алгоритма решения задачи . Многие авторы полагают , что
спецификация в отличие от программы (алгоритма) должна описывать ,
что надо сделать , а не как это делать , подчеркивая тем самым
непроцедурный характер спецификации. Однако задача может быть процедурной по своей природе и , кроме того, процедурность может быть высокого уровня , свободная от деталей реализации , которые должны обязательно присутствовать в любой работающей программе. В связи
с этим представляется более целесообразным говорить о процедурных
и непроцедурных спецификациях , имея в виду , что непроцедурные
спецификации , как правило , описывают постановку задачи ,а
процедурные - способ ее решения. Часто процедурные спецификации называют программными спецификациями , но в отличие от самих
программ в программных спецификациях отсутствуют, как правило ,
детали реализации.
Примеры спецификаций.
1) Максимум от чисел a и b :
ì a, если a>b
max(a,b) = í
î b , если a £ b .
2) Наибольший общий делитель натуральных чисел m и n :
ì n, если m mod n=0
gcd(m, n) = í
î gcd(n, m mod n) , если m mod n¹ 0 .
3) Максимальный элемент множества чисел M :
z=max(M) - zÎ M & (" x.xÎM => z ³ x)
С понятием спецификации тесно связано понятие надежности
программы . Программа является надежной , если она разработана в
полном соответствии со своей спецификацией . Отсюда следует , что не
всякая надежная программа обязательно является правильной , так как
сама спецификация может содержать ошибки .Соответствие программы
ее спецификации проверяется тестированием.
Однако , позволяя выявить допущенные в программе ошибки , процесс тестирования не позволяет как правило обосновать их отсутствие.
В связи с этим в программировании возникло понятие верификации
программ . Под верификацией программы понимается процесс
формального доказательства ее корректности (надежности) .
Предоставляя возможность доказательства отсутствия ошибок в
программе , методы верификации тем не менее не нашли применения в практическом программировании из-за их чрезмерной громоздкости и сложности. Однако , знание методов верификации является полезным
для разработчиков программ , так как эти методы позволяют более точно
и концептуально оценивать суть программирования и стимулируют
строгую и скрупулезную проверку всех промежуточных этапов процесса разработки программ .
Альтернативой верификациии является синтез программ ,
заключающийся в автоматическом построении программы по ее
спецификации .Синтез является более привлекательным , нежели
верификация , поскольку в результате синтеза должны получаться
готовые корректные программы при условии корректной работы
"синтезатора" . Разработка универсальных средств синтеза программ
относится к классу алгоритмически неразрешимых проблем , однако из
этого вовсе не следует , что использование синтеза программ на
практике обречено на неудачу. При определенном ограничении классов решаемых задач идея синтеза программ находит свое применение при создании генераторов программ.
Об этом свидетельствуют работы по созданию интегрированной
среды разработки современных объектно-ориентированных систем [2,3]. Реализация интегрированной среды разработки основывается на интеллектуальных генераторах программ , которые по сути можно
отнести к средствам синтеза программ.
При использовании спецификаций в разработке программ , а также
реализации интеллектуальных генераторов программ одной из основных
задач является выбор формализованного языка спецификаций и
установление соответствия между конструкциями языков спецификаций
и программирования. Это соответствие может устанавливаться путем
описания семантики базисных средств языка программирования
средствами языка спецификаций или наоборот. Рассмотрим один из
способов спецификации операторов языка программирования ,
основанный на языке исчисления предикатов [4].
Введем понятие состояния программы через состояние переменных
программы , в свою очередь определяемого через таблицу значений переменных программы. Состояние программы представляет из себя динамически изменяемый объект в процессе выполнения программы ,
которое может меняться в результате выполнения отдельной
программной конструкции (функции , оператора,модуля ).
Пусть s={x,y,… } -состояние программы (состояние переменных) до
выполнения некоторой программной конструкции P , а
s'={x',y',…}- состояние программы после выполнения конструкции P .
Тогда для спецификации конструкции P мы можем использовать
предикат YP (s,s') , показывающий , как изменились значения
переменных x,y,… в результате выполнения конструкции P.
В дальнейшем ,для простоты изложения материала, ограничимся рассмотрением только двух переменных x,y , полагая , что все
последующие рассуждения и выводы легко обобщаются на случай
любого числа переменных ) .
Тождественный оператор. Спецификация тождественного оператора
IDENT определяется как :
IDENT=df (x'=x) & (y'=y) .
Из спецификации следует , что тождественный оператор оставляет неизменными все значения переменных .