Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 642 11-08-2006 12:03 | |
Ответ на »сообщение 639« (Артем)
___________________________
Декларативный стиль плох тем, что при написании четких и ясных формул очень легко нарваться на комбинаторный взрыв.
Артем, то что Дельфи виснет с переполнением стека на рекурсиях - это проблема Дельфи а не рекурсии. :))
Ни лисп ни Хаскель на рекурсиях не виснут.
Мы приводили тут уже кучу примеров с огромным просто количеством итераций. Где и лисп и хаскель вполне неплохо отрабатывали, уходя с точки на которой виснет дельфи на мнооого вперед.
Во вторых вы опять упираетесь в производительность, не замечая, что мир программирования стремительно завоевывают такие жутко медленные языки как python, php, ruby, perl.
Разница в скорости достигает от 10 до 100 раз!.
А ведь компилируемые ФЯ (лисп, хаскель, ocaml) далеко не такеи медленные. В большинстве случаев они работают либо со скоростью си (то есть быстрее например чем си++ или java), либо всего в полтора раза медленнее.
Если скриптовым тихоходам отставание в скорости на порядки, не помешало найти свое место, привлечь миллионы программистов, решать огромный пласт прикладных задач, то почему вы думаете что совсем небольшое отставание в скорости ФЯ будет для них фатальным ?
А к тому, что все надежды на то, что растущая мощь компьютеров когда-нибудь полностью избавит программиста от обдумывания алгоритма (императивности) - беспочвенны.
Вы неправы. Растущая мошь компьютеров уже сейчас и сегодня избавила вас от обдумывания императивных алгоритмов для огромного просто количества задач.
Не для всех, но достаточно, чтобы в 8 из 10 случаев наивный функциональный алгоритм не представлял для конкретной задачи никаких проблем с производительностью.
И это на однопроцессорных системах. С заменой их на многоядерные (что происходит прямо сейчас) Вам вообще будет трудно найти хоть какой нибудь частный случай где разница в скорости была бы не в пользу ФЯ.
Наоборот, чем больше ядер будет в процессоре тем быстрее будет функциональный код по сравнению с "оптимизированным" императивным. Потому что ваш оптимизированный императивный код будет выполняться только на одном ядре. Для того чтобы распараллелить его на все остальные ядра, вам придется еще дальше его "оптимизировать", что приведет к такому взрывному росту сложности вашего кода, что ни в сказке сказать, ни вслух произнесть :))
Неоптимизированный функуциональный код при этом будет автоматически распараллеливаться.
Я использую лисп прямо сейчас на своей работе. Различные ФЯ используются сотнями тысяч программистов на практичке, для решения практических задач прямо сейчас. Время пришло.
Новый Perl 6 пишется на хаскеле, не на си, не на си++, не на ассемблере.
Я не говорю, что в ближайшей перспективе ФЯ заменят ИЯ. Нет. Просто они станут такой же частью программирования как и ИЯ. Если раньше у программистов в подавляющем большинстве случаев не было выбора.
То сейчас у вас и у меня такой выбор появился.
И это нам с вами решать какой язык выбирать для решения той или иной задачи.
Не зная ничего кроме своего любимого дельфи и производных от него (java, сишарп), программист не может вобщем то ничего выбирать.
Именно поэтому мы с вами говорим на сайте дельфи о ФЯ.
Мы хотим чтобы вы знали что задачи на ФЯ можно решать, прямо сегодня.
Что вы можете получить от этого конкретное преимущество, сделать свою работу легче, быстрее, с меньшим количеством ошибок, получать от своей работы большее удовольствие. Автоматизировать решение таких невероятно трудных технических проблем как распараллеливание ваших программ.
Заменить традиционные ИЯ ? Очень нескоро.
Стать необходимой частью современного программирования ?
Да, для ФЯ это время наступило.
Спасибо за это технологическому прогрессу, дешевым гигабайтам памяти, и массовому переходу на многоядерные процессоры.
№ 641 11-08-2006 11:04 | |
Ответ на »сообщение 640« (Денис Зайцев)
___________________________
Извините, что-то заклинило меня. Речь шла о числах Фибоначчи, а я - про факториалы. Но, насколько я помню, на тех тестах числа Фибоначчи с достаточно большим номером вычислялись, т.е. без арифметики большой разрядности дело тоже не обошлось.
№ 640 11-08-2006 10:55 | |
Ответ на »сообщение 632« (Jack Of Shadows)
___________________________
Ну что ж. Видимо я был неправ, когда посчитал что цифр слишком много.
Так что приведенные замеры на работе фиббоначи все таки оказались полезными.
Да нет, Вы таки, пожалуй, были правы, и вот почему. Давайте сравним 2 функции:
(defun fact (n)
(cond ((eq n 1) 1)
(t (* n (fact (1- n))))
)
)
и
(defun fact0 (n)
(cond ((eq n 1) 0)
(t (* n (fact0 (1- n))))
)
)
С точки зрения числа выполняемых действий они одинаковы. Давайте замерим их производительность. У меня LispWorks выдаёт:
(TIME (FACT 10000))
Timing the evaluation of (FACT 10000)
user time = 3.453
(TIME (FACT0 10000))
Timing the evaluation of (FACT 10000)
user time = 0.031
Отсюда вывод: замеряется производительность отнюдь не "собственно" LISP'а, а функции, умеющей перемножать большие числа.
Сама эта встроенная функция LISP'а (с поистине восхтительным по своей лаконичности именем "*") написана явно не на LISP'е, и даже не на ФЯ (готов поставить сто баксов против одного) и посему преимуществ ФЯ не имеет права демонстрировать.
То есть, это конечно, здорово, что такие замечательные возможности встроены в LISP.
Но вот если бы проверить решение системы линейных уравнений с матрицей, скажем, 500x500 методом Гаусса и обычной точностью, такой тест был бы более корректным.
№ 639 11-08-2006 10:48 | |
В языках, в которых размер числа не ограничен, работа с числами ведется как со строками. А в C++, Java, C# и т.д. используется процессорная арифметика. Соответственно, она гораздо более быстрая. В основной своей массе 32 разрядная арифметика пока еще удовлетворяет основную массу пользователей. А переход на 64-разрядную (в первую очередь для серверов) на десятилетия (а может и столетия) покроет все мыслимые практические потребности.
Работа со сверхбольшими числами нужна, например, при шифровании (вспомним тот же алгоритм RSA). Для работы с числами как со строками существуют, насколько я слышал, библиотеки. Если хотите, можете написать таковую сами (См. пример - http://articles.org.ru/cfaq/index.php?qid=1845&frommostrecent=yes )
Теперь насчет Фиббоначи. Прошу, конечно, прощения, что возвращаюсь к данной теме (давно я уже не ввязывался в это обсуждение). Пример вычисления чисел Фиббоначи как раз показал опасность слепого преклонения перед рекурсивностью. В Дельфи (мы же на сайте дельфистов, все-таки :) ) я могу написать рекурсивную функцию
function fib(n:Int64):Int64;
begin
if n=0 then Result:=1
else if n=1 then Result:=1
else Result:=fib(n-1)+fib(n-2);
end;
которая будет виснуть, а могу и итеративную
function fib1(n:Int64):Int64;
var i,n1,n2:Int64;
begin
if n=0 then Result:=1
else if n=1 then Result:=1
else begin
n2:=1;
n1:=1;
i:=2;
while i<=n do begin
Result:=n1+n2;
n2:=n1;
n1:=Result;
inc(i);
end
end;
end;
Которая будет мгновенно выдавать результат.
К чему это я? А к тому, что все надежды на то, что растущая мощь компьютеров когда-нибудь полностью избавит программиста от обдумывания алгоритма (императивности) - беспочвенны. Декларативный стиль плох тем, что при написании четких и ясных формул очень легко нарваться на комбинаторный взрыв. И развитие компьютеров тут не поможет, если количество внутренних вызовов при вычислении простейшей формулы превысит, например, число атомов в галактике. Да, конечно, тут говорили про автоматическую мемоизацию (пока только в экспериментальном Mercury), которая по сути является переходом к итеративности. Но, повторяю, никогда внутренний оптимизатор не сравнится с человеком. И если подсчет по такой простой формуле вызывает затруднения у современных реализация ФЯ (и Пролога тоже), то что говорить, о более сложных вещах?
№ 638 11-08-2006 08:37 | |
1) Случилось то, чего я боялся - обсуждение зациклилось на проблеме больших чисел. Это очень хорошо, что PHP и Algol68 могут решать эту проблему. Кто бы сомневался :). Но это мне не интересно. Мне интересно, как с этим справляются "лидеры промышленного программирования": С++, C#, Java. Могу ли я в этих языках так же просто возвести 2 в степень 10000 и увидеть на экране громадное натуральное число. Если да, то вопрос надо вообще закрывать - самые основные современные языки поддерживают арифметику "без ограничений" и обсуждать тут нечего. А вот если нет, то ставим плюсик напротив Лиспа, Хаскеля, PHP, Алгола68 и минусик напротив остальных. И начинаем обсуждать другие показатели языков, по которым можно судить об их сравнительных возможностях.
2) Вопрос в #627(2), наверно, слишком мудрено сформулировал. Повторю попроще. Основной структурой данных в ФЯ является список (в ЛИСПЕ, я так понял, вообще все вокруг списков вертится). Основной недостаток связанного списка с указателями - это доступ к произвольному элементу списка. Значит одно из двух - или в ФЯ списки дополняются какими-то специальными механизмами для индексированного доступа к произвольным элементам, или любая программа, где требуется быстрый доступ к произвольному элементу списка будет тормозить на обращении к произвольным элементам, особенно для списков большой длины. Какие комментарии по этому вопросу у специалистов ФЯ?
№ 637 11-08-2006 04:02 | |
Ответ на »сообщение 636« (Сергей Осколков)
___________________________
Извиняюсь, 2568 цифр - не для $i<1999, а $i<1001;
№ 636 11-08-2006 03:59 | |
Что касается вычислений с большими числами, в какой-то теме БП это обсуждали когда-то. Если не ошибаюсь, приводили пример Python, где просто пишутся арифметические действия и интерпретатор все делает, как нужно.
В PHP есть встроенная бибилиотека работы с большими числами. Код для вычисления факториала, вывода значения и его длины выглядит, например, так:
<?php
$n=1;
for ($i=1; $i<1999; $i++)
$n=bcmul($i, $n);
print $n."\n";
print"length=".strlen($n);
?>
Вывело после ~секунды вычислений число и его длину: 2568 (цифр).
№ 635 11-08-2006 03:15 | |
Ответ на »сообщение 633« (Jack Of Shadows)
___________________________
В-принципе я согласен что Лисп как язык имеет право на успех. В наше время дешевле купить более мощный компьютер, чем потратить умственные ресурсы на более эффективный с точки зрения компьютера кодинг.
С какой-то точки зрения действительно намечаются тенденции в сторону сдвига к функциональным языкам, которые как Вы говорите, так близки человеку. Тем более, что мы на сайте про Делфи.
Но, с другой стороны, это еще смотря какому человеку! Нужно заниматьсе тем, что лучше получается. Это во-первых. Во-вторых, сейчас намечается тенденция, когда все меньше и меньше людей умеют делать что-то на уровне "копания" и "заморачивания" в компьютерных интерфейсах. Из подавляющего числа программ, которые я встречал, лучше всего работают те, которые написаны на Visual C. А программы на Си шарп иногда пишут вообще дебилы (надеюсь, из тех кто это читает, таких нет). И дело даже не в том что программы на Си++ чуточку быстрее. Просто их пишут люди, которые лучше знают операционную систему и программные интерфейсы, и которые тщательней относятся к совместимости их программ с различными средами выполнения, технологиями и ситуациями. Уж не знаю почему, но вот так. Я имею в виду не детские поделки, а реально работающие программы.
Вы путаете задачи реального времени (перехват ракеты) и исследовательские задачи (исследование космоса, сверхбольших расстояний итд.)
Там совершенно разные требования.
Вы перевернули все с ног на голову :) Задачи реального времени могут выполняться и на ФЯ при условии достаточно большой производительности компьютера. Ракеты как летали со скоростью порядка звуковой, так и летают. А процессоры растут. А исследовательские задачи (артефакт числа Пи, поиск Внеземных Цивилизаций и т.п.) очень часто требуют максимальной производительности, чтобы выиграть пару лет вычислений.
№ 634 10-08-2006 15:48 | |
Ответ на »сообщение 630« (SJ)
___________________________
А насчет цифр я с Вами не согласен. Если бы я, допустим, был бы противником всяких ФЯ и горячим сторонником работы исключительно только в С++, Java или С#, то признаюсь - один только пример с вычислением числа из 100 или более разрядов с помощью одних только встроенных средств языка программирования смог бы заставить меня более уважительно смотреть в сторону Haskell или Lisp. Тут "агитация" работает сразу, на уровне "подсознания" - а ну-ка назовите языки, на которых я могу "с ходу" посчитать факториал 100 и программа это дело "проглотит" и при этом никаких библиотек, кроме встроенных, мне не потребуется.
Недавно я расхваливал ФП одному знакомому, так тот попросил меня вычислить 2 ^ 1000000.
Без проблем, тут же вычислил в Хаскелле, вот только по аське отправить ему 300 тысяч цифр результата не получилось, а упаковывать и тд. было лень... Но он поверил на слово... :-))
Хоть бы в скобочках 2-3 таких языка привели. Только те, в которых вычисление 100-разрядного числа можно выполнить с помощью встроенных средств языка (без дополнительно написанных программных "костылей" - их, ясное дело, можно к любому языку "привинтить" :))
Ну например, древний старичёк Алгол-68. Я недавно приводил тут пример расчёта 1000-го числа Фибоначчи на нём...
Никаких спец. библиотек, просто указываете директиву precision=... и тип данных LONG LONG INT или LONG LONG REAL ...
Я, правда, не знаю, какое там максимальное количество значащих цифр, проверял только до 10 тысяч знаков...
В языке Ада можно указать гарантированную точность вычислений, но я не уверен, что там можно указывать сотни цифр...
Вообще-то это зависит от реализации, как и у Алгола-68, да и у других языков (Хаскель, например)...
№ 633 10-08-2006 12:28 | |
Ответ на »сообщение 631« (Мухтар)
___________________________
Между прочим, операции с большими числами, как правило характерезуются тем, что их нужно выполнять максимально быстро, поэтому все реальные проэкты, работающие с большими числами до сих пор пишут на Си и assembler
"Максимально быстро" понятие относительное. Максимально быстрый ассемблерный код на старом 286 в разы медленнее любого скомпилированного кода на языке высокого уровня (паскаль, хаскель, лисп) на новом процессоре.
Кроме того насколько я знаю, математики для работы с большими числами НИКОГДА не используют ассемблер.
Просто потому что они не программисты :))
Для математических расчетов используются такие языки как Фортран и Лисп (традиционно) и разнообразные языки семейства ML (SML, OCAML)
Да и кстати там особенно выжимать каждую микросекунду не требуется.
Вы путаете задачи реального времени (перехват ракеты) и исследовательские задачи (исследование космоса, сверхбольших расстояний итд.)
Там совершенно разные требования.
Ну а для прикладных задач сверх большие числа конечно же не нужны.
Внедрение их в язык повлекло бы за собой ненужное усложнение и слишком большой расход столь ценных 40-50 лет назад рессурсов. Так что большие числа пали жертвой в борьбе за экономичность.
Однако меня другое удивляет. Сегодня уже нет нужды каждый байтик считать. И тем не менее современные ИЯ спроектированы таким образом, что кажется для их разработки пригласили пенсионеров из эпохи PDP-11
Все также с любовью берегут каждый байтик, заставляя программиста пользоваться "примочками" каждый раз когда нужно сделать то что ой ой ой не дай бог отьест несколько байтов лишних.
Вам все еще хочется себя чувствовать рабом, обслуживающим Большую Мигающюю Машину ?
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|