My mini interpreter using Prolog

One of my projects while doing my masters in CS at UT Dallas was creating an interpreter in Prolog that can parse a custom set of instructions(like if conditions, loops, arithmetic etc.) . So let’s say the user input to the interpreter will consist of two inputs that are provided in variables x and y.

If we wanted to write a program to find the power of a number, the code that would be written by the user and fed to the interpreter would be:

z=1             // z is assigned 1

w=x             // w is given the value of z. Here z and w are variables or stores.

while w>0      // while loop with a boolean condition

do z = z*y     // multiply z, w number of times

w =w-1         // decrement w by 1 for each pass through the loop
 
endwhile      // end of while loop

The above code along with the x and y values would be given to the interpreter by the user. In this case, for example, if y was 2 and x was 3, the output will be 2^3=8. Similarly other programs having different logic can be implemented by the user and fed to interpreter.

How it works:

The interpreter would run in two phases or passes. Once it will generate a parse tree(I had removed left recursion, so only one valid tree would be generated). The purpose of parse tree generation from the grammar was to check if the program written by user was correct syntactically. In the second phase or pass, the parse tree would be fed as input to the valuation functions. The purpose of valuation functions was to compute the value and display the result.

Later, I also fed my interpreter to Mixtus, which is a ‘partial evaluater’ for Prolog. In this case, the partial evaluater will take the interpreter and the user program as input and and return a specialized program that will execute more efficiently than the original user program. Lets call this specialized program returned by Mixtus the target code.

So the target code contains sort of a mixture of my interpreter and the user program (in this case it calculates the power). Now since we have this target code, we don’t need to explicitly mention the user program anymore. For the above example, we just need to input the two variables x and y. Once the target code gets the values of x and y, since its specialized to find the power, it will give the output as 8.

How this project has helped me:

This project has given me the satisfaction of watching my mini interpreter work and confidence that I can solve challenging technical problems.