Ответ на »сообщение 578« (Jack Of Shadows)
___________________________
>>>без проблем которые приносит ООП со своим наследованием.

Что вообще отказываются от отношения частное-общее?

Ответ на »сообщение 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.

"Вот что истинно хвостовая рекурсия-то делает..."

Ответ на »сообщение 573« (Geniepro)
___________________________

Lisp Hobbyist, а на каком железе Вы это вычисляли?

P4/2.8GHz

Ещё про числа Фибонначи.

fib n = fibs!!n
  where fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

>fib 1000
7033036771142281582183525487718354977018126983635873
2742604905087154537118196933579742249494562611733487
7504492417659910881863632654502236471060120533741212
73867339111198139373125598767690091902245245323403501 

Время вычисления даже на Hugs - доли секунды.

Ответ на »сообщение 577« (Geniepro)
___________________________
Отнюдь. Дело не в этом.
В конце концов и в хаскеле нужно работать с состоянием и хранить его в переменных.
ООП это не просто "данные + методы". ООП это метод достижения некоторых целей, а именно инкапсуляции и  полиморфизма. Не единственно возможный метод.
Существуют и другие механизмы которые позволяют достичь тех же результатов.
Посмотрите например type classes и modules в хаскеле.
Совместно они дают вам все что только может дать вам ООП. При этом в гораздо более понятном, простом виде, и без проблем которые приносит ООП со своим наследованием.

То есть функциональное Программирование дает вам ту же инкапсуляцию и тот же полиморфизм что и ООП.
Поэтому обьекты там лигние просто. Их нет смысла испольовать. Они ничего не приносят, только все осложняют.
В принципе это можно разобрать на примерах, просто у меня щас времени нет. Можно попросить кого нибудь из знающих хаскель разобрать эту тему.

Ответ на »сообщение 561« (Jack Of Shadows)
___________________________

О том что ООП и ФЯ мягко говоря несовместимы, и что если вы приняли на веру ООП, то это сильно ограничивает ваши возможности как программиста.

Насколько я понимаю, эта несовместимость происходит от того, что ФЯ в чистом виде не позоляют делать вычислений с побочными результатами, а в ООП все функции(методы) именно побочными эффектами и занимаются (меняют состояние обьекта-хозяина)...

Ответ на »сообщение 575« (Jack Of Shadows)
___________________________

Ответ на »сообщение 574« (Geniepro)

Это вы нам должны сказать что вы об этом думаете :))
Я могу говорить только о том чем пользуюсь сам.


Дык я пока ничего об этом не могу думать - потому и спросил, может кто уже пробовал, поделится впечатлениями...

Кстати, я тут нашёл некий Helium - http://www.cs.uu.nl/helium/distr/SetupHelium1.6.exe

Позиционируется для обучения Хаскеллю.
Весит немного, всего полтора метра, так что попробую, посмотрю, что это такое...

Ответ на »сообщение 574« (Geniepro)
___________________________
Что об энтом думаете?

Это вы нам должны сказать что вы об этом думаете :))
Я могу говорить только о том чем пользуюсь сам.

Кстати, я тут наткнулся на бесплатную систему Poplog - ftp://ftp.cs.bham.ac.uk/pub/dist/poplog/freepoplog.html
Включает в себя POP11, Common Lisp, Prolog и Standart ML.
Версия для Windows весит 13 метров - ftp://ftp.cs.bham.ac.uk/pub/dist/poplog/winpop/pop15-53.zip

Что об энтом думаете?

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 сек.
У Вас всего в пять раз медленнее. Для интерпретатора очень неплохо...