Computer Science, Off Course! Episode 1 - Programming as Theory Building

First real episode of CSoC dropped, you can also just not read all of this and start listening right away!

Peter Naur, most programmers will know him, if they do, from the Backus-Naur form, but this episode is about is his 1985 paper Programming a theory building.

Fun fact, Naur did not like to be associated with the formalism anymore later in his career and preferred for it to be called Backus normal form, because he started to reject the importance of formalism for programming. But let's not get ahead of ourselves, and talk about the paper!

The idea of the paper is that through programming, we engage in theory building. By this, he means:

theory is understood as the knowledge a person must have in order not only to do certain things intelligently but also to explain them, to answer queries about them, to argue about them, and so forth. A person who has a theory is prepared to enter into such activities; while building the theory the person is trying to obtain this.

Through programming, he says, you are not only building a solution, you can also then explain it. This is, I think, not how we usually see programming.

Is "programming as theory building" just programming?

One can wonder (as Hanna did wonder!) whether this form of programming is different from how we regularly see it.

In other words, should "programming as theory building" be a different thing? Maybe it would be nice to have a different term, but I do think that whenever you are programming, even making just a simple small thing, you are always building some theory.

What I love about the paper it that it really build upon knowledge from other fields, most notably on the work of Gilbert Ryle:

Ryle [11] develops his notion of theory as part of his analysis of the nature of intellectual activity, particularly the manner in which intellectual activity differs from, and goes beyond, activity that is merely intelligent. In intelligent behaviour the person displays, not any particular knowledge of facts, but the ability to do certain things, such as to make and appreciate jokes, to talk grammatically, or to fish.

Love this broadness of things that you can do intelligently! It made me think a recent piece I wrote in Volkskrant on how AI frames all tasks in a cognitive sense.

He (Naur) continues:

More particularly, the intelligent performance is characterized in part by the person's doing them well, according to certain criteria, but further displays the person's ability to apply the criteria so as to detect and correct lapses, to learn from the examples of others, and so forth.

What does this mean for programming?

One implication is for IDE design. Current IDEs are optimized for writing code, and they might now also have a few features for reading code, navigation support, but they don't have room to store the theories behind the code.

Greg Wilson has often asked why we can't draw diagrams on top of code, and I think this view of programming is one of the answers. We see code as a solution to a problem, not as a source of learning. We see documentation as unnecessary, because "talk is cheap, show me the code", but certain forms of knowledge can never be in the code. Knowledge like alternatives considered and rejected, paths explored and then backtracked, features that would be hard to add or trivial and why. And since the IDE if just for editing code, these ideas end up living only in the minds of a few programmers, as I think is recognisable for people that, like me, have been creator of a piece of software that then other people also needed to work on. So man decisions made in Hedy live only in my brain, it is hard to communicate them all.

And this I think come to the core of what Naur tries to say, he says in this on the first page of the paper:

[I]t is important to have an appropriate understanding of what programming is. If our understanding is inappropriate we will misunderstand the difficulties that arise in the activity and our attempts to overcome them will give rise to conflicts and frustrations.

One of these frustrations is the one above, where because we have no tools, methods and techniques for storing the theories, as we have no understanding of programming as theory building, they get lost and must be (expensively) reconstructed. The other frustration of course, is...

AI

This paper is so timely in times of LLMs because it gives us a definition for programming that an AI can never do, by definition. A large language model can never form a theory about what it is doing, that simply is not a goal of a language model. An LLM can not (consistently and correctly) answer questions about the code. An LLM has not considered, tried and rejected alternative implementations and stored them to memory. While we could ask it to consider and weight alternatives, clearly in 6 months it will not 'remember' what it 'considered'.

The worlds we build

One thing that also stood out while reading the paper is that Naur is very much talking about building software for the real world:

[P]rogramming denote[s] the whole activity of design and implementation of programmed solutions. What I am concerned with is the activity of matching some significant part and aspect of an activity in the real world to the formal symbol manipulation that can be done by a program running on a computer.

Here I wrote in the margin "But what do we do with worlds that do not exist?" One can argue that "a tweet" (or a skeet...) is not a thing that we are not modelling from the real world, but a thing that is created in the digital only. We could wonder how the theory of Naur fits in this case. What theories are we building by creating Twitter, or TikTok? Surely theories but maybe less about the real physical world.

Integrating Naur into the curriculum

One of the explicit goals of this blog series and podcast is to enrich Computer Science education with these types of insights. In this case I think that there are firstly implications for requirements engineering courses. Naur writes:

Also the very use of the program itself will inspire ideas for further useful services that the program ought to provide. Hence the need for ways to handle modifications.

This would be such a fun exercise, to give students a program and to have them explore, from its use, other features. This would be a fresh addition on the assumption that a customer knows what they want precisely in MoSCoW-style.

In a Software Engineering course (or even in an introductory programming course) we could ask students to write a little note after each hour of programming. What did you learn? What did you try and reject and why? What a rich source of learning that would be!

Closing it of with a banger:

A main claim of the Theory Building View of programming is that an essential part of any program, the theory of it, is something that could not conceivably be expressed, but is inextricably bound to human beings.

Homework

1. Read the paper
2. Programming something, and afterwards take a sheet of paper and write down all decisions you made on the way

See you next week, when we will talk about Computers as Theatre!

Homework

Dear Felienne,

It has been some time since we recorded the Peter Naur episode, but I finally did the homework. Or at least, what I remembered about the homework. Well, actually, I changed the homework a little to better fit my life and (lack of programming) skills. In any case, here are my notes. Please take my notes with a grain of salt. As you know, I am not entirely sure who I am — but I am definitely not an experienced programmer, I am also not an educational scientist, and I have not studied computer science even though I ended up in the CS department. And, of course, I have not looked into scientific articles to see how well my thoughts hold up against those of experts. Also, I overdid it a bit. Future homeworks will be shorter, I promise!!!

Homework reading

So as a first part of the homework, I read the "Programming as Theory Building" paper, which you discussed in our last podcast episode. Not surprisingly, I liked it a lot. I was even occasionally clapping enthusiastically while reading it. For instance, I loved Naur’s understanding of a theory as

’knowledge a person must have in order not only to do certain things intelligently but also to explain them, to answer queries about them, to argue about them, and so forth’.

Also, I couldn’t agree more with his conclusion that

‘the notion of the programmer as an easily replaceable component in the program production activity has to be abandoned’.

I believe it is more relevant than ever, with people constantly arguing that programmers can be replaced by AI.

But of course, I could not switch off the critical voices in my brain that start complaining whenever I read anything. So, let me share some of the 'loudest complaints' or criticisms I have.

The main issue I struggle with is how this theory that programmers develop according to Naur is presented as something that can only exist in programmers’ brains. It can only be obtained by programming, and it then is part of (the team of) programmers --- it is not something that can be shared with or transferred to other programmers/teams. As Naur puts it, ’the theory, is not, and cannot be, expressed’, it is something that ’is inextricably bound to human beings’. And while I agree that much knowledge and understanding will only be able to exist in programmers’ brains, I also believe that with some effort, (parts of) the theories that programmers build can be expressed, communicated, shared, transferred, and documented.

In fact, I think Naur himself provides an argument for the possibility of transferring theories when he draws an analogy to Newton's theory of mechanics. To understand this theory, in Naur's opinion, it does not suffice to ’understand the central laws, such as that force equals mass times acceleration’. Rather, one has to also comprehend ’how it applies to the motions of pendula and the planets, and must be able to recognize similar phenomena in the world, so as to be able to employ the mathematically expressed rules of the theory properly’. But in fact, understanding the theory this way is possible for people who only study its documentation. Newton’s theory of mechanics was not constrained to Newton's brain; he could share it with others. And I do not see (yet?) why the theories programmers come up with when programming should be so fundamentally different that they (or at least parts of them) can't be shared, expressed, documented, and so on.

Also, I find the idea that the theory exists only in programmers’ brains a bit problematic, as it might discourage and exclude non-programmers from participating in programming-related activities. And I think we need more non-programmers in programming and software engineering! (But I am pretty sure Naur did not mean it in a gate-keeping way...)

Of course, all of this does not mean that I disagree with his main message altogether. For me, one key point Naur is rather implicitly making is that direct communication beats documentation, and that direct communication (which allows back-and-forth) is much more valuable than one-way information transfer (i.e., providing documentation). I would certainly agree with this.

And I also believe a programmer will never be able to document everything. So yes, there will always be considerations, knowledge, and reasons for actions that will not find their way into documentation or code, but that the programmer can elaborate on when being asked. And I agree that this knowledge has immense value and can only be accessed through the programmers themselves. If I look at programming education, the value of this knowledge and of direct communication could probably be emphasized even more.

And when I think about education, I am worried that Naur’s view could discourage students from producing documentation, READMEs, and tutorials. To me, his paper almost sounded as if it were not worthwhile to document anything, as it would not suffice to convey the programmers’ theory anyway. I am sure this is not what he wanted to convey, but claims like ’reestablishing the theory of a program merely from the documentation, is strictly impossible’, though true, might discourage people from documenting anything?

His text also made me think of CS education in other respects. I think that when asking students to solve some of the typical beginner problems (sorting stuff, finding paths, checking for palindromes...you get the idea), they are, first and foremost, mostly "programming to learn programming" rather than "programming to solve real-world problems". So something different might be going on with regard to theory building at that stage. The theories and mental models the students are building are probably theories of how programming works, how the programming language works, and how the IDE works. And maybe, in addition, they gain knowledge about AI’s coding capabilities, the Teaching Assistant’s leniency, and their classmates. But these theories are different from the theories you build when you already have some advanced understanding of programming (something I never obtained), and are solving 'real problems' rather than learning-oriented problems.

Once you are solving real problems, you are (hopefully) building more of a theory about the problem at hand. For instance, when tasked with programming the logic for an elevator, you might develop a theory of what it means for an elevator to operate well, identifying factors at play, such as speed, energy efficiency, fairness, and safety. Or, when programming a Spotify alternative, you will develop a theory of what it means to shuffle songs in a pleasant manner (i.e., the player should probably not play the same song several times in a row, which might happen if you just pick songs from a list randomly). I definitely believe that to teach this type of theory building, we should ’have the student work on concrete problems under guidance, in an active and constructive environment’ (I am citing Naur here, of course).

Something else I take away from this article, in terms of education, is that we should encourage certain programming methods. Yes, Naur is critical of pushing certain methods and argues that the choice of which methods to use is for the programmer to decide. But still, I guess the Theory Building view suggests we should probably foster the use of methods that more actively support theory building and sharing. For instance, I would expect pair programming to result in 'shared theories’. Probably, the software engineering community has extensively studied which methods support theory building, but I didn’t have time to look into it.

Finally, I also thought about his article from a current AI perspective. In our podcast recording, we have already discussed this idea of programming as an intellectual rather than merely intelligent activity and how this distinction might be useful in times when AI produces a lot of code. So I won’t go into this. But I have also highlighted another thing that I found particularly relevant to the current age of AI. Namely, Naur points out that when solving real-world problems, the programmer knows how their solution relates to the aspects of the world that it aims to address. Here, as he puts it, ’the decision that a part of the world is relevant can only be made by someone who understands the whole world’. Such a true understanding of the world arguably does not exist for coding AIs. And while Naur talks about ‘the world’ in a way that suggests he means the physical world, I think a similar point applies to the digital aspects of the world. Even if one programs a solution for a social media platform, or another primarily digital service that an AI could theoretically know inside-and-out, decisions about what factors are relevant and not relevant to the challenge at hand can only be made by someone who understands the environment and real-world context in which such a product will be used. I believe that to truly program such digital solutions in Naur’s sense, one needs to exist in, understand, and reason about the real world and real humans who use them. Hence, AI can’t do it; AI can’t program in Naur’s sense.

Homework programming

Ok — so much about the paper. As a second part of the homework, I did some programming with Naur’s paper in mind. While programming, I was trying to observe my brain and aiming to catch it in the act of constructing theories and knowledge. However, since I rarely program (and have never followed a CS program myself), I decided to make my life easier by following a simple programming tutorial. I expected that following the tutorial would allow me to identify at least some instances of theory building in myself, and maybe even also some theory building by the author of the tutorial as an added bonus.

As a concrete project, I decided to build a pomodoro timer to help me focus on reading papers (like Naur’s!) without getting distracted. Of course, plenty of Pomodoro timers exist. So the goal was to follow a tutorial as a basis, and then adapt the tool to better cater to my personal needs.

The first thing I noticed, even before starting any particular tutorial, was how many Pomodoro timers are openly shared on GitHub and similar code collaboration platforms. I think the activities on such platforms, where programmers fork, modify, adapt, and extend projects to some degree, might conflict with what Naur is describing about new programmers taking over existing programs. As mentioned above, he suggests that it is usually better to discard existing code and for a new programmer (team) to appraoch the problem anew. He also writes:

’[t]he point is that building a theory to fit and support an existing program text is a difficult, frustrating, and time consuming activity. The new programmer is likely to feel torn between loyalty to the existing program text, with whatever obscurities and weaknesses it may contain, and the new theory that he or she has to build up, and which, for better or worse, most likely will differ from the original theory behind the program text’.

While this might be true, it might not be as frustrating or problematic as assumed. At least, many programmers seem to find taking over existing codebases beneficial enough to do it. They prefer it over having to start over (whether it is really benefiting them is another question). If reusing code is truly so frustrating and problematic, why is it done so much? (And on a more general note, how does theory building work in distributed, large collaborative coding communities?)

Following one of the Pomodoro tutorials was partially successful. At first, I was quite excited because I felt that several theories were at play, which I could actually distill from reading the code and the accompanying tutorial. For instance, there were some choices about how to communicate the passage of time that arguably suggested some understanding of how humans perceive time. Also, the timer had three states (i.e., "work," "short break," or "long break”). This, in my opinion, revealed underlying ideas about how humans work that are inherent to the ‘pomodoro technique’ and probably have their roots in existing psychological or behavioral theories of human focus, attention, and motivation. Hence, I came to believe that a program might actually start with existing theories (e.g., humans need breaks to focus and stay motivated). In such cases, programming can also be about translating existing theories into code, rather than about theory building in a narrow sense. So, yes, programming can be theory building. But programming can also be more than theory building. Let's not restrict it to theory building only.

After following the tutorial a bit further, I noticed that I could no longer understand some of the author’s decisions --- maybe due to the lack of a shared theory! And after some time, I felt so much like building a house in the trees, without knowing about the tree underneath it, that I got uncomfortable. Maybe that missing tree is the missing theory.

Eventually, I threw out the tutorial and started from scratch, and wrote my own little program. Fascinatingly, this is more or less what Naur's article would predict. After all, he writes about the revival of programs:

’the Theory Building View suggests, the existing program text should be discarded and the new-formed programmer team should be given the opportunity to solve the given problem afresh.’

So what theories or knowledge did I notice floating around in my brain when solving this Pomodoro-timer problem? Well, mostly insights about myself --- probably because I was writing the program for myself. For instance, I realized that personally, I prefer timers that count up over those that count down. (To me, time counting up feels like I am putting in time and reaching a goal, while time counting down feels like I am running out of time and fighting against the clock.) However, to be honest, most insights did not come directly from programming, but from trying out the program and iterating on it. To me, this (trying out the program with users and updating beliefs and theories accordingly) is an integral part of programming that did not get enough attention in Naur’s paper.

While trying my timer, I also realized that my first urge when trying to focus on something difficult, like a paper, book, or a complex student thesis, is to distract myself, and that this distraction typically involves reaching for my laptop and opening my email program or browser. To prevent this, I decided every movement of the mouse and or any keyboard press should immediately reset the timer to zero, to discourage me from doing this. Maybe by implementing this timer-reset function, I have incorporated the (existing) theory that distractions are bad for focus.

Looking back, I wrote some rather bad code --- but I think the resulting timer still solves my particular focus challenge very well. When I decide to read a book or a paper, I turn it on and am discouraged from using my computer in any way for at least 25 minutes. This keeps me focused on the words in front of me, at least most of the time. Of course, I can still get distracted by internal thoughts. For instance, while focusing on something else, one tiny thing that still bothered me about Naur’s article popped into my head.

To me, what Naur describes in his paper is not just true for programming but for any problem-solving, analytical, or learning activity. I believe that whenever we attempt to solve a problem or learn something new, we engage in knowledge building and theory building. For instance, we also engage in theory building when doing physics or when observing and analysing how people behave at a bus stop or when coming up with a design for a bike shed next to our house. In fact, in the paper, Naur himself compares learning to program to learning to write or play an instrument. I do not doubt such similarlities exit. But if we see programming as theory-building, it becomes one of the many activities that can be seen as theory-building activities. The question that he does not address, and that would be interesting from an educational perspective then, is if there is something unique about programming in that regard --- if and how this theory building differs from other types of theory building. How is learning to program different from other types of learning, and how is the programming activity different from, e.g., engineering or architecture? And if there is no difference, can’t we maybe teach problem-solving and theory-building at a more general level of abstraction so the skill can be applied more easily to many other domains (programming, engineering, music)? Then again, probably theory building is a skill that can’t be taught in the abstract.

Ok, this note got way too long. Reading it might even take 25 minutes. So, in case you want to use my weird pomodoro focus tool while you read this, I have put it online here: https://creativecode.cc (I realize it is a bit late to tell you this at the end of the note, but well, there will probably be more notes in the future). I am looking forward to the next recording and to our next read!

Cheers,
Hanna