Introduction to Programming Languages

A powerful programming language serves not merely as a tool for instructing computers, but as a framework for organizing thoughts about computational processes. Effective languages provide three essential mechanisms: primitive expressions, means of combination, and means of abstraction.

When approaching a programming language, we must consider what we need to process. In computer science, we deal with two fundamental concepts: procedures and data. Procedures describe the rules for manipulating data, while data represents the material we process.

Basic Elements: Expressions and Prefix Notation

Let's examine how expressions work in Scheme, a Lisp dialect. An expression represents something we need to evaluate.

(+ 3 4 3)
10
(- 2 1 1)
0
(* 2 2)
4
(/ 10 5 2)
1
(mod 5 6)
5

A combination assembles multiple expressions together. Scheme employs prefix notation, where operators appear before their operands. This approach offers distinct advantages: operators can accept any number of arguments, and nested expressions remain clear and unambiguous.

Definitions and Environments

The define keyword enables us to bind names to values, creating what we call definitions:

(define size 4)
(+ 3 size)
7

(define (multiply a b c)
  (+ (+ 3 a) (+ b 3)))
(multiply 5 6)
17

The definition form follows: (define (procedure-name parameters) body).

An environment establishes mappings between variable names and values or storage locations. We distinguish between global environments and local environments. Global variables remain accessible throughout the entire program, while locall variables exist only within specificc scopes—typically within functions.

Linear Recursion

Recursion represents a fundamental computational approach where a procedure calls itself during execution. Consider computing exponentiation:

(define (power base exponent)
  (if (= exponent 0)
      1
      (* base (power base (- exponent 1)))))

(power 4 5)

The evaluation proceeds as follows:

(* 4 (power 4 4))
  (* 4 (* 4 (power 4 3)))
  (* 4 (* 4 (* 4 (power 4 2))))
  (* 4 (* 4 (* 4 (* 4 (power 4 1)))))
  (* 4 (* 4 (* 4 (* 4 (* 4 (power 4 0))))))
  (* 4 (* 4 (* 4 (* 4 (* 4 1)))))
  (* 4 (* 4 (* 4 (* 4 4))))
  (* 4 (* 4 (* 4 16)))
  (* 4 (* 4 64))
  (* 4 256)
  1024

This pattern demonstrates linear recursion, where each recursive call reduces the problem size by one until reaching the base case.

Iteration

Recursive approaches, while conceptually straightforward, often perform redundant computations. Iteration provides an alternative that avoids this inefficiency:

(define (power base exponent)
  (define (iterate accumulator count)
    (if (= count 0)
        accumulator
        (iterate (* accumulator base) (- count 1))))
  (iterate 1 exponent))

(power 4 4)

The evaluation sequence:

1. (iterate (* 1 4) (- 4 1))
2. (iterate (* 4 4) (- 3 1))
3. (iterate (* 16 4) (- 2 1))
4. (iterate (* 64 4) (- 1 1))
Result: 256

This implementation demonstrates iteration—specifically linear iteration—where state variables update progressively until reaching the final result.

Recursion and iteration represent different computational mindsets. Recursion offers clarity in structure but produces complex call stacks. Iteration aligns more closely with sequential intuition, maintaining a simple state that transforms incrementally.

Evaluation Orders: Applicative vs Normal Order

Scheme employs applicative order evaluation, where arguments get evaluated before procedure application. Consider (1+ (1+ 3)):

• Applicative order evaluates (1+ 3) first, yielding 4, then computes 1+ 4 = 5
• Normal order (lazy evaluation) would substitute first: 1+ (1+ 3) = 1+ 4 = 5

Most procedural languages utilize applicative order because it avoids redundant re-evaluation. However, lazy evaluation can provide efficiency gains when some values might never be needed.

Conditional Expressions

The cond construct handles multiple conditions elegantly:

(define (classify value condition)
  (cond ((> condition 0) 1)
        (else value)))

Each condition pair follows the form (test result). Evaluation proceeds sequentially until a true test is found.

Logical Operators

Scheme provides three logical operators for combining conditions:

• and: Evaluates sequentially; returns false upon encountering false, otherwise returns the final value
• or: Evaluates sequentially; returns true upon encountering true, otherwise returns false
• not: Inverts the boolean value

(and condition1 condition2 condition3)
(or condition1 condition2 condition3)
(not condition)

Procedures as Black Boxes

Procedures should function as black boxes—users need not understand internal implementation, only their behavior. Abstraction manages complexity by allowing us to focus on what a procedure accomplishes rather than how it achieves the result.

(define (square x) (* x x))
(square 4)
16

Users simply need to know that (square 4) yields 16, without understanding the multiplication operation beneath.

This principle of procedural abstraction enables complex systems to remain manageable by ignoring unnecessary details.