Structure and Interpretation of computer programming- Introduction to scheme

SICP or structure and interpretation of computer programming is a fundamental book for understanding the simple logistics of programming in computers. According to the book SCIP A computational process, in a correctly working computer, executes programs precisely and accurately. novice programmers must learn to understand and to anticipate the consequences of their conjuring. Even small errors (usually called bugs or glitches) in programs can have complex and unanticipated consequences.Scheme a dialect of Lisp is a functional programming language taken to understand lexical scope and tail call optimization because of its minimalistic syntax notations which is very useful in translating to other languages as well.

Expressions and Naming 

We have prefix notation syntax in Lisp. 

=>(+ 2 3)                                            

      5 

The + operator can be applied to any number of elements.

=>(+ 2 3 5 6)

     16

We can assign value to variables and procedures ie, the function they are supposed to do by using the keyword define within parenthesis in mit-scheme.

In scheme it is as 

=>(define a 2)

=>a

     2

=>(define (s x) (x))

=>(s 2)

      2

For expression evaluations in lisp we have 

=>(/(+ 5 4 (- 2 (- 3 (+ 6 (/ 4 3)))))(* 3 (- 6 2)(- 2 7)))

 -23/90    

Compound procedures

Compound procedures are nothing but expressing the logic of a function in a given language. If we take the example of square of  number it is nothing but multiplying a number by itself. This is expressed in lisp as

=>(define (square x) (* x x))

=>(square 2)

     4 

Functions can also be passed as first order functions to other functions or rather procedures. These functions take in other functions as arguments and perform the required action on the variables. This is shown through a simple example:-

(define (sum term a next b)
        (if (> a b)
                0
                (+ (term a)
                        (sum term (next a) next b))))
(define (inc n) (+ n 1))
(define (cube x) (* x x x))
(define (sum-cube a b)
        (sum cube a inc b))
The above mentioned example takes in functions as arguments and the same function is called in another function to be applied.

Tail recursion and linear recursion

In simple recursion we have a function or a procedure calling it self many times. Each time a caller function calls a callee function the state of the caller function is saved in stack. In such cases the callee function has nothing to do but return the value to the caller function and in return it is returned back to its caller function. Some cases this proves to be very expensive in terms of space and/or time. In Scheme instead of iteration we have the same implemented as tail recursion optimization. 

In recursion if we see that if we call a procedure recursively, each recursive call has to be completed before the actual calculation to take place. This is illustrated using an example- 

(define (fibo n)
        (fibo-iter 1 0 n))
        (define (fibo-iter a b count)
                (if (= 0 count)
                        b
                        (fibo-iter (+ a b) a (- count 1) )))

The computation follows the pattern as-

(fibo-iter 0 1 5)

(fibo-iter 0 1 5)

(fibo-iter 0 1 4)

(fibo-iter 0 1 3)

(fibo-iter 0 1 2)

(fibo-iter 0 1 1)

(fibo-iter 0 1 0)

3

The actual value is computed after each recursive call then the final result is returned.

Now when we take the case of tail recursion, instead of saving the context of the caller procedure the callee procedure directly returns the result to the caller procedure's caller. Tail recursion is a feature of Scheme not just an implementation. In tail recursion at each time of the recursive call value of the running updates the value.In general a procedure may return to its caller (if it was non-tail called), or it's caller's caller (if it was tail-called but its caller wasn't) or it's caller's caller's caller (if it and it's caller were both tail-called), and so on. A procedure returns to the last caller that did a non-tail call.This can be shown by an example-

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

(fib 4) + (fib 3)

(fib 3) + (fib 2)

(fib 2) + (fib 1)

(fib 1) + (fib 0)

5

Each time the recursive call is made the value is returned to the caller procedure which returns to its caller and so on. Another example is pascal's triangle given as-

(define (pas row col)
        (cond ((or (= row col) (= 1 col)) 1)
                (else (+ (pas (- row 1) (- col 1))
                        (pas (- row 1) col)))))

returns the element of the triangle based on its position.

More examples based on the exercises from the book Structure and Interpretation of computer programming are experimented with in my git repository. Their Python translations are also available. https://github.com/anjalirmenon/scip.