SCIP 1.1: The Elements of Programming

Mix.install([])

1.1 The Elements of Programming

> We are about to study the idea of computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. (1)

Programming languages have three mechanisms for combining simple ideas to form more complex ideas:

• primitive expressions, which represent the simplest entities the language is concerned with
• means of combination, by which compoud elements are built from simpler ones
• means of abstraction, by which compound elements can be named and manipulated as units

There are two kinds of elements in programming:

• procedures: descriptions of the rules for manipulating data
• data: the stuff we want to manipulate

1.1.1 Expressions

Type an expression in an interpreter and it will respond with the result of its evaluating that expression.

486

An expression representing a number can be combined with an expression representing a primitive procedure to form a compound expression that represents the application of said procedure.

137 + 349

Combinations are expressions formed by a delimited list of expressions.

A combination will contain an operator and operands. The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

1.1.2 Naming and the Environment

A name identifies a variable whose value is the object.

size = 2
size * 5

A language’s convention for naming represents its simplest means of abstraction. define for Lisp, $ for PHP, var/const/let for JS, etc.

The interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment.

1.1.3 Evaluating Combinations

In order to evaluate a combination, we must perform the evaluation process on each element of the combination. Thus the evaluation rule is recursive in nature: to evaluate it must evaluate.

(3 + 5 + 7) * (2 + 4 * 6)

Recursion allows us to deal with hierarchal, treelike objects. The “percolate values upward” form of the evaluation rule is an example of a general kind of process known as tree accumulation.

To evaluate a combination, do the following:

1. Evaluate the subexpressions of the combination
2. Apply the procedure that is the value of the operator to the operands

graph TD;
  390-->*;
  390-->26
  390-->15
  26-->+
  26-->2
  26-->24
  15-->+_
  15-->3
  15-->5
  15-->7
  24-->*_
  24-->4
  24-->6

The exceptions to the general evaluation rule are special forms. Each special form has its own evaluation rule.

The various kinds of expressions (and associated eval rule) constitute the syntax of a programming language.

1.1.4 Compound Procedures

A procedure definition is a abstraction technique by which a compound operation can be given a name and then referred to as a unit.

(define (square x) (* x x))

We can read this as:

`(define (square     x)        (*      x      x     ))`
  |          |       |          |      |      |
  To      square something, multiply  it by itself

The special form for a procedure definition is:

(define([name] [formal params]) [body])

in which:

• name is a symbol to be associated with the procedure definition
• formal params are the names used within the body of the procedure to refer to the arguments of the procedure
• body is an expression that will yield the value of the procedure application when the formal params are replaced by the actual arguments.

1.1.5 The Substitution Model for Procedure Application

We can assume a basic evaluation mechanism of: To apply a compound procedure to arguments, evaluate the body of the procedure with each formal param replaced by the corresponding argument.

This is the Substitution Model for Procedure Application. The purpose is to help us think about procedure application, not to provide a description of how the interpreter really works. In practice, the “substitution” is accomplished by using a local environment for the formal parameters.

Let’s discuss two evaluation methods:

• Normal-Order Evaluation: “fully expand, then reduce”. Substitute operand expressions for parameters until an expression with only primitives is reached, and then evaluate
• Applicative-Order Evaluation: “evaluate the arguments, then apply”. Evalute the operator and operands and then apply the resulting procedure to the resulting arguments

For:

def square(x) do
  x * x
end
def sum_of_squares(x, y) do
  square(x) + square(y)
end

Normal-Order Evaluation

scheme

(sum_of_squares (+ 5 1) (* 5 2))
(+   (square (+ 5 1))      (square (* 5 2))     )
(+   (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2))  ) ; primitives reached, note the multipduplicated eval
(+   (* 6       6)         (* 10      10)       )
(+   36                    100                  )

elixir

sum_of_squares((5 + 1), (5 * 2))
square(5 + 1)       + square(5 * 2)
((5 + 1) * (5 + 1)) + ((5 * 2) * (5 * 2)) # primitives reached, note the duplicated eval
( 6      *  6)      + ( 10     *  10)
  36                +   100

Applicative-Order Evaluation

scheme

(sum_of_squares (+ 5 1) (* 5 2))
(sum_of_squares 6       10          )
(+   (square (6))        (square (10)) )
(+   (* 6 6)             (* 10 10)     )
(+   36                  100           )

elixir

sum_of_squares((5 + 1), (5 * 2))
sum_of_squares(6, 10)
square(6)  + square(10)
(6 * 6)    + (10 * 10)
36         +   100

1.1.6 Conditional Expressions and Predicates

A useful idiom is to be able to define tests and to perform different operations depending on the result of a test. This construct is case analysis. The form is:

(cond (([p1] [e1])
      ([p2] [e2])
      ([p3] [e3]))
      (else [e4]))

([p1] [e1]) is known as a clause. [p1] is known as the predicate. [e1] is the consequent expression. else is a special sumbol that can be used in place of the p as the final clause.

The word predicate is used for expressions or procedures that return true or false.

If there are precisely two cases in a case analysis, the special form if can be used:

(if [p] [c] [a])

[p] is known as the predicate. [c] is the consequent. [a] is the alternative.

Compound predicates can be constructed using logical operators:

(and [e1] [e2])
(or [e1] [e2])
(not [e])

and evaluates each expression left-to-right. If any expression is false, then the value of the and expression is false. If all evaluate to true, the value of the and expression is the final expression.

or evaluates each expression left-to-right. If any of the values of the expressions evaluate to true, that is the result of the or expression. If none of the expressions evaluate to false, then the or expression’s value is false.

Note that in scheme, and and or are special forms as not all expressions may need to be evaluated. not is an ordinary procedure.

1.1.7 Example: Square Roots by Newton’s Method

Mathematical functions are not identical to computer procedures. Procedures must be effective.

This contrast is a reflection of describing the properties of things vs. how to do things:

• Imperative: how to?
• Declarative: what is?

Mathematics is often concerned with declarative descriptions.

Computer science is usually concerned with imperative descriptions.

1.1.8 Procedures as Black-Box Abstractions

A computation can be broken down into several subproblems. Each of these tasks is achieved by a different procedure.

Each procedure should accomplish an identifiable task. Procedural abstraction allows you to use a procedures without concern for how, but what they do.

The meaning of a procedure should be independent of the parameter names used by its author. Parameter names must be local to body of the procedure.

Bound Variable: a formal parameter of a procedure that is bound by the procedure definition.

Free Variable: an unbound variable.

Scope: the set of expressions for which a binding defines a name.

Block Structure: a nesting of definitions, so that local subprocedures can be internalized by the procedure.

Lexical Scoping: free variables in a procedure are taken to refer to bindings made by enclosing procedure definitions.