Procedural abstraction
Abstraction is a process of focusing attention on the main problems by ignoring lower-level details. In high level programming, we deals with two particular kinds of abstraction: procedural abstraction and data abstraction.
Procedural abstraction
Its a model of what we want a subprogram to do (but not how to do it). It provides mechanisms for calling well defined procedures or operations as entities.
Example: In Python when we write from math import log; print log(2) we really don’t care about how log function is implemented in math library. we have no idea how that log(2) actually gets computed. We just care about functioning of log here.
Abstraction can be thinks in terms of layers model where each layer perform some meaningful task. Each layer hide the implementation details of its below layer.
NOTE: All the programmes are written in scheme language.
Example: Let there are 3 programmers (Alice, Bob & Jack). Alice need to write a program to calculate sum-of-squares. Alice understand the meaning of sum but have no idea about square. Bob & Jack both understand square and can help Alice as below.
;; Bob square procedure approach(define (square x)
(* x x));;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Jack square procedure approach(define (double x)
(+ x x))(define (square x)
(exp (double (log x))));;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Alice can use any of the Bob or Jack codes(define (sum-of-squares a b)
(+ (square a) (square)))
- Alice can use any of the square method(Either Bob code or Jack code). Alice don’t care about the implementation of square procedure.
- Here square procedure work as a layer for sum-of-squares procedure. Sometime we call these layers as blocks or entities.
- More meaningful layer you create, more powerful abstraction you will build.
Section-II
Now we will look some problems & try to understand how abstraction can be useful to solve those problems.
Series arithmetics
Addition operations:
- Calculate 1 + 2 + 3 + 4 + ………n
- Calculate 1³ + 2³ + 3³ + 4³ + …….n³
- Calculate 1/(1*3) + 1/(5*7) + 1/(9*11) + ……….. = pi/8
Without abstraction
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b))))(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2)))
(pi-sum (+ a 4) b))))
Above 3 procedures clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the procedure, the function of a used to compute the term to be added, and the function that provides the next value of a.
The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be brought to the surface.
One level Abstraction
We could easily generate each of the above procedures by filling in slots in the same template:
(define (<name> a b)
(if (> a b)
0
(+ (<term> a)
(<name> (<next> a) b))))As program designers, we would like our procedure to be powerful enough so that we can write a singal procedure that expresses the concept of summation itself rather than only procedures that compute particular sums. We can do so readily in our procedural language by taking the common template shown above and transforming the ‘‘slots’’ into formal parameters:
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))Now we can define our above addition procedures in term of sum:
(define (identity x) x)(define (cube x) (* x x x))(define (inc x) (+ x 1)(define (pi-term x) (/ 1.0 (* x (+ x 2))))(define (pi-next x) (+ x 4));;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;(define (sum-integers a b)
(sum identity a inc b))(define (sum-cubes a b)
(sum cube a inc b))(define (pi-sum a b)
(sum pi-term a pi-next b))
Multiplication operations:
- Calculate 1 * 2 * 3 * 4 *………n
- Calculate 1³ * 2³ * 3³ *4³ *…..n³
In similar way we can write generic series product procedure for:
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))We can define individual series product procedure in terms of generic product procedure
(define (product-integers a b)
(product identity a inc b)) (define (product-square a b)
(product square a inc b))
If you notice sum and product are both special cases of a still more general notion called accumulate. Both are sharing some common pattern.
Two level abstraction
Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out.
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))Now we can define our sum and product in terms of accumulate.
(define (sum term a next b)
(accumulate + 0 term a next b))(define (product term a next b)
(accumulate * 1 term a next b))
Section-III
Earlier I have tried to explained square-root approximation. There we have way to just calculate square-root but we don’t want to stuck to only square-root. We need similar procedure to calculate cube-root, fourth-root or nth-root itself.
Since all approach will based on approximation(Keep improving guess until it is good enough) so all of them are going to share common pattern.
Finding fixed points of functions
A number x is called a fixed point of a fn f if x satisfies the equation f(x) = x. For some functions f we can locate a fixed point by beginning with an initial guess and applying f repeatedly until the value does not change very much. f(x), f(f(x)), f(f(f(x)))……
Using this idea, we can devise a procedure fixed-point that takes as inputs a function and an initial guess and produces an approximation to a fixed point of the function. We apply the function repeatedly until we find two successive values whose difference is less than some prescribed tolerance:
(define tolerance 0.00001)
(define (average a b) (/ (+ a b) 2.0))
(define (close-enough? a b)
(< (abs (- a b)) tolerance))
(define (fixed-point f first-guess)
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))Average damping
Average-damp is a procedure that takes as its argument a procedure f and returns as its value a procedure (produced by the lambda) that, when applied to a number x, produces the average of x and (f x).
(define (average a b) (/ (+ a b) 2.0))(define (average-damp f)
(lambda (x) (average x (f x))))
Now square-root and cube-root procedures can be defined in terms of fixed-point and average-damp
(define (sqrt x)
(fixed-point (average-damp (lambda (guess) (/ x guess)))
1.0))(define (cube-root x)
(fixed-point (average-damp (lambda (guess) (/ x (square guess))))
1.0))
Above method is the special case of newton-method.
Newton method
If x →g(x) is a differentiable function, then a solution of the equation g(x) = 0 is a fixed point of the function x →f(x) where
f(x) = x - g(x)/D g(x)Dg(x) is the derivative of g evaluated at x.
The derivative of the function x →x³ is the function x →3x². In general, if g is a function and dx is a small number, then the derivative Dg of g is the function whose value at any number x is given (in the limit of small dx) by
Dg(x) = [g(x + dx) - g(x)] / dxThus, we can express the idea of derivative as the procedure
(define dx 0.00001)
(define (deriv g)
(lambda (x) (/ (- (g (+ x dx)) (g x))
dx)))With the help of deriv-procedure, we can express Newton’s method as a fixed-point process:
(define (newton-transform g)
(lambda (x) (- x
(/ (g x)
((deriv g) x)))))(define (newton-method g guess)
(fixed-point (newton-transform g)
guess))
newton-method takes as arguments a procedure that computes the function for which we want to find a zero, together with an initial guess. For instance, to find the square root of x, we can use Newton’s method to find a zero of the function y → y² — x starting with an initial guess of 1. This provides yet another form of the square-root procedure:
(define (sqrt x)
(newtons-method (lambda (y) (- (square y) x))
1.0))One more level abstraction
We’ve seen two ways to express the square-root computation as an instance of a more general method, once as a fixed-point search and once using Newton’s method. Since Newton’s method was itself expressed as a fixed-point process, we actually saw two ways to compute square roots as fixed points. Each method begins with a function and finds a fixed point of some transformation of the function. We can express this general idea itself as a procedure:
(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))
(define (sqrt1 x)
(fixed-point-of-transform (lambda (guess) (- (square guess) x))
newton-transform
1.0))
(define (sqrt2 x)
(fixed-point-of-transform (lambda (guess) (/ x guess))
average-damp
1.0))nth-root
nth-root can be easily defined in terms of fixed-point-of-transform.
(define (nth-root x n)
(fixed-point-of-transform (lambda (guess) (/ x (expt guess (- n 1))))
average-damp
1.0))nth-root procedure provide another way to write sqrt and cube-root procedures:
(define (sqrt x)
(nth-root x 2))(define (cube-root x)
(nth-root x 3))
Conclusion:
As programmers, we should be alert to opportunities to identify the underlying abstractions in our programs and to build upon them and generalize them to create more powerful abstractions. This is not to say that one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task. But it is important to be able to think in terms of these abstractions, so that we can be ready to apply them in new contexts.
By Abelson & Sussman (SICP authors)
NOTE: Now we have seen the small power of procedure-abstraction. Later we will talk about data-abstraction and finally we will combine both procedure-abstraction and data-abstraction.
