Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

implement a simple C like language in Prolog?

I'm new to prolog, so this's quite a challenge to me. I'm supposed to implement a simple C like language in Prolog.

the ultimate goal is to be able to execute something like this:
?- run([begin,a,:=,10,while,a,>,5,begin,write,a,a,:=,a,-,1,end,end]).

and get: 
10 
9
8
7
6 
yes

However, I'm stuck at the first step. This is what I have achieved so far. out of local stack!

statement(Vars,_Vars) --> assign(Vars,_Vars).
statement(Vars,Vars2) --> statement(Vars,Vars1), statement(Vars1,Vars2). 

assign(Vars,_Vars) --> default_assign(Vars,_Vars).
assign(Vars,_Vars) --> simple_assign(Vars,_Vars).

% a //default value 0
default_assign(Vars,_Vars) --> 
    var_name(Var_Name),
    {update_vars([Var_Name,0],Vars,_Vars)}.

% a = 0
simple_assign(Vars,_Vars) --> 
    var_name(Var_Name),[=],var_value(Var_Value),
    {update_vars([Var_Name,Var_Value],Vars,_Vars)}.

% a = b
simple_assign(Vars,_Vars) --> 
    var_name(Var_Name1),[=],var_name(Var_Name2),
    {
    update_vars([Var_Name1,Var_Value],Vars,_Vars)
    }.

var_name(Var_Name) --> [Var_Name],{\+number(Var_Name2)}.    
var_value(Var_Value) -->[Var_Value],{number(Var_Value)}.

% found match, update
update_vars(Var,Vars,_Vars):-
    member(Var,Vars),
    update(Var,Vars,_Vars),
    _Vars\==[].
% no match, append
update_vars(Var,Vars,_Vars):-
    \+member(Var,Vars),
    append(Var,Vars,_Vars).

update([Name,Value],[],[]).
update([Name,Value],[[Name,Old_Value]|T1],[[Name,Value]|T2]):-
    update([Name,Value],T1,T2).
update([Name,Value],[[Name1,Value1]|T1],[[Name1,Value1]|T2]):-
    [Name,Value]\=[Name1,Value1],
    update([Name,Value],T1,T2).

append([Name,Value],[],[[Name,Value]]).
append([Name,Value],[H|T1],[H|T2]):-
    append([Name,Value],T1,T2).

Here's my logic. First I want to be able to consume the list(that's how I interpret it - -!), so the grammar structure is really really important. And I'm also thinking about using a variable list 'Vars' in forms of [[Name,Value],[a,1],[b,2]...], and an updated version - '_Vars'. So I can pass it to other statements like while loop and write.

statement(Vars,Vars2) --> statement(Vars,Vars1), statement(Vars1,Vars2).
% this seems wrong...

But... It looks like the logic is wrong from the beginning. :\ below is the simplified version. I would really appreciate it if you can help me out here. And I really hope I won't take this with me in Christmas. T.T

statement --> assign.
statement --> statement, statement.

assign --> simple_assign.
assign --> default_assign.

default_assign --> 
    var_name(Var_Name).
simple_assign --> 
    var_name,[=],var_value.

var_name --> 
    [Var_Name],{\+number(Var_Name)}.    
var_value -->
    [Var_Value],{number(Var_Value)}.
like image 362
Hashbug Avatar asked Dec 17 '13 10:12

Hashbug


1 Answers

This is how I would go about it:

  1. transform the source code into a abstract syntax tree

    begin 
      a := 1
      while a < 5
      begin
        a := a + 1;
      end
    end
    

    becomes

    statements([
        assign(a, number(1)),
        while(greater(variable(a), number(5))), 
              statements([
                  assign(a, plus(variable(a), number(1)))
                         ])
             )
               ])
    
  2. build an interpreter for it.

    There are various interpreters. The easiest one is the vanilla interpreter. Here is one I would begin with:

    interpret(number(N), State, N, State).
    interpret(assign(Variable, Statement), State, Value, NewState) :- 
        interpret(Statement, State, Value, NewState1), 
        assignVariable(Variable, Value, NewState1, NewState).
    
like image 66
User Avatar answered Sep 24 '22 21:09

User