Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Базарная площадь
  
О разделе

Основная страница

Группы обсуждений


Тематический каталог обсуждений

Архив

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  23:28[Войти] | [Зарегистрироваться]
Обсуждение темы:
Функциональное программирование

Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.

Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.

Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.

 Jack Of Shadows

Количество сообщений на странице

Порядок сортировки сообщений
Новое сообщение вверху списка (сетевая хронология)
Первое сообщение вверху списка (обычная хронология)

Перейти на конкретную страницу по номеру


Всего в теме 5502 сообщения

Добавить свое сообщение

Отслеживать это обсуждение


Смотрите также обсуждения:
Средства разработки. Языки программирования.
  • Delphi 4 or Delphi 5
  • Что приобрести в качестве средства разработки?
  • Delphi6
  • Delphi vs PowerBuilder
  • Сравнение компиляторов
  • Вот и вышла Delphi 7... Вы рады?

  • <<<... | 582—573 | 572—563 | 562—553 | ...>>>
    Всего сообщений в теме: 5502; страниц: 551; текущая страница: 494


    № 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) и компоненты которые позволяют "автоматически" передавать функции (в данном случае ивенты) привело к тому что все программисты повально этими "ивентами" пользуются. А попробуй сам написать. Для спора на форуме - пожалуйста, для ежедневной работы - ну его нафиг.

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

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


    <<<... | 582—573 | 572—563 | 562—553 | ...>>>
    Всего сообщений в теме: 5502; страниц: 551; текущая страница: 494


    Добавить свое сообщение

    Отслеживать это обсуждение

    Дополнительная навигация:
    Количество сообщений на странице

    Порядок сортировки сообщений
    Новое сообщение вверху списка (сетевая хронология)
    Первое сообщение вверху списка (обычная хронология)

    Перейти на конкретную страницу по номеру
      
    Время на сайте: GMT минус 5 часов

    Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
    Функция может не работать в некоторых версиях броузеров.

    Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
    Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

     
    © При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

    Яндекс цитирования