Topic: programming as mathematics

topics > computer science > programming > Group: program representation

program proving

algorithmic complexity analysis
automated tests of specifications and designs
evaluation in an environment
expression language
formal methods and languages
functional programming
lambda calculus
machine independent programming
no need for efficiency
predicate transforms
programming without errors
reduction machines
set-oriented languages
specification is infeasible
symbolic manipulation of formulas
transformation of programs
what is a computer


The academic view of programming is that it is a part of mathematics. The champion of this view is Dijkstra with the support of many others. The hope is that a formal approach will handle the massive detail of programming without ad hoc methods and trial and error. Dijkstra even thinks that it will lead to a superior means of thought.

Mathematical approaches emphasize expressions over procedure. Ideally a program is an expression from one domain into another domain. At least a program satisfies a post-condition whenever its input satisfies a pre-condition. Programming languages may have a strong mathematical flavor.

Unfortunately, the real world doesn't fit into this mold. Programs in daily use are large and complex. Except in the scientific and numeric methods domains, programs tend to use very simple statements and unsophisticated algorithms. There are many special cases, and understandability is more important that formality. (cbb 4/94)

Subtopic: programming is mathematical up

Quote: mathematics is what programming becomes when freed of all considerations of efficiency [»schwJT_1972]

Subtopic: programs are mathematical up

Quote: procedural programs are mathematical expressions subject to a set of laws [»hoarCA8_1987]
Quote: computer programs are mathematical expressions of behavior, but they are not treated as such in practice [»hoarCA8_1986]
Quote: a program is an elaborate formulae for some formal system; made concrete by a computer [»dijkEW12_1989]
Quote: the purpose of a computer is to execute our programs, not vice versa [»dijkEW3_1976]

Subtopic: program with mathematics up

Quote: with a programming language, deal with mathematical integers instead of bit-patterns and addresses [»straC3_1973]
Quote: mathematical functions are a good foundation for sequential computation; nothing comparable for concurrent programming [»milnR1_1993]

Subtopic: formality and correctness up

Quote: formality is important in programming because of the large amount of detail which must be absolutely correct [»grieD_1981]

Subtopic: concise, formal notation up

Quote: by not using concise, formal notation, many authors exceed the five-line limit and introduce too much complexity

Subtopic: mathematical definition of language up

Quote: a programming language should have a complete, mathematical, definition independent of a compiler or computer [»wirtN3_1976]

Subtopic: symbolic calculation up

Quote: computing science may provide symbolic calculation that is better than human reasoning; Leibniz's dream [»dijkEW12_1989]
Quote: never anthropomorphize programs or equipment; think of programs in terms of computational behavior based on a model [»dijkEW12_1989]

Subtopic: symbol strings vs. abstract objects up

Quote: programming languages deal with abstract objects, contrary to the conventional view that programs are symbol strings plus rules for manipulating these strings; the later yields a macrogenerator without regard to semantics [»straC8_1967]

Subtopic: values vs. steps, expressions up

Quote: the world of expressions is orderly, has useful algebraic properties, and performs most useful computation [»backJ8_1978a]
Quote: "mathematical" approach to programming considers values of expressions instead of the steps that produced them [»straC3_1973]
Quote: a language is a mapping between expressions and a domain of discourse; if a function, the meaning of an expression is its consequent [»backJ_1973, OK]
Quote: a program is a partial function from initial states and valid inputs to possible ending states [»parnDL8_1983]
Quote: a program is a nondeterministic mechanism that changes the state of the machine it controls

Subtopic: mathematical language for algorithms up

Quote: simplified the semantics of Dijkstra's mini-language, while increasing its expressiveness [»redeDH7_1979]
Quote: a set of laws for types of algorithmic control; e.g., A*.A = A.A* (both sequences of A) [»kapoAA1_1978, OK]
Quote: 'A*' for repetition, 'A.B' for sequence, 'A+B' for selection, 'K:=U' for definition of K [»kapoAA1_1978]
QuoteRef: takaH1_1980 ;;62 "Condor is founded on circuit theory, i.e., a Condor program corresponds to a clock-free Boolean equation system and the like.

Subtopic: programming is not math up

Quote: programs are inevitably richer than their mathematical description; e.g., integer data type is not the same as a mathematical integer [»weisM11_1987]
Quote: mathematics and expression languages are poor models for programming [»cbb_1980, OK]
Quote: the need for user testing demonstrates that rational analysis is not sufficient for system design [»goulJD3_1985]
Quote: most practical programming doesn't involve much mathematical theory; contradicts computer science education [»boreNS_1991]
Quote: little agreement about the effectiveness of formally complete descriptions of Turing's universal machine

Related Topics up

Group: algorithms   (6 topics, 94 quotes)
Group: formalism   (9 topics, 478 quotes)
Group: mathematics   (23 topics, 560 quotes)
Group: program proving   (10 topics, 311 quotes)
Group: programming   (339 topics, 10149 quotes)

Topic: algorithmic complexity analysis (10 items)
Topic: automated tests of specifications and designs (12 items)
Topic: evaluation in an environment (35 items)
Topic: expression language (14 items)
Topic: formal methods and languages (53 items)
Topic: functional programming (45 items)
Topic: lambda calculus (16 items)
Topic: machine independent programming (13 items)
Topic: no need for efficiency (28 items)
Topic: predicate transforms (7 items)
Topic: programming without errors (28 items)
Topic: reduction machines (14 items)
Topic: set-oriented languages (20 items)
Topic: specification is infeasible (46 items)
Topic: symbolic manipulation of formulas (12 items)
Topic: transformation of programs (27 items)
Topic: what is a computer
(62 items)

Updated barberCB 11/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.