0
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ One instruction. "10: BR 10" is a program. $\endgroup$
    – user115736
    Feb 19 '20 at 2:46
  • 4
    $\begingroup$ @another-dave I've got you beat with the 1994 IOCCC winner for worst abuse of the rules. The "world's smallest self-replicating program" is zero bytes long and (with a suitable Makefile) compiles to an executable that prints nothing and exits. $\endgroup$ Feb 19 '20 at 3:03
  • $\begingroup$ I believe that computer memories often contain executing programs, essentially a sequence of bits, and there are no 'brackets' involved in the representation of such programs. What, then, is the distinguishing feature of programs this question is concerned with? $\endgroup$
    – user115736
    Feb 19 '20 at 12:43
  • $\begingroup$ @another-dave you are write about the brackets, of course ;;; I confused human readable source code with machine code... $\endgroup$
    – user115711
    Feb 19 '20 at 12:47
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Formal CS is in many ways more concerned with what an algorithm or (computable) function is, I suppose. But then, in compiler/interpreter/language theory, we are interested in what a program is and how to model it! $\endgroup$ Feb 19 '20 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy