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

[arseniiv]

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

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

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

Может, для решения 2 ввести какую-нибудь операцию RetOp, которая бы возвращалась к вызвавшей данную функцию функции?

Ага, да, этого не хватает в машине. Щас я ещё немного посмотрю тут и машину обновлю. Будут две операции, ещё и CallOp для вызова, чтобы в стек вызовов помещалось состояние, в которое вернуться, ну и RetOp будет его оттуда брать и туда идти.

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

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

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

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

Тут не понял.

Это я про то, что если определить statement: block | assign SEMICOL | expr SEMICOL, то функции ровно так же можно будет вызывать как оператор, но притом мы немного экономим в парсере. (Но тогда же можно будет писать и штуки типа [] + []; return x;, где выражение вычисляется впустую. Это не особая проблема, но и её потом тоже можно будет устранить предупреждениями при компиляции.)

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

Зачем комментариям удаляться в лексере? У меня ща они удаляются в парсере.

Но нельзя будет поставить комментарий например так: x = /* ... */ y; а вдруг я хочу.

[kotenok gav]

А что по поводу этого?:

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

Как, например, заставить функцию не вызываться без вызова ее?

-- 31 мар 2020, 01:29 --

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

Это я про то, что если определить statement: block | assign SEMICOL | expr SEMICOL, то функции ровно так же можно будет вызывать как оператор, но притом мы немного экономим в парсере. (Но тогда же можно будет писать и штуки типа [] + []; return x;, где выражение вычисляется впустую. Это не особая проблема, но и её потом тоже можно будет устранить предупреждениями при компиляции.)

Т.е. нагрузка снимается с парсера и переносится на еще ненаписанный компилятор? Не, это не очень.

-- 31 мар 2020, 01:31 --

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

Можно посчитать, что весь код завёрнут в одну большущую функцию

Это я делаю, да. Но проблема в локальных переменных, мы не понимаем, в какой они функции.

-- 31 мар 2020, 01:37 --

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

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

Это я тоже хотел сначала сделать, но потом передумал в пользу системы из той серии статей.

[arseniiv]

Кстати, что предполагалось вводить с помощью операции ввода? Если ввели натуральное число, закодировать его как множество? (И например ещё прибавить 1, чтобы можно было вернуть [], если ввели не число.)

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

А что по поводу этого?:

А, ну я не очень понял эту часть, можно пример?

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

Это я делаю, да. Но проблема в локальных переменных, мы не понимаем, в какой они функции.

Я бы проходил по всем переменным, упомянутым в теле функции, но притом не являющимися переменными, которые видны на месте её определения извне, и добавлял их в её локальные, плюс её аргументы. Можно сделать, чтобы локальные переменные объявлялись специально, типа var v1, v2, v3; в самом начале кода функции, и тогда локальные переменные функции — это ровно её аргументы и так объявленные имена, а всё остальное должно браться снаружи (и если какая-то переменная там отсутствует, выдать ошибку). Такое объявление позволит явно сказать, если мы хотим свою переменную с тем же именем, что есть вне, но внешняя в данной функции не интересна. Наконец можно вместо такого фиксированного var объявлять локальные переменные при присваивании, пиша let v = ...; в любом месте. Но тогда стоит будет проверять и то, не используются ли имена раньше объявления, и наконец если вне есть уже другая v, логически во всех местах до let v = ... должна вместо своей локальной использоваться она. Короче var в начале тела функции пока выглядит самым простым решением, а потом можно будет улучшать.

[kotenok gav]

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

Кстати, что предполагалось вводить с помощью операции ввода?

Множства вводить.

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

А, ну я не очень понял эту часть, можно пример?

Пример, скажем, мы хотим сделать функцию, выводящую [num]. Тогда, если мы, скажем, сделаем код 0: num, 1: something, 2: ClearOp(1), 3: AddOp(0,1), то, когда мы начнем исполнять код программы, функция непроизвольно выполнится. Можно, правда, попробовать начинать исполнение машины на строке после объявлений функций...

-- 31 мар 2020, 02:14 --

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

Я бы проходил по всем переменным, упомянутым в теле функции, но притом не являющимися переменными, которые видны на месте её определения извне, и добавлял их в её локальные, плюс её аргументы. Можно сделать, чтобы локальные переменные объявлялись специально, типа var v1, v2, v3; в самом начале кода функции, и тогда локальные переменные функции — это ровно её аргументы и так объявленные имена, а всё остальное должно браться снаружи (и если какая-то переменная там отсутствует, выдать ошибку). Такое объявление позволит явно сказать, если мы хотим свою переменную с тем же именем, что есть вне, но внешняя в данной функции не интересна. Наконец можно вместо такого фиксированного var объявлять локальные переменные при присваивании, пиша let v = ...; в любом месте. Но тогда стоит будет проверять и то, не используются ли имена раньше объявления, и наконец если вне есть уже другая v, логически во всех местах до let v = ... должна вместо своей локальной использоваться она. Короче var в начале тела функции пока выглядит самым простым решением, а потом можно будет улучшать.

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

[arseniiv]

Обновлённая функциональными командами мадшина теперь всё по тому же адресу.

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

Множства вводить.

А. Хм, логично, но я не додумался. Ну ладно, это в следующий раз скорее. Я даже не буду копировать парсер, а команда ввода бы просто принимала функцию, которая по строке выдаёт или множество, или None, и в машине регистру присваивает или пустое, если None, или [результат] — так можно будет узнать из программы, ввели что-то корректное или нет. Для вывода тогда будет две команды — выводящая сохранённую в себе строку (аналогично AssertOp) и выводящая множество из регистра.

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

Пример, скажем, мы хотим сделать функцию, выводящую [num]. Тогда, если мы, скажем, сделаем код 0: num, 1: something, 2: ClearOp(1), 3: AddOp(0,1), то, когда мы начнем исполнять код программы, функция непроизвольно выполнится. Можно, правда, попробовать начинать исполнение машины на строке после объявлений функций...

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

[kotenok gav]

Тогда нужно завести операцию HaltOp. А main можно создавать на уровне компилятора...

[arseniiv]

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

[kotenok gav]

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

достаточно переходить в None вместо какого-то существующего состояния

А, тогда хорошо.

[kotenok gav]

Кстати, в CallOp надо добавить аргументы, с которыми будет вызываться функция. Они должны перезаписывать ее первые регистры, скажем.

-- 31 мар 2020, 20:15 --

Ща один баг в парсере поправлю...

-- 31 мар 2020, 20:47 --

Парсер что-то комментарии не обрабатывает... Но это не к спеху чинить.

-- 31 мар 2020, 20:47 --

Не обрабатывает - в смысле, ошибку выдает.

[kotenok gav]

А, только что понял (потому что дошел до этого места в компиляторе): еще надо добавить ReturnOp возможность возвращать аргумент.

[kotenok gav]

Написал компилятор полностью, кроме вещей связанных с FuncCall.

[arseniiv]

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

Кстати, в CallOp надо добавить аргументы, с которыми будет вызываться функция. Они должны перезаписывать ее первые регистры, скажем.

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

А, только что понял (потому что дошел до этого места в компиляторе): еще надо добавить ReturnOp возможность возвращать аргумент.

Не обязательно. Можно загрузить значения до вызова и взять возвращённое после, притом выбрав те регистры, которые удобны.

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

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

Короче если я на днях попробую свою версию, я лучше наверно буду компилировать в питон.

-- Вт мар 31, 2020 19:07:50 --

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

[kotenok gav]

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

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

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

Но проще, кмк, сделать то, что я предложил.

[arseniiv]

Оно не спасёт от проблем с рекурсией.

[kotenok gav]

Хм, да. А как в обычных машинах такое реализовано?