Здравствуйте, INTP_mihoshi, Вы писали:
WH>>Тут для полноты картины надо еще и про исключения вспомнить. INT>Исключения перпендикулярны и функциональности, и типам. Но замечательно с ними уживаются. Исключение просто можно мыслить как вариант Variant
Я к тому что для сигнализации об ошибке еще и исключения используют...
... << RSDN@Home 1.1.4 rev. 185 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, faulx, Вы писали:
F>А вообще, конечно, на идеальном декларативном языке (синтаксис придумал сам, на ходу) алгоритм сортировки записывается примерно так:
F>
F>sort (in Sequence seq, out Sequence sorted)
F>PRE{
F> // Предусловие - вероятно, пустое
F>}
F>POST{
F> // Постусловие - описание отсортированности последовательности sorted
F>}
F>
F>А уж компилятор должен по этому описанию изобрести алгоритм быстрой сортировки, а заодно и его эффективную реализацию. Вот жизнь-то начнется, когда напишут такой компилятор
И не говори! Я уже даже представляю, какую первую программу для себя напишу:
Buisnes (in Man бедный, out Man богатый )
PRE
{
мало денег
}
POST
{
много денег
}
Э-х-х-х, и когда уже, наконец, появится этот компилятор???
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, FR, Вы писали:
FR>>Я уже три раза писал что меряют скорость работы памяти, но не слышат. Вообще в этом тесте если выбирать те ограничения которые здесь были (~3e6 элементов) то bcc5.4 c отключенной оптимизацией показывает примерно одинаковую скорость с VC7.1 c /O2
G>Ну если ты настаиваешь... Напиши решето эратосфена на Python (без psyco), и померяй им скорость работы памяти. Боюсь, что память почему-то будет работать медленнее , наверно программа на питоне ее сломает.
Я лучше на ocaml напишу Он точно не куда не упрется
Питон (c psyco) не может упереся в память, плохие у него массивы(вернее их и нету вовсе), мерять на специальных библиотечных массивах не стал, но скорее всего они уже упрутся в память.
G>Мы вообще-то компиляторы сравнивали, на одном алгоритме. Точнее, эффективность работы с массивами в чистом ФЯ сравнительно с С++. А не устанавливали рекорды скорости. Поэтому и не слышим.
А зря, потому что сравниваете не эффективность, а скорость работы шины памяти. Вообще наверно у меня были глюки когда я читал про хорошие компиляторы.
G>То, что С++ и Clean уперлись в память, говорит об эффективной работе с массивами. Haskell не смог "упереться в память". Боюсь у питона тоже не получится.
ну и что уперется в память могут языки (или компиляторы) производительность которых отличается на порядок, так что говорить об такой же эффективной реализации массивов в CLean как и в C++ очень даже некорректно, а из твоих постов напрашивается именно такой вывод.
Здравствуйте, INTP_mihoshi, Вы писали:
INT>Здравствуйте, prVovik, Вы писали:
V>>Здравствуйте, INTP_mihoshi, Вы писали:
V>>Во-вторых, это простой случай. Что, если бы пришлось учитывать не возраст, а, например, количество волос на голове? Пришлось бы каждый момент времени сохранять текущее значение? INT>Это уже вопросы реализации.
А именно о реализации и речь. Понятно, что в абстрактной теории все хорошо...
V>>Совершенно верно. Но проблему это всеравно не решает. INT>Какую проблему?
Проблему изменения малого компонента системы без того, чтобы менять всю систему и при этом остаться в рамках функционального стиля.
INT>Любую задачу, любой алгоритм, который можно выразить с помощью ыормальной логики, можно описать в чисто функциональном стиле. Это доказывается. Если ты хочешь доказать обратное — не трудись, это невозможно.
Я уже много раз повторял, что я с этим не спорю. Речь не о математики, а о программировании, которое отличается от матиматики одной малозначительной деталью: вычислительные, увы, не бесконечны.
Здравствуйте, Gaperton, Вы писали:
G>Мы вообще-то компиляторы сравнивали, на одном алгоритме. Точнее, эффективность работы с массивами в чистом ФЯ сравнительно с С++. А не устанавливали рекорды скорости. Поэтому и не слышим.
Ну тогда в качестве задачки предлагаю искать минимальный элемент в массиве. Для простоты элементы массива можно ниоткуда не вводить, а результат никуда не выводить.
void FindMin()
{
int array[500000000]; // ДВА ГИГАБАЙТА !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!for( int i=0, min=array[0]; i < sizeof(array)/sizeof(int); ++i )
{
if( array[i] < min ) min = array[i];
}
}
int main()
{
FindMin();
return 0;
}
Время выполнения: 0.0000000000 сек.
Не правда ли, у С очень эффективная работа с массивами!!!!!
Здравствуйте, Quintanar, Вы писали:
Q>Из локального изменения массива не следует возникновение строннего эффекта.
Из изменения массива появляется ВОЗМОЖНОСТЬ побочного эффекта. А функциональный стиль требует ГАРАНТИИ их отсутствия. Я понимаю, что в простейших случаях может сработать оптимизатор, но всеже...
Q>Для того, чтобы этого добиться в чистых функциональных языках применяют разные методы, про Clean тебе ответил Gaperton, а в Haskell'e это решается с помощью монад — они позволяют упорядочить вычисления, добиться того, чтобы перед вычислением Б обязательно вычислялось А.
Дак это и есть итеративная программа! То есть ты подтверждаешь мои слова!
Q>Дело в том, что реально такие сугубо императивные куски типа работы с массивами встречаются достаточно редко, их можно изолировать и обрабатывать отдельно в монадном-императивном стиле. Потом массив можно банально перевести в read-only форму и работать с ссылкой на него, не заморачиваясь проблемой копирования его целиком.
Опять таки, я с тобой абсолютно согласен, действительно, часть программы можно написать в функциональном стиле, но от императивного не избавиться. Об этом я писал еще в том посте, за который вы мне понаставили минусов (я, кстати, так и не погял: с чем именно вы не согласны? ).
Вот скажи, если бы тебе пришлось профессионально заняться фотографией, ты бы использовал для телефон со встроенным фотоаппаратом, или отдельный профессиональный фотоаппарат? Есть большое количество классов программ, а именно: программы, ориентированные на конечного пользователя (текстовые редакторы, например), всевозможные АСУ (бухгалтерские программы, документооборот и пр.), компьютерные игры (реальные, а не "академические") в которых будет доминировать именно итеративная составляющая. Дак может быть стоит все-таки использовать для таких задач языки, которые ИЗНАЧАЛЬНО приспособлены для программирования в итеративном стиле, а не "костыли", предоставляемые функциональными языками (это как телефон со встроенным фотоаппаратом ). Читая эту, и некоторые другие ветки, у меня сложилось впечатление, что вы все утверждаете обратное!
Здравствуйте, Sinclair, Вы писали:
S>В итоге, императивное программирование предоставляет программисту возможность формулировать эти представления вручную. Функциональное программирование больше сосредотачивается на результате, чем на процессе. Это фактически попытка передать больше обязанностей по выполнению той же задачи компилятору.
Да, но, увы, искусственного интеллекта не суествует, а потому в любом случае задачу придется "разжевать" до атомарной алгоритмической кашицы, которую часто практически "один в один" можно перевести на итеративный язык.
Здравствуйте, prVovik, Вы писали:
V>Из изменения массива появляется ВОЗМОЖНОСТЬ побочного эффекта. А функциональный стиль требует ГАРАНТИИ их отсутствия. Я понимаю, что в простейших случаях может сработать оптимизатор, но всеже...
Ты не понимаешь. Функциональный стиль не требует гарантии отстутствия побочных эфектов. Функциональный стиль как раз не предоставляет возможностей для возниктовения побочных эффектов.
Q>>Для того, чтобы этого добиться в чистых функциональных языках применяют разные методы, про Clean тебе ответил Gaperton, а в Haskell'e это решается с помощью монад — они позволяют упорядочить вычисления, добиться того, чтобы перед вычислением Б обязательно вычислялось А. V>Дак это и есть итеративная программа! То есть ты подтверждаешь мои слова!
f3(x,f2(y,f1(z))) — в строгом функциональном языке, функция f1 вычислится раньше чем функция f3. И это не итеративная программа. Монады — лишь синтаксический прием, что бы не писать вложеные вызовы. Заметь, в этой программе нет состояния в определенный момент времени. Тем не менее можно точно сказать что после чего будет вычислено.
Здравствуйте, Nick_, Вы писали:
N_>Еще бы эта программа компилировалась и ченить полезное делала...
Во-первых, эта программа компилируется, а во-вторых, она не менее полезна, чем та, о которой идет речь, и в-третьих, если я поставил мало смайликов и надо было специально написать слово "лопата", то извени...
Здравствуйте, prVovik, Вы писали: V>Да, но, увы, искусственного интеллекта не суествует,
Это верно V>а потому в любом случае
Уже спорно V>задачу придется "разжевать" до атомарной алгоритмической кашицы,
Вопрос в степени этой атомарности V>которую часто практически "один в один" можно перевести на итеративный язык.
А это уже совсем неправда. Я сходу могу привести N+1 примеров, в которых постановка задачи перед средой исполнения очень и очень далека от императивного (кстати, итеративный!=императивный) представления. И безо всякого интеллекта среда очень неплохо справляется с этой задачей.
... << RSDN@Home 1.1.4 beta 3 rev. 185>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Nick_, Вы писали:
N_>Ты не понимаешь. Функциональный стиль не требует гарантии отстутствия побочных эфектов. Функциональный стиль как раз не предоставляет возможностей для возниктовения побочных эффектов.
Это не так. См. ниже
Q>>>Для того, чтобы этого добиться в чистых функциональных языках применяют разные методы, про Clean тебе ответил Gaperton, а в Haskell'e это решается с помощью монад — они позволяют упорядочить вычисления, добиться того, чтобы перед вычислением Б обязательно вычислялось А. V>>Дак это и есть итеративная программа! То есть ты подтверждаешь мои слова! N_>f3(x,f2(y,f1(z))) — в строгом функциональном языке, функция f1 вычислится раньше чем функция f3. И это не итеративная программа. Монады — лишь синтаксический прием, что бы не писать вложеные вызовы.
Зато ТРЕБУЕТСЯ, чтобы результат вызова f( f1(), f2(), f3() ) был одинаковым вне зависимочти от порядка вызова f1() f2() f3(). Если какая-то из этих ф-ций имеет побочный эффект, то результат f( f1(), f2(), f3() ) неопределен.
Здравствуйте, VladD2, Вы писали:
VD>В приведенном виде сортировка уже может трактоваться как сортировка слиянием или даже пиповая. Хор изобрел конкретный алгоритм.
Хоар изобрел две вещи. Первая — это собственно алгоритм быстрой сортировки, формально отраженный приведенной программой на Haskell'е. Вторая — эффективная реализация этого алгоритма на императивной машине. Компилятор Haskell'а в данном случае выполняет часть работы Хоара — т. е. изобретает реализацию алгоритма на ассемблере. Разумеется, далеко не факт, что эта реализация будет столь же эффективна, как Хоаровская.
VD>Переврать Хор ничего не мог так как он был изобретателем данного алгоритма.
Повторяю — Хоар изобрел две вещи: алгоритм и его реализацию. Если будет найдена более эффективная реализация, будет ли это значит, что Хоар переврал в своей реализации? Нет? Тогда почему компилятор Haskell'а врет в своей?
VD>Алгоритм не может быть описан математически. Матемотически можно только задать принцип. А принцип скорее оностистя к лассу алгоритма. Ведь основной принцип в бустрой сортировке это рекурсивное деление списков на подсписки. Но под это определение начинают попадать и некоторые другие алгоритмы.
Почему это алгоритм нельзя задать математически? Математика — термин широкий, да и способов формализации алгоритма (точнее, вычислений) существуем тоже не один. Кстати, почему-то никто не упомянул о таком языке, как Рефал, который, сколь я знаю, основан на Марковских алгорифмах.
VD>К тому, же как я говорил у Хора за "средний" брался то ли элемент массива находящийся посередине, то ли послебний (правый). Если брать не средний элемент, то на сортированном списке алгоритм будет существнно медленнее.
Средний элемент — это не тот, который посередине, а медиана. Если браться находить медиану, то алгоритм тоже станет медленнее. Поэтому на практике берут какой попало элемент, и первый (в среднем) ничуть не хуже и не лучше второго или последнего.
VD>Это, как я понимаю, называется логическим программированием.
Ну, разве что в теории.
VD>Прологу уже много лет. Кстати, не факт, что такие простые вещи как сортировка не будет проще описать алгоритмически.
"Алгоритмически" — это синоним "императивно"?
Кстати, Пролог вряд ли решит эту задачу. Максимум, что он выведет из такого описания — это алгоритм сложности O(n!), генерирующий перестановки и выбирающий сортированную.
VD> Ну, а глваная проблема тут в том, что компилятор должен знать конкретные алгоритмы и уметь подбирать наиболее подходящий в конкретном случае, а то и уметь изобретать алгоритмы и выбирать наиболее подходящий. Ну, а это уже искуственный интелект. Да даже не искуственный, а идеальный. Ведь далеко не каждый человек знает все нужные алгоритмы и умеет правильно их выбирать. Но мечат о зеленой факсовй кномке нажатие на ктороую автоматически решает луюбую сложную проблему — это та мечта к которой нужно стремиться всему человечесту.
На самом деле, если такая кнопка будет (или будет такой компилятор), это далеко не решит всех проблем и не отменит программистов. Ведь спецификации тоже надо задавать. В качестве самопроверки: какие условия должны стоять в моей программе в секции POST?
PS. А вообще, чтобы не было недоразумений, спешу объясниться. Разумеется, некорректно сравнивать приведенную программу быстрой сортировки на Haskell'е с Хоаровской реализацией на С. Прежде всего, в них сортируются разные объекты — в Haskell'e список, а в Си — массив. Далее, некорректно сравнивать их по производительности. Разумеется, реалиазация на Си эффективней.
Потом, некорректно объявлять, что программа на Haskell'е выражает преимущества функционального подхода в целом. Дело в том, что эта программа приведена в самом начале учебника по Haskell'у, и иллюстрирует она именно преимущества этого языка, а не подхода в целом. В ней, собственно говоря, не так уж много чисто функционального. К тому же она не оптимальна — в ней делается лишний проход по списку (разделить список на два подсписка можно и за один проход), она не tail-recursive, да и операция конкатенации списков тоже накладна.
Однако это все придирки. На практике же это выглядит так: написали короткую программу, и она сразу заработала. Сортировка происходит без ошибок? Так в этом и состояла цель!
Здравствуйте, prVovik, Вы писали:
N_>>f3(x,f2(y,f1(z))) — в строгом функциональном языке, функция f1 вычислится раньше чем функция f3. И это не итеративная программа. Монады — лишь синтаксический прием, что бы не писать вложеные вызовы. V>Зато ТРЕБУЕТСЯ, чтобы результат вызова f( f1(), f2(), f3() ) был одинаковым вне зависимочти от порядка вызова f1() f2() f3(). Если какая-то из этих ф-ций имеет побочный эффект, то результат f( f1(), f2(), f3() ) неопределен.
Функциональные языки не предоставляют возможности написать функцию с побочным эффектом. Поэтому результат вызова f(f1(), f2(), f3()) будет одинаковым вне зависимости от порядка вызова. Можно даже вычислять аргументы одновременно в разных потоках.
А вот когда вызываются внешние функции, которые могут иметь побочный эффект, то им передается окружение, а они в свою очередь возвращают новое окружение, которое передается следующему вызову внешней функции. И f(f1(e),f2(e)), где f1 и f2 внешние функции написать нелзя.
Здравствуйте, Sinclair, Вы писали:
V>>задачу придется "разжевать" до атомарной алгоритмической кашицы, S>Вопрос в степени этой атомарности
Определяется атомарностью СТАНДАРТНЫХ для среды исполнения решений.
V>>которую часто практически "один в один" можно перевести на итеративный язык. S>А это уже совсем неправда. Я сходу могу привести N+1 примеров, в которых постановка задачи перед средой исполнения очень и очень далека от императивного (кстати, итеративный!=императивный) представления. И безо всякого интеллекта среда очень неплохо справляется с этой задачей.
Речь не идет о СТАНДАРТНЫХ решениях, под которые "заточена" та или иная среда исполнения. Я говорю о языках общего назначения. Хотя, если говорить иенно о стандартных решениях, то они существенно не отличаются от библиотек. И в том, и в другом стучае алгоритм ДЕТЕРМИНИРОВАН. Разница только в удобствах.
F>Кстати, Пролог вряд ли решит эту задачу. Максимум, что он выведет из такого описания — это алгоритм сложности O(n!), генерирующий перестановки и выбирающий сортированную.
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, faulx, Вы писали:
F>>Кстати, Пролог вряд ли решит эту задачу. Максимум, что он выведет из такого описания — это алгоритм сложности O(n!), генерирующий перестановки и выбирающий сортированную.
FR>
Это — слишком частное описание. Здесь мы фактически подсказываем компилятору, что делать. Нет, в данном случае я имел в виду, что после :- должно находится описание отсортированного списка. Я не настолько хорошо помню Пролог, чтобы записать это на нем, но попробую неформально:
1. Результат состоит из тех же элементов и в тех же количествах, что и исходный список.
2. Каждый элемент результата (кроме первого) больше (либо равен) предыдущего элемента.
Если ваш компилятор Пролога по этому описанию построит быструю сортировку — дайте ссылочку, где можно скачать
Здравствуйте, faulx, Вы писали:
F>Если ваш компилятор Пролога по этому описанию построит быструю сортировку — дайте ссылочку, где можно скачать
Если у вас есть компилятор любого другого языка, который по аналогичному описанию построит любой алгоритм с асимптотикой NlogN — тоже дайте сылочку!
... << RSDN@Home 1.1.4 beta 3 rev. 185>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, prVovik, Вы писали:
V>Зато ТРЕБУЕТСЯ, чтобы результат вызова f( f1(), f2(), f3() ) был одинаковым вне зависимочти от порядка вызова f1() f2() f3(). Если какая-то из этих ф-ций имеет побочный эффект, то результат f( f1(), f2(), f3() ) неопределен.
Разделяйте строгие и ленивые (нестрогие) функциональные языки. В строгих все аргументы вычисляются до вызова самой функции, поэтому порядок вычислений определен заранее и побочные эффекты особого значения не имеют — они только способствуют появлению императивных глюков и их лучше избегать. Чего вы пытаетесь доказать никак не пойму. Если, что на функциональных языках нельзя писать программы, то нет — можно. Все компиляторы ФЯ обычно пишутся на них самих, например. Если, что понятие состояния невыразимо в ФЯ, то это тоже не так. Только там оно (причем только в ленивых языках) явно передается по цепочке вычислений — это ничего не меняет по сути. В программе на С тоже можно в каждую функцию передавать глобальное состояние и не пользоваться глобальными переменными. Говорят, оптимизаторы именно так и поступают в императивных языках — делают изменение состояния программы явным.
).
