Functional programming with scheme

Why learn Scheme?

Main goal of learning functional programming is to better understand JavaScript and to have fun! We will be using Scheme (dialect of LISP) as a tool that will help us with this learning process. Scheme is not so popular programming language as JavaScript is. It is mainly well know inside university circles where it is usually used for some research in artificial intelligence. It is pure functional language what JavaScript off course is not, but it can be. That is beauty of JavaScript language. It can behave similar like object oriented language with code reuse pattern like inheritance and composition and in same time also as functional language. If you really want to learn JavaScript then previous knowledge is some functional language cannot hurt!

So anyway I'm start reading Structure and Interpretation of Computer Programs. One of the "must read" book for programmer. So lets see what this master peace has to offer.

And right on the foreword to this book I found some great comparison: "Pascal is for building pyramids -- imposing, breathtaking, static structures built by armies pushing heavy blocks into place. Lisp is for building organisms -- imposing, breathtaking, dynamic structures built by squads fitting fluctuating myriads of simpler organisms into place." Wow! Now I must read this book!

I did use Scheme at my university, but as year passed I can only remember basic stuff, so this will be great opportunity to refresh some of my knowledge.
Did you know that JavaScript has much in common with Scheme. Seems too odd, please see this link The Little JavaScripter. Douglas Crockford is one of the old gurus of JavaScript. Why they choose to build some part of JavaScript language similar to Scheme? My opinion is because Scheme is simple and concepts are natural. And there no much stuff going around you need to remember (like data types, pffff). So if you know Scheme it can be easier to understand some of JavaScript concepts. And I hear voices that this language (JavaScript that is) is becoming more and more important.

You can download MIT working Scheme interpreter, compiler, source-code debugger and what more not from here. Also you can download another scheme editor/interpreter named (recommended -- because it is more simple then MIT emacs environment) Racket (formerly know as DrScheme).

Language basics

In functional language you type expression and the compiler gives evaluation of that expression. Here are examples of rudimentary expressions in Scheme:

; expression
1586
; value of expression (evaluation) : 1586

; combination 
(+ 15 7)
; val: 22

(/ 12 3 4)
; val : 1

Combinations are expressions with within parentheses in order to denote procedure application. You can notice here that Scheme uses prefix notation which can look somewhat odd, but it have sever advantages over normal mathematical notation (operand-operator-operand). Firstly it enables procedures to capture arbitrary number of arguments and secondly it extends in straightforward way in allowing combination to be nested like in this example:

(+ 3 
   (* 2 3 5 
      (+ 2 1) 
      (- 8 1)) 
   (+ 3 1))

It is quite interesting that it is not necessary to explicitly instruct the interpreter to print the value of expression. Not like in Java where you explicitly must use System.out.println to print value of variable, here you know value of expression in every point. OK this is not so good comparison, but hopefully you get the point. :) In functional language any output from function can be input to another or can be printed to standard output.

For simple form of abstraction we use define keyword. It provide means for using names to refer to computational objects (variables). For example (semicolon represent comment):

; Use 'define' to identify variable PI and give it value. 
(define PI 3.14)
; Identify procedure for calculating area of circle.
(define (area r) 
  (* (* r r) 
     PI))
; run it
(area 5)

You can see that define also enables us to identify procedures (procedural definition) which is powerful form of abstraction by which a compound operation can be given a name. We refer to this kind of abstraction procedural abstraction and it help us suppressing details of procedure implementation and looking at procedure as black box.

You can see that procedure have parameters (these are formal parameter) and we say that procedure binds these formal parameters. In procedure definition the bound variables declares as formal parameters of the procedure have the body of the procedure as their scope. This means that names of formal parameters are "understand" only inside of procedure and are not defined outside of procedure body. But not all variables are binds (binds to the concrete procedure and are mining less outside that procedure...) to procedure. There can also be free variables. Free variables (such as +, -, *, /, pi, our defined PI and so on). Free variables are not bound. If we use free variable names as our procedure formal parameter we will then capture free variable name (binding it to current procedure we are defining) and by that we will introduce unexpected behavior and errors.

Here are some self explanatory examples of some procedure and variable definitions:

; Simple atomic operation (in this case +).
(+ 5 8 9 7 5 1 5 15)
; 55

; Nested combinations.
(+ (* 3 4) (- 4 6))
; 10

; Simple abstraction of variable.
(define a 3)
(define b 8)
(+ a b (- a))
; 8

; Calculate distance between two points.
(define (distance x1 y1 x2 y2) 
  (sqrt (+ (* (- x2 x1) (- x2 x1))
           (* (- y2 y1) (- y2 y1)))))
(distance 2 2 4 4)
; 2.828...

Every programming language must be able to define conditional expressions. In Scheme we use symbol cond followed by parenthesized pairs of expressions called clauses for conditional expressions. The first expression in each pair is a predicate - that is an expression whose value is interpreted as true or false.

(define (signum x)
  (cond ((> x 0) 1)
        ((= x 0) 0)
        ((< x 0) 0)))
(signum (- 3))
; value: 0

In previous example you can see definition of signum (sng) function using simple conditional expressions. It is straightforward how this function works. It evaluates predicates until it found one which evaluates to true. We can also use else in Scheme. Like in following example (calculation of absolute value):

(define (absolute1 x)
  (cond ((< x 0) (- x))
        (else x)))
(absolute1 456)
; values: 456

(define (absolute2 x)
  (if (< x 0)
      (- x)
      x))
(absolute2 456)
; value: 456

Here I also throw one example with special if form which is restricted type of conditional expressions that can be used when there are precisely two cases in the case analysis.