On the Nature of Programming Languages

post by Martin Sustrik (sustrik) · 2019-04-22T10:50:00.862Z · LW · GW · 13 comments

Contents

  April 22nd, 2019
None
13 comments

What are we doing when designing a programming language? We decide whether it's going to be imperative or declarative. We add a bunch of operators. We add some kind of objects and visibility rules. We decide to make it either strongly-typed or weakly-typed. Maybe we add generics or inheritance, or maybe multiple inheritance. And so on.

The question that interests me is whether the nature of these tools is determined by the problems we want to solve, whether they are, in some way, inherent to or, in other words, directly inferrable from the nature of the problem at hand, or whether they are rather crutches for our imagination, a purely psychological constructs that help our imperfect brains to deal with the complexity of the real world.

If you asked me ten years ago, I would probably argue for the latter.

And it's not hard to "prove" it: If two people write code to solve the same problem and one makes a terrible spaghetti monster in COBOL while the other goes for super-elegant and highly abstracted solution in Haskell, does it really matter to the computer? As long as the two are compiled to the same machine code, the machine does not care. All the clever constructs used, all the elegance, they are there only to guide our intuition about the code.

So, you see, the design of a programming language is determined by human psychology, by the quirks and foibles of the human brain. If there are inheritance hierarchies in your language it's not because things in the real world tend to arrange in neat trees — in fact, they never do, and if you want to point out the tree of life, I have bad news for you: most organisms have two parents and the tree of life is really a DAG of life — it's because human brains like to think in terms of taxonomies. They just happen to find it easier to deal with the complex world in that particular way.

But is it really so?

If you asked me today I wouldn't be so sure.

But it's a question not easy to answer. If you wanted to really tackle it you would need to take human brain out of the equation, so that you can find out whether the same kinds of "language constructs" arise even without a brain having anything to do with it.

So here's the idea: What about genetic algorithms? They don't require a programmer. Yet we can look at them and determine if a language feature, say, encapsulation does emerge from the process.

Or, rather, given the relative scarcity of data on genetic algorithms, let's have a look at evolution by natural selection. There's a code (genetic code), just like any programming language it can be executed (thus producing a phenotype) and there's definitely no brain involved. And we can ask: Is it just a random mess of instructions that happens, by a blind chance, to produce a viable phenotype or is there any internal structure to the code, something that we would recognize as a feature of a programming language?

And, I think, the answer may be yes.

Let's have a look at the concept of "evolvability". What it says is that natural selection may, in some cases, may prefer individuals who have no direct, physical advantage, but whose progeny is more likely to adapt well to the changing evolutionary pressures.

But what does that even mean? Well, here's a concrete example:

Imagine two gazelles that are, phenotypically, the same. They look exactly the same, they behave the same etc. One would naively expect that neither of them would be preferred by natural selection.

But consider this: One of them has the length of the left rear leg encoded in one gene and the length of the right rear leg in a different gene. The other has the length of both hind legs encoded in a single gene. If that gene mutates both legs will be either longer or shorter, but they will never have different lengths.

Which of them is going to fare better in the race for survival?

I would bet on the single-gene one. When the environment changes and demands longer hind legs the evolutionary process would remain blind, some of the offspring would have longer legs and some of them would have shorter legs, but at least there wouldn't be the need to invest precious resources in all those unhopeful mutants with left leg shorter than the right one.

What the concept of evolvability says is that representation matters. The encoding isn't, in the long run, selectively neutral.

And as programmers we have a direct equivalent of the above: We call it subroutines. If the code is doing the same thing at two places, it's better to create a single subroutine and call it twice than to make two copies of the code.

Yet another example: Do you think that an organism in which every gene effects every part of its phenotype, the nose, the tail, the metabolism, the behaviour, is going to fare better than an organism where each gene is specialized for a single concrete task?

No, it's not. Every feature depending on every gene means that every mutation is going to change the phenotype significantly, in multiple ways. It's very likely that at least one of those changes is going to be deadly.

And again, there's a clear counterpart to that in programming languages. It's called modularity or, if you wish, encapsulation.

So, in the end, it seems the representation, the language features matter even if there's no human brain around to take advantage of them.

That is not to say that some of the language features aren't purely brain-oriented. Sane variable naming, for example, is likely to be such feature.

But still, at least some of what we have probably goes deeper than that and is, in fact, objectively useful.

Now, to end with a lighter topic: Although I am a big fan of Stanisław Lem and therefore I have pretty serious doubts about whether we'll be able to communicate with the aliens if we ever meet them (having different society, different biology, different brain, different everything is not going to make it easy) the reasoning above gives us at least some hope. If both we and the aliens write computer programs they are probably going to share at least some features (subroutines, modularity). Calling that commonality "understanding" may be an exaggeration but it's still better than nothing.

April 22nd, 2019

by martin_sustrik

13 comments

Comments sorted by top scores.

comment by ryan_b · 2019-04-22T15:19:30.718Z · LW(p) · GW(p)

My intuition is strongly opposite yours of ten years ago.

  • For example, there are Domain Specific Languages, which are designed exactly for one problem domain.
  • C, the most widespread general-purpose programming language, does things that are extremely difficult or impossible in highly abstract languages like Haskell or LISP, which doesn't seem to match the notion of all three being a helpful way to think about the world.
  • Most of what we wind up doing with programming languages is building software tools. We prefer programs to be written such that the thinking is clear and correct, but this seems to me motivated more by convenience than anything else, and it rarely turns out that way besides.

I would go as far as to say that the case of 'our imperfect brains dealing with a complex world' is in fact a series of specific sub-problems, and we build tools for solving them on that basis.

On the other hand, it feels like there is a large influence on programming languages that isn't well captured by the tool-for-problem or crutch-for-psychology dichotomy: working with other people. Consider the object-oriented languages, like Java. For all that an object is a convenient way to represent the world, and for all that it is meant to provide abstractions like inheritance, what actually seems to have driven the popularity of object orientation is that it provides a way for the next programmer not to know exactly what is happening in the code, but instead to take the current crop of objects as given and then do whatever additional thing they need done.

Should we consider a group of people separated in time working on the same problem, an independent problem? Or should we consider that working with people-in-the-future is something we are psychologically bad at, and we need a better way to organize our thinking about it? While the former seems more reasonable to me, I don't actually know the answer here. One way to tell might be if the people who wrote Java said specifically somewhere that they wanted a language that would make it easier for multiple people to write large programs together over time. Another way might be if everyone who learned Java chose it because they liked not having to worry that much about what the last guy did, so long as the objects work.

Replies from: ryan_b, rossry
comment by ryan_b · 2019-04-22T18:24:09.282Z · LW(p) · GW(p)

On the other-other hand, an example was staring me in the face that points more closely to your old intuitions: I just started reading The Structure and Interpretation of Classical Mechanics, which is the textbook used for classical mechanics at MIT. Of particular note is that the book uses Scheme, a LISP dialect, in order to enforce clarity and correctness of understanding of mechanics. The programming language is only covered in the appendix; they spend an hour or two on it in the course.

The goal here is to raise the standard of understanding the world to 'can you explain it to the computer.'

comment by rossry · 2019-04-23T22:55:11.028Z · LW(p) · GW(p)

C, the most widespread general-purpose programming language, does things that are extremely difficult or impossible in highly abstract languages like Haskell or LISP

Can you give an example? I'm surprised by this claim, but I only have deep familiarity with C of these three. (My primary functional language includes mutable constructs; I don't know how purely functional languages fare without them.)

Replies from: ryan_b
comment by ryan_b · 2019-04-24T14:53:23.847Z · LW(p) · GW(p)

The usual example here is memory control. The point of the higher-level languages is to abstract away the details of memory and registers, so there is no malloc/free equivalent when writing in them; for this purpose they use garbage collection.

Of course, eventually people found a need for addressing these kinds of problems, and so features to allow for it were added later. C reigns supreme in embedded applications because of the precise memory and I/O capabilities, but there is stuff for embedded Haskell and embedded LISP now. But note that in these sources they are talking about stuff like special compilers and strategies for keeping the automatic garbage collection from blowing everything up, whereas with C, you just mostly write regular C. Also interrupts.

comment by Viliam · 2019-04-22T12:40:28.360Z · LW(p) · GW(p)

I never designed an actual programming language, but I imagine these would be some of the things to consider when doing so:

1. How much functionality do I want to (a) hardcode in the programming language itself, (b) provide as a "standard library", or (c) leave for the programmer to implement?

If the programming language provides something, some users will be happy that they can use it immediately, and other users will be unhappy because they would prefer to do it differently. If I wait until the "free market" delivers a good solution, there is a chance that someone much smarter than me will develop something better than I ever could, and it won't even cost me a minute of my time. There is also a chance that this doesn't happen (why would the supergenius decide to use my new language?) and users will keep complaining about my language missing important functionality. Also, there is a risk that the market will provide dozen different solutions in parallel, each great at some aspect and frustrating at another.

Sometimes having more options is better. Sometimes it means you spend 5 years learning framework X, which then goes out of fashion, and you have to learn framework Y, which is not even significantly better, only different.

It seems like a good solution would be to provide the language, and the set of officially recommended libraries, so that users have a solution ready, but they are free to invent a better alternative. However, some things are difficult to do this way. For example, the type system: either your core libraries have one, or they don't.

2. Who is the target audience: noobs or hackers?

Before giving a high-status answer, please consider that there are several orders of magnitude more noobs than hackers; and that most companies prefer to hire noobs (or perhaps someone in the middle) because they are cheaper and easier to replace. Therefore, a noob-oriented language may become popular among developers, used in jobs, taught at universities, and develop an ecosystem of thousands of libraries and frameworks... while a hacker-oriented language may be the preferred toy or an object of worship of a few dozen people, but will be generally unknown, and as a consequence it will be almost impossible to find a library you need, or get an answer on Stack Exchange.

Hackers prefer elegance and abstraction; programming languages that feel like mathematics. Noobs prefer whatever their simple minds perceive as "simple", which is usually some horrible irregular hack; tons of syntactic sugar for completely trivial things (the only things the noob cares about), optional syntax that introduces ambiguity into parsing but hey it saves you a keystroke now and then (mostly-optional semicolons, end of line as an end of statement except when not), etc.

Hacker-oriented languages do not prevent you from shooting your own foot, because they assume that you either are not going to, or that you are doing it for a good reason such as an improvised foot surgery. Noob-oriented languages often come with lots of training wheels (such as declaring your classes and variables "private", because just asking your colleagues nicely to avoid using undocumented features would have zero effect), and then sometimes with power tools designed to remove those training wheels (like when you find out that there actually may be a legitimate reason to access the "private" variables e.g. for the purpose of externalization).

Unfortunately, this distinction cannot be communicated openly, because when you say "this is only meant for hackers to use", every other noob will raise their hands and say "yep, that means me". You won't have companies admit that their business model is to hire cheap and replaceable noobs, because most of their energy will be wasted through mismanagement and lack of analysis anyway. But when designing a language, you need to consider all the usual horrible things the average developer is going to do with it... and either add a training wheel, or decide that you don't care.

3. It may depend on the type of project. But I fear that 9 out of 10 cases someone uses this argument, it is actually a matter of premature optimization.

Replies from: gjm
comment by gjm · 2019-04-23T00:39:53.441Z · LW(p) · GW(p)

I think your h4ck3r-versus-n00b dichotomy may need a little adjustment.

It's true that some hackers prefer mathematics-y languages like, say, Haskell or Scheme, with elegantly minimal syntax and a modest selection of powerful features that add up to something tremendous.

But _plenty_ of highly skilled and experienced software-makers program in, for instance, C++, which really doesn't score too highly on the elegance-and-abstraction front. Plenty more like to program in C, which does better on elegance and worse on abstraction and is certainly a long way from mathematical elegance. Plenty more like to program in Python, which was originally designed to be (inter alia) a noob-friendly language, and is in fact a pretty good choice for a first language to teach to a learner. And, on the other side of things, Scheme -- which seems like it has a bunch of the characteristics you're saying are typical of "expert-focused" languages -- has always had a great deal of educational use, by (among others) the very people who were and are designing it.

If you're designing a programming language, you certainly need to figure out whether to focus on newcomers or experts, but I don't think that choice alone nails down very much about the language, and I don't think it aligns with elegance-versus-let's-politely-call-it-richness.

comment by rossry · 2019-04-23T23:15:02.894Z · LW(p) · GW(p)

I think it's from SICP that programs are meant to be read by humans and only incidentally for computers to execute; I've been trying for more than a year now to write a blog post about the fundamental premise that, effort-weighted, we almost never write new programs from scratch, and mostly are engaged in transmuting one working program into another working program. Programs are not only meant to be read by humans, but edited by humans.

I think if you start from the question of how much effort it is to write a new program on a blank page, most languages will come out looking the same, and the differences will look like psychological constructs. If you ask, however, how much effort it is to change an existing piece of a code base to a specific something else, you start to see differences in epistemic structure, where it matters how many of the possible mutations that a human algorithm might try will non-obviously make the resulting program do something unexpected. And that, as you point out, opens the door to at least some notion of universality.

comment by Shmi (shminux) · 2019-04-23T04:06:57.401Z · LW(p) · GW(p)

Like you, I am a fan of Lem, who is sadly, underrated in the West. And I am quite sure that we will not only be unable to communicate with alien lifeforms, we would not even recognize them as such. (Well, I do not even believe that we are a lifeform to begin with, but that topic is for another day.)

As for the programming languages, and your gazelle analogy, notice that you fixed the gene position, something that is not likely an issue for a non-human mind. Just restructure the algorithm as needed. As long as the effort is not exponential, who cares. Computer languages are crutches for the feeble human brain. An intelligence that is not hindered by human shortcomings would just create the algorithm and run it without any intermediate language/compiler/debugger needed.

Replies from: gjm, jmh, sustrik
comment by gjm · 2019-04-23T11:54:54.887Z · LW(p) · GW(p)

I'm intrigued by your topic for another day.

How do you define "lifeform" so as to make us not examples? (Is the point e.g. that "we" are our _minds_ which could in principle exist without our _bodies_? Or do you consider that _Homo sapiens_ bodies don't constitute a lifeform?)

Replies from: shminux
comment by Shmi (shminux) · 2019-04-23T15:26:49.262Z · LW(p) · GW(p)

I mentioned multiple times on this site over the years that any definition of life that is more algorithmic and not based on the biological substrate we happened to be built on is necessarily wide enough to include some of what we consider non-living objects, like, say, stars. Also discussed in my blog post.

comment by jmh · 2019-04-24T12:53:35.211Z · LW(p) · GW(p)
An intelligence that is not hindered by human shortcomings would just create the algorithm and run it without any intermediate language/compiler/debugger needed.

Is that a "There are 10 types of entities in the universe. Those the understand binary and those that don't" type of statement ;-)

I did find the initial question interesting but suspect it will remain one debated a while -- which is not a bad thing. Our existence is rather messy and tangled so ultimate truths or answers probably more transient than enduring.

comment by Martin Sustrik (sustrik) · 2019-04-23T05:02:14.735Z · LW(p) · GW(p)

AFAIU, your argument is that a super-human intelligence can look at the program as a whole, be aware that both hind legs need to be the same length and can modify the code at both places to satisfy the constraint.

While imaginable, in the real world I don't see this happening except for toy examples (say, an academic exercise of writing a toy sorting algorithm). Actual software projects are big and modified by many actors, each with little understanding of the whole. Natural selection is performed by a, from human point of view, completely mindless entity. Same for genetic algorithms and, possibly, ML.

The point I was trying to make that in such a piecemal, uninformed development, some patters may emerge that are, in a way, independent of the type of the development process (human-driven, evolution, etc.)

Replies from: shminux
comment by Shmi (shminux) · 2019-04-23T05:34:49.088Z · LW(p) · GW(p)

Ah, I agree that mindless factorized development can lead to similar patterns, sure. But to examine this conjecture one has to do some honest numerical modeling of the process as applied to... an emergent language? Something else?