машинные языки и ассемблеры. Все остальные языки принято относить
к языкам высокого уровня . Однако необходимо иметь в виду наличие языков высокого уровня , в которые для удобства включены средства программирования низкого уровня . Примером является язык
программирования C .
Машинно- ориентированные и машинно - независимые языки
программирования . Языки программирования , зависящие от специфики определенного типа компьютеров , называются машинно-
- ориентированными. Все остальные относятся к машинно- независимым языкам .К машинно- ориентированным языкам традиционно принято относить машинные языки и ассемблеры . Однако из этого вовсе не следует , что все остальные языки программирования автоматически можно отнести к машинно-независимым языкам . Имеются языки программирования ,в которых содержатся машинно-ориентированная и машинно- независимые части.
Операторные и функциональные языки программирования .
К операторным языкам программирования относится большинство
традиционных языков ( PASCAL , C и т.п.) , в которых имеются понятия
операторов и функций . В отличие от операторных , в функциональных
языках программирования отсутствует понятие оператора , а программа
строится в виде суперпозиции функций. Классическим примером
является функциональный язык программирования LISP .
Процедурно- ориентированные и объектно-ориентированные языки программирования . Процедурно- ориентированные языки
программирования основаны на традиционном подходе к созданию программного обеспечения , при котором основным строительным блоком является процедура или функция . При объектно-ориентированном подходе в качестве основного строительного блока в процессе программирования выступает объект , принадлежащий определенному классу (являющийся экземпляром определенного
класса ) . Содержательно класс можно рассматривать как некий абстрактный объект, наделяемый свойствами , характерными для некоторого множества объектов .
Языки компилируемого и интерпретируемого типов .Язык
программирования относится к языкам компилируемого типа , если в результате трансляции текста исходной программы получается объектная программа на ассемблере или на некотором машинном языке. Языки интерпретируемого типа предусматривают получение в результате трансляции так называемого промежуточного кода, выполнение которого осуществляется специальной программой , называемой интерпретатором. Иными словами , для языков интерпретируемого типа происходит частичная компиляция , завершаемая генерацией промежуточного кода. Например , язык LISP относится к языкам интерпретируемого типа , а язык PASCAL -к языкам компилируемого типа .
Замечания к разделу . Приведенная классификация никоим образом
не претендует на полноту , так как кроме приведенных выше типов языков , существуют языки логического программирования , языки параллельного программирования , языки управления базами данных ,
языки искусственного интелекта и т.п.
2.3.Функциональные языки программирования .
Функциональное программирование -это способ составления
программ , в котором единственным действием является вызов функции,
единственным способом расчленения на части -введение имени для
функции и задание для этого имени выражения , вычисляющего
значение функции , единственным правилом композиции - суперпозиция функций . В этом разделе предлагаются элементы функционального программирования на основе языка программирования LISP. Раздел
никоим образом не претендует на руководство по программированию
на языке LISP , его цель - знакомство с основными принципами функционального стиля программирования . В предлагаемом ниже
изложении функционального стиля программирования в целях более прозрачного описания материала автор намеренно отходит в ряде
случаев от классической LISP- нотации , что по мнению автора
не затрагивает принципы функционального программирования.
Наиболее удачное изложение принципов функционального
программирования можно найти в книге [ 1 ] .
2.3.1.Простейшие приемы программирования.
В основе функционального программирования лежит определение
функции в виде так называемого выражения l - выражения . Функция F
определяется следующим образом : F(x,y.z)=df lx,y,z . PF , где x,y,z -
аргументы , а PF -выражение , определяющее способ вычисления
функции F.
Замечание. Для определенности мы рассматриваем здесь функцию от
трех переменных . В общем случае функция может содержать любое
количество аргументов.
Примеры:
1) (n-факториал)
fact(n) )=df ln. IF(n=0,1,n*fact(n-1))
2) (наибольший общий делитель)
gcd(m,n) )=df lm,n.IF(mod(m,n)=0,n,gcd(n, mod(m,n))) , где
mod(m,n) - остаток от деления m на n .
Замечания.
1) Функция IF(b,P,Q) определяется следующим образом :
ì P , если логическое выражение b истинно
IF(b,P,Q)= í
îQ , в противном случае .
2) В классической LISP-нотации функция записывается в виде (F,x,y,z,…) , где F - имя функции (операции) , x,y,z,…- аргументы , например (IF,b,P,Q) ,(MOD,m,n) , (EQ, n ,0 ) вместо n=0 , (EQ,(MOD,m,n),0) вместо mod(m,n)=0, и т.п. Однако в целях удобства изложения будем использовать привычную математическую нотацию.
3) Основным признаком функционального стиля программирования
является рекурсивное определение функций , характеризуемое
"обращением самой к себе " . Умение "адекватно" программировать
рекурсивно определяемые алгоритмы требует хорошего представления
о специфике реализации рекурсии. В отличие от итерационного способа программирования выполнение рекурсивно определяемой программы
происходит в два этапа . На первом этапе осуществляется построение рекурсивных соотношений и частичное вычисление с задержкой
выполнения действий , которые не могут быть выполнены на данном
этапе.Задержка вычислений обусловливается тем , что в описании
рекурсивно определяемой функции всегда присутствует явное или
косвенное обращение к той же самой функции . Первый этап
завершается после выполнения так называемого условия завершения рекурсии. На втором этапе осуществляется полное завершение всех задержанных действий путем последовательного "сворачивания"
рекурсивных соотношений.Например , при реализации функции
вычисления факториала , если n=4, результатом первого этапа является следующая последовательность :
fact(4)=4*fact(3)
fact(3)=3*fact(2)
fact(2)=2*fact(1)
fact(1)=1*fact(0)
fact(0)=1 .
Условием завершения рекурсии здесь является n=0 . Сворачивание
рекурсивных соотношений на втором этапе происходит путем
выполнения соответствующих подстановок , в результате чего
получается соотношение : fact(4)=4*3*2*1 .
4) В отличие от многих языков программирования в функциональных
языках программирования отсутствует строгое описание типов
переменных , предполагая , что тип переменной определяется в момент присваивания ей значения .
Упражнения к разделу.Запрограммировать следующие функции :
1) max(m,n) - максимальное из чисел m,n ;
2) sum(n)=1+2+…+n ;
3) exp(n,k)=nk -возвести в степень , используя умножение (k-целое);
4) sumexp(n)=11 + 22+ …+ nn ;
2.3.2.Обработка списков.
Списком называется последовательность элементов , являющихся
атомами (т.е. неразложимыми данными) или , в свою очередь , списками.
Атомы представляются константами , именами переменных и функций.
Для обозначения пустого списка используется nil .
Примеры списков:
1) ("ДЖОН" , "СМИТ" ,33,"ГОДА") ;
2) (x,(y,15),("A","B","C"))
5) () - пустой список (или nil ) ;
6) (F,x,y)
2.3.2.1.Операции над списками.
Над списками определены следующие операции:
1) head(s) -первый (головной) элемент списка s (s ¹ nil ) ;
2) tail(s) -список , получающийся из списка s удалением первого
элемента ( tail(nil)= nil ) ;
3) cons(a,s) -список , получающийся в результате добавления
элемента a в начало списка s ;
4) ìtrue , если a - атом
atom(a)= í
îfalse , в противном случае .
Из перечисленных выше определений очевидным образом следует соотношение t= cons(a,s) - head(t)= a & tail(t)=s .
Примеры.
1) Пусть s=(a,b,c) , тогда
а) head(s)=a ;
б) tail(s)= (b,c) ;
в) cons("d",s)=("d", a,b,c) ;
г) tail(tail(tail(s)))=nil;
д) atom(s)=false;
е) atom(head(s))=true .
2) Пусть s= ((a,b,c),d,(x,y)) , тогда
а) head(s)= (a,b,c) ;
б) tail(s)= (d,(x,y)) ;
в) cons((m,n),s) = ((m,n),(a,b,c),d,(x,y)) ;
г) atom(head(head(s)))=true .
2.3.2.2.Примеры программ.
1) Нахождение максимального элемента числового списка s.
Сначала определим функцию max2(x,y) , значением которой является максимальное из чисел x,y : max2(x,y) )=df lx,y. IF( x>y ,x ,y ).Теперь
функция нахождения максимального элемента списка может быть определена так :
max(s) )=df ls.IF(tail(s)=nil , head(s) , max2(head(s),max(tail(s))) ) .
2) Вычисление суммы всех элементов числового списка s .
sum(s) )=df ls. IF(tail(s)=nil , head(s) ,head(s) + sum(tail(s)) ) .
3) Удаление последнего элемента из списка s.
del(s) =df ls. IF(tail(s)=nil , nil , cons(head(s),del(tail(s)) ) .
4) Определение семантики оператора while b do P .
while(b,P) =df ls. IF( b, cons(P, while(b,P)) , nil ) .
Замечание. В отличие от операторных языков программирования в функциональных языках программирования отсутствует понятие
оператора и процедуры. Поэтому программистам , привыкшим к
операторному стилю, приходится сталкиваться с определенными
трудностями при программировании посредством функциональных
средств. Например , рекурсивное определение оператора while b do P
с точки зрения операторного стиля могло бы иметь следующий вид :
while b do P=df IF b then (P; while b do P) . Однако отсутствие оператора
последовательной композиции в функциональном программировании
вынуждает нас заменить конструкцию (P; while b do P) на
cons(P, while(b,P)) , где функция cons имеет чисто вспомогательную
роль и используется для соединения последовательно выполняемых
функций. С таким же успехом вместо функции cons мы могли бы
использовать любую 2-х местную функцию при условии корректного