Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 1102 03-09-2006 01:51 | |
сообщение от модератораinfo21 и Jack of Shadows получают по замечанию за сообщения №№1094 и 1097.
info21: может, хватит уже ветки гробить? Отрицательный опыт ничему не учит? Несогласие с Jack'ом можно было выразить не в столь оскорбительной форме.
№ 1101 02-09-2006 17:55 | |
Ответ на »сообщение 1100« (Geniepro)
___________________________
Думаю, программа на Ассемблере будет быстрее аналогичной на С++... ;-)
Возможно, но C++ в отличии от ассемблера высокоуровневый язык. Ладно, не буду оффтопить. :)
№ 1100 02-09-2006 17:29 | |
Ответ на »сообщение 1099« (Билли)
___________________________
Всем сомневающимся, что C++ самый быстрый язык (ну или в том, что для него созданы лучшие компиляторы :) ), предлагаю challenge: С++ vs all. Хотя это, наверное, не по теме.
Не только не по теме, но и не по сайту! :-))
Думаю, программа на Ассемблере будет быстрее аналогичной на С++... ;-)
№ 1099 02-09-2006 17:06 | |
Ответ на »сообщение 1097« (Jack Of Shadows)
___________________________
Ответ на »сообщение 1094« (info21)
___________________________
Господину info21 остается только посоветовать посмотреть на бенчмарки ФЯ vs ИЯ вот здеь хотя бы:
Clean (чистый ленивый ФЯ):
Против Оберона: http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=clean&lang2=ooc
Против Паскаля: http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=clean&lang2=fpascal
Против сишарп: http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=clean&lang2=csharp
Там же можете посмотреть на результаты Ocaml и Хаскель.
Они не столь впечатляющи как у Clean, но тоже вполне на уровне.
Из приведенных бенчмарков видно, что скорость работы программ зависит прежде всего от реализации конкретного компилятора, а не от того функциональный ли я зык или императивный.
Повторяю еще раз ЧИСТЫЙ ФУНКЦИОНАЛЬНЫЙ язык, НА ВСЕХ приведенных примерах бьет императивные, ВКЛЮЧАЯ ОБЕРОН.
Бенчмарки :), вот на С++, например, делается inline-функция и передаётся стандартному алгоритму указатель на неё... Ламеры, одно слово, что там ещё можно смотреть. Или другой пример с бинарным деревом. Какой идиот в простейшем примере будет использовать виртуальные функции? Но там они используются. :)
Всем сомневающимся, что C++ самый быстрый язык (ну или в том, что для него созданы лучшие компиляторы :) ), предлагаю challenge: С++ vs all. Хотя это, наверное, не по теме.
№ 1098 02-09-2006 16:56 | |
Интересный проект - LLVM Low Level Virtual Machine http://llvm.org
Отличается от .NET и JVM очень агрессивными оптимизациями, в том числе и развёрткой обычных рекурсий в хвостовые!
По крайней мере на страничке http://llvm.org/demo/ код функций Аккермана, Фибоначчи и факториала (на Си) вроде как компилируется в байт-код LLVM в хвостово-рекурсивном виде!
Щас вот пытаюсь разобраться, правильно ли он генерирует код... :-))
№ 1097 02-09-2006 13:29 | |
№ 1096 02-09-2006 13:17 | |
№ 1095 02-09-2006 05:52 | |
Ответ на »сообщение 1089« (Jack Of Shadows)
___________________________
То есть ваша задача написать рекурсию, удовлетворяющюю требованиям хвостовой рекурсии.
А уж компилятор, получив от вас такую рекурсию, срубит с нее весь стек.
Видимо хаскелю че то там не понравилось в вашем коде, и он решил что стек обрубить невозможно.
Необходимым условием хвостовой оптимизации рекурсии является то что перед передачей вызова дальше, функция не должна иметь локальную переменную от которой зависит результат.
Я не понимаю, что в варианте на Хаскеле неправильно и не соответствует этому требованию. Ведь он один в один копирует вариант на F#. ГДЕ там локальные переменные? Их нет там!
Хорошо, упростим задачу: (defun fact2 (n &optional (acum 1))
(if (< n 2) acum
(fact2 (1- n) (* acum n)))) Это Ваш вариант факториала на Лиспе. Перепишем на Хаскель: fact n = facttail n 1 where
facttail k v = if k==1 then v else facttail (k-1) (v*k) Сразу вспомним о том, что умножение больших чисел занимает много времени и памяти (и потому практически не позволит нам проверить вызов с аргументом, больше 100 тысяч), поэтому упростим задачу (заменим умножение ( v*k) прибавлением единицы ( v+1)): test n = testtail n 1 where
testtail k v = if k==1 then v else testtail (k-1) (v+1) Результат: test 1000000 даёт переполнение стека! Хотя вариант, где вообще не произодится операций с v: test n = testtail n 1 where
testtail k v = if k==1 then v else testtail (k-1) v стек не перегружает! В чём тут же убеждаемся, запустив test 1000000000 - через почти две минуты скомпилированный GHC код даёт результат: 1 (что и ожидалось получить).
Но ведь такой вариант ( testtail k v = if k==1 then v else testtail (k-1) v ) не имеет никакого практического смысла!
В чём дело? Что не так?
ЗЫ. Кстати, две минуты у GHC - это ОЧЕНЬ медленно, хотя и компилятор - на F# аналогичная функция выполняется за 1.64 сек (в 70 раз быстрее!!!)! И, кстати, вариант let rec testtail k v = if k=1 then v else testtail (k-1) (v+1) на F# стек нисколько не переполняет, и работает за те же 1.64 сек!
№ 1094 02-09-2006 05:26 | |
Ответ на »сообщение 1090« (Jack Of Shadows)
___________________________
.. ФЯ может памяти гораздо больше использовать чем ИЯ, но быть медленнее нет никаких предпосылок. ..
Более того, ocaml бьет по скорости с++, pascal, delphi, oberon, csharp, java на любых задачах.
"Остапа понесло" (С) Ильф и Петров.
Особенно сильно сказано "на любых задачах".
Тем более ставить в один ряд ... все это. (Лично я просто охреневаю от такого полета мысли.)
Если учесть, что скорость доступа к RAM'у все сильнее отстает от скорости доступа к кешу, то чем лучше локализованы данные и код, тем больше выигрыш у аккуратно спроектированного (на обероне, конечно) алгоритма.
Наоборот, "размазывание" списков по всей памяти ровным слоем, типичное для ФЯ -- ощутимо сказывается в плане производительности.
Вспоминается дополнение Вирта к закону Мура: "Софт бухнет и тормозится быстрее, чем ускоряется железо." Это как раз в глаз без преувеличения безумному предложению насчет алгоритма сортировки, который тут когда-то профигурировал.
Что-то у меня в третий раз сильные сомнения насчет того, понимает ли JOS то, что он провозглашает.
№ 1093 01-09-2006 23:14 | |
Ответ на »сообщение 1091« (Антон Григорьев)
___________________________
А вот пример факториала написанный с учетом требований хвостовой рекурсии: »сообщение 717«
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|