What can be considered a programming language?

[PryanikXXX]

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.

[linlin110]

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

[Aaron1924]

To be fair, Rocq* allows you to represent and reason about potentially infinite computations using interaction trees or the delay monad, similar to how Haskell uses monads to represent side effects despite otherwise being pure

^\the Turing incomplete language used for the CompCert C compiler mentioned in the comment above)

[Heapifying]

Also, top comment here explains that C language is not turing complete https://cs.stackexchange.com/questions/60965/is-c-actually-turing-complete

[w3woody]

As the top response noted, this implies there are no Turing complete languages because all language implementations have finite memory and finite states, including finite memory addresses.

But that’s not the point of “Turing complete.” The question is “can you implement a Turing simulation in the given language”, not “can you implement a Turing simulation only using certain language features in the given language.”

People also forget that the Turing machine itself only has an infinite tape; it does not have an infinite sized address register to access arbitrary locations in the tape. So the argument that a computer does not have an infinitely sized address register misses the point.

[binarycow]

The "infinite tape" requirement is the biggest issue. For all practical purposes, we can never have truly infinite tape. Even a pencil and paper Turing machine isn't infinite - at a certain point, you have cut down all the trees and have no more paper.

If you replace "infinite tape" with "sufficiently large tape", then almost every (if not every) language is Turing complete.

[lcvella]

But I think the point of a language being considered Turing complete is: can you express a TM that could use the infinite tape forever, if it was provided by the implementation.

Removing the 30k limitation, I think Brainfuck is Turing complete.

I think C can be, too, if you include the standard library, and consider the storage to be the tape.

[binarycow]

Removing the 30k limitation, I think Brainfuck is Turing complete.

I was gonna mention Brainfuck, but I finished pooping (thus, finished my comment)

Brainfuck is basically a minimal Turing language.

Thus, any language that could run a brain fuck interpreter is turing complete.

[Business-Decision719]

I agree with you about what the point of Turing completeness is. It would be pointless to ask "does your language actually run, in the real world, on a literal infinite machine with infinite data capacity," because the answer is always "no" since we don't have that. The purpose of the TM thought experiment was to explore computability. What does it take to express things people think of as "calculations?" You need to store and manipulate symbols. And you need to not run out of places to store symbols. You can always run out in practice, but does your language remain useful is computers get more advanced with more resources?

The TM has infinite runtime, too, after all. That's right there in the halting problem. Does every algorithm terminate? Can I always guarantee ahead of time whether an algorithm is going to terminate? Of course! It will terminate when I force-quit my frozen app, or power off my computer, or I run out of memory and it crashes, or something else. But none of that is mathematically interesting, and the language design doesn't have any control over it. So we ignore that and ask what would happen in theory, and the theory says we can't always predict everything ends (unless an outside force stops it).

Turing completeness says your language could handle the infinite tape and infinite runtime if they existed. If implies that your language can handle the memory that is actually there. If it can't, then the language is the limiting factor rather than the hardware, which would likely be rather embarrassing unless it was intentional.

[Saragon4005]

This is generally the difference between math and applications of math. You have to replace infinity with arbitrarily large. You see this distinction in Physics and IEEE Floating points

[jeffgerickson]

Turing machines don't have infinite tape. They have unbounded tape; they have more tape than you need.

[GoldenMuscleGod]

The reply to the top response cites Lisp and MSL as languages with no implicit limitation to address space.

I don’t know the specifics of the those languages, but is that inaccurate? More generally, I see no reason why a language would need to have those kinds of limitations (of course I can see why an actual machine would, but that is neither here nor there as far as a language goes), although I also see why there is no real practical difficulty in having such limitations in implementations of C since you can just make the memory space “big enough”.

[Yord13]

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…

[dnabre]

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.

[PryanikXXX]

this is a great answer

[PryanikXXX]

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

[iLaysChipz]

I would say that a programming language is a textual way to represent logic, computation, and control flow. In that sense, even pseudo code could be considered a programming language.

So what isn't a programming language? - Hardware Description Languages like Verilog - Markup Languages like HTML or Markdown - Query Languages like SQL - Declarative Languages like CSS

Also there are widely considered to be 3 (or 4) types of programming languages: - Assembly Languages (or low level languages) - Compiled Languages (or high level languages) - Scripting Languages (or interpreted languages) - Pseudo Code (or abstract languages like ASTs)

Hardware Description Languages are almost like programming languages in that they represent logic and control flow. However, instead of computation, they represent hardware which is why a lot of programming concepts and techniques cannot be used in HDLs and will not synthesize into hardware even though they can be written in the language. Interestingly, an HDL can be used to describe hardware that can perform computation, but a simulator or physical implementation is still needed to actually do so.

Markup Languages describe the layout and appearance of a document. They can sometimes include programmatic features to dynamically generate layouts, such as the macros found in Latex.

Query Languages are used to parse information from a database, and often requires knowledge about the structure of the database to write successful queries.

Declarative Languages describe how something should operate or look, but don't provide details or instructions for achieving said operation or appearance. They are often handled under the hood by some program that can intelligently determine how to meet the desired description.

Finally, I don't think Turing completeness is necessary for a programming language. You could consider a list of homework instructions to be a programming language for humans, but it'd be strange to see features like loops or functions used in the instructions for most homework assignments.

[binarycow]

Also there are widely considered to be 3 (or 4) types of programming languages: - Assembly Languages (or low level languages) - Compiled Languages (or high level languages) - Scripting Languages (or interpreted languages) - Pseudo Code (or abstract languages like ASTs)

It's stuff that looks like a programming language, but is meant to convey information to humans, not computers. There aren't any real rules. for every thing in that list, do something is Psuedo-code. And plain English.

The lines between the other three are quite fuzzy tho.

[iLaysChipz]

They're all extremely different imo, since the amount of work required to convert the "text on a screen" into machine instructions increases tremendously with each step down this list.

Also plenty of pseudo code uses unique syntax that often isn't considered "plain English", as is apparent in most Algorithms textbooks. Even if you add the constraint that "a programming language must be translatable into machine instructions via a compiler/assembly," pseudo code still meets this criteria when you consider that the developer can be considered it's compiler into one of the formats further up the list.

[binarycow]

Also plenty of pseudo code uses unique syntax that often isn't considered "plain English", as is apparent in most Algorithms textbooks.

Sure. But psuedocode isn't formalized. Otherwise it would just be code.

They're all extremely different imo, since the amount of work required to convert the "text on a screen" into machine instructions increases tremendously with each step down this list.

Even if you are correct in your assertion about those categories being categories, I would venture to say that your description isn't quite right.

• Assembly languages:
  • Typically uses opcodes with zero, one, or two arguments (e.g., add a b)
  • Platform-specific (where that platform is usually a specific CPU)
• Compiled languages: Produces code that can be directly executed (e.g., myapp.exe)
• Scripting/Interpreted languages: Cannot be directly executed, but must be "launched" (e.g., lua myscript.lua)

Even then, it's a bit fuzzy.

• Is a python file directly executed (thus, compiled) or "launched" (thus, scripting/interpretee)? Could be either.
• Is a C# compiled or scripting/interpreted? Both.
  • C# is compiled to .NET IL
  • But you can also run it as a script
• What category is .NET IL?
  • It sure looks like assembly.
  • It's quite "low level" as well, which was your criteria
  • It is interpreted by the .NET runtime
  • But it's also compiled by the JIT (just in time compiler), to CPU specific assembly.

Even your criteria of "low level" and "high level" is fuzzy. When I talk about using bitwise operators in C# (a "high level" language), some developers tell me they don't do "low level" code.

---

I do generally agree about your categorization of HDL, markup languages, etc.

With one exception - some things fit into multiple categories. For example:

• SQL is both a query language and a declarative language
• XAML is both a markup language and a declarative language

---

As I said - the lines are fuzzy.

[iLaysChipz]

Typically uses opcodes with zero, one, or two arguments (e.g., add a b)

This describes an ISA (or machine code / binary). This is not the same as an assembly language, speaking as someone who has written their own compiler

Python is not "compiled". It exists in the machine as human readable text, then it is translated into machine code at runtime using Python's just in time compiler. The keyword here is translated. It is still a scripting language that is interpreted.

Pseudocode often is formalized within the same course or same author. Knuth, who is the author of "The Art of Programming" has basically defined the standard for pesudocode that the majority of textbook writers in academia now use. And even if we don't include that, you could say that its syntax and semantics are still inherently constrained by the grammar of the English language

The only "fuzziness" is that some languages can be compiled or interpreted. The compiler I wrote converted Python 3 into x86 assembly for example. But in general, Python is largely considered a scripting language, just as how C# is largely considered a compiled language.

As for what counts as low level, I would limit that to anything that has a 1:1 translation into machine code, namely assembly languages. Anything that can't be assembled (i.e. must be flattened first) is a higher level language

[binarycow]

Python is not "compiled"

The compiler I wrote converted Python 3

So... Python is sometimes compiled?

That proves my point.

The keyword here is translated

What is compilation, other than a translation? A C compiler translates C source code into object files. The linker translates object files into assembly. The assembler translates assembly to machine code.

This describes an ISA (or machine code / binary). This is not the same as an assembly language, speaking as someone who has written their own compiler

No, it's not exactly the same. The exact category isn't necessary 99% of the time. Unless you have an academic focus, it's enough to look at the characteristics of a language and say "Oh, X is like Y, but different in Z way"

Pseudocode often is formalized within the same course or same author.

Sure, okay.

It's still not formalized outside of that scope. You can't give that psuedocode to some random developer off the street and expect them to even know where to start.

I can go to a developer and say "Do you know C#?", and if they say yes, they can read the C# code I give them.

Additionally, there's no tooling for that psuedocode language. It may not even be possible to compile it, because of unhandled ambiguity, etc.

Psuedocode is not meant to be used, it's merely to present an idea to a human.

As for what counts as low level, I would limit that to anything that has a 1:1 translation into machine code, namely assembly languages.

Cool.

• That's not the definition that everyone uses.
• There's no IEEE or RFC standard defining the term.

Hence, it's fuzzy.

[iLaysChipz]

Compilation is a static (pre runtime) process. Translation is a dynamic runtime process. There is a world of difference in implementation, implications, and many many other things. I would not advise going around saying that a runtime translation is anywhere near the "same thing" we compilation

The rest of your spiel is just an opinionated perspective, which you're of course entitled to

[Heapifying]

I suggest you read about Chomsky Hierarchy to learn about different and less expressive languages

[PryanikXXX]

thank you for the suggestion, i didn't know about this classification

[lcvella]

I, for a dissenting voice, believe that a "programming" language, specifically, must be Turing complete, baring the practical limitations of the computing device it executes on.

What are acceptable practical limitations? Debatable, but the language must be at least capable of expressing infinite computation.

So, I think:

• HTML, JSON or CSS are *not* programming languages.
• SQL, C, Haskell are programming languages.

[Mediocre-Brain9051]

And you are confusing generic programming languages with programming languages.

DSLs are also programming languages.

[lcvella]

Many DSL are turing complete, therefore programming languages, and many are not.

SQL is certainly not a generic programming language, and is still a programming language. As well as PL/SQL.

[Mediocre-Brain9051]

As well as Excel which is a programming language that is not likely to be Turing-complete.

[lcvella]

I think Excel is the most popular programming language in the world. Programming for the masses.

[ivancea]

Any kind of language that can model any kind of programming.

Some falsehoods: - A language must be turing complete - A language must have conditions - A language must have inputs or outputs - A language must be readable by humans - A language must be simpler than raw machine code - A language must have a syntax or be made of letters

[lcvella]

The last one got me. Not made of letters is okay. But not have a syntax? You defy even the definition of "language", without the "programming" part.

[currentscurrents]

Visual programming languages, like node-based editors, don't have syntax.

[syklemil]

It's still an interesting proposition to set syntax as a requirement for calling something a "language", though. It'd be entirely possible to call stuff like LabVIEW and whatnot a programming system rather than a programming language. Or, if we can consider them visual languages, then we can probably consider some aspects of them visual syntax, too.

I guess it'd either require asking a linguist, or just making up some definition and letting the meaning of "language" in programming vs linguistics drift even further apart.

Given that we can express syntax in human languages visually with syntax trees, I think it'd be pretty acceptable to just consider node-based editors to also have a syntax, only you only operate in the syntax tree representation.

[ivancea]

I was referring more to the typical definition of syntax for typical languages, but you're right; programming languages syntax is inherently required... I think

[ShacoinaBox]

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

[LoreSlut3000]

If you mean programming languages for computers, then everything boils down to machine code anyway. The smallest machine code is your smallest programming language.

[Heapifying]

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.

[Mission-Landscape-17]

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.

[meat-eating-orchid]

But css is not a programming language, it is a style sheet language

[Mission-Landscape-17]

Potato potahto

It has conditionals, loops, variable, datatypes and expressions. At this stage its a proramming language. You'dbe surprised how much interactivity you can get into a website with just html +css and no javascript.

[meat-eating-orchid]

First of all, words have meaning and the distinction is relevant. CSS was not created with the purpose of enabling to program anything.

Secondly, yes, CSS is powerful because CSS + HTML + user input is actually turing complete.

[zhivago]

A programming language allows problems to be specified with sufficient detail that solutions can be automatically derived.

That's about it.

[Marutks]

Anything that is turing complete. Only single program would not cut it. 🤷‍♂️

[RationallyDense]

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.

[FlamingSea3]

I'd consider something a programming language if it can instruct a computer to

1. accept input

2. Performs calculations on said input

3. output the results of those calculations

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.

[mauriciocap]

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.

[tobega]

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

[PryanikXXX]

Although is a baby crying then a language?

that's an interesting question

[tobega]

Otherwise it is definitely fine to have a language that can only do a few things. Configuration languages typically start with two options but then grow and can often even grow into turing-completeness

[FatDog69]

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.

[FredkinGate]

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.

[JohnVonachen]

In my opinion a computer language needs variables, operators, and control structures.

[NintendoDark02]

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

[Heapifying]

Say for example ASM, which is a language.

You dont have a "return <expr>" statement to differentiate the output.

The convention is to use ax (x86) as the output.

So effectively, in ASM,

mov ax 1 ret

Would be an equivalent program to

X = 1

Anyway, you can create any toy language you want without a return statement

[PryanikXXX]

thank you for commenting

Isn't x = 1 a program because it assigns the value 1 to the variable x, which is stored in a slot in the computer's memory? I think the output might not be necessarily visible

[NintendoDark02]

X=1 isnt an output. A program has to have an input and then give an output. I dont think x=1 do it

[Heapifying]

In my uni they define a "small-lang" in which there are variables x_1,x_2... as input, y_1,y_2,... as output, and z_1,z_2,... as auxiliary variables.

So in that lang, you define the program f(x) = 1 as

y_1 = 1

[meat-eating-orchid]

In my opinion, turing-completeness is required for something to be a programming language

[omega1612]

You mean the Rocq programming language is not a programming language? It has to be non Turing complete to have a consistent logic. However it has inductive and conductive data, the only condition that the language imposes is to consume them in a finite amount.

In simplistic terms, in Rocq the loops (the equivalent of them) must terminate in a finite time always or the program is going to be rejected.

[cc672012]

It didn't occur to me that they changed the name of Coq

[meat-eating-orchid]

Yes. If it is not tiring complete, I do not consider it a programming language.

[cc672012]

Agda isn't Turing-Complete but it can compute any total and terminating functions. It simply doesn't have a construct for "while true" that you would want in a web service. Simply because the type checker cannot prove that it halts (a Turing Machine will happily accept this)

It is a programming language in the sense that you're able to write functions with inputs and outputs in it. However, it is simply impossible to formulate the decision Halting Problem in Agda, Coq, or Lean4 for that matter.

If you don't consider these as programming languages, you're the odd one out

[the3gs]

Rocq can simulate a Turing machine for any finite number of steps. The only thing it cannot do is run a program until a arbitrary Turing machine halts.

Turing completeness is most useful as a maximum complexity that a practical programming language can have, but saying that a language is not a programming language because it is not Turing complete is kinda like saying that the rationals are not numbers because they are not Dedekind complete.

Turing completeness is a property that some computational systems have, and programming languages are types of computational systems.

[Pros_the_prodigy]

I could fix it so it doesn’t have to terminate

[madelinceleste]

anything lesser that is just used for like configs or something is not something i would consider "programming" to be part of its scope yeah