Fibonacci Series - LISP(Scheme)

Fibonacci Series - LISP(Scheme)

Now in coding for different problems , you might have certainly found the problem to find nth  number in a fibonacci series... First of all what is a fibonacci series ? 

Well fibonacci series is a series starts with 0 and 1 then further series is evaluated as sum of two previous numbers i.e 0, 1, 1, 2, 3, 5, 8, 13, and so on... One can find good detail on fibonacci series at 

Fibonacci Series.

Now let us see how we might implement the above problem in lisp...

We want to be able to find nth number , so suppose we want to find 4th number in the series, how will we go about it... 

first of all we know that we need to find fibonacci at 4th and for finding Fibonacci number at 4th place we need to add Fibonacci number at 3rd and Fibonacci number at 2nd place, similarly for 3rd place fibonacci number we need to know The Fibonacci number at 2nd and 1st place and similarly for 2nd we need to know The Fibonacci number at 0th and 1st place which we know and so we can see a series being formed following the pattern fib(n) = fib(n-1) + fib(n-2) which looks like:

 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ...

So first of all we need to create a procedure taking n, and if we want value of fib 0 or fib 1, we should be able to return it, otherwise we need to calculate (fib n-1) + (fib n-2).

(define (fib n)(cond((= n 0) 0)
                                ((= n 1) 1)
                                (else(+ (fib (- n 1)) (fib (- n 2))))))

In the above code we simply start by stating the values of n = 0 and n = 1, other than those values we simply ask it to recursively compute two thing's
1. fib(- n 1)
2. fib(- n 2)
and add those up.


The above code will look like :
>(define (fib n)(cond((= n 0) 0)
                        ((= n 1) 1)
                        (else(+ (fib (- n 1)) (fib (- n 2))))))
in the interpreter.
Lets run the procedure we just created:
>(fib 5)
5

We can write the same program using an iterative approach which helps in a better memory management.

For Iterative approach we simply don't want to store much so we start from what we know and calculate what we don't know rather than keeping track of what we need to calculate...

(define fib-iter a b n)(cond ((= n 1) b)
                                           (else(fib-iter b (+ a b ) (- n 1)))))

a b are initially 0 & 1 respectively and n is the nth fibonacci term we wish to find.

Written By,

Sarvesh Bhatnagar

Block Structure for Cube-Root (Scheme)

Cube Root - LISP(Scheme)

Using Block Structure

Let us try the same we did for finding out cube root using block structure in LISP(Scheme dialect). 

First we should define some common functions which can be safely named globally such as cube:

(define (cube x)(* x x x))

Now let us start by defining cuberoot function:

(define (cuberoot guess x)

  (define (goodGuess)(<(abs (- (cube guess) x)) 0.001))

  (define (improve)(/(+ (/ x (* guess guess)) (* 2 guess)) 3))

  (if(goodGuess) guess (cuberoot (improve) x)))

1. (define (cuberoot guess x)

in this step we simply define a block for cuberoot block ( main block ) and we know that we will require goodGuess procedure and an improve procedure both taking guess and x as a parameter but since both are already in lexical scope we can safely omit the parameters since we already know its value.

hence following (define (cuberoot guess x) we define goodGuess and improve : 

  (define (goodGuess)(<(abs (- (cube guess) x)) 0.001))

  (define (improve)(/(+ (/ x (* guess guess)) (* 2 guess)) 3))

inside the main block.

Then we implement the actual cuberoot function by checking if the current guess is a good one, if it is a goodGuess then we simply output the guess else we improve it and call cuberoot again.

So now in interpreter , the function's will look like: 

>(define (cube x)(* x x x))

>(define (cuberoot guess x)

  (define (goodGuess)(<(abs (- (cube guess) x)) 0.001))

  (define (improve)(/(+ (/ x (* guess guess)) (* 2 guess)) 3))

  (if(goodGuess) guess (cuberoot (improve) x)))

Now let us test the made program by running it in interpreter, it will look like: 

>(cuberoot 1.0 8)

2.000004911675504

where 1.0 is the initial guess and 8 is the number of which we are interested to find cuberoot of.

Written By,

Sarvesh Bhatnagar

Block Structure (Square Root) - LISP

Block Structure - LISP

Now the style in which we have been coding until now , is a bit dangerous if we are talking about large and complex program as our coding style may lead to ambiguity between different programmer's function nomenclature. suppose one programmer name's  a function 'addup' which add's 2 numbers and then add's it with the multiplication of two numbers : (x + y) + (x * y) and suppose another function similarly names some other routine 'addup' which adds 2 numbers two times like (x + y) + (x + y) or 2* (x + y) now during execution , there may occur some ambiguity which may lead to unintended consequences , so we use block structures in which the not so common functions are defined inside the main function which we are using , like in previous square-root and cube-root example good enough?  and improve are not common functions so we can use the block structure as follows: 

First defining the common functions, square of a number and average of 2 numbers...

(define (square x)(* x x))

(define (average x y)(/ (+ x y) 2))

Now defining the square-root function in a block structure method : -

(define (sqr-root guess x)
    (define (good-guess)(<(abs(- (square guess) x)) 0.001))
    (define (improve)(average guess (/ x guess)))
    (if(good-guess) guess (sqr-root (improve) x)))

In above code, we first know that we need to pass the guess and the number of which we want the square root : so we started by:
(define (sqr-root guess x)

Now we know from original method that sqr-root function looks like this :
(define (sqr-root guess x)(if (good-guess guess x) guess (sqr-root (improve guess x) x))

So we know that we will require good-guess and an improve function ,  so we define good-guess function as:
(define (good-guess) (<(abs(-(square guess) x))0.001))

we didn't passed the parameters guess and x to the good-guess function as we are defining the good-guess function inside of sqr-root function so we don't need to pass the parameters since inside the function sqr-root we already know the value of guess and x.
similarly , we defined improve inside the sqr-root function as :

(define (improve) (average guess (/x guess)))

Now let us see how the program will look like in the terminal :

>(define (square x)(* x x))
>(define (average x y)(/ (+ x y) 2))
>(define (sqr-root guess x)
    (define (good-guess)(<(abs(- (square guess) x)) 0.001))
    (define (improve)(average guess (/ x guess)))
    (if(good-guess) guess (sqr-root (improve) x)))

Lets run the program and try the function sqr-root out:
>(sqr-root 1.0 4)
2.0000000929222947

Written By,

Sarvesh Bhatnagar

Cube Root - LISP

Cube Root - LISP(Scheme)

Let us program similarly for finding the cube root of which just 1 thing changes. i.e, how the next improve guess is defined i.e: if we make a guess, g then the improved guess would be 

g' = (x/(y^2) + 2y)/3

So , we will mainly have to make changes in improve which would look as:

(define (improve guess x)(/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

Now our other functions are similar, just in checking of good guess we need to check the difference between the cube of the guess and x instead of square of the guess and x. Hence the procedure goodGuess changes to:

(define (goodGuess guess x)(<(abs(- (cube guess) x)) 0.001))

Now we need to define something else, instead of the function square, i.e: cube. 

(define (cube x)(* x x x))

Now let us define the main function cuberoot, its much similar to square root function we defined earlier. 

(define (cuberoot guess x)(if(goodGuess guess x)guess (cuberoot (improve guess x) x)))

Now our total code will look in interpreter like: 

>(define (cuberoot guess x)(if(goodGuess guess x)guess (cuberoot (improve guess x) x)))

>(define (goodGuess guess x)(<(abs(- (cube guess) x)) 0.001))

>(define (cube x)(* x x x))

>(define (improve guess x)(/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

Now let us see the code in action , 

>(cuberoot 1.0 8)

2.000004911675504

Written By,

Sarvesh Bhatnagar

Square Root

Lisp - Square Root

Lets take a look at the program to find square root of a number by newtons method

It involves 2 main steps : 

1. Check if current guess is a good one

2. If 1 returns false, improve the guess by guess + (x/guess) / 2 and re-apply the method to find square root.

so some basic functions which we might require are:

Average:

(define (average x y) (/ (+ x y) 2))

Improve Guess:

(define (improveGuess guess x) ( average guess (/ x guess )))

goodGuess? :

(define (goodGuess? guess x) (< (abs (- (square guess) x)) 0.001))

Average: Takes in 2 arguments x and y , adds them and then divides the sum by 2

 

Improve Guess: does what is mentioned in step 2

goodGuess: Calculates | guess^2 - x | and checks if the magnitude is more than 0.001, if it is then the guess needs to be improved , else the guess is good. 0.001 is the amount of error which is acceptable in calculation of square root.

now let us define square root:

(define (sqrt guess x) ( if(goodGuess? guess x) guess (sqrt (improveGuess guess x) x)))

Let us see total program in interpreter

>(define (average x y) (/ (+ x y) 2))

>(define (improveGuess guess x) ( average guess (/ x guess )))

>(define (goodGuess? guess x) (< (abs (- (square guess) x)) 0.001))

>(define (sqrt guess x) ( if(goodGuess? guess x) guess (sqrt (improveGuess guess x) x)))

Now let us use our defined function sqrt in action, Note that the initial guess value is required to be seeded, in this case we are initializing it as 1.0

>(sqrt 1.0 4)

2.0000000929222947

Simple Procedures - LISP

Simple Procedures - LISP (Scheme)

In this post we will see how to define some procedures and use them.

Square:

Square of a number is the number time's number itself. Lets see how we can define the procedure to find a square of a number.

(define (square x) (* x x))

yes its that simple, and can be read as: define square which takes 1 argument x, and returns x * x. 

Now suppose we want to find the square of 4, we would simple type the following in the interpreter:

>(square 4)

>16

Now lets try and define a procedure to find larger number from the two given numbers:

(define (findMax x y) (cond (( > x y) x) (else y)))

cond is for condition, and in front of the condition we are placing the conditions and if it evaluates to true then we simply give the output we desire for that condition and at the end if none of the preceding condition evaluates to true then we return the desired output for that scenario by placing an else before the output.

Similarly we can define another procedure which finds the minimum of the two numbers:

(define (findMin x y)(cond ((< x y)x)(else y)))

Now let us define another procedure which takes in 3 inputs and returns the summation of square of two large numbers:

(define (largeSquareSum x y z)(cond((and (> x y) (> z y)) (+ (square x) (square z)))((and (> y x) (> z x)) (+ (square y) (square z)))((and (> x z) (> y z)) (+ (square x) (square y)))))

The same program can be written in a more neat way as follows:

(define (largeSquareSum x y z)(cond((and (> x y) (> z y)) (+ (square x) (square z)))

                                                              ((and (> y x) (> z x)) (+ (square y) (square z)))

                                                              ((and (> x z) (> y z)) (+ (square x) (square y)))))

The above program follows a very simple logic, it checks if x,z pair are larger than y, or if y,z pair are larger than x or if x,y pair is larger than z and returns the sum of square of the pairs whichever is larger.

If we pass the following to the interpreter we will get :

>(largeSquareSum 1 2 3)

>13

Written By,

Sarvesh Bhatnagar

Arithmetic Operations - Lisp

Arithmetic Operations - Lisp

Any operation in lisp follows a prefix notation. i.e. Operator is placed before the operand's.

e.g. 

Addition: 

>(+ 4  5)

>9

The above operation is evaluated as 4 + 5

Subtraction:

>(- 10 4)

>6

The above operation is evaluated as 10 - 4

Division:

>(/ 20 10)

>2

The above operation is evaluated as 20 / 10

Multiplication:

>(* 2 3)

>6

The above operation is evaluated as 2 * 3

Similarly if we want to perform some complex nested operations such as ((2+4)*(5-2)) / (10 + 2) * 4

The same can be done as making an operation tree as:

                   /

      *                     *  

  +      -             +       4

2   4  5   2    10    2

Hence by looking at the nested tree, we know that in total division appears first, then we divide up the operations into two parts further we know in those two parts multiplication is needed to be performed between 2+4 & 5-2 and multiplication between 10 + 2 and 4 ... so our prefix notation leads to the following steps.

1.(/ (*)(*))

2.(/ (*(+)(-))(*(+) 4))

3.(/ (* (+ 2 4) (- 5 2)) (* (+ 10 2) 4))

Giving the equation obtained in 3 to the interpreter:

>(/ (* (+ 2 4) (- 5 2)) (* (+ 10 2) 4))

>3/8

hence the result of the operation is 3/8.

Written By, 

Sarvesh Bhatnagar

Lisp

Lisp

Lisp is a family of computer languages with a long history and a distinctive fully parenthesized prefix notation. Lisp is second oldest high level programming language in widespread use today, there are various dialects of lisp and we will mainly be focusing on the dialect known as scheme.

Scheme is a dialect of lisp supporting multiple programming paradigms, including functional programming paradigm and imperative programming paradigm. Scheme was developed at MIT AI LABS during 1970's.

The reference book we will be using for learning Scheme will be : Structure and Interpretation of Computer Programs.

The interpreter we will be using for Scheme is DrRacket.