Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 602 07-08-2006 12:19 | |
Ответ на »сообщение 601« (Lisp Hobbyist)
___________________________
Простите но автоматическая мемоизация это из области фантастики :))
Основывать свои утверждения на том что никто никогда не делал, и даже не имел планов,
это все равно что доказывать вечный двигатель, чего я конечно же не собираюсь делать так же как и французская академия. :))
Засим оставляю вас с вашими планами по автоматической мемоизации.
А пока что жду существенного ускорения предложенного вами первоначально алгоритма на любом из СУЩЕСТВУЮЩИХ языков.
Если хотите могу исправить свое первоначальное утверждение привести его к виду
На любом СУЩЕСТВУЮЩЕМ языке, первый алгоритм выдаст те же результаты по времени.
Так понятнее ? :))
№ 601 07-08-2006 02:34 | |
Очень неприятно нарушать торжественное обещание не флеймить больше на тему чисел Фибоначчи, но я тут поэкспериментировал с memoization, и результат удивил даже меня:
(defun fib (n)
(cond ((< n 3) 1)
(t (+ (fib (1- n)) (fib (- n 2))))))
(defun memoize (f)
(let ((ht (make-hash-table)) (old-f (symbol-function f)))
(setf (symbol-function f)
#'(lambda (x)
(multiple-value-bind (v found) (gethash x ht)
(if found
v
(setf (gethash x ht) (funcall old-f x))))))))
Особо отмечу, что это не обобщенное решение, а лишь модельный пример со множеством ограничений.
Пояснение для тех, кто не знает Лиспа. Вызов вида
(memoize 'f)
подменяет определение функции f: для нее создается анонимная функция-"обертка", которая при каждом вызове исходной функции с новым значением аргумента запоминает пару (аргумент, значение) в хэш-таблице. Соответственно, при повторном вызове функции ее значение не вычисляется, а берется из хэша.
Такое "кэширование", с одной стороны, может существенно ускорить выполнение программ, а с другой --- весьма опасно неожиданными побочными эффектами (или их отсутствием в случае повторных вызовов).
Результаты --- см. ниже. Все замеры выполнялись на том же clisp 2.33 в режиме интерпретации. Следует оговорить особо, что в случае с другими реализациями Common Lisp фокус может не получиться, поскольку компиляция может иметь в данном случае далеко идущие последствия:
http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc.htm
Within a function named F, the compiler may (but is not required to) assume that an apparent recursive call to a function named F refers to the same definition of F, unless that function has been declared notinline. The consequences of redefining such a recursively defined function F while it is executing are undefined.
Из этого следует, что notinline может решить проблему, но я не проверял, как это реализовано в различных системах.
Итак:
[2]> (time (fib 20))
Real time: 0.015625 sec.
Run time: 0.015625 sec.
Space: 0 Bytes
6765
[3]> (memoize 'fib)
#<CLOSURE :LAMBDA (X)
(MULTIPLE-VALUE-BIND (V FOUND) (GETHASH X HT)
(IF FOUND V (SETF (GETHASH X HT) (FUNCALL OLD-F X))))>
[4]> (time (fib 20))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 1696 Bytes
6765
[5]> (time (fib 200))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 14388 Bytes
280571172992510140037611932413038677189525
[6]> (time (fib 1000))
Real time: 0.015625 sec.
Run time: 0.015625 sec.
Space: 101044 Bytes
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875
ИМХО, ускорение вполне приличное (поедание памяти --- тоже :-). Аналогичный механизм может быть реализован "прозрачно", внутри исполняющей подсистемы любого "чистого" ФЯ. Естественно, в этом случае он может быть сделан сколь угодно интеллектуальным. Например, может быть организовано вытеснение редко используемых значений по принципу, аналогичному аппаратной кэш-памяти, либо же выбор кэшируемых значений динамически, по результатам измерения времени исполнения функций.
Ответ на »сообщение 586« (Jack Of Shadows)
___________________________
Что касается мемоизации, то это уже изменение алгоритма,
Если memoization сделана в коде самой программы --- то это другой алгоритм, но если она реализована внутри исполняющей подсистемы, то это становится такой же деталью реализации, как и оптимизация хвостовой рекурсии, и уж тем более автоматическое распараллеливание.
и ее точно также можно сделать в лиспе как и в хаскеле, и добиться абсолютно тех же результатов.
Можно. Но при наличии в языке императивной составляющей, корректная реализация memoization в коде программы становится потенциальным хождением по граблям.
Опровергайте. Об этом я вас уже в третий раз наверное прошу :))
Идентичную запись на хаскеле того алгоритма который вы гоняли на лиспе, я привел.
Компилируйте, прогоняйте и результаты в студию.
Ох, Jack, в своем стремлении меня уесть Вы сами роете себе яму. Во-первых, если Вы внимательно прочтете мое утверждение, то в нем нет ни слова о том, что реализация Haskell с memoization уже существует:
>>> Реализация функционального языка (того же Haskell), в которой не пожалеют памяти на memoization, вероятно, сможет опровергнуть это утверждение.
Здесь утверждается лишь то, что такая реализация в принципе возможна и указано, что именно нужно сделать. Ее вероятные временнЫе характеристики могут быть примерно оценены из приведенных выше замеров производительности. Они не достигают уровня производительности fib-tail, но они существенно лучше "наивного" вычисления fib (что и требовалось для опровержения Вашего тезиса). Что же касается того, существует она, или нет, то так уж случилось, что в математике не все доказательства существования конструктивны --- для того, чтобы убедиться в существовании иррациональных чисел "диагональным методом" Кантора вовсе не обязательно строить такое число до конца :-)
Во-вторых, раз уж мы углубились в дебри интересной науки под названием computer science, то давайте поступим в рамках общепринятых научных норм (обоснование утверждения ложится на его автора) и начнем с самого начала, с Вашего утверждения:
На любом языке, первый алгоритм выдаст те же результаты по времени.
Раз уж Вы предлагаете утверждение, претендующее на общезначимость ("любой язык"), то сначала докажите его. Формально, в общем виде, подобно тому, как в общем виде доказывается нижний предел N * log(N) сложности сортировки сравнением ключей. Успехов в этом нелегком деле.
№ 600 07-08-2006 00:08 | |
Ответ на »сообщение 599« (Geniepro)
___________________________
А ведь P4 2800 должен быть примерно в два раза быстрее, чем Celeron 1700 !
В том то и дело, что не должен. Во первых, при повышении частоты производительность растет нелинейно (к тому же 2800/1700 совсем не 2). А, во-вторых, у этих процессоров, скорее всего, еще и разная длина конвейера. Так что сравнивать на них скорость выполнения программ - совсем некорректно.
№ 599 06-08-2006 09:51 | |
Ответ на »сообщение 598« (Geniepro)
___________________________
Хм, интересно... Повторил тесты Lisp Hobbyist'а:
(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)
Напомню, у него CLisp 2.33 и P4 2800, у меня CLisp 2.39 и Celeron 1700 - время выполнения почти совпало! разница - меньше 0.1 сек (в режиме интерпретации при запуске из оболочки)
А ведь P4 2800 должен быть примерно в два раза быстрее, чем Celeron 1700 !
CLisp 2.39 похоже сильно ускорен... Советую переходить на него... ;-)
Он выполняет программы в псевдокоде всего раз в 6 медленнее, чем чистый машинный код на Компонентном Паскале. А интерпретация исходного кода ещё в пять раз медленнее...
Да, я там раньше упоминал, что на Компонентном Паскале рекурсивный вариант ф-ции Фибоначчи при n=32 выполняется 1.36 сек. Оказывается, я тогда некоректный замер делал - определял ещё и сколько раз вызывается сама ф-ция. Эта лишняя операция сложения замедлила работу в 6 раз... На самом деле - 0.235 сек.
Кстати, C# выполняет эту ф-цию примерно в 2.5 раза быстрее, чем Компонентный Паскаль, и раз в 15 быстрее, чем CLisp 2.39 (псевдокод). Но это у меня так, на другом железе может быть и по другому...
№ 598 06-08-2006 06:12 | |
Кстати, о переполнении стека в Дельфах. Я был сильно удивлён, когда
обнаружил, что рекурсивный QuickSort сдыхает на массиве со всего-то 20
тыс элементами, упорядоченными в обратном направлении...
Хотя там раньше где-то подсказывалось, как увеличить размер стека...
_____________
Эх, пытаюсь как-нить достать F# от Майкрософта, да что-то их сервак
глючит, не даёт мне ссылку на инсталлятор...
Люди добрые, помогите, если нетрудно, киньте рабочую ссылку, хочется
интегрировать ML в Студию...
Основная страница загрузки -
http://research.microsoft.com/fsharp/release.aspx
Но дальше окна с лицензией я пройти не могу - пишется про какую-то
ошибку сервера...
http://research.microsoft.com/research/downloads/download.aspx?FUID={70EB059F-DC3D-47E1-B8CA-9CED69F33C66}
№ 597 06-08-2006 00:28 | |
Ответ на »сообщение 595« (Сварог)
___________________________
И пусть мне кто-то станет рассказывать, что рекурсия неудобно реализуется в Делфи
Рекурсия быстренько сдыхает в дельфи с переполнением стека. Пример я уже здесь приводил.
Что касается приведенных вами алгоритмов, то второй вариант таки труднее для понимания.
По крайней мере для меня. :))
№ 596 06-08-2006 00:24 | |
Ответ на »сообщение 593« (Geniepro)
___________________________
Вряд ли стандартный Apache будет выполнять код на Лиспе или Окамле?
Ну стандартный Апач и PHP не выполняет. :)) Для этого используется плагин mod_php
Соответственно в случае с лиспом mod_lisp
Ну или можно воспользоваться одним из opensource лисп web серверов. AllegroServe, Araneida, LightHttpD
№ 595 05-08-2006 23:15 | |
Ответ на »сообщение 594« (Сварог)
___________________________
function fib1(n :integer) :integer;
begin
if (n<3) then
begin
Result := 1;
end
else
Result := fib1(n-1) + fib1(n-2);
end;
и
function fib2(n :integer) :integer;
var
i, k1, k2, k :integer;
begin
k1 := 1;
k2 := 1;
k := 1;
for i := 2 to n-1 do
begin
k := k2+k1;
k1 := k2;
k2 := k;
end;
Result := k;
end;
И пусть мне кто-то станет рассказывать, что рекурсия неудобно реализуется в Делфи или что второй вариант реализации функции труднее для понимания, чем первый :)))))))))))))))))
№ 594 05-08-2006 22:23 | |
Ответ на »сообщение 593« (Geniepro)
___________________________
А как выполняются веб-программы с использованием этих библиотек на ФЯ?
Ведь для них, наверное, нужны какие-то специализированные веб-серверы?
Вряд ли стандартный Apache будет выполнять код на Лиспе или Окамле?
А уж от веб-браузеров и подавно не дождётесь... :-)
Гм... я почему-то всегда думал, что библиотеки выполняет ОС компьютера, а не Apache или веб-браузер...
№ 593 05-08-2006 17:55 | |
Ответ на »сообщение 592« (Jack Of Shadows)
___________________________
Второй пример: императивный, трудный для чтения, записи и понимания. В миллионы раз более быстрый при исполнении.
Да, совершенно верно. Хотелось бы ещё добавить, что в таких алгоритмах легко совершить ошибку.
Ряд чисел Фибонначи выглядит ведь так:
1, 1, 2, 3, 5, 8, 13, ...
для значений n (соответственно):
1, 2, 3, 4, 5, 6, 7, ...
Ваша же функция (итеративная) даёт ряд:
1, 2, 3, 5, 8, 13, 21, ...
для тех же n.
Не хотелось бы показаться невежливым, но, по-моему, Ваша функция должна выглядеть так:
(defun fib (n)
(declare (integer n))
(loop repeat n
for f of-type integer = 0 then (+ f0 f1)
for f0 of-type integer = 0 then f1
for f1 of-type integer = 1 then f
finally (return f)))
PS. Кстати, а зачем Вы поставили (1+ n) вместо n? ;-)
_____________________
Кстати это же пример показывает несостоятельность утверждения "человек легче мыслить в циклах а не в рекурсиях".
Всего лишь три вложенных цикла, и итеративная версия алгоритма превращается в такую головоломку, что любая рекурсия по сравнению с ней - детская задачка.
Ну, не всегда... Вот вспомните опять тот алгоритм Queens, приведённый Trurl'ем - он ведь выполнен в чисто рекурсивном стиле - и понять его не так то просто. А попытка повторить его на Паскале или Си, имхо, обречена на провал...
Хотя, впрочем, итеративный вариант этого же алгоритма ничуть не проще для восприятия...
А ведь это очень простая задачка...
_____________________
Так что те кому требуется делать web приложения - советую обратить пристальное внимание на web библиотеки лиспа, окамла, питона и руби.
Это шанс не просто поигратсья, а на деле работать с ФЯ.
А как выполняются веб-программы с использованием этих библиотек на ФЯ?
Ведь для них, наверное, нужны какие-то специализированные веб-серверы?
Вряд ли стандартный Apache будет выполнять код на Лиспе или Окамле?
А уж от веб-браузеров и подавно не дождётесь... :-)
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|