Как назвать структурированный язык, который не может зацикливаться, или функциональный язык, который не может вернуть

Question

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

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

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

Бонусные баллы, если этот термин интуитивно понятен аудитории, которая хорошо разбирается в общих концепциях программирования, но не имеет формального фона CS.Также бонусные баллы, если есть определенный тип машины или автомата, который оценивает такой язык.О, да, имейте в виду, что мы не оцениваем поток данных - каждый элемент имеет (только для чтения) доступ ко всему набору входных данных.:)

Answer 1

Я считаю, что ваш язык достаточно мощный, чтобы точно кодировать без звезд .Это подмножество тех регулярных языков, в которых ни одно из выражений не содержит клинскую звезду.Другими словами, это язык пустой строки, нулевого набора и отдельных символов, которые закрываются при конкатенации и дизъюнкции.Это эквивалентно набору языков, принятых DFA, в которых нет направленных циклов.

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

1. Функции никогда не возвращаются.После вызова функции она никогда не вернет поток управления вызывающей стороне.
2. Все вызовы разрешаются статически (то есть вы можете посмотреть исходный код и построить график каждой функции и набора функций.это звонит).Другими словами, здесь нет никаких указателей на функции.
3. Граф вызовов является ациклическим;для любых функций A и B выполняется в точности одно из следующего: A транзитивно вызывает B, B транзитивно вызывает A, или ни A, ни B транзитивно не вызывают друг друга.
4. В более общем случае граф потока управления является ациклическим,Как только выражение вычисляется, оно никогда не вычисляется снова.Это позволяет нам обобщить вышесказанное, так что вместо того, чтобы думать о функциях, вызывающих другие функции, мы можем думать о программе как о серии операторов, которые все называют друг друга как DAG.
5. Ваш ввод - это строка, в которойкаждая буква сканируется один и только один раз, и в том порядке, в котором она дана (что представляется разумным, учитывая тот факт, что вы пытаетесь смоделировать блок-схемы).

Учитывая эти предположения, вот доказательствочто ваши программы принимают язык, если этот язык не содержит звездочек.

Чтобы доказать, что если есть язык без звездочек, есть программа на вашем языке, которая его принимает, начните с создания DFA с минимальным состоянием дляэтот язык.Языки без звезд не имеют петель и сканируют входные данные ровно один раз, поэтому будет легко создать программу на вашем языке из DFA.В частности, учитывая состояние s с набором переходов в другие состояния на основе следующего символа ввода, вы можете написать функцию, которая просматривает следующий символ ввода и затем вызывает функцию, кодирующую переходящее состояние.Поскольку DFA не имеет направленных циклов, вызовы функций не имеют направленных циклов, и поэтому каждый оператор будет выполняться ровно один раз.Теперь у нас есть это (∀ R. это язык без звезд → program программа на вашем языке, которая его принимает).

Чтобы доказать обратное направление импликации, мы, по сути, обращаем вспять эту конструкцию и создаем ε-NFA без циклов, соответствующих вашей программе.Выполнение подмножества в этом NFA для его преобразования в DFA не будет вводить никаких циклов, и поэтому у вас будет язык без звезд.Конструкция выглядит следующим образом: для каждого оператора s _i в вашей программе создайте состояние q _i с переходом в каждое из состояний, соответствующих другим операторам в вашей программе, которыеодин шаг от этого заявления.Переходы в эти состояния будут помечены символами входного сигнала, использованного для принятия каждого из решений, или ε, если переход происходит без использования какого-либо ввода.Это показывает, что (∀ программы P на вашем языке & существуют; язык без звездочек R принимает только строки, принятые вашим языком).

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

Конечно, мои предположения относительно того, что могут делать ваши программы, могут быть слишком ограниченными. У вас может быть произвольный доступ к входной последовательности, которую я думаю можно обработать с помощью модификации вышеупомянутой конструкции. Если вы потенциально можете иметь циклы выполнения, то вся эта конструкция ломается. Но, даже если я ошибаюсь, мне все равно было весело думать об этом, и спасибо за приятный вечер. : -)

Надеюсь, это поможет!

Answer 2

Я знаю, что этот вопрос несколько устарел, но для потомков фраза, которую вы ищете, это "дерево решений".Подробнее см. http://en.wikipedia.org/wiki/Decision_tree_model.Я считаю, что это точно отражает то, что вы сделали, и имеет довольно описательное имя для загрузки!