Using dynamic facts to simulate a "stack" in Prolog

Question

So basically I am trying to simulate asm code using Prolog.

With the help of @mbratch , I know it is straightforward and easy to use dynamic facts to simulate instructions like

add eax, 1
mov eax, 1

in this way:

:- dynamic(register/2).  % Fill in as needed

register(eax, 0).
....
add(Reg, Value) :-
(   retract(register(Reg, OldValue))
 ->   NewValue is OldValue + Value
),
assertz(register(Reg, NewValue)).

But the problem is that how to simulate the stack in a similar way...?

Originally I wrote some quite FP style code like this:

nth_member(1, [M|_], M).
nth_member(N, [_|T], M) :- N>1, N1 is N - 1, nth_member(N1, T, M).
.....
% push  ebp
ESP is ESP - 1, nth_member(ESP, STACK, EBP),
....

But the problem is I don't know how to rewrite this code in a dynamic facts style...

Could anyone give me some help..? Thank you!

Answer 1

The Prolog canon says, don't use dynamic facts for state unless you have a really good reason. In other words, if you want to model a stack, maintain it as a term that you mutate and pass to the next step of a recursive predicate that takes as arguments the state. For example (very simplified),

step(Current_stack, Final_stack) :-
    read_next_instruction(Instruction/*, whatever other arguments you need */),
    apply_instruction(Current_stack, Instruction, New_stack),
    step(New_stack, Final_stack).

The second argument, Final_stack, is there if you want to have the final stack after getting through all instructions in the code you are simulating. It will probably be a free variable at the beginning of the simulation, or, if you want to validate, the expected final state.

The stack itself would be either a list (if you only need the top of the stack), or a more complex, possibly nested term. You most probably would want to maintain all registers in this way too (as shown in my other answer).

There is another option, using proper mutable global variables. Depending on the Prolog implementation you use, this will involve different built-ins. For SWI-Prolog, look here; for GNU-Prolog, here. Other implementations will probably have predicates along the same lines as well.

The main point here is that using assert and retract for maintaining state that changes frequently makes your program very difficult to understand, and very inefficient. The "pure" Prolog solution is the first suggestion; using global variables can be more efficient in some cases.

PS:

As a full example of how to use a stack, see this answer to a question about a stack-based calculator (shameless self-promotion): Postfix expression list evaluation

And to expand on the "don't use dynamic predicates", they definitely have their use. A good example of when this is a good solution is if you are implementing a relational database. Then, your tables are implemented as facts, with one clause per column:

name_age('Bob', 20).
name_age('Jane', 23).
% etc

name_occupation('Bob', student).
name_occupation('Jane', teacher).
% etc

Here, you can use asserts to add new rows to your tables, or retracts to remove rows. The main point is that you will probably query your database much more often that you will alter it. You will also profit from Prolog's efficient lookup of facts, plus you can write queries in a more natural way.

Answer 2

I'd like to reinforce the point @Boris made: do not use dynamic predicates.

By far the cleanest solution is to use state variables to carry around the current state of the simulated machine. Because of Prolog's single-assignment characteristic, you will always have pairs of these: state before and state after. For registers and memory, the state is best represented as a table which maps register names (or memory addresses) to values. A stack can simply be kept as a list. For example:

main :-
    Stack0 = [],
    Regs0 = [eax-0, ebx-0, ecx-0, edx-0],
    Code = [movi(3,eax), add(eax,7), push(eax), pop(ecx)],
    sim_code(Code, Regs0, RegsN, Stack0, StackN),
    write(RegsN), nl, write(StackN), nl.

% simulate a sequence of instructions
sim_code([], Regs, Regs, Stack, Stack).
sim_code([Instr|Instrs], Regs0, RegsN, Stack0, StackN) :-
    sim_instr(Instr, Regs0, Regs1, Stack0, Stack1),
    sim_code(Instrs, Regs1, RegsN, Stack1, StackN).

% simulate one instruction
sim_instr(movi(Value,Reg), Regs0, RegsN, Stack, Stack) :-
    update(Regs0, Reg, _Old, Value, RegsN).
sim_instr(add(Reg,Value), Regs0, RegsN, Stack, Stack) :-
    update(Regs0, Reg, Old, New, RegsN),
    New is Old+Value.
sim_instr(push(Reg), Regs, Regs, Stack, [Val|Stack]) :-
    lookup(Regs, Reg, Val).
sim_instr(pop(Reg), Regs0, RegsN, [Val|Stack], Stack) :-
    update(Regs0, Reg, _Old, Val, RegsN).
%sim_instr(etc, ...).

% simple key-value table (replace with more efficient library predicates)
lookup([K-V|KVs], Key, Val) :-
    ( Key==K -> Val=V ; lookup(KVs, Key, Val) ).

update([K-V|KVs], Key, Old, New, KVs1) :-
    ( Key==K ->
        Old = V, KVs1 = [K-New|KVs]
    ;
        KVs1 = [K-V|KVs2],
        update(KVs, Key, Old, New, KVs2)
    ).

In practice, you should replace my simple table implementation (lookup/3, update/5) with an efficient hash or tree-based version. These are not standardised, but you can usually find one among the libraries that come with your Prolog system.