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

[arseniiv]

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

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

-- Вт мар 31, 2020 22:08:27 --

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

[kotenok gav]

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

[arseniiv]

Всё потребует проверки всё равно, и насколько подъёмно, не возьмусь оценивать. Я вот теперь думаю, или путём Lua пойти, или таки я буду потом делать компиляцию в питон и пусть он сам разбирается с поиском переменных и вызовами, благо перевод на его правила поиска будет почти безболезненным, а «неаппаратный»стек я хоть и предложил, но сам я бы его реализовывать бы не стал.

[kotenok gav]

Как мне кажется, для пути Lua надо изменить совсем немного - call_stack_push/pop (чтобы они убирали/добавляли еще и аргументы), CallOp/ReturnOp (чтобы можно было вызывать/возвращать аргументы), и новую операцию (ArgOp?) для получения последних аргументов данной функции из стека.

[arseniiv]

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

[kotenok gav]

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

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

Так тут же все просто: у последней вызванной функции последние аргументы. При окончании вызова аргументы удаляются, при вызове добавляются.

[arseniiv]

Это-то ясно, главное чтобы функция не могла ничего сделать с остальной, чужой частью стека.

[kotenok gav]

Так ArgOp вернет ей только ее собственные аргументы. Она никак не сможет добраться до других.

[arseniiv]

Но регистры-то для неё отдельные от всех остальных не заведутся. Я лучше потом на примере покажу, или может как-то иначе, не знаю как лучше объяснить.

[kotenok gav]

А, в этом смысле. Понял.

[kotenok gav]

arseniiv, ну как у вас успехи с обновлением Madhine?

[arseniiv]

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

[kotenok gav]

Но мне ведь компиляцию в Madhine тоже завершить хочется(

[arseniiv]

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

[kotenok gav]

Ну как успехи у вас?