Директивное программирование

Директивное программирование – одно из наиболее естественных для человека подходов к написанию программ. Ведь программа в этом случае состоит из операторов присваивания и предложении, управляющих последовательностью их выполнения. При написании подобной программы необходимо найти такую цепочку команд, которая приведет, в конце концов, к вычислению одной или нескольких искомых величин.

Директивное программирование стали называть процедурным, когда в процессе увеличения сложности моделируемых систем и размера получаемых программ возникла концепция подпрограмм,называемых так же процедурами (procedure), функциями (function), методами (method).Подпрограмма позволяет локализовать в ней процесс выполнения определенного действия, которое может быть повторено многократно с помощью механизма вызова.

При этом исходная программа превращается из одной большой цепочки команд в значительно более короткую и понятную последовательность вызовов подпрограмм, решающих более простые подзадачи. При вызове подпрограммы ей часто передают так называемые параметры, а она после завершения своей работы обычно возвращает некоторый результат. Механизмы передачи параметров в различных языках программирования сильно отличается друг от друга.

Ниже приводится пример программы на языке С, в которой кроме главной функции main используются еще две подпрограммы –print_array,печатающая элементы переданного ей массива целых чисел, и selection, сортирующая массив, переданный ей в качестве аргумента.

Разместите текст этой программы в файле с именем sort.c и выполните следующие команды, компилирующие и запускающие ее:

Sort.c

,/a.out

Функция main дважды вызывает процедуру print_array: сначала для печати исходного массива, а затем, после вызова функции selection, для печати его же в уже отсортированном виде. Однажды реализованные функции print_array и selection могут быть использованы при написании относительно большой программы неоднократно.

Для того чтобы программа была понятной, подпрограммы не должны быть слишком большими.

Увеличение числа подпрограмм тоже ведет к значительному росту сложной программы в целом и, как следствие, к снижению ее надежности. Отсюда следует вывод :написать большую правильно работающую программу, используя классическое процедурное программирование практически невозможно.

Со временем при проектировании программ акцент сместился с организации процедур на организацию структур данных. Современные директивные языки программирования предлагают еще один метод структурирования программ: инкапсуляция (от слова capsule –капсула, контейнер) данных и подпрограмм в более крупные объекты, называемые модулями. Большую часть данных модуля и выполняемые операторы можно скрыть таким образом, что их нельзя будет изменить или использовать способами, отличными от заранее предопределенных. Эта парадигма известна, как принцип сокрытия данных.Если в языке нет возможности сгруппировать процедуры вместе с данными, то он плохо поддерживает модульный стиль программирования.

Типичный пример модуля – реализация структуры данных, называемой стеком. Стек можно уподобить коробке с листами бумаги. Новый лист кладется в стопку поверх остальных. Только верхний лист может быть прочитан или извлечен из коробки. Для того чтоб извлечь некоторый лист из коробки, необходимо сначала вынуть все те, что лежат над ним.

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

При модульном подходе задача сначала разбивается на подзадачи и осуществляется реализация этих подзадач, а затем эти подзадачи комбинируются друг с другом для решения основной задачи. Программа, реализующая работу со стеком, написанная в модульном стиле, не позволит пользователю добраться до внутреннего представления данных стека. Доступ к его элементам будет возможен только с помощью методов push и pop.

Способность языка поддерживать модули не помогает разработчику оптимально разбить программу на модули. В то же время именно от качества декомпозиции и способности разработчика программы выбрать наиболее подходящую структуру для ее реализации зависит качество всей системы. Объектно-ориентированное программирование, с которым мы познакомимся чуть позже, предлагает принципиально иной подход к решению данной проблемы.

Языки, которые мы уже обсудили, имеют одну общую черту: базовый оператор в них - это оператор присваивания, который заставляет компьютер переместить данные из одного места в другое. Принципиально иной подход к программированию заключается в том, чтобы описывать вычисление, используя уравнения, функции, логические выводы и т.п. Особое внимание в декларативном программировании уделяется тому, чтонужно сделать, а не тому, как это нужно сделать.

Мы рассмотрим особенности двух ветвей декларативного программирования :функциональные, основанное на математическом понятии функции, которая не изменяет свое окружение, в отличии от функции в процедурных языках, допускающих побочные эффекты, и логическое, в котором программы выражены в виде формул математической логики компьютер для решения задачи пытается вывести логические действия из них.

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

Каждая функция возвращает некоторые значения в вызвавшую функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор, пока начавшая процесс вычисления функция не вернет конечный результат пользователю.

«Чистое» функциональное программирование не содержит оператора присваивания, в нем вычисление любой функции не приводит ни к каким побочным эффектам, отличным от собственно вычисления ее значения. Разветвление вычислений основано на механизме обработке аргументов условного предложения, а циклические вычисления реализуются с помощью рекурсии.

Отсутствие оператора присваивания делает переменные, используемые в функциональных языках программирования, очень похожими на переменные в математике – получив однажды свои значения, они больше никогда их не меняют. Отсутствие побочных эффектов в процессе вычисления функции приводит к тому, что порядок выполнения отдельных фрагментов программы.

Не существенен - итоговое значение в любом случае будет одинаковым.

Функциональное программирование весьма красиво и иногда в качестве первого языка программирования, изучаемого студентами, выбирается Haskell или Lisp. Для успешного овладения данным стилем программирования, впрочем, необходимо весьма глубокое понимание многих разделов математики.

Пример

Хорошей иллюстрацией функционального стиля программирования является программа на языке Haskell для получения всех троек пифагоровых чисел, не превосходящих заданного числа (пифагоровой тройкой называют три числа целых, являющихся сторонами некоторого прямоугольного треугольника).

Создайте файл с именем triads.hs в который поместите следующий текст :

Triads n=[(x, y, z):let ns =[1….n],x<-ns, y<-ns, z <- ns, x*x+ y+ y==z*z]

Такую программу легко понять: получить все тройки целых чисел х, у и z не превышающих заданного числа n и удовлетворяющих условию х²+у²=z².

Для запуска интерпретатора языка Haskell в командной строке наберите hugs. После появления приглашения >введите команду:load triads.hs для загрузки содержимого файла в память. Теперь можно находить пифагоровы триады, например, при помощи следующего вызова функции triads 50. Для завершения работы интерпретатора наберите: quit и нажмите на клавишу Enter.

Следующая программа на языке Haskell уже не столь очевидна, но она поражает своей краткостью.

Пример

Создайте файл с именем primes.hs и поместите в него следующие строки:

Primes=map head( iterate sieve [2….1)

Sieve (p:xs)=[x| x –xs , x rem p \=0]

После старта интерпретатора hugs и загрузки в него этой программы достаточно вызвать функцию primes (без аргументов) и программа начнет печатать простые числа до тех пор, пока вы не прервете ее выполнение, нажав комбинацию клавиш Ctrl+C.

Еще одной реализацией декларативного стиля является логическое программирование, основано на логике предикатов.

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

Пример

Для иллюстрации принципов логического программирования с использованием языка Пролог приведем программу, находящую решение известной головоломки «Ханойская башня», изобретенной французским математиком Люка в 1883 году и украшенной им же легендой.

«Где то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брамы. В начале времен, когда Брама создавал Мир, он воздвиг в этом монастыре 3 высоких алмазных стержня и на один из них возложил 64 диска, сделанных из чистого золота. Он приказа монахам перенести эту башню на другой стержень (в соответствии с правилами). С этого времени монахи работают день и ночь. Когда они закончат свой труд, наступит конец света».

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

Переместите в файл с именем Hanoi.pl следующий текст (символ % начинает комментарий, который не обязательно помещать в файл).

%move( число _дисков, откуда, куда, через)

Move(1,x,y_) :- write(« move top disk from» )

Write(x), write (to)

Write(y), n1.

Move(N,X,Y,Z): -N>1, M is N-1,

Move(M,X,Y,Z),

Move(1,X,Y,_),

Move(M,Z,X,Y).

Запустите интерпретатор языка Пролог при помощи команды p1.после появления приглашения к работе (?-) загрузите содержимое файла командой [ hanoi].(расширение файла указывать не нужно, а вот точка после закрывающей квадратной скобки не обходима). Теперь, чтобы заставить Пролог решать задачу о перемещении 3 дисков, введите следующий запрос: move (3,Left, right, center).

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

Для завершения работы с интерпретатором наберите команду half и нажмите Enter.

Задания:

1.Измените программу triads.hs так, чтобы не выводились одинаковые тройки чисел, такие как (3,4,5).для этого введите дополнительное условие, например, х <y.

2.Получите решение головоломки «Ханойская башня» для четырех дисков.