Morning Ed: United States {2016.06.28.T}

Well, I say keep teaching the trig and calc, but mostly cuz the rise in machine learning. Basically, you’re gonna want some REALLY SOLID foundations in linear algebra and basic metric spaces stuff. Sure, not everyone is gonna be writing a non-linear optimizer from scratch, but just as you want to know how a compiler works, you’re gonna want to know how TensorFlow works.

Taylor’s theorem works on higher dimensional manifolds. From this comes everything.

If you say, “Not everyone is doing machine learning,” I say, “They will.”

But yeah, the compsci foundations: automata theory, recursion, formal languages, a smattering of lambda calc and type theory, relational algebra and calculus, etc. We need more of that stuff. Tons more.

The thing is, most of it is pretty easy. Which sure, Gödel’s stuff still bends my brain a bit, like I have to take deep breaths and remember which is referring to what at which level. (It’s easier just to translate it into Lisp.) But yeah, anything “formal” I do these days, I mostly try to translate it into some basic typed lamdba calculi. Just, my brain is trained at doing that. Every well-typed Haskell program is a proof!

Train your brain!

We’re training people to wire up bad Javascript/CSS monstrosities backed by barely understood Ruby code. This is not the right way.

Beneath every bit of software is a problem, which can be expressed in formal terms — cuz computers are formal all the way down. And any “formal” thing is going to have a language, a logic, an algebra — even if you never write this down. It exists, if only as an emergent property.

After all, even fucking Perl had a semantics — just no one really quite knew what they were.

So anyway, learn to clarify, to write down, to find the logic, the algebra. Know the language, it’s terms, its compositionality, it’s rules. Code to that.

Every year software takes over more of everything. Every year it gets bigger, takes up more “space” in our lives and culture. This is good, but darnit we need to master this art form.

It’s math.Report

It is a mistake to assume Lisp programmers don’t know how memory works. For example, the application I work on is about 35% C++, and we share extensive data between both C++ and Lisp. Trust me, we understand where each bit goes and how it gets there — cuz we gotta. We pay a lot of attention to cache performance. At the scale we work, making sure related things land in memory close to other related things makes a huge difference. Likewise a large share of our static data is held on disk in its “in-memory” binary format, which C++ and Lisp handle just fine — we’ve hacked the Lisp GC to do what we want. In any case, we mmap that stuff in, for better VM performance, etc. etc.

Knowing abstract algebra and formal semantics does not preclude a programmer from also knowing how malloc/free works, or what a kernel trap is, or how virtual memory works, or how interrupt handlers work, or Unix signals, or any number of things. If you’re interested, you should see the crazy-as-fuck things Ed Kmett will do to get the Haskell to sing.

You saw above where I mentioned you need to know how your compiler works — you need to know this cuz you might not like what it does and need to tweak it to do something else.

You need to know how your linker works, in the sense of what it actually does, cuz you might need it to do something different.

Like, you might be working on some massive distributed system that deploys code packages to live boxes, and loads and unloads pages of code in real time — cuz that is what you need to do to distribute your problem across 10,000+ nodes. So you write that. Maybe you hack up your own linker.

(In our case, our Lisp does not produce standard ELF binaries, which creates trouble. Anyway, I personally haven’t dug into that part of the code, but someone has. If I ever needed to, I could. I know how linkers work.)

But still, big-hard-new problems require big-hard-new thinking. Things are bigger now, at enormous scales. The problems are also more ambitious. The tools are more advanced.

If you want to write something massively distributed, it really helps if you think in terms of associative algebras. If you’re problem does not have an associative decomposition, it’s going to be very hard to effectively distribute. (That whole Fortress thing that Guy Steele was working on was based on these ideas. It didn’t get anywhere. But still, the ideas were good and will show up again, cuz math is truth.)

Humans can solve these things with our brains, for small problems. For big problems, we need machines to do it. Deciding how to split up a variable amount of work among a variable number of CPUs under varying time restraints is not a problem you want humans reasoning about. So your work elements must be expressed in a formal way, so machines can decide.

Which is to say, something like Map/Reduce was a very early/simple example of this. But many problems don’t break out that way. Not many tricky graph algorithms are being done in Map/Reduce.

(There are large distributed systems to handle graphs, but you gotta know your shit to use them.)

Another example is rules-based event systems. When you are dealing with tricky timing, and 100k+ different semantic elements that need to be scheduled and sequenced in an unpredictable environment — well you don’t want humans figuring that out. A machine needs to do it. This is logic programming, but not the Prolog stuff. That was so primitive and too slow. But still, your rules need to be pre-processed and verified, for performance. In the end, you are writing a proof system. (You are also writing a combinatorial optimization algorithm. But the point is, your optimizer is processing formal structures that obey rules. Those rules need to be baked in. Perhaps those rules will change. If they do, can you afford to re-hand-code the optimizer? The point is, if you expect the rules to change, better to make it rules-based from the outset.)

(The entry-point of these ideas is declarative programming.)

(One way to think of this is, we are doing for rules and scheduling what SQL did for database access. Sure, you can deal with relational data without SQL. Perhaps in some high-performance environment you’ll need to. But darnit SQL makes it safer, cleaner, more predictable, and easier to reason about.)

(And yes it helps a lot to know how indexes work and to be able to read the output of a query planner. Someone on your team needs those skills. Usually that person turns out to be me.)

Anyway, I know some folks who do this sort of thing for real-time finance stuff. Semantic clarity is a big deal to them. They indeed think in terms of logic and algebras. For them, mistakes are expensive.

Anyway, the idea that knowing the “high level” stuff hinders knowing the “low level” stuff is nonsense. Certainly we want experts in each. People are going to find their focus. It’s clear the direction mine has gone. But that said, if you dismiss me as a “head in the clouds” type, you don’t know me.

Back in the day, the machine language folks through Fortran was silly. I’m sure the database gurus thought SQL was a waste of time. But we march forward with better abstractions each year, and we solve bigger problems with less cognitive load.

You don’t need map/reduce to distribute stuff. You don’t need TensorFlow either, when you want machine learning. But we have them now. Next year we’ll have more. And to keep everything doing what we expect, and to be able to communicate what we expect it to do, we will need formal languages to express these ideas, and we will need systems that understand those languages and that can process them correctly.

Else there is chaos.

It is math.Report

@davidtc — A well-rounded programmer is going to know a lot of things. Which is to say, I’ve written interrupt handlers — a long time ago on a 16 bit machine. I assume I could do it today. There are plenty of books titled “Linux Device Drivers for Boneheads.” I could read one. I haven’t needed to.

My point on semantics is, you’re doing this stuff anyway. You’re just not thinking about it.

Trust me, if your software system is over 10,000 lines, you are doing this stuff, just — in an non-deliberate way.

Okay, so the examples I gave were places where you must do it, because the complexity has outstripped our cognitive capacity. Fine. Not everyone writes software like that. But many will. It’s a changing world.

Anyway, my bigger point is, if you do something important, but in a not-thought-about way, then thinking-about-it can be a huge boost.

Look, actually automated formal systems are still largely “research” — although I know plenty of people who use them, but that’s from “selection bias.” Those are the people I seek out. But still!

(This might run long. I hope it’s worth your time.)

(I promise I have a point.)

#####

You know the seven-plus-or-minus-two thing, right? This is how much we can “hold in direct consciousness.” It’s what we can focus on.

What is the boundary of a concept? Well that is complicated, but look at it this way, the more sophisticated your concepts, the richer the structures you can think about. If I can hold a deep set of ideas as one concept, I can perhaps combine it with other deep sets of ideas in ways that I could not if I had to “keep in mind” all the complexity of each idea.

You do this already. Every time you name a subroutine or create a class, or really any abstraction. Each time you multiply “floating point numbers,” you are using a complex abstraction. You need to know how they work, but you don’t need all of that that centered in your active conscious every time you type something like

x = 3*cos(phi) + alpha;

We can abstract nouns. That is obvious. “EmployeeRecord” or “AtomicCounter.” These are things.

We can also abstract actions, relations, logical structures, some of them quite complex.

People like to make jokes about Haskell Monads and their complexity, but they do unify some deep patterns. Are they the right “sweet spot” of abstraction versus complexity?

I don’t know. They seem hard for people. They are very abstract.

I’m pretty sure the Java object model is too simplistic, which is why all that crazy-as-fuck “Java Enterprise” XML hellscapes got invented.

Okay, so a fun question: what is equality?

In Java/C/C++/etc., you have something called pointer/reference equality. But you also have (for simple types) value equality. But those are not enough. To write anything “real world,” you need to define more elaborate “structural equality” for compound objects. Each languages handles these differently, but it is the same underlying idea. (In C++, you overload ==. In Java, you implement .equals(). In C, you cry.)

Common Lisp has like 34080293904 different flavors of equality. It’s actually obnoxious and badly designed. (I like Lisp, but I don’t deny its flaws.)

Haskell has one notion of equality. Sort of. That’s a long conversation. Let’s skip it.

Consider this: what is the difference between identity and equality? How does that apply to an EmployeeRecord object, which might simultaneously exist in a database, a memcache, directly in the memory of your front-end web server, as Javascript objects in a user’s browser, and as display object in the browser’s DOM?

You don’t need to answer. The point is, it is essentially complex, and a fairly typical problem for “normal, ordinary” programmers.

It’s really nice to build your software on top of solid, well-tested frameworks that have already solved this kind of complexity —

— when they work! It’s tricky. We have a long way to go.

(Whenever I hear “eventual consistency” I want to cry. I get why it exists. I don’t have a better idea for software at that scale. But still, I cry.)

Formal methods.

Here is the Javadoc for Java’s hashCode() method. Just below that is the equals() method. Look them over. Notice something?

(I don’t know if you know Java. Perhaps you are already familiar with this.)

There is a formal contract you code must maintain if you implement these methods. Look at how they are expressed. “Reflexive,” “transitive.” That is formal math. If you do this correctly, then your objects will behave correctly when put in a HashMap (and many other structures). If you get it wrong, they will behave unpredictably.

Java does not check that you have done this correctly. The thing is, Java has no essential notion of equality for objects. It can check pointer/reference equality, but not any “higher level” of equality. You have to implement that yourself. You have to use your own brain to ensure that you got it right. (Plus unit tests.)

You are doing formal reasoning already.

I’ve written code that implemented (something like) set-union and -intersection semantics, but where “equality” was based around behavioral equality, and where certain objects could be unified in certain cases, but not others. It was complex. But clients of the code depended on its behaving a very specific way. We also had to optimize the heck out of the union/intersection stuff — which was really a kind of unification procedure — and we used different methods with different compromises depending on the size of the set. Tricky, tricky, tricky.

We used this structure to optimize a wall-clock-time-limited heuristic search over an NP-complete search space. It worked well. According to our sales folks, our competition “didn’t understand how we could do it.”

That’s a win!

These “sets” had a very specific semantics, which existed in three places:

1. Implicitly in the code,
2. Implicitly in the unit tests,
3. Explicitly in code comments.

That is the best we could do in Java. We could have specified things better in a language such as Scala, but even then, without full dependent typing, at some point you have to punt the ball. You do the best you can with the tools you have.

#####

Okay, summary time. (Did you make it this far?)

You already reason formally. You have to. Managing complexity requires it. That said, thinking about the formal models themselves, on their own terms, gives us sharper tools to build even better formal models. This means higher abstraction, which means more complex systems with less cognitive load. This means doing more with the same brainpower.

Mostly this is conceptual. It’s “in your head” stuff.

The next step is offloading the “translate the formalization into code” part. The more you can offload onto machine-checked and machine-generated systems, the better. This really is an example of the “make sure information exists in one place” principle. When you can do this, you can just look at the formal spec, which often fits on a few lines on your screen, and know fully what it will do. This is not to “dumb things down.” A skilled engineer still needs to understand the process from tip to tail. That might be one expert on the team, who teaches others, just as often a team will have a few “database gurus” who work beside a tons of folks who know basic SQL.

(These formal approaches precisely the same as knowing how your compiler works, but never having to hand-compile your code. It’s exactly that, just moved up a few levels of expressive power.)

There are limits. In its full measure, computer proof systems are semidecidable, and even when the result is “valid,” they are nowhere near polynomial time. We’ll always be threading the needle between the practical and the desired. We also must teach these ideas, make them accessible. That’s hard. I’m trying to do that literally right now, right here (to a degree).

#####

Postscript

Is it worth it? Consider math. Right now “smart but not world class” math students can, after 4-8 years in university, understand math concept that in a prior age could only be grasped by a small handful of humanity’s greatest geniuses. Think about that. This is the “shoulders of giants” thing.

It is real. It is due to greater expressive power, greater unification of ideas, deeper abstractions.

Take linear regression. You probably learned this in statistics class. It probably took a whole lecture, maybe multiple lectures. It was tricky with lots of moving parts.

If you are good with matrix algebra, it can be written in one line.

This is the power of abstraction. By looking at that one line, if you are good at juggling matrices, you can “just see” many, many interesting things.

The point is, abstraction makes hard things obvious. I can read the Wikipedia article on factor analysis, and I “just see” efficient ways to implement it, even though I’ve never studied it deeply.

(That said, if I had to implement it, I’d still go read some papers. But still, I have a foundation.)

So it goes for software engineering. We are solving harder problems now. We need better tools.

We still need people who know how interrupts works. But then, I understand them for single-processor models, cuz that is what existed “back then.” I assume it’s more complex these days in multi-cpu systems. I can kind of guess how they must work. If I need to know for sure, I’ll look it up.

How do interrupts work in modern “supercomputers” with 34802938409328094328509390 CPUs connected to weird geometric arrangements of RAM?

I dunno. If I ever work on a computer like that, I’ll want to understand it, at least at a basic level. Anyway, it sounds like a cool problem. I bet they use formal models.Report

@mike-schilling — Tee hee. I’m guessing it heats up your CPU.Report

[insufferable know-it-all mode]

Well there is a command line flag to set per-thread stack size: -Xssn

Discussed here: http://docs.oracle.com/javase/6/docs/technotes/tools/solaris/java.html

I suspect the behavior is at least implicit in the JVM spec, as a combination of these sections:

https://docs.oracle.com/javase/specs/jvms/se6/html/Overview.doc.html#6654

https://docs.oracle.com/javase/specs/jvms/se6/html/Overview.doc.html#17257

(I have no intention of reading that in detail.)

[/insufferable know-it-all mode — if you hate me now I don’t blame you]Report

The docs say:

(This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

You can actually launch the standard JVM with different garbage collectors, which have various speed/concurrency/etc. tradeoffs. Some are “moving” collectors. Some are not.

The standard library implements Object.hashCode() as a “native” method, which means it calls down into the underlying JVM code. In other words, it is “beneath the language” magic. The JVM will be required to use whatever is needed to ensure correctness. If it is using a “moving” collector, it will need to generate some kind of persistent object ID. There are many ways to do this.

In any case, if I were working on the JDK, I would remove that from the documentation. It should be irrelevant what the JVM does, so far as it obeys the contract.

Anyway, I mentioned Java’s .hashCode() and .equals() because I wanted a simple example of a formal notion that is not well-represented in its host language, but that you need to reason about yourself. I can give other examples. C++ is full of them. If you want to freak-the-fuck-out, read all the rules about how to handle exceptions in a complicated C++ constructor in a memory-leak-free way. It’s mind-bogglingly complex and specific.

Humans should not have to do this. But right now we do.

There are better ways.Report