Lets implement a simple Lisp Interpreter in Java

Edit 2015.03.20 : If you are really interested in implementing a LISP like language in Java, you can visit this, this and this. 

You are probably programing with C++, Java or .Net thingies but not Lisp. Why? Because it is the most beautiful language that human ever made :) Let me explain.

If you write in a programming language, you have to look and understand the interpreter's or compiler's principals. If you didn't do that yet, let me say, when you look inside an interpreter you will see a picture in which hundreds of objects being copied from one data structure to another called stacks. When you trace the interpreter, you will see nothing except those abstract data structures. The scene you will see is like a casino with hundreds of card dealers...

But when you program in Lisp, the interpreter exactly does what you write. There is no abstraction, no hacking. You will deal the cards in your fully controlled casino. Having knowledge about what the interpreter does is everything.

Lets look at the following Lisp expression

(+ 2 (+ 3 2))

which states that interpreter first will sum 2 and 3 and the gained number will be summed with 2. The result should be 7. How did we do that? Because of our primary school skills. Lets do that with a stupid machine that can only handle basic stack operations as in assembly language.

Suppose that we have a stack object and we are sequentially adding tokens into that stack. A token is defined as an atomic element of this expression. So our tokens are (, +, 2, (, +, 3, 2, ) and ) , respectively.

Now, take the first token and put it into the stack. Our stack is like that:

/

Lets add more elements until we encounter a closing parenthesis.

(

+

2

(

+

3

2

)

Again, suppose that, whenever we encounter a closing parenthesis, we collect some elements from the stack until we get an opening parenthesis, say that, we have now

(

+

3

2

)

collected from the stack. Calculate this simple expression and put the result back to our stack. Since result of the sub expression (+ 3 2) is 5, our stack comes to shape of

(

+

2

5

We didn't finish reading the tokens yet. We have one more token to push into the stack.

(

+

2

5

)

We encounter a closing parenthesis again and that means we have to handle the sub expression and put back the result to the stack. Since there is no sub expressions, we have the root expression at hand. Reading until having an opening parenthesis and performing calculations will give the result of 7 after all.

Note that, all we did here spans a 50 lines of Java class. I hope taking a glance at this code will help you to capture the whole story.

package smalllisp;

import java.util.Stack;

public class SmallLisp {

  Stack<String> stack;
  
  public SmallLisp(){
    String[] tokens = new String[]{"(","+","2","(","+","3","2",")",")"};
    stack = new Stack<String>();
    for (int i=0;i<tokens.length;i++){
      stack.push(tokens[i]);
      if(tokens[i].equals(")")) Interprete(); 
    }
  }
  
  public void Interprete(){
    String tok;
    Stack<String> callStack = new Stack<String>();
    tok = stack.pop(); /* This is the ) character */
    while(!(tok=stack.pop()).equals("(")){
      callStack.push(tok);
    }
    Call(callStack);
  }
  
  public void Call(Stack<String> callStack){
    String func = callStack.pop(); /* This is the operator or function */
    if(func.equals("+")) {
      double result = Plus(callStack);
      stack.push(String.valueOf(result));
    }
    //if(func.equals("-")) Minus(callStack);
  }
  
  public double Plus(Stack<String> callStack){
    double a = Double.parseDouble(callStack.pop());
    double b = Double.parseDouble(callStack.pop());
    System.out.println("Answer is "+(a+b));
    return(a+b);
  } 
  
  public static void main(String[] args) {
    new SmallLisp();
  }
}

Todo:

• Implement the minus function yourself.
• Implement the product function yourself.

Well done !