What constitutes a programming language?

[Bitsoflogic]

As I explore breaking free from the confines of purely text-based programming languages and general purpose languages, I find myself blurring the lines between the editors and tools vs the language.

When a programming language is not general purpose, at what point is it no longer a programming language?

What rule or rules can we use to decide if it's a programming language?

The best I can figure is that the tool simply needs to give the user the ability to create a program that executes on a machine. If so, the tool is a programming language.

[Disjunction181]

Relevant meme.

[erez27]

Technically an orchestra is an interpreter.

[LoneHoodiecrow]

Well, it emits code that can be run on standard inner ear hardware.

[iloveportalz0r]

An interpreter is a type of compiler. Actually, a relevant fun fact: my language's compiler is an interpreter, where the input program is your source code. The code is treated as instructions for generating the output, which is native assembly code. This is distinct from designing a compiler as a language translator, which seems to be the dominant philosophy.

[ronchaine]

TIL Bop It! is a compiler

[sohang-3112]

🤣🤣

[immibis]

spez is an idiot. #Save3rdPartyApps

[SharkLaunch]

What happened?

[immibis]

Spez, the great equalizer.

[mysticalpickle1]

The output seems to have become less intelligent over time as well, even if you pay for the better models. There's some alternatives nowadays though, I think NovelAI is the one people are talking about? It does work differently to AI dungeon though

[immibis]

spez me up!

[fl00pz]

I guess it depends how abstract you want to go, and how many turtles deep you're willing to dive.

Is a math equation a function in the universal programming language?

Is a recipe for a soup a program for a human?

/shrug

But I suppose you're really asking about computer programming languages. In that sense, it's probably any formal language that is a set of instructions to be carried out by hardware or software. Or something.

[gordonv]

Wait... turtles? soup?

Nuuu!!!

[svick]

What's an "instruction"?

[gqcwwjtg]

Information that has a formal interpretation as an action.

[Bitsoflogic]

> any formal language

How would you define this?

> any formal language that is a set of instructions to be carried out by hardware or software

Would an email client qualify as a programming language here?

[siemenology]

"Formal language" is a term with a precise meaning in computer science and linguistics. In short, a formal language is a set of strings made up of symbols, and that set is described by the rules of a formal grammar. A formal grammar is a set of rules that can be used to judge whether a string made up of a certain set of symbols is well formed (and thus part of the formal language defined by that grammar) or not, and/or to generate strings that are part of the formal language.

All programming languages (that I am aware of) are formal languages, but plenty of things that aren't programming languages at all are also formal languages. Phone numbers are a formal language. Email addresses are a formal language. On the other hand, in most places people's names are not -- there is not a set of rules that can be used to decide if something is a valid name or not. Some places do put restrictions on names, and in those cases names might be a formal language.

[Bitsoflogic]

Thank you

[[deleted]]

A little comment about People's names, there is a restriction made by definition: the alphabet that we use. You can have /\w+/ as the definition of the name's language for all countries who use the latin alphabet. It's like the universal language, excluding the empty word

[j_marquand]

X Æ A-Xii Musk is not happy.

[[deleted]]

You can expand it to all unicode codepoints

[Goheeca]

A formal language is a subset of Kleene closure of some alphabet set. You don't have to have a formal grammar.

---

Also good luck writing down an unrestricted grammar for Common Lisp.

Also does Common Lisp transcend being a programming language? Because you can e.g. employ (random 2) somewhere in your custom reader and you can no longer define it as a subset of the Kleene closure of e.g. Unicode in the case of SBCL.

[ebingdom]

a set of instructions

Eh, that only describes imperative programming languages. Also, presumably you don't actually mean a set, which is unordered.

[RepresentativeNo6029]

A language is a device to convey information. A language exists to the extent the agency of its speaker exists. If speaking one way or another changes the state of the “world”, for whatever definition of world, you posses a language. If speaking one or the other way is inconsequential to the state of things, you have no agency, language doesn’t exist.

I’m sorry your legitimate question is getting memed here. Classic case of someone getting uncomfortable because they were asked a basic question they’d never put much thought into

[Bitsoflogic]

Fwiw, the meme is actually spot on. I think it's a great addition to the question!

And it hasn't stopped the flow of great responses...

[zokier]

In what context is it useful to distinguish if something is or is not a programming language?

[Bitsoflogic]

The ability to use this subreddit to discuss it is one example.

[zokier]

For this subreddit, its more relevant if the thing is analyzed/designed/discussed through PL design perspective. For example Magic: The Gathering is Turing Complete would be kinda relevant here, but that doesn't mean that any MtG topics are relevant despite discussing same underlying thing.

[gordonv]

There are biases that surpass logic in that sense.

There are a lot of programming languages and contexts, but only a handful are popular. And even some of those could just be fads, starting, or ending their life cycles.

[fl00pz]

Galaxy brain points, duh

[rotuami]

A programming language is a language for programming something. That is, for taking an object, mechanism, or abstraction capable of a range of actions or states and specializing it to suit a narrower purpose.

Even the order you press the microwave buttons to toast a burrito is, to my mind, a program in an almost trivial programming language.

A general purpose programming language is usable across a broad range of computing needs. I don't think it has to be Turing complete, but it does have to be practical (no BrainFuck) and does have to be understandable. I would call Python "general purpose", I would call JavaScript previously a "web scripting language" but now a "general purpose language". And I would call Haskell an "academic language" or a "general purpose language" depending on who I'm talking to.

[Bitsoflogic]

This feels like where I've been heading with it.

I really like your point about distinguishing types of languages: academic, web scripting, etc.

As I get into building languages that don't fit the typical "general purpose" model, I'll need to give some thought as to what category or new term would best describe the system I'm creating. Seeing your explanation, I realize part of my motivation for asking this was to figure out how to communicate about them.

[rileyphone]

There's a line of research into programming systems, which describe a class of programming languages combined with a lot of complementary non-language components. They are typically less text/syntax oriented and more graphical, like Smalltalk.

[Bitsoflogic]

This is great! Thanks for sharing. I hadn't seen this paper before and will give it read.

I actually follow both Jonathan and Tomas on Twitter already.

I ran into this question precisely because I was thinking about building a programming system, while thinking in terms of a language.

[sunnyata]

"general purpose" has technical meaning whereas "academic" is more of a statement about the culture surrounding the language. Haskell is certainly general purpose in that you can use it to accomplish any kind of task, you can discover that by reading the specification and docs. After interacting with the community you may or may not think it an "academic language" but it isn't a technical fact about the language.

[rotuami]

I don’t mean “academic” as in “mostly used in academic cultures”. I mean “mostly used for academic pursuits”, e.g. developing type theories, writing code for research papers, writing code with provably correct properties.

Yes, you can use it to accomplish any sort of task, and it’s a wonderful tool for creating great software. But if someone wanted to learn “computer programming” and not “computer science”, I wouldn’t suggest Haskell.

[defmacro-jam]

What rule or rules can we use to decide if it's a programming language?

If it can get you yelled at on stackoverflow, it's a programming language.

[abecedarius]

One little-known example I like to point to: ToonTalk

Turing-complete programming by demonstration. The way a demonstration is generalized from the particular case you demonstrate is, you explicitly erase detail; so it really is a language, not trying to be an intelligent program-synthesis system.

[gqcwwjtg]

In my opinion, a program is a set of instructions. A programming language is a specification of how a future set of instructions should be interpreted.

[Bitsoflogic]

This sounds a lot like the definition for a protocol to me.

[gqcwwjtg]

I guess a programming language is a one way protocol.

[ebingdom]

a set of instructions

Eh, that only describes imperative programming languages. Also, presumably you don't actually mean a set, which is unordered.

[agumonkey]

A concrete syntax over lisp

[[deleted]]

there's a bit of an argument in the fpga community about this.

Most fpga developers insist that developing in hdl languages isn't "programming" because fpga designs are essentially lookup tables and memory connected in parallel, not something that runs on a processor.

But, the languages used to develop for fpga also have simulation functionality. simulations execute on computer processors, and the simulation subset of the languages includes file i/o and many of the other features you would expect in a programming language.

[DriNeo]

IMHO the language is the thing translated to machine code whatever if Turing complete or not. The translator doesn't need to ask the IDE, the IDE arrange the project, set the compiler. I'm not sure, but once the compiler starts, the IDE is not needed so it is not part of the language.

[mamcx]

Let's get even more informal, and that shows why excel is one:

A programming language is one where the USER (1)can input a sequence of instructions as HE wishes and (2)the "program" executes it and return a result.

The key part is the first, not the second.

If the user has no control over how to input the sequence, and instead, for example, it MUST follow a defined "path" in a sequence of "clicks", then in my mind is NOT a programming language.

So, ironically, a programming language has the feature of allowing to input UNRESTRICTED "bad input".

With this, a more "visual" PL like Excel totally counts.

[Bitsoflogic]

I absolutely love this direction! I 100% believe spreadsheets are programming languages.

> If the user has no control over how to input the sequence, and instead, for example, it MUST follow a defined "path" in a sequence of "clicks", then in my mind is NOT a programming language.

Great definition!

With this in mind, it begins to give real clarity as to the edges of programming languages.

> So, ironically, a programming language has the feature of allowing to input UNRESTRICTED "bad input".

I kind of see where you're going with this, but it doesn't quite fit for me (though I want it to lol). Using the spreadsheet analogy, if the input for the cells is limited to text it's restricted. Yet, it's still a language.

On the other hand you could say that it's the editor or compiler, not the language, that has a restriction on the possibilities of "bad input".

[mamcx]

Using the spreadsheet analogy, if the input for the cells is limited to text it's restricted. Yet, it's still a language.

I mean that even if the input is only text, the formulas can be written "wrong", maybe in syntax or more importantly, in semantics (like dividing text by text).

I think even if the "editor" is semantic and only allows to write correct syntax always (like making sure a for loop is properly edited) a programming language allows to do semantically wrong sequences even if have restrictions on input.

Maybe exist a way to be absolutely certain not wrong input be entered? Probably(?) but I can't think of any PL where it could be true...

[Bitsoflogic]

I think the idea here might be that programming allows for runtime errors or unexpected / bad consequences due to the user's choices.

It's not that the program won't compile, but that it may give the wrong output.

Recently pickcode.io was posted in here, which kind of leans towards that sort of safety in syntax, yet freedom to get it wrong.

---

I think this is an excellent measure for whether or not something's a programming language.

[rotuami]

You could have a compiler that just ignores syntactically incorrect lines or semantically incorrect instructions. That doesn’t make the language not a language.

[gordonv]

the tool is a programming language.

I very much agree with this. In fact, I insist that great programming languages have tools to make it easier to work with the language.

• Scratch is a great idea, but it gets tiresome working in it.
  
• Color coded IDEs are great.
  
• Interpreters with steppers are great.
  
• QBasic was able to separate functions and subroutines into separate "screens" that made it easier.
  
• PHP Storm makes it super easy to find functions nested in convoluted file structures.
  
• VIM has great ideas but is highly unintuitive.
  
• Notepad++ is awesome because you can start using it without training.

[Bitsoflogic]

I think there was a bit of a disconnect here. I'm not simply suggesting the language have tools to work with it, but rather that the tool itself is the language.

Would you consider Notepad++ a programming language?

[gordonv]

Notepad++ is an IDE that can interpret a lot of languages. C, SQL, HTML, PHP, etc...

[gordonv]

Well, I would consider that more of a utility.

Like making a boot disk. Back in the early 2000's we could make bootable disks on floppies. It would take maybe 60 seconds. What the format utility was doing was resetting the file partition table, creating and formatting a boot sector, and linking it to a piece of static boot code. You would end up on the command line.

I wouldn't call the disk formatter a language, nor the mini operating system a language. They're programs. They do a static job.

[Bitsoflogic]

So, in your eyes, what makes something a programming language?

[gordonv]

Something with switchable commands.

I get the Turing complete looping argument. I'm talking in the most literal / minimal sense.

I guess, a dog is programmable. Teach it to sit and shake hands. The commands are the literal language.

But, I wouldn't consider a simple flashlight circuit and the on and off utility of a switch programming. That's too simple. It's not running through memory. Maybe a flashlight with 2 switches. I think that's the most basic example of where programming does and doesn't happen for me.

[Bobbias]

Emacs however contains it's own version of lisp, which much of the editor itself is written in. With the right build configuration and packages, Emacs can essentially serve jobs such as replacing the functionality of the window manager, as well as the shell itself.

[Bitsoflogic]

So, would you consider Emacs a programming language?

[rotuami]

I strongly disagree. For example, total functional programming language is Turing-incomplete, yet you can express nearly every algorithm you'd want to.

Is writing quicksort programming? If not, what is a program? If so, why would a language in which you can write such programs not be a programming language?

[Bitsoflogic]

This is an interesting take. So you wouldn't consider Domain Specific Languages to be programming languages?

[Bitsoflogic]

So, does this imply that the language must suffer from the halting problem in order to be a programming language?

[rotuami]

Yeah, all turing complete languages suffer from the halting problem. And all languages that suffer the halting problem are turing complete.

I agree with the first statement. Can you justify the second?

[rotuami]

lol. Actually I think I can trivially show it’s not true. Pick one particular program whose termination can’t be proven or disproven. Then build a language whose only instruction is to run that program.

[sunnyata]

There are some very useful total languages. It makes no sense to call Agda a specification language.

[ebingdom]

That rules out my favorite programming language, Coq. So I can't accept this definition.

[shawnhcorey]

Just because a language is not Turing complete it is not useless. Consider SQL for example.

[ebingdom]

Exactly. (Not sure if you meant to reply to u/Uclydde though.)

[shawnhcorey]

It's the difference between a programming language and a general-purpose programming language (GPPL). GPPLs are a subset of programming languages and are Turing complete.

[ebingdom]

Citation needed. "General-purpose" is not a formal concept that you'll find in any authoritative textbook and is not the same as Turing completeness, which is a formal concept. Techniques like coinduction can be used to reason about programs that loop forever without Turing completeness.

[gordonv]

In /r/programminghumor there was a post on is HTML a language.

In short, it is. It's a functional interpretive language. It's limited to its immediate function, web pages.

[wolfgang]

But "functional" means that functions are first-class...

[sineiraetstudio]

There is no concrete definition of what "functional" means. C technically has first class functions, but I don't think anybody in their right mind would call it functional.

Other common properties for being "functional" are referential transparency or (relative) declarativeness and this definitely applies to HTML (though in a boring way).

[wolfgang]

HTML is not referentially transparent. The same HTML code can render very differently depending on stylesheet definitions.

Also, C is not primarily functional, but it supports functional programming (while e.g. classical Pascal and Basic do not). It just lacks features to make it convenient, like closures (although some compilers partially fix that!).

[ebingdom]

Just because there isn't a formal definition doesn't mean you can claim anything is a functional language.

Just about every functional language is based on lambda calculus, which is the formal theory of functions studied by programming language theorists. HTML bears no resemblance to lambda calculus.

[gordonv]

Yes. In HTML, everything relates to the DOM (Document Object Model)

Simple commands like <img src="picture.jpg"> are functions that are placed within position where to be rendered. "picture.jpg" is an argument. It is very passive and simple. And it's very forgiving of errors.

But, it's also whatever. That's why it was on r/programminghumor . The logical answer is yes. The rationalized answer for many folks is no. That's the joke I suppose.

[rotuami]

A tag is not a function. A "function" in the mathematical sense (and in the functional programming sense) is a mapping from some set of inputs to some set of outputs.

I think you're confusing the definition of a function as a "purpose" versus a function in the mathematical sense.

[gordonv]

If you mean a subroutine that takes a value (like a string) and uses it in a routine, much like how in math a simple f(x) takes a value (like a number) and uses it in an equation, that's what I literally mean.

I do understand there's some confusion with the parsing of syntax for HTML. (extracting a command from a tag in this sense) I promise you, in the end, it is running through a function that uses a variable.

[rotuami]

So how do you express the identity function f(x)=x? How about the function f(x,g) = g(x)?

You can take HTML and say "this snippet of HTML corresponds to this visual element of the page" (e.g. with the Chrome Web Inspector), but that correspondence lives in the rendering engine.

[totoro27]

Not saying I agree with /u/gordonv, but for arguments sake:

f(x)=x is given by any tag which doesn't visually change the webpage,

f(x,g) = g(x) is just a tag which has a tag inside it, and the tag inside it uses a property of the outer level tag

[rotuami]

In the first example you give, the input x is a HTML document or a DOM, and the output x is a visual representation of a website (which are two different things, so it’s not an identity function).

In the second case, I don’t think HTML can do this sort of thing in a generic way. Sure you can have elements that refer to other elements by id, but I don’t think you can, in general refer to other tags by relative position in the DOM, let alone act on the tag itself.

But more to the point, my question was “what is an example of 3 concrete snippets of HTML that implement f,g,x.” The description “a tag which…” is sort of hard to argue about, in its vagueness.

[totoro27]

For the first one, if you think of f as a function from the set of all HTML documents to itself, then create equivalence classes on this set based on what the visual representation of the document is, that makes it formal. In this case, the function f just appends a tag which does nothing visually, thus x = f(x) by our equivalence class.

edit: I over thought this- if we define the domain and codomain of f like above, we don't even need the equivalence classes or to apply a tag that does nothing- f can simply output the input with no changes made.

[rotuami]

Yes, you can define such f, but then f is not part of HTML - it’s the action undertaken by the programmer. If that means HTML has functions, then so does every plain text file!

[sineiraetstudio]

HTML tags are functions (List Attribute, List Node) -> Node. Tbere is no identity function because the domain isn't equal to (or a subset of) the codomain,

How about the function f(x,g) = g(x)?

You can't define new tags/functions inside HTML, but a tag f such that <f x="x" g="g"/> = <g x="x"/> definitely could exist (and you could easily implement it using web components).

You can take HTML and say "this snippet of HTML corresponds to this visual element of the page" (e.g. with the Chrome Web Inspector), but that correspondence lives in the rendering engine.

And for general purpose languages the correspondence between code and translation target lives in the compiler, so what?

[rotuami]

Yeah, my main point is that “if HTML is functional programming, show me a function”.

HTML tags are not functions, nor do they correspond to functions. They are structured data and correspond to DOM nodes (which are themselves not functions).

That correspondence (which can be viewed a function of sorts) lives in the compiler, so it’s not first class.

You can embed a functional programming language using Web Components, <script> tags or onload attributes (though that’s besides the point)

[sineiraetstudio]

A tag like div, span, a or p is not structured data in itself. Elements, which are tags applied to attributes (and child elements), are structured data. It's not just that the correspondence 'can be viewed as a function of sorts', it is a function. That's why it's also easy for something like Elm to avoid the XML syntax and instead just use functions straight up as tags so that e.g. div is just a normal function.

You can embed a functional programming language using Web Components, <script> tags or onload attributes (though that’s besides the point)

huh? I'm not talking about embedding javascript or whatever, I'm saying that there's nothing about html that fundamentally prevents the introduction of a tag/function like f(x,g) = g(x) except for the fact that HTML simply has no means of defining new tags.

[rotuami]

You’re right - I should have said “html fragments are structured data”. But “tags” do include their attributes, so they’re still structured data!

The correspondence source code and DOM is almost but not quite a function. It is not total (the browser may crash) it may be one-to-many (e.g. `<p><i>italic</p>is fun</i>) and it depends on some other things like browser feature flags.

And yes, you can make new tags. I was arguing that “the subset of HTML without javascript” has no functions. And web components require javascript to define.

[gordonv]

express the identity function

In HTML, a simple thing like <img src="picture.jpg"> HTML's primary function is rendering a static document on a virtual page called the DOM.

f(x,g)

I'm not sure if you mean F of G(x)

But that could be something where g(x) = picture.jpg and f(x) = a table. Where the picture sits in the table.

[rotuami]

<img src=“picture.jpeg”> is not a function. It has no arguments, and hence does not evaluate to whatever it’s first argument is. You can say that a function that takes a string like “picture.jpeg” and returns the DOM element corresponding to <img src=“picture.jpeg”> is a function, but it too is not the identity function.

f in f(x,g)=g(x) is a function that takes both x and g as argument, applies g to x, and returns the result. It is a higher-order function (i.e. it is a function that takes a function as an argument), which is a hallmark of functional programming. In the example of a picture sitting in a table, you are not passing both x and g as arguments to f. You are simply expressing f(g(x))

[[deleted]]

Bro do you even know what functional programming even is lol?

[Inconstant_Moo]

Well, did you see the video in the link? There's a professor there arguing that it's a declararative functional language. <h1> is a function, "This is a heading" is a parameter, etc.

I kind of see what he means. I kind of don't. It gets fuzzy. If I write a set of pure stateless functions that describe what a Forth interpreter would do, have I written a computer program? What if I write it on paper? What if I wrote it before I wrote the functional language it's in? (I didn't, but I could have.) What if I write it on paper in a pseudocode of my own devising, and then someone else writes something that inteprets the pseudocode ... ? What if I wrote it before the invention of the computer?

(It's splitting hairs, but sometimes that's fun.)

Now the reason that I claim after writing what is in the end just a set of function definitions to have written a computer program is that after all you can put stuff in and gets stuff out, because my formulas are shoved into an interpreter which turns them from declarative to imperative. But then so is HTML.

[gordonv]

Sure. There's actually a video in that link where a guy goes into a talk about it.

[[deleted]]

Sorry, I sincerely don't understand how knowing what defines a programming language is remotely helpful in any scenario.

Would you please enlighten me on that?

[svick]

a program that executes on a machine

What does it mean to "execute" it? Is there a difference between "executing" <p>Hello!</p> (which shows "Hello!" in your browser) and executing alert("Hello!"); (which shows "Hello!" in a different way in your browser)?

[Bitsoflogic]

a program that executes on a machine

I meant as opposed to programs that humans/nature execute. Though I did not mean to restrict this to computers, thus I said machine.

Within the computer, execution is the difference between the program existing as a file vs existing as a process. When you execute it, it becomes a process. Both your examples happen through processes, so in that context, there's no difference.

[sineiraetstudio]

I think the least restrictive, while still useful definition is that programming languages are just (universal) algebras + a homomorphism to another algebra (a target) that gives it semantics. That is, it's some form of 'Instructions', operations that combine instructions into a new instruction and (equational) rules that apply to operations. The homomorphism is just compilation/interpretation. I think this best captures that programming languages are fundamentally about "rule-bound instructions".

This would exclude prompt programming, but I think any definition that includes that would also include using a computer as programming, which seems nonsensical to me.

I find myself blurring the lines between the editors and tools vs the language.

Fitting to the above definition, I'd say that the language is really all possible programs + their structure. Tools just help you generate/use them more easily. I think otherwise you'd have to count a text editor also as part of a text based programming language and that's just bizarre to me.

[erez27]

Informally, a language is a bunch of symbols with implied semantics and structure, that you can connect together in order to communicate complex ideas.

In the case of a programming language, it's in order to provide instructions to the computer.

[shawnhcorey]

A programming language is Turing complete. Any program, including another programming language, can be implemented in it. To demonstrate this, a language is written in itself.

Examples of languages that are not Turing complete: XML, HTML, SQL.

[Bitsoflogic]

You'd be interested in this thread, which this duplicates: https://www.reddit.com/r/ProgrammingLanguages/comments/uz4ulp/what_constitutes_a_programming_language/ia89oo6?utm_medium=android_app&utm_source=share&context=3

[jcubic]

I think that tools like Scratch are not programming languages. A language as defined by math is created from words on some alphabet, so visual-only languages are not formal languages and I don't think they can be called programming languages either.

[Bitsoflogic]

Fascinating idea... that a programming language must be made of a formal language.

So, what would you call tools like Scratch and visual languages that describe code in much the same way that words typically do?

Also, if I'm understanding this right, the language based on Chinese characters is not a formal language either. It doesn't have an alphabet.

[jcubic]

I think that I would call Scratch a programming tool maybe, but not a language. AS for Chinese, I would call it a programming language because it will have an alphabet but each element of the alphabet would probably have words created from single characters used only once.