Tuesday, November 30, 2010
Thus, programming advice of the DTSTTCPW variety (i.e. 99% of programming advice) always makes me a bit uneasy. Instead of thinking - shouldn't I just be crankin' out code, putting it online, and blogging about it on LJ?
But a couple of days ago I made an observation: almost all programming advice applies to applications, but what I'm mostly working on are systems. Since then, I'm sleeping better.
As Dr. Theodor Holm Nelson says, you can't get to the moon by piling up chairs. You may be able to learn something about an application by cranking out a quick and dirty prototype. But for systems, prototyping seems futile. Either your ideas work, or they don't, and a quick gedankenexperiment will usually be enough to find out.
Of course, I don't want to denounce experimentation as worthless. You have to know whether your ideas will be useful and work on really existing computers. But if your system is so removed from reality or complex that you're unsure about that, you're probably doing it wrong.
Take Unix pipes. There's an early memo about the need for pipes from 1964. And in 1972, pipes appeared in Unix. Do you think they spent 8 years DTSTTCPWing? I don't think so. I think that in these 8 years they spent a lot of quality time thinking about the issue, and when they had the right idea, they just knew it was right, and went ahead and implemented it.
So, to all systems programmers out there: most programming advice isn't for you. Relax, and take the time to find the right ideas.
Thursday, November 18, 2010
|L1 cache reference||0.5 ns|
|Branch mispredict||5 ns|
|L2 cache reference||7 ns|
|Mutex lock/unlock||25 ns|
|Main memory reference||100 ns|
|Compress 1K bytes w/ cheap algorithm||3,000 ns|
|Send 2K bytes over 1 Gbps network||20,000 ns|
|Read 1 MB sequentially from memory||250,000 ns|
|Round trip within same datacenter||500,000 ns|
|Disk seek||10,000,000 ns|
|Read 1 MB sequentially from disk||20,000,000 ns|
|Send packet CA->Netherlands->CA||150,000,000 ns|
For more details: Agner's Software optimization resources.
GADTs are at the cutting edge of functional programming and become more widely used every day. Nevertheless, the semantic foundations underlying GADTs are not well understood. In this paper we solve this problem by showing that the standard theory of datatypes as carriers of initial algebras of functors can be extended from algebraic and nested data types to GADTs. We then use this observation to derive an initial algebra semantics for GADTs, thus ensuring that all of the accumulated knowledge about initial algebras can be brought to bear on them. Next, we use our initial algebra semantics for GADTs to derive expressive and principled tools -- analogous to the well-known and widely-used ones for algebraic and nested data types -- for reasoning about, programming with, and improving the performance of programs involving, GADTs; we christen such a collection of tools for a GADT an initial algebra package. Along the way, we give a constructive demonstration that every GADT can be reduced to one which uses only the equality GADT and existential quantification. Although other such reductions exist in the literature, ours is entirely local, is independent of any particular syntactic presentation of GADTs, and can be implemented in the host language, rather than existing solely as a metatheoretical artifact. The main technical ideas underlying our approach are (i) to modify the notion of a higher-order functor so that GADTs can be seen as carriers of initial algebras of higher-order functors, and (ii) to use left Kan extensions to trade arbitrary GADTs for simpler-but-equivalent ones for which initial algebra semantics can be derived.Mentioned by Oleg in GADTs in OCaml.
Wednesday, November 17, 2010
From the paper Boltzmann Samplers for the Random Generation of Combinatorial Structures.
While we're at it, Z-order space-filling curves are hot:
All of the mappings we have so far from real-world problems to software realizations are either bad (in the sense of imprecise and convoluted) mappings or map to pretty bad models (in the sense that the models are either devoid of semantics or have semantics too complex for the working programmer to really understand). OO "works" because it is the least-bad and least-incomprehensible mapping that has been identified to date.The thread is also notable for David Barbour's treatise Being poor at modeling is essential to OOP:
The poor modeling facilities of OOP are caused by essential properties of OOP. These essential properties include encapsulation and message-passing polymorphism. These are the same properties that make OOP powerful for configurable modularity, scalability, and object capability security. ...
I do not believe that modeling 'tax reports' in OOP is something that we would 'want' to do. Ever. We might need a tax-report value object as an artifact of the dataflow system (e.g. if tax-reports are dumped into the system as complex form objects), but that's just plain-old-data and could be done just as easily in functional or procedural, and is really not 'OOP'. ...Your comments (modeling the situation, wanting to model the 'tax reports' explicitly even when it is unnecessary, etc.) and those like them (being extremely prevalent in OO books and the education), are what lead people to start each program by writing a business simulator when what they want are business data processors.
Thursday, November 11, 2010
Here's a list of some papers I've found worthwhile or just found, and not read yet...
Fun with Type Functions (slides). Oleg Kiselyov, Simon Peyton Jones, Chung-chieh Shan. 2010.
How to fake it with Haskell's recently added type families. But Haskell increasingly looks horribly impure: it's not just that every type's inhabited by bottom, type-level programming is untyped! I think they really should work on their purity! ;) Mentions Ωmega's kind system - my prediction: typed type-level programming is coming to Haskell soon.Proof-assistants using dependent type systems. Henk Barendregt, Herman Geuvers. 2001.
Recommended as a great intro to all things dependent typing. Not by me though, as I still have to read it.ΠΣ: Dependent Types without the Sugar. Thorsten Altenkirch, Nils Anders Danielsson, Andres Löh, Nicolas Oury. 2009ish.
What's under the sugary hood of dependent programming languages. For when I develop a dependent language - because I'll have to.
- A Tutorial Implementation of a Dependently Typed Lambda Calculus. Andres Löh, Conor McBride and Wouter Swierstra. 2009.
Also frequently mentioned as an intro to dependent types.Verified Programming in GURU. Aaron Stump. 2009.
A book on dependent programming with a focus on verification.Generic Programming with Dependent Types (part II, part III). Stephanie Weirich. 2010.
Slides focussing on the extra expressivity afforded by dependent types. Agda.An Epigram Implementation. Edwin Brady, James Chapman, Pierre-Evariste Dagand, Adam Gundry, Conor McBride, Peter Morris, Ulf Norell, Nicolas Oury. 2010.
The 300-page literate Epigram (2?) implementation.