Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 572 03-08-2006 15:27 | |
Ответ на »сообщение 570« (Lisp Hobbyist)
___________________________
Кстати, а че это мы с вами переключились на обсуждение оптимизации ?
Это никакого отношения к теме не имеет.
Во первых я уже показал что это дело конкретной реализации компилятора, а не того функциональный ли язык или императивный.
Во вторых тот же Clisp например несмотря на то что гораздо медленнее Lispworks или ACL тем не менее более чем в 2 раза быстрее python и более чем 5-6 раз быстрее чем ruby.
При этом такая вот тормознутость не мешает python и ruby по праву завоевывать бешенную популярность, особенно в разработке web приложений.
Тот же Clisp например в связке с библиотекой UCW мечта просто для web разработки.
При этом гораздо быстрее python и ruby.
№ 571 03-08-2006 14:02 | |
Ответ на »сообщение 570« (Lisp Hobbyist)
___________________________
Lispworks 4.4.6 под windows
(defun fib-test (f)
(loop for i in '(33 40 42 45)
do (format t "~%~A -> ~A~%" i (time (funcall f i)))))
user time = 0.281
system time = 0.000
Elapsed time = 0:00:00
Allocation = 2304 bytes standard / 3102 bytes conses
0 Page faults
33 -> 3524578
Timing the evaluation of (FUNCALL F I)
user time = 7.593
system time = 0.000
Elapsed time = 0:00:08
Allocation = 8776 bytes standard / 1067 bytes conses
0 Page faults
40 -> 102334155
Timing the evaluation of (FUNCALL F I)
user time = 19.937
system time = 0.015
Elapsed time = 0:00:21
Allocation = 23736 bytes standard / 4103 bytes conses
0 Page faults
42 -> 267914296
Timing the evaluation of (FUNCALL F I)
user time = 86.984
system time = 0.000
Elapsed time = 0:01:34
Allocation = 10416 bytes standard / 3883 bytes conses
0 Page faults
45 -> 1134903170
NIL
CL-USER 2 >
Попробуйте сделать на дельфи или любом другом компилируемом языке, вам доступном и сверьте результаты.
Думаю разницы особой не будет.
А Clisp насколько я знаю компилирует в псевдокод.
Попробуйте DrScheme.org
№ 570 03-08-2006 13:47 | |
Ответ на »сообщение 569« (Jack Of Shadows)
___________________________
Как видите все в порядке с оптимизацией рекурсии в лиспе :))
Какая система используется? В clisp 2.33 компиляция ускоряет вычисления, но все равно, разрыв остается существенным. Еще было бы интересно увидеть результаты измерений для бОльших значений n, например, для чисел вида K * 100 (или для K * 1000, чтобы не мелочиться). Заранее благодарю.
№ 569 03-08-2006 11:53 | |
Ответ на »сообщение 568« (Lisp Hobbyist)
___________________________
Вы забываете все время что лиспы работают как интерпретаторы в REPL.
Надо явно компилировать.
Я прогнал ваши функции fib-test с компиляцией и в режиме интерпретации.
В режиме интерпретации результаты практически идентичны вашим.
А вот результат прогона скомпилированной функции:
CL-USER 6 > (fib-test #'fib)
Timing the evaluation of (FUNCALL F I)
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
1 -> 1
Timing the evaluation of (FUNCALL F I)
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
5 -> 5
Timing the evaluation of (FUNCALL F I)
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
12 -> 144
Timing the evaluation of (FUNCALL F I)
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
20 -> 6765
Timing the evaluation of (FUNCALL F I)
user time = 0.062
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
30 -> 832040
Timing the evaluation of (FUNCALL F I)
user time = 0.109
system time = 0.000
Elapsed time = 0:00:00
Allocation = 3656 bytes standard / 3740 bytes conses
0 Page faults
31 -> 1346269
Timing the evaluation of (FUNCALL F I)
user time = 0.156
system time = 0.000
Elapsed time = 0:00:00
Allocation = 3160 bytes standard / 1947 bytes conses
0 Page faults
32 -> 2178309
NIL
CL-USER 7 >
Как видите все в порядке с оптимизацией рекурсии в лиспе :))
№ 568 03-08-2006 09:46 | |
Ответ на »сообщение 566« (Jack Of Shadows)
___________________________
Все scheme имеют tail call optimization.
Возможно, я что-то упускаю из виду, но разве в примере с числами Фибоначчи накладные расходы на хвостовые вызовы играют решающую роль в потере производительности? ИМХО, куда важнее то, что здесь многократно перевычисляется одно и то же в двух ветках графа вызовов (число F(n-2) вычисляется само по себе и в ходе вычисления F(n-1)).
Что же касается исходного вопроса, будет ли такая программа оптимизироваться, могу сказать следующее: системой CLisp (2.33) --- не будет. Кстати, любителям unit test'ов может показаться интересным, как просто и элегантно в Лиспе пишутся "testbenches":
(defun fib (n)
(cond ((< n 3) 1)
(t (+ (fib (1- n)) (fib (- n 2))))))
(defun fib-test (f)
(loop for i in '(1 5 12 20 30 31 32)
do (format t "~%~A -> ~A~%" i (time (funcall f i)))))
...
> (fib-test #'fib)
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 0 Bytes
1 -> 1
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 0 Bytes
5 -> 5
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 0 Bytes
12 -> 144
Real time: 0.015625 sec.
Run time: 0.015625 sec.
Space: 0 Bytes
20 -> 6765
Real time: 2.640625 sec.
Run time: 2.609375 sec.
Space: 0 Bytes
30 -> 832040
Real time: 4.625 sec.
Run time: 4.546875 sec.
Space: 0 Bytes
31 -> 1346269
Real time: 7.484375 sec.
Run time: 7.359375 sec.
Space: 0 Bytes
32 -> 2178309
Отсюда следует, что оптимизация вычисления общих подграфов на графе редукции CLisp'ом не выполняется. Собственно, это не удивительно, так как Лисп все-таки не чисто функциональный язык, поэтому в приоритетах разработчиков Лисп-систем тонкая оптимизация выполнения аппликативных программ, скорее всего, занимает далеко не первое место. Рискну даже предположить, что дальше оптимизации хвостовых вызовов (полезных не только для ФП) дело вообще не идет.
В качестве альтернативы, я рискнул написать свой собственный вариант аппликативного расчета чисел Фибоначчи, который является ни чем иным, как императивным циклом, выраженным через рекурсию. Заранее предупреждаю, что писалось на скорую руку, так что формального доказательства корректности алгоритма я не предоставлю. Чтобы протестировать этот вариант функции, воспользуемся уже готовым testbench'ем:
(defun fib-tail (n &optional (f1 1) (f2 1))
(cond
((< n 3) f1)
(t (fib-tail (1- n) (+ f1 f2) f1))))
...
> (fib-test #'fib-tail)
Вывод я здесь приводить не буду, скажу лишь, что результаты совпали :-), а время исполнения на всех тестовых данных оказалось за пределами точности таймера.
Как писал в свое время Paul Graham (если не ошибаюсь): "Быстро написать программу на Лиспе просто. Куда сложнее написать на нем быструю программу."
№ 567 03-08-2006 02:48 | |
Ответ на »сообщение 565« (Geniepro)
___________________________
WinHugs это интерпретатор.
Естественно никакой оптимизации.
Попробуйте GHC компилятор. Мне самому интересно, что вы там получите. :))
№ 566 03-08-2006 02:46 | |
Ответ на »сообщение 565« (Geniepro)
___________________________
Все scheme имеют tail call optimization.
Многие лиспы тоже.
Так например оба коммерческих лиспа Lispworks и ACL имею tail call optimization.
По моему бесплатные Clisp и SBCL тоже.
Попробуйте
DrScheme.org или http://clisp.cons.org/
№ 565 03-08-2006 02:28 | |
У меня практический вопрос к серьёзным лиcперам и хаскеллистам.
Оптимизируют ли ваши трансляторы рекурсивные вызовы в функциях типа:
(defun fib(n)
(cond ((< n 3) 1)
('t (+ (fib (1- n)) (fib (- n 2)))
)
)
и
f :: Int -> Int
f 1 = 1
f 2 = 1
f n = f(n-1) + f(n-2)
Как у вас растёт время выполнения такой функции от увеличения аргумента - линейно или экспоненциально?
Я почему спрашиваю - если время растёт экспоненциально, значит оптимизации нет и программисту придётся постоянно думать о том, как будет выполняться его функция, и как её реализовать - рекурсивно или итеративно (императивно)...
А таких случаев может быть немало...
У меня есть простенькие (бесплатные) системы -
в WinHugs время выполнения растёт просто катастрофически,
newLisp - непонятно что, какой-то несовместимый с Common Lisp'ом диалект,
Ufasoft LispStudio - не знаю как её заставить работать...
Можете ещё раз посоветовать нормальные оптимизирующие компиляторы Лиспа и Хаскелля?
№ 564 02-08-2006 23:52 | |
Ответ на »сообщение 563« (Jack Of Shadows)
___________________________
То же самое и с передачей функций как параметров. Ее НЕТ В ИЯ. Не потому что невозможно это делать физически, а потому что слишком неуклюже, слишком много лишнего кода писать приходится. Поэтому никто этим не пользуется.
В результате в коде ИЯ программистов передачи функций как параметров НЕТ. Хотя они вам легко приведут такой код в качестве доказательства, после чего удовлетворенные "победой" вернутся писать свой код и все также не будет применять этот механизм.
Jack, я Вам уже приводил обратный пример, но Вы уперлись так же, как и Ваши оппоненты и не замечаете очевидных вещей.
Что принесло наибольший успех Delphi 1, как средству разработки? Правильно, механизм событий. Ну так с какого перепугу установка обработчика события перестала являться передачей функции (процедуры) как параметра? И если программист при разработке своего ПО следует идеологии Delphi (а не C/C++/Turbo Pascal и пр.), то у него тоже появляется досточно много классов, имеющих события.
Например, в системе, которую мы (на работе) разрабатываем, многие вещи действительно хоторошо работают только потому, что используют механизм событий.
Делегаты в C# тоже никто не отменял.
№ 563 02-08-2006 15:32 | |
Ответ на »сообщение 562« (Geniepro)
___________________________
По-моему, отличие только в том, что при передаче кода этот код описывается в месте его передачи, а при передаче процедуры этот код описывается чёрти где от места его передачи.
Да отличие ТОЛЬКО в этом. Да вот это ТОЛЬКО дорого стоит. Есть такое поняте enabler. Не знаю как по русски, но смысл таков. Свойство достаточно легкое чтобы применялось повсеместно. Соответственно просто иметь свойство недостаточно. Если оно будет неудобным для использования, его никто не будет применять. Будут делать похуже, но полечге для себя. То есть обходить это свойство стороной.
Здесь уже шел разговор о рекурсии. Так вот рекурсии в ИЯ НЕТ. Не потому что нет физически, а потому что этот механизм настолько неудобен в ИЯ, что им никто не пользуется. То есть рекурсии нет в коде программистов, пишуших на ИЯ.
Хотя в языке она поддерживается.
То же самое и с передачей функций как параметров. Ее НЕТ В ИЯ. Не потому что невозможно это делать физически, а потому что слишком неуклюже, слишком много лишнего кода писать приходится.
Поэтому никто этим не пользуется.
В результате в коде ИЯ программистов передачи функций как параметров НЕТ. Хотя они вам легко приведут такой код в качестве доказательства, после чего удовлетворенные "победой" вернутся писать свой код и все также не будет применять этот механизм.
При этом есть такие вот энейблеры (enablers) и у ИЯ программистов. Благодаря этим инструментам, которые делают передачу функций как параметров легкой, они начинают вовсю этим пользоваться и даже не представляют себе как это они могли без этого жить. Я об event-driven programming говорю :))
То что Борландд и MS создала внешнюю по отношению к языку тулзу (IDE) и компоненты которые позволяют "автоматически" передавать функции (в данном случае ивенты) привело к тому что все программисты повально этими "ивентами" пользуются. А попробуй сам написать. Для спора на форуме - пожалуйста, для ежедневной работы - ну его нафиг.
В случае с рекурсией я приводил пример того как один и тот же программист решая одну и ту же задачу, на ИЯ не будет пользоваться рекурсией, а на ФЯ - будет.
Так вот та же ситуация с передачей функций как параметров.
Тот же самый программист, та же самая задача.
В ИЯ никаких передач функций (кроме тех что для тебя делает среда, то есть ивенты)
В ФЯ - сплошь и рядом, СПЛОШЬ И РЯДОМ.
Эти вот "только" и "всего лишь" на самом деле дорого стоят, имеют принципиальное значение.
К сожалению, для того чтобы понять это, программисту нужно столкнуться с этим на практике, самому попробовать на зуб, так сказать. То есть поработать на ФЯ, решить практическую и нетривиальную задачу на ФЯ.
На это мало кто идет. Ограничиваются спорами на формуах о том чего не ели.
Вот мы с вами воду из пустого в порожнее и переливаем.
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|