Possible to simulate a simple CPU in prolog?

Question

My understanding is that a simple model of a CPU is a state machine.

When I look at prolog, it appears to tree-search (or graph search) combinations, whilst stopping at constraints running until its goals are found.

I've been told that you can simulate a simple CPU in prolog.

Is it possible to represent a state machine model like a simple CPU in prolog?

Answer 1

Prolog is a Turing-complete language, so you can express arbitrary computations in it, including the simulation of a CPU. You can express the execution of a single instruction as a relation between two states of the CPU, one before the execution of the instruction and one after it (the instruction to be executed next is also part of the state, since it is for example available in or via one of the CPU's registers):

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

A complete execution of a program can be described declaratively as a sequence of state transitions of the CPU. Procedurally, you transform a given state until it reaches some defined final state, for example, until some register contains or points to a specific value:

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

EDIT: For example, a state of the CPU could look like the Prolog term cpu(10, 20, 0) which could be a specific state where the first register contains the value 10, the second register contains the value 20, and a third register contains the value 0. Let us assume that the third register is the instruction pointer IP, and the CPU always executes the instruction that IP points to in the machine's RAM. So we also need to include the machine's RAM in the state representation. Let us represent the machine's state as a pair RAM-CPU, with RAM being a suitable representation of the machine's RAM contents, and CPU a representation of the CPU's registers:

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

Suppose now there is an instruction add, which adds the values of the first two registers and stores the result in the first register, leaving the RAM unmodified:

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

You can describe the effects of other available instructions by additional clauses of this predicate.

Answer 2

It's entirely possible, as mat says.

It's a non-trivial problem, of course.

Yes, you could have a state machine in prolog - there are several questions about making one here on stackoverflow.

I'd suggest that while it's true a CPU is a finite state machine, it could easily be a large one - the commonly used 8051 controller has 15 bytes of registers. Since it's reasonable for rough estimate to assume any one could assume any value,

1 ?- X is 2^(15*8) | . X = 1329227995784915872903807060280344576.

states. And that's without modeling the external memory. You may have trouble finding a machine with that much memory.

Where you might find a use for state machines is in interpreting individual instructions.

So, if you're brand new to Prolog, I'd suggest a bit more learning before attempting something of this scope. I started with a game to play tic tac toe. That was about the right scope.