5

From Structured Computer Organization by Tanenbum

A program is a sequence of instructions describing how to perform a certain task.

  • When trying to see a programming language as a formal languages added with semantics, I heard that a programming language is a set of valid programs (valid according to the syntax and other aspects of the language).

  • When reading Structured Computer Organization by Tanenbum, I understood that a programming languages is a set of instructions, from

    Each machine has a machine language, consisting of all the instructions that the machine can execute.

So I wonder if a programming language is a set of programs or a set of instructions? Thanks.

Improve this question
4
  • 3
    Your first argument is recursive.
    – Pieter B
    Feb 8, 2015 at 20:04
  • 2
    Some programming languages (and many more-or-less functional programming languages, e.g. Haskell, Ocaml, Scheme, Lisp...) don't have any instructions, only expressions. And Prolog has clauses & terms
    – Basile Starynkevitch
    Feb 8, 2015 at 20:18
  • Analogy to sort it out: language - English, set of instructions: dictionary of valid words and set of grammar rules, set of programs: results of proper use of words and grammar rules. A lot of confusion arises when you say a programming language IS a set of valid programs. You'd better say: allows for or can result with.
    – Marcin Wachulski
    Feb 8, 2015 at 20:33
  • 1
    A programming language is not the same as a "machine" ... Even though they may both use the phrase "to execute a program", the word "execute" has different meanings.
    – rwong
    Feb 8, 2015 at 21:15

4 Answers 4

Reset to default
19

From the perspective of programming language theory

I would say neither. A programming language is 3 things

  1. A set of rules for constructing programs: the grammar of the language.
  2. A set of rules for determining whether a particular program is a valid program without running it: the static semantics of the language*
  3. A set of rules for actually evaluating a program to a value: the dynamic semantics (this is what most people call "semantics")

You can't just call the set of programs a programming language because we, as programmers, care very deeply about how you interpret that program. If I told you I constructed a new language called Nothyp which had the same syntax as Python (accepted the same set of programs) but ran everything backwards (different dynamic semantics) it'd be characterized as the same language if we just looked at the programs they accept!

Plus, in this form proving something like type safety, termination guarantees, or the canonical values lemma is actually reasonably pleasant.

*The static semantics capture the essence of type checking and all the other things a compiler will catch before runtime

Improve this answer
11
  • Thanks. Do you have references (such as textbooks) that agree with you?
    – Tim
    Feb 8, 2015 at 19:52
  • 2
    @Tim Yes, see Practical foundations for programming languages (Bob Harper) or Types and Programming Languages (Benjamin Pierce) or Advanced topics in types and programming languages or even Program Logics (Andrew Appel)
    – daniel gratzer
    Feb 8, 2015 at 19:54
  • @Tim Pretty much any formal treatment of programming languages is split along these lines because that's how all interesting theorems work.
    – daniel gratzer
    Feb 8, 2015 at 19:55
  • 1
    @RobertHarvey Not necessarily :) There's a very rich field of using a programming language we don't know how to implement (Martin Lof Type Theory + Univalence) to prove interesting things about math. We also use unimplemented programming languages in proof theory or other areas of logic
    – daniel gratzer
    Feb 8, 2015 at 19:59
  • 1
    Another formulation that more or less means the same thing is: "Programming Language = Syntax + Type System + Semantics". The one you quoted is more inclusive, since its formulation more naturally applies to dynamically typed languages, for example, which often still have some static properties that are not part of the syntax.
    – Jörg W Mittag
    Feb 8, 2015 at 22:31
2

Note that the latter definition only talks about the machine language of some computer, not about programming languages in a general sense. I suppose the machine language is a programming language, but when treating programming languages as sets of programs, we can reconcile that with the latter definition by rephrasing it like this: The machine language is the set of of strings of machine instructions (or sequences of machine instructions).

Note that this nicely fits the first definition (program = sequence of instructions). That's because that definition is from an operating system developer's perspective: In that book, Tanenbaum does not care about fancy high level languages, only about binaries that can be executed by the CPU.

Also, none of those definitions is normative. There are many other useful and defensible perspectives on programs and programming languages.

Improve this answer
1

Why not just quote wikipedia? Nails it down in my opinion:

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs to control the behavior of a machine or to express algorithms. Wikipedia - Programming Language

Improve this answer
3
  • 3
    I have to disagree with this definition. Some of the best programming languages were designed to communicate instructions to a human, not a machine. Lisp, for example. John McCarthy, the designer of Lisp, didn't intend for it to ever be implemented. In fact, when Steve Russell realized that by implementing eval, you'd be implementing Lisp, McCarthy claimed that implementing eval was impossible. APL was also designed as a more rigorous notation for teaching mathematics. Smalltalk was designed on a piece of paper, the implementation was actually the result of a bet.
    – Jörg W Mittag
    Feb 8, 2015 at 22:26
  • The obligatory Alan Perlis quote: "Programs should be written for humans to understand, only incidentally for a machine to execute". It just turns out that, if you describe a set of instructions in such a way that human can unambiguously understand it, it just so happens that a machine can understand it, too.
    – Jörg W Mittag
    Feb 8, 2015 at 22:28
  • @JörgWMittag John McCarthy didn't inted for Lisp to be a programming language.
    – Pieter B
    Feb 10, 2015 at 7:54
0

computer program is a sequence of instructions, written to perform a specified task with a computer (by Wikipedia)

It has nothing to do with programming language. it's just the definition of program.

What is programming language?

A programming language is a language (like English language, Persian, Arabic, etc), it has syntax and semantic (syntax: valid sentences and invalid sentences). The meaning of the sentences (semantic), however, depends on the listener (computer). if you want to communicate with computer it should understand what you mean (machine language). However, you can use a high-level programming language and a compiler or an interpreter which translate your language to the machine language.

Is programming language a set of programs it accepts?

It's another definition of a language, and mainly concerns the syntax. It says a programming language is all the programs which are valid in that language.

For example English language is all the texts (infinite) which are according to English words and grammar. But you can't guarantee, these text have any meaning as you read them. However, if we include semantic accuracy (which is meaningful related to the target audience, for example computer) then yes that sentence is true.

Improve this answer

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.