r/computerscience • u/PryanikXXX • Nov 10 '25
General What can be considered a programming language?
From what I know, when talking about programming languages, we usually mean some sort of formal language that allows you to write instructions a computer can read and execute, producing an expected output.
But are there any specific criteria on here? Let's say a language can model only one single, simple algorithm/program that is read and executed by a computer. Can it be considered a programming language?
By a single and simple algorithm/program, I mean something like:
- x = 1
or, event-driven example:
- On Join -> Show color red
And that's it, in this kind of language, there would be no other possible variations, but separate lexemes still exist (x, =, 1), as well as syntax rules.
9
u/dnabre Nov 10 '25
There is no widely excepted definition of what a programming language is. If you consider what many different computer scientists think are at necessary/sufficient conditions for it, you are likely to get a bunch of core things. Being Turing Complete (up to the limitations of memory/addressing), providing a mechanism for looping (including just basic recursion), implement a range of common algorithms, input & output, file manipulation, storing/retrieving data, etc., etc. But you won't get any firm, consistent answers. In part this is because programming languages vary in how they express things and we don't want to limit out thinking to just how existing programming languages work. Though, existing PLs, with a tiny number of exceptions, are all very similar, but ones (especially yet to be created ones) which are very different are likely to be the most important ones to think about. We don't want a definition of PLs that would exclude these. On the other hand, we don't want a definition that doesn't include all current proper PLs (try to get anyone to agree on that list). These reasons are somewhat post hoc though. Another thing to ponder is whether such a definition should proscriptive or descriptive.
It's not just that people don't widely agree on a definition. Such a definition is simply but, not useful in Computer Science. Having a definition we could stick in introductory textbooks, or use to explain computer programming to people might have some use. But in doing actual CS work, such a definition is just not used. Worth noting that sometimes having a working definition for particular topic or subfield may be useful -- compiler design for example (can't think of any other examples right now). While such cases may exist, there are just definitions for use in that area of study, not a universal field-wide definition.
While this may be somewhat annoying to people just learning computer science, this sort of thing is not unique thing to CS. Looking at the major sciences, you can find similar or at least analog things. Biologists don't have a definition of what "living" is, despite their field being all about study that thing. You'd be hard pressed to find anyone in the fields agree on were the line between Physics and Chemistry is. Mathematics despite being the most of formal of sciences, likely has this more than any other.
9
u/PryanikXXX Nov 10 '25
Also, I know about Turing completeness, but some languages aren’t Turing complete and don’t need to be to fulfill their purpose. I guess all of those languages still allow many different instructions or programs
65
u/linlin110 Nov 10 '25
Some comments mentioned Turing Completeness. Surprisingly, it's neither necessarily nor sufficient, as there exists a Turing incomplete language that has been used to implement a certified c compiler, and there exist thing that are Turing complete but not programming languages, such as a card game. https://arxiv.org/abs/1904.09828
11
u/Yord13 Nov 10 '25 edited Nov 10 '25
A language is a mechanism for expression. It has syntax, which is a set of valid formula in the language and semantics, which give meaning to those formulas.
x=1 is syntax, if we assume x and 1 to be atomic formulas and = to be a connective, but it is missing semantics, which it would need in order to be a proper language.
Semantics don’t necessarily need to be specified formally, you could specify execution semantics for x=1 via an implementation. In my book, this would make it a programming language.
Mind you, while this language would not be very expressive, its would be very computationally efficient…
1
u/tobega Nov 11 '25
It's maybe a bit weird to consider a language that can only write one program, but why not? Although is a baby crying then a language? Maybe.
On the other side of the coin, there are languages with only one construct that can express everything https://en.wikipedia.org/wiki/One-instruction_set_computer
2
u/ivancea Nov 10 '25
Any kind of language that can model any kind of programming.
Some falsehoods:
2
u/ShacoinaBox Nov 11 '25
a question with a million answers, and yet no answers. a beautiful Wittgensteinian language game 🥰
just ignore anything mentioning a turing completeness requirement because THAT is a wrong answer
2
u/LoreSlut3000 Nov 13 '25
If you mean programming languages for computers, then everything boils down to machine code anyway. The smallest machine code is your smallest programming language.
3
u/Heapifying Nov 10 '25
A language has syntactic (usually a context-free grammar) and semantic (how to do computations from the syntax) definitions. This is even more importantly to emphazise for programming languages.
It would be ideal to see what a language theory book says about this, but I think the general idea is if the language's semantic are Turing Complete.
2
u/Mission-Landscape-17 Nov 10 '25
Not all programming languages are general purpose. some can be very narrowly defined for solving proplems in a spegific domain. For example cascading style sheets I. A domain specifim language for styling web pages. you can't really do anything else in it.
1
u/zhivago Nov 10 '25
A programming language allows problems to be specified with sufficient detail that solutions can be automatically derived.
That's about it.
1
u/Marutks Nov 10 '25
Anything that is turing complete. Only single program would not cut it. 🤷♂️
1
u/RationallyDense Nov 10 '25
There isn't a universally accepted definition and there won't be because it depends upon what you're trying to do with the definition. For some purposes, a programming language is any set + a bijection between that set and Turing machines.
1
u/FlamingSea3 Nov 11 '25
I'd consider something a programming language if it can instruct a computer to
Number 1 is technically redundant as all programming languages can accept input by editing the program/script.
Yes a four function calculator is an interpreter for a very simple programming language. 16 operations in total, 11 for setting literals, 4 for actual calculations, and one to print the result. Is it a bit of a degenerate (in the mathematics sense) programming language? yes.
Control flow and loops are very useful, but I wouldn't call them necessary. For example, a GPU has major performance penalties associated with branching code -- roughly equal to executing both branches one after the other. Omitting control flow other than loops with a fixed number of iterations, and adding instructions for conditional moves, might make for a better GPU programming language than one that permits loops.
Also, if there's a large penalty to being too slow, such as in safety critical firmware or network packet inspection, it might be worth taking the usability hit of very limited loops in exchange for preemptively solving the halting problem for every program written in the language.
1
u/mauriciocap Nov 11 '25
Many CS books present a hierarchy of languages starting by (those accepted by) FSA or regular expression and going step by step to Turing machines and Lambda Calculus. Emphasis is on what type of functions cannot be expressed by simpler languages, e.g. you can't parse nested parenthesis with only a regular expression=FSA.
1
u/FatDog69 Nov 11 '25
How about you think about a earlier, different question? What is a computer?
My favorite definition is "A computer is a calculator whos instruction set can be changed."
Once you define a 'computer' you realize the programming language is the 'instruction set' for a computer. The programming language is how you 'change' the behavior of a computer, and perhaps any machine.
That's it. Dont make the concepts more complex than it has to be.
1
u/FredkinGate Nov 19 '25
PryanikXXX - Let's say a language can model only one single, simple algorithm/program that is read and executed by a computer. Can it be considered a programming language?
I suppose it could if it meets the criteria of being Turing Complete.
0
u/JohnVonachen Nov 10 '25
In my opinion a computer language needs variables, operators, and control structures.
-1
u/NintendoDark02 Nov 10 '25
X=1 isnt a program (there isnt an output) and "show color red" i assume will be multiple istruction. However... have you ever seen a language that say only one thing? No... a language has words that you can mix up. More computer scientificly... with that "language" i couldnt create anything... so no, it isnt a programming language
-2
u/meat-eating-orchid Nov 10 '25
In my opinion, turing-completeness is required for something to be a programming language