Lambda the Ultimate

Historically, types for imperative code have not been very effective at describing what a program 'does' because of all the hidden side-effects.

But types are highly capable of addressing this concern, especially typed effects and substructural types. Substructural types even allow advantages of reasoning with structured programming, without the structure - i.e. enabling separation between the 'context free syntax' and useful behavior constraints. Typed effects can control which effects are accessible for a subprogram and may be used with substructural types to enforce at-most-N-times or at-least-N-times behaviors, or progress within a protocol. This lets us reason about what a subprogram does. Also, purely functional code, without side-effects, is just a structural transform. But pure functions can be used to model communication effects in terms of computing data structures which are then observed by the environment (e.g. an outbox or event list). So this also allows us to understand what a program 'does' by reifying actions into data structures.

Even without type checking, most programmers will continue thinking and understanding and documenting code in terms of types - they just won't have much help or interference from the machine. The lack of interference might be nice in cases that are difficult to typecheck without advanced type systems, e.g. when modeling generic routing code for messages of many different types. But most typed languages also have an escape hatch for these cases.

The essential difference between 'reason' and other modes of 'thinking' is that reason deeply concerns why you know something (the evidence, logic, etc.) - having reasons for one's beliefs. I don't equate reasoning with types, but types are effective evidence for valid reasoning.

As you say, for a program to be lucid, we should easily understand what it does. But lucidity doesn't directly have anything to do with reason. I.e. you don't have to know why you know what it does. (Your belief that "lucidity must ultimately be a form of reasoning" doesn't make sense to me.) Unlike types, lucidity certainly isn't compositional - i.e. if you compose a thousand individually lucid lines of code, the result is probably not lucid. But, at that scale, you might be able to organize and rewrite the whole thing to make it holistically comprehensible. At scales of "how many lines of code can civilization support" the rewrite option isn't feasible, and lucidity is not a viable possibility.

I am curious what sort of reasons and evidence you hope for developers to leverage.

I'll offer some miscellaneous thoughts on some of this. Other points I'll hope to explore later.

Historically, types for imperative code have not been very effective at describing what a program 'does' because of all the hidden side-effects.

Types for imperative code have not been very effective. That much I'm certainly comfortable with. It also seems safe to say the reason has to do with "side-effects", i.e., stuff that doesn't follow local syntactic tree structure as types do. It's also fair, I think, to say that imperative code can easily become hard to understand (opposite of lucid) due to this sort of non-locality getting out of hand, at which point the word "hidden" becomes appropriate. It seems a little over-enthusiastic on that point to presume all such things are equally "hidden" from a human reader; seems to me the imperative approach can sometimes be a lucidity gain, as well as sometimes a major lucidity liability, hence my caution here. I treat the proper management of imperative code as a major open challenge.

But types are highly capable of addressing this concern, especially typed effects and substructural types. Substructural types even allow advantages of reasoning with structured programming, without the structure - i.e. enabling separation between the 'context free syntax' and useful behavior types. [...]

I noted that material when you first put it on your blog. I'm still (more than a year later) looking for an opportunity to give it the in-depth careful attention it deserves. So that point is one I'll hope to address later.

The essential difference between 'reason' and other modes of 'thinking' is that reason deeply concerns why you know something (the evidence, logic, etc.) - having reasons for one's beliefs.

That sounds right. If there's a problem with that, I'm not seeing it atm, anyway.

I don't equate reasoning with types, but types are effective as evidence for valid reasoning.

Clearly stated. Which invites scrutiny. I see lucidity as a concern on both sides of the Curry-Howard corresponence, but with different lucidity goals that can conflict with each other. The traditional purpose of a proof is to make one's reasoning so lucid that everyone can agree on it. Modernly there's been some inclination to replace lucidity with machine-verifiability, and of course the difficulty with this is that if what you're sure of is that the machine says it checks out, your confidence in the result is then predicated on your confidence in the machine. I'm a traditionalist in that regard; like Wigner, I think it's well that the machine understands the problem but I want to understand it too. Even from the perspective of proof lucidity (setting aside program lucidity), it seems to me a sophisticated type system can become hard to follow.

As you say, for a program to be lucid, we should easily understand what it does. But lucidity doesn't directly have anything to do with reason. I.e. you don't have to know why you know what it does.

This sounds off-key, to me. The act of compehension may be effortless, so that you don't consciously think about the steps, but that's part of being really lucid, mimimizing the effort needed to grok the reasoning. If the "why" of the reasoning really isn't visible, then it seems that would imply that the lucidity is an illusion.

I distantly recall hearing of a techical paper disproving a conjecture of some sort (from context, it would have been in graph theory or perhaps geometry), where the whole technical content of the paper was just a picture. A counter-example, iirc. Now, in that case, the process of compehension is not explicit. It's not written out in the form of steps of formal reaasoning, and in fact it would probably be highly verbose and extremely un-lucid if written that way. But I don't think there's any lack of reason in that lucidity. Since this is a proof we're talking about — in the traditional sense, a proof to be understood by a human reader — the point is to make it perfectly clear, lucid, why the result is true. That's inherently reasonable, in the sense of reason you've suggested. I don't see why lucidity on the programming side of the correspondence should be any less reasonable — if you think you can see what a program does, but you haven't actually been given a reason to think that, then the lucidity is an illusion — although, again, it does seem to me that maximizing lucidity on one side of the correspondence would not reliably maximize it on the other side.

Unlike types, lucidity certainly isn't compositional - i.e. if you compose a thousand individually lucid lines of code, the result is probably not lucid. But, at that scale, you might be able to organize and rewrite the whole thing to make it holistically comprehensible. At scales of "how many lines of code can civilization support" the rewrite option isn't feasible, and lucidity is not a viable possibility.

I wouldn't assume that lucidity is all contained on individual lines of code. But yes, I quite agree that one wouldn't expect lucidity to be non-decreasing under composition. Complexity of the thing described should, somehow or other, place an upper bound on lucidity of description; and complexity ought to increase, in general, with composition, even if one is able to prevent it from increasing in a combinatorial explosion. Therefore lucidity must, in general, decrease with composition.

The code base supported by civilation doens't need to be comprehended as a whole in order to be supported, though, does it? Or does it. To what extent does the whole code base need to be coherent? And, when maintaining a particular software component, how much of what you need to comprehend is within that component, versus how much has to do with the surrounding software ecosystem in which it must operate? These strike me as rather fascinating questions; I don't have immediate suggestions on answering them, though.

I don't think lucidity has to decrease with composition. With type checking and theorem proving, it is possible to prove behavior conforms to simpler specifications. You could package a mutable data structure written with imperative code along with relevant proofs, so that from outside the code module it behaves like purely functional code. The proofs prevent implementation bugs breaking the abstraction, meaning the user of the component can treat it like a language built-in feature. Layers of domain-specific-languages can be built compositionally, but the user only needs to understand the top level.

Interesting thought. You're supposing here, if I understand you rightly, abstractions that don't leak thanks to type checking and theorem proving. I see a couple of potential difficulties in this scenario:

Preventing abstraction leaks is not easy. Some folks here maintain it's impossible. Big area for research and exploration there. Meanwhile, if your abstractions do leak, that would seem to provide a route for complexity to increase with composition after all.

Abstraction tends to make a system more brittle, thus reducing what can be done thereafter, including what abstractions can be done thereafter. This I see as another big area for research and exploration. How does the "shape" of an abstraction affect this ossification? (One might ask the same question about leakage: how does the shape of the abstraction affect it.)

I don't think it's impossible, and I think I know how to do it. This will be one of the core principles in the language I am developing. I can already write C++ code that has value semantics, so non-leaky abstractions are definitely possible, the remaining part is to guarantee they do not leak. I am reasonably sure this can be done with an effect system (which in my case will be embedded in monads in the type system) and substructural types.

Edit: On abstraction shape, I feel abstractions should try and fit established mathematical models, as this reduces the chance of making things brittle. For example having interfaces using algebraic concepts (groups, ring, modules) and fundamental programming concepts (iterators, containers, compound objects), category theoretic stuff like monoids, monads also.

I guess the discussion is havily biased by some task set that is not percisely identified, and I would suggest making the discussed task set explicit.

For example, as far as I see, many compiler developers try to optimize their languages for compiper developing. So language constructs are optimized for in-memory data transformation with assumption of results directly derived from unchanging input.

Alas, many applications do not follow these assumtions. They need to maitain state (both persistent and not persistent). They need to react differently at different moments of the time. Their input changing while application works (and it is almost only constant about it).

Imperative programming wins in industry not because of some obscure political reasons. It wins precisely because it directly corresponds to the tasks developers directly face. FP layer often is just jumping-loops way of changing state that could be just changed directly that offers a little benefit comparing to need of maintainig abstraction layers in the head. It is good for some tasks, but I'm yet to see a usable UI or database access library written in pure-FP way.

Just face it, the "side effect" is the precise reason programs exist at all (writing to screen or file is a "side effect"). The program without "side effects" just warms up CPU. So PL should make magement of "side effects" easier, rather than trying to eliminate them. I would suggest not to use the phrase "side effect" at all, as it confuses mind. Just use words "intended effect" or something else. I would even state, that PL should optimize for more externally observable effects per line of the code.

The same is for stateful computation, most program need to track relationship between past and future (we are not talking about compilers here, think insurance companies, shops, goverment services). It is actually why programs are deployed in the first place, because humans are actually very poor at maintaining such relationships.

I sometimes have very hard time explaining useful pieces of FP approach to developers in the field. When they see phrase "side effect", they get confused since the management pays them for "side effect" produced. It is not "side effect" for them, it is a "implemented requirement".

It is true that our software must eventually be bound to sensors, actuators, and state. But I don't believe we ever need side-effects to do this. By 'side-effect' I mean when a function or expression interacts with the outside world in addition to simply computing a value. However, we certainly cannot avoid side-effects if we stick to `void main()` as the interface for programs. When you have `() → ()` as a function type, then you have no choice but to perform side-effects in order to accomplish anything.

I've recently developed a simple machine model that supports purely functional effects. It's more or less this:

type Machine = (State, (Step, Signal))
type Step = (InMessage, State) → (OutMessages, State)
type InMessage = (Context, Content)
type OutMessages = List of (Capability, Content)
type Capability = Cap Context MachineID (opaque)
type Self = Context → Capability
type Signal = Context

A machine has some state, and a simple non-monadic step function. In each step, the machine receives one message, outputs a list of messages, and has opportunity to update its state. Machines can host machines, or even model communicating subnetworks of them, while remaining purely functional. The Signal value is essentially exported as a capability to the machine's host, enabling it to inject information about Self or environment, init, warn of impending halt for graceful shutdown, etc. The step function is separated from state to simplify live-programming and debugging and extensibility. A programmer can update the step function by tuning some source code, or may directly browse and manipulate machine state.

These machines may communicate with sensors and actuators and UI through messages. But at no point are there any 'side-effects' - no functions or expressions that interact with the world in addition to returning a value. This is possible mostly because I'm providing a richer functional interface than `void main()`. There are many other machine models or application models that could work just as well.

There is a big performance problem in your system. As you lump all application state into single immutable object, you have average O(ln(N)) [N - total object count in the state] update cost for the state (in case of simple and optimal data structures), because you will need to rebuild State after each update.

In contrast to it, imperative languages have cost O(1), because they do not need to rebuild data structures.

Also, in imperative languages the update is local to the data structure. In your case, the update has go through entire data structure from root, this increases the amount knowledge that programmers has to be aware of. And I'm starting to talk about problems of pure-functional languages with representing circular data structures, that greatly increases navigation cost for some situations. Just try to write function (connected_graph n) in haskell, where each node of the graph has list of references to each other node of the graph and a node number [Node(Int, Node List)].

BTW I'm aware about "amortized cost" concept for immutable data structures. It just not applicable here, becase State is not non-uniform for any application that is complex enough.

So approach you are advocating increases both CPU cost and human understading cost for normal business applications (for example accounting, that needs a lot interactions with persistent state and external systems).

In any physical system, memory is laid out in a 3-dimensional physical space. Consequently, speed-of-light delays between memory and any centralized processing unit increase by at least a factor of N^(1/3). Further, there is a lg(N) factor if we give every location in the space a unique address. Thus, if we account for physical constraints, the very best we can theoretically do for centralized processing of a data structure is O(lg(N) * N^(1/3)). At least with what we know of physics. In practice, memory tends to be laid out in two dimensions (surface of a board, surface of the Earth) so the factor is actually N^(1/2).

Usually, we ignore these physical factors. However, they're more difficult to ignore today than they were historically. Today, we have three levels of cache, NUMA, distributed shared memory models, using memory itself as cache for the disk, and so on.

If we do account for these physical factors, then functional data structures have the same asymptotic properties as imperative ones.

Conversely, functional structures can easily model physical memory - e.g. use a trie where every key is a 64-bit number. In this case, we can guarantee that the access and update is O(1) in the same asymptotic sense as is the case for physical RAM. Any update to the trie requires creating at most 64 new nodes.

So, no matter which perspective you take - physical or logical - functional code isn't asymptotically worse than imperative code.

However, FP does tend to be less efficient in every relevant absolute sense. Allocating 64 nodes is a lot more expensive than in-place mutation of RAM in a 64-bit address space. So, I do acknowledge that performance is a concern.

Performance can be divided into a few different concerns, such as efficiency, utilization, scalability. Efficiency: do we use our resources well? Utilization: do we use all of our resources? Scalability: can we easily throw more resources at the problem? (or gracefully take some away?)

While FP isn't doing so well with absolute efficiency, it can utilize resources and perhaps has greater potential for scalability (due to ease of parallelization, and location-independence of computations).

Further, due to structure sharing, FP performance tends to be more stable under external scenarios that might benefit from acquiring atomic snapshots of machine state: orthogonal persistence, time travel debugging, state visualization, live programming, rollbacks for exception-safe consistency, parallel reads and mirrored servers, etc..

So, while performance certainly is a concern, I believe FP fares very well - both asymptotically and absolutely - after we step back and look at the big picture.

problems of pure-functional languages with representing circular data structures, that greatly increases navigation cost for some situations

I'm avoiding direct representation of cyclic structures. Some FP languages do support them, e.g. via laziness. Mine doesn't. Developers must model cyclic structures indirectly, e.g. as a connectivity matrix or adjacency list.

State is not non-uniform for any application that is complex enough.

Surprisingly, state can actually be very uniform at the top-level - e.g. model an abstract filesystem using a trie. That will work for just about everything, much as a user filesystems works for a wide variety of applications. We can also leverage zipper on the state to efficiently and securely isolate substructures to different subprograms.

Whether zipping and unzipping state for each message is a significant overhead depends on how coarse-grained are our messages and how deep is our abstract filesystem.

approach you are advocating increases both CPU cost and human understading cost for normal business applications

I believe the human comprehension costs will ultimately be reduced. Compared to imperative state, pure state will be a lot easier to take snapshots for visualization, animation over time, experimentation and debugging.

When comparing imperative and functional style iteration, the kind of stuff you would compose maps and folds in functional programming, I and everyone who responded found the imperative code more understandable.

The reason appears to be the imperative code mutates a single object throughout all operations, the type and structure of which is explicitly stated and can be remembered whilst reading the rest of the code. Also indexed access with loops makes it clear what position in which object is being accessed. The functional version constructs many intermediate structures from the maps and folds, the types of which are never explicitly stated and have to be worked out as you read the code.

I wonder how many of those same people make or fail to recognize fencepost errors? Perhaps they're deluded about which ones they find more understandable. I wonder how many were adequately familiar with both approaches. Perhaps they were biased by familiarity. I don't trust ad-hoc polls without proper scientific controls. First Rule of Usability: Don't Listen to Users. (tldr: watch users, instead.) :D

Anyhow, FP certainly doesn't exclude manipulating a value with a familiar structure over multiple concrete, first-order steps.

Indeed, my current approach to FP is designed for this - i.e. you end up manipulating an abstract environment, which typically includes a Forth-like stack and some other stable objects, from one tacit concatenative step to another. This entire environment is represented by a plain old immutable value. It's very easy to 'think' in terms of imperative steps, while loops, repeat loops, foreach loops, asymmetric if statements, etc. and give programs a very imperative feel. There is no assignment statement, no aliasing. But it's still easy to 'increment' a number on 'the stack' in terms of a pure function that takes the whole environment and returns a new one.

Conveniently, because the environment is just a value, I can easily model a Forth-like stack, or a multi-stack environment, or a filesystem with 'cd' and 'ls' commands, or an interactive fiction model with multiple rooms and an inventory, etc.. I can tune or transform parts of the environment for each subprogram. I'm not constrained to a rigid stack+heap concept, and data structures aren't pinned by stateful aliasing.

Of course, nothing prevents users from modeling a stack+heap if that's what they want. E.g. our State could be a (Stack,Heap) pair, where Heap is a map from integers to values. Though, I don't believe this is very usable or comprehensible or visualizable or parallelizable or maintainable compared to many alternatives.

See: http://lambda-the-ultimate.org/node/5103

In summary, compare:

function permutations1(x) {
    return x.reduce(function(a0, v0) {
        return a0.reduce(function(a1, v1) {
            return a1.concat(v0.map(function(v2) {
                return v1.concat([v2]);
            }));
        }, []);
    }, [[]]);
}

with:

function permutations2(x) {
    var a = [[]];
    for (var i = 0; i < x.length; ++i) {
        var b = [];
        for (var j = 0; j < a.length; ++j) {
            for (var k = 0; k < x[i].length; ++k) {
                b.push(a[j].concat([x[i][k]]));
            }
        }
        a = b;
    }
    return a;
}

or even:

def perm xss 
   var tot = [[]]
   for xs in xss
      tot = [x:ys | x <- xs, ys <- tot]
   return tot

Ah, yes. I do remember not being very impressed with how you framed that question. We can, of course, write confusing code in any language. Your original code was even worse, with all sorts of array slicing noise.

We must be very careful where we attribute blame. What is due to functional vs imperative? What is due to how you chose to frame and factor the problem? What is due to the language of expression? If we aren't rigorous about this, or at least very cautious, we will mislead ourselves to whichever conclusions we wanted. The conclusion you're hoping for is, AFAICT: "FP would benefit a lot from good support for imperative algorithms". I'm happier with a conclusion that says FP rocks. As humans attempting rational discourse, we must beware our biases.

I find Matt M's variation much simpler and more comprehensible than your options. I also liked the cross-based impls.

def cross2 xs yss = [x:ys | x <- xs, ys <- yss]
def permutations = foldr cross2 [[]]

Though, realistically, for any non-trivial scale, I expect I'd want a diagonalization property for my permutations, and I probably want a stream (or generator) instead of a list (though, in Haskell, lists are streams). I'm sure I'd find a few ways to complicate this problem. :D

Yes,you can write confusing and complex code in any language. It is clear with effort we can write a clear functional version. My argument is more that the naive imperative version is clearer than the naive functional version. List comprehensions obviously help clarity, but that is a feature that can be in a an imperative or functional language, so we should factor that out of the discussion as I am sure we can contrive examples that cannot easily be expressed as list comprehensions.

The cross product was my suggestion, but you need to see the code not as a fixed point but an evolution. We write the naive version and refine towards the refined version. With the imperative example we start with something understandable, and we improve it. With the functional version we start with something far less understandable, and improve it.

In both cases we may end up with:

def cross2 xs yss = [x:ys | x <- xs, ys <- yss]
def permutations = foldr cross2 [[]]

Nobody came up with a foldr version in the original thread, and Matt's version with foldl was imperative as it had 'tot' as mutable variable. Although this is a correct solution, it seems most people don't think of it, and I for one find it hard to understand that it is correct from a quick look.

In any case this version would be valid in both an imperative and a functional context. So the refined version in both the imperative and functional languages may be the same, but the naive version is much more understandable in the imperative context.

with effort we can write a clear functional version. My argument is more that the naive imperative version is clearer than the naive functional version.

I think even a 'brute force naive' functional version would be a lot clearer if it were simply refactored into a few named functions.

It would also be clearer if you avoided JavaScript's attempt at OOP cleverness treating the functions as methods (forcing the developer to carefully validate that 'reduce' means the same thing each time, etc.)

List comprehensions obviously help clarity, but that is a feature that can be in a an imperative or functional language, so we should factor that out of the discussion

I'm not sure I should accept this logic. However, given that list comprehensions are just syntactic sugar for monads, which are supported by many FP languages and only a few imperative ones, here is an equivalent function without them:

def cross2 xs yss = do
 x <- xs
 ys <- yss
 return (x:ys)

And even if cross2 is brute-forced, i.e. such that you more or less reinvent monadic bind of the list (which itself involves map and concat functions), I think the resulting function would be clearer simply by breaking it down into a few reusable and independently meaningful pieces.

you need to see the code not as a fixed point but an evolution. We write the naive version and refine towards the refined version. With the imperative example we start with something understandable, and we improve it. With the functional version we start with something far less understandable, and improve it.

Imperative loops tend to be reinvented for every problem (which has its own problems with fencepost errors, etc.). Functional loops, modulo recursion, tend to be refactored into independently useful functions, and so clarity comes with experience and knowledge of these forms.

This does give FP a longer learning curve than imperative. But it doesn't mean we start with something far less comprehensible. Where we start depends on our knowledge, what we know to be a good fit. In this case, list comprehensions or the list monad are a very good fit.

It seems the taking longer to master argument actually supports my position, that it is less understandable. For any given competence level you would be able to achieve more with imperative code because you would need less brain power to understand it and therefore have the capacity to deal with bigger and more complex programs.

The relationship between learning curves and comprehensibility is not as simple as your arguments seem to require. A few points:

Code written by a neophyte in FP might be more difficult to understand than code written by a neophyte in imperative code. But this cannot be generalized to argue that code written by a master of FP is more difficult to understand than code written by a master of imperative.

The return on investment for time spent learning code depends to a significant extent upon reusability. For example, learning the `foldr` function has a greater ROI than understanding each imperative loop in context. Even if understanding individual imperative loops is easier, more brain-power may be saved in the long game with loop abstractions (or collections-oriented programming styles).

There is no clear relationship between how easily we understand someone's code and how much we can achieve. How many programmers try to read and grok the code behind the `cosine` function? or `sqrt`? or `sha1`? or the OpenGL API? Our ability to understand a function by reading its source is relevant largely to the extent we're expected to maintain it. This is probably more aligned with modularity and social issues in PL design (packaging, version control, documentation, trust, discipline, security, types, proofs, etc.) than with imperative vs functional.

Some emergent properties and requirements only become obvious at scale. As a general rule, comprehension for toy examples is never a good basis for estimating comprehension of a much larger system developed in the same style. For those 'bigger and more complex problems', it is my experience that imperative style does not scale gracefully to deal with concurrency and view consistency, partial failure, persistence and upgrade, and other concerns. Functional has its own problems with integrating open systems, but I think those are easier to deal with (cf earlier 'effects' post).

Seems to me comprehensibility, while of evident great interest, is not the only question you want to ask. You want to consider the shape of the space of possible programs in the neighborhood of the one you're looking at. Are there incorrect solutions "nearby" in the sense that they're hard to distinguish from a correct solution? Are there reasonably nearby correct solutions to other related problems?

Yes, it's very nice if a solution isn't easy to get wrong in a subtle way, or is easy to compose with other solutions, or is easy to partially reuse in related problems.

I still think its hard to work out what the intermediate types are in a functional style. If we have a mutable container object with clear structure we know that its type remains the same after mutation. This is clear that the imperative loops, and mutable update cannot change the type of the container.

With the function style of composing functions, intermediate types are not obvious (you will have to consult the type signatures of functions, which with pervasive type inference may involve further mental gymnastics working out the type of each function in turn. Also each function is likely to output an intermediate value of a different type. Yes, you can memorise the type of foldr and foldl, and such things may eventually become second nature, but is memorising the type signatures of a whole bunch of standard functions really a feature of a good language.

In many cases having the smallest set of reusable primitives to learn the types of, that allow for straightforward efficient implementation would be best. If you add something like fexpr to functional programs you can get 'macro' style functions that behave like 'for' loops, and with references you can have mutable containers. So imagining a language that is the convergence of imperative and functional, it could all just be a matter of style?

If we have a mutable container object with clear structure we know that its type remains the same after mutation. This is clear that the imperative loops, and mutable update cannot change the type of the container.

This seems closely allied to what I've been saying about types. The type of your mutable container is insufficient to prove correctness the program, so you need some additional non-type-based means if you want to prove correctness. Conversely, if you insist on pushing your reasoning all through the type system, you end up with much more complicated types. The imperative approach is one way to decompose the reasoning.

If you add something like fexpr to functional programs

I suspect you may find that the type-theory folks don't know how to cope with fexprs. I of course don't have this problem because while I'm interested in fexprs, I'd be tempted to count inability to type fexprs as a point in favor of fexprs. :-P

If you're comparing apples to apples then scalar insert/delete operations on functional collections will preserve types in the same sense as insert/delete on mutable collections.

In general, even imperative objects can be understood to change types over mutation. Some languages explore this explicitly, e.g. the Plaid language with typestate. But even without language support, we track this kind of type in our heads using descriptions like "life cycle" and "initialization" and whether a file-handle is "open" or "closed".

I don't believe functional vs. imperative has an inherent advantages with regards to simulating intermediate states in one's head. Honestly, I'm not fond of reading code and trying to use my organic brain to simulate the machine in either case. I am interested in automatic visualization during development, rendering inferred types and/or test values to make this information concretely accessible. The whole live programming concept seems like a good idea.

[does] memorising the type signatures of a whole bunch of standard functions really make a good language

I believe so. Humans are good at learning details for lots of things, keeping them in the back of the mind, drawing upon them through habit and associative memory. When we have a big vocabulary of easily reusable functions, that puts a lot of programming power at our fingertips.

Though, there are some constraints. We must keep boiler-plate to a minimum or it spoils the reuse. There are limits on the interface complexity of a function for effective memorization (e.g. the five-to-seven rule). Humans are much better at memorizing concrete concepts (like `foldr` or `pairwise`) than abstract ones (like `monad bind`). We should avoid learning curves so steep we need special equipment to climb them.

But we can do a lot within these constraints.

In many cases having the smallest set of reusable primitives to learn the types of, that allow for straightforward efficient implementation would be best.

Having a simple and solid bedrock is very useful, especially when things break. But this isn't exclusive with having a large library of reusable functions to gradually learn and master.

If you add something like fexpr to functional programs you can get 'macro' style functions that behave like 'for' loops, and with references you can have mutable containers.

Since FP is a paradigm largely defined by its useful constraints, I don't believe you can abandon those constraints and still have functional programming.

Haskell has metaprogramming implementable using type-classes and purely functional state containers? Is Haskell a functional programming language? ML provides references, and MetaML provides meta-programming facilities. Is ML a functional language? Is an imperative language with first-class functions not functional?

Personally I think the important property is regularity. That is when a function or procedure is called with the same arguments it should produce the same results. I don't think it matters whether those results are returned by mutation of the arguments.

With macros or fexprs, if you aren't careful, you can lose a lot of properties like referential transparency (e.g. a macro might distinguish between `2 + 2` and `4`) and alpha equivalence (e.g. a macro might distinguish whether a function is called 'foo' vs. 'bar'). The presence of macros can have a strong effect on what sort of refactoring you can perform while reasoning that it won't impact behavior.

Many earlier languages (Lisp, ML, OCaml, Erlang) have functional aspects but too easily used the imperative escape hatch to really offer a functional programming experience. Haskell greatly advanced the art and really made functional programming a thing.

Though, even Haskell leans very heavily on the imperative style and FFI bindings via the IO monad. How to more functionally address UI and database interactions remains an ongoing experiment in design.

Regarding 'purely functional state containers': Haskell's ST monad and STRefs can be modeled in a purely functional manner, and so we can understand it as a useful optimization.

But I won't be using that for my language. Simplicity is one of my own primary goals. Adding features for mutation then trying to keep it safe and isolated and ensure it interacts well with parallelism is a lot more complicated than just avoiding the whole issue.

I agree with your points, I just think my emphasis is different. If you can insert and delete values from containers that's half the problem. I do think that a list of statements can be clearer than a single expression. Consider giving instructions to a person, imperative is like an ordered list of steps. Functional is like trying to say everything in one sentence.

Purely functional programs can have a very imperative 'feel' to them, like lists of instructions. This is especially the case for concatenative FP (like the Joy, Kitten, or AO languages) or monadic expression (e.g. monadic parser combinators).

I posit the "trying to say everything in one sentence" impression you get from FP would be better attributed to the applicative style of expression. I grant there is a very strong historical correlation between languages with FP aspects and the applicative style.

For most hardware architectures, these numbers are fixed and are not dependent on the program size (cache trashing requires surpassing certain fixed limit rather than dependent on N). So insteand of O(log(N)), we have O(ln(2^64))=O(1). In any case, cost of pure FP is multiplied with hardware cost, so ignoring hardware cost does not invalidates analisys. If anything, pure-FP increaes potential memory load and at least triggers GC more often (which is a kind memory load as well). And thus increases all memory associated costs.

Note, I'm all for pure FP, where it is applicable. I just find an idea emulating state change with immutable structures only suitable for niche applications (where you actually need to track history).

Imperative code is more generic than pure FP, so it is nice to have demarcated islands of pure FP inside imperative code. But I think that reverse situation of having islands imperative code inside pure FP is bound to cause unnessary complexities. If something is going to change, it is better to model as such in the code, without building layers of state change imitation, like it is done in haskell with monads. Note, that even in haskell, IO monad is contagious, and we still have islands of pure FP in stateful code. It is just a statful code looks horrible and hardly manageable comparing to normal OOP. And haskell looses tail recursion (except for trivial cases) when monads are used.

BTW many assumptions about amortized cost of immutable collections break up, if you keep history too. Some performance and memory properties hold up only if you allow old copies to GC.

cost of pure FP is multiplied with hardware cost

FP tends to be less efficient by some linear factors. But the asymptotic factors are simply subsumed by the hardware costs.

triggers GC more often

Depends. Refct GC wouldn't be triggered more often. Mixed mode GC works really well at large scale: compact a bump-pointer nursery, trace a generational space, reference count the long-lived persistent stuff.

emulating state change with immutable structures only suitable for niche applications (where you actually need to track history)

For productivity as a programmer, I would think ability to track history in a debugger is useful for every application. Same for anyone who is concerned about security and data loss and the ability to quickly recover a system.

Though, I wouldn't mind support for SAFL-style optimizations for deployment of applications where performance is the more important concern.

If something is going to change, it is better to model as such in the code, without building layers of state change imitation

If you want to talk about what is better, then efficient performance is only one good property among many. Imperative stateful aliasing isn't better in many respects that I find important, such as simple behavior under concurrency, easy orthogonal persistence, easy upgrade and extensibility and live programming of behavior, visibility and debuggability of state, etc..

It is just a statful code looks horrible and hardly manageable comparing to normal OOP.

I think those AVMs will be a lot more manageable compared to OOP. It's easy to see all the state, and to create ad-hoc views of the state (lenses). One might think of the AVMs as a variation on E's vats, capable of modeling a large number of 'objects', but where the objects are bound to specific locations in state similar to a filesystem.

haskell looses tail recursion (except for trivial cases) when monads are used

No it doesn't.

many assumptions about amortized cost of immutable collections break up, if you keep history too.

Depends on the collection types involved. Tries don't have this problem, for example. Neither do finger-tree sequences, which make excellent deques and adequate array-replacements.

The simple two-list banker's queue does have this problem. But even in such cases, performance overhead isn't a significant issue for most uses of keeping history, such as time-travel debugging or resilient recovery.

Please explain how tail recursion is compatible with "do" operator in haskell (IO monad case). To the best of my knowledge - it is impossible due to "do" operator design. It is sometimes possible to work around lack of tail recursion using monadic loop combinators, but this is manual replacement of recursion with iteration, all possible clarity advantages of tail recursion are lost. The code looks just like a plain iterative code.

I not sure I get the problem with monadic tail decision as:

a <- someM
return a

Can be replaced with:

someM

I accidentally replied out of thread, but decided to leave it. I'm feeling squashed against the right margin here.

Concurrency in the Actor Model can be exponentially faster than the Parallel Lambda Calculus.

Please see the following articles:
* Inconsistency Robustness in Logic Programs
* ActorScript

Swiss cheese is the answer to the scheduling conundrum.

In the Swiss cheese paradigm,
* Referential transparency holds in a continuous section of cheese (mutual exclusion)
* Holes are allowed in the cheese (e.g. for internal queues and external operations)
* A variable can change only when transitioning out of cheese or to an internal delegated operation

Please see the following articles:
* Actor Model
* ActorScript

The act of compehension may be effortless, so that you don't consciously think about the steps, but that's part of being really lucid, mimimizing the effort needed to grok the reasoning. If the "why" of the reasoning really isn't visible, then it seems that would imply that the lucidity is an illusion.

Yes. Lucidity is oft an illusion.

Not all reasoning is valid. Even when humans are consciously reasoning, we fall prey to a panoply of fallacies and biases. When reasoning is subconscious, this happens more easily. Lucidity is nice when we have reason to trust the argument is also correct. But lucidity works equally well for the arguments of charlatans and con-men, or for self-deception, articulating plausible arguments for whatever we wish to believe. Lucid code can still be buggy or hand-wavy or incomplete.

I don't trust lucidity.

But I do appreciate lucidity as an aesthetic property.

Ah. It seems we're using "reason" pretty much the same way, but "lucidity" a bit differently. To me, it isn't really lucid if it only seems to be clear. When there's a hidden flaw in the reasoning, that's not "lucid". So when I ask for lucidity, sound reasoning is integral to what I'm asking for. (There are two different ways to interpret "the lucidity is an illusion": mine would be that "there seems to be lucidity here, but it's really not lucid", the other interpretation of those words would be "it's lucid, but deceptively so". For me, the lucidity that is deceptive is not the true lucidity.)

The opposity of lucidity would be turgidity. At least if you have obvious turgidity, you're probably better off than if you had the deceptive illusion of lucidity. But actual lucidity would be best.

If a program is truly lucid only when it's not deceptive, then I think it will be very difficult to recognize a lucid program or distinguish it from a deceptive program. At least, this isn't something humans will be good at distinguishing. Especially not when humans are in the habit of subconscious reasoning because many subprograms seem lucid. And, without types or other proof annotations or a language designed for inference, machines probably won't help much.

I'm interested in ways for humans to comprehend code that marginalize reading of code, such that lucidity becomes a non-issue. E.g. can we make it easier to graph and visualize behavior? animate computation? extract and understand arbitrary subprograms? automatically find edge-cases? I have pursued alternative metaphors towards this end.

If a program is truly lucid only when it's not deceptive, then I think it will be very difficult to recognize a lucid program or distinguish it from a deceptive program.

It's worth saying — in fact, it's worth saying often — that there are things can be done to make code less error-prone. Not just big, extreme things, but little things that add up, all the way from PL design to code formatting. When I program, I put a lot of my effort into its (heh) lucidity. Remember that big security bug that everyone was talking about a while back, that revolved around code like this:

if (first hairy condition)
        goto error;
if (second hairy condition)
        goto error;
        goto error;
really important stuff;
error:
other stuff;

When we were discussing it here at LtU, I made what I thought was an obvious suggestion, that it probably wouldn't have happened if the PL required some sort of endif delimiter. I was surprised to find I actually got some resistance on that suggestion. Actually, if I were writing that code, in that way, and I'm not allowed to modify the PL design so that it requires an endif delimiter, I would be inclined to write it with each goto on the same line with the if and vertically aligned with the gotos on other such lines, like this:

if (first hairy condition)  goto error;
if (second hairy condition) goto error;
really important stuff;
error:
other stuff;

Again it would be very difficult to slip in an extra goto there because it would stick out like a sore thumb.

without types or other proof annotations or a language designed for inference, machines probably won't help much.

There are things humans are better at than computers, and things computers are better at than humans. I'm particularly concerned that, as we try to bring computers to bear on what we're not good at, we get absolutely maximal leverage out of what we are good at. Human strengths are precious, and I don't want a drop wasted. I'm more willing to spend CPU cycles.

I'm interested in ways for humans to comprehend code that marginalize reading of code, such that lucidity becomes a non-issue.

I'd say lucidity is an issue regardless of whether the representation is text or something else; but I understand your point to be that text has drawbacks. I note it also has advantages. Text isn't good at the sort of relationships that the geometry of a visual representation can bring out quite effectively — you'll notice that my example above actually uses the geometry of the text layout — but when it comes to complex meaning, text is really quite versatile and high-bandwidth. Actually, I sense there's something more to it than that. Perhaps it's that text is language, and language seems very closely allied to what makes us sapient.

I've been quite interested in visual, or at least partly visual, programming myself for many years. I've heard things from my mother about the heyday of flowcharts; I get the feeling that's an area where, in our haste to disown a rejected paradigm, we've (as usual) thrown out more than we needed to, and consequently eliminated what we didn't like at the cost of also losing something worthwhile.

lucidity is an issue regardless of whether the representation is text or something else

To clarify, I'm NOT suggesting we change to a visual or pictographic representation then read that. I would like to marginalize reading code entirely, shift to alternative modes for comprehension that don't involve reading code and simulating machine behavior in one's head. This might involve easy machine simulations of code, live programming, automatic debugging and fuzz-testing, graphing or animating functions, compositional properties that make it easier to reason without reading, centralization and visibility of state in running programs.

Lucidity will be an issue in presentation regardless. But maybe we can separate this from representation, and instead treat it as a tooling concern like good UI.

Human strengths are precious, and I don't want a drop wasted. I'm more willing to spend CPU cycles.

I agree! But human attention is also a precious resource. There is a limit to how widely we can apply our human strengths. When our attentions are allocated inefficiently, much of our strength is wasted.

While humans are undoubtedly better at writing human-readable code compared to machines, we aren't very strong at writing it in any absolute scale (most humans aren't lucid even with natural language), and we aren't very strong at reading even the most lucid of code (it still involves pretending to be a machine and simulating code segments in our heads). The pursuit of 'readable code' may be an inefficient allocation of our attentions, and thus a waste of our strengths.

marginalize reading code entirely, shift to alternative modes for comprehension that don't involve reading code and simulating machine behavior in one's head. This might involve easy machine simulations of code, live programming, automatic debugging and fuzz-testing, graphing or animating functions, compositional properties that make it easier to reason without reading, centralization and visibility of state in running programs.

I very much favor everyone having the chance to pursue their ideas (which figures, considering the unconventional stuff I pursue). Fwiw, the vision you're after here isn't one I'm seeing. The things you're describing sound to me like they'd be imprecise/low-bandwidth on the discontinuities of behavior that characterize programming. They sound to me like things that might make useful tools for examining something already readable, but still you'll always be better off mazimizing readability without letting any of those factors get in its way and only then, secondarily, providing these augmenting tools. (This is not entirely dissimilar to my disapproval of WYSIWYG; it seems to me systems of long-term importance are grounded in actual text, not hiding it behind a WYSIWYG interface. The underlying text can describe all kinds of wonderfully displayed material, but you should always go back to the ground representation to work with it, and when you stop doing so the system is on its way to long-term irrelevance.)

I've been translating a Unicode processing library from C to Lua and I've been surprised by a few things:

1) Even though I've been programming in C and C++ for decades my eye can parse the Lua code much faster.
a) part of it is that

if ( EXP ) statement
else if ( EXP ) statement
else statement

is harder for my eye to encapsulate than

if EXP then statements ...
elseif EXP then statements ...
else statements ...
end

And to my surprise I'm finding that forcing closures to be

function (var, ...) statements ... end

is easier for my eye to parse than (lambda ...)
b) another bit is that Lua's grammar doesn't reuse operators in different positions and meanings (other than '-' and '(' ). It has to be like that because it is designed so that statements can usually touch each other with no intervening end of statement character or end of line. It's very limiting but it pays off too.

2)In Lua it's a parse error to have unreachable code.
So your example wouldn't parse.

There's a bug in the alpha version of Luajit where code is judged unreachable but IS reachable with a goto.

Even though I've been programming in C and C++ for decades my eye can parse the Lua code much faster.

I've been observing lately that I find JavaScript syntax almost impossible not to get wrong (after several years of working with JavaScript — not by personal choice, admittedly), and Lua fairly easy not to get wrong (after an afternoon reading about it).

And to my surprise I'm finding that forcing closures to be

function (var, ...) statements ... end

is easier for my eye to parse than (lambda ...)

Efforts to reform Lisp syntax tend to focus on allowing arithmetical expressions to omit some of the parentheses. I think that's completely backwards. I fully parenthesize arithmetical expressions in languages that don't require it (removing operator precedence from the picture). To me, the place parentheses don't work is larger-scale structures; I'd like to replace them there with some sort of flexible block syntax based on linebreaks, indentation, and delimiters of the same ilk as 'endif' etc.

When you get the code from the "low cost" indian offshoring company, you would likely prefer code havily annotated by types, and with some unit tests. The lucidity is good when you have time to polish code and could take a time at undestanding it.

For industrial cases, the teams are pushed at the boundary at which they could handle the code. The code is written while the team is capable handling it, then code is thrown off and the application is rewritten. But the most time of code existence, the development team is bareably capable of handling the code. For the good team, the amount of code they could handle is just bigger, but every team could be overloaded (and every team would likely be overloaded, since requirements from business are infinite).

In case of overload, so programming language features preferable to lucidity: locality, intention capturing, simplicity of understanding. I would gladly pay with textual "noise" of type annotations for this.

One of reason haskell-like type inferrence did not catch up yet, because it assumes that developers understand the code they are dealing with. In most cases, this is a wrong assumption. The modern developers mostly deal with code written by others, and modern systems are so big, that only partial understanding possible (particularly if we consider the libraries and containers). The explicit type annotations are very helpful there.

seems reasonable to suppose that the structure of human languages is correlated with what humans find understandable

This might be reasonable if humans didn't have so much difficulty understanding each other. Who's on first?

I've read a bug report on that incident. Tragic. If only the whole thing were staged. (is there a standard emoticon for trying to keep a straight face?)

Life imitates art. Our contextual languages are inherently ambiguous, which I would think is the exact opposite of what we want for computation.

is there a standard emoticon for trying to keep a straight face?

Perhaps :-|

I don't think the contextuality of our natural languages is what makes them ambiguous.

If a sentence's meaning can only be ascertained when paired with a context, that sentence is ambiguous by definition. Certainly other types of ambiguities may exist, but this only reinforces my skepticism that the structure of human languages is correlated with what we find understandable. I don't see how more ambiguity could help understanding.

Further, we could very well have special-purpose brain structure that evolved specifically to learn our first natural languages, brain structures which aren't engaged in general reasoning. Expressing and understanding general reasoning is what we're after, right? Studies have shown that people make more rational decisions when they reason using languages they learned as adults, rather than their first languages they intrinsically understand.

If a sentence's meaning can only be ascertained when paired with a context, that sentence is ambiguous by definition.

With respect, no sentence's meaning can be ascertained without its context.

You're equivocating on "context". If a word has more than one meaning, which not all do, it requires context to establish which meaning is intended. We don't classify "english" as context when conversing in the english language.

Fortunately, this demonstrates exactly how humans don't understand each other even with natural languages. Even with non-verbal cues, like tone and body language, these subtle ambiguities on "context" don't seem to lend themselves to understanding.

I think he is actually referring to the fact that we learn the meaning of terms by experience. Consider the word "human". What is a human? Given the command, do not harm humans, how do you determine if the object in front of you is human or not. The command is absolute, having a meaning about humans, but your definition of human may be incomplete. You may not believe the object is a human, but when you harm it, a jury of your peers will find you guilty of harming it nonetheless.

All in all language is meaningless without the culture and society that has agreed the meanings of the words. Meaning is learned through language-games. Non-ambiguous words still have indefinite meanings, ambiguous words (where the same word is used in more than one language-game) not only need the social and historical context to be understood, but also an implicit understanding of which language-game we are playing.

Yes. Some of this is already visible on the programming side as well, even in traditional PLs. The meaning of an identifier depends on its context; we can associate the identifier with a function mapping environments to values, and say that's it's meaning, but this amounts to saying we have no idea what it means until we learn more aobut its context. The context-dependence gets more intense when you get to fexprs. Lisp has no notation for code, only notation for data. For example, the "meaning" of

($define! a ($lambda (p) (not? (p p))))

is not a function definition; it's a list of three things, of which the first two are symbols and the third is a list of three things etc. In a rewriting calculus for such a language — say, vau-calculus — every source expression is an irreducible form, as it's already a data structure, which is to say, a constant. If you restrict the equational theory to only source expressions, of course it's trivial (and that's even if it doesn't have fexprs or even quotation). A source expression only participates in nontrivial computation if you embed it in a context that says "evaluate this in such-and-such environment". That's akin to the earlier observation that the meaming of a symbol depends on its context, but the pervasiveness of the principle is more apparent.

For A(M) the total size of executable image required to run program should be counted. Not just per line increment for plain source code. This include all runtime infrastructure required to support the code (GC, JIT, etc). OOP and FP have problems without GC as memory management overcompliate contract (I would state that they are unfeasible, and loops through which C++ library designers need to jump just prove it).

Also in A(M) you should include the code that is generated by containers and frameworks (EJB, JPA, Ruby on Rails, CPS-rewrite for FP, etc). This code is not included into A(C) because user does not change it directly. But this generated code contributes to A(M). Also most implementations for generics generate specialized code for the specific sets of type arguments. This also contributes to A(M). I'm not talking much about libraries here, which became much more feasible in OOP and FP than they were in structured programming world. Many things like collections libraries were simply unfeasible for C (in my personal recollection of C programming, about 25% of work was different implementations of linked lists and another 25% was error handling code [it was ODBC driver implementation]).

My statement is that user does not code in PL, user codes to platform that inculdes libraries and virtual machines and other stuff needed to run the code. A(C) is user code. A(M) total machine code needed to run application. It could be argued that Java is somewhat bloated and loads too much when starts. But eve for haskell, every program should do some IO (otherwise it would just warm up CPU) and IO library for haskell has greater A(M) than for C or Pascal.

Unikernels (Mirage, Ling, etc.) offer us a pretty effective way to measure the true amount of machine code used to run an application, at least on the server side. (This doesn't readily account for browser-side support.)

I expect A(M)/A(C) has actually been shrinking, or that it ideally should be. I.e. rather than code that blows up into a much larger machine, we're developing code that simmers down into a compact machine through type erasure, dead code elimination, partial evaluation, etc.. Though, this is mitigated by code reuse to form lots of different machines from a given line of code.

Unikernels will help to to guess how much static code is required. They will not help guessing about runtime. And GC-aware machine code is simply bigger than GC-unaware.

With C, one has pertty good idea on what happens in runtime, not such a good idea as with ASM, but still there is a clear correspondence. With Java, one have a little idea. But when we add runtime codegen, the code explodes. In Java, even reflection uses runtime codegen. It is hidden from user, but it still happens and it should be included into A(M).

A(C) are actual lines that are modified by user to achieve desired functionality. In modern PL, there are a lot of the machine code to support it, and a big portion of the code is generated in runtime. And A(M)/A(C) should be measured on programs that do the exactly same functionality: hello word, accounting with the same UI. Mainfame accounting application and web accounting application are generally not comparable, since function is somewhat different. Total behavior complexity (including handling web requests) of web application becomes affordable only with GC OOP and FP languages. With C++, web applications require highly skilled developers to write somewhat reliable code minor error could cause crash of the entire application.

Just compare ideomatical code for hello world in different languages. C and ASM would clearly win in size over Java, Haskell, or C++.

It maybe useful to treat the A(M) as actually executed code. So iterpreter actually execute less unique instructions. However, the iterpreter will execute them more often, so usually A(M) for interpreter is greater them for compiled code. The higher level languages cause more code to be executed on CPU per line of user code (if they do not do more observable funtions per line of code).

OK, that makes sense to me.

Perhaps we can abstract away the A(M)/A(C) ratio by assuming something like a Kolmogorov complexity -- some irreducibility. I am being a little handwavey here but let's see:

For a given M, hence a fixed A(M), we have a choice of notations for C. (The notation for C includes all the code needed to implement the notation system itself.) There is a hard lower bound on A(C), for that fixed A(M).

So with "perfect" programming platforms, optimal A(M)/A(C) is finite and irreducible.

The social question -- hence the language design question I have...

Well, let's suppose that PL design aims to produce systems in which A(M)/A(C) is generally close to maxed out.

Over time that ratio converges on some limit.

How big a A(C) can we handle?

To make this a little more concrete, maybe: It seems typical of modern programming language design to try to make it easier to raise the A(M)/A(C) ratio, mainly by emphasizing mechanisms of composition.

How valuable, really, are these mechanisms of composition? And when do they start causing us problems when we use them to build systems too much bigger than our collective head?

Firstly, I would not bother about possibility building software that we cannot maintain. The problem that we would have a hard time designing such software. Such projects usually fail at much earlier stages.

Also, we likely need to fix something other for comparision. There are two things that comes to mind Intention and Behaviour. The Intention is a real life problem that program need to solve (business requirements). Behaviour is externally observable behaviour. With contant B, higher level languages usually have less A(C) and more A(M) than lower level languages. With constant I programs designed for higher level languages has more extensive B (at least more bells and wistles). Compare modern enterprise web application and mainframe screen entry application.

New composition principles in PL reduce amount of the information to be considered when making a decision about the code. FORTRAN required to be aware every other line of the program (think "go to"). Structured programming reduced prerequise awareness space for code to parent blocks and procedure calls. OOP reduces normal awareness space even further (bug hunting is a completely separate topic, particularly in non-GC languages).

So each compositional principle makes decision making more efficient. And these composional principles are not something IT specific, these principles is just how human brain works.

Piaget studied these mental composion principles long ago and approximage correspondece is (the correlation is mine):

• Non-programmable calculator language = Sensomotor stage
• ASM, FORTRAN 77 = Pre-operational Stage
• C, Pascal, Algol = Concrete Operation Stage
• OOP, FP = Formal Operation Stage

There are theories that extend this sequence further. Acording to them the next compositional principle is systemic principle. If we look at emerging techologies, the next step in reducing awareness comes from grid and cloud technologies. We somewhat loose awareness of location, time, and of application composition.

These techologies heavily rely on feedback channels to regulate their behaviour and they are acutually ready to failures. OOP programs currently usually suppress some behaviour in case of failure (and notify user), new software design principles actually try to recover from failure. This is actually a new way of thinking, and I sometimes have a hard time discussing these kind of issues with developers as they got lost in circular casuality that is common in such systems.

Software systems have a life cycle. They are conceived, planned and built, put into use. They usually(?) do not continue to operate without periodic maintenance. They typical(?) must eventually be replaced.

This is abstractly similar to bridges. Bridges are planned and built, put into use, maintained, and retired or replaced.

If I asked: "How many bridges can civilization support?" I think we'd all agree that there is a kind of upper bound based on population size.

It's certainly possible for a civilization to build more bridges than it can maintain -- to run into crises associated with a crumbling bridge infrastructure. Every individual bridge might be well built and well designed. Yet society can easily build and come to rely upon more bridges than it can manage to maintain and retire/replace as needed. (Arguably, the U.S. has done exactly this.)

Romans can build more roads and more very good plumbing than the empire can manage. The crumbling roman infrastructure helps to shape and accelerate the collapse of the roman empire.

Civilization's aggregation of software system seems to me similar to bridges and roman engineering: From a "localized" perspective, every part of the software system can be a well engineered, easy enough to understand piece.... but.... the aggregation of software systems can nevertheless have a higher maintenance budget than civilization can afford.

New composition principles in PL reduce amount of the information to be considered when making a decision about the code.

Yes, code be made easier or less easy to reason about locally, but that doesn't say much about the scale of how much code civilization can manage in aggregate.

Bridges require maintenance, and have limited life, because there are physical constraints on their construction; their intended use causes deterioration; and they undergo wear from external factors, other than their use, over which we have substantially no control.

Software requires maintence and has limited life because it has to interact with its platform and with other software. Constraints on its construction are either consequences of the hardware it runs on, which so far doesn't seem to have been part of the focus here, or are seemingly self-imposed by us. The intended use of software shouldn't have to cause cumulative deterioration... in principle. External factors are what I named in my first sentence, interation with platform and with other software, but it seems on the face of it we ought to have a lot of power to minimize those too.

So I'm not so sure the analogy with bridges is as close as might first appear, at least not for extrapolating potential.

With software, a better analogy might be "how many social relationships can civilization support". Clearly, there would still be some limits even to these, but it's super-linear with the number of people, especially when you consider implicit relationships such as exists between you and an ad-server.

This question is more simple. For social relationships there is a known limit: Danbar Number, so it is (Popluation Size) * 150. There are other studies that suggest 300 as upper limit. That would be (Popluation Size) * 300.

That's for a class of stable, two-way relationships. I was also thinking about things like contracts, debts, the one-to-many relationships like between actors and audience, the relationships between you and google or twitter or ltu, etc.. Still, Dunbar's number provides a starting point. Thanks for linking to it.

This is actually a fun topic; we wrote a paper on it:

https://www.usenix.org/conference/hotos13/session/guo

There is definitely a movement to holistic thinking in the distributed systems community, really there is no other choice.

Cognitive complexity difference between FORTRAN and Algol is best described in classic "Go to considered harmful". I recommend to read it with comments at this link.

Basic argument that for FORTRAN you have to condider every other line of the code, to understand the real effect of the line (or at least every line with goto). For Algol, you need to conder only block and call stack O(ln(A(C))). But you still has to understand every line for every language to understan every program, so there is A(C) multipler. My C programming experience suggest, that one has to understad the memory tree for the subsystem and call tree to write reliable programs. Otherwise there will be abundant memory leaks and other problem.

For OOP and FP, getting the estimations is a bit difficult. But in generic, good OOP and FP code rely on contract knowledge rather than on understading context stack (that is required for resonably big C program). I estimate cost for human of contract knowledge as O(ln(Call Stack)) = O(ln(ln(A(C)))).

Note, it is possible to write OOP style program in C and even assembler, that will have the similar understanding benefits (openssl comes to mind on C front that is almost OOP library, also ODBC actually implements concept of objects and interfaces in C). But is is much harder to maitain, document, and be sure that OOP is actually followed here and nothing saves from dangling pointer or memory leak, and in some sense it would internal DSL rather than plain ASM or C code.

If you look at call stack of modern Java or .NET progam, you will see a huge call stacks data structures, that would be too complex to understand for program written in traditional C style. In Java and .NET, one could rely on contract knowledge, in C in addition to it one need to track larger context knowledge.

One successful outcome for this sort of discussion is clearly identifying points of irreducible disagreement. Looks like we're just about there. A few remarks.

Reading code is not high bandwidth or precise when a human does it.

You're talking about comprehension, not content. Comprehension is difficult; I don't think it's impossible, I think we can do far better than we have so far at mitigating the difficulty, and I think the effort is worth it because otherwise you simply give up on having any control of your technology. You can't control a system effectively if the information needed to do so is actually not there, in one place where you can find it; that means there's a single primary representation and you have access to it. Ultimately, human readability cannot be acheived if you're willing to compromise it for something else.

Nor is reading code very scalable - a couple hundred lines could take a whole afternoon.

Whether it's scalable depends on the language; if you're talking about an unstructured language (say, FORTRAN spaghetti code) then yes, it doesn't scale at all well. How well different programming paradigms scale was the question that (as I recall) let us to this discussion.

Btw, whether a whole afternoon is inapprpriately long depends on the task; if that couple hundred lines of code is the whole of a major system, maybe an afternoon is a perfectly reasonable investment.

It seems analogous to trying to understand a liter of water by reading "H₂O * 3.34E25" and simulate in one's head what that formula will mean when applied physically.

Since we are talking about language, I'd suggest that "H₂O * 3.34E25" may be a less appropriate representation than "a liter of water". Also, we're not talking about water, we're talking about programs, and programs have inherently discontinuous behavior. You can show the programmer a liter of water and they won't realize it might at any moment turn into a sperm whale and a potted petunia.

Reading code is just one approach to comprehending it. We understand a LOT of things without reading them. For example, I have never once read a hammer, or read a liter of water. But I have read about them (i.e. documentation). And I have observed them, and used them.

programs have inherently discontinuous behavior

This is something we can fix. Programming languages can have laws, such as the four laws for the object capability model, immutable values, equational laws, compositional laws, types. Compositional laws, especially, provide the similar sort of continuity and locality properties that you'd expect from a physical world. With types, we don't need to worry about freak Douglas Adams sperm whale accidents unless they also happen to our physical computing systems. My Awelon Bytecode even eliminates jumps and control flow, a major source of discontinuous behavior, in order to support streaming.

You can't control a system effectively if the information needed to do so is actually not there, in one place where you can find it

I'm not saying "the information isn't there". I'm saying "the information isn't optimized for human reading". There is a rather significant difference between those two conditions.

human readability cannot be acheived if you're willing to compromise it for something else

It certainly cannot be maximized if you compromise. But that doesn't mean your code becomes completely unreadable, either.

And the important part: Compromising readability does not necessarily compromise comprehensibility, especially when readability is compromised to support other modes for comprehension (such as laws and continuity properties). If your goal is instead to maximize comprehensibility, then we may well need to compromise readability. I.e. you can't maximize human comprehensibility if you compromise it for human readability.

We understand a LOT of things without reading them. For example, I have never once read a hammer, or read a liter of water. But I have read about them (i.e. documentation). And I have observed them, and used them.

But here the thing has no existence outside its behavior as defined by instructions. There's nothing else like that. I maintain (and I gather you disagree) one can't fully understand code by observing its behavior, and trying to do so is so inefficient and faulty it makes any difficulties of reading code pale by comparison. Our disagreement seems to me to be largely rooted in what we believe to be possible; each of us is pursuing a vision of something that the other doesn't think will work. I'm okay with that.

programs have inherently discontinuous behavior

This is something we can fix.

There's a point on which we disagree fundamentally. I maintain discontinuity is inherent in programming, in fact it's kind of the whole point. Perhaps I can explain a little more...

Programming languages can have laws, such as the four laws for the object capability model, immutable values, equational laws, compositional laws, types. Compositional laws, especially, provide the similar sort of continuity and locality properties that you'd expect from a physical world.

Whereas I see this route leading to one of two things. One, the laws imposed are fundamentally limiting what can be done, in ways that will cause people to routinely dive underneath those laws to the underlying system where the laws don't apply (leaky abstraction). Or, two, the laws imposed are necessarily fundamentally different from the sort you'd expect from a physical world, as I've suggested.

With types, we don't need to worry about freak Douglas Adams sperm whale accidents unless they also happen to our physical computing systems.

I acknowledge that in Douglas Adam's scenario it was accidental. It's not good when that happens to a program accidentally. However, sometimes it might be what's meant to happen.

My Awelon Bytecode even eliminates jumps and control flow, a major source of discontinuous behavior, in order to support streaming.

Just to take an opportunity to say so: I do wish you well in your pursuit.

I'm not saying "the information isn't there". I'm saying "the information isn't optimized for human reading". There is a rather significant difference between those two conditions.

Which is why I didn't stop at saying it has to be there.

It certainly cannot be maximized if you compromise. But that doesn't mean your code becomes completely unreadable, either.

I was aware I'd not worded that perfectly. My point is that whenever you compromise readability for some other concern, in the long run the other concern takes over. It doesn't become completely unreadable, but it asymptotically approaches it. I remember in the first years of the web, we wrote our pages in html. Not too bad, as markup languages go. A little sparse in capabilities. But human readability wasn't the primary concern, and now most web pages are well-nigh unreadable in their ulderying html form. Wiki markup came along, and was successful because its core is really amazingly easy for humans; but it's got extensions that were added around the fringes that have been compromised for other considerations, and now the WMF has decided they should be moving away from humans directly editing the wiki markup — if they succeed, wiki markup will end up unreadable because it's been written by and for machines (which will doom wikis to long-term irrelevance, because wikis succeeded in the first place only because wiki markup is so easy for humans, something the WMF has managed to forget... but I digress).

There's a point on which we disagree fundamentally. I maintain discontinuity is inherent in programming, in fact it's kind of the whole point.

Well, at least it's good to understand where we disagree. :D

this route leading to one of two things. One, the laws imposed are fundamentally limiting what can be done, in ways that will cause people to routinely dive underneath those laws to the underlying system where the laws don't apply (leaky abstraction). Or, two, the laws imposed are necessarily fundamentally different from the sort you'd expect from a physical world

I disagree.

First, laws won't inherently limit what can be done, only how you go about doing them. In programming language terms, this means that a language with laws may be less expressive (in terms of Felleisen expressiveness) than one without those laws. But you can still support Turing equivalent computations and model effects.

Second, computation is mechanical. That is, computation is ultimately performed mechanically by physical systems. Adding two numbers requires their physical representations and the instructions or physical structure to add them coexist in a physical space and time. Information has real physical properties, cf. Landauer principle. Consequently, the very best constraints and laws and metaphors for a language of computation are aligned with those we'd expect from a physical world. Such laws are the best because they do not compromise scalability.

It's only when we pretend that computation is somehow spiritual or magical that we get into trouble.

I maintain (and I gather you disagree) one can't fully understand code by observing its behavior

I actually agree with this. But I would add that one also cannot fully understand code by reading it. Not at the scales that matter: full browsers, applications, operating systems, networks, or even complex functions of a few hundred lines. If humans could 'fully' understand even relatively small amounts of code by reading it, I think it would have taken less than twelve years to notice the bug in Timsort used by Java, Android, and Python.

Since there is no perfect method to fully comprehend code, especially not at larger scales, I believe it's critically important to have effective methods to work with code that we only partially comprehend, including ability to locally reason about the impact of our changes on the larger system. If this requires sacrificing some readability, well, reading code wasn't all that effective anyway.

trying to [understand code just through observing its behavior] is so inefficient and faulty it makes any difficulties of reading code pale by comparison

I'm not sure how 'difficulties of reading code pale by comparison'. But I do believe we need lots of different means for comprehension. Observing, visualizing, animating behavior is one. Documentation another. Types and compositional properties are also useful. Even reading the code is on the list - marginalized, not eliminated.

whenever you compromise readability for some other concern, in the long run the other concern takes over. It doesn't become completely unreadable, but it asymptotically approaches it.

Programmers will find ways to make readable just the subprograms that they believe need to be readable. They can do this even in a language that doesn't make this easy. If it requires an (E)DSL and staging, that's what they'll use. So, we end up with is pockets of highly readable code where people think it's important, and swathes of moderately or weakly readable code that we can get back to if necessary.

wiki markup will end up unreadable because it's been written by and for machines (which will doom wikis to long-term irrelevance, because wikis succeeded in the first place only because wiki markup is so easy for humans

I am, at the moment, developing a wiki where pages will consist entirely of bytecode. It's a more human-friendly bytecode than most, with a Forth-like look and feel to it. And it will be bytecode that generates renderable and editable structures, which will more or less serve the same role as ASTs in a structured editor. But it's still bytecode, unfit for consuming through one's eyes in great quantity.

So I guess I have a different opinion on what is necessary for success. I think comprehensibility and direct manipulation are more important than readability and writability. I think we should be careful not to confuse readability as a means with the ends it is meant to achieve.

It's only when we pretend that computation is somehow spiritual or magical that we get into trouble.

Heh. I'm quite confident getting into trouble doesn't require that. :-)

Even reading the code is on the list - marginalized, not eliminated.

And I, on the other hand, maintain reading the code has to be our first line of defense, and moreover that it can be if we stop distracting ourselves with compromises and really get to grips with how to make our code readable. (One might argue that in fact we can't stop distracting ourselves, since it seems we never have done so yet; to which I'd counter that readability always takes a back seat to other objectives because it's a lot easier to figure out how to design for those other things, so if we got a clue how to design for readability we'd have a prayer of doing so.)

Programmers will find ways to make readable just the subprograms that they believe need to be readable.

I don't think that's true. Programmers will find ways to make just barely readable enough the particular stuff they most desperately need to be readable enough, maybe; but serious readability doesn't arise spontaneously.

If humans could 'fully' understand even relatively small amounts of code by reading it, I think it would have taken less than twelve years to notice the bug in Timsort used by Java, Android, and Python.

I'm leery of your use of "fully". It could easily place an impossible burden on programming that we wouldn't demand of any other subject of intellectual endevour.

One can't validly reason that because something hasn't been done, it can't be done; if one could, the Timsort example would disprove your approach, too. More to the point, though, some things are genuinely difficult, and you can't get away from those things by creating a shield to protect people from them. Somebody was just remarking (iirc, somewhere up there in this sprawling thread) that industrial programming teams are always at the very outer edge of what they can handle; I suggest that isn't, altogether, because of the limitations of our technology, but rather because people are competing with other people and therefore necessarily pushing the limits of whatever technology they have. Give 'em better languages/whatever and they'll still be at the very outer edge of what they can handle, just with the edge set further out.

Seems to me, if I'm right then pursuing your approach is likely to produce some very useful tech, and if you're right then pursing my approach is likely to produce some very useful tech. So in that sense we're pretty well situated.

reading the code has to be our first line of defense

And you'll put it on the front line by eliminating every other line of defense. :)

Reiterating a few points against: (1) we only have the time and attention to read code for a small subset of the system, (2) reading code has not proven effective at avoiding security holes, (3) we can't read the adversary's code anyway (open systems are full of code closed to us), (4) we cannot seem to maximize readability without compromising a bunch of other useful properties.

readability always takes a back seat to other objectives

Thus 'readability as first line of defense' is untested. Hardly offers confidence in your conjecture. :D

I'm leery of your use of "fully". It could easily place an impossible burden on programming

I wasn't implying a burden, just noting the infeasibility of fully comprehending code and the consequent need for effective means to work with code and systems we don't fully comprehend.

One can't validly reason that because something hasn't been done, it can't be done

We do have a long history of coding style guidelines and code reviews and various best practices for reading code and writing readable code. So, I think there is more than a little evidence on the effectiveness of these efforts, should we bother to dig it up.

How would you get your programmers to write the readable code when abundant such historical efforts have failed to take or failed to stick? Seems more difficult than herding cats to me, exacerbated by both deadlines and the curse of knowledge (i.e. I cannot easily judge my own lucidity because I have all the context and facts I need to grok my own writings). Do you have some way to make lucidity the path of least resistance?

How effective is reading code against different classes of bugs? You presented one bug above that is locally and syntactically visible, which might have been better highlighted with better formatting. Of course a dead code warning would have also worked. But it isn't clear that this generalizes to a lot of other errors.

How quickly does quality of code reading deteriorate with a larger number of lines of code? I've read the typical experience is: give me a ten line program and I'll find ten errors; give me a hundred lines and, eh, it looks alright. But we can probably find some real numbers if we dig.

some things are genuinely difficult, and you can't get away from those things by creating a shield to protect people from them

I don't recall implying we should. Essential complexity isn't something we can hide. Language design can only avoid or shield people from accidental complexity.

And you'll put it on the front line by eliminating every other line of defense.

I've no interest in eliminating every other line of defense. I'd like to rearrange some of them to avoid undermining the first one, but that's quite different. There will always be reasons people don't use the others, so the first one had better be good.

Thus 'readability as first line of defense' is untested. Hardly offers confidence in your conjecture. :D

I had to poke around for the quote. It's from G. K. Chesterton, What's Wrong With The World, Part One: "The Christian ideal has not been tried and found wanting. It has been found difficult and left untried."

I'm leery of your use of "fully". It could easily place an impossible burden on programming

I wasn't implying a burden, just noting the infeasibility of fully comprehending code and the consequent need for effective means to work with code and systems we don't fully comprehend.

I meant that you might be asking programming to live up to a standard that we don't ask of any other intellectual activity. In terms of your explanation here, I suggest that, perhaps (I'm still leery of what is meant), we never fully comprehend anything whatsoever.

We do have a long history of coding style guidelines and code reviews and various best practices for reading code and writing readable code. So, I think there is more than a little evidence on the effectiveness of these efforts, should we bother to dig it up.

We've learned quite a few ways not to make a lightbulb. Although I acknowledge that a lot of folks haven't learned those lessons.

Language design can only avoid or shield people from accidental complexity.

Some kinds of shielding may cripple programmers' ability to cope with essential complexity.

Some kinds of shielding may cripple programmers' ability to cope with essential complexity.

We can design to avoid that, too. It isn't even difficult. If something doesn't fit anywhere else, stick it into your effects model, e.g. message passing or the IO monad or algebraic effects. Done. We might contemplate: how can we avoid doing too much of this? But at least you haven't crippled anyone's ability to deal with essential complexity, and you preserve whatever reasoning your effects model supports.

"The [readable code] ideal has not been tried and found wanting. It has been found difficult and left untried."

For what it's worth, I hope you do find a way for programmers to consistently and easily write readable code. Even if it proves ineffective in guarding against bugs and security holes and lots of other concerns, it would still be a nice property to have.

But, realistically, I expect that writing lucid code is one of those "genuinely difficult problems", not something the language designer can solve. Maybe we can help by providing good support for EDSLs. But unless we can get readable code onto a 'path of least resistance', lucidity will continue to be "found difficult and left untried".

For what it's worth, I hope you do find a way for programmers to consistently and easily write readable code. Even if it proves ineffective in guarding against bugs and security holes and lots of other concerns, it would still be a nice property to have.

I want to play with elevating metaprogramming, so that every domain can have a suitable custom notation.

John's interest may be similar since he invented an abstract metaprogramming system. And like me, he is leary of typing... Lisp like languages seem appropriate for personal projects anyway, and I'm not programming in a corporate environment.

It bothers me that typing is a hard to work with, inexpressive language and I keep thinking it could easily be subsumed in a more general and expressive proof system.

It bothers me that typing is a hard to work with, inexpressive language and I keep thinking it could easily be subsumed in a more general and expressive proof system.

That's my take on the role of the type system. Embed all values in a powerful logic and let the type system serve as a lightweight mechanism for automatically inferring some of the easier proofs.

I should have said "logic system" not "proof system"

I just want the expressiveness and I'm not interested in proofs. I realize that lots of areas of engineering would benefit from proofs, but I'm not interested in that.

Algebraic types, for instance, add some expressiveness to a language, but that expressiveness can be easily simulated with something like prolog matching and testing, and the resulting language is much more expressive.

I am doing this, I have a logic interpreter which has the types of the main language as its terms. It's a bit different from Prolog as it always uses sound unification, only has a sound not-equals constraint, and searches using iterative-deepening.

It has some interesting properties, in that predicates on types can be expressed directly in logic, removing the need for an explicit type-class syntax.

It is designed so that type-inference is decidable, so unless you explicitly write a non-terminating type-level logic program, it will always terminate.

An approach I've been dabbling with (as I've occasionally mentioned) is to add to a Kernel-like language a type of first-class propositions, with a subtype of theorems. Constructors for the theorem type are, in effect, rules of deduction; the act of constructing a theorem is proof. The idea being that, in the spirit of Lisp, deciding what to prove and how to prove it should be in the hands of the programmer rather than the language designer. Which leads to at least a couple of design problems — how to integrate programmer-designed deduction seamlessly into the programming process, and what rules of deduction to use; the latter of which has led me to ongoing explorations of Gödel's Theorem.

It strikes me that logic features prominently in all these approaches. I suspect in the long run what emerges will defy attempts to say whether dmbarbour or I was "right" because anyone taking either side will have grounds to claim it.

I should qualify that. Others might claim victory for either side. dmbarbour and I, if still around to see it, might well both think we lost. :-P

You're evidently supposing that in the long run, people are divided into professional programmers who maintain code, and everyone else who doesn't. One might ask, is that supposition necessary; is it likely; and if it tuned out not to be so, would that make any significant difference to the formula?

It's been clear for many decades now, imho anyway, that just as our society has long elevated those who can read and write to a power class, compared to those who can't, we've been clearly headed for a world in which those who can program are a power class compared to those who can't. It therefore deeply worries me when someone talks about regulating programming so only those with a license are allowed to do it. If programming were something a large fraction of the population participated in, rather than something done by a dedicated class — say, something done via Wikipedia's sister project Wikiware — then the maintainable codebase size depends not on how big a population of programmers society can support, but how much code maintenance an average member of the population does. Perhaps the average citizen, even if empowered to help maintain software, will do so much less than a professional programmer that the code maintenance burden is completely dominated by the number of professionals; but, speaking of unknown parameters, it seems that the whole shape of civilization's code maintenance support system is still in question. Perhaps programming will be something eveyrone does, and will comparatively fade into the background, as literacy does... for those who have it. Which in turn suggests that a society's educational system may play an essential role in determining how much code it can support.

http://lambda-the-ultimate.org/node/4424

(link)
Oh! Should have remembered that thread; cool. :-D

the number of LoC that civilisation can support is determined by a very simple equation: the number of LoC a programmer can support * the number of programmers a civilisation can support.

Some observations:

1. You assume without basis that the labor cost of maintaining software systems grows linearly with LoC.

2. You assume that a society's aggregate software systems are best understood by partition into sub-units, each of which is apparently to be maintained independently of the others.

Those two overlook bugs that only appear when separately developed and maintained systems are composed in ad hoc, unplanned ways.

3. If I follow you correctly I guess your conclusion of no important limit on the total mass of software is premised on the unbounded expansion of population, an assumption with no imminent relevance whatsoever.

In general and not just to you: I think any real answers in this area have to acknowledge the fragility and increasingly problematic large scale failures of existing software systems. One of my favorite examples is the payment system: Software is all but eliminating cash in day to day life and making it harder to bring cash back into common use ... yet at the retail level our payment systems repeatedly demonstrate massive and unaddressed vulnerabilities.

I have not assumed that the cost grows linearly, which implies that I have been somewhat unclear in what I have stated. I assume that the LoC maintained by a single human being is bounded by a constant. I went with LoC as that was the terminology in your question, although personally I think it is the wrong way to measure it. Conway has already been brought up by several people, I would work with the assumption that each of the factors I mentioned (understanding / searching / isolating / patching) grows quadratically in effort when measured in something that correlates roughly with LoC. i.e. the functional units of behaviour in a code-base may scale linearly with its size, but the behaviour of those units would scale in a quadratic manner.

I'm unsure what you refer to as an unbounded expansion on population - I assume we are climbing a sigmoid that will have a very hard bound on resource exploitation.

As your interpretation seems to differ from my intention I will try to be somewhat clearer: I would assume there is a hard bound on population, and a hard bound on the proportion of the useful productive capacity that population can devote into programming. This would imply a hard bound on the amount of code that can be maintained, although it cannot be expressed in LoC as the measure itself does not correlate very tightly with "the size of code" and only with "one particular size of one particular representation of code".

On a slight tangent: security is not always about ability, or resources. Sometimes it is actually cheaper and more efficient to not care. I think the product recall discussion from Fight Club captures the situation more succinctly than I could.

If as you say the labor cost of maintaining software grows quadratically with the amount of code then I don't think you mean "LoC * n_programmers" but instead "K * sqrt(n_programmers)". That is to say, the amount of code a society can support grows as the 1/2 power of the number of people taking care of software.

Another way to say this is that the more code there is ("K * sqrt(n_programmers)").... the less code can be supported per programmer ("(K * sqrt(n_programmers)) / n_programmers").

(I'm not endorsing the quadratic cost model. Just drawing out its implications. I do guess quadratic is closer to realistic than the linear model for all widely deployed software systems that are networked.)

I would argue that civilization-scale LoC/person is plausibly linear, because civilization does not construct its software as a single unitary system.

The vast majority of all code is application code, not libraries, infrastructure, or middleware layers. Direct horizontal dependencies between this class of system (as opposed to libraries, infrastructure, and middleware) is not unknown, but is fairly rare, and certainly sparse. This makes coordination costs for this class of code a constant factor.

I suspect that the remaining code has similar properties, recursively. Dense and circular dependencies between systems are rare and sparse. Extremely large, unitary systems are difficult and expensive to build, so we don't make many.

Hey, this state of affairs doesn't take any particular engineering competence to achieve. It's just the result of selection, as impractical efforts fail.

Wouldn't the difficulty of maintaining code increase with the size of the environment in which the code must exist? How quickly it would increase being a separate question; logarithmically seems plausible, on the face of it.

True, but I don't think it's useful to define the environment of a project to be "all the code that has ever been written". The relevant environment for bounding coordination costs is "the platform and libraries that the project was written on".

If I write a GUI app for MS Windows, I will incur coordination costs from dealing with the Microsoft environment it's written on, plus those of any libraries it uses, plus those of any network services it uses, and so on. However, this environment does not include that of, say, the IBM 370, the Commodore Amiga, or DEC VMS.

I think I understand Thomas's point to be, in part, that in a networked world, your networked services could in fact depend on an IBM mainframe environment without your knowledge. If so, my response would be: this kind of dependency is administratively opaque; even if you happen to have ready expert knowledge of IBM mainframes, you are unlikely to be able to use it to fix a glitch in someone else's services.

Whatever your opinion of the causes and consequences of this kind of information hiding, the result is abstraction of a sort...

The relevant environment for bounding coordination costs is "the platform and libraries that the project was written on".

Well, hmm.

In the U.S. we have a kind of constitutional and societal crisis over the issue of mass surveillance. Many dystopian scenarios are imminent regarding this crisis deriving from a loss of legitimacy of the government and as well the wide range of abuses to which such mass surveillance is susceptible.

This is a little hand-wavey but please consider that ultimately the problems of all this electronic surveillance are not questions of software security, or reliability, or bugs that emerge through networked integration. Everything is working properly, to spec.

Nevertheless, the surveillance problem (as just one example) threatens to disrupt society as a whole, one way or another. I would say it is catastrophic.

At the same time, society as a whole has no imminent escape route from the mass surveillance problem. We have built digitized communications and electronically mediated commerce and so forth so far into society that to try to abandon it suddenly would also be catastrophic. We have made a software system mess that existentially threatens us and at the same time we depend on that mess for our survival.

In other words: amassing deployed software has made us socially dependent on surveillance prone systems. And amassing deployed software has given us catastrophic levels of surveillance. Is there a limit to this amassing?

Have we in that way approached the society's limit for amassing software? Has accumulating software and haphazardly integrating it into social relations as we have done ... has that already sealed in the inevitable collapse of our society's capacity to keep accumulating more and more software?

Software as a medium for social interactions still has plenty of room for new visions and architectures to replace old ones. In part, this is even inevitable: most software will be replaced due to changes in hardware, adapting to future challenges of VR, AR, smart homes or internet of things. Augmented reality, especially, will be interesting insofar as it is possible to augment social interactions even in face to face discussions (e.g. to detect lies or boredom, or help track a conversation).

Some approaches to software have potential to be vastly more scalable, tailorable, personalized, and sharable than what we have today. A relevant point is: if we can make software very easy to edit and share and reconfigure, then the number of unique programs will tend to scale linearly with the number of humans. (Oval was an interesting experiment along these lines.)

Naturally, not every use of software as a social medium will be 'good' for us, even if popular. Some suffer from selection bias, finding all and only the 'truths' we search for. Some may be addictive to fractions of the population. Some might be used for bullying, or give too much voice to trolls, or be subject to a tyranny of the majority. Others might have a weakness of being prone to surveillance or making us more vulnerable in other ways.

Just as naturally, some political groups may be served by these weaknesses and act to entrench them. And some groups will feel threatened, and act to control these media. It is feasible that we will get 'stuck' in a particular modes of software for hundreds of years at a time. But such political constraints aren't a hard limit for human civilization.

I don't think it's useful to define the environment of a project to be "all the code that has ever been written".

A more relevant definition would be "all the code that's being maintained". Since the question wasn't how much code can have been written by a civilization, but how much can it maintain. If two pieces of software are both being maintained at the same time, the further "away" from each other they're located in the overall structure of cyberspace (gee, haven't had occasion to use that term in years), the less intensively they'll interact, but on a statistical basis they'll still interact with each other.

Humans make plenty of other throw-away or use-once things (consumables, munitions, packaging, live music, etc.). Software has, perhaps counter-intuitively, been more difficult, fragile, and finicky than other arts and crafts. If these issues can be addressed, however, I think there are plenty of areas where software could be usefully developed for short term use. Live coding of music is one example. A GM programming and tuning events for a role-playing game might be another.

So it isn't just an issue of how much software we can maintain. An equally interesting aspect of 'support' involves the bulk rates of software creation and consumption.

A nuance I glossed over in the preceding, for simplicity, is software that has ceased to be maintained. It does contribute to the volume that maintained software may interact with, but in a diminishing way over time; so how much it contributes to the volume depends on the rate at which it's abandoned rather than the total amount of it that's been written. Your putative use-once software would be part of the no-longer-maintained element.

It is perhaps unfortunate that I chose mostly-obsolete systems as non-dependencies; let's say we're talking about code which is currently in use and being maintained; call this "active code". Suppose we want to figure the influence on the cost of building and maintaining a project, of all active code which is unrelated to it (as described above).

Now, I don't know actual numbers (or what kind of methodology might yield them), but surely the total amount of active code has increased dramatically over the past few decades. If unrelated active code generates significant coordination overhead, it should be contributing substantially more to the cost of buildiing and maintaining a project today than it did 30 years ago.

How do these coordination costs manifest? Concretely, what are they? I'm not saying I don't believe in them, but I'd like them identified.

The only concrete manifestation of coordination costs with unrelated active code that I can name off the top of my head is researching relevant and available libraries/platforms/etc. For example, you might look around for the current set of linear algebra libraries, then see which is most appropriate for your application. However, this generally takes a fairly small fraction of the design phase, never mind the total including development, testing, and maintenance.

And, personally, when doing this kind of search, I have not increased the amount of effort I need to spend on it. Then, as now, I might check out 3 to 5 of the most well-known or well-recommended options. The expense of this kind of coordination seems limited by my willingness to take the trouble....

Coordination costs are frequently communication costs. Whenever we want to combine services provided by multiple applications, we must either integrate some APIs (which frequently come with varying authorization models, concurrency concepts, and other cross-cutting concerns) or much worse when adequate APIs are lacking (e.g. screen scraping, parsing web pages meant for human, automating keyboard events). Integration of APIs that provide events/callbacks is relatively difficult because it requires careful attention to state (cf. why not events).

Extension is also a common source of coordination costs. When you find a service that does almost what you need, but you need some small tweak to its behavior or API that cannot be implemented as a wrapper, it is convenient if the service provides some means for you to provide that tweak. Alternatively, you can coordinate with the humans developing the other service, e.g. via feature requests and potentially some money changing hands.

Usually, the only content that cannot be wrapped is when you're working with stateful services. If more people used an unhosted style model, where the client provides external state resources for most of their own service, or at least RESTful access to state, then wrappers would be more widely feasible (though the difficulties of coordinating heterogeneous stateful data models would remain). Also, ability to wrap or capture other side-effects can be useful for extension, e.g. via favoring capabilities or free monads rather than ambient authority.

Related to extension, package versioning, distribution, and configurations management can become another source of coordination complexity. Dependency hell is a thing, and with a large number of dependencies each with multiple versions we get combinatorial difficulties. I'm interested in approaches that might mitigate the issue, rejecting the 'package' based libraries in favor of, for example, naming bytecode by secure hash (for separate compilation and dynamic linking) or use of a dictionary-based model (eliminating external dependencies except for network services).

I think exposure to these difficulties depends a lot on what kinds of applications or services you write.

In my previous job, developing multi-platform robotic controllers where every platform, sensor, payload, etc. has its own APIs and special cases (and physical concerns - balance, vibration, etc.), coordination was most of the challenge.

My point was that we only incur these costs for systems we actually depend on.

Interaction can be initiated from either end. Just because a given software element only seeks to interact with things it depends on, does not mean it only interacts with those things. Overt malware is one obvious example of software that interacts with things that don't seek to interact with it; and with increasing software sophistication, one would think, it'd get harder and harder to draw a line in this respect between malware and commercial software.

As a developer of software, you aren't just a client of services. You're also the provider of a service. You coordinate not just with those to whom you are the client, but also with your own clients. The latter coordination involves maintenance of your APIs (or UIs, for that matter) to meet client needs.

Beyond that, there is also much indirect dependency. Deadlock is possible when dependencies are shared badly. With feedback loops, a subsystem may both influence and observe whole system behavior. The tongue-in-cheek definition of "distributed system" is when a failure in a computer you've never even heard about causes your own code to stop working. In these contexts, we may need to understand a lot of the system to understand a buggy behavior or achieve a desirable behavior.

We can do a lot to help isolate and stabilize our interfaces, e.g. develop lots of reusable functions or other software components with clearly documented types or data models. But components dealing with business logic and changing client requirements or dependencies will either be modified or replaced.

Coordination costs manifest as interference, either by making you fail when other things fail, or by wasting your time on analyzing whether you are exposed to failure under blurrily defined scenarios. Something always fails once you reach a certain threshold of complexity. What was it? Can you stop it from happening again? Hmm. What if you can't even determine what happened?

Just trying to pin down what you depend on is coordination cost. If it exists, and might cause part of your suite to fail, maybe you depend on it. The hardest problems to debug are things that don't happen, because there's no evidence, just nothing. You end up tracing signals (in an abstract sense), to see where the chain of expected communication derailed. Ah, it was the 50th step that ate the data flow and went silent. This takes forever when it never occurred to earlier devs that someone would need to trace those signals.

Lately I'm writing unit tests for an IPsec library that wasn't designed to be tested, or to be driven piecemeal outside a running system, or even to reveal state in data structures or messages. So nearly all my time is spent on coordination cost in the form of software archeology on decades-old code, written by devs so different from me I can't imagine how they think, who spoke another language so comments are rare. Unit tests are needed to establish whether failures might be due to some library actions; it's hard to tell. Nobody can force original devs to write tests; it you depend on their code, you have to do it.

As dmbarbour noted, software often needs extending. I added traffic selector narrowing to this library, causing it to dynamically generate new config info after negotiation. But the original code, and client code using it, assumes config info is static, so if part of it is there, all of it must be there already. Instead, it propagates as a signal, where not all the signal arrives at the same time in processes that fire event handlers after part of the signal shows up, but also depending on state in signals yet to arrive. As assumptions in the original code aren't stated, finding out when they affect you can be hard. Distributed systems tend to foster exotic order dependent behavior; truth depends on time, connectivity, and change resolution.

While we might incur costs only when we depend on something, because the line delineating what we depend on is blurry, we incur some of the cost trying to establish the line. Costs would go down if we could secure scope of possible influence a little better. Meta-programming might help there (meaning programs that write programs).

Monads do not implement concurrency.

For example, semantics of the similar Do construct in ActorScript is not captured by the above monadic transformation.