While we have achieved greatness with the Von Neumann evolutionary line, now that the Mhz free lunch is ending, it’s time for us to recognize that its sequential nature is holding us back. There are still many branches of Computer Science that researchers and industry have barely explored. We need to reevaluate these other branches like Functional and Dataflow programming.
Ivan Sutherland explains it best when he says that concurrency is not fundamentally hard. The problem is that we constraining ourselves to the fundamentally sequential Von Neumann architecture.
https://www.youtube.com/watch?v=jR9pAaQlVRc#t=267
I feel the Mill architecture is sufficiently familliar while still being quite different that it could help us transition to more interesting/efficient/parallel/concurrent etc. architectures.
On the contrary, I think that we haven't exploiting sequential machines to their full potential, and what's "holding us back" is all this theoreticism and overabstraction. There likely is a point where concurrency is really necessary, but one only has to look at the demoscene, full of people who have never formally studied CS, to see something closer to what hardware can really do -- and then wonder how so many others working in software, with formal backgrounds and extensive education in CS, couldn't.
This crosses my mind every time I hear about the MHz free lunch.
https://www.youtube.com/watch?v=oBegD7k2wvo , 02:20. JS and WebGL, which seem to be all the rage nowadays, would smoke the shit out of my i7 doing that. In case younger chaps are watching, the C64 has a 1 MHz CPU and a whopping 64 KB of RAM. For comparison, minified jQuery 2.0.0 is about 80 KB.
I agree that concurrency isn't fundamentally hard, but the reason everyone kind of prefers faster serial execution is because a lot of algorithms (extremely simple example: f^100000(x)) are fundamentally unparallelizable. Faster serial execution is just so much more straightforward.
So a common problem with concurrency tends to be not "How do I make these functions run in parallel", but "Is there an algorithm that does the same thing I want without relying on constant function composition?"
I feel like "industry" doesn't really want functional style programming to take over. Languages like OCaml provide really great speed while having also utilizing a relatively high abstraction level, while Lisp may not have as much speed but it takes your brain on a journey to another dimension.
However, in practice, people seem to just want "C with Lambdas" languages like Go.
This is probably going to be unpopular:
My main problem with most functional languages is that they encourage cryptic code.
From the tutorials I've read Lisp seemed somewhat readable, but the tutorials encouraged me to use list comprehension all over the place because it's so convenient. I need to decrypt all the map zip range calls in order to grasp what's happening. Disclaimer: I don't know if Lisp is used like this in a productive environment.
Haskell is often described as "elegant" (Here for instance: http://www.haskell.org/haskellwiki/Why_Haskell_matters#Elega...). To me, the examples are far from elegant. They just prove how much functionality one can cramp into an operator. But if I have to decrypt code in order to understand it then the language does it wrong. Math works like that and I never understood why they called variables "x" instead of "potatoes" or "time". It's simply non-descriptive.
I don't know if you can write code that is as descriptive as code from an imperative language, but the FP community doesn't encourage it either.
map/zip/range isn't cryptic once you get used to it. You start thinking them as additional CS concepts, which you just apply in one "chunk" to problems. This is working-as-intended: it's you learning how to think at a higher level so that you can solve more complicated problems quickly. Once you've done this you can actually "back port" this knowledge to traditional programming languages: I often think of Java or C code in terms of "Oh, this is a map" or "this is a fold over a tree traversal".
There are a bunch of other, legit readability problems with typical Haskell style: the fetish on single-character variable names is just nuts (it comes from math, where it's customary because mathematics culture arose before computers and autocomplete), and once you get into point-free style, combinator libraries, and monads/arrows things really get nuts. In general I've found that abstractions should only be used when they're re-used frequently, so you can internalize them, and Haskell tends to encourage rather overzealous abstracting. But map/zip/range show up all the time in typical industrial programming, and learning how to think of it as a unit frees up brainpower to think about higher-level algorithms.
There are many common operations in programming, and it's worthwhile building a consistent syntax for them. Over time, as one layer of abstraction solidifies it's possible to see common patterns at the next level up.
It saves brainpower because you you don't need to analyse the logic within the structure to understand what the operation is intended to produce.
E.g. in the old days:
10 I=1
20 PRINT A[I]
30 I=I+1
40 IF I <= 10 THEN GOTO 20
You need to parse the logic to realise "Ah, this is a for loop". The I variable and the IF statement are bookkeeping code that doesn't have any relevance to the actual effect you're trying to produce.
This construct is common enough that the for-loop was developed. Likewise with the if/else construct and others.
The old fogeys would say "we don't need this structured programming nonsense, gotos are more flexible. I can easily look at this and understand what's going on".
Structured programming is now widespread enough that we don't think of it as anything special, it's just part of "programming" in general.
Now there are several common operations that we do when looping over a list of items. Things like maps, folds and gathers are just building another level on top of structured programming, hiding the bookkeeping code and making similar operation similar, so you can concentrate on the unique aspects of the program.
What to you mean by "cryptic"? Something you struggle with? An abstraction?
You're not used to maps, folds, and filters (the bulk of sequence comprehension), so they don't free up your brain power. But seriously, they're not complicated, and using them instead of regular loops often reduce the amount of code by a factor of 3 to 5. Simple code, where the same idioms come back over and over —just like in regular loops, only shorter.
Don't tell me that doesn't free brainpower, eventually.
Cryptic to me means that I have to translate (decrypt) the code in order to understand it. I have no problem when list comprehension is used to achieve a simple, single goal. But when I see whole algorithms implemented with list comprehension, I find that rather stupid. Amount of code is not my most important metric when writing code. Time is. I don't care if code is 3 to 5 times smaller when everybody that encounters it need 10 times longer to understand it.
Assembly was cryptic in the same sense: you had to translate it to get to the "real" machine code.
Fortran was cryptic in the same sense: you had to perform even more complex translation to get to the "real" assembly.
In other words, you're doing it wrong. You think in sequential terms, loops… and are translating list comprehension to that. Just don't. There are more direct ways. In a list comprehension, there's generally a filter part, and a map part. While they are interleaved during the execution, they are logically separate, and you should think of them that way.
I once specified the processing of a sequence of data as a pipe of maps and filters. A colleague came to me and told "how can you waste all that memory, generating all those lists around?". Dude, this is a specification of the end result, not a computational model. Of course I won't generate 10 big arrays.
Simply put, you need to separate the "what" from the "how".
Functional orgami is hella hard to debug. Their is a reason functional programming relies so heavily on equational reason and pure FP relies heavily on static typing: the alternative, actually debugging programmers, is so painful that you just want to avoid that at all costs.
A loop is way easier to debug than a filter or a map, you just step through it. Who cares about code length? Haskell doesn't become a usable language until someone comes up with a decent dataflow debugger, if that's even possible.
I don't agree with this. Usually, the typing does half the debugging for you and when you have a real bug (as in, the program does something but not what you intended), you debug at the reasoning level, not at the "is there an overflow here?" level.
Some people tend to reach for the symbolic debugger the instant their program behaves funny. I hear Haskell is at a disadvantage here, being non-strict and all. Though I wouldn't know, I never tried Haskell's symbolic debugger.
> Some people think to program, others program to think.
That one needs to be framed on a wall.
I'm definitely in the first camp (think to program), and have no problem with paranoid type systems, and I seldom need a debugger. Now I understand why other people do.
The types have to do most of the work, because Haskell debuggers aren't that great in the face of its laziness, and making your code strict for debugging purposes can lead to some heisenbugs.
The mantra "well typed programs can't go wrong" actually means "our well typed programs can't go wrong, or we are so screwed."
A loop is way easier to debug than a filter or a map, you just step through it.
Why can't you just step through the function being called by map/filter? You set a breakpoint on the function and examine the values when it is called.
Sometimes you don't have a line to break on, sometimes the code that is actually mapping and filtering is very generic and used in lots of places, sometimes you simply lack out per context when the break occurs because of laziness. When control flow becomes more indirect, debugging becomes more difficult, and functional orgami is all about making control flow indirect to rather emphasize dataflow.
Someday, someone might discover how to do good dataflow debuggers that could work well for time-intensive (read: stateful) programs, and in that case, I would be happy to indirect my control flow a lot more than I do. But no one has figured out how to really do that yet.
Why "x"? It's idiomatic, like using T for a type in C++ templates, argc and argv for the inputs to main in C, making the second returned value in a Go function the error and calling it err and not error or e or er or failed, using the type "t" in OCaml to specify "the" type a particular module is defining (I think...), or anything else. X, y and z in maths are idiomatic; there's no good reason they're used instead of a, b, c, or LR, UD, FB (left-right, up-down, front-back) for coordinates except that that's what people are used to, and sticking to the convention makes code/equations easier to follow because your brain is used to seeing x used a certain way, so you don't need to keep checking to see what it is when you see it in longer code/equations.
Many haskell functions operating on lists are described in terms of the first element "x" and the rest of the elements xs (exes or "the rest of the x's"). It's a common convention used because we have no idea what x might be, all we know is that, in this case, elements of the type that x is can be ordered. This means that one function works on lists of numbers, letters, string, lists of numbers, booleans, etc. Basically terse names like that are used because many haskell functions are very general. We could have decided on (hd:tl) or something, but there's something nice about stating that there is one value x and some values which are also x's.
You have to remember these are not features of the language, they are the idiomatic styles that are built up by the users of the language. Haskell's community encourages writing short code which is clear once you understand whatever abstractions are being used (Applicatives, Monads, lists, curried functions, type classes and so on). This is in some ways the essence of programming, building abstraction upon abstraction to make beautiful, "obviously correct" code. Haskell allows very (cognitively and syntactically) cheap abstraction, so they're used everywhere.
You complained about having to "decrypt code" in order to understand it, but this is true of any language; you may understand the keywords and how to put things together, but you won't get far if you can't get used to the idioms and conventions used by others using the language.
User-defined, powerful operators are the most important feature that make programming in Haskell feel so foreign. Yet, since they often require the programmer to sort of grasp a model of the thing the program is trying to accomplish, once you understand the operators (e.g. parser combinators) you have a rather deep understanding of the foundation for this particular program and the rest of the code is expressed very concisely and (sometimes) reasoned about easily.
Regarding the short variable names in math: They are supposed to be written and, more importantly, manipulated by hand and so short notation is very important.
I for one, write code under the assumption that the reader will have to decrypt it in order to understand it. Therefore I postpone implementation details until the very end. This leads to code that outlines the logic in a fairly readable manner. Of course the implementation details are still code, but at that point there is so little code that you will understand it in no time. The Haskell examples of elegance I've seen so far seem to cramp so much responsibilities in so little code, yet nobody seems to bother about the Single Responsibility Principle.
I like operator overloading, but I use them for implementation details, not to keep the number of lines small.
The downside is that I have a deeply nested programming structure, which can be unfamiliar for people who churn out 500 lines of bare implementation details in one function.
My criticism towards math goes further than variable naming. The language of math is non-descriptive and anyone accepts it with the reasons that:
a) That's how it's always been.
b) It's short and once you get used to it it's easy.
But this just keeps people who struggle with the language of math to embrace and love mathematics.
I don't say I have a better solution, but I say that we can get in programming right what's wrong in math: a descriptive language with a low entrance barrier.
You get used to it, more or less. It is similar to naming your variables i,j,m,n,x,y, or using bash | or > or >> ... you get used to, that in haskell x:xs refers to head and tail of a list.
Yeah, this is why I'd bet a lot on Go's success. The nice thing is that once you get "C with lambdas" most of the FP abstractions can be brought in.
...what "industry" doesn't like is "deep thinking" in general and anything else that can make programmers less replaceable and interchangeable. The fun thing will be when they'll realize that this is exactly what FP can bring :) ...less side-effects means less time for a programmer to "load a codebase-part into his working memory" and start working productively on a new project he's never seen before.
And as a programmer too I tend to like languages that make me replaceable: it's always fun to be able to jump from one project to another and be able to quickly "load it in your mind". Paradoxically, both "retarded OOP" languages like Java, "retarded dynamic" languages like Javascript and "fundamentalist" languages like Haskell give you this. Anything in between, like Ruby or Lisp, forces you to first to load someone else's pseudo-DSL into your mind before being able to start doing productive work on a new project. Dunno about "hybrids" like Scala though... maybe they are a solution, maybe not.
EDIT: 'more' -> 'less' in first sentence, sorry... dunno who upvoted before the edit as the message gets kind of reversed :)
You know when toddlers try to put a round peg in a square hole? that's how it feels using functional programming in a turing-machine-like CPU. It just don't fit.
If you are far away from the peg and the hole, you use a robotic arm with high strength and poor sensors, and you have blurry vision (this would be the equivalent of the mindset of a high level programmer that lives far away from actual hardware, and I "ashamefully" include myself here), all pegs are pegs, all holes are holes, and the trusty robotic arm dutifully forces any peg into any hole, regardless of their shape :)
When you eyes and mind swim in weird Javascript architectures all day, with 70% of stuff happening in the browser and the other half in a high level server-side language VM, monads in Haskell don't feel any less natural than anything else. That's why you see a lot of things like 'lisp to javascript' or 'haskell to javascript' compilers, because at this level, so far away from the actual hardware, the shapes of the pegs and holes don't matter that much (because trusty VMs fit anything into anything) and they are too blurred to distinguish anyway...
> However, in practice, people seem to just want "C with Lambdas" languages like Go.
Most likely because that is what is desired by companies that see developers as replaceable cogs, that they can change at will and off-shore to far away galaxies.
Languages with better expressive power require people with skillets they aren't willing to pay for and harder to replace.
The "industry" took OCaml and built F# to make it possible to leverage more of existing libraries and frameworks and make it more approachable - the thing still did not take off. Unfortunately the tools are still missing (e.g. automated refactoring). The academics who are fond of functional languages unfortunately don't like real-world messy things, such as proper IDE support. I personally would have chosen F# over C# had ReSharper for it been available. But not even Roslyn is...
i would rather have a mix-n-match of different paradigms based on the task at hand. here is something that works best with an imperative style so let's just use it, for something over-there functional style is best suited, rule-based stuff will be exactly right in this instance, let's use that etc. etc.
if you have not seen sussman's 2011 strange-loop talk "We Really Don’t Know How to Compute!", please do, it is quite enlightening (whatever that means)
I think the key bit of the title is "Algebra of Programs". This is a piece about being able to calculate programs. In section 12, Backus goes into some detail on how this construction makes algebraic reasoning easier and gives some specific examples. While it is not required to have a pure FP system to have a language that can be reasoned about algebraically, introducing arbitrary ad-hoc iteration will certainly destroy those algebraic properties.
I think this ties in well with Erik Meijer's essay from a few days ago[1]. If you are trying to produce a framework for mathematical reasoning, it does not make sense to allow arbitrary exceptions. As a species, humans are pretty new to this whole computing thing, so I would agree we don't have it figured out yet. However, over the last 5000 years or so we have developed a shockingly effective toolkit for reasoning about arbitrarily-defined abstract objects and I don't think it is unreasonable to try to bring those tools to bear on a newer class of abstract object, that is to say programs. The cost of this is that we have to figure out how to formalize our ad-hoc methods. This will be painful, but every engineering discipline does it. In essence, formalized design methods applied to practical problems are the core of engineering practice in general. For example, I think software engineering right now is in the same place as electronic filter design was in the 1920's. We have methods that work, given enough design effort, but our results are brittle and it is very difficult to make changes to working systems without introducing problems.
Note: I am blown away by Sussman's talk every time I watch it, but I think throwing out math as a tool for understanding computing is very premature given its success as a tool for building and understanding abstraction, especially given that computing as a field started as an attempt to understand some deep questions about the foundations of mathematics.
"but I think throwing out math as a tool for understanding computing is very premature given its success as a tool for building and understanding abstraction"
But the problem with mathematics is that it doesn't deal with time. This may (in a sapir-whorf fashion) be limiting our understanding of the universe (see Lee Smolin's Time Reborn). But even if the universe is actually timeless in many circumstances it still does not suit us to model it like that. We can have some timeless physical law expressed mathematically (say F=ma) and if we know all the initial conditions in a fairly pure environment we can predict the state of the system at any time. But this kind of system is useless in many real world situations. For example we don't build a control system for a robot or a car based on this kind of thinking. We don't try and predict the state of the world. We just treat it as a stateful system that changes and we keep reading those changes and then try and behave accordingly - Its all I/O and state. Similarly our brains in order to be efficient do hardly any calculation, instead its a massive cache against which we pattern match (see "On Intelligence"). As Leslie Lamport's state:. "Computer scientists collectively suffer from what I call the Whorfian syndrome the confusion of language with reality. Since these devices are described in different languages, they must all be different. In fact, they are all naturally described as state machines. "
especially given that computing as a field started as an attempt to understand some deep questions about the foundations of mathematics.
I believe that computing started as an attempt to solve real problems, and maths just happened to be the one that people wanted to work on the hardest because, quite frankly, no one wanted to do arithmetic and algebra all day long. A "computer", just like "calculator", used to be a human.
Here's the talk[0] for anyone wondering; I'm watching it now.
Thanks for referencing it, glad I watched it.
Edit: So far this is a talk comparing computer systems to the human genome in a somewhat abstract manner. Sussman is the creator of Scheme and wrote SICP.
It is funny how this paper like the writings of Dijkstra is widely cherished, while its attitude and conclusions simultaneously are completely ignored. Seems to me that people simply really like to complain about the current state of the matter, how dirty programming is and how everything is inelegant just to get back to churning code a minute later using exactly the style criticized.
People like Backus and Dijkstra really wanted to prove theorems about programs and do formal derivations like they were used to do in mathematics, that's practically all they cared for, as far as their writings go. The "liberation" is in fact an act of bondage, an attempt to limit programming techniques to a narrow range to try to get all the noble benefits of mathematics, which is a priori assumed to be the best way to go about reasoning. It's really ironic in the case of Dijkstra, who writes about how people cannot appreciate "radical" novelties and instead keep old mental habits, and then proceeds to argue how programming is just a branch of mathematics.
I wonder how many people who mention those papers as cornerstones of CS actually prove their programs correct on a daily basis or derive them from "axioms". I actually think many people in the formal methods camp had a very narrow and limited vision of what programming is and what it will be become, and as a result turned out to be very much wrong about the importance of proofs in programming. Some of them actually admitted it:
In the end, reducing all programming to formal manipulations of this kind turned out to be as successful as the ideas of axiomatization of biology. Formal methods are useful in mission-critical software, functional programming penetrated mainstream languages and is interesting in its own right, but even its proponents hardly go about writing programs the way Backus imagined; mathematical theories of programming turned out to be very limited and yield poor crops compared to the mathematical theories that turned out to be successful, hardly any new insights over what was found earlier by dabbling were found, and that is that. I love math, but it seems that programming, like biology, is actually richer than math in some sense. Consider the example Peter Norvig gives in "Coders at work": how do you prove Google is correct? You immediately run into issues with the very notion of correctness, not everything can be convincingly formalized to the last detail, and we build more and more of those "fuzzy" systems, just consider the rise of machine learning and data mining in the last years.
I see no reason to go around pretending programming didn't live up to the noble vision of the ancient masters. The masters were frequently wrong (no shame for they were pioneers of the field and nothing was known), and we simply moved on.
> Dijkstra […] then proceeds to argue how programming is just a branch of mathematics.
Which it is.
In a trivial sense, programming languages are formal systems. Even when poorly specified, the computer they run on is a formal system.
In a less trivial sense, we have the Curry-Howard correspondence.
In a very real sense, programming language designers have denotational and operational semantics.
Fuzzy systems need not get rid of mathematics. They just switch from first order logic to probability theory (or a computationally tractable approximation).
Ignorance of basic mathematics is why so many fools believe lambdas or monads are hard to understand. It feels like we're scared of abstractions. For instance, we solve linear equations every time we go to the grocery and pay cash. Yet being presented with those linear equations as such, get us running away screaming into the night.
---
Programming is applied math, period. The question is, which kind of math do we want to use? Which are the more useful notations, formalizations, theorems? How does all that relate to the old math?
Computers are formal systems as much as an alternating electrical current is a complex number, same with programming languages, even though both programming languages and formal systems can be viewed as abstract entities. Technically speaking all that can be said is that certain programming languages can be models for certain formal systems, and there is a big difference between being a model for a formal theory and something simply being only a formal theory:
Programming language designers of most popular programming languages have no clue about neither denotational nor operational semantics and make use of no formal theory whatsoever.
Anyhow, I do not deny the importance of various kinds of mathematics for programming, in some selected places and in the sense of writing programs that do mathematics. I am saying two things:
- The attempts so far to turn programming itself into a single mathematical theory have failed miserably. Can you name one really important algorithm that was discovered by doing derivations in a formal axiomatic theory of programming? There is the "Algebra of programming" theory by Bird, the "Elements of programming" by Stepanov, but nothing particularly striking seems to ever come out of it, only proofs of things we already know.
- There are hundreds of aspects of programming that have nothing to do with mathematics and turned out to be of far bigger importance than finding effective means of formal correctness proofs of programs. To give one example, programmers have to work in teams with the size of problems we are dealing with today, something the formal methods people never seemed to address much, and issues with communication and coordination cause much more problems than simple logical errors in algorithms.
> Programming language designers of most popular programming languages have no clue about neither denotational nor operational semantics and make use of no formal theory whatsoever.
That may explain why so many of our popular languages have several glaring flaws. Java doesn't support tail calls dammit! We had to wait for scheme to finally have lexical scope! C++ is impossible to parse!
> The attempts so far to turn programming itself into a single mathematical theory have failed miserably.
Wait, what attempts? I've read many Haskell papers, and did not stumble upon such a thing.
Bold, claim, considering all the C++ parsers out there that work just fine... The fact that you need to code a parser by hand doesn't mean that the language is impossible to parse at all. And even for an easier to parse language, if you want to write a parser that spits error messages that make any sense to most users, and that may use some heuristics to guess the programmer's intend in order to give even better error messages, you will have to code it by hand anyway.
Okay. Though if it's not a peer reviewed paper, it doesn't exist. Anyway, I have a more positive outlook: those "failures" are just the beginning. We'll build on those. We failed to fly for a long time, for instance.
Actually Dijkstra also was a proponent of deriving programs, it's discussed in his "Discipline of programming" and 30 years ago there was some interest in this, with lots of papers published, but it never gained much traction:
I disagree. Computer Science might be a branch of mathematics, but computer science is also just a part of programming. Programming also involves things like software design and engineering and human computer interaction which are not a branch of mathematics.
Programming is like building a bridge. Yes lots and lots of math is involved in building a successful bridge, but claiming that bridge building is just a branch of applied mathematics is kind of missing the forest for the trees.
Not quite. When you build a bridge, you'd better doing according to spec, or it will collapse. The specs better be sound according to the known (mathematical) laws of physics, or it will collapse. Lot's of theorems to use, and lots of proving your design is sound.
Software is often more lenient, and as such less mathematical than bridge building.
But that doesn't help my point.
How would you go about proving a mathematical conjecture? You think, you talk to colleagues, you try approaches, you design tools (notations, programs that do math…). That's less formal than you might think. Heck, the proof you provide in the end is often not even machine checked! Coq users are often more rigorous than the most die hard mathematician in this respect.
Just like software writing and bridge building, the process of doing math is not mathematically formalized. In that sense, there is a lot more to math than math.
Software practice is more lenient than bridge building practice, but only by virtue of being so new as to escape regulation. There's nearly four fucking millennia worth of precedent for regulating construction because people die from blunders.
The lack of accountability for the consequences of programs is unlikely to remain the context for practicing development. But even 25 years ago The Morris Worm was a treated as a felony and the list of actions for which there is criminal or civil liability has only grown. At some point normal programming activities will entail the risk of such liabilities to a degree that programming entails a formal standard of care like architecture and civil engineering and orthopedic surgery.
Lot's of theorems to use, and lots of proving your design is sound.
If you've actually tried to build an actual bridge you'll know that that is just a small, but very important, part. Getting the structural math right is necessary, but far from sufficient, for getting a bridge built. You've also got bridge and landscape architects designing how to make the bridge work in the existing landscape, you've got traffic and city planners working on exactly where the bridge should start and end and which roads it should connect to. You've got traffic analysts trying to work out the traffic flow implications on the large area based on the different placements of the bridge. You've got building engineers that are trying to work out how to build this thing on time and on budget. You've got logistics people working on designing the building schedule so that the right amount of people and building materials get to the right point at the right time. And then there are the finance people and the insurance people doing their magic money dance in background. Oh and lawyers arguing about land use and building permissions and whatever else lawyers like to argue about. And each of these decisions feed back into the structural calculations, and the results of these calculations feed back into all these parts and so on. And yes there is math involved in many of these steps, but that doesn't make the whole process a field of mathematics. Not everything that uses math is mathematics.
PS: While I've never had the word "mathematician" on a business card, my Masters was in mathematics and much of the work I've done has involved modeling and data analysis, so I know in broad strokes how math gets done.
Of course not. And I never intended to say so. I originally said that "programming is applied math" (I insist on "applied"). Because if you ignore the math behind programming, you're running into trouble.
Same goes for bridge building, by the way: you can't ignore math. It's like Dracula: you may not see it often, but it is ever present, and influences everything. (I'm not talking about the laws of physics here, but about a bunch of people doing math, then using the results to make far reaching decisions.)
Saying that programming is a branch of mathematics is a stronger claim, but not such an outlandish one either. After all, it is all about the manipulation of a formal system. But I wouldn't go that far. Rather, I'd say computer science is math (not applied, just math).
Only a bit of math goes into building a bridge, though. It's not like the construction workers are continuously solving differential equations. Even when the specification is being written, math is just a tool to deal with constraints that are not identified using math. Quite similar to programming actually.
> Even when the specification is being written, math is just a tool to deal with constraints that are not identified using math.
I beg your pardon? You have to model the weather, come up with a whether distribution over the years, a probability of collapse each time you encounter such and such circumstance… The constrained are not only identified using math, they're often pinned down with math.
> It's not like the construction workers are continuously solving differential equations.
Sure. But when the differential equation tells them to screw that bolt here, they better screw that bolt here, or compromise the integrity of the bridge.
Right, but how many mathematicians does it take to build a bridge? Probably just a few engineers, and the process is probably very standardize. That architect probably isn't using much math in his/her design. Software is similar: there is some math involved, but it is often abstracted away and you might not ever be exposed to it.
It feels like we're scared of abstractions. For instance, we solve linear equations every time we go to the grocery and pay cash. Yet being presented with those linear equations as such, get us running away screaming into the night.
Because it is far easier to see value in solving real-world problems than to think in terms of just abstractions; and at the end of the day, real-world matters. Computers were invented for solving problems in reality, and that is one thing that should always be kept in mind when programming them. Abstractions, while powerful, also have a cost, both mentally and in terms of computing resources, and the latter is definitely finite, so being scared of them is both natural and reasonable.
To put it bluntly, how many programmers don't know what "Curry-Howard correspondence", "first order logic", or "denotational and operational semantics" are, and yet have written hugely useful and popular applications? I argue that there is very little math and theory that one must know to do great things with programming - arithmetic and algebra are sufficient. So I believe we may see some truly wonderful things when we stop propagating this notion that computer science is hugely abstract maths, and instead focus on its more concrete aspects. (I touch on this point here too: https://news.ycombinator.com/item?id=7672252 )
One way to look at this is to consider the situation with the "science of dealing with numbers" before mathematics gained a rigorous foundational basis. Sure, we do a lot of code but likely not as efficiently and not in an optimally systemic manner.
So, yes, you can do some things with "numbers" without theoretical mathematics.
You know when toddlers try to put a round peg in a square hole? that's how it feels using functional programming in a turing-machine-like CPU. It just don't fit.
Yup, I agree. Functional languages failed in part because they modelled the machine poorly (Richard Gabriel has some reflections on Lisp in this area).
But the funny thing is that hardware has changed! Imperative programming languages are now the square peg in the round hole :)
Multicore machines are going to elaborate lengths to maintain the illusion of a uniform address space. But if we programmed with message passing and heterogeneous processes, then our programs would have more mechanical sympathy for the machine.
Shared memory and locks are basically the result of not wanting to disturb too much source code when converting from a single-threaded to a concurrent/parallel program. But it results in poor performance and scalability, not to mention untestable and unmaintainable programs. You can look at the evolution of multicore scalability in the Linux and FreeBSD kernels, or Python and Ruby GILs (coarse grained locks in a Turing machine model), for examples of this.
The other thing that has changed is that our hardware is distributed (not just clusters, but also client-server). Networks are fundamentally unreliable, and that means that idempotency of subprograms is a very important property. Idempotency is of course a word from the same area of mathematics that functional programming comes from (abstract algebra).
The other algebraic property that is important in distributed systems is commutativity. This basically has to do with physics[1]. Commuter[2] is a nice project which addresses commutativity in interface design.
It's not an accident that MapReduce and all the newer big data frameworks are based on the model of functional programming. They are using the imperative model at the scale of a single machine, where its appropriate, but the functional model at the scale of the cluster, so subprograms can be retried and executed in any order.
The alternative to explicitly thinking about these properties in your program design is to (only) use slow state machine protocols like Paxos. You could naively apply this transformation to your sequential programs, but you will be making very poor use of the hardware. There is a reason that they are only used for very small bits of state in distributed systems.
tl;dr Distributed systems (multicore included) are not Turing machines. I see a lot of bugs that are a result of people in the imperative mindset not understanding this.
The MapReduce use case is quite narrow, we also have replicated storage systems that require, as you said, paxos; many HPC loads are using CUDA these days, which, even though heavily based on SIMD, is very imperative. As soon as you want iterative computation or long running incremental computation on streams...you need to worry about fault tolerance again, and state becomes very useful.
You can leverage commutativity without going functional...heck, that's how most physics engines work and they are very far away from FP.
I'm not only talking about MapReduce; I'm saying there are ideas from functional programming that have more affinity for the underlying hardware than state machines. This is only going to get more important in the future. Right now we're straddling the two worlds kind of awkwardly.
State is useful; however exactly as in "traditional" functional programming, it should be used sparingly in distributed systems. State requires very special handling and thought. Statelessness or purity is the default. Clusters have a tiny bit of state and lots of stateless workers, just like a Haskell program has a tiny bit of state and lots of pure functions.
To be clear, I don't think Haskell makes sense at the single machine level. (I personally don't want to program in it.) I'm saying that the ideas are more appropriate at the level of architecture and not code.
I think you are talking about a distributed calculation. This is not really representative of all distributed systems. Telecom software or engine managment systems don't make much use of map-reduce for example
the von neumann architecture is the internal combustion engine of computing. we've made it do some pretty amazing stuff, but it'd be awesome to try something new.
I think that's a very appropriate (if oblique) 'car analogy'.
To extend it further, one might consider an alternative to the ubiquitous IC, the steam engine: external combustion, clean(er), more efficient, multi-fuel...
Aside: steam cars were actively developed throughout the 20th century, even advancing to a sports car in the 1960s. The best article I read on this subject was 'Steamer Time?' by Wallace West, in the September 1968 issue of Analog Science Fiction.
Fittingly, the same article mentions the concept of 'steam engine time', a term coined by Charles Fort, who "contended that the steamboat was invented only when economic, political, scientific and engineering developments combined to usher in steamboat time."
Ivan Sutherland explains it best when he says that concurrency is not fundamentally hard. The problem is that we constraining ourselves to the fundamentally sequential Von Neumann architecture. https://www.youtube.com/watch?v=jR9pAaQlVRc#t=267