Take the 2-minute tour ×

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
Ok - so just for the sake of refining my mental model, if I were to use prolog to simulate a simple CPU as a set of state transitions, I'd have to define the state transitions as a graph, and then to simulate execution, I'd have to constrain all but the one path I wanted to go down. Is that what you're suggesting? –  hawkeye Nov 24 '12 at 23:08
You define the relation between states with a Prolog predicate (like cpustate0_cpustate/2 above). It contains all constraints of the state (like: what are admissible CPU register values, instructions, successive states etc.). To simulate the execution, you invoke a predicate like cpu_before_after/2 above. The predicate relates the initial state of the CPU with its state after the first, second, third etc. and final instruction is executed, yielding the final state of the CPU (if there is any - maybe the program loops). There is only one computation path if the CPU is deterministic. –  mat Nov 25 '12 at 0:08
add comment

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.

share|improve this answer
add comment

Your Answer


