Building Abstractions with Procedures

Building Abstractions with Procedures

The Elements of Programming

Programming languages not only serve as a means to instruct computers to perform tasks, but also serve as a framework within which programmers can organize ideas about processes.
Every powerful language has three mechanisms for combining simple ideas to form more complex ideas:
- Primitive expressions, representing the simplest entities the language is concerned with
- Means of combination, by which compound entities are built from simpler ones
- Means of abstraction, by which compound elements can be named and manipulated as units.
Lisp interpreters operate in a read-eval-print loop, wherein an expression is read, evaluated and outputs the result.

486 ; A number, which is a primitive expression in Lisp

(+ 137 349) ; A combined expression, made up of a list of expressions
  ; The leftmost element (+) is the 'operator'
  ; The other elements are 'operands'
  ; The value of a combination is obtained by applying the procedure specified by the operator to the 'arguments' (the values of the operands)

(+ (* 3 5) (- 10 6)) ; A nested combination. A combination whose elements are themselves combinations.
  ; Subcombinations are evaluated first

(define size 2) ; Creates a variable `size` associated with the value 2

(define (square x) (* x x)) ; Defines a procedure 'square'
(square 21) ; Invocation of our defined procedure

Substitution model for procedure application / Applicative Order: A model for procedure application. First the operands are evaluated, followed by evaluation of the operator to get the procedure to be applied, e.g.:

(sum-of-squares (+ 5 1) (* 5 2)) ; User provided invocation
(sum-of-squares 6 10) ; Step 1: Operands are evaluated
(+ (square 6) (square 10)) ; Step 2: Operator is evaluated to get the procedure to be applied.
(+ (* 6 6) (* 10 10)) ; Step 3: Operators of the operands are evaluated to get the subprocedures to be applied
(+ 36 100) ; Step 4: Operands are fully evaluated. Expression is now de-nested
136 ; Final result of user provided invocation

Normal Order: Expressions are fully expanded and then reduced, e.g.:

(sum-of-squares (+ 5 1) (* 5 2)) ; User provided invocation
(+ (square (+ 5 1) (square (* 5 2)))) ; Expanding step 1
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2))) ; Expanding step 2
(+ (* 6 6) (* 10 10)) ; Reducing step 1
(+ 36 100) ; Reducing step 2
136; Reducing step 3

Lisp uses applicative-order evaluation in most cases for efficiency reasons (note how in the normal order example (+ 5 1) had to be redundantly evaluated twice to reduce the expression)

Conditionals

(define (abs x)
  (cond ((> x 0) x) ; If x > 0, resulting expression is 'x'
        ((= x 0) 0) ; If x = 0, resulting expression is '0'
        ((< x 0) (- x)))) ; If x < 0, resulting expression is '-x'
; A cond is made up of clauses, e.g. ((> x 0) x), which are made up of predicates and consequent expressions.
; A cond will evaluate by going through the list of clauses. If a predicate is found to be true the cond will evaluate to that clause's consequent expression.

(if (> x 0) x (- x))
; Restricted form of conditional used when there are precisely two cases in the case analysis.
; If the predicate is true, this expression evaluates and returns the consequent (x)
; If the predicate is false, the expression evaluates and returns the alternative (- x)
; Note that unlike cond, if uses normal-order evaluation. The consequent and alternative won't be evaluated unless they're being used for the return value.

Predicate constructors

(and predicate1 predicate2 ... predicateN)
(or predicate1 predicate2 ... predicateN)
(not predicate)

Procedures and the Processes They Generate

Procedure: Pattern for the local evolution of a computational process.
Recursive Processes: A process characterized by a chain of deferred operations that builds up and contracts.
Linear Recursive Processes: Processes in which the length of the chain of deferred operations (and thus the amount of information required to keep track of it), and the number of steps required, grows linearly with n.
Linear Iterative Processes: Processes in which the length of the chain of operations is constant throughout the process, and the number of steps grows linearly with n.
In general, an iterative process is one whose state can be summarized by a fixed number of state variables together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate.
Recursive Procedure: A procedure that refers to itself at some point in the body.
Tail-Recursive Procedure: A procedure whose final step is a non-nested invocation of itself. In Lisp tail-recursive procedures will generate iterative processes that maintain constant space.
Tree-Recursive Process: A process which, as it evolves, branches out into multiple chains of deferred operations. The number of steps grows exponentially with the input and the space required will be proportional to the maximum depth of the tree. Generated by procedures that invoke themselves more than once when executing.

Orders of Growth

Orders of Growth: Gross measure of the resources required by a process as the problem size (denoted by n) become larger.
Constant time: Doubling the problem size does not affect resource utilization. Θ(1)
Linear growth of a process: Doubling the problem size multiplies resource utilization by a constant factor. Θ(n)
Logarithmic growth of a process: Doubling the problem size increases resource utilization by a constant amount. Θ(log n)

Formulating Abstractions with Higher-Order Procedures

Procedures are abstractions that describe compound operations on primitives independent of the particular values. Give a language the ability to not only perform an operation but express the concept in abstract.
Higher-Order Procedures: Procedures that manipulate procedures.
The presence of a common pattern in multiple procedures, where the procedures could be generated simply by filling in slots in one template, indicates that a useful abstraction could be extracted and used.
Anonymous procedures can be expressed in Lisp using (lambda (<formal-parameters>) <body>).
- Lambda functions can be immediately invoked using ((lambda (<formal-parameters>) <body>) <arguments>), the same way you'd invoke a name function but replacing the name with the definition.
Anonymous functions can create local variables by the use of the syntactic sugar expression let. The first part of a let is a list of name-expression pairs. When let is evaluated, each name is associated with the value of the corresponding expression. The body of the let is evaluated with those names bound as local variables. Usage:

(let ((<var1> <expression1>)
      (<var2> <expression2>))
    <body>)

Using let allows one to bind variables as locally as possible to where they are used.
First-class elements: Elements with the fewest restrictions on their manipulation in a programming language. Some 'rights and privileges of first-class elements are:
- They may be named by variables
- They may be passed as arguments to procedures
- They may be returned as the results of procedures
- They may be included in data structures
In Lisp, procedures have first-class status