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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ One instruction. "10: BR 10" is a program. $\endgroup$
    – user115736
    Feb 19, 2020 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$
    – Aaron Rotenberg
    Feb 19, 2020 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, 2020 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, 2020 at 12:47

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\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$
    – D. Ben Knoble
    Feb 19, 2020 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.