Можно ли рассматривать объектно-ориентированную программу как конечный автомат?

13

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

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

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

Если это не интерпретация FSM в проектировании объектов, что именно люди имеют в виду, когда они внедряют FSM в программном обеспечении? я что-то пропустил?

Благодарность

Перец
источник
6
Компьютер + программное обеспечение является конечным автоматом, если вы ограничиваете память, дисковое пространство и другие типы хранилищ (например, Интернет). Как только разрешено взаимодействие с Интернетом или другим внешним оборудованием (подразумевается неограниченное хранилище), это становится больше похоже на машину Тьюринга. Вы когда-нибудь слышали фразу «Тьюринг завершен»? В любом случае, функциональные и ориентированные на obj программы в конечном итоге становятся ассемблерным кодом. Я не знаю Haskel (чисто функциональный язык) / монад, но между ним и машиной Тьюринга должны быть интересные отношения.
Работа
В добавление к точке Джобса любая форма недетерминизма также превосходит как конечный автомат, так и модели Тьюринга. В Интернете у вас есть несколько несинхронизированных компьютеров, потеря данных из-за несовершенных соединений и т. Д. Даже с простым одноядерным компьютером вы получаете недетерминированный ввод от пользователя, но обычно вы игнорируете эту проблему и притворяетесь, что все вход был известен заранее.
Steve314
@ Steve314: Формально детерминированные автоматы находятся в одном состоянии. Каждый вход приводит к новому состоянию. Для недетерминированных автоматов каждый вход может привести к нескольким состояниям. Недетерминированный автомат с N состояниями может эмулировать детерминированный автомат с 2 ^ N состояниями.
Кевин Клайн
@cline - В этом случае вы абсолютно правы, но я думаю, что я имел в виду разновидность параллелизма и изменения времени, которые происходят в реальной машине - такие вещи, как ядро ​​работает немного медленнее, потому что он слишком горячий точное время, когда данные оказываются под головкой чтения и т. д. Все это вписывается в недетерминированную модель конечных автоматов, которую вы описываете, конечно, так что вы абсолютно правы - но число состояний будет безумно огромным. Я думаю, что я мог иметь в виду непрерывные измерения, такие как эти температуры, как часть состояния системы (а не только последствия).
Steve314

Ответы:

16

Любая однопоточная программа, работающая на компьютере с ограниченным объемом памяти, может быть смоделирована как конечный автомат. Конкретное состояние конечного автомата будет представлять конкретные значения всех соответствующих хранилищ - локальные переменные, глобальные переменные, динамическое хранилище, данные, в настоящее время выгруженные в виртуальную память, даже содержимое соответствующих файлов. Другими словами, в этой модели конечных состояний будет много состояний, даже для довольно тривиальных программ.

Даже если единственное состояние, в котором находится ваша программа, - это одна глобальная переменная с 32-разрядным целочисленным типом, что подразумевает не менее 2 ^ 32 (более 4 миллиардов) состояний. И это даже не принимая во внимание счетчик программ и стек вызовов.

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

Есть объяснение в Википедии , но не увязайте в разделе формального определения.

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

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

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

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

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

Можно моделировать один объект ООП как конечный автомат. Состояние машины будет определяться состояниями всех переменных-членов. Как правило, вы будете считать только допустимые состояния между (не во время) вызовами методов. Опять же, вам, как правило, придется беспокоиться о многих состояниях - это то, что вы можете использовать в качестве теоретической модели, но вы не захотите перечислять все эти состояния, за исключением, может быть, тривиального случая.

Тем не менее, довольно часто моделируется некоторый аспект состояния объекта с использованием конечного автомата. Распространенным случаем является ИИ для игровых объектов.

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

Steve314
источник
1
«Можно моделировать один объект ООП как конечный автомат». Правда, но слабый. Это невозможно". Это вопрос определения. Работа языка программирования состоит в том, чтобы выразить FSM в аккуратной нотации. ООП - это реализация FSM с более простой системой обозначений для всех различных состояний.
С.Лотт
1
@ S.Lott - Да, но большинство людей не считают объект ООП выражением FSM, по крайней мере, в большинстве случаев. Использование имени «конечный автомат» имеет тенденцию подразумевать, что вы используете какую-то конкретную реализацию, такую ​​как шаблон проектирования состояний или переменная члена-идентификатора состояния. «Моделирование как конечный автомат» часто также подразумевает что-то в спецификации или проектной документации, отличное от реализации этого класса. Следовательно, моделирование класса как модели конечного состояния субъективно означает нечто иное, чем просто предоставление исходного кода для класса.
Steve314
«люди не думают». Правда. И глубокая проблема. Все программы являются конечными автоматами. У них много состояний. Это то, что требуется для теста Turing Complete для языка программирования. Это очень, очень сильное (и абсолютное) правило. Вместо того, чтобы предполагать, что это «возможно», это больше похоже на «необходимо» и «достаточно».
С.Лотт
1
-1: Автоматы с пуш-ап не настолько мощные, как машины Тьюринга.
Кевин Клайн
1
@kevin cline - спасибо - и о чем я думал !!! Отредактировано, чтобы вычеркнуть это. Несмотря на то, что я сказал о формальном обучении, я знаю лучше, и тогда должен был знать лучше.
Steve314
5

Вопрос не в том, является ли нечто «конечным» или «не» конечным автоматом. Конечный автомат - это ментальная модель, которая может быть полезна для понимания чего-либо, если эту вещь можно представить как единое целое.

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

Майк Данлавей
источник
1

Чтобы ответить на ваш вопрос напрямую: почти наверняка нет. Похоже, что для ООП не существует формальной математической теории, в которой лямбда-исчисление и / или комбинаторная логика лежат в основе функционального программирования, или машины Тьюринга лежат в основе обычного старого императивного программирования.

Видеть этот вопрос stackoverflow для получения дополнительной информации.

Я предполагаю, что отсутствие основной математической теории - это то, почему все знают, что такое «объект», когда они его видят, но никто не видит «объекты» так же, как кто-либо еще.

Брюс Эдигер
источник
0

Нет, практически нет. Конечный автомат обычно запоминает только один фрагмент данных: его текущее состояние.

Типичное применение FSM - это лексирование или разбор. Например, когда мы выполняем лексические операции, (обычно) довольно легко кодировать действия для каждого возможного ввода с точки зрения текущего состояния и значения ввода.

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

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

Сам FSM имеет некоторые ограничения - у него нет механизма подсчета. Рассмотрим, например, язык, который использует «/ » для начала комментария и « /» для завершения комментария. Его лексер, вероятно, имел бы состояние COMMENT, в которое он вошел, когда увидел токен '/ '. На этом этапе он не может (кроме добавления другого состояния, такого как COMMENT2) обнаружить другое "/ " и понять, что имеет дело с вложенным комментарием. Скорее, в состоянии комментария он распознает */как выход из состояния комментария, а все остальное оставляет его в состоянии комментария.

Как уже упоминалось, вы, конечно, могли включить состояние COMMENT2 для вложенного комментария - и в этом состояние COMMENT3 и так далее. Однако в какой-то момент вам надоест добавлять новые состояния, и это будет определять максимальную глубину вложения, которую вы допускаете для комментариев. С какой-то другой формой синтаксического анализатора (то есть, не с помощью конечного автомата, а с чем-то, что имеет некоторую память для подсчета), вы можете просто отслеживать глубину вложенности напрямую, поэтому вы остаетесь в состоянии COMMENT до тех пор, пока не достигнете жетона близких комментариев, балансирует первый, поэтому ваш счетчик возвращается к 0, и вы выходите из состояния COMMENT.

Однако, как я уже сказал, когда вы добавляете счетчик таким образом, то, что у вас есть, больше не является настоящим ФСМ. В то же время он на самом деле довольно близок - в частности, достаточно близко, чтобы вы могли смоделировать счетчик, просто добавив больше состояний.

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

Джерри Гроб
источник
«его текущее состояние» может включать в себя большое количество информации. FSM может легко подсчитать, имея состояния для каждого числа, которое он будет считать. Это конечно (в отличие от машины Тьюринга), но все равно прекрасно умеет считать. Я думаю, вам может понадобиться лучший пример.
С.Лотт
Программное обеспечение в вашем мобильном телефоне представляет собой набор ужасно сложных конечных автоматов, которые запоминают многие данные и интерпретируют их в соответствии с текущим состоянием.
Mawg говорит восстановить Монику
-2

Я не верю, что принятый ответ является полностью правильным.

Вы не можете моделировать произвольную программу, написанную на языке Turing Complete, независимо от того, является ли она объектно-ориентированной или нет, как конечный автомат. Почти все современные компьютерные языки, такие как Java, C ++ или Smalltalk, являются Turing Complete.

Например, вы не можете создать конечный автомат для распознавания последовательности объектов, где у вас есть n экземпляров одного объекта, за которыми следуют n экземпляров другого объекта, потому что конечные автоматы неспособны записать n в переменную. Они могут только читать ввод и переключаться в состояние.

Джеймс Фремен
источник
это просто повторяет высказанные замечания и объяснения в ответах, опубликованных 3 года назад, например, в этом
комнат