DRAKON.SU

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

По поводу формальных моделей процессоров.
Трудно представить, что бы изготовители процессоров не имели таких формальных моделей, несмотря на всю сложность современных процессоров. Ещё в начале 80-х фирма INMOS имела вполне себе формальные модели своих арифметических сопроцессоров и транспьютеров.

Недавно в институте INRIA (разработчик ФЯ O'Caml и системы доказательства теорем Coq) создали верифицированный компилятор подмножества языка Си для процессора PowerPC The CompCert C compiler -- очевидно, для этого процессора тоже была разработана формальная модель.

Кстати, в этом компиляторе отбросили такие небезопасные конструкции, как оператор goto, процедуры longjmp/setjmp, ненормальные формы оператора switch, процедуры с переменным количеством параметров, и почему-то такие типы данных, как long long и long double. Ну, видимо, если бы было больше финансирования, это всё тоже могли бы реализовать...
По тестам код, генерируемый этим компиляторам превосходит код, генерируемый GCC без оптимизаций, и ненамного уступает GCC с оптимизацией -O1...

Не потребуется. Добавляется одна итерация в цикл разработки, но алгоритм в целом остается тем же самым.

To Alexey_Donskoy
Это сообщение - памятка мне. Я отвечу более развёрнуто (если додумаюсь как : ) ) чуть позже.

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

Это не серебряная пуля. Алгоритм будет эффективен для группы процессоров. Вряд ли для всех процессоров на основе формальной модели.

Немного подумав, я решил, что был неправ, забирая у процессорной логики статус формальной модели. Однако, есть два момента:
1. С точки зрения трансляции алгоритмов в инструкции процессора, такая модель неполна.
2. Для процессора можно построить несколько формальных моделей. При разработке процессора, на мой взгляд, правильнее было бы руководствоваться тем, что модель процессора должна поддерживать трансляцию с ЯВУ в поток инструкций. Примерно об этом несколько десятков лет назад уже писал Вирт. Он говорил, что не смотря на то, что прогресс шагнул далеко вперёд, и повсеместно используются ЯВУ, процессора продолжают разрабатывать для того, чтобы писать программы на ассемблере. Нет поддержки эффективной трансляции с ЯВУ.

Таким образом, на вопрося отвечу заново: это формальная модель, но она неполна. Я уверен, что можно построить (и реализовать) такую фромальную модель, на основе которой можно будет реализовать компилятор, генерирующий код максимальной эффективности. То есть, с помощью ассемблера эффективнее сделать не получится.

Geniepro писал, что сомнительно отсутствие формальной модели процессора у компаний-производителей. Если он под моделью понимал то же, что и я, а также, если он прав, то это объясняет, почему Интел может написать компилятор под свой процессор лучше, чем кто бы то ни было ещё. Но фактически можно констатировать отсутствие модели, поскольку на сайте производителя я её не нашёл. Да и производители компиляторов, скорее всего, её не имеют.

Кстати, эти вопросы очень подробно рассмотрены в первой части книги В.М. Пентковский. "Язык программирования Эль-76" (http://store.oberoncore.ru/lib/book/pvm1989r.djvu). Тем, кто уже раньше скачивал "Автокод Эльбрус" 1981-го, советую посмотреть эту версию 89-го года, в ней всё изложено сильно по-новому.
А так же "Защищённые информационные системы" Бабаяна (http://www.mcst.ru/SECURE_INFORMATION_SYSTEM_V5_2r.pdf). Настаиваю на прочтении всеми , просто чтобы не открывать Америку, а идти дальше...

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

Идём на сайт любого производителя, берём даташит на процессор и прочую документацию. Это и есть не что иное, как формальная модель исполнителя (включая архитектуру и систему команд).

Берём синтаксические диаграммы языка Паскаль. Это и есть не что иное, как часть формальной модели языка. В сумме с архитектурной частью (в данном случае, с описанием типов данных - какой диапазон у integer и т.п.) будет формальная модель исполнителя.

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

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

Разумеется, можно пойти и другим путём - делать исполнителя под какую-либо формальную модель. Так, например, появились стековые Форт-процессоры. И, как напомнил Илья, так появлися Эльбрус.

Однако сегодня парадокс заключается вот в чём - современный процессор способен на очень эффективные действия, которые не находят аналога в промежуточном звене - ЯВУ. То есть ЯВУ являются по существу слабым звеном, тормозящим прогресс:
- с одной стороны, недоиспользуют высокоуровневые абстракции (ту же математику);
- с другой стороны, недоиспользуют низкоуровневые возможности исполнителя.

Насколько мне известно, никто ещё не рассматривал ЯВУ в подобном аспекте. Может, время пришло?

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

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

Далее, по поводу "недоиспользования высокоуровневых абстракций". Алексей, я знаю, что у Вас голова тут ещё по "GOTO-вопросу" болит (т.е. по проблемам линейного структурного программирования), я его сейчас намеренно обойду (эти вопросы разрешимы).

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

Посмотрим на ФП. Компьютеры, вообще, это "физически реализованная математика". Математика работает со структурными моделями реальности, существующими в нашей голове. В универсальных цифровых ЭВМ удалось сделать обратное отображение - физически смоделировать идеальные понятия математики (например, полную дискретность - а отсюда многое другое... Эту особенность - что программист имеет физическую реализацию идеальных вещей - Дейкстра ещё отмечал). Понятие алгоритма - оно, вообще, довольно естественного порядка (из реальности ухваченное). Понятие функции в его максимальном обобщении вроде как более умозрительное, идеальное. Математика, как уже сказали мы выше, работает с идеальными моделями каких-то объектов. Может быть модель на модель, модель в разных терминах (теоретико-множественных, функциональных и т.п.) - это уже их, математиков, прерогативы.
(Кому интересна хорошая книжка об этих вопросах - моделировании и т.п., при этом с точки зрения физика, то могу посоветовать и дать PDF Г.П. Мельникова "Азбука математической логики" (1969 г.). Книжка не требует спец. подготовки и знаний, всего 100 стр., но очень глубокая по своему анализу сути вещей...)

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

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

Ещё был такой язык SETL. Любопытный язык, развивался в нек. университетах США и в Новосибирске, как раз с претензией на сверхвысокоуровневость, только не через функции, а через теоретико-множественные модели. http://ru.wikipedia.org/wiki/SETL
Тоже соблазн - если мы при обычном программировании специфицируем исходные и конечные условия в виде логич. утверждений, которые частично дублируют смысл программы, то не писать ли вообще только эти утверждения, а машина пусть сама трудится над алгоритмом?
Проблемы Сетля немного рассмотрены у Непейводы. Оказывается, что слишком далёкий уход от физической вычислимости чреват последствиями. На подобном языке можно написать с виду безобидные и простые конструкции, совершенно понятные, но чудовищно неэффективные. И оптимизировать их машина не может в принципе - такая трансляция тоже экспоненциальна либо неразрешима... И разделить в сверхвысокоуровневом языке средства так, чтобы сразу была видна их цена, тоже невозможно. Слишком большое расстояние от "чистого существования" в математике до способа это конструктивно сделать в реальности (из чего как раз возникла идея конструктивной математики-логики).

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

Так я, вроде, и не нагружаю. Один и тот же объект может иметь несколько моделей. Я имел в виду не ту модель, к которой привыкли Вы.Прежде, чем отправить то сообщение, я специально зашёл на сайт Интел и не нашёл в документации того, о чём говорю. Документацию, естественно, нашёл.В том-то и дело, что современные процессоры имеют экзотические команды, а алгоритмы таких команд обычно (или всегда) не содержат. Кнут, когда описывает, что такое алгоритм, выбрал именно рецепт в качестве примера того, что алгоритмом не является. Вы уж извините, что на Ваше "алгоритм" я постоянно в ответ "Кнут". С одной стороны, Кнут - заслуживающий доверия источник, с другой, можно глянуть и куда-нибудь ещё (для расширения кругозора). Вот на днях Info21 кому-то (вроде бы Вам) посоветовал книгу по алгоритмам, где, возможно, есть иное толкование. Да, вот, то ли времени не хватает, то ли лень меня заела... : )А разве с середины 50-х и до середины 80-х не именно этим во всём мире занимались?

Если это относится к моим словам (что, прикладывая модель к алгоритму, мы почти автоматически получаем решение), то я это имел в виду в другом контексте. В настоящее время, производители дают для определённых случаев рекомендации: лучше делать так, а не иначе. Это просто рекомендации, они не являются частью модели процессора. Отсюда и проблема: как компилятор может распознать ситуацию, чтобы выбрать оптимальный вариант? А модель не позволила бы блуждать в потёмках как программисту, так и компилятору. Это свойство модели я и назвал "почти автоматическим получением решения".

Да, Илья, Пентковского стоит почитать, спасибо. Почти сразу сформулировал фразу, которую говорил так долго и невнятно. : )
Чтобы повысить эффективность программ на ЯВУ, требуется, чтобы компиляторы знали особенности процессора. А это вряд ли возможно, если эти особенности не являются частью формальной модели.

Никогда не мог понять (и сейчас не пойму), зачем Вы так упорно разделяете алгоритмы и функции. Можете объяснить, Илья?

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

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

Однако Вы также всё время ноете, что аппаратура вообще не тем курсом идёт: не-RISC, плохо заточена под современные языковые конструкции, нет аппаратного теггирования и тд и тп.

Так что мы тут с Вами, Илья, в похожем положении... :о)

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

Валерий, Ваша уверенность под большим вопросом. Тому, что ранее было сказано о неполноте она противоречит.

Сюда.

А вот интересно как раз об рецепте... Можно ли считать не-алгоритмом рецепт на основании того, что в нём что-то задано неточно, с нашей точки зрения? Ведь такие неточности будут всегда и в любом алгоритме - некоторые неопределённости в интерпретации инструкций. Вон для реалтаймщиков жизненно важной может быть длительность выполнения каждой инструкции...

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

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

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

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

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

Мне такой подход кажется неконструктивным (если не сказать утопическим). Мне надо решать конкретные производственные задачи, со вполне конкретным оборудованием. Заделы на будущее - это хорошо, но производителей заставить делать "правильные" процессоры сегодня нереально. И завтра тоже. Если смотреть правде в глаза, то двигателем прогресса выч.техники являются игрушки (на видеокарты посмотрите ) и реальные потребности промышленности (спрос на микроконтроллеры максимально широкой функциональности). То, что разработка софта существенно отстаёт от аппаратной части, давно известно. Что делать?

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

Кстати, мне так кажется, что недетерминированность убивает инварианты и делает бесполезными пред- и постусловия.

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