Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 1912 21-02-2007 11:01 | |
Ответ на »сообщение 1911« (Geniepro)
___________________________
Ну, вообще-то оптимизации включать надо. По умолчанию они не включаются...
Так что были там и отложенные вычисления, и хранение списка...
Поставил -O2. Та же фигня. Компилятор скачивал вчера. Может там еще чего-то покрутить надо?
№ 1911 21-02-2007 10:41 | |
Ответ на »сообщение 1910« (pepper)
___________________________
Похоже на полный бред. Или ты путаешь калькуляторы с АЦП/ЦАП.
За что купил, за то и продаю... :о))
К сожалению, не могу найти ту книгу и не помню автора, но точно помню, что там так объяснялось, почему у обычных калькулаторов 8-9 разрядов, а у лучших (и дорогущих) - 12...
Объяснялось это вроде довольно убедительно - в детстве, когда я читал эту книгу, она меня убедила. Сейчас сомневаюсь... :о))
Книга была старая, а может быть автор её был в неадеквате, когда описывал эту теорию...
Я не поленился и набросал такой простенький тестик:
...
Программа съела больше гига памяти и ушла в своп. Компилировал GHC. Почему даже на таком простом примере компилятор не смог ничего соптимизировать (выкинуть конструирование очень большого списка)?
Ну, вообще-то оптимизации включать надо. По умолчанию они не включаются...
Так что были там и отложенные вычисления, и хранение списка...
Я обычно компилирую программы простеньким bat-файлом, в котором указана опция -O2 (или можно просто -O - качество кода, по утверждению создателей GHC, будет почти таким же).
Так что этот код отработал у меня, потратив всего 2.5 мегабайта памяти и никаких свопингов...
№ 1910 21-02-2007 09:06 | |
Ответ на »сообщение 1881« (Geniepro)
___________________________
Оптимизирующие компиляторы, проведя анализ строгости (strictness analysis), могут вообще не создавать код с отложенными вычислениями (если задача это позволяет). Именно эта оптимизация и позволяет в подобных случаях программам на ленивых функциональных языках держаться на примерно одинаковом уровне по быстродействию с обычными императивными программами с энергичными вычислениями, а в некоторых случаях (когда задача хорошо подходит под отложенные вычисления) - и превосходить...
Я не поленился и набросал такой простенький тестик:
test_list = 0 : test_list
index xs 0 = head xs
index xs n = index (tail xs) (n - 1)
main = do
print (index test_list 1000000000)
Программа съела больше гига памяти и ушла в своп. Компилировал GHC. Почему даже на таком простом примере компилятор не смог ничего соптимизировать (выкинуть конструирование очень большого списка)?
№ 1909 21-02-2007 09:02 | |
Ответ на »сообщение 1892« (Geniepro)
___________________________
Мне как-то в одной довольно старой книге попалось утверждение о том, что больше 12-13 разрядов калькуляторы не могут считать по причине тепловых шумов в электронных схемах (или что-то типа того, короче, какой-то термодинамический предел...).
Похоже на полный бред. Или ты путаешь калькуляторы с АЦП/ЦАП.
№ 1908 21-02-2007 07:38 | |
Ответ на »сообщение 1907« (Денис Зайцев)
___________________________
Долго набивал :) Geniepro меня опередил.
№ 1907 21-02-2007 07:33 | |
Ответ на »сообщение 1901« (Geniepro)
___________________________
Функцию Вашего знакомого обдумать надо - почему у неё после n=37 происходит такая катастрофическая потеря точности. Но в любом случае, даже если реализовать плавающую арифметику с, например, миллионом цифр в мантиссе, быстрее простого целочисленного варианта точно не будет, и при этом опять же точные результаты будут даваться только до определённого значения n, а после него опять произойдёт резкий рост погрешности...
Может быть аналитически эта функция и верна, но непрактична однозначно...
Совершенно верно, эта функция непрактична. Потому что чрезвычайно чувствительна к ошибкам округления. Можно показать, что последовательность a(n) экспоненциально сходится к числу "золотого сечения" ~0.6180339... (это число является корнем уравнения x^2+x-1 = 0). А затем мы вычисляем a(n)^2+a(n)-1, в результате получается вычитание двух очень близких друг к другу (и к единице) чисел, что и ведёт к потере значащих цифр (катастрофической для больших n). Реально вычисленная последовательность a(n) начиная с некоторого номера N стабилизируется (при любом n>N a(n) = наиболее близкое к числу "золотого сечения", представимое в процессоре или языке). Поэтому неудивительно, что стабилизируется и f(n).
Вот здесь можно почитать обсуждение вопроса о том, как быстрее всего считать n-й член последовательности Фибоначчи:
http://algolist.manual.ru/maths/count_fast/fibonacci.php
№ 1906 21-02-2007 07:00 | |
Ответ на »сообщение 1905« (Geniepro)
___________________________
Основан на свойстве чисел Фибоначчи - соседние числа дают отношение, равное золотому сечению
Пардон. Не равное, а приближающееся к золотому сечению отношение...
№ 1905 21-02-2007 06:56 | |
Ответ на »сообщение 1900« (Jean)
___________________________
Подсказал один знакомый математик :))). Кстати, к формуле он приложил ее строгий аналитический вывод на 2 листах :).
Мда... Любопытный алгоритм. В принципе, похоже (интуитивно) - правильный.
Основан на свойстве чисел Фибоначчи - соседние числа дают отношение, равное золотому сечению - ((sqrt 5 + 1) / 2) = 1.61803398874989...
Чем больше номера чисел в ряду Фибоначчи, тем ближе это отношение к золотому сечению. И тем больше влияние погрешности плавающей арифметики в компьютере. Так что после определённого n эта разница становится такой маленькой, что не отличается от машинного эпсилона - вот и происходит сбой, функция выдаёт одно и тоже значение при любых n, больших критического...
Аналитически формула верна, но практически неприемлема...
№ 1904 21-02-2007 01:33 | |
Ответ на »сообщение 1898« (Jack Of Shadows)
___________________________
А вот как прогнать список функций над одним значеним ?
Казалось бы надо писать новый map который будет принимать 1 значение и список функций, который она будет вызывать с этим значением.
На самом деле все невероятно просто и красиво. Пример:
map ($ 3) [(+5), (*4), (^2)]
Output: [8,12,9]
Это не только красиво, это ещё и ближе к математической нотации, а значит - более правильно. Вместо 3 ставим объект, характеризующий положение в партии в шахматах, а список - список возможных сценариев стратегий дальнейшей игры... Всё наглядно. Сообщение не подписано
№ 1903 21-02-2007 00:52 | |
Ответ на »сообщение 1898« (Jack Of Shadows)
___________________________
А вот как прогнать список функций над одним значеним ?
Казалось бы надо писать новый map который будет принимать 1 значение и список функций, который она будет вызывать с этим значением.
На самом деле все невероятно просто и красиво. Пример:
map ($ 3) [(+5), (*4), (^2)]
Output: [8,12,9]
Забавно.
Но на самом деле тут всё же стандартное действие функции map - применение функции ($ 3) к списку (содержащем функции в данном случае) [(+5), (*4), (^2)].
Вот что значит функции - объекты первого класса... ;о)
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|