Тьюринг-полон ли данный язык

[kotenok gav]

Ага, кажется, понял. Т.е., будут операции PutOp и PopOp, которые будут вытаскивать и класть аргументы/результаты из стека, причём, скажем, чтобы вызвать функцию, надо вызвать PutOp на аргументах функции, и затем PopOp в самой функции, а чтобы вернуть результаты, надо вызвать PutOp в функции, и затем PopOp после её выполнения? Ну тогда в Madhine надо всего лишь добавить стек (просто массив) и эти две операции (просто добавить/вытащить последний элемент стека)...

[arseniiv]

Ага. Я бы эти операции назвал как-нибудь типа «arg» и «res», но это для вызывающей функции они такие, а для вызываемой наоборот, так что да, что-нибудь стандартное типа push/pop.

[kotenok gav]

Хорошо, тогда допишу компилятор с учётом этого (что есть дополнительные операции PutOp и PushOp (и нет CallOp и ReturnOp)).

(Оффтоп)

Кстати, мне тут пришла в голову одна идея, которая, в каком-то смысле, даже более эзотерическая По сути, это даже две идеи: разработать некий способ описания конструкции компьютера (и IDE, в котором можно это делать (можно даже взять это из MHRD)) (это не такая эзотерическая идея, она даже вполне практическая) и создать алгоритм автоматической реализации конструкции в Wireworld и Minecraft (это уже более эзотерическая идея ).

[kotenok gav]

Синтаксис этих операций должен быть примерно такой: PushOp(следующий_адрес, массив аргументов) (просто кладёт в стек массив вида [аргумент_1, аргумент_2, ...] (если это вызов функции, то первым аргументом идёт адрес, куда вернуться)) и PopOp(следующий_адрес, массив регистров) (достаёт массив из стека и перемещает аргументы в соответствующие регистры). всё, пойду дописывать компилятор

-- 20 окт 2020, 00:58 --

Хм, скажем, а как остановить программу (точнее, main), если последней строчкой она вызовет другую функцию? У меня остановка реализована примерно так:

Используется синтаксис Python

if name == "main":
    last_register = max(func.code.keys())
    if type(func.code[last_register]).__name__ != 'JumpOp':
        func.code[last_register].next = None
    else:
        func.code[last_register].next_when_empty = \
            None if func.code[last_register].next_when_empty > last_register
        func.code[last_register].next_when_inhabited = \
            None if func.code[last_register].next_when_inhabited > last_register

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

-- 20 окт 2020, 01:18 --

И та же самая проблема происходит и в самих функциях! Когда компилятор пытается изменить адрес, куда пойдёт последняя операция функции (чтобы функция вернулась куда надо), может произойти это же...
Ладно, я, кажется, придумал, как это исправить.

-- 20 окт 2020, 01:33 --

kotenok gav в сообщении #1487934 писал(а):

если это вызов функции, то первым аргументом идёт адрес, куда вернуться

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

-- 20 окт 2020, 01:34 --

А как тогда это (ну, куда передавать адрес возврата?) реализовать?

[kotenok gav]

Ладно, похоже, что без ReturnOp не обойтись (CallOp всё же не нужна).

-- 20 окт 2020, 22:27 --

(ReturnOp при вызове берёт (в качестве адреса, т.е. сам ReturnOp аргументов не принимает) первый (и единственный) элемент последнего элемента стека (и удаляет последний элемент), PopOp возвращает весь последний элемент, но удаляет из него все элементы, кроме первого)

-- 20 окт 2020, 22:35 --

(Причём, кстати, PushOp должен класть не сами аргументы, а адреса, по которым те находятся)

-- 20 окт 2020, 23:02 --

Хм, я придумал поистине гениальное упрощение для изменения адреса Достаточно просто добавить пустую операцию в конец main.

-- 20 окт 2020, 23:08 --

Загрузил новую версию компилятора. Ща примерно набросаю исправление для Madhine, и завтра буду тестить.

[kotenok gav]

(Старое сообщение)

Хм.. Давайте всё же лучше вы его (ну, исправление Madhine) сделаете Вот подробное описание этих трёх операций:
PushOp(следующее_состояние, массив аргументов) (аргументы могут быть регистрами или состояниями): просто кладёт массив в стек (выдаёт исключение, если стек полон).
PopOp(следующее_состояние, массив регистров): вытаскивает все элементы (и удаляет все, кроме первого! реализуется так: last_element = stack.pop(), stack.push([last_element[0]])) из последнего массива в стеке, копирует аргументы, находящиеся в регистрах-элементах в регистры-из массива регистров, выдаёт исключение, если кол-во элементов не совпадает.
ReturnOp(): перемещает текущее состояние на состояние, находящееся в единственном элементе последнего массива стека (выдаёт исключение, если элемент не едиственный или стек пуст), удаляет последний массив из стека.

Написал сообщение и заметил проблему: если мы вызвали PopOp в другой функции (чтобы получить результат той, которую мы вызвали), то мы не получим результат... А если сделать, чтобы первый элемент массива в PushOp был состоянием (чтобы решить эту проблему), возникнет проблема с ReturnOp и PopOp: когда функция попытается вернуть результат, она сначала вызовет ReturnOp, и он вызовет исключение. Что делать?

[arseniiv]

kotenok gav в сообщении #1487867 писал(а):

По сути, это даже две идеи: разработать некий способ описания конструкции компьютера (и IDE, в котором можно это делать (можно даже взять это из MHRD)) (это не такая эзотерическая идея, она даже вполне практическая) и создать алгоритм автоматической реализации конструкции в Wireworld и Minecraft (это уже более эзотерическая идея ).

О, о, ну вы и неподъёмную (но интересную) задачу придумали!

Насчёт языка для описания конструкции возможно будут чем-то полезны языки типа VHDL, но я их не изучал. Этот язык насколько я помню более высокоуровневый и описывает больше преобразования сигналов, чем соединения конкретных элементов, и на таком скорее и больше захочется писать, а более конкретное представление получать уже как часть компиляции. А потом докомпилировать в совсем уж конкретные элементы — для майнкрафта конкретные блоки и для Wireworld отдельные клетки vs. некие абстрактные «это-то идёт оттуда туда». Впрочем вместо умножения разных видов представлений можно просто аннотировать самое первое высокоуровневое постепенно всё больше и больше, а потом отрезать всё лишнее и получить низкоуровневое на уровне расположения блоков.

Для того, чтобы определиться с самим высокоуровневым описанием, может наверно быть полезным вопрос, позволять ли данные неограниченной во время выполнения длины (как int в питоне) или нет, и если нет, давать ли определять данные неограниченной, но известной до выполнения длины (хочу — выбираю int32, а хочу — int10005000). Если не допускать первого, преобразования должны будут довольно упроститься, а если и второго, то может ещё капельку, хотя то уже наверно перебор.

-- Сб окт 24, 2020 03:49:39 --

kotenok gav в сообщении #1487934 писал(а):

Синтаксис этих операций должен быть примерно такой: PushOp(следующий_адрес, массив аргументов) (просто кладёт в стек массив вида [аргумент_1, аргумент_2, ...] (если это вызов функции, то первым аргументом идёт адрес, куда вернуться)) и PopOp(следующий_адрес, массив регистров) (достаёт массив из стека и перемещает аргументы в соответствующие регистры).

Исходно я думал, что будет браться по одному регистру за раз, но раз мы не особо ограничены в абстрактном представлении машины, то так наверно к лучшему!

kotenok gav в сообщении #1488087 писал(а):

Ладно, похоже, что без ReturnOp не обойтись (CallOp всё же не нужна).

Да я бы их обе оставил. Не очень понял как вы сэкономили на CallOp, надо будет перечитать…

Ммм… мне по-моему проще будет расписать, что я думал насчёт архитектуры, чем разобраться, что надо менять здесь, потому что я пропустил кучу изменений и в них долго разбираться. Должно было быть так:
• Итого у нас есть стек данных, хранящий просто значения: HFSet, и стек вызовов, который хранит кортежи (адрес возврата: State, локальные регистры: Dict[Register, HFSet]).
• Функция обращается всегда к своим локальным регистрам, смотря их в стек вызовов (и если вводить глобальные переменные, они будут смотреться в регистрах самой машины).
• ReturnOp() запоминает адрес возврата сверху стека вызовов, выкидывает верх этого стека и устанавливает следующим состоянием запомненный адрес. (А если стек пустой, как и раньше исключение.)
• CallOp(cs, rs) добавляет в стек вызовов кортеж (rs, пустой словарь) и ставит следующим состоянием cs.
• В самом начале выполнения машины мы как бы (да или так прямо и делаем) выполняем CallOp(начало главной функции, None). И когда главная функция выполнит ReturnOp(), следующим состоянием окажется None, машина станет его выполнять и благополучно завершится. Если главная функция не забыла свои результаты положить в стек данных, машине будет откуда их забрать. А, ну и конечно пусть она перед вызовом главной функции так же положит ей в стек данных аргументы.

Кажется, согласованно, проверяйте.

[kotenok gav]

arseniiv в сообщении #1488774 писал(а):

Не очень понял как вы сэкономили на CallOp, надо будет перечитать…

CallOp - это просто PushOp с переходом в начало нужной функции.

arseniiv в сообщении #1488774 писал(а):

Итого у нас есть стек данных, хранящий просто значения: HFSet, и стек вызовов, который хранит кортежи (адрес возврата: State, локальные регистры: Dict[Register, HFSet]).
• Функция обращается всегда к своим локальным регистрам, смотря их в стек вызовов (и если вводить глобальные переменные, они будут смотреться в регистрах самой машины).
• ReturnOp() запоминает адрес возврата сверху стека вызовов, выкидывает верх этого стека и устанавливает следующим состоянием запомненный адрес. (А если стек пустой, как и раньше исключение.)
• CallOp(cs, rs) добавляет в стек вызовов кортеж (rs, пустой словарь) и ставит следующим состоянием cs.
• В самом начале выполнения машины мы как бы (да или так прямо и делаем) выполняем CallOp(начало главной функции, None). И когда главная функция выполнит ReturnOp(), следующим состоянием окажется None, машина станет его выполнять и благополучно завершится. Если главная функция не забыла свои результаты положить в стек данных, машине будет откуда их забрать. А, ну и конечно пусть она перед вызовом главной функции так же положит ей в стек данных аргументы.

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

[kotenok gav]

arseniiv в сообщении #1488774 писал(а):

Ммм… мне по-моему проще будет расписать, что я думал насчёт архитектуры, чем разобраться, что надо менять здесь, потому что я пропустил кучу изменений и в них долго разбираться. Должно было быть так:
• Итого у нас есть стек данных, хранящий просто значения: HFSet, и стек вызовов, который хранит кортежи (адрес возврата: State, локальные регистры: Dict[Register, HFSet]).
• Функция обращается всегда к своим локальным регистрам, смотря их в стек вызовов (и если вводить глобальные переменные, они будут смотреться в регистрах самой машины).
• ReturnOp() запоминает адрес возврата сверху стека вызовов, выкидывает верх этого стека и устанавливает следующим состоянием запомненный адрес. (А если стек пустой, как и раньше исключение.)
• CallOp(cs, rs) добавляет в стек вызовов кортеж (rs, пустой словарь) и ставит следующим состоянием cs.
• В самом начале выполнения машины мы как бы (да или так прямо и делаем) выполняем CallOp(начало главной функции, None). И когда главная функция выполнит ReturnOp(), следующим состоянием окажется None, машина станет его выполнять и благополучно завершится. Если главная функция не забыла свои результаты положить в стек данных, машине будет откуда их забрать. А, ну и конечно пусть она перед вызовом главной функции так же положит ей в стек данных аргументы.

Я вот сейчас подумал снова, и у меня получается как-то так (по поводу последнего пункта ничего не пишу - насчёт него не уверен):

1) Есть стек данных (который хранит кортежи множеств) и стек вызовов (который хранит адреса).
2) PushOp принимает адрес (куда потом прыгнет функция после ReturnOp) и кортеж регистров, добавляет адрес в стек вызовов, и добавляет кортеж множеств, находящихся в переданных регистрах (не сами регистры!!!) в стек данных.
3) PullOp принимает кортеж регистров (и, конечно же, следующий адрес для выполнения), куда выгружает последний кортеж множеств из стека данных. Если их размеры не совпадают, возвращается ошибка.
4) ReturnOp принимает кортеж регистров (возможно, пустой), добавляет кортеж множеств, находящихся по этим регистрам в стек данных, получает последний адрес из стека вызовов, и прыгает туда. Потом функция, вызвавшая эту функцию, должна получить результаты (возможно, пустой кортеж), вызвав PullOp.

Вроде бы так всё должно работать.

[kotenok gav]

О, а ещё так открывается возможность возвращения функцией несколько результатов и, в частности, деструктурирующего присваивания. Так можно делать даже вложенные функции! Т.е. как-то так:

func1() {
    return [], [[]], [[], [[]]];
}

func2(a, b, c) {
    return (a + b) + c;
}

func2(func1());