Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 582 04-08-2006 05:04 | |
Ответ на »сообщение 578« (Jack Of Shadows)
___________________________
>>>без проблем которые приносит ООП со своим наследованием.
Что вообще отказываются от отношения частное-общее?
№ 581 04-08-2006 03:38 | |
Ответ на »сообщение 572« (Jack Of Shadows)
___________________________
Кстати, а че это мы с вами переключились на обсуждение оптимизации ?
Это никакого отношения к теме не имеет.
Очень даже имеет. Во-первых, рекламируя выгоды функционального подхода (которых я не отрицаю!), нужно добросовестно информировать окружающих и о той цене, которую им придется за них заплатить. Автоматическое распараллеливание и прочие прелести ФП пока что ИМХО еще не вышли за пределы исследовательских лабораторий, а писать программы приходится здесь и сейчас.
Во-вторых, говоря о ФП, Вы почему-то упорно сводите его к Лиспу. Я не отрицаю того факта, что Лисп существенно удобнее для ФП, чем традиционные императивные языки (разница даже не количественная, а качественная). Но несмотря на это, я считаю, что Лисп в данный момент не имеет эффективности в ФП, сравнимой с языками, специально под него заточенными. Я уже косвенно упоминал, почему так думаю, теперь расшифрую подробнее --- для тех, кто с Лиспом плохо знаком. Дело в том, что существенную часть стандарта ANSI Common Lisp занимают сугубо императивные средства. Если судить о языке исключительно по тому, что Вы, Jack, о нем здесь рассказываете, может сложиться мнение, что на Лиспе пишут преимущественно в функциональном стиле. Количественных измерений проводить не берусь, но рискну утверждать, что императивный подход (а скорее, смешанный) если не преобладает, то по крайней мере достаточно распространен, чтобы с ним считаться. В любом случае, достаточно того, что императивная составляющая прописана в стандарте. Как следствие, разработчики компиляторов просто не в состоянии реализовать все те оптимизации, которые могут себе позволить разработчики реализаций чистых ФП-языков. Дело ухудшается еще и тем, что Лисп в дополнение к наличию в нем императивных составляющих, еще и динамичен (динамическая типизация + перекомпиляция "на лету", за что я его и люблю). Для разработчиков оптимизирующих компиляторов это ночной кошмар.
Особо хочу оговорить, что сказанное выше --- не довод против Лиспа. В нем есть достаточно других свойств, делающих его в моих глазах на голову выше других языков: макросы, рефлексивность, легкость определения Domain-Specific Languages. Но рекламировать Лисп в контексте чистого ФП --- ИМХО, некорректно.
В третьих, обсуждая пример с числами Фибоначчи, Вы к чему-то упомянули оптимизацию хвостовой рекурсии, которая там не при чем. Ну нет там хвостовой рекурсии, а есть параллельная. Которая к тому же и не оптимизируется.
Во первых я уже показал что это дело конкретной реализации компилятора
Во-первых, ИМХО всецело полагаться на "интеллект" компилятора опасно, а во-вторых, взглянем еще раз на Ваши измерения (с Вашего позволения, я их немного подчистил для наглядности):
user time = 0.281
33 -> 3524578
user time = 7.593
40 -> 102334155
user time = 19.937
42 -> 267914296
user time = 86.984
45 -> 1134903170
Как говорится, прошу уважаемую публику обратить внимание: рост времени вычислений нелинейный! Что и требовалось доказать --- никаких высокоуровневых оптимизаций, устраняющих "последствия" параллельной рекурсии с повторяющимися аргументами, компилятор не делает.
Во-вторых, Jack, я же просил выдать мне результаты измерений для куда больших чисел, например, для 100, 200 или 1000. Что-то мне подсказывает, что это неспроста.
Со своей стороны, могу их показать:
[6]> (time (fib-tail 100))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 1016 Bytes
354224848179261915075
[7]> (time (fib-tail 200))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 3328 Bytes
280571172992510140037611932413038677189525
[8]> (time (fib-tail 1000))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 53000 Bytes
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875
Первоначальный вариант функции fib я вообще не запускал, так как у меня уже на аргументах порядка 50 мне надоедает ждать.
Как и прежде, изменения делаются на интерпретаторе clisp, но уже при скомпилированной функции. Корректность результата почти проверена Maxima --- проверил совпадение нескольких первых/последних цифр. Почему это отличается от результата Trurl --- не знаю. :-) Возможно, его функция вычисляет что-то другое, я не знаю Haskell.
"Вот что истинно хвостовая рекурсия-то делает..."
№ 580 04-08-2006 02:22 | |
Ответ на »сообщение 573« (Geniepro)
___________________________
Lisp Hobbyist, а на каком железе Вы это вычисляли?
P4/2.8GHz
№ 579 04-08-2006 01:41 | |
Ещё про числа Фибонначи.
fib n = fibs!!n
where fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
>fib 1000
7033036771142281582183525487718354977018126983635873
2742604905087154537118196933579742249494562611733487
7504492417659910881863632654502236471060120533741212
73867339111198139373125598767690091902245245323403501
Время вычисления даже на Hugs - доли секунды.
№ 578 03-08-2006 20:31 | |
Ответ на »сообщение 577« (Geniepro)
___________________________
Отнюдь. Дело не в этом.
В конце концов и в хаскеле нужно работать с состоянием и хранить его в переменных.
ООП это не просто "данные + методы". ООП это метод достижения некоторых целей, а именно инкапсуляции и полиморфизма. Не единственно возможный метод.
Существуют и другие механизмы которые позволяют достичь тех же результатов.
Посмотрите например type classes и modules в хаскеле.
Совместно они дают вам все что только может дать вам ООП. При этом в гораздо более понятном, простом виде, и без проблем которые приносит ООП со своим наследованием.
То есть функциональное Программирование дает вам ту же инкапсуляцию и тот же полиморфизм что и ООП.
Поэтому обьекты там лигние просто. Их нет смысла испольовать. Они ничего не приносят, только все осложняют.
В принципе это можно разобрать на примерах, просто у меня щас времени нет. Можно попросить кого нибудь из знающих хаскель разобрать эту тему.
№ 577 03-08-2006 18:57 | |
Ответ на »сообщение 561« (Jack Of Shadows)
___________________________
О том что ООП и ФЯ мягко говоря несовместимы, и что если вы приняли на веру ООП, то это сильно ограничивает ваши возможности как программиста.
Насколько я понимаю, эта несовместимость происходит от того, что ФЯ в чистом виде не позоляют делать вычислений с побочными результатами, а в ООП все функции(методы) именно побочными эффектами и занимаются (меняют состояние обьекта-хозяина)...
№ 576 03-08-2006 18:33 | |
Ответ на »сообщение 575« (Jack Of Shadows)
___________________________
Ответ на »сообщение 574« (Geniepro)
Это вы нам должны сказать что вы об этом думаете :))
Я могу говорить только о том чем пользуюсь сам.
Дык я пока ничего об этом не могу думать - потому и спросил, может кто уже пробовал, поделится впечатлениями...
Кстати, я тут нашёл некий Helium - http://www.cs.uu.nl/helium/distr/SetupHelium1.6.exe
Позиционируется для обучения Хаскеллю.
Весит немного, всего полтора метра, так что попробую, посмотрю, что это такое...
№ 575 03-08-2006 18:06 | |
Ответ на »сообщение 574« (Geniepro)
___________________________
Что об энтом думаете?
Это вы нам должны сказать что вы об этом думаете :))
Я могу говорить только о том чем пользуюсь сам.
№ 574 03-08-2006 17:23 | |
№ 573 03-08-2006 16:08 | |
2 Jack Of Shadows & Lisp Hobbyist
Окей, спасибо!
Закачал CLisp 2.39, что-то так быстро и незаметно (7 МБт), аж удивился... Надеюсь, её изучение пойдёт у меня такими же темпами... :-)
Щас качаю plt-352, как я понял, это версия Scheme-системы.
Потом поищу и GHC.
(Блин, что-то я за слишком многое решил взяться. Даже Рефал зачем-то скачал... :-( )
____________________
По поводу чисел Фибонначи.
Естественно, я бы не стал на практике использовать тут рекурсию. :-)
Просто этот пример показался мне самой простой и яркой иллюстрацией к моему вопросу - будет ли оптимизирована функция с несколькими рекурсивными вызовами? ;-)
Не просто какой-то там факториал, а вот типа Фибонначи...
А на практике, если бы нужно было, я бы использовал что-то типа такого варианта:
f(n)=(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5)
(придумал в школе, изучая ряд Люка, так что сильно не смейтесь... :о)) )
Такая формула практически не чуствительна к значению аргумента, если использовать сопроцессор, конечно. Вычисляет за раз! :-))
Хотя, впрочем, там возведение в (целочисленную) степень n тоже итеративно... Кажется... :-(
Как писал в свое время Paul Graham (если не ошибаюсь): "Быстро написать программу на Лиспе просто. Куда сложнее написать на нем быструю программу."
Это справедливо не только для Лиспа. :-)
Как говорится, медленно запрягаем, да быстро ездим! :о)
ЗЫ. Lisp Hobbyist, а на каком железе Вы это вычисляли?
У меня на Селероне 1700 на Компонентном Паскале при n=32 время расчёта было 1.36 сек.
У Вас всего в пять раз медленнее. Для интерпретатора очень неплохо...
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|