Ответ на »сообщение 3324« (Руслан Богатырев)
___________________________

Насчет состояний в ФП. Они, конечно, есть. Только в отличие от ИП носят скрытый (подпольный, косвенный) характер, что позволяет отдалить программиста от соблазна прямого вмешательства и, тем самым, содействовать повышению надежности. В этом существенный плюс ФП, который, как и любой плюс, в другом аспекте становится минусом. Считайте, что это автопилот. Но когда нужно ручное пилотирование, приходится стоять на ушах, чтобы отключить автопилот и получить доступ к штурвалу.

Ответ на »сообщение 3322« (Jean)
___________________________
>>>Странный вопрос. Базовые характеристики алгоритма, такие, как,
O(f(N)), прежде всего, зависят от самого алгоритма
Вопрос не странный. Все алгоритмы сортировки, более быстрые, чем O(N^2) используют дополнительную память и различные хитрые манипуляции с ней. Естественно возникает вопрос, как реализовать эти алгоритмы в языке без операции присваивания не увеличивая многократно объем необходимой памяти.

Ответ на »сообщение 3305« (Сергей Перовский)
___________________________

Пока складывается представление, что ФП предпочтительнее для программирования-в-малом, как замена процедурному программированию.

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

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

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

Конечный автомат -- это типичный представитель синхронного мира. Есть набор состояний. Есть матрица переходов. Находясь в таком-то состоянии и прочитав то-то, переходим в другое состояние и пишем то-то. Что читаем и пишем, определяется алфавитом.

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

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

Как известно, чем мощнее модель, тем сложнее она поддается анализу. Поэтому так распространены различные варианты ограничений сетей Петри. Наиболее активно применяются так называемые сети "условия-события" (event-condition nets), когда переход (transition) мыслится как событие (действие), а позиция (position) -- как индикатор условия. В них емкость позиции не может превышать 1 (условие либо выполняется, либо нет), число односторонних дуг между любой конкретной позицией и переходом не может быть больше 1.

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

В реальной практике используют группы автоматов (ансамбли), равно как и иерархические сети. Очевидно, это нивелирует некоторые неудобства моделей, но их сути принципиально не меняет. Чисто математически легко доказывается эквивалентность построения КА из автоматной сети Петри и наоборот.

В принципе можно говорить об автоматном (КА) и асинхронном (СП) программировании как о двух взаимодополняющих мирах. Здесь есть достаточно очевидно прослеживаемая связь с мирами императивного и функционального программирования.

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

К чему это я? Взаимосвязь ИП и ФП носит глубинный характер.

Перефразирую: можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?

Тот же вопрос об HeapSort и времени работы в "худшем" ?

Мне странно, что вместо ответа, я получаю игнорирование или якобы непонимание.

Насколько я знаком со Scheme - это не возможно.

>>>Мой вопрос "можно ли реализовать сортировку за O(N log N) на ФЯ?" в
>>>соседней ветке проигнорировали.
Странный вопрос. Базовые характеристики алгоритма, такие, как,
O(f(N)), прежде всего, зависят от самого алгоритма, а не от того, на каком языке он написан и на какой аппаратуре выполняется. Быстрая сортировка Хоара всегда будет быстрее "пузырька" - и на си, и на паскале, и на хаскеле.
Вопрос лучше поставить таким образом: "Существуют ли алгоритмы сортировки, которые дают время решения задачи O(N log N)?"
Если да, то достаточно написать эти алгоритмы на ФЯ и Вы получите решение задачи за время O(N log N). Если это будет не так, значит транслятор ФЯ заменяет Ваш алгоритм каким-то другим :). Но это уже вопрос к разработчикам транслятора.

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

Не хочу быть назойливым, возвращаясь к моему первому вопросу о производительности. Но "гармоничность" ФЯ построена в ущерб производительности. Поэтому вопрос скорее в том, хотим ли мы получить одно в ущерб другого.

Вы все время выпячиваете больной для ФП вопрос. :) Так мы от "инопланетян" правды не добьемся. Ведь понятно, что их схема есть специфическое ограничение императивного мира. Раз так, значит можно имитировать это ограничение (как определенной дисциплиной, так и средствами библиотечной поддержки). На сугубо императивной архитектуре, как верно заметил Вирт, у императивщиков всегда в этом плане будет преимущество.

Если Вы хотите сказать, что на задачах мелкого масштаба (каковыми являются агоритмические олимпиадные задачи) существенную роль играет расширение типа, связанные процедуры или модификаторы ООП, то позвольте не поверить. Они там просто не успевают "раскочегариться".

Разумеется нет.

В остальном -- нужно смотреть на удобство программирования алгоритмической части в условиях жесткого лимита времени...

Именно об этом. Несмотря на кажущуюся схожесть (Борланд) Паскаля, Модула-2 и Оберонов, тем не менее даже для маленьких программ, где не требуются несколько модулей или расширение записей, есть разница. простой пример - открытые массивы как параметры в функциях. Работа со строками. Или выделение динамической памяти. Да и просто чистота и простота синтаксиса. Надёжность :).

Но мы-то сравнение по олимпиадным задачам проводим с "инопланетянами", братьями по разуму с далекой планеты ФП. :) Которых дискриминируют в высшем обществе спортивного программирования.

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

Не хочу быть назойливым, возвращаясь к моему первому вопросу о производительности. Но "гармоничность" ФЯ построена в ущерб производительности. Поэтому вопрос скорее в том, хотим ли мы получить одно в ущерб другого. Вот такой я не хороший...

Ответ на »сообщение 3318« (Руслан Богатырев)
___________________________

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

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

ИМХО, КП даже в олимпиадах имеет преимущество по сравнению с Паскалем.

Конечно, имеет. Кто же с этим спорит? Хотя Вы наверняка не о классическом Паскале, а о Turbo/Borland/Object Pascal/Delphi?

Давайте попробуем провести разграничительную линию между Паскалем (классическим), Модулой-2 (классической, не ISO), Обероном (классическим) и Компонентным Паскалем. Опять-таки, будем иметь в виду, что есть три ключевые области (о которых упоминал): алгоритмическая, интерфейс (UI, ввод-вывод), инфраструктура.

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

Если грубо "округлять", то разница между Модулой-2 и Обероном -- расширяемые RECORD-типы. Разница между Обероном и КП -- связанные процедуры и модификаторы ООП.

Если Вы хотите сказать, что на задачах мелкого масштаба (каковыми являются агоритмические олимпиадные задачи) существенную роль играет расширение типа, связанные процедуры или модификаторы ООП, то позвольте не поверить. Они там просто не успевают "раскочегариться".

В остальном -- нужно смотреть на удобство программирования алгоритмической части в условиях жесткого лимита времени. Здесь будет играть роль даже все тот же пресловутый регистр идентификаторов (начавшийся в пост-паскалкевских языках с Модулы-2). Это относительное неудобство нивелируется известными средствами, о которых много уже говорили, поэтому в принципе нельзя считать изъяном. В остальном даже отсутствие бесконечных избыточных begin-end уже дает преимущество пост-паскалевским языкам, равно как и общая наглядность синтаксиса в алгоритмической части.

Но мы-то сравнение по олимпиадным задачам проводим с "инопланетянами", братьями по разуму с далекой планеты ФП. :) Которых дискриминируют в высшем обществе спортивного программирования.

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

ИМХО, КП даже в олимпиадах имеет преимущество по сравнению с Паскалем. У меня был переход с Модула-2 на Паскаль. Даже после месяца интенсивного "знакомства" с этим чудо языком, у меня осталось ощущение, что "плаваю в галошах". Даже с точки зрения решения задачек на олимпиаде.

Предполагаю, что схожее ощущение остаётся и от перехода с КП на Модула-2 или Паскаль.

Что касается ФП, то вопрос производительности даже для олимпиад является актуальным. Мой вопрос "можно ли реализовать сортировку за O(N log N) на ФЯ?" в соседней ветке проигнорировали. Но из моего опыта участия в олимпиадах могу сказать, что даже в простых задачах, тестирование проводится таким образом, что бы "простое" решение не проходило по времени на 20% тестах. Что является принципиальным в олимпиадах АСМ.