HUGS 98: различия между версиями

135 байт убрано ,  12 лет назад
м
робот косметические изменения
м (робот косметические изменения)
Данный лабораторный практикум предназначен для практической поддержки курса лекций «Функциональное программирование», в котором рассматриваются основы функционального языка Haskell стандарта 1998 го́даго́да. Курс по функциональному программированию читается в Московском инженерно-физическом институте (государственном университете) на кафедре кибернетики (группы 222 и 223) в рамках специальности «Прикладная математика» (шифр 657100) более десяти лет.
 
Первая часть практикума посвящена описанию инструментального средства HUGS 98, которое является бесплатным программным комплексом для программирования на языке Haskell. Кроме того, в первой части приведены базовые сведения о парадигме функционального программирования — его история, назначение и свойства.
Автор — '''[[Участник:Dark Magus|Душкин Р. В.]]'''
 
== Предисловие ==
 
Традиционно на кафедре кибернетики [[w:Московский инженерно-физический институт|МИФИ]] преподавались [[основы функционального программирования]] на примере языка [[w:Лисп|Лисп]], разработанного в середине [[w:XX век|XX века]], а лабораторные работы проводились на версии <math>\mu</math>-Lisp. Со времени разработки Лиспа было создано множество новых теоретических механизмов, формализмов и методологий функционального программирования, венцом чего стала разработка унифицированного стандарта Haskell-98, ставшего в последующем функциональным языком программирования.
Также выражаю благодарность своим коллегам — Клочкову Андрею и Мирошкину Алексею за их помощь и особые советы, которые помогли сделать курс и лабораторный практикум более лёгким для понимания. Особенную благодарность выражаю своей жене Елене за её понимание и поддержку.
 
== Введение ==
 
Созданная в 1998&nbsp;году спецификация языка Haskell (названного так в честь учёного Хаскелла Карри, одного из основоположников функционального программирования) нашла необычайно широкую поддержку в научных кругах, в первую очередь, Европы и Японии. В связи с этим буквально за несколько месяцев различными исследовательскими группами и коммерческими компаниями было создано несколько реализаций языка Haskell как в виде интерпретаторов, так и в виде компиляторов — бесплатных и коммерческих.
 
Наиболее интересным инструментальным средством (ИС), которое используется во многих университетах мира при изучении основ функционального программирования, является ИС HUGS&nbsp;98, включающее в себя собственно интерпретатор языка Haskell стандарта 1998&nbsp;го&#769;даго́да (далее Haskell-98), а также интегрированную среду программирования.
 
Кроме того, ИС HUGS&nbsp;98 является абсолютно бесплатным программным средством и может быть свободно получено через интернет по адресу [http://www.haskell.org/ www.haskell.org]. Это дополнительно способствует распространению рассматриваемого ИС в качестве средства для обучения, хотя оно и обладает некоторыми недостатками по сравнению с коммерческими реализациями языка Haskell-98.
 
== Функциональное программирование ==
 
Прежде чем начать описание собственно функционального программирования, необходимо обратиться к истории науки о программировании.
 
Как известно, в 40-х годах XX&nbsp;ве&#769;каве́ка появились первые цифровые компьютеры, которые программировались при помощи переключения различного ро&#769;даро́да тумблеров, проводков и кнопок, а впоследствии при помощи перфокарт и перфолент. Число таких переключений достигало порядка нескольких сотен и неумолимо росло с ростом сложности программ. Иногда происходило так, что лаборанты путали стопки перфокарт, что влекло за собой долгие поиски причин неправильной работы созданной программы. Поэтому следующим шагом развития программирования стало создание различных ассемблерных языков с простой мнемоникой. Например:
 
<code>MOV 5, AX
Однако даже ассемблеры не могли стать инструментом, удобным для пользования, так как мнемокоды всё ещё оставались слишком сложными, тем более что всякий ассемблер был жёстко связан с архитектурой компьютера, на котором он исполнялся. Таким образом, следующим шагом после ассемблера стали так называемые императивные языки высокого уровня (BASIC, Pascal, C, Modula и прочие, включая объектно-ориентированные). Императивными такие языки были названы по причине того, что главным их свойством является ориентированность, в первую очередь, на последовательное исполнение инструкций, оперирующих с памятью (т.&nbsp;е. присваиваний), и итеративные циклы. Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности (предписания)&nbsp;[9].
 
Функциональное программирование основано на совершенно иных принципах. Краеугольным камнем в парадигме функционального программирования является понятие функции. Если вспомнить историю математики, то можно оценить возраст этого понятия. Ему уже&#769;уже́ около четырёхсот лет, и математика придумала бесчисленное множество теоретических и практических аппаратов для оперирования функциями, начиная от обыкновенных операций дифференцирования и интегрирования, заканчивая различного ро&#769;даро́да функциональными анализами, теориями нечётких множеств и функций комплексных переменных.
 
Математические функции выражают связь между параметрами (входом) и результатом (выходом) некоторого процесса. Так как вычисление (а в общем случае и программа) — это тоже процесс, имеющий вход и выход, функция является вполне подходящим и адекватным средством описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно, т.&nbsp;е. через самих себя. В процессе выполнения программы функции получают параметры, вычисляют и возвращают результат, в случае необходимости вычисляя значения других функций. Программируя на функциональном языке, программист не должен описывать порядок вычислений. Ему необходимо просто описать желаемый результат в виде системы функций&nbsp;[10],&nbsp;[11].
== История функционального программирования ==
 
Широко известно, что теоретические основы императивного программирования были заложены ещё в 30-х&nbsp;годах XX&nbsp;ве&#769;каве́ка учёными Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, также родилась в 20-х&nbsp;–&nbsp;30-х&nbsp;годах XX&nbsp;столетия. В числе разработчиков математических основ функционального программирования можно назвать Мозеса Шёнфинкеля (Германия и Россия) и Хаскелла Карри (Англия), разработавших комбинаторную логику, а также Алонзо Чёрча (США), создателя <math>\lambda</math>-исчисления.
 
Теория так и оставалась теорией, пока в начале 50-х&nbsp;годов XX&nbsp;ве&#769;каве́ка Джон МакКарти не разработал язык Lisp&nbsp;[1],&nbsp;[10],&nbsp;[12], который стал первым почти функциональным языком программирования и на протяжении многих лет оставался единственным. Хотя Lisp всё ещё используется (как, например, и FORTRAN), он уже&#769;уже́ не удовлетворяет некоторым современным запросам, которые заставляют разработчиков программ взваливать как можно бо&#769;льшуюбо́льшую ношу на компилятор, облегчив тем самым свой непосильный труд. Необходимость в этом, конечно же, возникла из-за всё более возрастающей сложности программного обеспечения.
 
В связи с этим всё бо&#769;льшуюбо́льшую роль начинает играть типизация. В конце 70-х&nbsp;–&nbsp;начале 80-х&nbsp;годов XX&nbsp;ве&#769;каве́ка интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов, как абстракция данных и полиморфизм. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число их диалектов, применяемых для решения конкретных задач.
 
В результате вышло так, что практически каждая группа исследователей, занимающаяся функциональным программированием, использовала собственный язык&nbsp;[13],&nbsp;[14]. Это препятствовало дальнейшему распространению этих языков и порождало многочисленные более мелкие проблемы. Чтобы исправить ситуацию, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х&nbsp;годов. В настоящее время действителен стандарт Haskell-98&nbsp;[2].
=== Краткость и простота ===
 
Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языках. Для примера можно сравнить программы на языке C, на некотором абстрактном функциональном языке и на языке Haskell на примере сортировки списка быстрым методом Хоара (пример, уже&#769;уже́ ставший классическим при описании преимуществ функциональных языков).
 
'''Пример 1. Быстрая сортировка Хоара на языке C:'''
=== Строгая типизация ===
 
Практически все современные языки программирования являются строго типизированными языками (возможно, за исключением языка JavaScript и его диалектов, не существует императивных языков без понятия «тип»). Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов, просто не может выпасть в операционную систему с сообщением подобным «access violation», особенно это касается таких языков, как C/C++ и Object Pascal, где применение указателей является типичным способом использования языка. В функциональных языках бо&#769;льшаябо́льшая часть ошибок может быть исправлена на стадии компиляции (первого шага интерпретации — кодогенерации), поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ.
 
Рассматривая пример с быстрой сортировкой Хоара, можно увидеть, что помимо уже&#769;уже́ упомянутых отличий между вариантом на языке C и вариантами на абстрактном функциональном языке и на языке Haskell есть ещё одно важное отличие: функция на языке C сортирует список значений типа <code>int</code> (целых чисел), а функции на абстрактном функциональном языке и на языке Haskell — список значений любого типа, который принадлежит к классу упорядоченных величин. Поэтому последние две функции могут сортировать и список целых чисел, и список чисел с плавающей точкой, и список строк. Можно описать какой-нибудь новый пользовательский тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функции quickSort и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным полиморфизмом и поддерживается большинством функциональных языков.
 
Ещё одной разновидностью полиморфизма является перегрузка функций, позволяющая давать различным, но в чём-то схожим функциям одинаковые имена. Типичным примером перегруженной операции является обычная операция сложения. Функции сложения для целых чисел и чисел с плавающей запятой различны, однако для удобства они носят одно и то же имя (инфиксный знак «+»). Некоторые функциональные языки помимо параметрического полиморфизма поддерживают и перегрузку операций.
В языке C++ имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные quickSort. В стандартную библиотеку C++ STL входит такая функция и множество других полиморфных функций. Но шаблоны языка C++, как и родовые функции языка Ada, на самом деле порождают множество перегруженных функций, которые компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort — это одна единственная функция.
 
В некоторых языках, например в языке Ada, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Чтобы избежать этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста. Этот механизм называется механизмом вывода типов. Известно несколько таких механизмов, однако большинство из них являются разновидностями модели типизации Хиндли-Милнера, разработанной в начале 80-х&nbsp;годов XX&nbsp;ве&#769;каве́ка. Таким образом, в функциональных языках в большинстве случаев можно не указывать типы функций.
 
=== Модульность ===
 
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними. Тем самым облегчается процесс проектирования и последующей поддержки больши&#769;хбольши́х программных систем. Поддержка модульности не является свойством именно функциональных языков программирования, однако поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. В качестве примеров подобных языков можно привести языки Modula-2 и Ada-95.
 
=== Функции — это значения ===
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём декомпозиции и синтеза существующих объектов. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов. Однако это не мешает этим языкам имитировать некоторые полезные императивные свойства, такие как исключения и изменяемые массивы. Обычно для этого существуют специальные методы.
 
Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть ещё одно весомое преимущество — параллелизм. Раз все функции для вычислений используют только свои параметры, мы можем вычислять независимые функции в произвольном порядке или параллельно, на результат вычислений это не повлияет. Причем параллелизм этот может быть организован не только на уровне компилятора языка, но и на уровне архитектуры. В нескольких научных лабораториях уже&#769;уже́ разработаны и используются экспериментальные компьютеры, основанные на подобных архитектурах. В качестве примера можно привести Lisp-машину.
 
=== Отложенные (ленивые) вычисления ===
Рис. 4. Диалоговое окно просмотра конструкторов типов
В верхнем поле представлен список всех имён конструкторов ти¬пов с соответствующей пиктограммой, обозначающей при¬ро¬ду конструктора. При помощи строки поиска можно осу¬щес¬т¬вить инкрементный поиск по всему списку — при вводе оче¬ред¬ной буквы курсор в списке перемещается на первое имя, которое на¬чинается на введённую последовательность символов. В поле «Type» приводится определение соответствующего типа. В двух ниж¬них полях предоставляется информация о конструкторах и се¬лекторах выделенного типа, а также об экземплярах типа (ес¬ли они есть).
При помощи этого диалогового окна разработчик может быс¬т¬ро перейти к редактированию выделенного конструктора (при на¬жатии на кнопку «Edit type») или к редактированию вы¬де¬лен¬но¬го экземпляра типа (при помощи нажатия на кнопку «Edit in-stance»).
2.3.4. Просмотр иерархии классов
Просматривая иерархию классов, программист может уви¬деть отношения наследования между созданными классами. Не¬об¬ходимо отметить, что алгоритм прорисовки классов и от¬но¬ше¬ний в HUGS 98 несколько неадекватен, поэтому для более пол¬но¬го понимания от программиста требуется либо чутьё, либо спо¬собность быстро разбросать все классы по диалоговому ок¬ну, создав планарный граф.
Рис. 5. Иерархия классов из файла Prelude.hs
 
== Лабораторная работа 1 ==
 
'''Цель:''' ''изучить основные принципы и методы функционального программирования; овладеть такими базисными возможностями функциональной парадигмы программирования как работа со списками, использование бесконечных списков, использование аккумуляторов, охраны и локальных переменных.''
# Для чего необходима конструкция описания λ-выражений на языке Haskell? Каким образом можно применять безымянные функции?
 
== Лабораторная работа 2 ==
 
'''Цель:''' ''изучить структуру и реализованные возможности файла начальной загрузки HUGS&nbsp;98 — <tt>Prelude.hs</tt>; узнать, какие классы, простые структуры данных и функции для их обработки уже&#769;уже́ реализованы разработчиками HUGS&nbsp;98.''
 
=== Предварительная подготовка ===
# По согласованию с преподавателем выбрать один класс и исследовать его свойства и методы.
# По согласованию с преподавателем выбрать один экземпляр какого-либо класса и исследовать его реализацию.
# Составить список всех функций, работающих с натуральными числами. Описа&#769;тьОписа́ть некоторые из них.
# Составить список всех функций, работающих с действительными числами. Описа&#769;тьОписа́ть некоторые из них.
# Составить список всех функций, работающих со списками. Описа&#769;тьОписа́ть некоторые из них.
# Составить список всех функций, работающих с символами и строками. Описа&#769;тьОписа́ть некоторые из них.
# Составить список всех типов и функций, описывающих примитивы из реализации HUGS&nbsp;98. Описа&#769;тьОписа́ть некоторые из них.
# Составить список всех монад. Описа&#769;тьОписа́ть одну из них.
# Составить список всех функций, работающих с консолью. Описа&#769;тьОписа́ть некоторые из них.
 
=== Выполнение работы ===
 
 
== Лабораторная работа 3 ==
 
'''Цель''': ''изучить расширенные возможности языка Haskell; овладеть навыками решения задач на перебор, сортировку и обход бинарных деревьев при помощи методов функционального программирования.''
=== Предварительная подготовка ===
 
После '''[[#Лабораторная работа 1|первой лабораторной работы]]''' в главном каталоге для проведения лабораторных работ по функциональному программированию уже&#769;уже́ должны быть созданы каталоги, названия которых соответствуют номерам групп, а также каталоги, названия которых соответствуют именам студентов. Если таких каталогов нет — их необходимо создать (подробнее см.&nbsp;предварительную подготовку к '''[[#Лабораторная работа 1|первой лабораторной работе]]''').
 
При помощи стандартного текстового редактора (Notepad для Windows) создать новый файл с расширением hs. Желательно, чтобы в названии файла был отражён номер текущей лабораторной работы.
##Генерация списка всех возможных расстановок максимального количества слонов на доске N&nbsp;x&nbsp;N клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
##Генерация списка всех возможных расстановок максимального количества ладей на доске N&nbsp;x&nbsp; N клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
##Генерация списка всех возможных расстановок минимального количества коней на доске N&nbsp;x&nsbp;N клеток таким образом, чтобы ни один из коней не бил другого. Конём называется фигура, ходящая на две клетки в прямом направлении, а пото&#769;мпото́м на одну клетку в перпендикулярном изна¬чальному (буквой «Г»).
##Поиск и генерация списка всех возможных расстановок восьми ферзей на шахматной доске (8&nbsp;x&nbsp;8) таким образом, чтобы ни один из ферзей не бил другого. Ферзём называется фигура, ходящая в любом направлении: по горизонтали, вертикали или диагонали.
##Генерация списка всех возможных расстановок N&nbsp;ферзей на доске N&nbsp;x&nbsp;N. В случае, если сгенерированный список получается пустым (например, для N&nbsp;=&nbsp;2), считается, что таких расстановок не существует.
=== Предварительная подготовка ===
 
После первой лабораторной работы в главном каталоге для проведения лабораторных работ по функциональному программированию уже&#769;уже́ должны быть созданы каталоги, названия которых соответствуют номерам групп, а также каталоги, названия которых соответствуют именам студентов. Если таких каталогов нет — их необходимо создать (подробнее см.&nbsp;предварительную подготовку к '''[[#Лабораторная работа 1|первой лабораторной работе]]''').
 
При помощи стандартного текстового редактора (Notepad для Windows) создать новый файл с расширением HS. Желательно, чтобы в названии файла был отражён номер текущей лабораторной работы.
 
Четвёртую лабораторную работу можно выполнять в домашних условиях, если существует такая возможность, так как она требует большого усердия и высоких временны&#769;хвременны́х затрат. Те студенты, которые не могут работать в домашних условиях, смогут за время, отведённое на лабораторную работу, только познакомиться с теоретическим материалом, и, возможно, начать разработку.
 
=== Задание ===
#Что такое «генетические алгоритмы»?
 
== Литература ==
 
=== Обязательная ===
#Джонс&nbsp;С., Лестер&nbsp;Д. Реализация функциональных языков. М.: Мир, 1991.
 
== Приложение ==
 
=== Языки функционального программирования ===
 
# '''Lisp''' (List processor). Считается первым функциональным языком программирования. Нетипизирован. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. Сейчас наиболее распространён диалект Common Lisp, ушедший от принципов ФП. Язык сложен в изучении, имеет очень непривычный синтаксис. Существует объектно-ориентированный диалект языка — CLOS.
# '''Scheme'''. Один из многих диалектов языка Lisp, предназначенный для научных исследований в области информатики. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем базовая версия языка Lisp. Отличается простотой как самого&#769;самого́ языка, так и стандартной библиотеки функций, хотя несколько проигрывает в универсальности. Кроме того, здесь точнее соблюдаются принципы функционального программирования.
# '''ISWIM''' (If you See What I Mean). Функциональный язык-прототип. Разработан Ландиным (США) в 60-х&nbsp;годах для демонстрации того, каким может и должен быть язык функционального программирования. Вместе с языком Ландин разработал и специальную виртуальную машину для исполнения программ на языке ISWIM. Эта виртуальная машина, основанная на вызове по значению, получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
# '''ML''' (Meta Language). Целое семейство строгих функциональных языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих университетах мира (в некоторых даже как первый язык программирования).
# '''Clean'''. Функциональный язык, специально предназначенный для параллельного и распределенного программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющих программировать графический пользовательский интерфейс под Win32 или MacOS.
# '''Erlang'''. Язык, разработанный компанией Ericsson, ориентирован на сферу коммуникаций; происходит от Пролога, хотя сейчас похож на него лишь внешне. Имеет лёгкий в освоении синтаксис, богатейшую библиотеку, в том числе: переносимый графический интерфейс, СУБД, распределенные вычисления и многое другое; причем всё это доступно бесплатно. Язык является параллельным изначально — возможность параллельной работы нескольких процессов и их взаимодействия заложена на уровне синтаксиса. Недостаток пока только один: компиляция в байт-код, для которого нужен «тяжёлый» и не слишком быстрый интерпретатор.
# '''Рефал'''. Функциональный язык, разработанный в СССР ещё в семидесятых годах XX&nbsp;ве&#769;каве́ка. В некоторых отношениях близок к Прологу. Крайне эффективен для обработки сложных структур данных типа текстов на естественном языке, XML и&nbsp;т.&nbsp;д. Эта эффективность обусловлена тем, что Рефал является единственным языком, использующим двунаправленные списки — это позволяет сократить объём некоторых программ и ускорить их работу (за счёт отсутствия необходимости в сборке мусора). К сожалению, в последнее время разрабатывается не очень активно. С другой стороны, по языку много документации на русском языке; имеется суперкомпилятор — система оптимизации программ на уровне исходных текстов (т.&nbsp;е. фактически оптимизация алгоритма!).
# '''Joy'''. Чистый функциональный язык, основанный на комбинаторной логике. Внешне похож на Форт: используется обратная польская запись и стек. Пока что находится в стадии развития, хотя уже&#769;уже́ имеет неплохую теоретическую основу. Существует даже прототипная реализация. Основное преимущество перед другими языками — линейная запись без переменных, что должно резко облегчить автоматизацию написания, проверки и оптимизации программ. Помимо недоразвитости, есть ещё один серьезный недостаток: как и у Форта, у Joy страдает читабельность.
 
=== Интернет-ресурсы по функциональному программированию ===
ИС HUGS&nbsp;98 предоставляет программисту возможность тонко настраивать интерпретатор и саму ИС под ту или иную задачу. Это возможно при помощи изменения настроек (параметров) ИС. На рис.&nbsp;П1 показано состояние настроек, загружаемых по умолчанию (такой набор параметров действует при первоначальной установке HUGS&nbsp;98).
 
[[ИзображениеФайл:OptionsHUGS.gif|center|Рис.&nbsp;П1. Диалоговое окно установка параметров ИС]]
 
<center>'''Рис.&nbsp;П1. Диалоговое окно установка параметров ИС'''</center>
 
В верхней части представленного диалогового окна находится набор так называемых флагов, значения которых могут быть либо ИСТИНА (флаг установлен), либо ЛОЖЬ (флаг сброшен). Каждый флаг отвечает за тот или иной параметр интерпретатора или само&#769;йсамо́й оболочки.
 
В нижней части диалогового окна настроек находятся поля ввода внутренних переменных окружения ИС HUGS&nbsp;98.
234

правки