High-order Procedures

Most modern programming languages provide certain abilities to blur the traditional distinction between ``passive'' data and ``active'' process, one of the most well-known techniques might be so-called OOD, i.e., Object Oriented Design. Languages such as Lisp in traditional way provide programmers the power to handle precedures as data, which pioneered a new programming flavor called Functional Programming, or, FP in short (Now some FP languages also implemented OO facilities). Procedures that manipulate procedures are called higher-order procedures.

Put aside the consideration of efficiency, we can implement some atomic operations such as cons, car and cdr like following:

(define (cons x y)
  (lambda (f) (f x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

Here, cons just returns a procedure which takes x and y as parameters. car and cdr applies the procedure constructed above with parameter (a procedure) which returns the former and latter parameter, respectively.

Generator

Languages like Python, Ruby provide a keyword `yield' to help build a generator. It's really convenient for programmers who hate C-style static local variables, which indicates not thread-safe. For example:

def sequence(start):
  current = start
    while True:
      yield current
      current = current + 1

#Create a new sequence generator starting at 1
generator_func = sequence(1)
print generator_func.next() #prints 1
print generator_func.next() #prints 2
print generator_func.next() #prints 3

Languages support functional programming needn't craft a `yield' keyword (most of them support another more general mechanism named `continuation'). We can easily build a generator like above use Scheme:

; helper procedure to construct a simple generator
(define (make-iter start step)
  (lambda ()
    (let ((old start))
      (begin (set! start (+ start step))
          old))))

; a generator which starts from 1 and steps 1 on each accumulation
(define sequence (make-iter 1 1))

(sequence) ; evaluates 1
(sequence) ; evaluates 2
(sequence) ; evaluates 3

Fast Exponential

Generally, we can compute exponentials in a linear-recursive way.
For example: exp(b, n) = b * b * ... * b which requires n steps.

But there is a faster approach which makes use of successive squaring, for instance, to compute exp(b, 8):
b^2 = b * b
b^4 = b^2 * b^2
b^8 = b^4 * b^4

This method needs only 3 steps instead of 8, and works fine or exponents that are powers of 2. Of course we can expand this to general usage with the help of the following rules:
b^n = (b^(n/2))^2 if n is even;
b^n = b* (b^(n-1)) if n is odd.

So, we can compute exp(b, n) with time complexity costs O(logn) rather than O(n).

Inspired by this method, you can even find a cleverer algorithm to compute the Fibonacci numbers in a logarithmic number of steps.

Some Lessons

There are some important ideas in algorithm and program design:

1. There is more than one way to do it.
   Your first task is to find a correct algorithm. After that, strive for clarity,simplicity, efficiency, scalability and elegance. Good algorithms and programs are like poems of logic. They are a pleasure to read and maintain.
2. Be the computer.
   Grand Master Turing once dreamed that he was a machine. When he awoke he exclaimed: "I dono't know whether I am Turing dreaming that I am a machine, or a machine dreaming that I am Turing!"
3. Generality is good.
4. Don't reinvent the wheel.
   As you are learning to program, designing from scratch is great experience. Truly expertprogrammers, however, know when to borrow.
   

-- 7.5.5 Some Lessons

Science is organized knowledge. Wisdom is organized life.
-- Immanuel Kant

What is Computer Science?

You might be suprised to learn that computer science is not the study of computers. A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy. The computer is an important tool in computer science, but is is not itself the object of study. Since a computer can carry out any process that we we describe, the real question is What process can be describe? Put another way, the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question. The three main ones are design, analysis, and experimentation.
-- Python Programming: An Introduction to Computer Science, section 1.3