Lisp for the C++ programmer: Numerical Integration

In the series of Lisp for the C++ programmer, we present some Common Lisp examples in a way similar to examples which are written in C++ or some other languages belong the same family tree of C++.

Here is the example of Riemann sum in Common Lisp. We first define a function f which takes a single parameter x and the function y = f(x) = x, for simplicity. We will change this function later. It is known that integration of this function from 0 to 1 is 0.50.

Common Lisp code for numerical integration (approximatly result) is:

 (defun f (x)  
     x  
 )  
 (defun integrate (f start stop)  
     (setq epsilon 0.0001)  
     (setq sum 0.0)  
     (loop for i from start to stop by epsilon do  
         (setq sum (+ sum (* (funcall f i) epsilon)))  
     )  
 sum  
 )  
 (print (integrate 'f 0 1))  

The result is 0.4999532. Now we can use a more complex function, for example a normal distribution function with zero mean and unit variance. This function can be defined in Common Lisp as

 (defun normal (x)  
     (setq a (* (/ 1 (sqrt (* 2 3.141592))) (exp (* -0.5 (* x x)))))  
 a  
 )  
 (defun integrate (f start stop)  
     (setq epsilon 0.0001)  
     (setq sum 0.0)  
     (loop for i from start to stop by epsilon do  
         (setq sum (+ sum (* (funcall f i) epsilon)))  
     )  
 sum  
 )  
 (print (integrate 'normal -1 1))  

In the code above, as it can clearly be seen, we integrate the standard normal distribution from -1 to 1 and the result is 0.6826645.

Lisp for the C++ programmer: Changing an element of a list

Here is the example of changing an element of a Common Lisp List and its equivalent code in C++ typed as List comment.

 ; #include <cstdlib>  
 ; #include <cstdio>  
 ;  
 ; int main(){  
 ;    double *d = (double*) malloc (sizeof(double) * 3);  
 ;    d[0] = 1;  
 ;    d[1] = 2;  
 ;    d[2] = 4;  
 ;  
 ;    puts("Current List:");  
 ;    printf("%f %f %f\n", d[0], d[1], d[2]);  
 ;  
 ;    puts("New List:");  
 ;    d[0] = 100;  
 ;    printf("%f %f %f\n", d[0], d[1], d[2]);  
 ;    return(0);  
 ;}  
   
   
 (setq aList (list 1 2 3))  
 (print "Current List:")  
 (print aList)  
   
 (setf (elt aList 0) 100)  
 (print "New List:")  
 (print aList)  
   
   

Lisp for the C++ programmer: for loop

Here is the example of for loop. Equivalent C++ code is commented on the top the Common Lisp code as comments.

 ; for (int i = 0; i <= 10; i++){  
 ;    printf("%f\n", i);  
 ;    printf("%f\n", i * 2);  
 ; }  
   
 (loop for i from 0 to 10  
     do  
     (progn  
         (print i)  
         (print (* i 2))  
     )  
 )  
   

Lisp for the C++ programmer: Function definitions and function calls

Here is the simple Common Lisp example, in which a sum and an ArithmaticMean functions defined. Both C++ and Common Lisp code here calculate the arithmetic mean of 1,2,3,4,5 and 6 which is 3.5. C++ code is commented as in the Common Lisp file.

 ; double sum (double *d, int len){  
 ;    double mysum = 0.0;  
 ;    for (int i = 0; i < len; i++){  
 ;        mysum += d[i];  
 ;    }  
 ;    return(mysum);  
 ; }  
 ;  
 ; double ArithmeticMean (double *d, int len){  
 ;    return ( sum(d) / len );  
 ; }  
   
 ; int main(){  
 ;    double *mylist = (double*) malloc(sizeof(double) * 6);  
 ;    for (int i = 0; i < 6; i++){  
 ;        d[i] = (double)i;  
 ;    }  
 ;    printf("%f\n", ArithmeticMean(d, 6);  
 ;    return(0); 
 ; }  
   
   
   
 (defun sum (aList)  
     (setq mysum 0.0)  
     (dotimes (i (length aList))  
         (setq mysum (+ mysum (nth i aList )))  
     )  
     mysum  
 )  
   
 (defun ArithmeticMean (aList)  
     (/ (sum aList) (length aList))  
 )  
   
 (print (ArithmeticMean '(1 2 3 4 5 6)))  
   

Lisp for the C++ programmer: cond expression

Here is the example for the cond expression of Common Lisp and its C++ equivalent.

 ; int x = 10;  
 ; if (x < 10) {  
 ;    puts("x is smaller than 10");  
 ; } else if (x > 10){  
 ;    puts("x is bigger than 10");  
 ; } else if (x == 10){  
 ;    puts("x equals to 10"));  
 ; }  
   
 (setq x 10)  
   
 (cond  
     ((< x 10) (print "x is smaller than 10"))  
     ((> x 10) (print "x is bigger than 10"))  
     ((= x 10) (print "x equals to 10"))  
 )  
   

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 !