The start of a simple interpreter

[WarFox]

As you guys may have seen from my discord avatar, I am a big South Park fan. For awhile, I have been dabbling with the idea of a creating a small language for the fun of it, it is also a great project for learning some important concepts. I will discuss one or two of them here. But the source code is small test code to test a few ideas of implementation, this is far from a finished product.

Interpreters seem to be a lot easier to craft. One really basic way of doing is by taking input and putting it into the form of another language, also "executing" the code "live." As a form of a programming language, this has some advantages and disadvantages. Simple to implement, don't have to spend as much time or any time digging in assembly, and executing "live." Executing "live," I mean it executes line by line as it runs. In a compiled language, the source file is compiled then ran, which can lead to it being harder to debug. Where as in Python, since it is ran line by line and executed that way, it is harder to trace errors in the programming or logic. Overall, it is easier to implement because I can get better use of another language's features to build features in my own. The major drawback of course, is speed. So in this implementation, function are interpreted and used as method within Java. So, you can imagine the process it has to go through.

So, in this program, I have implemented two stacks (LIFO) data structures. I got this idea from doing a function solver that read from left to right, using two stacks much like this. The two stacks are a stack of operands (numbers as an example) and operators (think of mathematical operations).  Read in the the function name and place it into a stack of operators. Then read in each operator and place in the operator stack. When ")" is reached, pop the operand and perform the operation by popping the operators off of the stack and performing the operation specific.

This is a really basic implementation. To there are currently only two functions. killKenny, which terminates the program. The other function is cartmanSays, which would be a print function.

 

Spoiler

import java.util.Stack;
import java.util.Scanner;

public class Interpreter {

  // instance variables
  private Stack<String> operands;
  private Stack<String> operators;
  private Scanner scan;
  private int opsThisFunction;

  // constructor
  public Interpreter() {
    operands = new Stack<>();
    operators = new Stack<>();
    opsThisFunction = 0;
  }

  public void interpretFromTerminal () {
    System.out.print(">> ");
    scan = new Scanner(System.in); // read input from terminal
    String currentToken;
    while (scan.hasNextLine()) {
      currentToken = scan.next();
      if (currentToken.equals("killKenny")) {
        operands.push(currentToken);
      } else if (currentToken.equals("cartmanSays")) {
        operands.push(currentToken);
      } else {
        if (currentToken.equals("(")) {
          continue;
        } else if (currentToken.equals(")")) {
          evaluate();
          System.out.print(">> ");
        } else {
          operators.push(currentToken);
	        opsThisFunction++; // counts operators within this function
        }
      }
    }
  }

  public void evaluate() {
    String currentOperand = operands.pop();
    if (currentOperand.equals("killKenny")) { // does not take operators
      System.out.println("Killing kenny......");
      System.exit(0);
    } else {
        if (currentOperand.equals("cartmanSays")) {
	         String currentOperator = "";
  	       while (opsThisFunction > 0) {
	           currentOperator = operators.pop() + currentOperator;
  	          opsThisFunction--;
	         }
           System.out.println(currentOperator);
        } else {
          System.out.println("Error");
        }
    }
  }

  // test code
  public static void main (String[] args) {
    Interpreter i = new Interpreter();
    i.interpretFromTerminal();
  }

}

 

Quote

>> ( cartmanSays hello world )
helloworld
>> (killKenny) 

 

[Freak]

This is pretty cool. It's a good start, and it looks very robust and versatile.

Do you have any plans for allowing multiple operands in a single line? For example if you had a random function and wanted to do something like:

( cartmanSays randomFunction )

Right now you just print everything. I think that the idea of using lists for operands is really cool and gives you a lot of potential for some really cool one-liners like with many functional languages, so I'm curious how you would tackle that problem. Maybe there's a cool way to make the Evaluate method recursive or something.

[WarFox]

It should be fairly easy to get going. Call a function and perform an operation on the operators within it. Then push the return value on to the stack where it can be evaluated again. This is one thing that makes implementing a functional language easier than say an object-oriented language, everything has a return value and can be evaluated function by function. This is where the stack data structure shines since in a function language, the last function called within nested functions is the first operated on and so forth.

So like in Haskell

factorial x = if x < 2 then 1 else x * factorial (x-1)

(print (factorial 5))

When the final line is being ran, print is pushed onto the operator stack. Then factorial is pushed on the operator stack. 5 on the operand stack. Hit a right parenthesis. pop both top values on the operator and operand stack. Evaluate using the operator 'factorial' using the operand '5'. Returns the value 120, which will be pushed on the operand stack. Read the next, which is the right parenthesis, so time to evaluate. Pop operator off operator stack, print function. Pop value off of the operand stack, 120. Evaluate print function with the value 120.

This same basic idea behind the algorithms I am trying to invoke are the same ones that can be used to solve functions like

Quote

3 + 2  ( 3 / 2 + (3*2(4+8)) ) + 1 * 7

It should already handle multiple parameters. It does not evaluate the function until it hits a single right parenthesis. The next steps are just to add more complex functions and checking of the syntax.

[WarFox]

First: I am hoping that someone on the admin team could move this topic to the Projects board maybe and I will continue to document my progress on this thread.

 

Now for some changes. I have changed over to using enumerations for the functions. This will help clean up the code and keep the Interpreter source file from growing to be large with everything embedded inside of it. So what the program does is read in a token, checks if it matches a case within enumerations, then returns the enum value. Pushes that to the operators stack. Meanwhile it checks to see if there is an enum value of END_FUNCTION, where it will then evaluate. Eventually, I plan to off the evaluate the function to another source file to keep that clean and perhaps also organize functions into "modules." Also, instead of 1 source file, there are 3. A main class, Interpreter class and Functions class.

Spoiler

/*
 * Main.java
 * 
 * Copyright 2019 Todd <todd@pop-os>
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02110-1301, USA.
 * 
 * 
 */


public class Main {
	
	public static void main (String[] args) {
		Interpreter i = new Interpreter();
		i.interpretFromTerminal();
	}
}

 

 

Spoiler

import java.util.Stack;
import java.util.Scanner;

public class Interpreter {
	
	// instance variables and datastructures
	private Stack<String> operands;
	private Stack<Functions> operators;
	private Scanner scan;
	private int operandsThisFunction;
	
	public Interpreter () {
		operands = new Stack<>();
		operators = new Stack<>();
		
		operandsThisFunction = 0;
	}
	
	public void interpretFromTerminal () {
	System.out.print(">> ");
		scan = new Scanner(System.in); // read input from terminal
		String currentToken;
		while (scan.hasNextLine()) {
			currentToken = scan.next();
			Functions fx = Functions.checkForToken(currentToken);
			if (fx != Functions.DOES_NOT_EXIST) {
				if ( fx == Functions.END_FUNCTION) {
					evaluate();
					System.out.print(">> ");
					continue;
				}
				operators.push(fx);
				// System.out.println(fx); // test statement - works
			} else {
				if (currentToken.equals("(")) { // ignore character
					// System.out.println(currentToken); // test statement
				continue;
				} else {
					operands.push(currentToken);
					operandsThisFunction++; // counts operators within this function
					// System.out.println(currentToken); // test statement
				}
			}
		}
	}
	
	public void evaluate() {
		Functions currentOperator = operators.pop();
		// System.out.println(currentOperator); // test statement
		if (currentOperator == Functions.QUIT) { // does not take operators
			System.out.println("Killing kenny......");
			System.exit(0);
		} else {
			if (currentOperator == Functions.PRINT) {
				String currentOperand = "";
				while (operandsThisFunction > 0) {
					currentOperand = operands.pop() + currentOperand;
					operandsThisFunction--;
				}
				System.out.println(currentOperand);
			} else {
				System.out.println("Error");
			}
		}
	}	
}

 

Spoiler

public enum Functions {
	
	PRINT,
	QUIT,
	END_FUNCTION,
	DOES_NOT_EXIST
	;
	
	public static Functions checkForToken (String s) {
		switch (s) {
		case "cartmanSays" :
			return Functions.PRINT;
		case "killKenny" : 
			return Functions.QUIT;
		case ")" :
			return Functions.END_FUNCTION;
		default:
			return Functions.DOES_NOT_EXIST;
		}
	}	
}

 

Output:

Spoiler

>> ( cartmanSays Hello World )
HelloWorld
>> ( killKenny )
Killing kenny......

 

 

Edited December 28, 2019 by WarFox

[WarFox]

Updates to development:

 

Source code may be viewed on github here.

 

The language not performs basic arithmetic such as addition, multiplication, division, and subtraction. Every number is handled as a double. Also, am important note, there is no checking in the langauge, as seen in the README.md. In other words, the program will not notify is there is a wrong type inputed to a function, flaw in logic, or mistype. I hope to get around to this in a future update, but I have been working on another interpreter for an already defined esoteric language that I will post a tutorial/documentation on, this will contribute to me learning for how to implement certain functions in this language.

Some notes about how I handled various things. There is a slightly custom data structure that I have employed. Normally, languages use an AST (type of tree structure) to implement the language. I have decided to try a little but of a different route, for fun and I am not too familiar with trees currently. So, a future iteration may implement a tree. My custom data structure is simple a stack for a type that implements the function name with an according stack of operands. Every function is put on to the stack with its operands, unless that operand is a function itself. The top function that is terminated by a left parenthesis is evaluated and pushed on to the top item of the stack's operands.

 

Here is some sample code and output:

Quote

>> ( cartmanSays ( + ( + 1 1 ) ( - 2 4 ) ) )
4.0

Since I have implemented it using stacks, one important thing to stress for math operations, operations are evaluated from right to left. So here would be a translation of the basic arithmetic here:

Quote

(4 - 2)+( 1+1)