At what point did programming take a wrong turn

Show and Tell
1

So, I’m here researching for an article I want to write on “Scaling Elm Web Applications” and I come across this 8 year old comment by Evan. It’s not the first time I’ve seen him make a comment like this so I find it very telling that he has to repeat this over and over. Do software developers not know about data abstraction? Are they not taught that anymore? Data abstraction is what Evan is describing in his comment. Data abstraction is what he described in his presentation “The life of a file”. (Yes, and by Richard Feldman as well in “Make Data Structures”.)

When I was taught Pascal programming in secondary school in the 90s we learned about data abstraction. It was one of the key concepts that was stressed. Build your program structures around your data structures. Pascal programmers valued structured programming, modularity, and data abstraction. You can shrug at Pascal syntax all you want but those who took the time to learn the language were also exposed to programming practices that stood the test of time. On reflection I realized that I’ve been implicitly using those ideas I learned in Pascal in my Elm programs.

Well as you can imagine I got sidetracked and decided to look into books on Pascal programming to see what they taught developers at the time. I found a book called “Data abstraction and program development using Pascal” from 1988. Here are a few excerpts:

This book integrates data abstraction and the use of abstract data types in programming into a course on data structures and algorithms.

… the main theme is the useful guide to the design of programs in modular form provided by data abstraction. The choice of suitable modules out of which to build large programs is the main problem in top-down design or step-wise refinement. Once the modules have been designed, programming can proceed at a much higher level than that provided by the usual programming language constructs.

There has been extensive discussion of these issues in the literature. Over the past 10 to 15 years it has become increasingly clear that programming must be liberated from the burden of implementation detail. This means that low-level hardware features and peculiarities of particular programming languages should be kept out of programming for as long as possible, noting that the semantics of a program are determined only by the semantics of the data. Programming should therefore take place in two stages:

  1. The design of the abstract data types which are required and of the algorithms for the data types. This is the actual problem solving part of programming.
  2. The representation of the abstract data types and of their algorithms in a programming language.

The first stage begins with the recognition of the information which is available. Decisions must be made about the operations which will be performed on the data. In other words, programming begins with an abstract view of the data to be used by the program. This is the most important phase of programming because all decisions about modularization of the program ultimately depend on it.

The book demonstrates how the use of abstract data types can lead to the design of programs which are modularized in a way that makes them easy to understand and easy to modify. M.A. Jackson in Principles of Program Design (Academic Press, London, 1975) stated that the structure of the data should be reflected in the structure of the program.

… A good modularization becomes a natural consequence of the use of abstract data types.

Are you kidding me? He said “Over the past 10 to 15 years it has become increasingly clear that programming must be liberated from the burden of implementation detail.”. So that’s what since the 1960s. And we’re still programming in languages like JavaScript, Ruby, Python, etc. that could care less to allow you to hide your implementation details (i.e. no opaque types). Anyway, rather than get sidetracked let’s dig into this book he mentions “Principles of Program Design” from 1975. Let’s see what it says:

page 10, … program structures should be based on data structures.
page 11, … If, therefore, we give our program the same structure as the data it processes we can expect that we will have no difficulty.

The design techniques.

  • We start by considering the data structures, which we then use to form a program structure.
  • We list the executable operations needed to carry out the task.
  • We allocate each operation to a component of the program structure.

The quality of the work we do as we take these steps will determine the quality of the programs we write.

This must be a joke. And this book gives all its examples in COBOL. When did all this useful information get lost? So, you’re telling me that in 1975 COBOL programmers knew how to design better programs than present-day JavaScript developers. Are we too focused on programming language syntax and features and not enough on the timeless principles of program design?

Out of curiosity, I skipped ahead to Chapter 5 on “Errors and Invalidity” to see what he had to say about that.

Error processing accounts for a high proportion of the program code in a data processing system.

… We will use the term “error data” for data containing errors of this kind, and we will contrast error data with “good data”. The distinction between error data and good data is meaningful to the user of a system: broadly, good data is what he tries to present to the system; error data is what he presents when he makes a mistake. But no such distinction is meaningful to the system itself. From the point of view of the system and its programs, both error data and good data require processing, and the processing must be correct according to the specifications.

… Because error data must be processed correctly, just as good data must, we must design our programs to take account of error data. And this means that the data structures, on which the program design is based, must also take account of errors. It would be wrong to design a program to handle only good data, hoping to fit the error processing into a structure determined solely by the good data. The result would be a partially designed program–partially correct, partially intelligible and partially maintainable.

Pure gold. Impeccable deduction. You can expect that I’m going to be drawing inspiration from these books for my future articles.

Data abstraction by example

Tic-tac-toe

You can play a full game without a UI.

Wordle

You can play a full game without UI.

Calculator

The calculator is fully unit tested and driven by tests instead of by a UI. No need for elm-program-test, not to imply that it is never needed though.

And more…

SICP

SICP has an entire chapter on “Building Abstractions with Data”.

Java

I recall learning about it in Java as well. For e.g. here’s some notes on it from a Princeton course.

The Clean Architecture, Hexagonal Architecture, Onion Architecture, Screaming Architecture DDD, etc.

Seems to me to be derivable from data abstraction. It’s couched in OOP but has nothing to do with OOP. Read Domain Modeling Made Functional by Scott Wlaschin to learn more.

Domain modeling

… Domain Driven Type Narrowing, CQRS, state machines. Just start with data abstraction.

A short history lesson

I recently discovered this and found it quite interesting. Barbara Liskov introduced abstract data types and the principle of data abstraction.

Conclusion

Data abstraction is a useful concept that transcends programming language paradigms. It’s a technique that software developers learned a long time ago to help them tame complexity in large software systems. Computer scientists have traditionally shown how to use the concept with various data structures like stacks, queues, trees, and graphs but it extends beyond that to other domains as well.

P.S. These are unpolished thoughts that still need refinement but I couldn’t help but share my findings. Back to thinking about scaling Elm web applications.

10 Likes
2

I’m very interested in this discussion because I’ve been following Elm for at least 7 years but I still find the same confusion on this topic - the update function topic, not data abstraction. Sorry if I derail your focus a bit.

In the original reddit post you linked, the question asked is “how do you scale your update function?”. I’ve always struggled with the same issue, not being happy with what ends up being an uninteresting piece of boilerplate that requires way too much maintenance. I don’t like long update function that are hard to navigate and structure.
The only solution I’ve found is to extensively use function to simplify it (which still results in a case list as long as the number of UI events) and/or give it a hierarchical structure, splitting it in smaller update sub-functions (which has a plethora of small management problems).

This is where my confusion arises: what does data abstraction has to do with the complexity of the update function? Modelling data types around the domain and your application around the data types is the best way to structure a project, no objections here, but the size of the update function only depends on the Event type, not the Model (does it not?).

1 Like
3

I don’t think data abstraction has anything to do with the complexity of the update function. I think the response from Evan is a bit confusing in that regard, but he did also say “That’s all pretty vague advice”, so I get the impression he was just listing some suggestions that might overall help with program structure, rather than specifically that better data abstraction is going to simplify the update function. I mean, it might if there is just too much code in the update that could be hidden behind a better abstraction, but…

If your application has 100 side effects, you will have 100 update function case branches overall - even if you split into many nested update functions. The only way I can see around that is using:

type Msg = Next (Model -> (Model, Cmd Msg))

or even

type alias Msg = Model -> (Model, Cmd Msg)

And choosing which next function to apply in the view or subscription code.

I don’t do that, but I do always split out each and every brach of the update function into its own top-level function and try to give it a good descriptive name that reflects what it does.

2 Likes
4

That’s correct, the number of cases in your update function depends on the number of data constructors in your message type, Msg. If Msg has n data constructors then your update function will have O(n) cases to consider. Is there a way to do better than that? For e.g. can we get it down to O(log n) cases? Well, there’s no general algorithm or technique that would allow us to do so since the Msg type depends on the interactivity you have in your UI. If your UI is static then you most likely don’t even need a Msg type. However, if your UI is highly interactive then your application would have lots of events and those events would generate lots of different messages.

And that’s a good solution. Let’s say we have the same UI but in React. I bet if you counted all the functions that handle all the interactions you’d end up with the same number of event handlers as cases in the update function. There’s no way around it since you have to decide on the semantics of a given interaction. Elm is already making it easier for you by putting it all in one place, i.e. the update function.

Can you elaborate? What are the small management problems?

My take on it. Elm gives me the features (modules, custom types, opaque types, pure functions, immutable data) to model my problem to exquisite perfection using data abstraction. When I hook that data model up to the UI all I have to do is write some boilerplate code to handle the interactivity. Maintenance involves fiddling with simple boilerplate code. That’s a tradeoff I’m willing to make.

This fits into managing the complexity of the update function because it significantly reduces the amount of code that ends up in a given branch.

I also just wanted to point out that the update function is just that, a function. It’s seems weird to ask how to scale a function? You ask how to scale a server so that it can handle more concurrent connections. But, for a function that gets too large you ask about how to refactor that function to make it more manageable to deal with. When you think about it that way then you realize it’s a question about refactoring a large function and there’s tons of resources on doing that. Here’s one example. It’s not an Elm specific problem. It’s a program structuring problem.

Conclusion

TEA redirects all your messages to the update function. Messages are generated due to the dynamic/interactive parts of your UI. More interactivity, leads to more events which leads to more messages needing to be handled. In a different language/framework you’d handle these events in separate functions scattered throughout your code base. Regardless, you have to handle these events because the way you handle them define the semantics of your UI. There are two orthogonal approaches to refactoring your update function:

  1. Reduce the amount of code in an individual case. Extract a function or think about the data structures you can use that would allow you to move the logic into a function in a module. Either way you end up extracting a function.
  2. Reduce the amount of cases by grouping the events in some sensible way. That all depends on your understanding how your UI works. You don’t want to just group for grouping sake because that could lead to even more confusing code.

Above all, the update function is a function. As a result, all the techniques for refactoring large functions will apply.

1 Like
5

The approach I took in my photo album app was to break up / group my Msg type into related “subtypes”. (in scare quotes because this isn’t subtyping in the OO sense.)

type MainAlbumMsg
    = Bootstrap BootstrapMsg
    | Meta MetaMsg
    | Album_ AlbumMsg
    | General GeneralMsg

Then my update function just has four cases, each of which delegates to a helper function that just deals with one subtype of update message.

Have a look at the type definitons and update functions for all the details.

The cost of this, of course, is that everywhere I produce one of these message subtypes, I have to wrap it in MainAlbumMsg. But I find that a very worthwhile tradeoff.

2 Likes
6

One funny presentation about this “wrong turn” is Bret Victor’s “The Future of Programming”.

In any case, it is an evolutionary principle: survival of the fittest. Not the strongest, not the prettiest, the fittest. Most of the programming languages did not fit properly into the context. Fittedness is a function of object & context.

Also, Abstract Data Types are really Objects. That is, data defined by behavior (interface) not by its structure.

1 Like
7

On the topic of scaling up, my biggest app so far (around 40k loc in 70 modules) has a big flat model, and a big Msg type, mostly flat as well.

Every module imports this Types.elm file, and each module has the implementation of the relevant view and update sub-functions, which are in turn called by the main update and view functions.
So far I found it less troublesome than wrapping related messages together into subtypes of Msg.
Is there something fundamentally wrong with this approach?

1 Like
8

No and yes.

Why no?

No because you can give the Elm compiler your modules and it compiles without issue. You can then run your application and it works as expected. So, there’s nothing wrong with the approach in that regard.

Dillon Kearns in The Life of a File Elm Radio episode talks about how the pain you feel when you’re working with code is a signal that’s telling you that something may not be quite right. (*)

If you’re not feeling any pain with your code then there’s probably no need to refactor.

Why yes?

Yes because it is not the case that every way to split your code is helpful in the long run.

Here’s a way to split a book. First, let’s get rid of grouping by chapters. When I group by chapters I tend to want to put ideas related to one concept under that chapter. Even though it’s helpful to do so in the long run, while I’m writing the book it’s hard to think of everything I want to say in that chapter all at once. So you know what, as ideas come to me I’m going to write them down. And then, I’d leave it just so. All my ideas are there in the book so what’s the problem?

Here’s a related example. What’s 0x2FB + 0xED in decimal? There are at least two approaches. First you can do the addition in hexadecimal and then covert it to decimal or you can do the conversion and then the addition. The point is, some translation is involved. So it is with programming. We have to get the mental representation of our solution to the problem into code so that the machine could understand. If what we write is far removed from how we have it mentally represented then we have to pay a translation cost every time we interact with that code. That’s why high-level languages were created. Rather than translate our solutions to assembly language we write using abstractions like conditionals, loops, and functions. However, as an example, I’m sure your mental representation of tic-tac-toe is not in terms of conditionals, loops, and functions. It’s probably in terms of x’s and o’s, 3x3 grid, game rules, etc.

Data abstraction is a tool that we can apply to program design so that our language can be raised up to the level of our mental representations so that the cost of translation between our mental representations and code is reduced. This makes data abstraction helpful in the long run and it leads to nice properties for your code.

Mental representations

I first learned about the value of mental representations from Anders Ericsson’s book Peak. Chapter 3 is devoted to the topic. Here’s an interesting except:

Beginning in the early 1970s researchers sought to understand how grandmasters remember chess positions with such accuracy.

Herb and Bill asked a simple question: Are chess experts recalling the position of every piece, or are they actually remembering patterns, where the individual pieces are seen as part of a large whole?

To answer the question… They tested a chess master, a mid-range chess player, and a chess novice on two types of boards, one that had the pieces arranged in a pattern taken from a real chess game, and the other with a random jumble of pieces of the sort that made no chess sense at all.

When shown chessboards… arranged in a pattern from the middle or the end of a chess game, the master could remember the positions of about two-thirds of the pieces after five seconds of study, the novice could remember only about four, and the mid-range player was somewhere in the middle.

When shown chessboards with the pieces arrayed randomly, the novice player did worse.

What was surprising, however, was that neither the mid-range player nor the chess master did much better.

Something similar has been shown with verbal memory. If you ask someone to recall a seemingly random assortments of words verbatim, starting with the first word – “was smelled front that his the peanuts he good hunger eating barely woman of so in could that him contain” – the average person will remember only the first six of those words. If, however, you read the same words rearranged into a sentence that makes clear sense – “The woman in front of him was eating peanuts that smelled so good that he could barely contain his hunger” – most adults would remember most, if not all, of the words in perfect order.

What’s the difference? The second arrangement carries meaning that allows us to make sense of the words using preexisting “mental representations.” They’re not random; they mean something, and meaning aids memory. Similarly, chess masters don’t develop some incredible memory for where individual pieces sit on a board. Instead, their memory is very context-dependent: it is only for patterns of the sort that would appear in a normal game.

Any relatively complicated activity requires holding more information in our heads than short-term memory allows, so we are always building mental representations of one sort or another.

9

That’s a wild strawman to build and you spend all that time arguing against it instead of either checking if software developers really don’t know about data abstraction or if that’s really the problem in mentioned comment.

And the subsequent waterfall of links made me chuckle a little. Liskov’s paper? Fundamental idea is that ADT are defined completely by operations that are available on that type. That’s a big no-no in Elm, where you need to reach right ear over left shoulder with storing functions on extensible records. Also this is not a first way to abstract data in other functional languages, even if they give you access to protocols/typeclasses/traits. Functional data modeling is about shape and contents first.

Data abstraction is a loose term, reinvented multiple times through history of computer science. Linking to all related concepts doesn’t add any weight to the argument. First establish necessary definitions, then argue.

1 Like
10

Even with one flat model and one big Msg type, things that are conceptually relevant to one problem are split into their own modules, the modules in turn contain all the relevant update and view functions, so there is some abstraction still.

I guess it might get unwieldy if the app grows a lot more, but for now and considering I am the only person working on it, so far so good…

1 Like