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

[arseniiv]

Да как-то не очень, то времени нет, то желания нет. Что-нибудь будет, я пока пытаюсь несколько дней другую штуку довести до ума, но ни одной буквы туда так за три дня и не дописал. Надо чуть-чуть переждать…

[kotenok gav]

А как сейчас?

[arseniiv]

И сейчас пока никак(

[kotenok gav]

А сейчас?

[arseniiv]

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

[kotenok gav]

Я немного подредактировал парсер (в том числе я частично добавил в него и __repr__, но оно выглядит довольно плохо) и компилятор. В принципе, они практически рабочи, если не считать вещей, связанных с вызовом функций. Я пока решил составить список недостатков текущей версии (назовём её S1 v0.9, до S1 v1.0 осталось лишь то дополнение Madhine, а в S1 v2.0 я уже поправлю недостатки):

• Отсутствие возможности импорта файлов.
• Отсутствие IO (добавлю в S1 v1.0, это несложно).
• Невозможность вложенных функций.
• Отсутствие возможности не писать фигурные скобки (для условных выражений/циклов), если код внутри них состоит из одной строчки (как в JS) (может, и не буду это добавлять).
• Отсутствие конца программы (программа переходит на регистр без операции вместо перехода на None) (поправлю в S1 v1.0, это просто).
• Отсутствие операторов +=, -=, *=, ~=.
• Отсутствие assert.
• Отсутствие библиотек работы с числами, графами, строками, etc.
• бесконечные множества!! (не раньше S1 v3.0)

Ссылка на репозиторий с S1 v0.9: https://github.com/LeviPesin/S1-compiler

[arseniiv]

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

[kotenok gav]

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

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

А как у вас успехи с тем "функциональным" дополнением Madhine?

-- 17 окт 2020, 03:58 --

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

• Отсутствие возможности импорта файлов.
• Отсутствие IO (добавлю в S1 v1.0, это несложно).
• Невозможность вложенных функций.
• Отсутствие возможности не писать фигурные скобки (для условных выражений/циклов), если код внутри них состоит из одной строчки (как в JS) (может, и не буду это добавлять).
• Отсутствие конца программы (программа переходит на регистр без операции вместо перехода на None) (поправлю в S1 v1.0, это просто).
• Отсутствие операторов +=, -=, *=, ~=.
• Отсутствие assert.
• Отсутствие библиотек работы с числами, графами, строками, etc.
• бесконечные множества!! (не раньше S1 v3.0)

Ой, я забыл еще недостаток - отсутствие else и elife/elifne.

[arseniiv]

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

А как у вас успехи с тем "функциональным" дополнением Madhine?

Я тогда когда немного покрутил его, понял, что проще будет компилировать сразу в питон (используя ast). Машину, которую можно легко запустить по шагам и трансформировать как угодно, конечно иметь приятно, но машина того типа вышла очень плохорасширяемой. Может быть можно начать с нуля и сделать функциональную, но пока я не выделю времени на это — много разностей надо бы поделать, включая аккуратный переход системы на Win10 с как можно меньшими проблемами (собирался уже сто лет, но как раз выход на днях Python 3.9 стал той самой последней соломинкой).

-- Сб окт 17, 2020 23:43:44 --

(Оффтоп)

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

Насколько та или иная шкала интервалов годится для музыки, немало зависит от тембра инструмента, которым предполагается на ней играть. Пифагорейская теория небольших рациональных чисел как хорошо звучащих интервалов в основном подкрепляется тем, что у многих известных нам инструментов «гармонический тембр» (неудачный термин) с отношениями гармоник к основной $1, 2, 3, 4, 5, \ldots$ Инструменты с достаточно сильно негармоническим тембром могут делать другой набор интервалов консонантными, и таким образом это связано с альтернативной настройкой и микротональностью.

Тут как раз удобным оказывается Jupyter notebook, чтобы прям на месте проигрывать звуки, сгенерированные кодом. Но пока мало написал, чтобы показывать. Гармонический тембр уже можно послушать, но не те, которые меня как раз интересовали, где гармоники соотносятся с основной частотой как $m\varphi + n$ (для лишь аккуратно выбранных $(m, n)$, перечисление которых я как раз не успел пока написать; $\varphi$ — золотое сечение), и также у меня в планах послушать несколько тембров, сконструированных для других целей, и попробовать ещё как-то собрать тембр с гармониками, относящимися к основной частоте как $1/n$, но притом не перехватывающих для нашего уха роль основной частоты, так что их амплитуды нужно будет сделать достаточно маленькими, и не факт что что-то получится, но если получится, то это должно быть связано с интересной темой под именем negative harmony, и опять же интересно как это будет для уха.

[kotenok gav]

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

Я тогда когда немного покрутил его, понял, что проще будет компилировать сразу в питон (используя ast).

Код для Madhine компилировать или код на S1 (ну, лучше первое)?

(Оффтоп)

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

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

Насколько та или иная шкала интервалов годится для музыки, немало зависит от тембра инструмента, которым предполагается на ней играть. Пифагорейская теория небольших рациональных чисел как хорошо звучащих интервалов в основном подкрепляется тем, что у многих известных нам инструментов «гармонический тембр» (неудачный термин) с отношениями гармоник к основной $1, 2, 3, 4, 5, \ldots$ Инструменты с достаточно сильно негармоническим тембром могут делать другой набор интервалов консонантными, и таким образом это связано с альтернативной настройкой и микротональностью.

Тут как раз удобным оказывается Jupyter notebook, чтобы прям на месте проигрывать звуки, сгенерированные кодом. Но пока мало написал, чтобы показывать. Гармонический тембр уже можно послушать, но не те, которые меня как раз интересовали, где гармоники соотносятся с основной частотой как $m\varphi + n$ (для лишь аккуратно выбранных $(m, n)$, перечисление которых я как раз не успел пока написать; $\varphi$ — золотое сечение), и также у меня в планах послушать несколько тембров, сконструированных для других целей, и попробовать ещё как-то собрать тембр с гармониками, относящимися к основной частоте как $1/n$, но притом не перехватывающих для нашего уха роль основной частоты, так что их амплитуды нужно будет сделать достаточно маленькими, и не факт что что-то получится, но если получится, то это должно быть связано с интересной темой под именем negative harmony, и опять же интересно как это будет для уха.

Звучит интересно, но, честно говоря, не очень понятно

[arseniiv]

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

Код для Madhine компилировать или код на S1 (ну, лучше первое)?

Сразу код для S1, раз подходящего варианта машины для функций нет.

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

Звучит интересно, но, честно говоря, не очень понятно

Да, так и задумывалось это скорее аннотация была.

[kotenok gav]

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

Сразу код для S1, раз подходящего варианта машины для функций нет.

Но вариант предварительной компиляции S1 для Madhine, скажем, позволяет попытаться построить аппаратную реализацию Madhine для быстрой работы на ней S1, а еще мне просто хочется дописать компилятор...

[arseniiv]

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

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

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

Тут можно заметить, что этот «стек данных» используется очень консервативно: он почти всегда пустой, в нём ничего не лежит долго в ожидании вдали от вызовов и возвратов. И у этого опять следствие, что мы должны запретить рекурсию, и явную и неявную (f вызывает g вызывает h вызывает f), потому что на одну функцию у нас лишь один набор регистров.

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

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

[kotenok gav]

Ну, у меня в компиляторе уже есть разделение на функции (обычные и генерирующуюся компилятором из остатка функцию main), и там уже частично реализован доступ к переменным не этой функции (если точнее, то в случае, если компилятор не находит переменную, он ищет её в main). ИМХО, изменение переменных функций, вызывающих эту (типа того, что реализуется в Python с помощью "global") - не такая уж и важная пока вещь.

[arseniiv]

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