Можно ли смоделировать простой процессор в прологе?

Question

Насколько я понимаю, простая модель процессора - это конечный автомат.

Когда я смотрю на пролог, кажется, что он сочетает в себе поиск по дереву (или поиск по графику), хотя останавливается на ограничениях, работающих до тех пор, пока не будут найдены его цели.

Мне сказали, что вы можете смоделировать простой процессор в прологе.

Можно ли представить модель конечного автомата как простой процессор в прологе?

Answer 1

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

cpustate0_cpustate(State0, State) :-
      ....

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

cpu_before_after(State0, State) :-
    (    final_state(State0) -> State = State0
    ;    cpustate0_cpustate(State0, State1),
         cpu_before_after(State1, State)
    ).

РЕДАКТИРОВАТЬ: Например, состояние процессора может выглядеть как термин Пролог cpu(10, 20, 0)это может быть конкретное состояние, где первый регистр содержит значение 10, второй регистр содержит значение 20, а третий регистр содержит значение 0. Предположим, что третий регистр является указателем инструкций IP, и ЦП всегда выполняет инструкция, на которую указывает IP в оперативной памяти машины. Поэтому нам также необходимо включить оперативную память машины в представление состояния. Давайте представим состояние машины в виде пары RAM-CPU, где RAM - подходящее представление содержимого RAM машины, а CPU - представление регистров CPU:

cpustate0_cpustate(State0, State) :-
     State0 = RAM0-cpu(_,_,IP0),   
     ram_at_value(RAM0, IP0, Instruction),
     instruction_state0_state(Instruction, State0, State).

Предположим, сейчас есть инструкция add, который добавляет значения первых двух регистров и сохраняет результат в первом регистре, оставляя ОЗУ без изменений:

instruction_state0_state(add, RAM-cpu(A0,B,IP), RAM-cpu(A1,B,IP)) :-
    A1 #= A0 + B.

Вы можете описать влияние других доступных инструкций с помощью дополнительных положений этого предиката.

Answer 2

Это вполне возможно, как говорит мат.

Конечно, это нетривиальная проблема.

Да, у вас может быть конечный автомат в прологе - здесь есть несколько вопросов о создании одного из них на stackru.

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

1? - ​​Х равен 2^(15*8) |, Х = 1329227995784915872903807060280344576.

состояния. И это без моделирования внешней памяти. У вас могут возникнуть проблемы с поиском машины с таким большим объемом памяти.

Вы можете найти применение конечным автоматам в интерпретации отдельных инструкций.

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