Ответ на »сообщение 570« (Lisp Hobbyist)
___________________________
Кстати, а че это мы с вами переключились на обсуждение оптимизации ?
Это никакого отношения к теме не имеет.
Во первых я уже показал что это дело конкретной реализации компилятора, а не того функциональный ли язык или императивный.

Во вторых тот же Clisp например несмотря на то что гораздо медленнее Lispworks или ACL тем не менее более чем в 2 раза быстрее python и более чем 5-6 раз быстрее чем ruby.
При этом такая вот тормознутость не мешает python и ruby по праву завоевывать бешенную популярность, особенно в разработке web приложений.

Тот же Clisp например в связке с библиотекой UCW мечта просто для web разработки.
При этом гораздо быстрее python и ruby.

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

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


Как видите все в порядке с оптимизацией рекурсии в лиспе :))


Какая система используется? В clisp 2.33 компиляция ускоряет вычисления, но все равно, разрыв остается существенным. Еще было бы интересно увидеть результаты измерений для бОльших значений n, например, для чисел вида K * 100 (или для K * 1000, чтобы не мелочиться). Заранее благодарю.

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

Как видите все в порядке с оптимизацией рекурсии в лиспе :))

Ответ на »сообщение 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 (если не ошибаюсь): "Быстро написать программу на Лиспе просто. Куда сложнее написать на нем быструю программу."

Ответ на »сообщение 565« (Geniepro)
___________________________
WinHugs это интерпретатор.
Естественно никакой оптимизации.
Попробуйте GHC компилятор. Мне самому интересно, что вы там получите. :))

Ответ на »сообщение 565« (Geniepro)
___________________________
Все scheme имеют tail call optimization.
Многие лиспы тоже.
Так например оба коммерческих лиспа Lispworks и ACL имею tail call optimization.
По моему бесплатные Clisp и SBCL тоже.
Попробуйте
DrScheme.org или http://clisp.cons.org/

У меня практический вопрос к серьёзным ли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 - не знаю как её заставить работать...

Можете ещё раз посоветовать нормальные оптимизирующие компиляторы Лиспа и Хаскелля?

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

То же самое и с передачей функций как параметров. Ее НЕТ В ИЯ. Не потому что невозможно это делать физически, а потому что слишком неуклюже, слишком много лишнего кода писать приходится. Поэтому никто этим не пользуется.
В результате в коде ИЯ программистов передачи функций как параметров НЕТ. Хотя они вам легко приведут такой код в качестве доказательства, после чего удовлетворенные "победой" вернутся писать свой код и все также не будет применять этот механизм.

Jack, я Вам уже приводил обратный пример, но Вы уперлись так же, как и Ваши оппоненты и не замечаете очевидных вещей.

Что принесло наибольший успех Delphi 1, как средству разработки? Правильно, механизм событий. Ну так с какого перепугу установка обработчика события перестала являться передачей функции (процедуры) как параметра? И если программист при разработке своего ПО следует идеологии Delphi (а не C/C++/Turbo Pascal и пр.), то у него тоже появляется досточно много классов, имеющих события.
Например, в системе, которую мы (на работе) разрабатываем, многие вещи действительно хоторошо работают только потому, что используют механизм событий.

Делегаты в C# тоже никто не отменял.

Ответ на »сообщение 562« (Geniepro)
___________________________
По-моему, отличие только в том, что при передаче кода этот код описывается в месте его передачи, а при передаче процедуры этот код описывается чёрти где от места его передачи.

Да отличие ТОЛЬКО в этом. Да вот это ТОЛЬКО дорого стоит. Есть такое поняте enabler. Не знаю как по русски, но смысл таков. Свойство достаточно легкое чтобы применялось повсеместно. Соответственно просто иметь свойство недостаточно. Если оно будет неудобным для использования, его никто не будет применять. Будут делать похуже, но полечге для себя. То есть обходить это свойство стороной.

Здесь уже шел разговор о рекурсии. Так вот рекурсии в ИЯ НЕТ. Не потому что нет физически, а потому что этот механизм настолько неудобен в ИЯ, что им никто не пользуется. То есть рекурсии нет в коде программистов, пишуших на ИЯ.
Хотя в языке она поддерживается.

То же самое и с передачей функций как параметров. Ее НЕТ В ИЯ. Не потому что невозможно это делать физически, а потому что слишком неуклюже, слишком много лишнего кода писать приходится.
Поэтому никто этим не пользуется.
В результате в коде ИЯ программистов передачи функций как параметров НЕТ. Хотя они вам легко приведут такой код в качестве доказательства, после чего удовлетворенные "победой" вернутся писать свой код и все также не будет применять этот механизм.

При этом есть такие вот энейблеры (enablers) и у ИЯ программистов. Благодаря этим инструментам, которые делают передачу функций как параметров легкой, они начинают вовсю этим пользоваться и даже не представляют себе как это они могли без этого жить. Я об event-driven programming говорю :))
То что Борландд и MS создала внешнюю по отношению к языку тулзу (IDE) и компоненты которые позволяют "автоматически" передавать функции (в данном случае ивенты) привело к тому что все программисты повально этими "ивентами" пользуются. А попробуй сам написать. Для спора на форуме - пожалуйста, для ежедневной работы - ну его нафиг.

В случае с рекурсией я приводил пример того как один и тот же программист решая одну и ту же задачу, на ИЯ не будет пользоваться рекурсией, а на ФЯ - будет.
Так вот та же ситуация с передачей функций как параметров.
Тот же самый программист, та же самая задача.
В ИЯ никаких передач функций (кроме тех что для тебя делает среда, то есть ивенты)
В ФЯ - сплошь и рядом, СПЛОШЬ И РЯДОМ.

Эти вот "только" и "всего лишь" на самом деле дорого стоят, имеют принципиальное значение.
К сожалению, для того чтобы понять это, программисту нужно столкнуться с этим на практике, самому попробовать на зуб, так сказать. То есть поработать на ФЯ, решить практическую и нетривиальную задачу на ФЯ.
На это мало кто идет. Ограничиваются спорами на формуах о том чего не ели.
Вот мы с вами воду из пустого в порожнее и переливаем.