| Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение 
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
| № 892 21-08-2006 12:47 |   |
Ответ на »сообщение 886« (info21)
___________________________
>>>Смоделировать любую рекурсию со стеком -- элементарное дело для любого правильно обученного программиста.
По сути получается не смоделировать, раз речь идет о стеке, а реализовать рекурсию. Использование механизма рекурсии, встроенного в исплняющую систему, позволяет представить алгоритм гораздо проще, т.к. вся работа со стеком происходит автоматически. Насколько я понял именно это демонстрирует пример в № 891.
Имеет смысл использовать итерацию вместо рекурсии только если это позволяет отказаться от использования стека. Тогда возможен заметный выигрыш по скорости.
| № 891 21-08-2006 12:14 | |
Ответ на »сообщение 886« (info21)
___________________________
Смоделировать любую рекурсию со стеком -- элементарное дело для любого правильно обученного программиста.
Смоделировать то нетрудно.
function Ackerman(m,n:integer):integer;
var
s: array[1..1000000] of Integer;
t, c :integer
begin
t := 1;
s(t) := m;
while t > 0 do
begin
m := s(t);
Dec(t);
if m = 0 then
Inc(n)
else
begin
if n = 0 then
begin
Inc(t);
s(t) := m - 1;
n := 1;
end
else
begin
Inc(t);
s(t) = m - 1;
Inc(t);
s(t) := m;
Dec(n);
end
end
end;
Result:=n;
end;
Но как вы это потом читать и понимать будете ?
Данный код конечно правильно работать не будет, потому что integer быстренько переполнится, да и размер стека я там для простоты забил в 10000000.
Но идея я думаю проиллюстрирована понятно.
Итерация жутко нечитабельна.
| № 890 21-08-2006 09:25 | |
Хочу немного уточнить ситуацию с итерацией :)
Почему я так уверен, что любой алгоритм можно выразить в форме итерационного процесса (так же, впрочем, как и рекурсивного)?
Все очень просто.
1) ЛЮБОЙ алгоритм представим в форме машины Тьюринга - во всяком случае математики до сих пор не нашли нарушения этого тезиса.
2) Работу любой машины Тьюринга можно смоделировать на любом реальном компьютере. Из конструкций управления для этого потребуются только логические и циклические (типа if и while). Таких моделей МТ в Интернете навалом.
Следствие 1 и 2: ЛЮБОЙ алгоритм можно представить с помощью условий и итераций.
| № 889 21-08-2006 09:18 | |
>>>1. Эквивалентность всех машин Тьюринга никто не доказывал, и не думаю, что это возможно.
А никто и не говорит об эквивалентности машин :)
Речь идет только о представимости ЛЮБОГО алгоритма в форме программы для соответствующей МТ. Могу Вас порадовать - это тоже нельзя доказать формально. Но за 80 лет никто так и не смог найти алгоритм, который не представим в форме программы для МТ! Хотя попытки были. Ведь найти такой алгоритм - это вечная слава в истории математики.
>>>2. Вообще говоря, любые существующие в мире процессоры являются
конечными автоматами. ;-)
И автоматами тоже. Я же уже говорил об этом. Существует множество так называемых универсальных алгоритмических моделей: конечные автоматы, машины Тьюринга и Поста, нормальные алгоритмы Маркова и т.д. Все эти схемы РАВНОЦЕННЫ - если мы построили хотя бы одну из них, значит можно построить и все остальные! Поэтому все компьютеры - это и конечные автоматы и машины Тьюринга одновременно. Все зависит от того, какая модель представления удобнее в данной конкретной ситуации.
| № 888 21-08-2006 05:31 | |
Ответ на »сообщение 887« (Trurl)
___________________________
Боюсь, для его десятичной записи не хватит бумаги во Вселенной.
Это уж точно.
| № 887 21-08-2006 05:18 | |
Ответ на »сообщение 884« (bb)
___________________________
>>>А как насчет A(4,3)?
Боюсь, для его десятичной записи не хватит бумаги во Вселенной.
| № 886 21-08-2006 04:17 | |
Ответ на »сообщение 880« (Jack Of Shadows)
___________________________
... Geniepro не говорил что функцию Акермана нельзя написать в итерации.
Он сказал что ее гораздо труднее написать в итерации.
То есть теоретически можно, практически, вряд ли вы найдете программиста который с этим бы справился.
Смоделировать любую рекурсию со стеком -- элементарное дело для любого правильно обученного программиста.
Разве что и вправду трудно найти правильно обученного программиста.
Но хотя бы один-то -- Trurl -- у нас точно есть!
| № 885 21-08-2006 03:14 | |
Ответ на »сообщение 872« (SJ)
___________________________
что-то в "массиве-списке" ускоряет обращение по индексу. Что именно? Расположение элементов в списке в смежных полях памяти (как в "классическом" Array) или другие методы?
Вот конкретный вопрос, без "философии" :). Кто знает ответ?
Можно реализовать массив-список в виде сбалансированного дерева. Тогда элементы массива не обязаны располагаться в смежных областях памяти, но операции вставки нового элемента в массив (в том числе и в середину), удаления элемента и обращения к элементу по индексу будут требовать времени O(Log(N)), где N - текущее число элементов в массиве.
Навскидку не могу привести ссылку на конкретный алгоритм, но должно быть у Кнута, также можно поискать в Интернете по ключевым словам "сбалансированные деревья", "AVL-деревья" или "красно-чёрные деревья".
| № 884 21-08-2006 02:44 | |
Ответ на »сообщение 883« (Trurl)
___________________________
А как насчет A(4,3)?
| № 883 21-08-2006 02:31 | |
Ответ на »сообщение 876« (Geniepro)
___________________________
>>>ЗЫ. Кстати, не могли бы Вы посчитать эту функцию с аргументами 5 и 0 ? ( Асс(5, 0) или (асс 5 0) )
>>>Мне очень интересно, какой результат Вы получите...
65533
Добавить свое сообщение
Отслеживать это обсуждение
| Дополнительная навигация: |
| 
