The contrast between function and procedure is a reflection of the general distinction between describing properties of things and describing how to do things, or, as it is sometimes referred to, the distinction between declarative knowledge and imperative knowledge. In mathematics we are usually concerned with declarative (what is) descriptions, whereas in computer science we are usually concerned with imperative (how to) descriptions.
SICP is a book by Harold Abelson, Gerald Jay Sussman and Julie Summnan used in introductory course at MIT. I started reading the same book one month before. now completed 1st chapter. i want to share what i learned from it. It was very fun and i enjoyed a lot. I believe lot of its readers also enjoyed a lot. that’s why this book got lot of attention in the past decades. Book was published on 1984. Online version of the book is available at https://mitpress.mit.edu/sicp/full-text/book/book.html and you can download as pdf.
SICP contains 5 chapters:
- Building Abstractions with Procedures
- Building Abstractions with Data
- Modularity, Objects and State
- Metalinguistic Abstraction
- Computing with Register Machines
I will tell what i learned from first chapter in the this article
I presume that you are familiar with atleast one language. SICP teach with Lisp. Lisp mostly considered as academic language, not a mainstream language. See what book says about the evolution of Lisp:
Lisp was not the product of a concerted design effort. Instead, it evolved informally in an experimental manner in response to user’s needs and to pragmatic implementation considerations
You may wonder if you see the syntax of the Lisp, it is in a prefix style. let me give an example how we write same expression in C and Lisp
In C : a = b*5 + c – 6;
In Lisp : (define a (+ (* b 5) (- c 6)))
A quick demo of Lisp syntax will get from http://learnxinyminutes.com/docs/common-lisp/
You will understand how syntax works after do some little programs in Lisp.
Every powerful languages will have the following things:
- Primitive expression: Which is simplest things we can do with language, as it’s name says.
- Means of combination: Using the primitive expressions we can create complex entities.
- Means of Abstraction: Compound entities can be named and manipulated as units.
Sample primitive expressions in Lisp: 512 ; a number (+ 4 3) ; adding two numbers (- 10 5) ; subrtacting 5 from 10 (* 5 6) (/ 8 2) more complex one: (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6)) = 3 * ((2 * 4) + 3 + 5) + 10 - 7 +6 for naming an object use "define" a = 5 can be written in Lisp as (define a 5) (define pi 3.14)
This chapter insist us to think procedurally. Lisp interpreter itself use th following procedure to evaluate compound expressions
1. Evaluate the sub expressions of the combination
2. Apply the procedure that is the value of the left most sub expression(the operator) to the arguments that are the values of other sub expressions(the operands).
in (+ 2 3) left most sub expression is ‘+’ which is operator other two sub expressions ‘2’ and ‘3’ are operand. it is clear that + is a primitive procedure and 2, 3 are primitive data.
Evaluation models is recursive, because it is obvious that one sub expression may other compound expression. we can represent it like a tree. book explain about it very well.
We can define our own procedures.
See an example of cube procedure
(define (cube x) (* x x x)) (cube 2) will return 8. some of cube of two numbers can found by like (+ (cube 3) (cube 4)).
general form of procedure definition is
(define (<name> <formal parameters>) <body>)
First chapter introduce two types of evaluation model. Normal order and Applicative order.
Normal order: which is fully expand expression until it involves only premitive expression and evaluate
Applicative order: It evaluates arguments first and apply procedure. Interpreter itself using this method.
Authors explain about it very well in the book, read book to understand how those works very well, they demonstrate it with images.
Conditional expressions
Conditional expression is to execute some code block depend on some test. there are two types of conditional structures in lisp
1. if statement perform different operations depend on the result of the test
2. cond statement can be considered as case in many language. we can specify unlimited number of tests and their operations if test is true.
Example
(if (= 1 0) -> test expression (+ 2 4) -> execute if true (- 4 2)) -> execute if false (cond ((> 2 2) (error "wrong!")) ((< 2 2) (error "wrong again!")) ((= 2 2) 'ok')) ; => 'OK
SICP demonstrating concepts with interesting problems like finding roots with newton’s method and at the end of the each sections there are lot of excersise to do. You can see my solutions to the excersise problems of chapter 1 at https://github.com/faisalp4p/sicp/tree/master/ch1
Procedures as black box Abstraction
Explaining power of procedure is the main goal of this chapter. even name of the chapter is ‘Building Abstractions with Procedures’. Procedures can be considered as a Black box. which will take some parameters as input, process it and produce output. For example sqrt is a procedure which take a number x and produce square root of x. once we build sqrt procedure we don’t need to do the same procedure, instead we can call sqrt procedure by its name and the number as argument. We can have procedure definitions inside a procedure, that is we can combine as much as functions to produce another procedure. sqrt function is recursive in nature, because same function call itself. this function tell us a lot of interesting things about recursion. see there is no looping statement in Lisp, we do procedures which need loop with recursive calls. and chapter keep explaining about tail recursion and tree recursion. tree recursion explain using a procedure to generate Fibonacci series. Through out the chapter we meet interesting problems.
sqrt procedure: (define (average x y) (/ (+ x y) 2)) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) (define (improve guess x) (average guess (/ x guess))) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (define (sqrt x) (sqrt-iter 1.0 x)) (sqrt 9) 3.00009155413138
Order of Growth
Process consume computational resources. order of growth is one of the notation to describe rate of consumption. You may familiar with Big O notation. this sesion explain details about what is order of growth and how we can measure order of growth of a procedure.
Chapter goes through Exponentiation, Greatest common divisor, primality test etc. different methods to solve problems in such domains and how we can optimize that using different tricks.
Higher order functions
This section describes about abstraction with higher order function. Power of a procedure for abstraction will extend considerably if we can accept a procedure as argument and procedure as return value.
We can pass procedure as argument. consider a situation we need find out sum of square of two numbers. after that we have to compute sum of cube of two numbers. above two procedures are some what similar. consider a procedure which take two numbers and a function as arguments that will return sum of those numbers applied to the function received as argument.
we can create anonymous function using lambda keyword. which helps to produce a procedure without name and pass as arguments or as a return value.
Procedures as return value
Now procedure as return value. we can also retrieve a procedure as a return value and use that function. section explain procedure as return value using newton’s method to find roots of numbers with the help of fixed-point function. and there are lot of problem related to this in the exercise part.
At last chapter says, in Lisp procedure is a first-class object. that is we can consider procedures like other first class objects like numbers and string. that’s why can pass and return procedure like numbers and other primitive types.
Links
SICP index : https://mitpress.mit.edu/sicp/full-text/sicp/book/
My solutions for the exercises : https://github.com/faisalp4p/sicp
Quick reference of Lisp language : http://learnxinyminutes.com/docs/common-lisp/
Out of Context 