Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Реферат - Общие сведения о функциональном программировании - файл hugs.doc


Реферат - Общие сведения о функциональном программировании
скачать (164.8 kb.)

Доступные файлы (1):

hugs.doc3579kb.16.06.2003 17:25скачать

содержание
Загрузка...

hugs.doc

  1   2   3   4   5
Реклама MarketGid:
Загрузка...
Содержание

Предисловие 5

Введение 8

1. Общие сведения о функциональном программировании 9

1.1. История функционального программирования 11

1.2. Основы функционального программирования 13

1.2.1. Краткость и простота 13

1.2.2. Строгая типизация 16

1.2.3. Модульность 18

1.2.4. Функции — это значения 18

1.2.5. Чистота (отсутствие побочных эффектов) 19

1.2.6. Отложенные (ленивые) вычисления 20

2. Основы работы с HUGS 98 21

2.1. Панель инструментов HUGS 98 22

2.2. Команды консоли HUGS 98 25

2.3. Дополнительные возможности для отладки 28

2.3.1. Просмотр классов 30

2.3.2. Просмотр зарегистрированных имён объектов 31

2.3.3. Просмотр конструкторов типов 33

2.3.4. Просмотр иерархии классов 34

Работа 1
Основы функционального программирования 36

Работа 2
Изучение файла Prelude.hs 40

Работа 3
Углублённое изучение возможностей языка Haskell 43

Работа 4
Выполнение сложных задач Искусственного Интеллекта 48

Список литературы 51

Приложение 53

А. Языки функционального программирования 53

Б. Интернет-ресурсы по функциональному прог­рам­ми­ро­ва­нию 57

В. Параметры ИС HUGS 98 58


Предисловие


Традиционно на кафедре кибернетики МИФИ преподавались ос­новы функционального программирования на примере языка Lisp, разработанного в середине XX века, а лабораторные ра­бо­ты проводились на версии -Lisp [1]. Однако со времени раз­ра­бот­ки языка Lisp было создано множество новых теоретических ме­ханизмов, формализмов и методологий функционального прог­раммирования, венцом чего стала разработка уни­фи­ци­ро­ван­ного стандарта Haskell-98, ставшего в последующем фун­к­ци­о­нальным языком программирования [2].

До сих пор стандарт Haskell-98 остаётся «вехой» в развитии фун­кционального программирования, поэтому каждый, ин­те­ре­су­ющийся этим вопросом, должен знать хотя бы основы нового стан­дарта и нового языка. Однако несмотря на то, что уже из­да­но много работ на английском языке, использование языка Haskell в России тормозится отсутствием русскоязычной ли­те­ра­ту­ры даже в таком «безграничном» источнике, как Интернет.

Настоящий практикум продолжает серию учебно-ме­то­ди­чес­кой ли­тературы, предназначенной для практической поддержки спе­ци­альностей и специализаций по искусственному ин­тел­лек­ту.

Парадигма функционального программирования основана на ма­тематическом понятии «функция», что позволяет наиболее эф­фективно создавать программы расчётного характера. Кроме то­го, функциональное программирование предоставляет воз­мож­ность эффективно проводить вычисления на уровне сим­во­лов, а не чисел. Поэтому этот факт нашёл самое явное от­ра­же­ние в искусственном интеллекте [3], [4], [5].

Теоретические основы функционального программирования бы­ли заложены ещё в 20-х годах XX столетия после разработки та­ких мощных вычислительных формализмов, как ком­би­на­тор­ная логика и λ-исчисление [6]. Впоследствии λ исчисление стало ба­зисом всех разработанных функциональных языков, начиная от первого функционального языка Lisp, заканчивая последней раз­работкой — языком Haskell-98.

Несмотря на то, что в мире разработки и создания прог­рам­м­но­го обеспечения прочно заняла главенствующую позицию па­ра­дигма объектно-ориентированного программирования, что наб­людается особенно в последнее время в связи с появлением но­вых стандартов распределённого вычисления (CORBA, COM/DCOM, RMI и некоторые другие), принципы фун­к­ци­о­наль­ных программ всё ещё остаются основополагающими. Ведь да­же самые современные технологии программирования не мо­гут обойтись без понятия «функция», поэтому объектно-ори­ен­ти­рованное программирование включает в себя некоторые прин­ци­пы программирования функционального.

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

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

Лабораторный практикум состоит из двух частей. Первая часть практикума посвящена описанию инструментального сред­ства HUGS 98, которое является бесплатным программным ком­плексом для программирования на языке Haskell. Кроме то­го, в первой части приведены базовые сведения о парадигме фун­кционального программирования — его история, назначение и свойства.

Вторая часть предназначена для выполнения лабораторных ра­бот по курсу «Функциональное программирование» и состоит из четырёх лабораторных заданий, разбитых на части по уровню слож­ности решаемых задач.

Автор выражает особую благодарность своему научному ру­ко­водителю Рыбиной Галине Валентиновне, основателю и бес­смен­ному руководителю лаборатории «Системы ис­кус­с­т­вен­но­го ин­теллекта», за предоставленную уникальную воз­мож­ность взять в свои руки одно из направлений подготовки спе­ци­а­листов по кафедре кибернетики.

Также выражаю благодарность своим коллегам — Клочкову Андрею и Мирошкину Алексею за их помощь и особые советы, которые помогли сделать курс и лабораторный практикум более лёгким для понимания. Особенную благодарность выражаю своей жене Елене за её понимание и поддержку.

Введение


Созданная в 1998 году спецификация языка Haskell (наз­ван­но­го так в честь учёного Хаскелла Карри, одного из ос­но­во­по­лож­ников функционального программирования) нашла не­обы­чай­но широкую поддержку в научных кругах, в первую очередь, Ев­ропы и Японии. В связи с этим буквально за несколько ме­ся­цев различными исследовательскими группами и ком­мер­чес­ки­ми компаниями было создано несколько реализаций языка Haskell как в виде интерпретаторов, так и в виде компиляторов — бес­платных и коммерческих.

Наиболее интересным инструментальным средством (ИС), ко­торое используется во многих университетах мира при изу­че­нии основ функционального программирования, является ИС HUGS 98, включающее в себя собственно интерпретатор языка Haskell стандарта 1998 года (далее Haskell-98), а также ин­тег­ри­ро­ванную среду программирования.

Кроме того, ИС HUGS 98 является абсолютно бесплатным прог­раммным средством и может быть свободно получено через Ин­тернет по адресу www.haskell.org. Это дополнительно спо­соб­с­твует распространению рассматриваемого ИС в качестве сред­­ства для обучения, хотя оно и обладает некоторыми не­дос­тат­ка­ми по сравнению с коммерческими реализациями языка Haskell 98.
^

1. Общие сведения о функциональном программировании


Прежде чем начать описание собственно функционального прог­раммирования, необхо­димо обратиться к истории науки о прог­раммировании.

Как известно, в 40-х годах XX века появи­лись первые циф­ро­вые компьютеры, которые программировались при по­мощи пе­ре­ключения различного рода тумблеров, проводков и кнопок, а впос­ледствии при помощи перфокарт и перфолент. Число таких пе­рек­лю­чений достигало нескольких сотен и не­умо­ли­мо росло с ростом сложности прог­рамм. Иногда происходило так, что лаборанты путали стопки перфокарт, что влекло за со­бой долгие поиски причин неправильной работы созданной прог­раммы. Поэтому следующим шагом развития прог­рам­ми­ро­ва­ния стало создание различных ассемблерных языков с простой мне­мо­никой. Например:

MOV 5, AX

MOV 4, BX

ADD BX

Однако даже ассемблеры не могли стать инструментом, удоб­ным для пользования, так как мнемокоды всё ещё оставались слиш­ком сложными, тем более что всякий ассемблер был жёс­т­ко связан с архитектурой компьютера, на котором он ис­пол­нял­ся. Таким образом, следующим шагом после ассемблера стали так называемые им­пе­ра­тив­ные языки высокого уровня (BASIC, Pascal, C, Modula и прочие, включая объектно-ори­ен­ти­рован­ные). Императивными такие языки были названы по причине то­го, что глав­ным их свойством является ориентированность, в пер­вую очередь, на пос­ле­до­ва­тель­ное исполне­ние инструкций, опе­рирующих с памятью (т.е. присваиваний), и итеративные цик­­лы. Вызо­вы функций и процедур, даже рекурсивные, не из­бав­ляли такие языки от яв­ной импера­тивности (пред­пи­са­ния) [9].

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

Математические функции выражают связь между па­ра­мет­ра­ми (входом) и результатом (вы­ходом) некоторого процесса. Так как вычисление (а в общем случае и программа) — это тоже про­цесс, имеющий вход и выход, функция является вполне под­хо­дящим и адекватным средством описания вы­чис­ле­ний. Имен­но этот простой принцип положен в основу функциональной па­ра­дигмы и фун­к­ционального стиля программирования. Фун­к­ци­о­нальная программа представляет со­бой набор определений фун­кций. Функции опре­деляются через другие функции или ре­кур­сивно, т.е. через самих себя. В процессе выполне­ния прог­рам­мы функции получают па­ра­метры, вычисляют и возвращают ре­зультат, в слу­чае необходимости вычисляя значения дру­гих функ­ций. Программируя на функциональ­ном языке, прог­рам­мист не должен опи­сы­вать порядок вычислений. Ему не­об­хо­ди­мо просто описать желаемый результат в виде сис­темы функ­ций [10], [11].

Особо следует подчеркнуть, что функцио­нальное прог­рам­ми­ро­вание, равно как и логическое программирование, нашло боль­шое применение в искусственном интеллекте и его приложениях [7], [8], [12].

В качестве базовой литературы, раскрывающей вопросы функ­ционального программирования, можно посоветовать такие ос­новополагающие работы, как [1], [3], [4].

Расширенный список литературы по функциональному прог­рам­мированию приведён в конце лабораторного практикума.
  1   2   3   4   5



Скачать файл (164.8 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации