Computer Science from the Bottom Up (2016) | Hacker News Reader

Computer Science from the Bottom Up (2016)

bottomupcs.com

618 pointsmerlinsbrain76 comments

Author here ...

Yes as pointed out many times not "computer science" and I somewhat regret the name. However, it came out of me being a teaching assistant for people doing computer science degrees. A surprising number of people got to 3rd year operating systems courses without realising things like 2^10 is a kilobyte, 2^20 is a megabyte, etc. Let alone how a program was linked and loaded. I hope for this to be helpful, there are plenty of similar resources but sometimes the way one person says something resonates more than another.

I deliberately wanted to avoid x86-only to illustrate for similar reasons. Unfortunately Itanium proved to be a poor choice, ARM would have been better, but it gives me something to update if I get time! However, much of the basic content still remains relevant many years on.

What year should we put up there?

2016 probably

Thanks!

Looks like someone has vandalized your guide.

> Reordering

> This bit is crap

Yes, it has some rough edges. One lesson you can learn is probably not to write things like this, and just let what you have stand as it is, and incrementally improve it.

Thanks for the guide nonetheless. Going to be refreshing myself on a lot of this.

Is there a mechanism to submit fixes?

This is a wonderful resource, but the deeper I get, the more I find it needs a little proofreading. I'd be happy to open PRs/whatever with typo/grammatical fixes.

Also, thanks for writing this - I've had to deal with more and more of these concepts recently and this is the first resource I've found that has helped me understand how the parts fit together and why they exist.

Isn't it amazing how people pass courses, even perhaps demonstrate mastery at a point in time, but manage to get to later courses without fully understanding things? Students end up with a very strange mental framework by the time they graduate, and it seems like most students actually know shockingly little. I don't know that there's a solution, or even that it's an issue. To me, this is simply a reflection of how people learn.

Regardless, this seems like a nice little document for those 20% of students who are still willing to read supplementary materials. Then again, this is short and clear enough that if it were properly chunked within a course and had graded assignments attached, many students would probably actually skim it.

If you ever want to develop this some more, I hope you'll consider something like Runestone[0], in order to give it some auto-graded questions along the way!

[0] https://runestone.academy/runestone/default/user/login?_next...

When I did my CS programme decades ago, we all started with Scheme, which is very high-level, and forced everyone to focus on the algorithms, the math of it, instead of what the hardware is doing, or how the Scheme interpreter is implemented. It gets you going, thinking about values and execution and iteration and recursion.

Starting with bits and bytes and hardware would be pretty goddamn boring, I think. You'd lose a lot of students that way.

That said, in the third year we had a course in analog electronics, which was basically transistors and logic gates.

Following that course was one in digital electronics, where we all built our own little toy 8-bit computer, wiring the CPU ourselves, writing the microcode ourselves. I'll never forget the a-ha moment when you realize that your instruction set are just binary patterns representing which wires to put a current on, which units to toggle on and off. The instruction to move a value from a register to an address in RAM has to look like this, because you need to toggle the read input on the correct register, and the write input on the RAM unit, and everything else has to be off. Blew my mind at the time.

The clock was manual if you wanted to, so you could step through and watch your little CPU run a program, or you could set it to like 1Hz and watch the thing go. And from there, you can sort of get how a modern computer works, it's just a matter of going from 1Hz to 1GHz, wider buses, wider instruction sets, but it's no longer "magic" how the CPU works, it's all ones and zeroes, for a reason, and you now know that reason.

I think it depends on the audience.

For a group of prospective CS majors, or people learning programming for its own sake, I think it would be good to start with a high level language, say Python, Scheme or Ocaml, and then progressively deconstruct the layers of abstraction between the language and the physics.

For a group of electrical engineering majors, it might actually tie in better with their other courses if one starts with simple physical constructs like bits, bytes, and gates, and gradually introduce abstraction layers to form more convenient programming models.

That’s basically how they taught my computer architecture course, but they started from C (instead of Python) and worked back to assembly and then to transistors or whatever those gate things are (I studied enough to make an A and don’t care anymore unless someone pays me to).

I think it must be a reasonably normal approach.

Scheme is deadly boring. You'd lose a lot of students that way. Starting with bits and bytes and hardware would be pretty goddamn fun, I think.

I first really got into things with assembly language for DOS. It was interesting to directly control the IRQ controller, real-time clock, interval timer, and keyboard interface. These were all motherboard chips that could be messed with.

Years later I passed a mandatory Scheme class. I tolerated it to get my degree, but I was furious. I handed in just enough assignments to pass the class. If the degree had started with Scheme or required very much of it, I would have found something less miserable to do with my life.

Agreed.

I recall, in high school, we were writing a disassembler for a custom weird assembly language which was written by one of the school's graduates a few years prior to that... and we had to use this assembler as a language of choice :) That's high school! And it was quite fun. These days, many CS grads/post-grads know tensorflow and other flashy high level stuff while having very vague understanding of how things actually work at the lowest level (source: interviews).

Another positive aspect of starting off with Scheme was that it leveled the class out, it removed the edge that all the self-taught programmers thought they would have over the people who hadn't really done much programming. Everyone was pretty much equally clueless. Very refreshing.

You make an interesting (unsupported) assertion here. You, who find talking to an IRQ controller, real-time clock, etc. interesting, find Scheme boring, therefore others (who may not share your interests in such details) will also find it boring. Bit of a logical fallacy there...

I've run a lot of surveys of introductory students trying to find what topics are more or less interesting to them. A part of my dissertation was committed to it, actually.

At this point, I'm more or less certain you'll rarely find situations where you have a mass-appealing context. One students' dream context is another students Most Boring Possible. You're probably better off having many diverse contexts and hit all the MUSIC guidelines (eMpower students, Useful to their long/short term goals, make students Successful, make it situationally and domain-based Interesting, and give people opportunities to demonstrate that they Care about each other).

It's interesting as I studied Computer Engineering which focused on the hardware and low level, with some programming on top of that. I was pretty good at that too. However afterwards the Google-style interview algorithm questions do not come naturally for me, and you'd think I'm a complete imposter by the look in some 20-something interviewers eyes, even though have been programming for 20 years...

I feel exactly the same way: Computer Systems Engineering. Took to programming easily, as well as digital. (Not as good in analogue though). Was teaching my tutors programming by the end of first year. Getting asked to hack/ deconstruct software in 2nd.

Would fail miserably in these Google style tests.

I think the difference is that our brains are wired to solve issues from first principles. Some of the best CS I've come across use pattern recognition to determine the best algo to apply to a situation.

The end result is the same code, but we speak different languages until we arrive at the same end. Other design methodologies help give us a better framework for cross communication.

Eg. Voronoi diagrams. Absolutely fantastic way of doing mesh reduction. Took a CS guy to point it out to me ... (I was mostly thru designing my own).

Eg. Same CS would never consider using ASM to save clock cycles.

Recently I had a conversation with someone who has been featured in Kaggle leaderboard(top 1%) telling 'CS background isn't helpful for Machine Learning'.[1]

I believe that he didn't understand what Computer Science actually is, besides having a degree in it. I'd say it's because of the educational system, where one could attain a degree without actually qualifying in it.

In under developed/developing economies if only qualified people get their degrees, then only a fraction would get their jobs and it would be very bad for that economy and so bad educational systems are by design.

[1] https://twitter.com/heavyinfo/status/1209330850363404288

What does he think Computer Science is, and what do you think it is?

> Isn't it amazing how people pass courses, even perhaps demonstrate mastery at a point in time, but manage to get to later courses without fully understanding things?

People remember what they are required to recall (citation needed). Classes can only test for so many things, so people are going to remember what they needed for assignments or tests. It feels like that's one of the reasons apprenticeships are hailed by some as useful. They "test" what is required in real world application. I've never needed to know that 2^10 is a kilobyte as a developer building websites, but would that be surprising/amazing? There are many things I've needed outside of school that were never taught.

As long as CS is used as the path to software development, it will be a balance between theory and application.

Most students approach courses as a form of top-down search with a cache for items they see often. It is generally difficult to get them to reason about subjects from the bottom up.

A smaller proportion of students approach courses from the bottom-up (10-20%?) - they tend to start with the basic pieces and glue them together over time to understand larger concepts.

I’ve read about this phenomenon (it is extensively documented in pedagogic literature) and seen it in action (I taught CS for about ten years) but still could not explain to you why that split occurs.

I would speculate that it is a difference in type-1 vs type-2 reasoning based on the level of familiarity and comfort with the prerequisites to each course, but even that guess is heavily biased by studying constructivism in CS pedagogy.

When I was in college I was very interested in learning computer fundamentals bottom-up, but I had some pripr experience programming a high level language. With that prior knowledge everything made sense to me.

Maybe if I didn't have this prior knowledge back then the classes would be very boring.

Can you link a document discussing this phenomenon or at least give the relevant keyword to search myself? I have noticed something similar when TA'ing, observing my colleagues and also when learning myself.

I can't give you a direct link to such an article, although I can do a bit more and less. Five years I was writing such an article, although sadly I got side-tracked by other activities, I still have the rough outline that I was working on. From there I can give you a list of keywords / some seed articles to read in the area that you can snowball from to find more relevant material.

Keywords: CS1, cognitive approaches, curricular planning, programming, difficulties, learning, novices, programming, teaching, student retention.

Articles: * SIGCSE Bull. A cognitive approach to identifying measurable milestones for programming skill acquisition. http://doi.acm.org/10.1145/1189136.1189185

* IJ of Man-Machine Studies. "Novices and Programming" by Soloway and Spohrer (Book Review). 1993

* Lawrence Erlbaum Associates. Studying the Novice Programmer. 1989 (Soloway, E. and Spohrer, J. C.

* ITiCSE '05. A study of the difficulties of novice programmers. 2005. http://doi.acm.org/10.1145/1067445.1067453

* Using Alice in Overview Courses to Improve Success Rates in Programming I. Johnsgard, Karin and McDonald, James. 10.1109/CSEET.2008.35

* ITiCSE '03. Using lab exams to ensure programming practice in an introductory programming course. http://doi.acm.org/10.1145/961511.961519

* SIGCSE. Constructivism in computer science education. Mordechai Ben-Ari. http://doi.acm.org/10.1145/273133.274308.

* Signs. Epistemological Pluralism: Styles and Voices within the Computer Culture. Turkle, Sherry and Papert, Seymour. 1990. http://www.thinkingcurriculum.com/turklePapert.pdf

Based on your question I would recommend the last two articles as the most interesting. It's been a long time since I read the Turkle article but I recall that it is the most relevant to understanding why we observe this behaviour, and the Ben-Ari article is a comprehensive framework to wrap that understanding within.

Although I never finished the article (fairly typical academic story :) I did write the software / courses that used it and tried it out successfully for five years. I can't give you a link to the software / results for fairly boring reasons to do with IP and confidentiality, but my overall view was that we can build learning experiences that can be successfully accessed by both types of student - but the level of polish and integration that is required to pull it off is about an order of magnitude greater than what is typically invested in undergraduate education. Obviously there is such a huge variation in the effort that goes into individual courses that such an observation is only relevant to a similar institution / student group at a particular point in time.

I think middle-out is superior for learning both bottom and top at same time ;)

Allows much better compression of knowledge :)

>it seems like most students actually know shockingly little

I think that having students take 5-6 classes together in 16 weeks doesn’t promote mastery in any of those classes. Tying the performance in those classes to scholarship eligibility and job placement incentives grades, not necessarily understanding. Grades and mastery can be separated because 2-3 exams in a class, which determines the majority of the grade, rewards students the most, on a time investment vs. performance basis, for understanding technicalities in the grading system and for hyper focusing on the types of problems that can be on an exam. This doesn’t promote mastery, this is a game academia and students play for the satisfaction of government, finance and corporations. Definitely, a problem, solutions could include more frequent sampling of understanding, more diverse ways of measuring knowledge, decoupling performance from financing and longer periods to learn topics.

I’ve been thinking a lot lately about why understanding and mastery is not rewarded in education to the extent some/I believe it should be. My current thinking is that it’s simply not how most people learn, and few systems can withstand pressure from the great majority.

There are interesting exceptions though: take the Putnam math test for instance. It’s taken mostly by math and theoretical physics majors who want to go to grad school in those subjects. The maximum score is 125, and the top scores are typically 115+. The median score however is usually... [wait for it]... zero.

I suspect a lot of grades would have that kind of distribution if they really tested for deep understanding and mastery of the subject.

*kibibyte

Hello, thanks for releasing this! Are there any plans to release chapter 10?

It is written in DocBook, which has become increasingly annoying to publish with and I think is, unfortunately, unmaintained now.

I have been considering some parts on containers and virtualisation which isn't covered at all.

The Itanium and PowerPC examples probably haven't aged well. There is no question that Itanium is a very interesting architecture with many interesting features, but now it is dead it's like deciphering hieroglyphs. I think I have to update these to ARM, or maybe even RISC-V to be more relevant moving forward.

So that would be my plans, as they were :)

I actually think "bottom up" is more of a misnomer than "computer science" as a title for this material, since when I think of "bottom up" I think of things like nand2tetris and Petzold's book. This looks more like "selected topics in operating systems" with some review of computer architecture basics mixed in.

This was really seeded for me when trying to teach people taking computer science courses who were trying to do practical things like integrate C libraries into their higher level projects, but didn't really understand how things were working under the hood and getting themselves into a mess.

If they understood a little more about how their program was built and run ... from the bottom up, as it were :) ... they would have had less pain.

Of course, it just shows as usual the hardest problem in computer science is indeed, naming!

Edit: BTW you're right, "Code" by Petzold should be required reading http://www.charlespetzold.com/code/index.html

Perhaps adding a "Prerequisites" chapter might further help in getting the intended audience across?

I associate "from the bottom up" approach with something being explained by starting from the very basics and aimed towards someone completely unfamiliar with the subject.

Hey, so this is a great work you did. One thing perhaps you can explain... I've stared at this example now for like 30 minutes...

https://www.bottomupcs.com/chapter01.xhtml

Section on "Masking"

How do you get 0x09 or 0x90?

I get how using <memory> & <mask> = <extracted data>...

so:

10100101

11110000

10100000

But I have yet to see how this is 0x90 or 0x09, perhaps I'm misunderstanding. I'm trying to understand the 'shift' piece of it

It’s a typo: he meant 0xa0 or 0x0a and the shift is the four positions to the right to extract the top nybble of the byte.

Awesome, thank you... I thought I was going insane. So you shift 4 times correct?

Thanks, I believe this should be clearer with https://github.com/ianw/bottomupcs/commit/d8dfd3dc6be5795f4b...

Great resource - very detailed and your style is clear and readable. I'd happily recommend this to anybody who is studying an OS course (and in fact emailed a link to some people who teach similar courses to see if they would use it as background reading).

It appears this section might be incomplete:

Branch Prediction

pipeline flush, predict taken, predict not taken, branch delay slots

While not technically all of what's covered in CS, in my experience with a PhD in Comp. Eng., 8 years as an AF comm officer, and 3.5 years in the commercial sector as a soft. eng., this is vastly more useful than most of what's covered in a CS curriculum.

The CS curriculum probably made more sense back in the day when everyone was essentially an embedded developer. But nowadays, the most useful knowledge I have is the low level mechanics of how things like the OS and networking protocols work. S/W eng. classes are a bit useful, but mostly knowing how to write in C++, Java, and now Python has gotten me most of the way. As it is, I have almost never run into a situation where most of my CS classes have been relevant. And, where they are relevant, it can be covered by a week course in the basics.

I feel the CS curriculum would be much better service for students if it covered more of the knowledge of how to get things done. And not in a faddish, framework du jour manner, but there are constant elements throughout all the fads that a good developer should learn cold, and are not covered very well, at least in my 8 years in CS academia.

IMHO the real problem with CS is that it's driven by AI envy, and much of what is considered important only makes sense in light of the assumption the human mind is basically a computer, and CS is all about how to recreate a human mind. However, almost none of that line of thought matters in the real world, and is most likely false.

I'm assuming you have some concrete curriculum in mind, but I'm curious how what you're thinking of compares to something like the learning objectives spelled out in the CS Curricula 2013[0]?

Personally, going through OP's site, I was nodding my head and comparing it to what I learned in my undergraduate CS degree. Some of it is dated, but most of it connects to the Architecture and Operating System classes I took.

[0] https://www.acm.org/binaries/content/assets/education/cs2013...

That would be an engineering program not a science program. 40 years ago there wasn’t much difference but the field has moved on since then! A number of schools have split the tracks, or offer only a computer engineering program.

Could someone elaborate on what they think a good developer should "learn cold"

Linear algebra, discrete math, calculus. The mathematical underpinnings of algorithms and data structures. Turing machines will be a lot more useful once you actually know how to use properties to prove more things. A kindergartner can recite the layman description of an infinitely long tape with ones and zeroes but such simplistic understanding has very little practical use if you don't understand how it fits into the context of CS in general. Machines improve, architectures evolve, frameworks change. But math doesn't. Every few days there is a new "linear algebra for machine learning" guide that pops up on HN and every now and then there will be a "how to learn math" question on HN. The lack of mathematical maturity among software devs and engineers is not a good thing and reflects poorly upon the industry. Too many universities these days focus mostly on practical leet coding rather than the theoretical underpinnings of CS. An in-depth study of the finer aspects of a networking protocol would become outdated the moment the next iteration comes out, but a close examination of Shannon and information theory will serve you well for life. There seems to be a continuous myth that undergraduates cannot code a FizzBuzz to save their lives and thus all focus should be placed on testing that specific skill. This mentality of being dismissive towards math is pernicious to computing as a science and relegating theory as "stuff I never ever needed in my n years in industry" creates a harmful echo chamber for software engineering.

Can you recommend resources that teach what you think the fundamentals should be?

Not OP, and not necessarily endorsing these specific topics as most fundamental to a CS education (I've more often drawn on discrete math/symbolic logic) but 3Blue1Brown has great series on introductory linear algebra and calculus. And Symbols, Signals, and Noise: An Introduction to Information Theory by John Pierce is also good.

My own view echoes this (https://meaningness.com/metablog/how-to-think), which is that it's often useful to know a little about a lot of different kinds of math. That way you'll set yourself up to notice when and where some specific discipline might apply, then you can go back and learn the details if you need to.

I'm not saying these aren't important but for most developers this stuff is rarely going to be used. Most "developer" jobs are not math heavy. I'd rather push someone to learn how to write clean code and focus more on the engineering aspect.

Yes, this is what I'm referring to. Math and algorithms rarely, if every, show up in my work beyond basics that don't require more than a week or two of information.

Agreed, the typical CS education does not equip students to become useful programmers. I don't think AI has much to do with its failings, though. Universities like to think they are training up scientists.

It is much easier to teach an engineer to make good software than to teach a CSist to do engineering. I have seen the latter happen, but the usual results are... well, we see that every day.

> the CS curriculum

There is no 'the' CS curriculum. You must be thinking of one particular school's CS curriculum, like maybe your own? Another school's CS curriculum is going to be wildly different.

Most CS curricula I've seen have commonality, at least in the US and UK, with a significant focus on math, algorithms, datastructures, and so on. A lot is interesting, but most is useless for normal work. I think it all should be kept, but the curricula should also be designed with the fact that most students will not become CS researchers, and will have normal programming jobs.

A curricula, OTOH, that prepares a student to be a good developer should also have a heavy emphasis on: - #1 is write a lot of code with a focus on good coding practice, preferably in a combination of Python and Java or C++ - Understand Linux and be proficient with command line tools

Here’s a slightly different take: The Secret Life of Programs (https://nostarch.com/foundationsofcomp ). It starts with a practical set of things and then ends with some survey overviews for people who want to know more.

A complement, not really an alternative, to this pdf.

(I fumble fingered this the first time and left out the link! Unfortunately I can't delete the confusing comment but fortunately it is being downvoted away)

This seems more for OS fundamentals than full-on CS, still good, though.

Previous discussions:

https://news.ycombinator.com/item?id=13249675

https://news.ycombinator.com/item?id=7611093

Seems an excellent place to mention http://linuxfromscratch.org/

Related: nand2tetris: https://www.nand2tetris.org/.

"This site supports a course and a textbook that guide students and self-learners through the construction of a modern, full-scale computer system - hardware and software - from the ground up."

> "This bit is crap" (https://www.bottomupcs.com/chapter02.xhtml under "Reordering")

Might want to proofread some of this and remove the ... proof-reading notes? Not sure what you thought was crap about this section?

I think in my mind at the time I was comparing it to Hennessy and Patterson; something that is obviously playing a in a completely different league!

Over time I have become a bit more realistic :) I've stopped worrying if it's better or worse than anything else. As long as it's factually correct, I think a rising tide floats all boats so the more we all write and read others work, the better off we'll be.

Looks like a decent resource for Unix OS / system programming, but it's definitely not computer science.

Agreed. I don't see how you can leave out (among other things) databases, Big O notation, networking, and call it a computer science primer. Good for what it is, but misnamed.

This is great. It covers a pretty wide range of stuff one is presumed to know and allows for both a big picture view and sufficient detail for some "hole-filling" and connection between ideas. I would consider this an interesting lecture series.

Does anyone know if there's a book like this? Basically intro to OS but conceptual stuff only - for someone who didn't take it in school and wants to learn the high level details, not to the level normally covered in a college course.

Computer Systems - a Programmer's Perspective

I have this favorited/bookmarked for the foreseeable future. Thank you for working on this (I hope it's still an active project if readers point out discrepancies)

Not very good to be honest. Nothing about schedulers, bootstrap, and most of it is very general information. it doesn't give actual clear picture how everything comes together, and it is very system specifics (unix). CS should be agnostic to any system architecture. You do cover binary , but the more fundamental question what is the foundation of binary mathematics. It goes back to Turing machine, and how transistors are built and how you compose them into bigger units, and then you talk about CPU architecture, the adder, multiplexer, the PLU, etc.

Can you recommend one or more resources that you think do a better job achieving a bottom up approach to CS?

This looks like a great resource. I wish I had it for my OS class.

Here’s a slightly different take: starts with a practical set of things and then ends with some survey overviews for people who want to know more.

A complement, not really an alternative, to this pdf.

Call it Information industry corners from bottom up.

I remember reading this a few years back.

I stopped reading at some point because there were so many errors, unfinished bits, and just flat-out garbage.

Sorry to the author but this needs to improve. It's a good start, but you need to invite fixes and implement them. Put your email address on every single page and invite fixes and then implement them.

This could be an awesome resource, but right now it's too full of errors to be useful.

Nobody should be recommending this. Nobody who had actually reviewed it all would recommend it.

Everyone who tries to create something eventually comes up against being told their work is flat-out garbage. Unfortunately I don't think there is a vaccination for it, and one must just take their chances and hope to build a mental immunity so it doesn't ruin your day. It's sad to say that many don't develop a resistance, and I think we lose many good contributors that way.

It's always good to take constructive criticism but when the negative commenter contributes little of worth, both in the comment and to the wider community, I think it is safe to ignore.

Thanks for sharing

As has been said before: ignore the boos. They usually come from the cheap seats.

Reply on news.ycombinator.com