Scheme Note

Recently I am playing with some scheme code, here's some introduction and code snippet about it.

What is Scheme?

Scheme is a pure functional programming language that was developed by MIT media lab.
The design philosophy of scheme is, rather than provide more features, it's more important to provide elegant core functions, minimize the weak points and restriction of the languages.(which is: less is more)

A functional programming language, as the name, is a language that treat function as first level primitive. In functional language, you can pass and return function as variable, the program in functional language is constructed by multiple recursive function call.

for example, a for loop iterate a data array in structure language is like:

int[] a = [0,1,2,3,4]
for (int i = 0 ; i < 5 ; i++){
  print(a[i]);
}
// 01234

in scheme you have to define a for-each loop like this and pass the function:

(define each (lambda (list proc)
  (if (not (null? list))
      (begin
        (proc (car list)) ; car : get first element of list
        (each (cdr list) proc) ; cdr : get the rest of list except the first element
      )
)))

(each '(0 1 2 3 4) write) ; pass the function "write" to execute on each element
; 01234

In functional language, a function is more like a logic unit, take inputs and return output, it's more close to the function in Mathematic. Therefore, a function will not have any side effects and dependencies, which make it very easy to test and reuse.
Another good part in functional language is lazy-evaluation. The function passed will only executed when it's needed to, for example, a program in structure programming like:

print(db.read());

Will call the read() function and save in memory before print, but in functional language, the function call is strict synchronization:

(print (read db ))

The read function will only perform when print function is going to print, and only read the data that is needed to print, if the print function abort, the read will not be executed. In this way, the function call can be integrated and optimized. Also, because the only things effect function output is the input, so we can easily save the results of function and reuse it. In Scheme, you can call the "delay" function to cache the results of function output: http://www.ibm.com/developerworks/linux/library/l-lazyprog.html

functional language is mainly used on science, math ,AI and financial area,

the functional language on the block included: scheme, haskell, f#, clojure and more.

more information about fp:
why fp matter
why fp matter matter

Getting Started

Racket is a good implementation and IDE for scheme, it's more friendly then MIT-Scheme, you can install it and choose the language as "R5RS" which is the newest version of scheme implementation.

snippets

get last element or list:

(define last (lambda (list) 
             (if (> (length list) 1) 
                 (rac(cdr list)) 
                 (car list) 
             )))

fibonacci:

(define fib (lambda (level)
            (if (< level 2) 
                 level
                 (+ (fib(- level 1)) (fib (- level 2)) ) 
            )))
; dynamic programming version
(define (fib-dym level) 
        (let fib ((base0 0) (base1 1) (n level))
        (if (< n 1)
            base0
            (fib base1 (+ base0 base1) (- n 1)))))

quick sort:

(define (partition pivot num-list)
  (if (null? num-list) '(()()) 
      (let ((split-of-rest (partition pivot (cdr num-list)))) ;split of rest is a 2 way list:((first...) ( second...))
        (if (< (car num-list) pivot)
            (list (cons (car num-list) (car split-of-rest)) ;put x into first list
                  (cadr split-of-rest))
            (list (car split-of-rest) ;put x into second list
                  (cons (car num-list)(car (cdr split-of-rest))))
            ))))

(define (quicksort num-list)
  (if (<= (length num-list) 1) num-list
      (let ((split (partition (car num-list) (cdr num-list))))
        (append (quicksort (car split)) ;smaller
                (list (car num-list))   ;pivot
                (quicksort (cadr split) ;larger
                           )))))

simple test function:

(define test (lambda (case expr ) 
                 (begin
                 (if (eqv? expr #t) 
                     (write (cons case "complete" ))
                     (write (cons case "failed" ))
                 ) (newline)
                 )))
;execute testCase:
(test "fib is fibonacci function:" (equal? (fib 8) 21) )