HUGS 98: различия между версиями
м
робот косметические изменения
Содержимое удалено Содержимое добавлено
D'ohBot (обсуждение | вклад) м робот косметические изменения |
|||
Строка 1:
Данный лабораторный практикум предназначен для практической поддержки курса лекций «Функциональное программирование», в котором рассматриваются основы функционального языка Haskell стандарта 1998
Первая часть практикума посвящена описанию инструментального средства HUGS 98, которое является бесплатным программным комплексом для программирования на языке Haskell. Кроме того, в первой части приведены базовые сведения о парадигме функционального программирования — его история, назначение и свойства.
Строка 9:
Автор — '''[[Участник:Dark Magus|Душкин Р. В.]]'''
== Предисловие ==
Традиционно на кафедре кибернетики [[w:Московский инженерно-физический институт|МИФИ]] преподавались [[основы функционального программирования]] на примере языка [[w:Лисп|Лисп]], разработанного в середине [[w:XX век|XX века]], а лабораторные работы проводились на версии <math>\mu</math>-Lisp. Со времени разработки Лиспа было создано множество новых теоретических механизмов, формализмов и методологий функционального программирования, венцом чего стала разработка унифицированного стандарта Haskell-98, ставшего в последующем функциональным языком программирования.
Строка 35:
Также выражаю благодарность своим коллегам — Клочкову Андрею и Мирошкину Алексею за их помощь и особые советы, которые помогли сделать курс и лабораторный практикум более лёгким для понимания. Особенную благодарность выражаю своей жене Елене за её понимание и поддержку.
== Введение ==
Созданная в 1998 году спецификация языка Haskell (названного так в честь учёного Хаскелла Карри, одного из основоположников функционального программирования) нашла необычайно широкую поддержку в научных кругах, в первую очередь, Европы и Японии. В связи с этим буквально за несколько месяцев различными исследовательскими группами и коммерческими компаниями было создано несколько реализаций языка Haskell как в виде интерпретаторов, так и в виде компиляторов — бесплатных и коммерческих.
Наиболее интересным инструментальным средством (ИС), которое используется во многих университетах мира при изучении основ функционального программирования, является ИС HUGS 98, включающее в себя собственно интерпретатор языка Haskell стандарта 1998
Кроме того, ИС HUGS 98 является абсолютно бесплатным программным средством и может быть свободно получено через интернет по адресу [http://www.haskell.org/ www.haskell.org]. Это дополнительно способствует распространению рассматриваемого ИС в качестве средства для обучения, хотя оно и обладает некоторыми недостатками по сравнению с коммерческими реализациями языка Haskell-98.
== Функциональное программирование ==
Прежде чем начать описание собственно функционального программирования, необходимо обратиться к истории науки о программировании.
Как известно, в 40-х годах XX
<code>MOV 5, AX
Строка 55:
Однако даже ассемблеры не могли стать инструментом, удобным для пользования, так как мнемокоды всё ещё оставались слишком сложными, тем более что всякий ассемблер был жёстко связан с архитектурой компьютера, на котором он исполнялся. Таким образом, следующим шагом после ассемблера стали так называемые императивные языки высокого уровня (BASIC, Pascal, C, Modula и прочие, включая объектно-ориентированные). Императивными такие языки были названы по причине того, что главным их свойством является ориентированность, в первую очередь, на последовательное исполнение инструкций, оперирующих с памятью (т. е. присваиваний), и итеративные циклы. Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности (предписания) [9].
Функциональное программирование основано на совершенно иных принципах. Краеугольным камнем в парадигме функционального программирования является понятие функции. Если вспомнить историю математики, то можно оценить возраст этого понятия. Ему
Математические функции выражают связь между параметрами (входом) и результатом (выходом) некоторого процесса. Так как вычисление (а в общем случае и программа) — это тоже процесс, имеющий вход и выход, функция является вполне подходящим и адекватным средством описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно, т. е. через самих себя. В процессе выполнения программы функции получают параметры, вычисляют и возвращают результат, в случае необходимости вычисляя значения других функций. Программируя на функциональном языке, программист не должен описывать порядок вычислений. Ему необходимо просто описать желаемый результат в виде системы функций [10], [11].
Строка 67:
== История функционального программирования ==
Широко известно, что теоретические основы императивного программирования были заложены ещё в 30-х годах XX
Теория так и оставалась теорией, пока в начале 50-х годов XX
В связи с этим всё
В результате вышло так, что практически каждая группа исследователей, занимающаяся функциональным программированием, использовала собственный язык [13], [14]. Это препятствовало дальнейшему распространению этих языков и порождало многочисленные более мелкие проблемы. Чтобы исправить ситуацию, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов. В настоящее время действителен стандарт Haskell-98 [2].
Строка 92:
=== Краткость и простота ===
Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языках. Для примера можно сравнить программы на языке C, на некотором абстрактном функциональном языке и на языке Haskell на примере сортировки списка быстрым методом Хоара (пример,
'''Пример 1. Быстрая сортировка Хоара на языке C:'''
Строка 149:
=== Строгая типизация ===
Практически все современные языки программирования являются строго типизированными языками (возможно, за исключением языка JavaScript и его диалектов, не существует императивных языков без понятия «тип»). Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов, просто не может выпасть в операционную систему с сообщением подобным «access violation», особенно это касается таких языков, как C/C++ и Object Pascal, где применение указателей является типичным способом использования языка. В функциональных языках
Рассматривая пример с быстрой сортировкой Хоара, можно увидеть, что помимо
Ещё одной разновидностью полиморфизма является перегрузка функций, позволяющая давать различным, но в чём-то схожим функциям одинаковые имена. Типичным примером перегруженной операции является обычная операция сложения. Функции сложения для целых чисел и чисел с плавающей запятой различны, однако для удобства они носят одно и то же имя (инфиксный знак «+»). Некоторые функциональные языки помимо параметрического полиморфизма поддерживают и перегрузку операций.
Строка 157:
В языке C++ имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные quickSort. В стандартную библиотеку C++ STL входит такая функция и множество других полиморфных функций. Но шаблоны языка C++, как и родовые функции языка Ada, на самом деле порождают множество перегруженных функций, которые компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort — это одна единственная функция.
В некоторых языках, например в языке Ada, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Чтобы избежать этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста. Этот механизм называется механизмом вывода типов. Известно несколько таких механизмов, однако большинство из них являются разновидностями модели типизации Хиндли-Милнера, разработанной в начале 80-х годов XX
=== Модульность ===
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними. Тем самым облегчается процесс проектирования и последующей поддержки
=== Функции — это значения ===
Строка 183:
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём декомпозиции и синтеза существующих объектов. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов. Однако это не мешает этим языкам имитировать некоторые полезные императивные свойства, такие как исключения и изменяемые массивы. Обычно для этого существуют специальные методы.
Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть ещё одно весомое преимущество — параллелизм. Раз все функции для вычислений используют только свои параметры, мы можем вычислять независимые функции в произвольном порядке или параллельно, на результат вычислений это не повлияет. Причем параллелизм этот может быть организован не только на уровне компилятора языка, но и на уровне архитектуры. В нескольких научных лабораториях
=== Отложенные (ленивые) вычисления ===
Строка 303:
Рис. 4. Диалоговое окно просмотра конструкторов типов
В верхнем поле представлен список всех имён конструкторов ти¬пов с соответствующей пиктограммой, обозначающей при¬ро¬ду конструктора. При помощи строки поиска можно осу¬щес¬т¬вить инкрементный поиск по всему списку — при вводе оче¬ред¬ной буквы курсор в списке перемещается на первое имя, которое на¬чинается на введённую последовательность символов. В поле «Type» приводится определение соответствующего типа. В двух ниж¬них полях предоставляется информация о конструкторах и се¬лекторах выделенного типа, а также об экземплярах типа (ес¬ли они есть).
При помощи этого диалогового окна разработчик может быс¬т¬ро перейти к редактированию выделенного конструктора
2.3.4. Просмотр иерархии классов
Просматривая иерархию классов, программист может уви¬деть отношения наследования между созданными классами. Не¬об¬ходимо отметить, что алгоритм прорисовки классов и от¬но¬ше¬ний в HUGS 98 несколько неадекватен, поэтому для более пол¬но¬го понимания от программиста требуется либо чутьё, либо спо¬собность быстро разбросать все классы по диалоговому ок¬ну, создав планарный граф.
Строка 311:
Рис. 5. Иерархия классов из файла Prelude.hs
== Лабораторная работа 1 ==
'''Цель:''' ''изучить основные принципы и методы функционального программирования; овладеть такими базисными возможностями функциональной парадигмы программирования как работа со списками, использование бесконечных списков, использование аккумуляторов, охраны и локальных переменных.''
Строка 385:
# Для чего необходима конструкция описания λ-выражений на языке Haskell? Каким образом можно применять безымянные функции?
== Лабораторная работа 2 ==
'''Цель:''' ''изучить структуру и реализованные возможности файла начальной загрузки HUGS 98 — <tt>Prelude.hs</tt>; узнать, какие классы, простые структуры данных и функции для их обработки
=== Предварительная подготовка ===
Строка 398:
# По согласованию с преподавателем выбрать один класс и исследовать его свойства и методы.
# По согласованию с преподавателем выбрать один экземпляр какого-либо класса и исследовать его реализацию.
# Составить список всех функций, работающих с натуральными числами.
# Составить список всех функций, работающих с действительными числами.
# Составить список всех функций, работающих со списками.
# Составить список всех функций, работающих с символами и строками.
# Составить список всех типов и функций, описывающих примитивы из реализации HUGS 98.
# Составить список всех монад.
# Составить список всех функций, работающих с консолью.
=== Выполнение работы ===
Строка 426:
== Лабораторная работа 3 ==
'''Цель''': ''изучить расширенные возможности языка Haskell; овладеть навыками решения задач на перебор, сортировку и обход бинарных деревьев при помощи методов функционального программирования.''
Строка 432:
=== Предварительная подготовка ===
После '''[[#Лабораторная работа 1|первой лабораторной работы]]''' в главном каталоге для проведения лабораторных работ по функциональному программированию
При помощи стандартного текстового редактора (Notepad для Windows) создать новый файл с расширением hs. Желательно, чтобы в названии файла был отражён номер текущей лабораторной работы.
Строка 451:
##Генерация списка всех возможных расстановок максимального количества слонов на доске N x N клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
##Генерация списка всех возможных расстановок максимального количества ладей на доске N x N клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
##Генерация списка всех возможных расстановок минимального количества коней на доске N x&nsbp;N клеток таким образом, чтобы ни один из коней не бил другого. Конём называется фигура, ходящая на две клетки в прямом направлении, а
##Поиск и генерация списка всех возможных расстановок восьми ферзей на шахматной доске (8 x 8) таким образом, чтобы ни один из ферзей не бил другого. Ферзём называется фигура, ходящая в любом направлении: по горизонтали, вертикали или диагонали.
##Генерация списка всех возможных расстановок N ферзей на доске N x N. В случае, если сгенерированный список получается пустым (например, для N = 2), считается, что таких расстановок не существует.
Строка 499:
=== Предварительная подготовка ===
После первой лабораторной работы в главном каталоге для проведения лабораторных работ по функциональному программированию
При помощи стандартного текстового редактора (Notepad для Windows) создать новый файл с расширением HS. Желательно, чтобы в названии файла был отражён номер текущей лабораторной работы.
Четвёртую лабораторную работу можно выполнять в домашних условиях, если существует такая возможность, так как она требует большого усердия и высоких
=== Задание ===
Строка 532:
#Что такое «генетические алгоритмы»?
== Литература ==
=== Обязательная ===
Строка 554:
#Джонс С., Лестер Д. Реализация функциональных языков. М.: Мир, 1991.
== Приложение ==
=== Языки функционального программирования ===
Строка 561:
# '''Lisp''' (List processor). Считается первым функциональным языком программирования. Нетипизирован. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. Сейчас наиболее распространён диалект Common Lisp, ушедший от принципов ФП. Язык сложен в изучении, имеет очень непривычный синтаксис. Существует объектно-ориентированный диалект языка — CLOS.
# '''Scheme'''. Один из многих диалектов языка Lisp, предназначенный для научных исследований в области информатики. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем базовая версия языка Lisp. Отличается простотой как
# '''ISWIM''' (If you See What I Mean). Функциональный язык-прототип. Разработан Ландиным (США) в 60-х годах для демонстрации того, каким может и должен быть язык функционального программирования. Вместе с языком Ландин разработал и специальную виртуальную машину для исполнения программ на языке ISWIM. Эта виртуальная машина, основанная на вызове по значению, получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
# '''ML''' (Meta Language). Целое семейство строгих функциональных языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих университетах мира (в некоторых даже как первый язык программирования).
Строка 571:
# '''Clean'''. Функциональный язык, специально предназначенный для параллельного и распределенного программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющих программировать графический пользовательский интерфейс под Win32 или MacOS.
# '''Erlang'''. Язык, разработанный компанией Ericsson, ориентирован на сферу коммуникаций; происходит от Пролога, хотя сейчас похож на него лишь внешне. Имеет лёгкий в освоении синтаксис, богатейшую библиотеку, в том числе: переносимый графический интерфейс, СУБД, распределенные вычисления и многое другое; причем всё это доступно бесплатно. Язык является параллельным изначально — возможность параллельной работы нескольких процессов и их взаимодействия заложена на уровне синтаксиса. Недостаток пока только один: компиляция в байт-код, для которого нужен «тяжёлый» и не слишком быстрый интерпретатор.
# '''Рефал'''. Функциональный язык, разработанный в СССР ещё в семидесятых годах XX
# '''Joy'''. Чистый функциональный язык, основанный на комбинаторной логике. Внешне похож на Форт: используется обратная польская запись и стек. Пока что находится в стадии развития, хотя
=== Интернет-ресурсы по функциональному программированию ===
Строка 588:
ИС HUGS 98 предоставляет программисту возможность тонко настраивать интерпретатор и саму ИС под ту или иную задачу. Это возможно при помощи изменения настроек (параметров) ИС. На рис. П1 показано состояние настроек, загружаемых по умолчанию (такой набор параметров действует при первоначальной установке HUGS 98).
[[
<center>'''Рис. П1. Диалоговое окно установка параметров ИС'''</center>
В верхней части представленного диалогового окна находится набор так называемых флагов, значения которых могут быть либо ИСТИНА (флаг установлен), либо ЛОЖЬ (флаг сброшен). Каждый флаг отвечает за тот или иной параметр интерпретатора или
В нижней части диалогового окна настроек находятся поля ввода внутренних переменных окружения ИС HUGS 98.
|