| Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение 
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
| № 3302 06-10-2007 18:24 |   |
Ответ на »сообщение 3298« (Руслан Богатырев)
___________________________
А как же бэктрекинг? Присваиваем (унифицируем), откатываемся, опять присваиваем и т.д.
Ого, вот уже унификацию присваиванием обозвали :))
Ну раз уж пошла такая пьянка, так почему бы и передачу параметров функциям присваиванием не обозвать ? Вызвали функцию в цикле сто раз ? 100 раз присвоили ее параметрам разные значения. Чем не императивное программирование ? :)))
Руслан, pattern matching в хаскеле это ведь тоже унификация. Там наверное тоже многокоратное присваивание ?
Более того, pattern matching в хаскеле ПОСЛЕДОВТАТЕЛЕН!!! То есть исполнение зависит от последовательности записи!
Руслан, backtracking это просто обход дерева функцией. То есть передача одной и той же функции разных параметров по определенному алгоритму (откат) до тех пор пока не найден искомый результат. Где вы там умудрились найти многократную запись В ОДНУ И ТУ ЖЕ ячейку памяти ?
| № 3301 06-10-2007 18:20 | |
В плане дополнительной информации о распараллеливании императива (последовательных программ).
В области теории параллельного программирования классические результаты принадлежат В.Е.Котову и А.С.Нариньяни: они предложили одну из первых моделей параллельных программ - недетерминированные асинхронные автоматы, и для этой модели получили ряд важных результатов, связанных с условиями отсутствия конфликтов параллелизма, с преобразованием последовательных программ в параллельные и преобразованиями, увеличивающими внутренний параллелизм. Работы в этой области продолжали В.В.Вальковский, И.Б.Вирбицкайте и ее ученики.
Источник: http://www.iis.nsk.su/pottosin/40/win/book06.html
| № 3300 06-10-2007 18:10 | |
Ответ на »сообщение 3297« (Jack Of Shadows)
___________________________
Ответ на »сообщение 3295« (Илья Ермаков)
___________________________
Если вы возьмете свой алгоритм и скомпилируете его на разных платформах и разными компиляторами, означает ли это что сам ЗАПИСАННЫЙ выми алгоритм поменялся ?
Не важно, во что в итоге программа компилируется. Если на уровне виртуальной машины языка решение задачи описывается как последовательность элементарных шагов, то алгоритм есть. Если нет - то алгоритма нет. А есть другой формализм... Нельзя сказать, что это единственно верная точка зрения, но такая точка зрения на использование понятия "алгоритм" в теор. информатике тоже есть.
| № 3299 06-10-2007 18:06 | |
Ответ на »сообщение 3289« (Jack Of Shadows)
___________________________
Ответ на »сообщение 3286« (Руслан Богатырев)
___________________________
Нужно нужно, поищите. Может в конце концов убедитесь что распараллеливать цикл можно только тот в котором НЕТ многократного присваивания, то есть императивного программирования.
Предположим, что каждый оператор блока кода может выполняться параллельно. Т.е. истрактуем императив как декларатив - как описание целого класса алгоритмов. Однако нужно ещё и соблюсти требование эквивалентности. Пусть компилятор анализирует причинно-следственные связи по использованию переменных и накладывает ограничения на класс алгоритмов, описываемых программой. Далее в пределах наложенных ограничений операторы запускаются асинхронно. Совершенно реалистичный механизм.
Да, в некоторых случаях лишние присваивания станут причиной чрезмерных ограничений, и код не выполнится так эффективно, как мог бы. Не распараллелится в одном - распараллелится в другом, при распределению выполнения по большой "площади" это компенсируется. А если выполнение сконцентрировано в конкретных местах, то можно будет всегда переписать эти места так, чтобы они не были узкими...
| № 3298 06-10-2007 18:06 | |
Ответ на »сообщение 3289« (Jack Of Shadows)
___________________________
Может в конце концов убедитесь что распараллеливать цикл можно только тот в котором НЕТ многократного присваивания, то есть императивного программирования.
Многократное присваивание и есть отличительный признак ИЯ? Язык Пролог вроде как декларативный. А как же бэктрекинг? Присваиваем (унифицируем), откатываемся, опять присваиваем и т.д.
Выдержка ( http://www.intuit.ru/department/pl/plprolog/6/):
Суть этого механизма такова: в том месте программы, где возможен выбор нескольких вариантов, Пролог сохраняет в специальный стек точку возврата для последующего возвращения в эту позицию. Точка возврата содержит информацию, необходимую для возобновления процедуры при откате. Выбирается один из возможных вариантов, после чего продолжается выполнение программы. Во всех точках программы, где существуют альтернативы, в стек заносятся указатели. Если впоследствии окажется, что выбранный вариант не приводит к успеху, то осуществляется откат к последней из имеющихся в стеке точек программы, где был выбран один из альтернативных вариантов. Выбирается очередной вариант, программа продолжает свою работу. Если все варианты в точке уже были использованы, то регистрируется неудачное завершение и осуществляется переход на предыдущую точку возврата, если такая есть. При откате все связанные переменные, которые были означены после этой точки, опять освобождаются.
Кстати, в декларативном Прологе есть оператор отсечения (явный намек на императив) и важен порядок (последовательность) клозов (просмотр клозов идет сверху вниз).
| № 3297 06-10-2007 18:02 | |
Ответ на »сообщение 3295« (Илья Ермаков)
___________________________
Одна программа на ФП эквивалентна целому классу алгоритмов, в зависимости от того, какой порядок выберет рантайм. Это я и имел в виду - поравьте, ежли в чём не прав :-)
И на ИЯ тоже, в зависимости от того какие флажки оптимизации включены при компиляции и какой вообще компилятор (пусть и одного и того же формального языка) выбран. Вас же различия алгоритма на ТАКОМ низком уровне, не волнуют, правильно ? Вы же не считаете что ФОРМАЛЬНЫЙ алгоритм, то есть не привязанный к конкретному железу и конкретным оптимизациям конкретного компилятора, вот этот вот алгоритм записанный вами, изменился.
Если вы возьмете свой алгоритм и скомпилируете его на разных платформах и разными компиляторами, означает ли это что сам ЗАПИСАННЫЙ выми алгоритм поменялся ?
| № 3296 06-10-2007 17:57 | |
Ответ на »сообщение 3287« (Jack Of Shadows)
___________________________
Ответ на »сообщение 3286« (Руслан Богатырев)
___________________________
Видно что перед тем как записать новое выражение в X, старое выражение должно быть с него считано. Распараллелить эту операцию невозможно в принципе.
Автоматы Гуревича отлично формализуют отношения между "старым" и "новым" в процессе выполнения императивной программы.
| № 3295 06-10-2007 17:53 | |
Ответ на »сообщение 3282« (Jack Of Shadows)
___________________________
Ответ на »сообщение 3276« (Илья Ермаков)
___________________________
Ну это в корне неверно. Декларативно записанный алгоритм не становится МЕНЕЕ от этого точным.
Я за то, чтобы понимать алгоритм в изначальном смысле, формализованном Тьюрингом/Постом - как заданная последовательность элементарных шагов исполнителя для достижения результата. А декларатив - это уже не алгоритм, а некий эквивалентный по мощности формализм из области теории вычислимости, с другим названием.
В ФП - рекурсивные функции. В марковском - правила подстановок. В логическом - предикаты.
Решение одной и той же задачи происходит либо в виде выполнения алгоритма, либо в виде вычисления функции, либо в виде унификации...
Но отображение-то между ними получается не биективное. Одна программа на ФП эквивалентна целому классу алгоритмов, в зависимости от того, какой порядок выберет рантайм. Это я и имел в виду - поравьте, ежли в чём не прав :-)
| № 3294 06-10-2007 17:52 | |
Ответ на »сообщение 3291« (Руслан Богатырев)
___________________________
Руслан, ну прекратите вы в конце концов кидать ссылки даже не читая что там написано :)))
Такому одновременному выполнению могут мешать конфликты между итерациями, связанные с использованием одной и той же переменной во всех итерациях. Например, в цикле...
Понятно, нет ? Там написано ТО ЖЕ САМОЕ что я вам уже сто раз наверное говорил. Если в цикле есть МНОГОКРАТНОЕ ПРИСВАИВАНИЕ, то такой цикл НЕВОЗМОЖНО распараллелить. :)))
А как обеспечить выполнение этого условия ? Либо запретить вообще присваивания, и поучить таким образом чистый функциональный язык. Либо надеяться на честное пионэрское слово программиста, то есть получить катастрофические вылетания программы.
Нет и не будет вам автоматического распараллеливания императивного кода Руслан.
Не знаю сколько вам надо работ просмотреть, прежде чем до вас дойдет, что везде необходимым предусловием такого вот распараллеливание является отсутствие многократного присваивания.
| № 3293 06-10-2007 17:47 | |
Ответ на »сообщение 3277« (Jack Of Shadows)
___________________________
Я тоже не понимаю гигантсике "прыжки мысли" Руслана от императива/функционала к синхоронному/асинхронному выполнению.
А "выполнению" Вы сами дописали.
Как я понял, речь не об этом. А о синхронной и асинхронной структуре программы.
Для декларативного программирования существуют всего два существенных момента времени - начало и окончание работы программы. И можно описать как связаны эти два состояния.
Императивное программирование необходимо, когда существует множество моментов времени связанных с работой программы. Не важно является это время реальным или условным.
Добавить свое сообщение
Отслеживать это обсуждение
| Дополнительная навигация: |
| 
