Ответ на »сообщение 611« (Jack Of Shadows)
___________________________

currying Это когда любую функцию, принимающюю n аргументов можно представить как n функций, каждая из которых принимает только один аргумент.

http://en.wikipedia.org/wiki/Currying

Почитал статью, суть в принципе понятна, вот только примеры там какие-то странные...
Нет бы просто написать: f(x1, x2, x3) -> f1(f2(f3(x))) или что-то типа того...

Кстати, по-моему, так можно преобразовать далеко не каждую функцию.
И для чего, это, кстати, нужно? Какие выгоды даёт?


Теперь мне остается надеяться, что вы таки представите цифры по прогону представленного алгоритма на mercury.
Язык доступен для скачивания. За чем же дело встало ?

Хе-хе... А он в отпуск ушёл, ему не до Меркурия... :-)

А почему, кстати, такие сомнения по поводу автоматической мемоизации?
Разве у Вас есть основания думать, что на Mercury результаты будут хуже, чем на CLisp?
Почитаю, что такое этот Mercury, может, тоже скачаю, посмотрю... Что-то типа Хаскелля, что ли?..

Ответ на »сообщение 609« (Geniepro)
___________________________
Нельзя ли в двух словах про currying?
currying Это когда любую функцию, принимающюю n аргументов можно представить как n функций, каждая из которых принимает только один аргумент.

http://en.wikipedia.org/wiki/Currying

Ответ на »сообщение 608« (Lisp Hobbyist)
___________________________
Спасибо за ссылку на mercury. :))
Благодары вам я теперь знаю что автоматическая мемоизация не только возможна но и реализована.
Теперь мне остается надеяться, что вы таки представите цифры по прогону представленного алгоритма на mercury.
Язык доступен для скачивания. За чем же дело встало ?

А я и сравниваю --- существующие языки с существующими языками.

Где ? В упор не вижу. Сравнение существующих языков с существующими же языками предполагает прогон кода и предоставление результатов на двух компиляторах.
Вы представили цифры по лиспу. Где цифры по другому языку ?


Наличие в Common Lisp по стандарту императивных составляющих и динамического переопределения кода "на лету" существенно затрудняет для него реализацию интеллектуальных исполнителей. Т.е. проблема --- в дизайне языка.


Согласен. Более того я говорил уже об этом. О том что императивная составляющая лиспа делает невозможным примемение оптимизации, которая доступна чисто функциональным языкам.


Пока что мне понятно лишь то, что доказательства своих слов Вы привести не можете, а занимаетесь словесным жонглированием.


Вот упертый. :)) Да это не мне а вам нужно было приводить доказательства.
Это вы начали тему про оптимизацию функционального алгоритма средствами компилятора.
Это вам нужно было приводить цифры прогона на ДРУГОМ компиляторе.
Чего я у вас многократно просил, и кстати продолжаю просить.
Вы сделали пол дела - показали мне что я был неправ по поводу автоматической мемоизации.
Так доделайте свое дело. Приведите цифры прогона алгоритма на mercury.
Или нужно обязательно проспорить на сотню сообщений, прежде чем вы триумфально выкатите факты ?

Ответ на »сообщение 607« (Jack Of Shadows)
___________________________

У вас есть что представить общественности, кроме пожеланий на эту тему ?
Опять таки, если у вас есть что то интересное по теме автоматического преобразования алгоритмов, с удовольствием приобщусь.


Увы и ах! Пока я только интересуюсь этой проблемой...


А пока что единственное что я знаю по этому поводу это currying.


Нельзя ли в двух словах про currying?
________________

Начал снова перечитывать книгу Питера Хендерсона "Функциональное программирование..." Лет десять в руках не держал.

Попробую реализовать транслятор упрощённого варианта Лиспа - там эта тема неплохо раскрыта. Самому интересно, что получится...
Интерпретатор на Дельфах я уже видел, так что шансы сделать есть... ;-)

Когда сделаю транслятор - буду думать над подобными оптимизаторами.
Для чистого ФЯ без побочных эффектов, мне кажется, мемоизация вполне подойдёт.
Развёртка рекурсий, наверняка, тоже...
Интересно, как развернуть косвенную рекурсию?.. Явно непросто...

Ответ на »сообщение 602« (Jack Of Shadows)
___________________________

Простите но автоматическая мемоизация это из области фантастики :))

"А мужики-то и не знают!"

http://www.cs.mu.oz.au/research/mercury/download/release-0.8.html


>>>  We have added support for automatic tabling (memoization).

Насколько я могу судить из описания этой системы программирования, возможность memoization уже встроена в нее, правда пока что включается для каждой функции выборочно специальной прагмой. Впрочем, никто не мешает подправить реализацию так, чтобы этот режим был выбран всегда, но при нынешних объемах ОЗУ это все же пока менее практично, чем выбор более эффективных алгоритмов.

изначально речь шла о том что мол лисп медленный или неэффективно оптимизирует.
Но вы можете утверждать это только сравнивая лисп с СУЩЕСТВУЮЩИМИ языками, а не с гипотетическими.

А я и сравниваю --- существующие языки с существующими языками. Существующие их реализации --- между собой, и оценочные характеристики будущих  реализаций (спрогнозировать их можно с высокой степенью точности) --- между собой и с существующими. Еще раз:

1. Применение технологии memoization в состоянии улучшить эффективность вычисления "наивных" рекурсивных определений до практически приемлемого уровня (при этом эффективные алгоритмы все равно, скорее всего, будут впереди). С ростом объемов ОЗУ цена применения этой технологии будет снижаться.

2. Для сохранения простоты и прозрачности функциональных программ все вопросы их исполнения должны максимально быть отданы на усмотрение исполняющей подсистемы, в т.ч. memoization.

3. Наличие в Common Lisp по стандарту императивных составляющих и динамического переопределения кода "на лету" существенно затрудняет для него реализацию интеллектуальных исполнителей. Т.е. проблема --- в дизайне языка. Еще раз отмечу: я не утверждаю, что Коммон Лисп плохо спроектирован --- просто он предназначался для других "паттернов" использования.

4. Для чисто функциональных языков проблема реализации интеллектуальных исполнителей сводится к другим факторам --- нехватке существующих вычислительных мощностей, отсутствию интереса/необходимости. Т.е. проблема в отсутствии подходящей реализации --- дизайн языка таких же серьезных трудностей, как Common Lisp, не вызывает.

Проблема (3) будет существовать все время, пока определение Коммон Лиспа будет таким, каким оно есть, а проблема (4) --- временная. ИМХО, разница все-таки наблюдается: изменить дизайн языка практически невозможно, а написать новую реализацию --- не то, чтобы совсем просто, но гораздо проще изменений языка.

Таким образом, отсюда следует тот вывод, который я и пытаюсь озвучить уже немалое количество времени: если кого-то интересует именно та простота и четкость выражения своих мыслей, которую дает ФП, то ему не следует связываться с Common Lisp'ом, так как в самом дизайне языка заложены неустранимые (с точки зрения ФП) препятствия для роста его эффективности. С другой стороны, уже существующие специализированные ФП-языки такой "родовой травмы" не имеют, и в ближайшем будущем их реализации по эффективности с высокой вероятностью превзойдут реализации Лиспа.

Если на пальцах, "наивная" функция fib написанная сегодня на Лиспе и Хаскелле (например!) будет тормозить практически одинаково. Но через 5-10 лет эта же самая функция, запущенная на выполнение в будущих реализациях тех же самых языков, может показать принципиально иные результаты --- Хаскелл может оказаться (и скорее всего, окажется) быстрее. Вопрос нехватки быстродействия станет менее острым, но зато во всей своей красе предстанет другая выгода "наивности" --- читабельность и легкость понимания. А на Лиспе писать в "наивном" стиле будет по-прежнему невозможно. Изучение ФП сейчас --- это инвестиции в будущее. Поэтому я и призываю тех, кого интересует ФП (именно ФП, а не другие фичи Лиспа) очень внимательно подумать, во что им вкладываться. А Лисп при этом изучить все равно надо --- чтобы получить представление о том, что рамками ФП программирование не ограничено :-)

Если хотите могу исправить свое первоначальное утверждение привести его к виду

На любом СУЩЕСТВУЮЩЕМ языке, первый алгоритм выдаст те же результаты по времени.

Так понятнее ? :))


Пока что мне понятно лишь то, что доказательства своих слов Вы привести не можете, а занимаетесь словесным жонглированием. Кстати, между прочим, AFAIK обычно сравнивают эффективность не языков, а их реализаций. Похоже, в этом и есть источник непонимания --- у меня складывается впечатление, что Вы отождествляете язык как абстрактную конструкцию (с присущими ему свойствами) и его конкретную реализацию (у которой набор свойств зависит от свойств языка, но уже другой), а такая эквивалентность неверна.

На этом откланиваюсь --- я пришел к выводу, что могу найти своему отпуску лучшее применение, чем, как бы это вежливо сформулировать, "синхронизация методом тыка систем взглядов на вопросы Computer Science и методологию науки в целом". Можете считать, что эта дискуссия осталась за Вами, если это так важно для Вашего реноме.

Ответ на »сообщение 606« (Geniepro)
___________________________

Но так и прогресс остановиться может...


Эт вряд ли :))


А как же методы компьютерной алгебры, теория преобразования алгоритмов?...


У вас есть что представить общественности, кроме пожеланий на эту тему ? У меня нет.

Ну а конец света, о котором я говорил, в научных кругах называется технологической сингулярностью, и ожидается примерно на том отрезке времени, который я указал.
Еслb интересуетесь - можете почитать вот здесь:
http://en.wikipedia.org/wiki/Technological_singularity

Но это офтопик, так что давайте вернемся к нашим ФЯ.

Опять таки, если у вас есть что то интересное по теме автоматического преобразования алгоритмов, с удовольствием приобщусь.
А пока что единственное что я знаю по этому поводу это currying.
Но там преобразованием рекурсии в итерацию не пахнет.

Ответ на »сообщение 605« (Jack Of Shadows)
___________________________

Ну а что там возможно будет через 50 лет, у меня на этот счет своя теория, и боюсь она вам не понравится. :))

Я ожидаю конца света к году эдак 2045-2050.
Как вам наше обсуждение в свете близкого конца света, а ? :))

Ну, это спорный вопрос... Тут уж действительно загадывать невозможно - конец света и завтра может наступить - сойдёт с ума какой-нить президент с красной кнопкой в руках - и усё, Конец, Света!
Или просто машина переедет - субьективно, тот же самый конец света... :-(


Поэтому я стараюсь придерживаться обсуждения тех вещей, которые нам доступны прямо сейчас.

Типа - Keep It Real?! (С) Ali G ;-) Но так и прогресс остановиться может...


Не думаю что это возможно в ближайшем будущем.
То же самое про автоматический преобразователь.

А как же методы компьютерной алгебры, теория преобразования алгоритмов?...
Особенно в свете крутости Лиспа в области символьной обработки... ;-)

ЗЫ. Я ожидаю конца света к году эдак 2045-2050.
Кстати, а почему именно этот период? :-о

Ответ на »сообщение 604« (Geniepro)
___________________________

Может быть, поставим вопрос по другому:

"Возможно ли сделать автоматический преобразователь функций с несколькими рекурсивными вызовами в итеративный и более эффективный вариант?"


Дык вопрос можно поставить самымми разными способами. :)) Как например предложил Lisp Hobbyist - автоматическая мемоизация.
Не думаю что это возможно в ближайшем будущем.
То же самое про автоматический преобразователь.
Видите ли, можно превратить эту ветку в мечтания со слюнопусканием, типа "а что было бы если..."
Опять таки, рано или поздно мы все с вами придем к идее квантовых компьютеров, и прочей лабуде, несомненно очень интересной, но не в рамках нашего обсуждения функциональных языков.
Поэтому я стараюсь придерживаться обсуждения тех вещей, которые нам доступны прямо сейчас.

Ну а что там возможно будт через 50 лет, у меня на этот счет совя теория, и боюсь она вам не понравится. :))

Я ожидаю конца света к году эдак 2045-2050.
Как вам наше обсуждение в свете близкого конца света, а ? :))

Ответ на »сообщение 603« (Jack Of Shadows)
___________________________


изначально речь шла о том что мол лисп медленный или неэффективно оптимизирует.


Может быть, поставим вопрос по другому:

"Возможно ли сделать автоматический преобразователь функций с несколькими рекурсивными вызовами в итеративный и более эффективный вариант?"

Мне почему-то кажется, что это возможно...

Ответ на »сообщение 601« (Lisp Hobbyist)
___________________________

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


Я не буду с вами в этом спорить, но изначально речь шла о том что мол лисп медленный или неэффективно оптимизирует.
Но вы можете утверждать это только сравнивая лисп с СУЩЕСТВУЮЩИМИ языками, а не с гипотетическими.
Поэтому ваш наезд на меня по поводу автоматической мемоизации мне непонятен.
Я ведь тоже могу отталкиваться от того что не существует, от квантовых компьютеров например.
Ну и к чему мы с вами придем в таком случае ?
Ведь дискуссия станет бессмысленной.
Мы говорим здесь о ФЯ сегодня. О применении их в учебе и на практике. Об использовании существующих прямо сейчас компиляторов, библиотек, сред.
А вы со своими гипотетическими языками с автоматической мемоизацией, чего вы хотите сказать ?
Что лисп и вообще любой ФЯ медленный ? По сравнению с чем ? С несуществующими языками ? или с несуществующими же квантовыми компьютерами ?
Или может быть по сравнению с тем что существует и используется в программировании ?
О том и речь, приведите факт.
Приведите данные по времени исполнения наивного алгоритма скомпилированного на любом существующем языке, компиляторе.
Тогда можно будет говорить о том насколько лисп медленнее.
А пока что это все досужие разговоры. Есть ли жизнь на Марсе, нет ли жизни на Марсе :))