Elements of Programming

Feb 21, 2017 18:20 · 500 words · 3 minutes read fundamentals programming sicp

The three things that a powerful computer language should have is:
1. Primitive expresssions: The simplest entities the language is concerned with.
2. Means of combination: How compound components can be made from smaller ones.
3. Means of abstraction: Creating new units that can be used in more complex structures.
In this text, I am using MIT-Scheme[a lisp variant] which is in-built in emacs. Scheme has a small set of primitives such as: +, /, * and so on.You can use these primitives to form primitive expressions like so:

(+ 74 23)

You can also use the key word define to form new abstractions. If you come from other programming languages, it can help to think of define as a way to create variables or make procedures[functions]. Here’s an example:

(define (cube x) (* x x x))

The general form of a procedure definition is:

(define (<name> <formal parameters>) <body>)

In scheme, there are other primitive expressions which help us to make conditional statements. They are if and cond. Here’s an example of their use:

(define (abs x)
	(cond ((< x 0) (- x))
		((= x 0) 0)
		((> x 0) x)))

This function can also be re-written using if as follows:

(define (abs x)
	(if (< x 0) (- x)
		x))

Here’s a summary of how they work:

(define (<name> <formal parameters>)
	(cond ((<condition1>)) (<execute if condition1 is met)
	(cond ((<condition2>)) (<execute if condition2 is met)
	)))
(define (<name> <formal parameters>)
	(if (condition1) (<execute if condition1 is met)
		<else execute this section>))

The substitution model

An interpreter needs a way to evaluate a combination whose operator names a compound procedure. This is where the substitution model comes in. It helps us think about procedure application[and not to provide the inner workings of the interpreter]. You can go further and classify this model into 2 types: Applicative Order and Normal Order.

Applicative Order

These steps are followed:
1. Evaluate the body of the compound procedure
2. Evaluate the corresponding arguments
Let’s take an example here. Assume a function f, sum-of-squares and square are defined as:

(define (f x)(sum-of-squares (+ x 1) (* x 2)) )
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (square x) (* x x))

The compound procedure (f 5) is evaluated as follows:

(sum-of-squares (+ 5 1) (* 5 2))
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36  100)
136

You can think of the applicative order as Evaluate the arguments adn then apply

Normal Order

In this model, the operands are not evaluated until the substitution process evaluates all the procedure bodies to the primitive operations. In other words, Full expand then reduce . Here’s an example using (f 5) which was defined above:

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)