0x340 Foundation


The Elements of Programming

  • primitive elements: represents the simplest entities the language is concerned
  • means of combination: by which compounded elements are built from simpler ones
  • means of abstraction: by which compounded elements can be named and manipulated as units

Declarative vs. Imperative

In Mathematics, we are usually concerned with declarative (what is) descriptions, whereas in computer science we are usually concerned with the imperative (how to) descriptions.

For example, the following square mathematical description is declarative, i.e. what properties square has, but gives no clue how to compute it

$$\sqrt(x) = \{ y | y \geq 0 \land y^2 = x \} $$

In contrast, procedure (imperative) description (e.g. Newton methods) can specify how to compute square root.

Normal order vs Applicative Order

Lisp uses applicative-order evaluation, i.e. interpreter evaluates the operator and operand and then applies. The alternative is normal-order evaluation which the interpreter fully substitutes to expand and then reduce.

Recursive Process vs. Iterative Process

The recursive process expands the procedure by chaining deferred operations

The iterative process keep their info in state variables (in arguments) and call itself using tail-recursive (which can be optimized without adding new stack frame in some languages including Scheme, C looks like not require it)

A good technique to design iterative algorithms is to define an invariant quantity that remains unchanged from state to state (SICP exercise 1.16)

First-class Citizen vs Second-class Citizen

An element is called the First-class citizen in one programming language if it supports most operations available to other elements with the fewest restrictions.

Some properties of the first-class citizens 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

For example, array in C language is not first-class because array loses its size when passed to a procedure. Lisp unlike other common languages, awards procedures full first-class status.


Prefix Notation vs Postfix Notation

Prefix notation (Polish Notation): Operator comes before the operands. Lisp is this style

Postfix Notation (Reverse Polish Notation): Operator comes after the operands. It is similar to SOV languages (e.g. Japanese). PostScript is this style.



The followings are Kernighan’s summary about successful languages

Why languages succeed?

  • solve real problems in a clearly better way
  • culturally compatible and familiar
  • environmentally compatible
  • weak competition
  • good luck!

Why languages fail to thrive?

  • niche or domain disappears
  • poor engineering
  • poor philosophical choices


[1] Abelson, Harold, and Gerald Jay Sussman. Structure and interpretation of computer programs. The MIT Press, 1996.

[2] Brian Kernighan on successful language design https://www.youtube.com/watch?v=Sg4U4r_AgJU&t=2501s