What is "program"? essentially, conceptually.

What is the ontology that you accept for answering the question? It can go from "it is a sequence of instructions" to "it is the human-readable specification of an application that can be executed on a chip" to "it's a valid string according to the grammar of a specific programming language". Is a "program" the same as an "app" or the same as a "source code"? Without context, it is difficult to even start answering the question.

from a system-centric pov, a program is just a message to a system that modifies the system's behavior. incidentally, data is the same.

> Without context, it is difficult to even start answering the question. fair. I have a strong lasting feeling that most of daily programming routines I do as developer – are incidental complexity™. So I am trying to figure out what is the essential complexity™ of programming. Assuming mapping from program to how-to-run-it-on-hardware is factored out – what is left? Can that execution mapping really be factored out? Is there a language for "what is left"? is it eg. Prolog? TLA+? What should that language help with? My take on it so far is "program is mapping from state to state". Which makes it a function? Is "real" program different from a function only because it is also "mapped onto hardware"? Or is there something else missing? If program is a function, then programming language is a tool for "convenient" description of state-to-state mapping?

no the state-to-state thing is not important IMHO. IO i.e. stdin/stdout, thats the important bit. Moving state around a RAM chip is not useful, its only when the computer is between keyboard and monitor that it becomes useful and interesting. IO, the side-effects, is the point, to me anyway. So I do think the hardware mapping is the important bit. When considering the internals, I think the state-to-state bit is useful when domain mapping, converting between domain representations and abstraction levels. Then thats when the computer becomes a tool for the mind (coz it unburdens you from doing domain mappings in your head)

I’ll just drop in some commentary I made on another forum: > It’s sort of “folk wisdom” in some of my social circles that it is actually very hard to define programming, or to draw clean lines between programming and not-programming. > > For example, “programming = writing textual code” breaks down because of visual programming languages, structured editors, etc. The broader “programming = manipulating symbolic representations roughly equivalent to textual code” breaks down because of Drawing Dynamic Visualizations / Wrangler / programming-by-demonstration. > > So sometimes I go for ends rather than means, like “programming = authoring dynamic artifacts”. But lol what are dynamic artifacts? Oh, they’re “artifacts that respond differently to changing inputs / interactions / circumstances”, in contrast to “static artifacts”. But >

n = 0
> for i in range(10):
>   i += n
> print(n)

> only ever produces one output value... Is it a dynamic artifact? Is a HTML website that responds to changing screen size with CSS rules a dynamic artifact? Which of these are programming?

state-to-state is one model of behavior and in general a program is a representation of some subset of system behavior. a typical 'program' is missing a lot of aspects. notably any notion of persistence is absent. data lives on longer than programs. newer programs have to contend with data left over by old programs (or earlier versions). this is why i think the typical notion of a program as this transient entity you run, which computes something and then is done, does not get close to covering the entire span of system behavior. there is a fair bit of incidental vs accidental complexity discussion in the past in this slack if you search the history. there was also the related tarpit episode https://futureofcoding.org/episodes/063.html

@Joshua Horowitz movies support moving pictures but you can freeze an image or even go to black. Analogously, it seems to me that the dynamism is a possibility the medium provides, whether or not any particular work uses it. I gather people were making stage plays in the new medium for decades while gradually understanding dawned of all the new possibilities that it opened up.

@Kartik Agaram I don’t think that quite gets at what’s interesting to me about the Python test case. I don’t see that script as, like, a degenerate program, in the same way that a single-frozen-frame movie would be a degenerate movie. I think that script DOES take advantage of the dynamism the medium provides. But its output is entirely static! This means you shouldn’t judge something to be a “program” or a “dynamic artifact” solely on the basis of its externally visible behavior treated as a black box. Sometimes you care about how the externally visible behavior responds to edits in the artifact itself. But I don’t know how to pin this down.

@Misha A I think you've basically nailed it in what you said there. This is exactly how I started my journey: looking for "the essence of programming". I described it as seeking a "Target and Domain Independent" programming language: one that was unconstrained by having to execute it on specific hardware Target, and untarnished by the needs of any given Domain. My conclusion was exactly what you're saying: that programs move one state to the next. That's basically it.

re: state vs. IO it seems to me that IO is state too. The question is: at what point it becomes more useful/convenient to start distinguishing between the two. What would be the difference? Should the programming language treat them as the same, but let user introduce the difference when necessary. Or should the difference be baked in already? What is the difference, again? What other differences between seemingly same things are better ("better" when, for whom?) to be baked into the language? It seems that the programming languages game is all about designing syntax(tool) convenience proportionally to task frequency. Seeing a lot of same things as different – breeds proliferation of tools. So maybe seeing similar things as the same would reduce tools ... "fragmentation"? (e.g. java's classes with their personal new-every-time-DSLs vs clojure's "everything is a map, but these several functions is all you ever have to learn")

Related to the 'incidental complexity' question - sometimes I get frustrated with all the code it seems to take to do even simple tasks. I question why there are so many lines of code? Why can't the computer just do what I intend? I've thought about categorizing the lines of code in some of my programs to see what all those lines are doing.

I've heard this line of reasoning before, and it's worth questioning the premise. For some arbitrary computing task, how do we know how simple it is? I don't think we can, short of building it from scratch for ourselves. And so we can't really make any assumptions about the level of essential/incidental complexity of a task without a lot of careful effort and analysis. It's tedious, error-prone, intricately-detailed work. It's definitely a common reaction, and I've been guilty of it myself. My best guess these days is that it's a cognitive fallacy related to Moravec's Paradox. People just have really poor intuitions when it comes to computation. Simple things a child can learn without us grown-ups exerting any effort require tremendous quantities of effort for a computer to "learn". And the human reaction is repeated disbelief. That can't be right!

Here's how I see it: everything is complicated... The idea of creating general purpose languages is a loser... https://open.substack.com/pub/programmingsimplicity/p/programming-is-too-complicated?r=1egdky&utm_campaign=post&utm_medium=web&showWelcomeOnShare=true

For some reason I get "then it does not matter" from "everything is complicated" comments. If everything is complicated, why not deal with essential complexity instead of incidental one? Feels like comparable amount of work, but radically different outcomes. Sometimes treating different things the same way makes things easier or even simpler. Sometimes treating similar things differently does. but it seems to me, scanning this space of variations is more tractable from the root tree-side, where combinatorics haven't really kick in yet.

The Thirty Million Line Problem▾

I watched this several years ago and deeply disagree with the conclusion. IIRC, Moratori blames USB Plug'N'Play on the exponential rise in complexity in software development. He bases his conclusion on a graph that shows the correlation between complexity and the invention of USB Plug'N'Play. Basic science says that correlation does not imply causation. The fact that the hockey stick curve of complexity jumps upwards at the same time as USB Plug'N'Play was invented does not necessarily mean that USB Plug'N'Play caused the rise in complexity. In fact, a different explanation for this particular correlation might be as a manifestation of incidental complexity caused by something much deeper and invented much earlier (hint: over-use of the function-based paradigm). [Note that this, also, ties in with bicycles-for-the-mind thread. Programmers have forgotten how the hardware works and have veered off into believing that there is only one way to program hardware - i.e. with lines of code written in programming languages buttressed by operating systems.]

I've gone back and forth on whether the incidental vs essential complexity dichotomy is a useful perspective. I now think it is useful but has to be situated in a specific context. Say you wanted to build a game of pong that runs over a network. You decide to build it multiple times using various stacks and various programming languages. if you build it on posix/c, you will need to first build a network messaging protocol with message formats that you parse. If you pick a higher level stack like python, you may be able to easily reuse http with json or similar. So some pieces of the puzzle only need to be built in some stacks, but not all. To think about essential complexity, consider the pieces you must build in all stacks. On first thought, this includes the actual logic of the gameplay - for instance, you'd need a representation of a ball and bats and players and scores. This looks like essential complexity. However this is not clear cut either. What about drawing rectangles or circles? If you have a graphics library that can do these then you dont need to build it, otherwise you do. The boundary is quite fuzzy here. It's not just about libraries though. Consider the knowledge we have accumulated and internalized by being part of society. Are math skill necessary? For example, knowledge of angles and such (even if you have a library to do arithmetic and trigonometry, you will still need a mental model to apply that library). What if the specific problem domain you are working on (say it's not pong) would benefit from a new kind of math/model? You could build it and even implement a library but to use it others will have to first learn that math/model. Does learning this new model now count as incidental complexity because it was not already familiar? What even can we consider the familiar, ubiquitous baseline? I say situated in a context because the narrower the scope of the kinds of programming you are doing, the easier it becomes to distinguish between essential and incidental and the easier it becomes to establish the 'baseline' of what we expect the programmers know and understand.

@Misha A

If everything is complicated, why not deal with essential complexity instead of incidental one?

You definitely should if you can. Particularly if it seems obvious enough to have you asking "why not?" The problem in my experience is that we don't yet know how to reliably separate those two categories. And that brings the ontology into question.

For some reason I get "then it does not matter" from "everything is complicated" comments.

Yeah, that's not my intent. I was responding to, "why are there so many lines of code?" Maybe it's because we haven't yet done the work to reduce them. And maybe we haven't because it's more effort to do so. It's hard not easy. Basically I'm saying: reduce your ambitions. "The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility.." -- Dijkstra

What is "program"? @ reduce your ambitions. :D