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

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

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


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

Архив

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


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

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

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

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

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

 
   
С Л С

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

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

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

Квинтана

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

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

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

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

 
  
АРХИВЫ

 
 

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

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

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

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

 Jack Of Shadows

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

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

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


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

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

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


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

  • <<<... | 612—603 | 602—593 | 592—583 | ...>>>
    Всего сообщений в теме: 5502; страниц: 551; текущая страница: 491


    № 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
            forof-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 будет выполнять код на Лиспе или Окамле?
    А уж от веб-браузеров и подавно не дождётесь... :-)


    <<<... | 612—603 | 602—593 | 592—583 | ...>>>
    Всего сообщений в теме: 5502; страниц: 551; текущая страница: 491


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

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

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

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

    Перейти на конкретную страницу по номеру
      
    Время на сайте: 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» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

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