Hacker News new | comments | show | ask | jobs | submit login
Computer Science from the Bottom Up (2013) (bottomupcs.com)
516 points by Chesco_ on Dec 24, 2016 | hide | past | web | favorite | 156 comments



Thanks, I wrote this!

It was a bit of a different time, when docbook was the way to publish, when Itanium was the 64-bit architecture, things like go and rust didn't exist and we used bitkeeper. But most of it is still relevant, and despite acquiring 2 kids since I started still have some ideas.

Yes yes, it's not Alan Turing-esque computer science. I have taught algorithms and data structures courses as well as operating systems courses to "computer science" students and this is more the second obviously. You gotta know both!

All I can say is that being a professional now for some time, anyone who knows this stuff is welcome in my team, no matter if we're bit banging hardware or writing JavaScript. When you have some concept of what's happing underneath, you write better code and, more importantly, are a better debugger.

I'm mostly cloud-y devops-y these days ... But when your CI triggers a kernel panic or a crash in some low level libray, it's nice to be able to go digging and send a patch upstream to fix it :)


Just as idle inquiry about the "CS" term, do you think the name "Computer science" would still apply (and did it always apply) to things such as CPU and OS architectures, the toolchain, etc - basically the subject of your e-book?

I am under the impression that there's a distinction between "Computer Science", which is algorithm and data structure design and analysis, and "Computer Engineering" which is basically everything else, from the hardware level up.

Or is this mostly a European distinction?

Because my friends who do "real CS" at various universities generally avoid anything which has to do with hardware and practical operating systems, and are basically mathematicians working on problems relatable to computers - their language of choice is TeX, not C. More like Turing instead of Torvalds.


I'm not the OP, but have spent more than my share in CS departments in the US. :) I think it's more of a EU/US distinction.

In the US, CS departments typically include both the theory (of computation, algorithms, data structures, complexity, etc) as well as a healthy dose of applied CS, which then divides up into: systems (operating systems, networking, etc), applications (scientific computing, AI, etc), interfaces (graphics, HCI, etc) and a number of other ones depending on the department.

This topic definitely fits into intro-level material in a systems division of a CS department in the US. In comparison, US "computer engineering" tends to include much more emphasis on the hardware (including CPU design, circuits design, etc) and overlaps with CS in low-level aspects of systems. How about it?


Not the OP, but from skimming the ToC, about 90% of the topics covered are taught in undegrad courses required for graduation for my CS degree.

> Because my friends who do "real CS" at various universities generally avoid anything which has to do with hardware and practical operating systems, and are basically mathematicians working on problems relatable to computers

Are they in grad school / doing research? Maybe they're just specializing in those areas (I think it's called theoretical CS).


In Denmark, or at least on University of Copenhagen, it's a mixture. Many courses introduce the math and the programming paradigm together, and have exercises in both. I think that works out well, as it you can see how to apply the theory in practice as you learn it.


I studied CS at Utrecht University in the Netherlands, and there the 'C' stood for 'computational' or 'computing' science, which always made sense to me.

I still know very little about how a computer works on a hardware/low level, but I do know about how the calculations are being done from a higher level.


I've been looking for something like this for awhile now. I'm a very 'bottom-up' learner. Thank you.


It's not often you brush up against someone whose work you read and enjoyed. Thanks for what you wrote. It helped me become a better programmer.


I've been rattling this idea around in my head and, although it may sound crazy, I think C is a little high level to start an adult out on.

I know many people won't agree with this but all of the people I admire in the world of CS and everyone who is a true scottsman for all intents and purposes loves dipping down to a lower level once and a while. I think the best way to learn about computer science it to program for a machine so simple anyone can understand how every bit works. No magic.

One such example of this is old retro computers. Systems like old Z80 machines. If I wanted to teach everyone how to be an amazing programmer I'd start them out on an old broken computer, help them fix it and get it working, help them get programming and wet their feet copying in some hex values to get some binaries programs working, start them up with a notebook and give them "homework" of a few really useful routines to write for themselves in Assembly. They'd write the assembly and compile it with pen and paper so ther really understand what's going on. Then we'd write an assembler together, then from an assembler we'd write up a standard library, then from there we'd get to a compiler for a language they make up. After that the sky is the limit. Maybe help them start writing their own ROMs for the machines and see where they can take it. (Maybe 6 months to 1 year)

If someone was able to get through that they'd really, truely, understand everything in the computer. Funnily enough that's what most of my CS education feels like right now (except much less fun and I'm learning less then I would from this). Intersplice these sessions of training with lectures of computer architecture, basics of electronics, how each of the components in the computer works, different protocalls and why they are used. You'd be very well rounded and pretty much well suited for many programming jobs. Follow this up with a slow maybe 5 week transition period where you come back to a modern computer, learn some C and why C was made, learn some LISP was made, and then apply that to real world projects while only introducing new technologies and concepts only when they are of imediate use and then allow the student to learn directly from taking advantage of the benifits of these technologies.

I think a student would come out very well rounded from something like this. I wish I could pay for an education like this.


Computer science is not about computers; where does stuff like algorithms fit into this?

What is a "true scottsman" of CS? Low level programmers? What about people that have pioneered the theory of computer science? The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.?

I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute.

Increasingly today the underlying architecture, for most intents, is becoming irrelevant (to first order of magnitude). The biggest gains are not made from superoptimizing compilers, but from algorithmic efficiency. That doesn't figure anywhere in your curriculum.

I think your curriculum would be great as an intro to computer architecture, or even as a series covering the topic, but I don't think it's an adequate introduction to computer science.


Maybe I am too old, but from my vantage point, "Computer Science" and "Algorithmic Science" are really two entirely separate fields.

Computer Science is exactly what the OP talks about: computers, CPUs, implementation details, hardware, plumbing, etc... One needs actual hardware on the table to work this out. Imperfect hardware, with latencies, clock issues, etc... THAT is true computer science, IMHO, and is very near Electrical Engineering.

On the other hand, Algorithmic Science really is an applied form of mathematics. One does not actually _need_ a computer to design, understand, invent algorithms. A brain, paper and pen are enough.

Those are two different sciences, and I suspect very few people are actually great (world class) in both simultaneously. It is futile to imagine that a single school curriculum would adequately form people in those two very different topics.

I could add that where I work, we have in-house the two kinds of people: a couple of mathematicians for the (amazing algorithms) and a few very picky low-level programmers who actually implement the algorithms with blazing fast, hand-crafted code. The two groups would never dream of doing the other's job.


Science is the pursuit of truth, whereas engineering is the art of balancing resources and time to achieve a concrete goal (like a product). In that sense, Computer Science is the pursuit of observing, classifying, and predicting of computation phenomena, whereas Computer Engineering is the actual practical matter of building things that take advantage of computation phenomena.


Best distinction so far.


> Computer Science is exactly what the OP talks about: computers, CPUs, implementation details, hardware, plumbing, etc... One needs actual hardware on the table to work this out. Imperfect hardware, with latencies, clock issues, etc... THAT is true computer science, IMHO, and is very near Electrical Engineering.

It really depends on what sources you base your concepts on. I would say that, for instance, what you mention is more closely related to "computer engineering" than "computer science".

For instance, in [0]: "Thus CS is closer to the underlying theory of computation, with its roots in mathematics, and CEN is closer to the design of physical devices (...) Of the three great divisions in computing, namely theory, software and hardware, to a first approximation theory goes with CS, hardware with CEN, and software with both (...)"

In my country, our technical schools and most universities provide what we call "informatics engineering" (engenharia informática), which has a bit of CS (in terms of basic concepts, algorithms, abstract data types, etc.), CE (some low level electronic stuff) and Software Engineering (Programming, OOP, Web Programming, Logic/functional programming, etc.).

[0] http://www.eng.buffalo.edu/undergrad/academics/degrees/cs-vs...


Computer science is as much about computers as astronomy is about telescopes https://en.wikiquote.org/wiki/Computer_science


Yes and no. The difference with computing the design of the physical hardware influences the design of the programs that are written for it. If the astronomy analogy fully applied then the design of the telescope would influence the design of the universe.


Telescopes influence what you can see they do not influence the stars.


Computer design can't influance what you see but what you can implement.

If computers still only had 512bytes of memory we'd be writing programs different then today making a trade off of computation speed for ram size.

If CPUs didn't have pipelines then parallelized algorithms wouldn't be as important and I feel that mutli-CPU machines would have taken off to make room for other forms of parallelization.

As the GP says, Galileo's telescope didn't make the universe smaller or larger, it just let him see things in that universe. Nothing changed but what he was holding.


You are missing the point. No doubt the Hubble telescope shows much more than what Galileo had available in XVII century. New instruments enables discovery. But the science is not about the instruments.


> Computer Science is exactly what the OP talks about: computers, CPUs, implementation details, hardware, plumbing, etc... One needs actual hardware on the table to work this out. Imperfect hardware, with latencies, clock issues, etc... THAT is true computer science, IMHO, and is very near Electrical Engineering.

This is typically called Computer Engineering in curricula.

Computer Science is all about the "Science" of Computing, hence its focus on algorithms, computability, etc.

What's missing is actually Programming. "Software Engineering" tends to focus on project management; "Computer Science" is about modeling computing and not programming; "Computer Engineering" is about how the hardware works, not how to use it...

Programming well still tends to be tribal knowledge, apprenticeship, and craft.


In my native country, computer science is called "informatics" [1], a term which I've always liked but which hasn't quite gained a foothold in the US. It covers everything from complexity theory to algorithms, but is focused on science, not engineering.

[1] https://en.m.wikipedia.org/wiki/Informatics


I was using today's nomenclature, where computer engineering refers to the low level architecture stuff, and computer science to the higher level things.


> What about people that have pioneered the theory of computer science? The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.?

> I doubt these people know the inner workings of computers

...wha...? This is so ridiculous of a claim that I can't even think of how to respond...


Why is it ridiculous? All that I named are theoretical computer scientists. They certainly have the ability to learn about the intricacies of computer architecture, but I highly doubt they know, for instance, how a multiplexer works in hardware.

This is my impression from my interactions with some of them.


> Why is it ridiculous?

I've explained here: https://news.ycombinator.com/item?id=13252108


>> I doubt these people know the inner workings of computers

> ...wha...? This is so ridiculous of a claim that I can't even think of how to respond...

GP probably means that while these pioneers might be aware of, might have tinkered with the nuances of processor design and syscalls and nitty-gritty details of TLB's and interrupts and stuff that, say, a kernel-level or SSD firmware guy might deal with regularly, it's highly unlikely that they would know their way around these like they know their way around the algorithms that they deal with on a regular basis, which exist at a much higher level of abstraction.

Take everything with a grain of salt.


> GP probably means that while these pioneers might be aware of, might have tinkered with the nuances of processor design and syscalls and nitty-gritty details of TLB's and interrupts and stuff that, say, a kernel-level or SSD firmware guy might deal with regularly, it's highly unlikely that they would know their way around these like they know their way around the algorithms that they deal with on a regular basis, which exist at a much higher level of abstraction.

I think you missed my point. What I'm saying is there's a world of difference between "X knows B better than A" and "X doesn't know A [very well]". When you're talking about world-class experts who are at the forefront of research in their fields, if you work in the same discipline, there's a pretty damn good chance they're more of an expert at your work area than you are. (I'm obviously assuming "you" here are not the world-class expert in your area. "You" are just a generic but respectable engineer in your area of work.)

I think what you (& the OP) need to realize is that there's a HUGE and crucial difference between being, say, "rusty" on something (e.g. because you're not doing it on a day-to-day basis, or because it's someone else's system and obviously you can't magically know how it was designed a priori), and not having enough prior expertise such that your ramp-up time would be low enough to be negligible, should you ever need to touch that thing at some point. You need to realize, these folks have done so much work that they even get rusty on their own research topics after a few years. That doesn't mean they stop being experts on their topics. On top of that, they still keep up with their colleagues' research in other related areas... which, mind you, are likely to be more advanced than what you're doing. Chances are if they spent a day or two reviewing other stuff, they'd be as good (or even better) experts on them than they were originally, quite likely better than you (again, generic "you" here, as above).


It sounds like you hold researchers in the highest regard and believe everyone should too.


There's a difference between a researcher and an expert.

I'm a researcher and particularly I'm an undergrad assistant to people who do important things. EWD was an expert. I know a little about computer science and am still learning. EWD knew everything there was to know at that time and was teaching.

That's what an expert is. The pinical of the field's knowladge accumulated into one person. You don't earn the title Expert from a degree. You don't earn it by any means from years of experiance. You earn the title Expert by consistantly blowing the minds of everyone else in your field and by consistantly pushing your field forward further then your peers.


> It sounds like you hold researchers in the highest regard and believe everyone should too.

Nice strawman. Where did I ever generically talk about "researchers"? Are these people mentioned (Karp, Valiant, etc.) just merely "researchers" to you? You really think I have the same regard for (say) a random grad student as I do for someone like Karp? And you really think I don't have the same respect for the best people working on corporate/commercial technology (Musk, Page, etc. just as a couple of examples off the top of my head)? It seems like you really have low opinions of all researchers no matter how accomplished they are, in which case that would explain everything, but I certainly don't. Otherwise it's like you're actively trying to waste my time and miss my point...


To be clearer, I should have included "these researchers".

I don't have a low opinion of researchers.


Advances in algorithms are a fundamental starting point, but I think it's a common mistake to conflate the efficiency of an algorithm in the abstract sense to how those benefits are manifested in the applied sense. While true, all things held equal a new algorithm will advance the field, providing "gains" as you said, but it's false to assume that algorithms are more important than understand computer architecture, full stop.

A simple example is dijkstra's algorithm vs bellman ford. Sure, in the abstract sense, the greed algorithm wins. However, it would be wrong to assume that dijkstra's algorithm is faster than bellman ford, because it's not. That's because dijkastra's algorithm doesn't parallelize as well, where as bellman ford parallelizes very well (and by "well" I mean it exploits the architecture - in a sense has "mechanical sympathy"). You end up creating very exotic data structures that are good for caching and stealing work from unused threads. There are many other examples, check out matrix matrix multiplication if your interested.

I'm not making the argument that one is more important than the other, but I think it's a bit reductive to say algorithm only matter because there are so many examples of where computer architecture matters more (and vice versa).

Another way to say what I mean is that ultimately reality matters.

> The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.? I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute.

Um, why would you think that they don't understand the inner workings of computers? Is that just your intuition or is that based on some practical knowledge? I'm not saying I know the answer (I haven't quizzed them), but since we're guessing here I'm going to say that they probably know a lot about the inner workings of computer - and there's no harm in us mortals trying to do the same. They probably don't know like specific things about how intel's branch prediction works or anything like that, but as a general concept, the inner workings of computers is pretty fundamental stuff and is very helpful to know, along with algorithms.


>> The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.? I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute.

>Um, why would you think that they don't understand the inner workings of computers?

Yes, great point. I know of at least one person who seems to straddle both those worlds - Jon Bentley:

https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientis...

He wrote Programming Pearls, More Programming Pearls, and Writing Efficient Programs. I own copies of either two or all three of those, and have read good amounts of the first two, and pretty close to the whole of the third (some years ago), which is out of print. A fantastic book (the first two are too).

And the point here is that in the Efficient programs book, he goes into a lot of detail on performance improvement at the lower levels too, not just at the level of algorithms, though he covers that some too. And he has also invented algorithms (e.g. the Bentley–Ottmann algorithm). So he is an example that one can do/be both high-level and low-level.

And of course, many more people do that, at a lower level of accomplishment (but still non-trivial), such as working with low-level languages (C, assembly) and doing perf tuning, as well as creating or improving algorithms and data structures for their work, high-level software design/architecture, etc.


Studying algorithms is independent from solving that problem practically; we know plenty of problems having an optimal solution that is impractical, and a "less-efficient" algorithm that is much more practical.

This doesn't make the study of algorithms any less important. Thankfully, the initial study of algorithms (basic stuff like greedy and dynamic algorithms, etc) usually doesn't cover impractical algorithms, which makes it appropriate for new students.

From my interactions with some of the names I mentioned, as well as from my (short) experience in the TCS community, I do not think it likely that many theoretical computer scientists remember what they learned in computer architecture class.

I agree that it is useful to learn it; I was pushing back in the idea that learning architecture at the expense of the rest of computer science is a good thing.


>common mistake to conflate the efficiency of an algorithm in the abstract sense to how those benefits are manifested in the applied sense

> While true, all things held equal a new algorithm will advance the field, providing "gains" as you said

> but it's false to assume that algorithms are more important than understand computer architecture, full stop

I wish there were two like buttons. I have nothing to add that you haven't said better then I could have.


Studying algorithms is independent from solving that problem practically; we know plenty of problems having an optimal solution that is impractical, and a "less-efficient" algorithm that is much more practical.

This doesn't make the study of algorithms any less important. Thankfully, the initial study of algorithms (basic stuff like greedy and dynamic algorithms, etc) usually doesn't cover impractical algorithms, which makes it appropriate for new students.

From my interactions with some of the names I mentioned, as well as from my (short) experience in the TCS community, I do not think it likely that many theoretical computer scientists remember what they learned in computer architecture class.

I agree that it is useful to learn it; I was pushing back in the idea that learning architecture at the expense of the rest of computer science is a good idea.


> Increasingly today the underlying architecture, for most intents, is becoming irrelevant

... amidst cries from a handful of lunatics who insist we shouldn't be using linked lists any more because they don't use the L1 cache very well compared to arrays.


In some contexts this optimizations make no sense. In others you'd be laughed out of the office for suggesting that you should use a linked list. You'd be shitcanned before you got back to your office.

In the same sense if you're in a python shop doing web development and you say "EVERYONE we need to STOP using python and write ALL of our HTTP code in C! We'll be able to optimize the hell out of it and probably save 10K of memory per request! That's HUGE!" you would also in tern be shitcanned before you finished the sentence.

If you take that same exact mentality and bring it to a company that builds realtime systems that do DSP and maybe even handle some user interaction in an embeded form facter and you say "EVERYONE! I've found that if we replace our current memory allocator with a circular buffer and pre-allocate everything in an SRAM we can get power-off tolerance AND allow ourselves to make use of all of our memory while not even needing to WASTE the cyles on freeing our memory! We'll save on the oders of 1ms over 50actions! That's a HUGE boon for our batter life!" you'd walk out the head of the office. Saving 500ns, 100 bytes, or even improving something on that scale no matter what it is in contect is huge.

The problem boils down to one thing. For the embeded systems people saving 1MS may be on the oder of 20% of their runtime. For the python shop saving 10K of memory is probably on the oder of sub-00.001% of their memory usage.

It is all about context.

(Disclaimer: I have changed from LL to arrays in some applications because it made a measurable improvement to the speeds of my systems.)


Yep. Totally.

Also, if you're working in an HLL, know how LL is implemented in your PL. Because even in Lisp, not all LLs are created equal, and even if you create them the same way, they don't necessarily have the same perf characteristics.

For instance, because Haskell, ML, and the other functional languages don't allow datastructure mutation, they can CDR-code all their lists, something Lisp does as well (which is why list literals created with QUOTE cannot be modified, IIRC). This collpses the linked list structure into something resembling an array, increasing cache response time. Additional conses will be allocated separately, but this will still increase efficiency.


Software is an inverted pyramid, most programmers don't need to know the low-level bits. However if you don't have at least someone to hold up the lower layers of the pyramid then everything falls over.

Performance and memory is one of those weird things where it doesn't matter until it does, and then it really matters. I can't count the number of projects I've been on where there wasn't a way to "scale" out, we had fixed resources and the only path forward was deep low level optimizations.


Errrr, how is this lunacy? Seems like something everyone should be aware of.


It is, but if you're, say, writing a small-scale webapp or some other app that's disk-bound (99% of all applications), it's probably not something you'll have to worry about.


Right but what's the reason not to pick a data structure with better performance? This should be a really trivial choice with virtually 0 impact on code since a list and array will have nearly if not entirely the same interface.

I would also challenge that 99% of all applications are disk bound but I think it's really besides the point. Really, the argument is that performance doesn't matter in all situations, which is true, but hardly means that we should be against writing fast software.


Of course. But OTOH, we shouldn't immidiately discount LLs when writing code, just because the perf isn't optimal.

>but hardly means that we should be against writing fast software.

On the contrary.

Lisp is slow. Python is slow. Ruby is slow. Smalltalk is slow. What do these languages have in common? Dynamism. They trade speed for other that were, in the language designer's opinion, equally or more important than being fast.

The point is, that when you make a decision about performance, the decision has consequences in either direction. LLs are slow, but they have a lot of advantages. With skip lists you can get decent access tumes on ordered LLs, and in some contexts even O(n) is acceptable. But what LLs do better than other list structures like arrays is insertion. With an array, you get best-case O(1) appends, but all other types of insertion are O(n), and even appends can be O(n) if you run out of space and have to reallocate.

By contrast, provided you have a pointer to the location in the LL that you want to insert at (which is why most LL uses in applications like to insert at the head of the list), LL insertion is guaranteed O(1). That's sometimes useful.


> Of course. But OTOH, we shouldn't immidiately discount LLs when writing code, just because the perf isn't optimal.

Most of the time you should, I'd say. Regardless, the decision should be very natural/ trivial for any developer - understanding the performance attributes of the most common data structures is not asking too much of developers.

> They trade speed for other that were, in the language designer's opinion, equally or more important than being fast.

Yes, of course. I am not advocating for highly tuned software - I've stated as much in the last post. There are often tradeoffs.

No one is arguing that a linked list is not more algorithmically efficient at certain things. What I will say is that Vectors still end up faster for most operations, and it shouldn't be hard for a developer to determine when those situations arise.

I am not arguing against LL. I am just saying that it isn't 'lunacy' to understand basic performance characteristics of your software. Your post essentially came off, at least to me, as "people are crazy for wanting ot use a more efficient data structure".


>I am not arguing against LL. I am just saying that it isn't 'lunacy' to understand basic performance characteristics of your software.

It's not: it's very important.

>Your post essentially came off, at least to me, as "people are crazy for wanting ot use a more efficient data structure".

My point was more that people aren't necessarily crazy for using an LL. I don't, however, think that anybody is crazy for choosing not to use one for perf reasons.

I guess what I'm saying is that AFAICT, we're entirely in agreement, and I have no idea why we thought we weren't.


I wouldn't say it is the dynamism as much as the lack of control. Specifically, if you write your code non idiomatically and control all allocations, the languages probably gain a lot on speed. Unless you need inline assembly. Some lisps allow this.

I find that taking these lessons to database access patterns helps a lot. Know your data access, and the data structure design has meaningful discourse. Don't know your access patterns? You are unable to pick the best one. Period.


>Know your data access, and the data structure design has meaningful discourse. Don't know your access patterns? You are unable to pick the best one. Period.

Pretty much: if you don't know the access patterns, draw up a naive implementation so you can figure them out.

This is actually connected to one of the disadvantages of Lisp: because Lisp makes it so easy to draw up a naive datastructure based on LLs, it can take some effort to rip all that out and make something actually fast in its place.

>I wouldn't say it is the dynamism as much as the lack of control.

Don't undereatimate the cost of runtime dynamism. Lisp compilers have gotten pretty good at avoiding implementing it when possible, but there are pretty tight limits on how far you can go with that sort of optimization.

Essentially, every time you call a CLOS method, or you use eval, or you in any way introspect on your runtime state, or create the possibility for your code to do so at runtime, the code you are writing becomes more costly to run.


I am in complete agreement that lisp makes it possible to write slower programs. I just challenge that it is an inherently slower language.

I view it as reducing the coefficient of writing a program. This means more will be made. So more slower ones will get made.

However, nothing prevents you from writing a fast program in that language. Other than the slower successes.


With a compiler smart enough to aggressively cull any uneeded dynamism, it might be possible. But it would still be hard.


A pragmatic view, perhaps, is that as a tool, a given Lisp environment doesn't constraint how fast a solution we can devise to a problem in some manner. That really fast solution might not simply be a Lisp program fed to the Lisp compiler.

Suppose you're required to solve a problem with very high performance, and it has to be expressed in some high level language. No high level language achieves it using any straightforward code without dropping to assembly language. Not C, nothing.

In that situation, I'd arm myself with Lisp, because the problem basically requires inventing some specialized fast language and mapping it to the machine at hand.


So a custom Assembler using CL as a macro language? That works.



If you don't know the access patterns, you can't pick the best representation if the prioritized list of criteria determining "best" begins with access speed. If the list begins with something else, you may still be able to pick the best one.


Fair. And yes, I was assuming "best" as in the fastest or most predictably bounded.

I did not think I was stating anything profound.


You need both.


I agree, and the good computer science programs take this approach.


Theory is useless without implementation and implementation is nothing without an understanding of theory. Implementation and theory are in lockstep but by learning theory you will not necessarily know how to implement, or even really understand, the topics you have memorized. On the other hand it is necessitated by the concept of implementation that you on one hand understand the tools you are using to solve this problem and on the other have reached a point where you see why the tool is used.

You can sit a person in front of a whiteboard all you want. Brainwash them about arrays, maps, matricies, trees and graphs and they have a high likely hood of coming out knowing nothing but verbatum what you have told them. Conversly you cannot sit a person in front of a computer, guide them through the exercises that I described, and expect the same as the student who once sat in front of the whiteboard.

Trees grow from seeds and the best way to plant these seeds are not with an expo marker but, in my opinion, by bringing the student to a crossroads where they need to discover a concept on their own. This is a common tactic in game design: allow the player to discover new rules after you've taught them the basic foundation.

After they understand the basic foundation of how they will be interacting with the machine I think that, with the guidance of the correct assignements in the notebook codesegment phase of the program, the student will be able to create these different routines and ideas on their own.

Some such examples I will provide below:

   - Make some way that will allow you to find a number between two possitions in memory
   - Make a wrapper for this routine that will operate from a starting possition and an offset of the size
   - Make a way to find the distance between two points on an X, Y plane
   - Find a way to apply the same transformation in every item between two points in memory
   - Find a way to implement a way of storing data about an X, Y plane. For instance where a dot is on a section of graph paper
   - Make a subroutine that will allow you to store potentially infinite items in a collection. There are many ways to approch this but the three main ones are to: use a section of memory that is preallocated and reallocated when it is filled, make some way to daisy chain items of the list together possibly by wrapping them in in more data that will serve to aid your program, do the same as the daisy chain but allow the chain to coninue in more then one direction. Hint: this will probably need an init_<structure>, add_<structure>, remove_<structure>, free_<structure> 

This would take a long time but under the correct stimulating guidance the student will be able to seek out why they need these tools. These tasks should be presented after they've completed a project that someone in our position knows that the optimal way of solving the problem was not choosen and a more abstract and simple solution exists. These situations will present themselves often. I've possitioned myself to make these suggestions to my peers at my university who are having a very difficult time passing the classes we are in together. The people who need to see why AND how.

I'll look at their work and say "how about try using X method of solving the problem and show me what you come up with" and when they come up with a solution I say "now try and make it a library. Remove it from your current solution and allow yourself to use it for further work on other projects".

This changes the way they think about programing.


> Theory is useless without implementation and implementation is nothing without an understanding of theory.

I feel that you greatly misunderstand why theory is important. It is not just something to be memorized to aid in implementation. It is useful and interesting in its own rite. CS Theory is Mathematics and like mathematics can be pursued simply with the goal of better understanding.

An understanding of Turing Machines and computability is a good example for this. Generally knowing that there exist uncomputable functions is of little practical use as you are exceeding unlikely to encounter one in implementation. Similarly understanding turing machines well is not useful as they compute in a very different way compared to current computers. However, from a purely theoretical standpoint it is critical to know that there exist uncomputable functions.

> You can sit a person in front of a whiteboard all you want. Brainwash them about arrays, maps, matricies, trees and graphs and they have a high likely hood of coming out knowing nothing but verbatum what you have told them

The same could be said for teaching implementation. Thoughtless memorization is rarely useful in any field. You can instead have them discover the theory like they would discover an understanding of implementation you advise.

Much of the theory of CS is not particularly hard to work out yourself if you are given the right hints. For example, an approach to teaching sorting algorithms could start by asking students to devise an algorithm to sort a list, and then have them compare algorithms and devise a way to evaluate which ones are the best and in which ways. Then after their progress slows introduce ideas like big O to help them further develop their ideas. The sorts taught in introductory algorithms classes are not very hard to understand (or design), and with the idea of big O in hand the introductory analysis in within reach of the student.

However, I agree that teaching programming in general from learning the rules to interact with tyeh computer and building up abstraction is often the right path for many students. Personally, it was not a great start for me (I started with C; not exactly the lowest level, but lower than most CS courses nowadays). I would have preferred to learn more theory earlier in my learning, and that is not easy to do when you are focused only on the code and not on the ideas behind the code that are universal.


> feel that you greatly misunderstand why theory is important. It is not just something to be memorized to aid in implementation. It is useful and interesting in its own rite. CS Theory is Mathematics and like mathematics can be pursued simply with the goal of better understanding.

I don't think you understand what I mean. I don't mean the theory isn't important. Nor do I feel that the only thing important is the theory.

What I do feel is this: - If you're teaching someone something they don't care about yet and wont remember, it's useless - If you're learning theory before running into WHY you need that theory then you by definition don't care

Our field should be about hiding the unimportant abstraction for the time being and it shouldn't be able shoving it in your face and saying "you'll need this in 3 years when we get to graphs".

No one will remember that. I have a hard time remembering every single "important algorithm". Do you think I could write a radix sort off the top of my head with no prep time? What about something easier like a merge sort? No. I don't care because my job isn't writing sorts. Most of the time using the built in language sorting function is ok. If I need to write one I choose based on the language I'm using and task by sitting down, thinking through my past experiances and what I used them (like not using a radix for floats/strings and instead using a merged quicksort). After I find one that'll work like it has in the past I google for that and reimplement the algorithm.

There are hundreds and thousands of ideas that I need to keep in my head when programming of which sorting is one of the least important ones.

> The same could be said for teaching implementation. Thoughtless memorization is rarely useful in any field. You can instead have them discover the theory like they would discover an understanding of implementation you advise.

The entier point of my post is to say we shouldn't do that. We should give them a task that they will want to acomplish and like every good task you take one too many cakes from a stranger and fall into a rabit hole of other problems. You can go from

   - I need a script to manage this deamon
   - Now I want logs parsing and a way to run analytics on them
   - Ok now I want to run realtime events triggered by these log lines
   - One of those needs to be a SMS service, let me go write that
And that goes on and on and on and on until you run into every problem in the book a software developer runs into.

Feature creep, undocumented code, bad styles, slow performance due to features, breaking changes, why a dev enviroment is important.

Programming is a small part of being a programmer.

> Much of the theory of CS is not particularly hard to work out yourself if you are given the right hints

That's exactly how I feel.

> Personally, it was not a great start for me (I started with C; not exactly the lowest level, but lower than most CS courses nowadays).

C has many problems that are not present in far lower levels in the stack. In assembly you can do anything any way. You don't need to care. You have a magical way to save the contents of a register and get it bad, to go to a subroutine, and a massive set of "pre-defined functions" (instructions).

On older, simpler, systems this was even less of a problem. For instance a Z80 machine has huge advantages one such being the amazing instruction set and extremely simple features.

> I would have preferred to learn more theory earlier in my learning, and that is not easy to do when you are focused only on the code and not on the ideas behind the code that are universal

The theory should come as you get stuck, not before. The act of getting stuck and then pulled out of the hole is what teaches you when something is meant to come in handy.

One such example is when your car battery dies. You probably don't have one of those self-jumping battery packs in your car but they come in handy. You only ever see why after your battery goes flat and you cant find anyone to give you a jump.


> If you're learning theory before running into WHY you need that theory then you by definition don't care

My point is that there does not need to be a need for the theory. Learning for the sake of knowledge is enough. If you don't care about that reason though, learning much of theory will be hard unless you have a more concrete reason (a need for the theory in practice).

> Do you think I could write a radix sort off the top of my head with no prep time? What about something easier like a merge sort? No. I don't care because my job isn't writing sorts.

I think pretty much all programmers should be able to write a merge sort off the top of their heads. At its core mergesort is really just `merge(mergesort(leftside),mergesort(rightside))` which should not be hard to remember and writing the splitting of the list and merge is something any decent programmer should be able to do.

I will give a pass on radix sort though, it is a little more complicated and not at widely known. (I would also excuse not knowing how to implement heapsort).

> > The same could be said for teaching implementation. Thoughtless memorization is rarely useful in any field. You can instead have them discover the theory like they would discover an understanding of implementation you advise. > The entier point of my post is to say we shouldn't do that. We should give them a task that they will want to acomplish

I am not sure I understand your response. Would you not have people naturally discover theory with strategically minded hints to help make sure they don't get stuck for a long time?

> The theory should come as you get stuck, not before. The act of getting stuck and then pulled out of the hole is what teaches you when something is meant to come in handy. > One such example is when your car battery dies. You probably don't have one of those self-jumping battery packs in your car but they come in handy. You only ever see why after your battery goes flat and you cant find anyone to give you a jump.

Oftentimes you need to know the applicable theory before you get into a problem that necessitates it because you would never know that the theory even existed unless you had studied something related. For most practical people, a decent taste of some of the big theoretical ideas should be learned simply to facilitate later on-demand looking up of theory.

For example, big O is a powerful concept, but you may not have ever heard of it unless you looked into theory of algorithms. Despite that you may start writing some brute force (exponential time complexity) algorithm and not realize that is a problem while working on AI pathfinding for a game. Despite there being many polynomial time complexity algorithms out there.

More seriously though, knowing a number of NP-complete problems may help you realize that a problem you are working on is NP-hard and thus you should stop looking for a polynomial algorithm for it (unless you think you can break NP =? P).

Following your analogy, what if you never knew that even jumper cables existed and instead got your car towed to a mechanic every time your battery died. You may learn about jumper cables after doing that once, but it would have been much better if you knew they existed beforehand.


Do you have a blog? You have some interesting ideas that would be good to explore in a longer form.


I do it's https://blog.gravypod.com but nothing interest is on it right now.

I'd love to write more but I usually need a prompt on a topic that I've thought about. I try to keep my ideas to myself until I've formulated an argument for either side that is "sufficient" in my mind.

I'd love to write about this in more detail and I'll definitely write about anything emailed to me if I'm able to formulate an idea either way. I'm heading home soon and write up something more detailed on this topic and why I feel this way on the topic of education.


I also advocate for starting with the low-level basics, although slightly lower - logic gates. Students should start off building circuits using 74-series ICs on a breadboard, while learning about Boolean logic. If the resources to work with actual hardware aren't available, a logic simulator should suffice. This is something that I think even young kids would be comfortable with doing: simple circuits to "compute" simple logic.

Then introduce binary maths and how that can also be computed using logic gates, and the concept of sequential circuits (flip-flops, latches, registers) --- allowing one to build a simple adding machine with memory. From there it's a short jump (no pun intended) to a basic CPU that interprets its data as instructions (critical concept!), and the rest follows naturally.

IMHO it's "interpretation of data" that is the key concept, regardless of whether you're working in high or low level, and that comes directly from understanding the basics.


I agree 100%. I'd suggest picking up NAND to Tetris. It's a fantastic book that takes you through this. It starts you off building all of the TTL components.

Sadly the software is horrible and needs some engineering to make it approchable.

I'd love a 7400 series simulator that isn't complete crap as then I wouldn't have to resort to designging my CPU on paper. If you have recommendation please tell me.

I'd buy the components and build things up but I'm a college student and that isn't economically viable.

Edit: Link to 2 minute pitch: https://www.youtube.com/watch?v=wTl5wRDT0CU


I'd actually argue an FPGA/CPLD is a slightly better approach, simply because you have block memory that acts very much like "cache" and makes it abundant why system memory is so much slower.

Since you have timing statistics it also makes it really easy to demonstrate pipelining and many other modern "quirks" of processors that have a large impact on performance.


The barrier to entry in the FPGA world is tooling and expression. If that hurdle is solved then I'd be all for it. It will usher a new era of electrical engineering design that is as cheap as software desgin making it practical for students to try EVERYTHING on their own.

To conduct similar experiments as I have with computer in electronics (as I'd like to do one day so I can get to the same place I am in electronics as I am in computer science) I'd need to spend thousands of dollars on chips and parts.


>The barrier to entry in the FPGA world is tooling and expression.

Re: tooling, both major vendors of FPGAs have free basic versions of their tools (e.g. Xilinx's Vivado and ISE Webpack) and supported development boards are available for $99 or less (e.g. Digilent's Arty Board).

Re: expression, both Verilog and VHDL permit gate level modeling. Verilog even has gates as language primitives.


>"The barrier to entry in the FPGA world is tooling and expression"

Regarding tooling, I'd say it's not quite the barrier it used to be, now that Project IceStorm exists.

http://www.clifford.at/icestorm/


If you're writing VHDL or Verilog then it's for electrical engineers, not humans. The barriers include bad description languages.

You should just have an EDA system. It will take time for pros to use but will be easy for beginners (especially considering that the output of the EDA will usually be what they did)


The GP mentioned 'tooling and expression', I mentioned tooling, you're mentioning expression.

Aside from that, other HDLs than just Verilog and VHDL do exist, such as Chisel and CλaSH:

https://chisel.eecs.berkeley.edu/

http://www.clash-lang.org/

Also, whilst I'm sure open source EDA tools could be improved, some of the basic building blocks exist, it appears to be more of an issue of packaging than availability. Seems like EDA tooling is a niche that a specialist Linux distro could fill (if tutorials are also provided).


See also this presentation: Creating a language using only assembly language (https://speakerdeck.com/nineties/creating-a-language-using-o...).


Wow, this was really interesting. Do you know if there is any video of the presentation available? I wasn't able to find it in a quick search.

Also I love to see people using speakerdeck.com to make their presentations available, it is so much nicer and and elegant that the abomination that is slideshare.net. Cheers.


I couldn't find either. Only the github page https://github.com/nineties/amber


That may be the ideal way to learn CS, but the problem IMO is that lots of people are going to lose interest immediately. When you start with a web app or a game they can immediately feel like they are developing a practical skill.


It's not only that, but doing something like writing your own assembler probably isn't going to be terribly relevant to someone creating a web app or making a game in Unity - particularly so 5, 10, or 20 years later. Heck, I'm not even sure that working on an assembler is going to be terribly useful to most people who will be writing in assembly.

Students who aren't interested in a particular requirement will complete it and then soon forget most of the things they learned. Heck, even students interested in it will probably forget most of it if they're not using it for a particular task. If they're not, you're probably better off with a quick survey course which gives them the basic understanding they need.

From my experience, the biggest problem with "CS" education (which tends to be a catch all for most software related computer studies) is the lack of focus. Students get a little bit of experience making a toy in language A, then they get a little experience making a toy in language B, then they get a little dusting of algorithmic theory, etc.

My suggestion would be to try to get them quickly up and running on projects they're interested, to the point where they feel self-sufficient. Then teach them what they need to make their project better. They're going to both retain a lot more and come out of it being able to do a lot more. Trying to make every CS student a jack of all trades ends up being a colossal waste of their time and money.


All software is related in some degree. You will find that people who come from a background of compilers will do well in developing certian portions of games.

In a sense most games are a compiler. You feed it in source (images, dialog, models, textures, etc) and it spits out an interactivly compiled narrative.

Websites are also compilers. They just operate on a higher level of abstraction then the simple toy compiler we would right.

The information to someone new is invaluable so long as they learn it themselves and aren't forced through it.


Even most people I know who have written compilers haven't written assemblers; neither have most people I know who have written (real, not toy) programs in assembly. The argument isn't that it would be useless, but rather that it's an extremely inefficient use of one's time and money if the goal is higher level development - or even, I'd argue, if one was aiming for a proficiency writing programs in assembly.

Again, I'd argue that focusing on being proficient at the level someone is interested in is much, much more useful than focusing on making a lot of different toys at a bunch of different levels and in a bunch of different languages. You are going to learn something either way, but jumping around with a bunch of small projects all over the place probably means that you aren't going to retain much and you're not going to have any particular strength at the end.

Conversely, if you focus you're going to retain a lot more, since you can incorporate a lot more of your previous knowledge as you get more knowledge - in fact, if you work on a real project instead of a toy, you're probably going to be seeking out a lot more knowledge on your own as issues come up. In the end you're going to be able to say your proficient in your chosen area, and you'll probably be in a good place to expand to other areas (and you'll have a good sense of where you should expand to).


> extremely inefficient use of one's time and money if the goal is higher level development

Have you ever written an assembler?

Have you ever written a compiler?

An Assembler is far simpler then a compiler and after building the Assembler a compiler is an extremely strait forward next step as you've already finished the first quarter of what you need to do in a compiler. You've tokenized (broken the problem into small bits) and you've generated some opcodes. That's the perfect starting place for any systems programming background and a systems programming background is the perfect place to start out at higher level languages.


Writing an assembler teaches you nothing. The skills gained while building an assembler teach you everything.


> I think the best way to learn about computer science it to program for a machine so simple anyone can understand how every bit works. No magic.

We do this in my school, sort of. The 2nd year courses teach you to know how to write assembly in a fictional subset of MIPS (https://www.student.cs.uwaterloo.ca/~cs241/mips/mipsref.pdf). There is a course where we write a compiler that emits this fictional MIPS, and a course where we learn how to implement a CPU that can execute (an even smaller subset of) these instructions (starting from CMOS gates).


Want to trade? You can come to NJIT: the land of physics, math, and more math. Oh and 4 "inter-disaplinary" corses (read wastes of time).


If you have an audience that is even interested in C (they came specifically to learn about it) it is probably safe to assume that they are interested in lower levels of tech simply by the popular association between C and that.

People benefit from context. A "how stuff is made" tour might help. I would show the newbies all the steps: how we start with a piece of C source, and go to executable. Here is a simple program that adds two numbers. Okay, we pass it through this compiler and here it is in the processor-specific assembly language, which is quite different. The "plus" is being done by this ADD instruction here, which receives values from two internal data places in the processor called registers, which are a bit like the storage boxes in a pocket calculator. Then, assembly language is coded, nearly instruction by instruction, to machine code, which is these numbers here representing ones and zeros. This is a bit like sheet music for piano being translated to a punched paper piano roll, but even more direct.


That is very top down. This is perfectly fine and the only reason why I think differently is because most of my peers are afraid of experimenting. They think everything they haven't seen is magic.... because well it seems that way. It's voodoo to them. When I see a compiler I just think "pfft, tokenizer, lexer, tree". When they see a compiler they think "I could never understand this in my life".

It's like when I go to my mechanic. I pop the hood, he looks at it, spouts off some Geordi LaForge-sounding nonsense, I pay him and I walk away feeling like I've made out like a bandit! "That moron! That stuffs so complciated this work was worth double that! Hahahaha!"

What's really happening is that my mechanic has touched under the hood and no matter the car he things "eh, I'll figure it out". Or "How hard could it be? I'f fixed thousands of cars and thousands of problems, I know what's wrong already!"

He gained that experiance from actually messing around under the hood. Not from driving the car at a high level like I have but from sticking his hands in and getting into the nitty gritty.

Going from the top down leaves people affraid to push further down into their machine. This is the fear of infinite complexity that they think is hiding under the surface. The truth is that all computer science material of of constant complexity when looked at on it's plane of theory. IF everything has been correctly abstracted and defined then nothing should be "complicated" but it should be "entierly understandable". Anyone who gets the basics should be able to go "eh, I'll figure it out" when referencing any part of the computer if it has been correctly implemented.


>When I see a compiler I just think "pfft, tokenizer, lexer, tree". When they see a compiler they think "I could never understand this in my life".

To be fair, they're probably more correct in this context. Even if you understand the basics of compilation (and by the way, if you're reading this comment and you don't have a basic understanding of how compilation works, you should go learn that. Like, right now, if you can) the chance of you actually understanding the entirety of GCC and/or Clang without taking three years to study them is pretty slim, AFAICT.


The exercise isn't to put you ahead of everyone else. It is to get you to see where everyone else came from.

I could try and run a marathon but I'm very out of shape. One of my friends can try and run a marathon who isn't out of shape and while they won't win they can still do it and learn from the experiance. The goal isn't to win, it's to learn in this case.


That wasn't my point. My point is, even if you know the theory behind compilers, and maybe have written a few yourself, you probably will have difficulty understanding GCC, Clang, or another production compiler unless you've done work with such a compiler before.

That is, your friends' awe of the compiler is not only justified given their skill level, it's also likely justified at your skill level as well (although as I don't know you personally, I can't say for sure).


The awe you're describing and the "awe" of his friends are very different, AFAICT. What you describe is perfectly healthy and reasonable: GCC/etc are unquestionably complex systems that can't be fully understood without thorough long-term study and experience. Oversimplifying them would be reckless, and so the average user of them should possess a certain awe and respect for them.

But this is different from having no conception of how compilers work and how one might implement one. As complex as modern compilers are, the foundational principles still apply to them, and an understanding of these principles makes them much less awe-inspiring. I think that having a clear view of the big picture, rather than having certain areas of the picture blocked off entirely as magical black boxes, allows for better engineering choices.


I agree. So I suppose that awe is a bit different.


Except at some point you have to deal with x86 and ARM and wait a minute - this looks a lot like computer engineering.

It's a very distinct segment of the whole hardware/software spectrum that's very, very far off from the realm of, say, dev ops.


Dev ops is not computer science. Dev ops is the operations of computational devices and the upkeep of the programs that run on them. Computer Science is the creation of these programs by taking advantage of the hardware they are running on.

Dev ops are the road builders to the shipping companies. They do absolutly nothing related to each other but they both need each other.

Dev ops is more an information technology field and it's useless to make devops people take courses from CS other then a familarity with Unix and Windows sytems. In fact Dev Ops people should go far further into depth on Unix and Windows systems to the point at which they know every bit of information of every documentation concerning running applications, services, and jobs on these machines. Computer scientists should go into how these are implemented.


Interesting in the 70's at high school my first language was CECIL a cut down assembler designed for teaching.

Bear in mind that this class was aged 14 and was the CSE (ie the vocational stream for those leaving at 16)


Assembly is very simple. That's it's saving grace.


Great explanation: you just described the perfect 9-12 year education for the future software developers or even a "STEM track" for those so inclined.


I'm worried that it may just be my love for microcomputers, old mainframes, and just computers in general that is clouding my judgement but I think this would really improve the understanding of computational systems for anyone who was so inclined to participate in the course(s) required to teach this material. Much like the steriotipical sex-ed course where students are made to carry a baby I think college CS students should be made to "carry"* their example computer that they have worked so hare to maintain and program.

I feel that something like this would be rather easy to do, cost wise, as many fanatics (in an endering sense of the word) have constructed kits that replecate the functionality of these machiens. One such example is the PDP-8 kit. This would make it extremely affordable to build systems like these for may students to come. [0]

I'm not saying that this exact system should be used, I'm just a fan of DIGITAL and wish I could play with more of their gear (anyone in NJ with a PDP or other microcomputers my email is in my profile), but the stands.

   - It's cheap to make
   - They understand the "GOOD OLD DAYS" to better understand design choices made on old software they will be maintaining
   - Due to the tough constraints of these machines they will likely cut corners. Corners we all have cut before. They will see the pain of doing that in a safe enviroment where millions of dollars or lives aren't on the line (like in the real world).
   - They will know every portion of the computer inside and out.
   - They'll get to friggen build things! Make things work! Really Program! (We all know the feeling of getting shit done and how addictive that is)


* Not carry everywhere, just to class and home.

[0] - http://www.sparetimegizmos.com/Hardware/SBC6120-2.htm


I agree. You have to learn from both directions: go read SICP, PLAI, TAPL, PAIP, Dragon, Algorithms, and whatever else so you have an understanding of the concepts.

Now build a Z80 or 6502-based computer (at the very least) and implement stuff on the bare metal so that you understand how the machine works, at least on a basic level.

But if you can't be bothered to actually build a computer yourself (which is completely understandable), and still want to get a feel for hardware, write some games for an old game console. I recommend the Gameboy: it's dirt cheap (~$20 for a GBA), you can buy a flashcart + reader/writer and/or SD cart from BennVenn for ~$80-$100 (although you may have to wait a bit until he restocks), it's well documented (the PanDoc and numerous tutorials can help you out), and the toolchain is widely available (actually, several toolchains are widely available: various forks of the now-dead RGBDS, and WLA-DX, which seems to be more lively, so it's what I'd reccomend).


I want to build a CPU from scratch actually but I can't find any 7400 series logic simulators that are worth their salt.


IMHO it does not have to be a 9-12 year education. Just having a one year course of teaching assembly would suffice. Then the student could go on learning by himself/herself.

In order to write good programs, you already need years of work and self study. It's much like being a writer. The most important role of education is to guide people and teach properly, so they won't get lost and have courage to pursue knowledge.

The problem is that not all people are passionately interested in computing. Most people here on HN are, and would still be amazed if they did not have an access to computers and wrote hand-written assembly. But regular people, even the ones who have an interest in technology in general and most of my friends who are currently studying CS, do not feel the same way.

The current university education aims to supply specialized workers, not free tinkerers. In 4 years you can train someone to write working programs. But training someone to be good at programming requires a different mindset. In order to become better at programming one needs to enjoy programming and devote a certain piece of his/her life to it.

In short: programming is a lifelong pursuit. Like all skills you get better over time, if you stick to it. But guidance can really help in the process and opens many doors for the interested. That's why a path that covers the lowest level is important. There are not many resources and it can be quite frustrating for a beginner. I never had the chance to study CS in a formal setting, but I still remember everything from my computer classes in high school. I am grateful for every piece of theoretical knowledge I acquired at that time. I had a real hard time accepting that I could not study CS. It took me a while to realize that they do not teach the CS I want at the universities that my friends attended and I could still work with computers like I always did; by reading and tinkering.

I think books like this are extremely important for the unfortunate ones amongst us, who are really passionate about computers, but cannot pursue CS full-time in formal settings.


What is the point in copying hex values?


To the outside world of non-CS people the concept of a processor is magic. It is in a sense still magical to me but I can see that a processor is just a complex state machine that takes in numbers and spits out numbers. Saying that without really experiancing it means nothing and I cannot put into words the value of understanding this. It makes so many previously unaprochable tasks much less daunting.

Copying in hex values will give the student many important skills. At first they will learn to recognize errors in the hex by identifying opcodes for the instruction set you are using. IIRC 0xEB amd 0xEA is a jmp. Secondly they will understand how the assebmly is turned into code executable by the CPU. It's not magic it's just a simple map operation taking the text from the assembly and 1:1 mapping it (in most cases) to opcodes.

Knowing the opcodes by heart is nice for debugging and decompiling/reverse engineering code. It's fun to do and a really important skill, in my book, for anyone doing computer science in the real world (and if you're paying >10k/semester at college you should know how to do it!).

Getting a feal for what is really happening under the hood, just numbers being read, run, and repeat will help you understand how to write a compiler.

Again, I can tell you all this and give you a chart to memorize and say "THIS WILL HELP YOU" or I can let you natrually tackel your tasks and allow you, on your own time, to find out what helps you get the job done.

The one thing that isn't negotiable is giving you tasks that incrementally will challange you but not scare you away. What is negotiable is how these are presented. I feel they should be unseen tasks hidden undernethe something that looks like something else to the student.


> It's not magic it's just a simple map operation taking the text from the assembly and 1:1 mapping it (in most cases) to opcodes.

Maybe in the Z80, but in modern x86 the instructions are broken down into micro ops and also pipelined (multiple pipelines, even).

> Knowing the opcodes by heart is nice for debugging and decompiling/reverse engineering code. It's fun to do and a really important skill, in my book, for anyone doing computer science in the real world (and if you're paying >10k/semester at college you should know how to do it!).

Why would you need to memorize hex opcodes for CS in the real world? I'll just use objdump or my favorite disassembler (even gdb can print instructions).

> will help you understand how to write a compiler.

Not sure how it will help one understand.


You've taken assembly, transformed it into opcodes in paper, and then manually typed that into a file.

The instructor should ask "Is there a way that you can do this that would allow you to avoid doing this?"

You've now been - Told there's a better way - Want to stop doing this as it's error prone and boring - Know every step of binary construction by heart

That's the perfect starting ground for exploring cs in my book.


But this isn't a comp sci book really since it doesn't actually cover any comp sci topics such as the analysis of computer programs, algorithms and data structures.


That's one portion of computer science. Computer science encompases, in my mind, the study, operation, maintnence, and information that is required to perform computing tasks of the modern era.

It's no use to know about algorithms and complexity if you only know how to sort punch cards as that isn't a modern day computing task.

A computer sceince background inherently implies software development background. This also includes an understanding of low level implementation and backing hardware that makes computation possible so you may understand the limitations of the hardware and how to engineer within those constraints.

An algorithm that takes infinite time for 1 instruction is O(1) and still constant time. An algorithm that takes infinite memory for every run is still a constant memory complexity. Knowing this tells you nothing about how implementable these algorithms are and thus a focus on only this algorithm and datastructure portion of computer science is useless without practical applications and an understand of how to go about implementing and discovering your own data structures and algorithms for real life tasks.


Algorithms and complexity theory are independent of any physical model of computation; they capture what it means to compute.

The entire field of theoretical computer science stands as a counterexample to your comment. Computer science is not about software engineering.


Computer science assumes that the code is run on a machine with a very specific set of operations since otherwise you wouldn't be able to calculate time complexity. The set of operations were deliberately chosen to be a reasonable abstraction of a modern computer. Thus computer science would look very differently if computers had different capabilities.

For example, lets say that a new computer could switch places of two blocks of memory in constant time no matter their sizes. That would completely revolutionize computer science since many of our old results hinges on the fact that moving memory takes linear time.


The extended Turing thesis says that whatever is efficiently computable in one "reasonable" model of computation, is also efficiently computable in another reasonable model of computation.

Of course, the truth of this thesis has been called into question with the advent of quantum computers, but it holds otherwise.


An algorithm that is infinitly complex and takes infinite time is of no practical use in every day computation. Maybe in theory, in textbooks, in labcoats, but not in industry.

I don't know where an uncomputable algorithm would be useful.

I do know that you cannot possibly start a student out on a plane of the purely theoretical as they cannot see the value of what they are learning, they cannot understand the implications of the material, and frankly they won't remember it if they don't need it. To their minds, they don't need it if they haven't used it. It can be JFM (Just Fking Magic) to them if they haven't seen a case where it has improved their own algorithms. They will also not really understand how it works with no implementation. It is impractical to say the least.

Theoretical computation is a higher level topic then real computation topic. In the same sense that you start math with addition, subtraction, multiplication, and division you should start out computer science with implementation.


Nobody is talking about "infinite time" algorithms; complexity theory concerns itself with what is efficiently computable. This might not directly correspond to "real-world" efficiency, because an algorithm, while polynomial-time, but have poor constants or a huge polynomial.

However, this does not mean complexity theory is useless; it still informs us of what computers can and cannot efficiently do. It marks the limits of feasible computation.

> I don't know where an uncomputable algorithm would be useful.

Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant.

As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten.

My point, as stated in another comment of mine in this thread, is that it is not necessary that a "true computer scientist" know anything about low-level computer details. I suspect this holds true not only for theoreticians, but also many systems builders (like in distributed systems and such). So, having a intro course focusing on low-level details as the main component will not necessarily provide a good introduction to computer science.


> Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant.

I do not think this is a correct statement from what I've seen.

> As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten.

If the course is organized correctly the experiance can be magical. You're pulling the curtian on the the giant talking head. You're showing the students how everything works and you should do this directly. Like all teaching the student needs to THINK they have been the ones to discover something while in reality the teacher is supposed to have errected an artificial situation where in this was the case.

You don't start them off with bits right off the bat although that is one approche (That is extremely successful: see NAND 2 Tetris). Like I said in my other comment you state them off with a broken machine. You give them an artifical reason to continue. "If you want to get a grade you have to open up this machine and, with me coupled with some hand holding, diagnose the problem." That gives them a reason to learn about the different parts of the computer. That errects a situation where they FEEL that have found something that they weren't meant to. They've explored something when in reality it was all, as someone smarter then me once said, a "Head Fake". Get them looking at a nearer goal and they'll start dreaming of further ones.


But is the point of your course computer science, or computer engineering. I don't think I'm particularly special, but I have taken just the one computer architecture course as an undergrad (and I don't remember much if any of what I learnt), and now I just completed the first sem of my PhD in computer science. I haven't used the information I learnt in that class yet, even though I'm in a partially applied field (security and cryptography).

All I'm pushing back is on the idea that learning the intricacies of modern computing is necessary for being good at computer science.

EDIT: And wrt complexity theory and computability: there is a subfield of mathematics called computability theory that concerns itself with various notions of what is and isn't computable. Complexity theory concerns itself instead with what is efficiently computable; the problems it considers are already computable.


Well you're not going to like when I say this.

Cryptography isn't Computer Science. It uses some things that Computer Science developed but it isn't Computer Science. It's applied Math.

If Cryptography is in CS then Nuclear Reactor Operations is in CS. NRO uses computers for monitoring systems and develops algorithms to detect certian... ahm... undesierable states. That doesn't mean we should move a reactor into the CS building at every college near you (although I'd love to work on one eventually, sounds like cool work).

Academics may think that crypto is a CS field but the work involved has absolutly nothing to do with CS. For example, all cryptographic functions can be implemented in hardware. If you are building a cryptographic function in hardware, you're not part of the Electical Engineering department or the Mechanical Engineering department you are still in the Math department because all you're doing is implementing an abstract design.

(Insert unintelegable "get off my lawn" statement)


... what?

I am not sure what your idea aof cryptography is, but crypto relates to the most basic of questions about computation: what is and isn't efficiently computable, that is, P ?= NP.

You do realise that the origin of the field of Computer Science lies in mathematics, specifically Turing's work, right? By your argument, the entire field of Theoretical Computer Science is ... not a part of computer science. Some how, I think that that's not quite right.


> A computer sceince background inherently implies software development background.

> An algorithm that takes infinite time for 1 instruction is O(1) and still constant time.

> An algorithm that takes infinite memory for every run is still a constant memory complexity.

None of these are true.


> An algorithm that takes infinite time

Can you give an example of such an algorithm? My understanding of an algorithm is that it must terminate in a finite amount of time, but maybe you have a different definition of an algorithm


> My understanding of an algorithm is that it must terminate in a finite amount of time

Any practical algorithm yes. Any theoretical algorithm no. This is where the will it hault questions come from. Check out Ackerman's function as a good example that we aren't sure if it will terminate. It is still extremely interesting from an algorithms analysis perspective but not from a CS (as I use it) perspective.

Also I'm not specifically talking about algorithms. I'm talking about flaws in O() notation in practice. It is easy to make something look fast in theory when it is far slower in practice.


The algorithm that computes Ackerman's function recursively (https://en.m.wikipedia.org/wiki/Ackermann_function) always terminates in finite time


More specifically operating systems from the bottom up. The title suggests this is far more comprehensive than it actually it is.


This is very Unix, C, and Intel specific, to the exclusion of practically everything else. It's quite a good introduction to some aspects of those, but the title should be changed to make this clear.


As someone who was trained on the hardware side of EE, but has a passion for general CS and is truly fascinated by it, I believe this book will be perfect for me. I have programmed on and off for years with varying levels of intensity, but have never truly understood and studied the lower level aspects of what I was doing. My programs range from robot control to web apps, but all have been on the uppermost levels of abstraction.

I will read this over the course of the next few days and edit this comment with my thoughts and notes.


If you want to try something out but get put off by some of the C frustrations like dealing with memory and working out how to deal with the standard library you should pick up a cheap copy (or download the free copy) of Structure and Interpretation of Computer Programs. It's a book that walks you through, program by program, all of the basic concepts of programming languages, computation, and programming in a clear and orderly mannor. You'll learn LISP, which to someone who works on lower level systems may not be of any use to you, but it is choosen because it is the simplest language to learn that will allow you to on your own pase explore different concepts dealing with computation.

The book is well worth the $10s you pay for it and it isn't written like a textbook and more like a tutorial/walk through the park of computer science.


I remember trying do do that years ago, and getting hung up as a newbie on there being a million different LISP implementations. I think I tried to use Racket, if I remember correctly, but whatever I picked didn't support some of the book's LISP statements out of the box. Any recommendations for a more friction-free experience?


I remember trying to learn a garbage-collected language with curly braced blocks, functions and infix operators years ago, but was hung up on there being a million implementations. I think I tried to use Java, but was hung up on the book's C# statements that weren't supported out of the box. Any recommendations for a more-friction free experience?

How about this recommendation: use the exact same language that your book or tutorial teaches!

Racket has even gone out of its way not to be named Scheme (it was a Scheme once called PLT Scheme, but changed its name). Scheme, in turn, went out of its way not to be named Lisp.

A tutorial that purports to be about Lisp is quite probably about a traditional language which has characteristics such as the symbol nil being a self-evaluating expression representing the empty list and Boolean false.


I don't think this is a fair comparison to what the GP is saying. You can pick up pretty much any book on programming for the C-style and more then 90% of the information will transfer over. Classes may be omitted in some, reqired in others. The same may apply to types. But after they see a compiler warning you're likely to google it and figure out what's wrong very easily.

On the other hand most people, who are quite professional in our field I might add, don't even know the names of the most used LISP derivatives. Many also don't even realize they have one built into their browser that is perfectly adequate for satisfying the desires to explore functional programming and general computation principles.

This isn't a statement of malice or even a bad question from the GP. It is confusing and we only have ourselves to blame for this (ourselves being the world of people who want FP to become more mainstream in the SE world).

Look at the stark differences in these two websites:

   - http://racket-lang.org/
   - https://www.rust-lang.org/
What we need is this (with much less crap):

   - https://www.python.org/
And what we don't need is this (with all of this text and few examples of what you CAN do):

   - http://julialang.org/

Granted these are for different markets but the point still stands. If you want adoption by the general software development communities we must make a good case as to why this move should be made. Historically this required a few factors

   1. A better alternative to at least 1 problem *
   2. A simple unified way of introducing people to the change
   3. Simple support for the rollover. Or at least simple enough as to not overpower the benifits presented by switching over.
* = Something that has already been done by the FP community.

You have to understand that peeople call it like they see it and when they see Lots of Insane and Silly Parrens they see LISP and no name change will disaccosiate Scheme, Racket, and LISP in the eyes of the average programmer. I've been using functional languages for a good part of my life as a programmer and I feel they ARE the same. The ideas are common even if their presentation isn't.

The only LISP-Like languages that have sucessfully hid from the tarnished name of LISP are JavaScript and Python and they've managed to develop their own bad raps for themselves in the eyes of some programmers.

No progress will be made by barrating people. Prucussive maintence works on tools and gear, not peers.


>"Many also don't even realize they have one built into their browser that is perfectly adequate for satisfying the desires to explore functional programming and general computation principles."

Are you referring to Javascript being a LISP dialect here? I've heard this occasionally but I also though that the one predominant feature of LISP was that of homoiconicity which I don't believe applies to Javascript or is that not correct? Thanks.


JavaScript IS lisp with 1) a new syntax and 2) more things bolted on top that make it a non-LISP language. There are two things under the catagory of JavaScript. The Functional size and the Imperative side. It's the only language in the lisp family that allows you to write both, neither, or some combination in the same program. I say neither because other paradigms can be expressed from within JavaScript that will not be expressable in most FP and Imperative languages without some muscle involved in forcing it to do so.

Watch David C.'s talk on JavaScript the Good Parts to see this diamond in the rough.


> It's the only language in the lisp family that allows you to write both, neither, or some combination in the same program.

Where did you get that from?

Almost all Lisp dialects allow you to write functional and/or imperative code.


I will give this talk a watch, thanks.


I can't seem to find this talk anywhere on the internet.


Racket has an SICP plugin that makes everything from the book work.


Racket is much less approchable for people. I can't figure that mess out. Many people seem to find it difficult to endorse "get started and go" mentalities. The reason for N language implementations in Racket is that many LISP programmers are big fans of Domain Specific Languages (DSL) and this is also something that is taught in SICP.

Edition 2 of SICP was reimplemented in Common Lisp [0] (more specifically ANSI Common Lisp). Common Lisp is to Racket/Scheme/JavaScript/Clojure as C is to Rust/Java/Python/C++. It isn't the only way to implement a language and no one will say it's the "best" when compaired to My Favorite Implementation (TM) but everything draws from it and everything influenced it at the same time. It's the common ground that everyone can hold a leg on and knowing it will be your Rosetta Stone.

One common implementation is CLISP which is a GNU package.

To find out how everything works it is recommended that you attempt to read through the UNIX man page on the operation of this program. You will better understand how to interface with the program then. If you've used python then you will instantly recognize the idea of the REPL. [1]

If you have a software development background then [2] is probably all you need to get started. If not, as I have mentioned, you can check out SICP [3] as the book is online for no cost on an MIT website. Reading through this, maybe even one chapter per day, and doing the exercises as the book tells you to will give you a solid understanding of the concepts.

[0] - https://en.wikipedia.org/wiki/Common_Lisp

[1] - http://www.clisp.org/impnotes/clisp.html

[2] - https://en.wikipedia.org/wiki/Common_Lisp#Syntax

[3] - https://mitpress.mit.edu/sicp/full-text/book/book.html


CLISP is redistributed under the GPL, but isn't part of the GNU project.

GNU project's Common Lisp implementation is a project called GCL: GNU Common Lisp, a descendant of Kyoto Common Lisp.

Also, your analogy that Common Lisp to various Schemes and Clojure is like C to Java/Rust/Python is severely flawed in multiple ways.


I am curious do you have a different suggestion for a LISP implementation for working through SICP other than CLISP or would you agree this is a good choice?


SICP is squarely based in Scheme. One of the two authors of SICP is Gerald Sussman. Sussman, together with his then student, Guy Steele, invented Scheme.


Thanks.


Every CS degree I know teaches aspects of every level at once. I can't think of any course which, over time, goes from a high level downwards. It wouldn't make sense.


I think Nand2Tetris got this approach right:

http://www.nand2tetris.org/


At my school (NCSU) Computer Engineering was taught from the bottom up - Assembly was 100 level, C was 200, Java was 300. Advanced topics covered CPU caches and memory hierarchies, CS never got those.

Computer Science was taught from the top down - Java in 100 level and C/Assembly were touched on in 300 level. Advanced concepts were data structures, operating systems, and algorithms, CE never got those.

Most of us are hacking on web apps these days anyways in which a baseline from either CS or CE is fine.


First impression was wow, I've forgotten how much I've learned over the years. You would learn a lot this way.

However it's hard to call it computer science without specific attention to data structures and algorithms. What about information theory, networking, database systems, and some kind of AI related course?


Is this more about the science vs the trade? I do wonder if a practical foundation helps people understand and go deeper into the science.

When I did a computer science degree from the University of Victoria, Canada, 1996+, it more started from the "bottom". Though if I remember assembler was being moved or removed from second second year. On the other hand before I finished for new students discrete mathematics, matrix algebra, and differential equation courses were also being dumbed down or eliminates. By the time I finished course catalog had a lot of "software engineering".



This reminds me of the computer engineering coursework I completed before switching to CS during my time at university. Interesting stuff sure, but a great way to overwhelm a beginner.


I so wish I could have learned CS this way in college. I ended up doing EE instead, which really came down to a preference for the order in which I learn things.


This is similar to the practical side of the CS education we got at The Evergreen State College, except fancy high-level stuff like Unix and C wasn't covered until long after we learned to write simple programs in assembly/machine code on virtual Von Neumann machines that we implemented ourselves.


Based on the comments I see here (about how they wished to learn CS, or CS vs EE), I wish this book had a different title with more of an indication that this is a operating systems book (though not 100%). Computer Science is more than what is presented here.

Big O Notation/Data Structures/Algorithms, ala Dr. Knuth

Proof and theorems

Computer architecture and design (NAND gates and the like)

Language design, interpretation, and implementation

...and much more.

Do not get me wrong, I believe this book is valuable (BIG 'THANK YOU' to Ian Wienand for it). I just wish the title could have been different.


I agree, the book isn't very "bottom-up" at all, perhaps with the exception of "Binary and Number Representation" being the second chapter; the rest of it looks like OS stuff.

This is what I'd consider "bottom up":

https://www.amazon.com/Code-Language-Computer-Hardware-Softw...


My choice for bottom-up book: The Elements of Computing Systems: Building a Modern Computer from First Principles https://www.amazon.com/Elements-Computing-Systems-Building-P...


This is also known as the "nand2tetris" course: http://www.nand2tetris.org/

Great book!


I agree, and these are important CS topics. However, Big O made so much more sense to me after I've had a chance to understand basic machine execution and written a few non-trivial programs.

There's another aspect regarding when to introduce some of these topics - getting kids and new CS students interested and energized about what they are studying. I know the argument could be made that if these topics aren't of interest then don't do CS, but they must be introduced at the right time.


My first job after graduation (CS) was writing code in 6502 assembler for business phones (I know, I'm dating myself). What I learned there was the basis for code I write even today. There's nothing like understanding from the ground up.


Thanks for making this wonderful resource!


check these open articles from The VLDB Journal

http://link.springer.com/search?query=&search-within=Journal...


Excellent list! Thanks for sharing ... Merry Xmas & Happy New Year.


IMHO if you're not learning computer science from the bottom up, then you're not really learning computer science.


You can read this online here -> https://www.bottomupcs.com/





Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: