Математика и программирование

[Tauon]

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

А есть ли в математике идеи как конвертировать программу из одной архитектуры в другую?

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

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

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

P.S. Извините за возможный сумбур в изложении мысли.

[rockclimber]

Вам слово java говорит о чем-нибудь?
А слово "кроссплатформенность"?


-- 12.07.2017, 15:58 --

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

[Tauon]

rockclimber
Да, Вы правы на счет Java и кроссплатформенности, но это не совсем то что я хотел. Я хотел бы узнать про математическую теорию, которая позволяла бы "преобразовывать логику из одной логической системы в другую с помощью уравнений" (не знаю как правильно сказать чтобы не засмеяли ). А Java работает иначе: она для каждого аппаратного решения создает свою виртуальную машину, логика которой везде одинакова. Трюк хитрый конечно, но это не то.

rockclimber в сообщении #1233010 писал(а):

Я это к тому, что на практике задача решена немного другим способом.

В точку.

[mihaild]

Что вы понимаете под "уравнениями"?)

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

[Tauon]

mihaild в сообщении #1233019 писал(а):

Что вы понимаете под "уравнениями"?)

Ну... Скажем какой-то аналог уравнений перевода координат точки из одной системы отсчета в другую систему отсчета. Точнее не могу конкретизировать.

mihaild в сообщении #1233019 писал(а):

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

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

[Munin]

rockclimber в сообщении #1233010 писал(а):

Вам слово java говорит о чем-нибудь?
А слово "кроссплатформенность"?

Ещё добавлю слово "эмуляция".

[mihaild]

Tauon в сообщении #1233022 писал(а):

Скажем какой-то аналог уравнений перевода координат точки из одной системы отсчета в другую систему отсчета. Точнее не могу конкретизировать

А придется, иначе совсем непонятно будет.
Уравнение - это обычно запись вида $F(x) = 0$, где $x$, $F$ выражено через что-то. Можете сформулировать, что такое у вас $x$ (видимо, пара программ), и через что вы хотите выражать $F$?

Tauon в сообщении #1233022 писал(а):

Но мы, наверное, можем провести поиск минимума/максимума быстродействия (опять же не тривиальная математическая задачка).

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

[Sonic86]

Tauon в сообщении #1233022 писал(а):

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

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

int f(int n){
  while (n>1){
    if (n%2==0){
      n=n/2;
    }
    else{
      n=3*n+1;
    }
  }
}

до сих пор никто оптимизировать не может ($n\in\mathbb{N}$)

mihaild в сообщении #1233027 писал(а):

и еще тут надо решить, что делать, если на одном входе одна быстрее, а на другом - другая

Кстати да. Только асимптотики, как известно, недостаточно.

Tauon в сообщении #1233014 писал(а):

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

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

[mihaild]

Sonic86, для 32-битной архитектуры оптимизировано:)

Sonic86 в сообщении #1233028 писал(а):

($n\in\mathbb{N}$)

плохо согласуется с int n.

[Sonic86]

(Оффтоп)

mihaild в сообщении #1233031 писал(а):

для 32-битной архитектуры оптимизировано:)

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

[Tauon]

mihaild в сообщении #1233027 писал(а):

Tauon в сообщении #1233022 писал(а):

Скажем какой-то аналог уравнений перевода координат точки из одной системы отсчета в другую систему отсчета. Точнее не могу конкретизировать

А придется, иначе совсем непонятно будет.
Уравнение - это обычно запись вида $F(x) = 0$, где $x$, $F$ выражено через что-то. Можете сформулировать, что такое у вас $x$ (видимо, пара программ), и через что вы хотите выражать $F$?

Наверное, необходимо следующее:
1. Каким-то формальным образом записывать логику архитектуры;
2. Каким-то формальным образом записывать логику программы для конкретной архитектуры;
3. Установить формальные правила, позволяющие устанавливать эквивалентность двух программ (одинаковость результата выполнения).

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

Вот так я представлял это себе. Тогда $x$ -- это пункты 1 и 2, а $F$ -- это пункт 3.


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

[mihaild]

(Оффтоп)

Sonic86 в сообщении #1233032 писал(а):

Просьба не говорить, что жесткий диск конечен и можно все влазящие в него числа перебрать - мне это неинтересно

Ну так тема как раз про реальное железо, в которое бесконечную память не засунешь.

Tauon, если, скажем, компьютер - это машина Тьюринга с лентой размера $n$, то задача "верно ли, что данная программа на данном компьютере пустом входе выдает $0$" ($n$ задается в унарном виде) - $PSPACE$-трудна (а это очень сложно - скорее всего, гораздо сложнее чем $NP$, например).

[arseniiv]

Tauon в сообщении #1233014 писал(а):

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

Архитектуры процессоров — ни в каком математическом понимании не логики. Только в весьма переносном значении что-то там. Никакой особой теории для этого не нужно, да и если специально её рисовать, получится слишком общая, потому что процессоров человечество наизобретало к текущему моменту вагон и маленькую тележку, и потому немая. rockclimber уже упомянул про преобразование кода на одном языке в код на другом — так бинарный код для разных архитектур сюда тоже, в принципе, входит. И это преобразование ни что иное как компиляция — раньше компилировали, в основном, из языков высокого уровня в языки низкого, но теперь, в принципе, употребление этого термина шире, потому что можно, например, тестовую реализацию своего языка сделать компилирующейся в C (который отдать на откуп уже существующим компиляторам).

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