Tuesday, August 3, 2010

My definition

Here's my definition:
A computer program is a description of a process which is formal enough to be carried out by a machine.
Most of the other definitions describe a program as a ‘set of instructions’. Some of the definitions suggest that these instructions should be organized in some way, perhaps as a (linear) list. These instructions ‘make the computer do things’, ‘bring about a certain result’, ‘cause the computer to behave in a predetermined manner’, or ‘alter the contents of memory’. But these definitions have an explicit or implicit assumption: a sequential, imperative mode of thought.

Look at this Prolog code:
append(c(H,T), B, c(H,TB)) <= append(T, B, TB).
append(nil, B, B).
This code describes relationship of appending lists, but it doesn't specify how to accomplish the appending. Is the first clause an ‘instruction’ to build a list, or to take one apart? Are the clauses to be run in any particular order? Is there a deterministic ‘answer’?