?

Log in

No account? Create an account
Haskell: что это такое - Лямбда - функциональное программирование [entries|archive|friends|userinfo]
Лямбда - функциональное программирование

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Haskell: что это такое [Dec. 30th, 2005|08:01 pm]
Лямбда - функциональное программирование

ru_lambda

[avva]
[Tags|]

Я не знаю лучшего способа для себя что-то понять, чем попробовать объяснить это другим. Поэтому я решил учить Haskell следующим способом. Я буду читать tutorial (а именно Yet Another Haskell Turorial, который многие знатоки хвалят), и по мере чтения и решения упражнений буду сюда постить то, что понял или не понял. Если это кому-то окажется полезным, буду только рад. Я начну с нуля (некоторую часть я уже читал пару месяцев назад, но тогда забросил и с тех пор забыл)

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

Мне кажется, что некоторым здесь (и я включаю в это множество себя в первую очередь!) будет полезно, перед тем, как заниматься разбором кусков кода, посмотреть на Haskell издалека, попробовать понять, в чём вообще суть такого подхода к программированию, чем язык типа Haskell принципиально отличается от C или Java итп. Поэтому я попробую дать такое описание (опять-таки, очень может быть что неточное или неполное, и любые поправки и замечания приветствуются) перед тем, как заняться собственно чтением tutorial.

Итак, есть формальный документ, определяющий Haskell: The Haskell 98 Report. У этого документа есть также русский перевод. Глава первая, "Введение", первый абзац суммирует суть языка (я выбросил пару лишних слов, которые хвалят сам язык, ничего конкретного не говоря):
Haskell является чисто функциональным языком программирования общего назначения. Haskell обеспечивает функции высокого порядка, нестрогую семантику, статическую полиморфную типизацию, определяемые пользователем алгебраические типы данных, сопоставление с образцом, описание списков, модульную систему, монадическую систему ввода - вывода и богатый набор примитивных типов данных, включая списки, массивы, целые числа произвольной и фиксированной точности и числа с плавающей точкой.


Попробую теперь подойти к каждому пункту из этого перечисления по отдельности.

  • General-purpose programming language — язык программирования общего назначения

    Haskell - не язык, созданный для решения какого-то определённого вида проблем (domain-specific language), а язык, который в принципе подходит для решения очень широкого класса проблем, неограниченно широкого, потому что заранее никто не может предугадать, для чего ещё его можно использовать. Например, SQL - не язык широкого назначения, а язык запросов к базам данных; даже несмотря на то, что у него есть варианты (как PL/SQL в Оракле), где можно определять переменные, функции, циклы, и в принципе писать что угодно, на практике это никто делать не будет и не для этого он существует. А Haskell, как C++, Java, SmallTalk или Lisp, вообще говоря подходит для "чего угодно", с определёнными ограничениями.

  • pure functional / чисто функциональный

    Для того, чтобы описать, что такое функциональный язык, попробую оттолкнуться от знакомого - императивных и объектно-ориентированных языков.

    Что такое программа на императивном языке (C, например)? Последовательность указаний компьютеру, что ему делать. Желательно хорошо структурированная последовательность, с разбивкой на блоки (функции), с использованием переменных и структур данных, но в конечном итоге - план микроменеджмента того, чем надлежит заниматься компьютеру. Итак: программа как список команд.

    Что такое программа на объектно-ориентированном языке (Java, SmallTalk)? Есть иерархия классов, и набор объектов, эти классы воплощающих. Объекты хранят своё состояние, и общаются между собой путём вызова методов, создают и уничтожают себя и другие объекты итд. Объекты изолированы друг от друга в значительной степени, как благодаря привилегированному доступу методов класса к состоянию объекта (encapsulation), так и благодаря фундаментальному, полезному незнанию того, кого я собственно вызываю (может, того, кого я думаю, а может, его наследника), что заставляет меня полагаться только на объявленный интерфейс взаимодействия (polymorphism). Итак: программа как контролируемая эволюция системы автономных объектов.

    Функциональные языки ставят во главу угла функцию - подразумевая тут математическое понятие функции более, чем "функции", знакомые нам из императивных (или частично императивных) языков. Что такое функция с математической точки зрения? Некое правило, ставящее в соответствие любому аргументу, или любому набору из нескольких аргументов, фиксированное значение; при этом главнейшим является тот факт, что в ответ на один и тот же аргумент функция всегда даст одно и то же значение, сколько раз её не вычисляй. Это свойство называется однозначность или определённость функции.

    В C есть функции, мы все их знаем. У них даже есть аргументы, у каждого свой тип, и возвращаемое значение, у которого тоже есть свой тип. Но функции в C, кроме того, что они возвращают какое-то значение, делают множество других вещей; например, они могут общаться с пользователем, читать/писать информацию из файлов, менять какие-то структуры данных, выделять память под что-то или возвращать её, итд. итп. Зачастую собственно смысл существования функции на C — именно в том, что она делает, а не в том, какое значение возвращает; а значение — не возвращает никакого, или, скажем, код возможной ошибки самого её действия. Более того, если одну и ту же функцию на C вызвать два раза с совершенно идентичными аргументами, вовсе не факт, что она вернёт одно и то же значение. И очень может быть, что такой двойной вызов, если он не предусмотрен заранее, "испортит" работу программы в том смысле, что свои какие-то действия она повторит дважды, а это окажется неправильным.

    Попробуем себя ограничить и сказать: мы хотим функции, как в C (со списком аргументов и возвратным значением), но чтобы они больше походили на математические функции. Это не значит, что они будут работать именно с числами (математические функции тоже работают не только с числами, впрочем); в первую очередь это значит, что мы ограничим то, что они могут делать. Скажем, что единственным смыслом существования функции должно быть вычисление её значения, и ничто больше. Всё то, что функция на C может делать кроме этого - менять значение всяких переменных вне самой себя, писать в какие-то файлы, вообще менять что-то в окружающей среде - назовём побочными эффектами (side effects) и запретим - наши функции не должны этого делать. Всё, что наши функции делают - вычисляют то, что они должны вычислять, и возвращают; естественно, для этого они могут пользоваться какими-то своими временными переменными, вызывать другие функции (что очень важно), итд. итп. - но не менять ничего: только вычислить и вернуть. Более того, потребуем, чтобы функции наши были однозначно определёнными: одни и те же аргументы должны всегда привести к одному и тому же результату.

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

    На первый взгляд это кажется очень неудобным ограничением. Да, можно написать: int f(int a) { return a*a; }, и это будет функция возведения в квадрат, отвечающая нашим ограничениям - но далеко ли ускачешь с такими функциями? Как заставить компьютер делать то, что тебе хочется? Но оказывается, что эти ограничения, с одной стороны, казалось бы, отсекая почти всё то полезное, что мы привыкли делать в коде, очень сильно упрощают систему взаимодействия кусков кода друг с другом, позволяя тем самым нам делать всё те же сложные вещи, но другим путём, и, возможно, даже эффективнее и лаконичнее.

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

    Во-вторых, функция стала такой простой, предсказуемой штукой, что ей становится очень удобно пользоваться именно в качестве объекта внутри самого языка. Конечно, это есть и в C, например: можно держать ссылку на функцию (function pointer), передавать её другой функции, та другая может по ней вызвать то, на что указывает эта ссылка. В каком-то смысле это - использование функций в качестве объектов. Но всё-таки это частный случай, а не правило. В языке типа C есть огромная разница между if (x), где x - переменная, и if (*g(1,2,3)), где g - переменная типа ссылки на функцию. В первом случае налицо просто обращение к памяти, и ничто не мешает, скажем, повторить его ещё раз, если надо. "y=x; z=x;" — то же самое (я знаю, что здесь нужна оговорка, но простоты ради опустим её), что "y=x; z=y;". А если вместо x подставить *g(1,2,3), то это будут совершенно разные вещи, потому что в одном случае функция, адрес которой сидит в g, реально вызывается дважды, а в другом - один раз. И если она что-то делает кроме того, что собственно вычисляет свой результат; или даже если только вычисляет, но возвращает то одно, то другое - общий итог будет очень разный.

    А в функциональном языке - всё не так. Мы знаем заранее, что функция всегда вернёт одно и то же значение, если вызвать её с определённым аргументом; неважно при этом, когда вызвать или сколько раз. Это, во-первых, позволяет умному компилятору кэшировать её значение и действительно "по-настоящему" вызывать её только один раз с данным аргументом, даже если мы в своей программе делаем это многажды; и, во-вторых, даёт нам возможность передавать её в качестве объекта из функции в функцию, сохранять её в структурах данных, словно она число или строка, и делать с ней всё, что угодно, всё, что мы можем делать с любым другим значением. На практике это, оказывается, даёт невероятную свободу и лёгкость действий, недостижимую в языке, в котором на функции не накладываются такие ограничения. В программах на чисто функциональном языке функции всё время, постоянно, передают самих себя и другие функции в качестве аргументов, генерируют на лету функции в качестве значений, итд. итп. Когда говорят, что в функциональных языках функции - объекты первого класса (first-class objects) - эта терминология пришла из математики - имеют в виду именно это равноправие функций с другими значениями, которыми оперирует программа. Функции ничем, действительно ничем не отличаются от, скажем, чисел или строк или любых других значений сколь угодно простых или сложных типов, ими можно пользоваться абсолютно свободно, как и другими и значениями, и кроме того с функциями можно делать ещё одну дополнительную операцию: можно передать им какие-то аргументы и получить что-то взамен, какой-то результат.

    Это ещё далеко не полный список тех преимуществ, которые мы получаем, переходя к такому взгляду на функции. Если подумать: всё, что делают функции в программе на чисто функциональном языке - это вызывают друг друга (доходя в итоге до каких-то примитивов, реализованных на уровне компилятора/интерпретатора, конечно), получают какие-то значения... и что с ними делают? В языке типа C мы сказали бы: записывают их в какие-то переменные. Но наши функции не имеют побочных эффектов, они не могут ничего записывать "вне себя" (кроме своих временных переменных), они могут только возвращать. Значит, выходит, что в функциональном языке функциям не нужно менять значения переменных. По сути дела, они не могут это делать (чтобы не иметь побочных эффектов), но не нужно оказывается лучшим описанием происходящего, т.к. на самом деле это очень удобно. Это называется immutable values (неизменяемые значения). Предположим, мне нужно отсортировать список чисел. В C я могу сделать функцию, которая принимает ссылку на список, и сортирует числа прямо в этом списке (in-place); в функциональном языке у меня будет функция, которая принимает весь список в качестве аргумента, и возвращает новый отсортированный список в качестве результата. В каком-то смысле это трата памяти, и, возможно, времени (на создание/копирование структур); но, с другой стороны, насколько это упрощает работу и ментальную картинку того, как устроена программа! Нет больше "буферов", которые меняются и не знаешь точно, что в нём в данный момент сидит. Исчезли все проблемы с динамической памятью и её потерями - компилятор/интерпретатор сам проследит, какие значения мы ещё используем, а какие перестали, и всё для нас сделает. Отладка в тысячу раз проще: если где-то откуда-то возникло какое-то значение и где-то сохранено, то оно больше никогда не изменится. В общем, уследить за потоком данных по мере работы программы становится гораздо проще.

    Остаётся один очень важный вопрос. Если всё, что делает наш код в функциональном языке - это функции, которые вычисляют свои результаты, оперируя аргументами и вызывая другие функции - как мы собственно сможем когда-либо что-то сделать с точки зрения интеракции с внешним миром? Ясно, что компилятор/интерпретатор может позволить нам сказать написанной программе: вычисли f(...) и дать какой-то список аргументов, и она это сделает. Но как насчёт работы с файлами, с сетью, с стандартными вводом/выводом, всеми этими вещами? Ведь всё это - те самые побочные эффекты, которые наши функции иметь не могут! Тут разные функциональные языки решают эту проблему по-разному. Некоторые, например, ослабляют ограничение на побочные эффекты для определённых функций. Haskell же использует механизм, который называется "монады", и в каком-то смысле даёт нам возможность "говорить" с окружающим миром, не поступаясь нашими функциональными принципами. То, как этот механизм работает, я пока ещё не понимаю, поэтому и не буду пытаться объяснить; более того, известно, что это одна из самых сложных для понимания тем в процессе изучения Haskell. Но можно сказать, по-моему, что стоит изучить вначале "чистый" функциональный Haskell, не пытаясь понять монады, пока не разберёшься хоть немного и не привыкнешь к чисто функциональному подходу. Да, это значит, что не получается начать изучение языка с разбора программы "Hello world", но этим можно пожертвовать.



    Продолжение здесь.
linkReply

Comments:
[User Picture]From: dimrub
2005-12-30 06:31 pm (UTC)
Очень хорошее описание, аффтар, продолжай!
(Reply) (Thread)
[User Picture]From: kozodoev
2005-12-30 06:33 pm (UTC)
Почти все верно, кроме того, что процесс понимания через сравнения с императивными языками не кажется мне самым оптимальным - реально никакого противопоставления функциональный подход сам по себе не несет и никаких сознательных ограничений по сравнению с императивным не вводит.
Например, отказа от состояний как таковых на самом деле нет - просто состояния сами по себе вещь концептуально размытая. Чем, спрашивается, деструктивный апдейт переменной отличается от освобождения памяти занимаемой этой переменной?
Если попытаться строго ответить на этот вопрос, то выяснится, что замена этой операции например функциональной композицией ничего не изменит.

Что касается монад, то их сложность на самом деле - это такая детская страшилка. Ничего сложного в них нет - просто их обычно откладывают на потом, потому что понимание их зависит от понимания других вещей в хаскеле, например - конкретно, от понимания как работает его система типов.
Ну и еще конечно желательно, чтобы человек уже достаточно освоился, чтобы не проводить параллелей с императивным I/O - монады полностью декларативны и довольно сильно абстрактны, чтобы можно было просто так расписать соответствия.
(Reply) (Thread)
[User Picture]From: kozodoev
2005-12-30 06:58 pm (UTC)
вот наспех склеенное объяснение как можно организовать ввод-вывод в языке без побочных эффектов из одного моего комментарии про монады в какой-то конференции (сами монады конкретно тут не затрагиваются).
----
Понятно, что в общем это ограничение запросто может не касаться основной функции программы, которая может получать необходимые данные при вызове и возвращать нужный результат. Например, так:

> -- ПСЕВДОХАСКЕЛЬ
> main input = calcSomethingStupid (read input :: Int)


Уже что-то, но мало пригодно для чего-то, кроме вычислительных задач.

Следующей идеей, которая может прийти в голову, будет внешняя программа написанная на менее привередливом языке, которая читает с STDIN какой-то заранее определенный набор команд, выполняет их и направляет их результат туда, куда скажут. Так как это делает UNIX shell:

dd bs=10 count=1 if=/dev/random > random.value
# Но можно и:
dd bs=10 count=1 if=/dev/random | ./myprogram

То есть если мы запустим нашу программу как:

`./myprogram start`

то она сможет давать шеллу команду сделать что-то полезное вместе с указанием вызвать себя же с этим полезным в качестве входа.

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

> -- ПСЕВДОХАСКЕЛЬ
> -- функции main просто возвращает пару значений,
> -- где первый - это что сделать, а второй - куда его подать
> main _ = (readLine "Enter your name", hello)
> hello name = (writeLine name, ())
> -- функция hello принимает на вход строку и возвращает команду напечатать
> -- и пустое значение (), означающее, что пора заканчивать.
> -- readLine и writeLine просто представляют из себя функции,
> -- возвращающие закодированное сообщение в нужном виде для внешнего цикла

Cама семантика ввода-вывода необязательно должна быть императивной, в вполне может определяться как соответствие между _значением_ входа и выхода. То есть мы вполне можем читать программу вслух не как: <прочитать байт, прибавить единицу, записать байт>, а {функция от прочитанного байта будет равна записи этого байта плюс единица}. Причем, интуитивно нет оснований полагать, что такая интерпретация выглядит менее естественной, чем императивная.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: angerona
2005-12-30 11:37 pm (UTC)
Честно признаюсь, что обьяснение прочла до половины (сейчас времени нет, а по русски мне такие вещи медленно даются).

А чем Haskell лучше чем, скажем, Lisp или Scheme?

(define (a x y) (+ x y))

(define (b x arg1 arg2) (x arg1 arg2))

(b a 1 2) --> 3
(Reply) (Thread)
[User Picture]From: avva
2005-12-30 11:45 pm (UTC)
О том, чем он отличается (лучше или хуже - вопрос вкуса), в основном ещё не написано. Это, например, умная статическая типизация, а также lazy evaluation.
(Reply) (Parent) (Thread) (Expand)
From: indimo
2005-12-31 12:28 am (UTC)

небольшая неточность

"Объекты хранят своё состояние, и общаются между собой путём вызова методов, создают и уничтожают себя и другие объекты"

Понятно что вы дали краткое описание, но все же, в общем случае, объекты посылают сообщения другим объектам. В зависимости от реализации языка ООП, посылка сообщений сводится к вызову метода, к примеру, в Java.
Это реализовали как истинное сообщение в smalltalk. Так существует специальный метод, который реализует вызов других методов, имея в аргументах сообщение.
(Reply) (Thread)
[User Picture]From: avva
2005-12-31 12:44 am (UTC)

Re: небольшая неточность

Я первоначально перечислил несколько терминологических вариантов в скобках, а потом решил упростить.

По-моему, Вы правы и неправы. Можно назвать это вызовом метода, а можно посылкой сообщения; второе иногда предпочтительней с точки зрения пуриста, но это вопрос предпочтения той или иной концептуальной метафоры, а не общности понятия. Что такое есть "посылка сообщения" или "вызов метода", зависит не от названия, а от сути языка, в первую очередь, от того, статическая в нём привязка или динамическая. Так, в Перле она динамическая и хотя операция называется "вызов метода", она позволяет те же динамические удобства, что и Smalltalk - например, аналог смоллтоковского doesNotUnderstand итп.
(Reply) (Parent) (Thread)
[User Picture]From: catpad
2005-12-31 12:57 am (UTC)
Очень хорошо написано, просто и по делу. Очень хочется продолжения, потому как Haskell интересен, а руки до него не доходят. Про монады интересно бы узнать.
Продолжай, пожалуйста.
(Reply) (Thread)
[User Picture]From: avva
2005-12-31 10:51 am (UTC)
Спасибо! Обязательно буду продолжать, наверное завтра - сегодня слишком занят по очевидным причинам :)

До монад руки дойдут, но не сразу, а, думаю, недели через две, т.к. я их не знаю, а напишу, когда узнаю и пойму в процессе обучения.
(Reply) (Parent) (Thread)
[User Picture]From: volan
2005-12-31 08:19 am (UTC)

Очень любопытно

Прочту все.

Спасибо.
(Reply) (Thread)
From: 314truha
2005-12-31 10:26 am (UTC)
Замечательно написано - просто, доступно и удобоваримо. Аффтар, пишы ищо, жду с нетерпением.
(Reply) (Thread)
[User Picture]From: stas
2005-12-31 01:57 pm (UTC)
Спасибо за описание, я наконец-то начинаю понимать, в чём же дело в функциональных языках.
(Reply) (Thread)
[User Picture]From: 109
2005-12-31 06:50 pm (UTC)
спасибо! про ввод-вывод действительно непонятно. даже точнее, непонятно про побочные действия, типа открытия tcp сессии и посылки туда чего-нибудь. если язык, декларирующий невозможность побочных действий, находит способ таки делать эти побочные действия, много ли толку от такой декларации?
(Reply) (Thread)
From: ex_ex_zhuzh
2006-01-01 04:10 pm (UTC)
Декларируется не невозможность побочных действий, а их хорошее поведение. В частности, по типу функции всегда можно понять, допускает она побочные действия или нет, а если да, то какие именно.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: kozodoev
2006-01-01 04:28 pm (UTC)
Много. Потому что побочные эффекты тем не менее невозможны.
Кто сказал, что это язык делает побочные эффекты?
(Reply) (Parent) (Thread) (Expand)