IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

Question

_{The following is what I came up with from my synthetic prior research but I might be wrong.}

I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features:

• Internal implementation: Everything from start to end, including possible functions and possible sub functions
• External interface: A parameter set with which arguments might correspond in execution or call → if any

Internal implementation includes:

• Data structures: Primitive data types and possibly also functions or modules (depends what term one prefers)
• algorithms: outside or inside a function/algorithm → if any
• Database interfaces → if any

I understand that external interface (very often represented by parenthesis) can be part of internal implementation (which, in programming languages, is very often represented by brackets) and that yes or no depends from language architecture.

IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

Answer 1

Computer Science is far too diverse to have a single notion of program. For a theoretician, it might be an input tape to a universal Turing Machine, or any lambda expression in lambda calculus. For someone working on the front end of a compiler, it could be defined by a formal grammar while for someone working on the back end, or to the HW architect, it might be a sequence of binary instructions. For someone working on operating systems, it might be any file with the executable bit set.

Perhaps it could be said that a unifying theme is any form of information that can used to control the operation of a process, or an abstract or real machine, to produce information in the same or different form.

For some, I’m sure this will be too broad, for others, too narrow.

Answer 2

This is not IMO a 'computer science' matter. A 'program' is necessarily expressed in a particular programming language, whether that's a programming language with an implementation on a computer, or a 'mere' logical formalism.

The particular language will tell you what a program is. Which means that it's a grubby implementation issue, not a pristine question of science. (I'm a rude mechanical so I'm ok with that).

For example, for Algol 60

<program> ::= <block> | <compound statement>

and therefore (if you chase the definitions down) the minimal Algol 60 program is just a pair of statement brackets:

begin end

Contrariwise, in Algol 68 as far as I recall a particular-program needs to be a block, so a declaration is needed:

begin int k end

Your implementer may add additional requirements.