How to Design Programs | Hacker News Reader

How to Design Programs

htdp.org

253 pointsLordNibbler66 comments

After 20 years of programming, this is what comes to my mind when I hear "How do Design Programs":

1: Start with the data structure

The tools to operate on the data can be rewritten or improved without much pain. Changing the data structure is what hurts. If the data structure is elegant, the code will fall into place. If the data structure is messy, the code will grow into a giant hairy ball of madness.

2: Don't use a DB. Use human-readable text files

It makes everything so much easier. You can see if your data structure is elegant. Because then the files will be easy to read and navigate. You will be able to start up your software 20 years from now without any installation and without having to go through the hell that is setting up the environment and updating dependencies. The website you are reading this on, Hacker News, stores all data in text files.

3: Build small tools to operate on the data

Like Linus started git by writing small tools "git-add", "git-commit", "git-log" etc. On the web you can have one url to do one thing (/urser, /item, /edit here on HN) and map them to one code file on your disk. If you want to use a framework like Django, Laravel or Express, those will unfortunately make it a bit harder to do that. But you can still stick somewhat closely to this approach.

4: Let people use it right away

If you are building it for yourself, you already have a user. Great. If not, let your target group use it right away. Otherwise, you will waste many years of your life building software features nobody understands or even wants.

> 2: Don't use a DB. Use human-readable text files

This is interesting, can you elaborate? Do you mean like CSV files, or some JSON structure, etc?

Depends on what you want to build.

I do use CSV and JSON for some types of data, yes.

Sometimes I use YAML. Sometimes just free text. Sometimes I roll my own format.

this also holds true for serialized vs plain text data (json, csv, or roll your lang + parser : ))

funnily enough, points 1, 3, and 4 are all core parts of the book : )

I would agree with everything except 2). Human-readable files are ok if you're building a small program mostly by yourself, but in larger programs, on a team with other people, it becomes a mess very quickly. And if you need to enforce data integrity, forget about it. You're going to find yourself replicating what a DB gives you for free in your own code, except you're going to get it wrong.

So: Hacker News, tiny team (one person?), very simple application, doesn't change. An accounting system: rather complex, frequently changing requirements, often developed by larger teams, needs to be accessible to non-developers, has data integrity requirements. You've really got no choice except SQL.

You should definitely consider every application's needs individually, but there's a line for everything where it makes more sense to use a DB, and not understanding where the line is will bring you a lot of pain. As for longevity: the SQLite3 format has been around since 2004 and is utterly ubiquitous. I think it's pretty safe.

Small teams? Here is to small teams! Vim, Git, Hacker News, Photopea - many of my favorite, most used programs are created by a team of one!

Larger programs? Look at Linux and its "everything is a file" philosophy. Linux is one of the largest codebases out there.

SQLite will be around for a while, but not as long as text files. Who knows how long you can easily access present day sqlite files without fiddling with SQLite version numbers. And the format does not offer the easy access to the data that text files do.

I'm not saying nobody should ever use a DB. But files are often the superior approach.

Torvalds created the initial version of Git. It was eventually handed over to Hamano and has been developed by many different people since then.

> Vim, Git, Hacker News, Photopea - many of my favorite, most used programs are created by a team of one!

Git is actively maintained by a number of people: https://github.com/git/git/graphs/contributors

Most commercial software is developed by teams.

> Larger programs? Look at Linux and its "everything is a file" philosophy. Linux is one of the largest codebases out there.

"Everything is a file" is an abstraction that Unix presents to the user. It's certainly not the case that that's how everything works underneath — the file system itself isn't a file, for example.

> I'm not saying nobody should ever use a DB. But files are often the superior approach.

And I'm not saying nobody should ever use text files. But a database is often the superior approach.

"The file system itself isn't a file" is not a valid argument.

Otherwise I would counter "Even SQLite stores its data in files".

I agree, I would only add that you should implement the SQL db as matter of factly as possible. If you can store data in files, figure out a way to make a dead simple set of tables, maybe even just one. Nothing fancy. Just wait till you hit real limits before thinking about all the high availability, dtributed db stuff.

Regarding 2: I've had problems with this strategy. Even though I used the swap technique instead of overwriting, files easily get corrupted on common file systems, and if it's just the user force quitting the application during the operation. (I mostly use Ext4 for testing.) Whatever Sqlite does under the hood is way more resilient to such problems. I guess that's because the Sqlite developers have been testing ACID compliance extensively.

In one of my Racket applications with high integrity demands I've resorted to writing the temp file, swapping it with the original, then opening it read-only and verifying all of its contents. That is very reliable but obviously slow. But in another application written in Go I've switched entirely to Sqlite even for simple settings files and had no problems since.

We would have to discuss the specific use case and how the data got corrupted.

When interacting with a typical web application, the user cannot terminate it in the middle of a file write application.

Is the swap technique you mention writing to a tempfile and then performing an (atomic) rename to overwrite the existing file? I understand how that could cause data loss if the process exited before the rename but I don't understand how it might cause corruption. Are you able to expand on that?

A related thing I discovered recently is the potential non-atomicity of writes using O_APPEND on Linux[1], although I couldn't get the attached test program to fail on my machine. I would love to find some kind of confirmation that this behaviour has been changed and that appends can be relied upon to be atomic.

In the application I'm working on at the moment I've managed to get add more certainty around this stuff since I'm only ever appending to the file in 4096 byte chunks, so can perform a simple file size check to see if data was written completely or if the file needs to truncated to the nearest multiple of 4096. I'm fortunate that it prevents having to do something like open it read only to verify contents as you mentioned.

1. https://bugzilla.kernel.org/show_bug.cgi?id=55651

Yes, I used a tempfile with atomic rename. I agree data corruption should not occur as long as fsync(2) is used before the swap. If I remember correctly an empty file was an error condition in this case, though, and that sometimes occurred. Problems can occur when the user shuts down the OS or hits that reset button. Besides, in Go it's easy to inadvertently write to a file concurrently and extra care has to be taken to avoid that. So you might need a locking mechanism, too, and then it's getting really complex.

Of course, it should be perfectly possible to get this right in languages like Go or Racket. At least Go has low-level enough interfaces to the filesystem API. My point was merely that using Sqlite turned out to be less error-prone in my experience for end-user applications, especially if you use WAL and set some cautious Pragma options. It's really good at dealing with unusual filesystem conditions.

Thanks for clarifying.

I agree that reliably writing files is a sneakier problem than it first appears and that the likes of SQLite have already solved it.

Despite that my preference these days is still for a DB, like almost all dependencies, to have to justify its existence in my projects rather than defaulting to it as many seem to favour. It's straightforward to add SQLite but I'd typically rather take a little extra pain around the filesystem upfront to not have to deal with all the extra complexity of an SQL database if I can avoid it.

Naturally, this kind of simplicity is just one factor among many such as the size and shape of the data, expected access patterns and a host of others to weigh up during the trade-off decision.

> SQLite does not compete with client/server databases. SQLite competes with fopen().

https://www.sqlite.org/whentouse.html

At least for my needs, NeDB[0] is the best of both worlds for prototyping and early-stage production releases. It's human-readable, on-disk, greppable, still supports indexing and a subset of Mongo features while remaining serverless and in-memory.

[0] https://github.com/louischatriot/nedb

See https://danluu.com/file-consistency/ for a blog post on why files are hard.

Excellent link, thanks!

One of the linked papers[1] in that article is highly recommended.

1. https://www.usenix.org/system/files/conference/osdi14/osdi14...

So people shouldn’t use databases because 20 years down the line it will save someone the hassle of installing it?

What about when the data grows a little bit and you need an index? Or you need to do a simple join? Implement your own BTree? Write your own join? Reimplenting a worse version of SQLite is not my definition of everything being easier.

I agree with the rest of the points btw.

you migrate into a database when you find you need an index, or a join.

This migration is easy to go from a flat file into a database tbh. And you can do this migration in pieces - copy the flat file and perform the ETL as a separate thing, all while your existing app runs fine unchanged. You can then implement the needed joins or indexing on this copy in the DB, and then schedule some sort of job to re-import the DB from the flat file.

Sure it's not real time, but it's enough to implement most features, with little effort from migrating the read/write code in your app from flat file to the DB. And nothing stops you from migrating the read/write api from flat files into the DB, after you find that it is really needed.

> you migrate into a database when you find you need an index, or a join.

So, almost always.

While I agree databases are widely overused in areas where they are extreme overkill, whether human readable files are recommendable really sort of depends on what sort of data you are working with. Even just seeking in a line- or delimiter-based format is slow if the file is sufficiently many gigabytes. There are many cases where human-readable files fall apart, and ACID solves a lot of those problems.

Honestly, the software I wrote 10-20 years ago, if it doesn't run now it's not because I used a database system that's fallen out of fashion. If anything, systems built back then most likely would have leaned into storing everything into some cronenbergian XML-amoeba. It's unpleasant to work with, but it's not like it's somehow no longer viable.

The problems I hit are caused by changing requirements and some assumption that were I had before implementing something are no longer valid, and now you need to change a lot of code to work with the new assumption. Usually if I have the time I might get a beautiful data structure/code structure at the third attempt.

For HN text files is probably fine but for most enterprise apps with changing requirements and people expecting to do any kind of query I think relational is a good default. It also gives you a lot of tooling out of the box. Yes it does mean a bit more to set up later as a dependency. SQLite might be good there as you can just bundle the whole thing in the same repo.

1,3,4 are all fine but 2 ? really ? As far back as the 1970s Codd was already screaming at anybody who would listen not to roll your own persistence.

I can see the appeal: text files are forever! read and write as simple strings!. But what do you do when you want to search ? whip up a regex or a for loop ? can you see how this will get unimaginably nasty with any remotely complex query, you will end up implementing a buggy, slow and informal subset of SQL without realizing it. Or, what if the data has constraints in it, like uniqueness of a particular column value across all rows, or other complex constraints, or types. Text files can't help you. Hell, if you aren't careful with charsets text files produced on 1 OS turn out to be garbage on another.

Maybe use text files as a conceptual\prototyping tool to imagine the persistent form of your data structures, or as a dump of the database for backup. That's reasonable.

I think it depends on what ones actions performed will be. If I am rendering a blog from some markup files, I might not need to build my own persistence or things like that. The information flow is unidirectional. In such and other simple cases, a relational database is overkill.

It is also not too difficult to switch from plain text files to a database, if one does this step in time, before implementing ones own persistence, joins and whatever on basis of files.

+1 for #2. Keep it simple

2. Wow I didn't know that HN did that! I have never really considered using text files as long term storage outside of some very questionable things I had to implement at financial institutions for some ancient FTP/UserManagement stuff.

Do you store in plain text or do you simply use CSVs and treat them like a database?

Do you find that the repository pattern helps mitigate the issue with long-term DB deprecation? You could backup your databases as CSV files, and then load those into any DB server later. Your repository layer should allow you to use whatever DB tooling is fancy at the time and the CSV backups would be around for longevity?

2: Don't use a DB. Use human-readable text files

For even faster prototyping -- maybe better called experiments -- skip the text files and do everything in memory. Just use the built-in collection types of the programming language. In Python for example, that would be lists, dictionaries, tuples etc, then you can simulate database queries with set comprehension expressions.

Agree. And I will even take it one step further: 95% of the code you write will be code that transforms one data structure to another. Think about it: even UI code is exactly that. It transformed data in one representation (internal data) to another representation (the UI state). And back again when the user presses “OK’ or whatever.

If anyone wants a faster paced version of the book or the edx course, here's a link to one of the authors' website having videos and problems/solutions. I have found this to be helpful to share with devs who have experience but would like to revisit fundamentals.

https://www.cs.utah.edu/~mflatt/htdp-lite/

https://my.eng.utah.edu/~cs5510/htdp-videos.html

Here's another course which I have used to train interns. It's faster paced and useful for people who learn and progress at a faster pace.

https://web.cs.wpi.edu/~cs1102/a16/index.html

Here's another version of the same/similar where the assignments are challenging enough. You can do them in either racket or pyret.

https://cs.brown.edu/courses/cs019/2018/assignments.html

Thanks!

How to Design Programs (2014) - https://news.ycombinator.com/item?id=26493990 - March 2021 (136 comments)

How to Design Programs, second edition - https://news.ycombinator.com/item?id=16561815 - March 2018 (30 comments)

How to Design Programs, Second Edition - https://news.ycombinator.com/item?id=14932552 - Aug 2017 (40 comments)

How to Design Programs - https://news.ycombinator.com/item?id=12768134 - Oct 2016 (3 comments)

How to Design Programs, Second Edition - https://news.ycombinator.com/item?id=8778569 - Dec 2014 (39 comments)

How to Design Programs, Second Edition - https://news.ycombinator.com/item?id=6150967 - Aug 2013 (26 comments)

How to Design Programs, Second Edition - https://news.ycombinator.com/item?id=2958108 - Sept 2011 (18 comments)

How to Design Programs: An Introduction to Computing and Programming - https://news.ycombinator.com/item?id=2049477 - Dec 2010 (17 comments)

How to Design Programs - https://news.ycombinator.com/item?id=637152 - June 2009 (4 comments)

I prefer Norvig's "Design of computer programs" over this: https://www.udacity.com/course/design-of-computer-programs--...

I learned how to build a vocabulary for the problem domain first, and then use the vocabulary to solve the actual problem through this course. Norvig has great examples on bottom-up problem solving approach.

There needs to be a slight 'middle up' come back.

Could you elaborate on what that means a little?

Likely a reference to the sit-com Silicon Valley.

when you're doing neither top-bottom nor bottom-up. I think pg or some other lisper described that by a set of thin DSLs, so not purely bottom-up, something a bit more agile.

They're both worth checking out. The biggest complaints I've seen about either were about the pace: slow for HtDP, fast for Norvig. I think HtDP's recipes are worth reviewing even if you'd get bored with its pace.

As someone who was a self-taught programmer working through this book has been an absolute game changer for me. After learning about design recipes, type-driven development (although they may not use that term), function wish-lists, recursion, etc. I was able to easily tackle problems that would baffle me before. And my programs just worked with so fewer problems! I mostly build stuff w/ TypeScript/React and I've found the thought process to be very applicable and helpful.

How long did it take you to go through the book?

I've worked at it very occasionally, off and on over the last couple of years and currently I'm on section 4/5.

If I were to do it consistently for an hour a day 4ish days a week I think I could have finished it all in 2-3 months.

> I was able to easily tackle problems that would baffle me before

could you please explain how this book helped in tackling a new class of problems?

I'm currently going through a youtube (edx?) video course[1] based on htdp, which I found through this hackernews comment[2].

I like it so far, but was initially surprised that there's a systematic way of designing programs. I've just been winging it throughout my self-taught career.

[1] https://www.youtube.com/channel/UC7dEjIUwSxSNcW4PqNRQW8w/fea...

[2] https://news.ycombinator.com/item?id=28351733

IMHO, the best introductory programming course there is. I worked through it when MOOC were still free.

I think it is better structured than HtDP and the recipe pages in the wiki are priceless. Do they have a course website?

I couldn't find the course site used in the videos, but I did find the design recipes and other info on edx:

https://edge.edx.org/courses/course-v1:UBC+CPSC110+2021W2/77...

If my recollection is correct, some thought HTDP was an easier read than SICP. But now, there is a version of SICP adapted for Javascript:

https://mitpress.mit.edu/books/structure-and-interpretation-...

Does the assertion still hold?

I’ve not read HTDP, but I’ve been reading the JS SICP in dribs and drabs and find it very readable. (I’ve not read the original.)

I found HTDP a lot easier to read and work through because it works through more "practical" problems (like building a game) whereas SICP gets into some pretty heady math based problems. Also see this article that explains how it takes a different approach to teaching recursion. I found this approach very understandable and helpful.

https://parentheticallyspeaking.org/articles/how-not-to-teac...

i would rec HTDP, simply because DrRacket has some very cool tools for tracing recursive calls

Yes it does.

Scheme is not what makes SICP challenging. The sheer density of concepts is.

HtDP is a bit repetitive and gets a bit boring over time.

While some things overlap, I would recommend to first work through HtDP (or better through this online course https://www.youtube.com/channel/UC7dEjIUwSxSNcW4PqNRQW8w/abo...) and then work through SICP - especially if you try to learn programming by yourself.

I'm so upset at my early educators that they did not expose me to lisp when I was first starting.

Everyone leaving a CS education should work through SICP.

Lately I've been wondering how different my life would be if my university had chosen LISP over PASCAL for intro CS, and introduced computation at a deeper level than 'for loops are great for computing the stuff'

I started reading this and taking the edx course that’s based on it (How to Code) the other week. I feel pretty comfortable reading code and modifying things, and finding documentation, but tend to get stuck deciding how my data structures or types should be laid out. This week I’ve hit the “How to Design Data” part of the course and it’s been giving me a lot of clarity.

Approximately how long does it take someone to read this entire book?

It took us a little less than a semester at Uni, so roughly ~2.5 months, if you are doing all the exercises? Note that this was 1/4 classes we were taking that semester, so probably less

https://ds26gte.github.io/tyscheme/index-Z-H-2.html#TAG:__te...

From a recent Reddit comment:

https://www.reddit.com/r/compsci/comments/vyxqqt/comment/ig5...

Here is a course (with videos) based on HtDP 2e: https://legacy.cs.indiana.edu/classes/c211/index.html

I do think Concepts, Techniques, and Models of Computer Programming by Van Roy and others, is a more comprehensive book on the same topic. It ties together a lot of programming into a systematic science.

I actually prefer CTM over SICP. A really great book.

Wasn't the first edition longer than this one?

https://htdp.org/2003-09-26/Book/curriculum-Z-H-1.html#node_...

They're similar in length, but the First Edition covers somewhat more material, in particular mutation, while the Second edition has more details and exercises, and covers the 2htdp/universe functional animations that are new for that edition.

Reply on news.ycombinator.com