I’ve had learning the computer language Haskell on my to-do list for some time. I’m actually stepping up to learn it now, thanks to a temporary lull in my other activities and a vicious cold that has left me disinclined to strenuous work. I may associate Haskell with the taste of zinc gluconate for the rest of my days; both have an astringent and medicinal quality and produce fervent claims of effectiveness about which I am moderately optimistic but which I have not yet personally verified.
Haskell is very obviously a language built by mathematical logicians for mathematical logicians. Category theory lurks behind it in the same way that the lambda calculus lurks behind LISP. The following is an effort to make Haskell’s way of carving up the world intelligible, written partly to clarify my own thoughts.
Haskell is built around a handful of powerful primitive concepts and a pons asinorum. The most pervasive of these, purely functional programming without side effects or variables, is generally described in introductions to Haskell as the most difficult barrier for most programmers arriving from conventional imperative or OO languages like C, C++, and Python. And yes, if your mental model of programming is all about for-loops and static variables — or, for that matter, objects! — learning to think in Haskell is going to be quite a wrench.
There are reasons to make the effort. Haskellers (Haskellites? Haskellians? Haskellators? Haskelletons?) maintain that imperative programming relies heavily on side effects that push proving the correctness of programs to somewhere between impractically difficult and impossible. They also like to point out that side effects make programs difficult to automatically parallelize across multiple processors, an increasingly important consideration as multicores become the rule rather than the exception.
Both are solid arguments. It’s less a wrench for me to give up imperative thinking than for most because I’m a Knight of the Lambda Calculus from way back — and, while LISP is not a purely functional language, anyone who programs seriously in it will develop a feel for the functional style. Accordingly, while hanging out on the #haskell IRC channel I recommended to someone newbier than me that he might consider learning some LISP first and then coming back to Haskell. None of the hard-core Haskellians on the channel demurred, and I think this is probably good advice in general.
Now I will admit that the preceding paragraphs contained two fibs. First: Haskell does have variables, sort-of kind-of. But such a “variable” can only assigned once and the value of the variable is a promise to re-evaluate the expression on the right side of the assignment whenever the variable is evaluated; it behaves more like a safe macro or an Algol-60 call-by-name than like what people used to modern imperative languages call variables. Second: it is possible to define operations that have side effects, and things that have the behavior of real variables, using a construct called a monad.
I’ll get back to monads, but before I do I should introduce two other fundamentals of Haskell: static typing and lazy evaluation. Static typing shouldn’t be a strange concept to anybody who’s ever written in a compiled language like C or Java, but Haskell pushes the concept to some sort of logical limit. Variables need not have explicit types (they’re implicitly typed by the expression they’re shorthand for), but there’s a syntax that allows you to attach type signatures to any function, and the compiler does type inference from those. This has two consequences: it makes efficient compilation of the language possible (which is unusual for a language at Haskell’s level of abstraction), and (more importantly in the Haskell view of things) the type annotations assert invariants that can be used to prove the correctness of the program.
User-defined types are (more or less) the values of type-valued expressions (it’s actually more complicated than that, but thinking about it this way is a useful point of entry). The single most delightfully weird detail of Haskell I’ve run into so far is this: you can have type-valued variables, and write type-valued expressions that are recursive! For some types, such as trees, this is the natural way to do things.
Lazy evaluation is easier to understand. All it means is that the value of an expression is not computed until it’s actually needed by the caller; evaluation runs outside-in rather than inside-out. If you’re familiar with the idea of a closure from Scheme (or another language, such as Ruby, that has borrowed Scheme closures) it helps to think of Haskell expressions as returning closures. When the program runs, the outermost (main) closure is forced (evaluated); this may trigger the forcing of other closures (expressions and function calls) directly inside it, and so on through their sub-expressions which are also closures. Local color so you can sound like you know what you’re talking about: in Haskell-land, a closure is called a “thunk”.
Various optimizations make lazy evaluation efficient; notably, because expressions are (usually) pure, the closure can often be replaced by a pointer to its value and never need to be evaluated more than once. A benefit of lazy evaluation is that you can write code like an Icon or Python generator that spins forever, returning a value on each cycle, and it will only be called for the exact number of returns that the enclosing program actually needs even if the caller is itself a generator. This is one of the capabilities that replaces for-loops in imperative languages.
Even if most of your Haskell code is pure (no state, no side effects) it’s going to need to interface with a stateful world. I/O, in particular, is not pure; getting a line from your input source gives a result which will vary depending on the state of the world outside the program. Normal Haskell practice is to write your programs with as much pure code as possible and a minimum number of calls to functions with side effects (such as getting a line of input from standard input or putting a line of input to standard output). Only, because evaluation is outside in, what I/O function calls actually do is create closures that will have I/O side effects when they’re forced.
So, the question: let’s say we have multiple calls to functions generating closures with with output side effects. How do we write the code so the closures get forced in the order we want? There are multiple ways this could be done; the most obvious would require some kind of special construction that is an exception to “everything is function calls”. What Haskell uses for such sequencing is a monad.
Ah, monads. These are Haskell’s pons asinorum. Haskellers are in love with the fact that they actually behave like a recondite concept called “strong monads” from category theory; at this point in many expositions of the language the author would start waving this fact around. I’ve been a mathematician myself, I retain some grasp of category theory, and I say invoking it here is confusing and unnecessary.
A simpler way to think about monads is as a hack to turn function composition into a way of forcing the sequencing of function calls, or the functional-programming equivalent of a shell pipeline. And having said that provocative thing, I’m not going to go into the gory technical details required to make that actually happen.
I normally consider the syntax of a language, no matter how odd, to be a mere detail compared to more important things like its type ontology and how it does evaluation. But one central thing about Haskell’s syntax deserves attention: the way it uses productions. A Haskell function can be written in a sort of AWK-ish style as a series of pattern-action pairs; they’re tried, in sequence, and the first pattern to match the input fires. Falling off the end of the list yields a runtime error, but a wildcarded “everything else” production is easy to write.
Summing up: I don’t know what I’m going to use Haskell for, or indeed if I’ll ever use it at all. But the time I’ve spent wrestling with it has not been wasted; it has challenged my preconceptions, shown me some possibilities I hadn’t seen before, forced me to develop a practical grasp of some concepts like lazy evaluation that were previously only theory to me, and in general shook up my thinking. That’s valuable in itself. In How To Become A Hacker, I wrote “LISP is worth learning for [..] the profound enlightenment experience you will have when you finally get it. That experience will make you a better programmer for the rest of your days, even if you never actually use LISP itself a lot.” I think the same can be said of Haskell, and for very similar reasons.
Make sure you glance over the docs for GHC’s extensions some time early in your Haskell education, with multi-variable typeclasses and GADTs being the two most important. They greatly increase the expressiveness of Haskell’s type system. It took me a few months to find these, and when I finally did, and the experience was something like “Whoa… I know kung fu!”
Alternatively, become a Zed-hed ;)
You won’t have a problem with languages like Lisp or Haskell after that….”monads” are practically an implementation of Z’s “;” and/or “>>” expressions.
Btw, “thunk” is not synonymous with “closure” and it’s not a term unique to Haskell. A thunk, roughly, is a body of computational work that will eventually yield a value. It’s approximately synonymous to a closure that accepts no arguments. To see how the term gets used in Scheme, try grepping for it section 6.4 of R5RS.
ESR says: True. I nearly mentioned the use in Algol-60 but decided it would be merely distracting.
Hm. Sounds like a language by mathematicians, for mathematicians. Can it be understood by those whose formal education didn’t get past differential equations?
Jay, yes it can. It’ll then leave you mystified by why some of its terminology is so weird, but as Eric discovered in the case of monads, this is not really a handicap.
Genuine quote from my old logic professor: “Haskell? Oh, must be named for Haskell Curry. Good guy. I dated his daughter.”
Actually, most other languages have variables, sort-of kind-of; Haskell has variables in the true strict mathematical sense of being placeholders for a value (as opposed to mnemonic names for memory locations where values may be stored).
:)
>but as Eric discovered in the case of monads
Entertainingly, in order to get it about monads I actually had to ignore the correspondence with abstract categories. It was a distraction.
One of the other benefits of pure functional languages, that you didn’t mention, is the opposite of lazy evaluation. Because programs are tractable, it is possible to partially evaluate considerable amounts of a program at the compilation stage. By way of illustration, consider the C expression:
int bufSize = sizeof(int) * BUFSIZ;
Generally speaking the multiplication will take place at compile time not runtime for a good compiler (an optimization called constant folding.) However, because there are no side effects in pure functional code (which is to say the state is small and explicit), it is possible to do this much more extensively on pure functional languages, folding together multiple levels of function into preanalyzed functions.
I have no idea the extent to which this is actually implemented, but the possibilities are rather tantalizing.
the value of the variable is a promise to re-evaluate the expression on the right side of the assignment “whenever the variable is evaluated
This is very wrong. Haskell has call-by-need, not call-by-name. The whole point of call-by-need vs call-by-name is precisely that the right-hand side of the expression will be evaluated once and only once. This is guaranteed by Haskell semantics. And this makes call-by-need and call-by-value mutually not macro-expressible (whereas call-by-name is trivially macro-expressible with call-by-value).
ESR, I would sincerely recommend that you try out Clojure (for writing real apps, not just for the fun part). I am sure you will be amazed.
Since you said learning Haskell will make one a better programmer, I thought you might get a laugh outta this:
http://lukeplant.me.uk/blog/posts/why-learning-haskell-python-makes-you-a-worse-programmer/
Faré, unfortunately, that’s not true. The Haskell standards do not guarantee that stuff is only evaluated once (or zero times). Since there are no side-effects compilers can also choose to evaluate stuff a hundred times.
In practise all compilers force thunks no more than once.
I have similar reactions to Haskell. The language was invented by logical formalists to bring their formalisms to bear on actual programming (instead of toy scenarios). That sets the language up for a tug-of-war between practical programmers and formalists. The formal language-as-defined has some limitations that, AFAIKT, are there to keep Haskell programs “provable” rather than (necessary) to keep the language sane. But of course there’s extensions…
Haskell “variables” really are constants, in that they don’t ever “vary.” The fundamental idea is that every name has a single definition point, which makes all that delicious formal analysis possible. Of course, many of those constants are *function* constants, but that doesn’t make them vary, and they don’t have any state attached to them – which is the fundamental point.
I tend to think of monads simply as hidden-state abstractions. They’re great in that you can write higher-order code that can reason about implicit dependencies. In practice, “I’m a monad” means “I have a dependency I don’t want to be explicit about, so we’ll have to negotiate some sequencing here.” If you enjoy abstractions, then “how is I/O like list parsing?” has “they’re both Monads!” as a neat answer. If you don’t, just don’t worry about it.
Incidentally, another candidate for your “different enough to be interesting” list might be Inform 7. That’s a language for writing interactive text fiction, and obviously isn’t going to replace C or Ruby or Haskell, but it’s another language whose approach is different enough to teach you something about your “native” languages. Besides, it’s fun. :)
Cheers
— perry
Yes.
It may take a bit of self-education, but learning and becoming competent in Haskell is certainly possible for any programmer who hasn’t got himself irreparably stuck in a “blub” mindset.
Although I’m clearly not a mathemathician, don’t even like it, I’m kind of under Dijkstra’s spell, namely, that if we did it right ALL programming would be applied math. After all computers are supposed to compute stuff. Or are they?
It seems on the level of programming there are two very fundamentally different uses of a computer:
1) to compute stuff, to which the functional style is a natural fit
2) to instruct it to execute “tangible” instructions like beeping the speaker, colouring a pixel on the screen, printing an image on a printer, or read or write a database record, to which the imperative style is a natural fit.
Well it’s the last one that interests me the most because that’s my daily job ( http://en.wikipedia.org/wiki/C/AL – I’m not happy about it but money talks).
Database access is at the ISAM root is stictly imperative because it is about “tangible” instructions: dear computer, please take this index and this range in the index, read a physical file alongside the index and give me the results one by one.
You can abstract it away to a certain extent with stuff like SQL which is basically functional programming – can we say that every sufficiently complicated LISP program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of SQL? In other words: doesn’t http://en.wikipedia.org/wiki/LINQ provide 90% of what you’d ever use functional programming for in a much more palatable way? – but there will always be a level of complexity, or let’s say, irregularity where it will break down and you will resort to imperatively looping through cursors.
But wait – according to Boyce and Codd, database access _is_ math – therefore, it could be functional.
So – can we imagine such a thing as a fast an efficient Haskell(-like) database or is it some sort of law of nature that the bolts of abstacting away reading and writing indexed files will show and we MUST get imperative or sacrifice lots of performance, because it is about reading and writing physical files and whenever we are talking about twenty million General Ledger lines performance DOES count, even if it doesn’t sound very fashionable these days?
Can databases be reduced to computation or must they remain essentially instructions? Because if they could be reduced to computation they could be reduced to math and then to functional programming.
(For all I know, the reason modern SQL databases don’t quite work like Boyce and Codd wanted them to work is that whatever Boyce and Codd wanted would be too slow.)
I haven’t spent much quality time with Haskell, but I did go through YAHT and worked with the examples.
For those wanting to learn Haskell, I’d say if your primary languages are, say, C and Java, I agree with esr greatly: first learn LISP or Scheme to get the feel for functional programming. I’d also say you could probably learn Python first; I never understood LISP or other functional languages until I learned Python.
>I never understood LISP or other functional languages until I learned Python.
Really? I find that strange. Can you explain?
“Sounds like a language by mathematicians, for mathematicians.”
It’s not, unless you’re a category theorist. This is a common misconception amongst those who first encounter the general purpose descendants of primarily theoretical (aka “academic”) languages like ML, Lisp, etc. Sure the syntax is similar to some mathematical notation, but the language has quirks that no sane mathematician would have let slip in (like Monad not being a subtype of Functor, despite monads being functors *by definition*) and that the compiler doesn’t enforce the monadic axioms (which is a lot more understandable given the language itself evolved before the idea of using monads within it so graciously did), etc.
For “languages” for mathematicians, by mathematicians, you can look into the Coq proof assistant, Mathematica, Maple, Axiom, Maxima, and so on. General purpose languages are used less by pure (and some applied) mathematicians because GPLs, by default, don’t have the kinds of tools most pure (and some applied) mathematicians use. This is what gave rise to languages like R. Certainly one can implement many features of these languages in libraries for Haskell, but some are simply not convenient to use (e.g., the symbolic manipulation found in algebraic languages and the Lisp family)
In reality, I think I view most Haskell programmers’ relationship to math in a similar light as Guitar Hero players are seen by real guitarists. An excuse to seem smart by tossing around buzzwords like “monad,” “functor,”
“isomorphism,” “homomorphism,” “catamorphism,” etc without ever actually getting a degree in mathematics, or having to read long, (boring) graduate texts about category theory, or ever really understanding any of these concepts. They’re Haskell /programmers/. Not mathematicians.
There are, of course, exceptions in both programmers and their programs. But the exception is not the rule, and the average Haskell programmer is not a mathematician, just like his window manager, package management system, version control system, and so on written in Haskell are not proofs or testament to anything more than their ability to sling code just as one would say about a Python programmer.
>In reality, I think I view most Haskell programmers’ relationship to math in a similar light as Guitar Hero players are seen by real guitarists.
LOL. Compare my reaction as an ex-mathematician who actually does understand the rudiments of category theory (though not very well, anymore) – I found I had to brush aside Haskellers’ formalistic claims about it in order to understand what the language is actually doing.
>>I never understood LISP or other functional languages until I learned Python.
>Really? I find that strange. Can you explain?
Although the question wasn’t asked of me, something similar happend to me: CA-Clipper “code blocks” (sort-of-lambdas) -> Python generator expressions -> Ruby “do” blocks -> a little bit of LISP (nor very much).
For me the basic question was WTF is functional programming even good for in real life?
And when I first began to grasp it was the following: again, why are using computers for? What is the core necessary construct that makes a program different from a config file? Is it a variable assignment? No. Is it a condition? No. It is a loop. If I’d want to make one point red on a piece of paper, I’d take a red pen and not a computer. (Yeah, thoroughly un-mathemathical thinking: the computer as an appliance.) It is when I want to make many points red does it make sense to take a computer and a printer and write a program for it. If I need to set one byte to 43 I’ll take a hex editor, if I need to set many bytes to 43, I’ll write a program.
So for me programming = loops. No loop, no need for writing a program.
The first time I grokked the most primitve basics of functional programming could be useful was when I realized instead of looping through some sort of array or set, I could apply a function to each member of the set. And the function doesn’t necessarily need to have a name, can be a “lambda”, which is in my non-mathemathical mindset simply means “nameless function” – yes, I know that’s not right, but anyway. This I could do in CA-Clipper, such things were called “code blocks”, the syntax was {|x|x+1} and there was a function that meant “map”, with a different name, but unfortunately I’ve forgotten the name. I think it was “aeval” or “arrayeval” or suchlike. This seemed like a more elegant solution to me than writing loops.
The next step was Python generators. I began to realize functional programming is like SQL which I already knew. Or rather that functional programming applied to one use, “map” is like it. I realized functional programming is not weird mathemathical stuff but simply that general stuff of which SQL is a very handy and clearly understandable subset of. I learned functional programming does not need to be mathemathical or hard, it actually can be very expressive, normal and natural.
Ruby blocks took the whole thing into a different direction. In Rails you can even define an SQL table with a do-block. At this point I realized functional programming is something that enables you to write domain-specific languages in.
Then in LISP I realized that a function that doesn’t evaluate it’s parameters can be sometimes handy, because you might need the parameters the way they are, and then I grokked the concept of a macro.
Geez, shenpen, I just realized I used to create ‘functional’ windowing programs in C. I’d build a big array of structs including some function pointers to do the specific behaviors attached to individual gadgets. Then I’d loop through the array (map) running the specific functions (reduce).
I really liked that style at the time, but I could tell it was to complex and gimmicky for most people. SQL, OTOH, is not.
Yours,
Tom
>Geez, shenpen, I just realized I used to create ‘functional’ windowing programs in C. I’d build a big array of structs including some function pointers to do the specific behaviors attached to individual gadgets. Then I’d loop through the array (map) running the specific functions (reduce).
Hell yeah. I write C like that, too. That style is a fairly reliable way to spot old LISP-heads. Smart data, dumb logic => win.
Well, I could basically half understand what was going on in a LISP program, but I found the syntax to be cumbersome to work with when writing.
You have to understand that all the languages I worked with prior to Python were imperative langugages, like C and Pascal. That and I lack formal computer science training; I’m mostly self-taught in that regard, somethings I learned by studying other people’s work.
I’m not the academic programmer type, I’m more the practical guy. :)
>But the exception is not the rule, and the average Haskell programmer is not a mathematician, just like his window manager, package management system, version control system, and so on written in Haskell are not proofs or testament to anything more than their ability to sling code just as one would say about a Python programmer.
Witness the Haskell community’s embrace of Darcs, the ephemeral theory of which appears to be little more than cargo-cult mathematics.
>Witness the Haskell community’s embrace of Darcs, the ephemeral theory of which appears to be little more than cargo-cult mathematics.
Can you unpack this any? I have an active interest in the design of version-control systems.
LOL. Compare my reaction as an ex-mathematician who actually does understand the rudiments of category theory (though not very well, anymore)
Haskell’s brand of category theory is very different from the use of category theory most mathematicians wil be familiar with (which is closely related to universal algebra). Look into the the Curry-Howard-Lambek correspondence (which relates the simply typed lambda calculus to intuitionistic logic and Cartesian closed categories) and William Lawvere’s work on categorical logic.
# esr Says:
> Hell yeah. I write C like that, too. That style is a fairly reliable way to spot old
> LISP-heads. Smart data, dumb logic => win.
I know we are all Microsoft haters here, but you guys should consider some of the features introduced into C# 3.0. The so called Linq feature offers many of the features of functional languages, such as beautifully simple syntax for closures and lambda, along with true lazy evaluation. It offers this with extended data structures beyond the typical lists used in functional programming languages. For example (I am assuming the html cleaner will totally screw up the formatting of this code, but here goes anyway):
var ChicagoResidents = from user in data.People
where user.AreaCode == 312
orderby LastName
select user.LastName + user.FirstName;
ChicagoResidents.ForEach(name => Console.WriteLine(name));
(Please forgive any syntax errors.)
It is a very SQL like syntax, and how it actually implements this depends on the type of data (which might be a database table, or an array or a user defined structure with appropriately implemented interfaces and so forth.) Various mechanisms optimize this query, using, for example, data indexes and so forth automatically (similar to an actual SQL implementation.)
Secondly the variable ChicagoResidents is lazily evaluated, which isn’t relevant here, but can be very important where there are high costs for evaluating the elements of the list.
Finally I have given an example of an anonymous function to make the use of map, reduce and similar data structure traversing operations effective.
Basically, they did a very nice, intuitive job in this design. It actually is useful in practice, unlike the total botch job the C++ committee did in their horrible STL and functional features in C++.
FWIW, there is a question as to what good is FP? I suggest that it really is about to become more relevant quite simply because its more tractable structure makes it much easier to operate in parallel, and that is “The Next Big Thing”, which is to say in computationally intensive situations its inherent weaknesses might be overcome by the overwhelming advantage it has in the reduced need for inter process locks, and its significantly increased coding complexity might be overcome by the huge increase in complexity procedural programs have when multi-threading is needed. But, I’m no expert by any means.
You are assigning the characteristics you found in Haskell to Haskell itself.However, these characteristics belong to fully functional programming languages and are not found in Haskell only. learn Erlang for example and you’ll find more or less the same features, along with pattern matching and more.
Indeed. Functional programming has been legitimized, now that Microsoft supports it with its toolset.
Jessica,
C# does not introduce true lazy evaluation. C# cannot have true lazy evaluation without an effect tracking system (like Haskell). You can emulate lazy evaluation using System.Func but only to the extent that your code remains pure. Also, Linq does not introduce simple syntax for closures and lambda; the language does.
Finally, Linq is a degenerate notion of what esr alludes to (knowingly?) with respect to monads. Linq is a monad comprehension. However, it doesn’t allow you to abstract on the monad. For example, what is the type of this expression? from aa in a select f(aa). In Haskell, the type would be: (Monad m) => m a -> (a -> b) -> m a or using C# syntax: M => Func => M. Notice that the “M” is abstracted on. This type system feature is called higher-kinded polymorphism. C#/Linq does not allow this, which is the most important part of all.
C# is watered-down to the extent of being significantly less practical than Haskell. I wish some of the guys at MSR would admit it; they know it.
the language has quirks that no sane mathematician would have let slip in (like Monad not being a subtype of Functor, despite monads being functors *by definition*)
Fair enough.
the compiler doesn’t enforce the monadic axioms
IIRC, you can setup the Haskell toolchain to check that the monadic axioms are respected by randomized testing (“QuickCheck”). Anything stronger than that would require turning Haskell into a full-blown proof assistant. If you want that, you can look into Agda and Coq (see below)
For “languages†for mathematicians, by mathematicians, you can look into the Coq proof assistant,
Yes, Coq fits the bill here. But note that Coq is quite similar to Haskell in its logical foundations, although it does add features including dependent types and provable termination (it is not Turing complete). Note that you can extract the computational content of a Coq proof to Haskell and the structure of the original proof term will be preserved.
Mathematica, Maple, Axiom, Maxima, and so on.
With the possible exception of Axiom, none of these are languages for doing mathematics. Computer algebra systems are untrusted tools which routinely return wrong answers due to their lack of formal mathematical foundations. By contrast, a proof-carrying program in Coq or (with some reservations) a Haskell program can be translated into mathematical notation in a straightforward way, since type theory is a perfectly viable foundation for constructive mathematics. Look into Errett Albert Bishop’s Foundations of Constructive Analysis: cargo-cult mathematics indeed.
>Can you unpack this any? I have an active interest in the design of version-control systems.
If by formulate good criticisms of the theory, then no. People have been hand-waving about Darcs’ amazing patch algebra for years, but nobody has a scrutinized paper that describes it to a satisfactory depth. This being the case, it can simply morph into something different when faced with criticism.
>Haskell program can be translated into mathematical notation in a straightforward way, since type theory is a perfectly viable foundation for constructive mathematics. Look into Errett Albert Bishop’s Foundations of Constructive Analysis: cargo-cult mathematics indeed.
I’m not sure if this is directed at me, since I would not disagree with anything you’ve said here. I reserve the carge-cult comment specifically for Darcs. If your marketing material is going to forever repeat that Darcs is ‘smart’ because it is based on a patch algebra, I think someone should actually go and thoroughly analyse these ideas.
From what I have seen of the “darcs patch theory”, I agree that it needs to be fleshed out and made far more rigorous if it is to be taken seriously. Nevertheless, this paper by Bieniusa et al. suggests that a large body of research could be brought to bear on this problem: The Relation of Version Control to Concurrent Programming
Tony Morris Says:
> C# is watered-down to the extent of being significantly less practical than Haskell.
I wasn’t suggesting that C# was a pure functional programming language, I was simply pointing out that they had added some powerful features that introduce some of the syntactic conciseness of a functional language into a fundamentally procedural language. I think part of my comment comes from my frustration of trying to do these sorts of things in C++ and failing miserably because language support is so poor, and then enjoying the simplicity and directness of the implementation in C#.
In regards to your comment on lazy evaluation: perhaps it doesn’t meet some definition you have, however, from a practical point of view it offers the core benefits that I am looking for, which is to say delaying execution of the evaluation until it is actually needed. I recognize that a deeply tractable program as is possible in a purely functional language has a number of benefits, however, one can hardly expect that from a language which is heart and soul procedural. That doesn’t mean that none of the benefits can be realized.
I doubt many people would agree with your view that C# is somehow less practical than Haskell. After all many, many new pieces of software for Windows and the Web are written in C#, some of them extremely large complex systems. As far as I am aware the same is not true of Haskell. This would seem pretty strong evidence as to which is more practical.
Jessica, the precise definition of lazy evaluation can be observed by this Haskell:
> let f x = “boo” in f undefined
> “boo”
There is no other definition. C#/Linq has nothing like it. You can emulated it with Func, but you can say the same for Java. C# offers nothing at all like lazy evaluation. This is extremely important, because it doesn’t have an effect tracking system. I leave it up to you to think of an example with uncontrolled side-effects in a hypothetical C# that did in fact, have something like lazy evaluation.
Also, whether many people agree to a proposition does not alter its truth value.
*ponders*
Having delved into Haskell, will there be a functional language re-draft of INTERCAL in the future, Eric?
*hides someplace VERY FAR AWAY*
>Having delved into Haskell, will there be a functional language re-draft of INTERCAL in the future, Eric?
I have it! I shall redesign INTERCAL as the anti-functional language! Side effects, nothing but side effects and globals, all the time! Program flow so snarled that you not only can’t prove it correct, you can’t even prove the correctness of any adjacent pair of statements! BWAHAHAHA!
I’m guessing this has nothing to do with Eddie Haskell from Leave it to Beaver?
Gee that’s some lovely code you have there Mrs. Cleaver!
Ok I’ll shutup now.
> There are reasons to make the effort. Haskellers (Haskellites? Haskellians? Haskellators? Haskelletons?) maintain that imperative programming relies heavily on side effects that push proving the correctness of programs to somewhere between impractically difficult and impossible. They also like to point out that side effects make programs difficult to automatically parallelize across multiple processors, an increasingly important consideration as multicores become the rule rather than the exception.
I do not believe these are the arguments that would be most emphasized, you’re putting words in the communities mouth, which is quite a disservice.
Now, I do not claim to be a representative haskellite, although I am a (thusfar) quite minor member of the community, I suggest that the following are purported boons:
More concise and understandable code, and furthermore better code, which as better product. Just to wiggle out of the sweeping generalization I’m making, lets say “for most domains”, but for those who have really drank the kool aid, it seems more that those domains just remain to be properly conquered. Procedural languages have been given quite a few more decades to develop.
Here’s how: the power of haskell’s constructs allow you to fairly easily partition your solution in many ways. Your power of abstraction is strictly larger. With great power comes great responsibility, though (did I really just use that?…), and you need to train even harder than in procedural languages to pick the right partitioning.
Thankfully, the actual fundamental medium is actually quite a bit less complex, as it’s basically just functions/expressions all the way down. In a sense, the level of haskell’s capabilities for abstraction allow you to establish new semantics, ala lisp, to expressions structured a certain way.
Monads actually aren’t that heavily embedded in the language, they’re like any other class. The only difference is that the language comes with one instance of it built in: the IO monad. And yeah, monads just introduce an embedded domain specific language that follows certain common rules. This is an illustration of our power of abstraction.
So yes, it’s more likely to be able to prove something directly about haskell functions. But this isn’t the value of that fact. It also implies that the programmer is able to reason about their code more easily too! The reason that static analysis can’t prove much about procedural code in general is the same reason that it’s difficult for humans to reason about.
Being able to reason about your own code in a methodical fashion = good.
It takes a few months of immersion to see these things. Haskell is like a Durian, smells nasty when you’re not used to it, but tastes so sweet once you take the plunge.
>I do not believe these are the arguments that would be most emphasized, you’re putting words in the communities mouth, which is quite a disservice.
Several drafts, and the final version, were reviewed on #haskell. The strongest criticism it received was that the wording describing expressions being evaluated “each time” might be misleading. At least one of the regulars remarked that I’d done surprisingly well, considering what they think of the usual quality of such summaries.
I think if you’re looking for some interesting things to do with Haskell, try writing some multicore programs. Take your off-the-shelf Haskell programs, and start dropping `par` constructs in there, and watch your extra cores fire up. It’s intoxicating!
This is probably a good first mental approximation of the IO monad, but it’s not a good way to think about monads in general. They are best understood as imperative mini-languages where you can program your own semicolon “
;“. The selection of possible side-effects is huge: state, logging, exceptions, non-determinism, coroutines, … . In particular, non-determinism does not fit the “ensure evaluation order” picture.The equivalent of a shell pipeline is plain function composition
(.)coupled with lazy evaluation, at least if the shell commands are essentially side-effect free.> Perry The Cynic Says:
> I have similar reactions to Haskell. The language was invented by logical formalists to bring their formalisms to bear on actual programming (instead of toy scenarios).
That’s just wrong, there were no logical formalists around when Haskell was designed. I was actually there.
Its important to distinguish between the definition of a monad (roughly, its a type with a couple of operators defined) and the several ways that monads are used in Haskell.
*One* of those ways is to sequence several operations in some context, and one of those contexts is “IO”. This is indeed a neat hack, but the big news is that monads are not just a way to force IO semantics into a pure language, they are a way to introduce any kind of sequencing semantics you might want. Its a bit like having an overloadable semicolon; what do you want “{x;y;z}” to mean?
For instance, for one application I wrote a threaded discrete event simulation framework in Haskell using a combination of continuation and state monads with IO (because a suspended thread is actually just a continuation). This let me write application-level code with multiple threads where “delay (hour 1)” only delayed the thread long enough for the next hours-worth of simulated events to happen in other threads, rather than 1 hour of wall-clock time.
This is important because requirements are often expressed in terms of the form “do this, then do that”, where “then” has a domain-specific meaning. If you can capture that meaning in a monad then suddenly you have code that can be read and understood by a domain expert, which greatly reduces the opportunities for error.
Its true that Haskell makes formal mathematical proof of programs easier, and its true that even in Haskell a formal mathematical proof is still too difficult. However this property also makes regular programming and debugging easier, because whenever you read a program you have to create informal mathematical proofs in your head all the time. If you see “x := sqrt(y)” then you have to be sure that “y” can never be negative at that point in the program; if it can then there is a bug. So in your head you construct an informal proof of this proposition. Once you have done so you can approve of the code and forget your proof (or possibly note it in a comment if it took more than a few seconds to construct).
The purity of Haskell makes this kind of reasoning much easier for the same reason it makes the formal proofs much easier.
Foolish hacker; stop spending $5 on zinc snake oil, and just switch to hard candies. They’ll work just as well, and you won’t be enriching the hucksters.
@esr:
You could probably start with this obscure language. :-P
Now that you learned Haskell, here is a programming challenge for you: write, in Haskell, a GUI program that allows the user to manipulate a tree of data structures; the members of the tree should be of different types.
For added bonus, also write, in the same program, a simple game (let’s say, Pacman) to run in one of its windows.
Achilleas Margaritis, these are exceedingly difficult problems for a beginner in Haskell. The first requires implementing dynamic types (although GHC does provide a Data.Dynamic library) and binding with a GUI library. The “bonus project” requires dealing with global state: for a few hints on how to do this elegantly, see Purely Functional Retrogames.
mathymathy,
Boy, James Hague is fun to read! Thanks for that link.
Yours,
Tom
>>Witness the Haskell community’s embrace of Darcs, the ephemeral theory of which appears to be little more than cargo-cult mathematics.
> Can you unpack this any? I have an active interest in the design of version-control systems.
Actually, the “algebra of patches” on which darcs is based was invented not
by a mathematician but by a physicist – David Roundy. Physicists tend to look for
mathematics-like formal manipulations that just work. They use them to get
the job done, without worrying too much about how the math really works beneath
the surface. They leave the work of truly understanding the mathematics for
mathematicians to do later on. That’s pretty much how it went with darcs, too.
@Archilleas
No need to treat it as a challenge. Just look at how other people write GUIs and games in Haskell. Thanks to Hackage we have thousands of examples of using Haskell for all sorts of different problems, including games http://hackage.haskell.org/packages/archive/pkg-list.html#cat:game and gui programming.
@augustss:
> That’s just wrong, there were no logical formalists around when Haskell was designed. I was actually there.
I’ll take your word on that. (I wasn’t there, so your testimony beats mine.) Care to elaborate a wee bit, though (or point at an online story)?
Cheers
— perry
Some point by point answers to T, above, because there’s a good deal of bad information:
> Sure the syntax is similar to some mathematical notation, but the language has quirks that no sane
> mathematician would have let slip in (like Monad not being a subtype of Functor, despite monads being functors > *by definition*) and that the compiler doesn’t enforce the monadic axioms (which is a lot more understandable > given the language itself evolved before the idea of using monads within it so graciously did), etc.
The point about the unenforceability of monadic laws in general outside of a general purpose proof system has already been made. Outside of that, Haskell doesn’t have subtypes, so no class is a subtype of any other class. Monad indeed lacks a Functor class constraint, but that’s a historical accident and is widely recognized as such — its simply too entrenched in too much code to change lightly. There are alternative Preludes which have different typeclass hierarchies, especially with regards to the numeric tower, precisely because of this. Since the core of the language isn’t contingent on a particular hierarchy or numeric tower, they can be dropped in by people who want the extra precision.
As for the mathematical character — that’s simply because Haskell functions, like normal functions in math, are referentially transparent — their output is determined only by their input.
> Certainly one can implement many features of these languages in libraries for Haskell, but some are simply not > convenient to use (e.g., the symbolic manipulation found in algebraic languages and the Lisp family)
This is sort of weird to say — certainly Haskell doesn’t have a built-in symbolic math package, but the entire ML family of languages are historically the *most* suited to capturing and manipulating syntactic strcture, syntax trees, etc.
> An excuse to seem smart by tossing around buzzwords like “monad,†“functor,â€
> “isomorphism,†“homomorphism,†“catamorphism,†etc without ever actually getting a degree in mathematics.
This is just outlandish. Monad and Functor are used not for any “buzzword” reasons (to the extent that they are “buzzwords,” outside of certain branches of math, this is solely because of Haskell and not the other way around) but because they are the words which properly describe particular typeclasses. Homomorphisms are important, sure, but Haskell programmers don’t use the word except if they’re actually talking about mathematical foundations. Similarly, people will speak about isomorphisms, but they do so reasonably, and because Haskell programmers are a mathematically inclined bunch, and if I want to say that, e.g., the two structures “Maybe a” and “Either a ()” are, for all intents and purposes, two ways to capture exactly the same information, then there’s no simpler way than to say that they are isomorphic. People talk about catamorphisms when being more formal, but generally simply talk about folds, and functional programming, with its emphasis on both regular and irregular algebraic data types, is rich in uses of various folds, recursion, and traversal schemes. If somebody does talk about a catamorphism, and distinguishes it from e.g., and anamorphism or the like, odds are they know what they’re talking about, and they’re trying to illustrate an underlying structure behind some particular traversal pattern.
In reply to R. Phillips, certainly darcs is not fully formalized. However, it is significantly more so than other dvcses, and more importantly, the darcs development community is *working towards* a formalization, which is a better goal than *not working towards* one. See, e.g., http://projects.haskell.org/camp/
Haskell is certainly not just by or for mathematicians and computer scientists. It is a practical, functional language, suitable to be learned by beginning programmers, and suitable for general purpose use. But the formal foundations of Haskell, and the continual give-and-take between a growing community of commercial and hobbyist users on the one hand, and computer scientists and PLT researchers on the other, have given the language community, and the development of the language itself, at least for now, a unique flavor where there is impetus to do practical things well balanced by impetus to do things carefully, formally, and rigorously.
I have actually become a big fan of using haskell as part of shell command lines, for when sort isn’t /quite/ what you need, but perl seems like it would take too long.
To get that to work, the trick is to have a .hs file with common functions and imports in it. Then use
$ ghc -e EsrUtils.hs
In particular, interact tends to be of great use. (interact . unlines $ map (show . . read) . lines)
>In reply to R. Phillips, certainly darcs is not fully formalized. However, it is significantly more so than other dvcses
I don’t think this is true at all.
>and more importantly, the darcs development community is *working towards* a formalization, which is a better goal than *not working towards* one. See, e.g., http://projects.haskell.org/camp/
Other VCS’s have informal models. In fact, the informal models behind the more conventional DVCS’s are more immediately convincing than Darcs. Using fancy symbols and terminology doesn’t imbue a description with rigor. That the Darcs people are working on this is great; they are not there yet, so it is untrue to say that it has any kind of formal foundation.
Tom DeGisi,
“I’d build a big array of structs including some function pointers to do the specific behaviors attached to individual gadgets. ”
An array of structs containing function pointers that are attached to individual gadgets? I’d rather call that OOP of the not class-based but prototype-based one, like in JavaScript.
Not that these are necessarily different concepts, of course. The most surprising and perhaps the most valuable thing Python have taught me is that functions are objects and objects are functions. If you define functions inside a function, you basically get an object where the constructor is the original, main function itself. If you tag an object as runnable or executable (I forgot the actual term) and use only it’s constructor function, you got a function. Whatever. Perhaps a mathemathician would be horrified of this simplification – Xah Lee has written that OOP is based on something called “sigma calculus” in a similar way functional programming is based on lambda calculus and they two totally different concepts – but in its actual implementation it rather looks mind-blowingly elegant to me.
Hi Roger, and Eric,
Ian Lynagh’s 5 minute video http://projects.haskell.org/camp/unique does a great job explaining what makes Darcs and Camp unique. The two projects are close; and may merge in the future.
One point I will make is that Darcs tries to do something quite different from other DVCses, something I hope folks will steal from us. We want to do merging without any guessing. How do we avoid guessing? By taking the history into account. That’s the “smart” part. Merging becomes a fully mechanical process: we are 100% certain that your patch to line 3 of foo.c should now apply to line 53, because we notice in the history that there were patches in between that added 50 lines worth of stuff. We don’t try to guess this by looking at the contents of the file; we just follow the history.
We have this notion of “patch commutation” that lets us have this really handy property that any ordering of commits permitted by Darcs gives you the same result. This means that cherry picking patches works really well; and we can encourage you to do as much as you like in the user interface. Darcs offercs cherry picking in all its operations: you can cherry pick patches to push, to revert, to unrevert, to destroy completely. (Darcs will only refuse cherry-picking if commutation fails, ie. if a syntactic dependency is violated)
The criticism that Darcs is not well formalised is well deserved. You may be interested in Judah Jacobson’s paper which attempts to formalise Darcs using inverse semigroups.
http://www.math.ucla.edu/~jjacobson/patch-theory/
More bad news: we still don’t know how do deal with conflicts properly. Ultimately, conflicts are the user’s responsibility and we definitely respect that! But before handing off to the user, there is a minimum amount of work that Darcs needs to do for commutation purposes. Unfortunately, our two current algorithms for doing that work have flaws. They work fairly well in practice, but people in the real world do sometimes get stuck.
We’re not giving up! In the short term, we are working on tools to help them get unstuck (darcs rebase); and in the long term, we are working on a better approach to conflicts. You may be interested in reading Ian’s work in progress (with proofs in Coq). http://projects.haskell.org/camp/files/theory.pdf
All right, Haskell is for sure going on my languages-to-learn list, right after whatever LISP variant I eventually start with. Thanks for the recommendation.
ESR, do you have any opinion on the Lua programming language? I’ve been using it a lot lately and I like it quite a bit, I’d be interested to hear what you think.
>right after whatever LISP variant I eventually start with.
For your purposes (running up to Haskell) Scheme would be best, no question.
>ESR, do you have any opinion on the Lua programming language?
I think it’s a very sound design, though not without some really odd quirks – WTF is up with that 1-origin indexing?
Battle For Wesnoth is using it as an extension language for our C++ core, replacing Python in that role. I like Python a lot, but I approved that change. lua can be securely sandboxed, Python can’t be, and that turned out to matter a lot.
>For your purposes (running up to Haskell) Scheme would be best, no question.
All right, thanks. :)
Erlang pattern matching is quite possibly the best surprise language feature i’ve ever seen.
The first newbie thought is “aww… case statements are ugly and ifs are broken, i hate this language” and then someone tells them “just send it to a worker function and pattern match the parameter”.
At this point the mind starts boggling.
(Fair disclosure, i am unredeemably addicted to the erlang kool aid)
(also to be fair, it’s much the same pattern matching as is in Prolog and Haskell)
For “the functional equivalent of intercal”, I would nominate unlambda: http://www.madore.org/~david/programs/unlambda/
>For “the functional equivalent of intercalâ€, I would nominate unlambda: http://www.madore.org/~david/programs/unlambda/
I was thinking something similar about Unlambda when I joked about creating an anti-functional INTERCAL. Combinators make…head…asplode.
Here’s a list that needs to be compiled (ha): programming languages that have more lines written about them than written in them.
> The single most delightfully weird detail of Haskell I’ve run into so far is this: you can have type-valued variables, > and write type-valued expressions that are recursive! For some types, such as trees, this is the natural way to do > things.
that’s straight from ML, right?
Jeff Bonwick,
As Gates said, measuring programming progress by lines of code is like measuring aircraft progress by weight.
In Haskell you don’t need too many lines to get a lot of stuff done. Also, a hundred-line program may take hours to craft. (But in the end, if it type-checks, it probably works!)
@Jeff Read:
That statement has a lot of truth to it, but it’s also not completely true that LOC is totally useless as a gauge. As it turns out, LOC is a pretty marker for gauging the complexity of a given project as compared to other projects written in the same language (or a similar language).
Comparing a C program to a Haskell program by LOC would pretty be worthless, because it’s like comparing berries to grapefruit.
You recommended learning a LISP (probably Scheme?) as a bridge to Haskell from widely-used programming languages, but in my case I learned an ML (OCaml) first. The type system and syntax has similarities to Haskell’s without requiring the same level of understanding of unfamiliar semantics.
> I think [Lua is] a very sound design, though not without some really odd quirks – WTF is up with that 1-origin indexing?
The short answer is that Lua was designed and intended for a user/programmer community who thought that 1-based was more natural.
See http://www.stanford.edu/class/ee380/Abstracts/100310.html and http://ee380.stanford.edu/cgi-bin/videologger.php?target=100310-ee380-300.asx for more discussion.
Actually, for me 1-based indexing has always been more natural. If I want to get the first 10 elements of an array, why do I have to write for i:= 0 to 9, why not for i:= 1 to 10? Or if I write for i:= 1 to 10, then why do I have to write array[i-1]?
I think it is 0-based indexing that requires justification because we normally count as first, second, third and not as “zeroeth”, first, second, third.
Anything that gets a programming language closer to natural language WITHOUT 1) bloat 2) lossage of precision is a Good Thing, because it is a step towards affording to think more about the problem and thinking less about the syntax or the implementation.
What is your justification for 0-based indexing?
>What is your justification for 0-based indexing?
Just that I’ve been used to it for so long from LISP and C and Python that 1-origin seems perverse to me.
> What is your justification for 0-based indexing?
It’s traditional because it’s close to the hardware, I think. But yes, nearly every other human tradition starts counting at one, so zero based indexing isn’t all that natural. There is no Zeroth Street in my city. OTOH the first address on the block is 9500. On the gripping hand there is no year zero, either.
Yours,
Tom
That’s because the Romans didn’t have a zero.
I always have trouble when I visit Monsterette 2 in her suburb of insanely-addressed Wichita. 100 N is right across the street from 100 S, so the houses between, say, 48th and 49th are the 4900 block. I’m always a block off when navigating there, until I remind myself to make the adjustment.
Because we have no year zero, this century technically started with 2001, not 2000, and this is the last year of its first decade, not the first year of its second. That’s very confusing.
I am willing to declare the year 1 BC(E) to be 0, 2 BC to be -1, … just to make sense of such things. But then the years 0-99 would be the Zeroth Century, and we would now be in the Twentieth instead of the Twenty-First. Unfortunately, cardinal numbers “naturally” start with “first”, and “zeroth” doesn’t make sense to the general public like it does to us geeks.
The short answer to why indexing should start at zero is that with zero-based indexing, you need only multiply the subscript by the element size and add that to the base address of the array to get the address of the element you seek. With one-based indexing, there’s an added step of subtracting one from the subscript, the multiplying…
The long answer was given by Dijkstra.
> The short answer to why indexing should start at zero is that with zero-based indexing, you need only multiply the subscript by the element size and add that to the base address of the array to get the address of the element you seek. With one-based indexing, there’s an added step of subtracting one from the subscript, the multiplying…
The too short way of saying this is that it’s closer to the hardware.
> The long answer was given by Dijkstra.
And it was not convincing, because it failed to take into account the influence of culture. The key graph is:
But this graph does not take into account that the programmers in question may simply have been acculturated to prefer a particular convention. What I want to know is what confused programming newbies. My hypothesis is that experienced programmers in assembly and recent languages prefer 0 based, but experienced FORTRAN programmers and newbies prefer 1 based. As evidence for newbies I note that Excel numbers it’s rows starting at one.
Yours,
Tom
Tom,
a) No, that is not the key graph. Dijkstra is too much of a snobbish theoretician to justify any claim of his primarily on the rickety and tendentious foundation of actual programmer practice. :) The key graph is the bit at the top, where he explains that the convention of making the lower bound of an integer interval closed and the upper bound open allows for some nice mathematical properties of integer intervals expressed in this way compared to all the other possible ways.
b) His remark about the Mesa language isn’t about array indices; it’s about intervals of integers. He notes that the other three conventions for talking about integer intervals were more cumbersome and prone to off-by-one errors.
Zero-based indexing has other nice mathematical properties; for instance, any number modulo the size of an array will be a valid index into that array. That makes using arrays for hash tables and the like much easier.
As for newbies, when you stop talking about application packages and start talk about programming languages, you expect your target audience to be grown-up enough to be able to adjust to the new convention.
Because that’s how it’s always been. The hardware numbers things from 0.
But actually, my best justification is that 0 is the smallest unsigned integer. If you were sorting a list of unsigned integers, the 0s would be at the beginning (or end, if sorting in reverse), right?
Jeff,
> No, that is not the key graph.
It’s the key graph to me. I prefer Larry Wall (not snobish linguist)over Dijkstra (snobbish mathematician) any day.
> Zero-based indexing has other nice mathematical properties; for instance, any number modulo the size of an array will be a valid index into that array. That makes using arrays for hash tables and the like much easier.
I also prefer you (not obscure programmer) over Dijkstra (obscure mathematician). You make sensible arguments. He says things like this: “The observation that conventions a) and b) have the advantage that the difference between the bounds as mentioned equals the length of the subsequence is valid.” Which is fine, but totally neglects the crucial explanation of why that is an advantage.
> As for newbies, when you stop talking about application packages and start talk about programming languages, you expect your target audience to be grown-up enough to be able to adjust to the new convention.
1. Spreadsheets are programming languages disguised as applications.
2. People will adjust to anything, even trench warfare. I’m hypothesizing about what takes the least adjustment.
Yours,
tom
>I also prefer you (not obscure programmer) over Dijkstra (obscure mathematician). You make sensible arguments. He says things like this: “The observation that conventions a) and b) have the advantage that the difference between the bounds as mentioned equals the length of the subsequence is valid.†Which is fine, but totally neglects the crucial explanation of why that is an advantage.
Presumably, he doesn’t explain this because he identifies it as a dead end, and so the argument is discarded. The remainder of his explanation is justified from the perspective of notational convenience.
…early every other human tradition starts counting at one, so zero based indexing isn’t all that natural…
I always point to non-US numbering of floors in buildings to explain the zero-index thingy to noobs.
> What is your justification for 0-based indexing?
It’s almost certainly due to the fact that C is a low-level language (basically a generalized assembly language) and assembly indexing starts at 0. When you grab the memory address of a buffer in assembly and put it into a dptr (or register, whatever), it’s already pointing at the first member of the array, no ‘++’ required.
Extrapolating from there, C is the 800-lb gorilla for programming languages (I recall from somewhere that something like 70% of current open-source projects are written in C), so it would seem perfectly natural to assume the majority of programmers are comfortable with 0-based indexing when designing new languages.
Plus, it’s the little things that tend to tick people off. And if you’re trying to attract attention to your project, you’ll do as little of it as possible without good reason. I remember reading ESR’s review of Python where he stated that he almost ditched the language because it foolishly included whitespace as part of the syntax. I think most commenters here know how that turned out…
Roger Phillips,
> Presumably, he doesn’t explain this because he identifies it as a dead end, and so the argument is discarded.
That’s true.
> The remainder of his explanation is justified from the perspective of notational convenience.
That may be, but you said it and he didn’t. Therefore I also prefer Roger Phillips (justifying mathematician) over Dijkstra (non justifying mathematician). He said ugly. His argument boils down to this:
These are ugly:
-1 < i ≤ 12
-1 < i < 13
-1 ≤ i ≤ 0
1 ≤ i < N+1
These are pretty:
0 ≤ i < 13
0 ≤ i < 0
0 ≤ i I always point to non-US numbering of floors in buildings to explain the zero-index thingy to noobs.
An explanation not needed is easiest.
Yours,
Tom
Roger Phillips,
> Presumably, he doesn’t explain this because he identifies it as a dead end, and so the argument is discarded.
That’s true.
> The remainder of his explanation is justified from the perspective of notational convenience.
That may be, but you said it and he didn’t. Therefore I also prefer Roger Phillips (justifying mathematician) over Dijkstra (non justifying mathematician). He said ugly. His argument boils down to this:
These are ugly:
-1 < i ≤ 12
-1 < i < 13
-1 ≤ i ≤ 0
1 ≤ i < N+1
These are pretty:
0 ≤ i < 13
0 ≤ i < 0
0 ≤ i < N
Ugly is obscure. They look pretty to me, but I’ve been using Algol derived languages for twenty years. “Can be expressed as an unsigned integer allowing one to express all possible indexes using a natural data type for any given two’s complement architecture” is less obscure.
Which boils down to: It’s closer to the hardware. (And beautifully closer to my Pascal/Modula 2/C/C++/Java trained eye.) If I consider languages like Erlang, which claim to have numbers with arbitrary precision and expects you to use them, the convienence is less clear.
I’m not sure that a zero based notation is all that convenient for the programming language user. It is good for the programming language implementor. I’m very happy my daughters (and lots of other kids) are programming in Scratch. I don’t want programming to be the exclusive domain of mathematicians and professionals. People are not used to seeing zero as a subscript or superscript, either, which is the natural way for us to describe an array.
If I had some evidence that zero based is easier for everyone I’d be happy.
Dan,
> I always point to non-US numbering of floors in buildings to explain the zero-index thingy to noobs.
An explanation not needed is easiest.
Yours,
Tom
Sorry about the first post. I forgot about the importance or less than and greater than in HTML.
Yours,
Tom
>Therefore I also prefer Roger Phillips (justifying mathematician) over Dijkstra (non justifying mathematician)
It’s a non-refereed memo; you can expect to have to work a little to get something out of it.
>Ugly is obscure.
Ugly in this context refers to the extra work it takes to formulate definitions. If you’re working with natural numbers, having to have a negative number in there is a problem that requires extra notations to deal with. In mathematics these issues can be resolved by the reader; a computer can do no such thing. I don’t see the connection between Dijkstra’s argument and integer representations.
>If I had some evidence that zero based is easier for everyone I’d be happy.
No notation sits well with everyone, and striving to conform to linguistic norms is essentially hopeless, since nobody has been able to define what a linguistic norm is anyway. I think we should regard this as fortunate, as natural language is terrible for forming precise definitions. Programmers can ill-afford notational incongruities, hence the need for everyone to number from zero.
Also to clear something up I’m not a mathematician, I just use maths in my work.
Roger Phillips,
> It’s a non-refereed memo; you can expect to have to work a little to get something out of it.
Expectation met.
> I don’t see the connection between Dijkstra’s argument and integer representations.
Well, I can’t legally represent -1 as a size_t in C, for example, nor can I legally represent the MAX_UINT + 1. So 0 ≤ i < MAX_UINT is not just prettier, but syntactically correct, although C will probably allow you to get away with it. IIRC neither Pascal nor Modula 2 would allow such a thing. (On a non two’s complement machine things might be different. I haven’t thought about those.) Reading the non-refereed memo forced me to think about this. Therefore I also prefer Dijkstra (puzzling mathematician) over Tom DeGisi (lazy programmer). My brain needs the exercise.
> No notation sits well with everyone, and striving to conform to linguistic norms is essentially hopeless, since nobody has been able to define what a linguistic norm is anyway. I think we should regard this as fortunate, as natural language is terrible for forming precise definitions. Programmers can ill-afford notational incongruities, hence the need for everyone to number from zero.
I like this argument.
> Also to clear something up I’m not a mathematician, I just use maths in my work.
I know, but we were having this pleasant discussion earlier about computer science = mostly math / computer science = mostly engineering….
Yours,
Tom
…although C will probably allow you to get away with the ugly versions. IIRC neither Pascal nor Modula 2 would allow such things….
@Tom DeGisi:
Computer science is mostly math. Software development, which is not pure computer science, but applied computer science, is mostly engineering. Feel better?
morgan,
That’s what I said at the time. So, especially since it’s you saying it, I do feel better.
Yours,
Tom
Bear in mind that the way I use “software development” it’s a methodology, or more accurately, a set of methodologies. One classic methodology for example, is the systems development lifecycle (SDLC) waterfall model. Two more are outlined in The Cathedral and the Bazaar, which — at the risk of inflating esr’s ego more than necessary — is probably one of the most influential books on the practice of software engineering ever, since most of the so-called “new” methodologies that are en vogue today are basically ripped straight from CatB, rewritten in the language of corporate managers.
>since most of the so-called “new†methodologies that are en vogue today are basically ripped straight from CatB, rewritten in the language of corporate managers.
It’s often less direct than that, I think. CATB influenced the group that wrote the Agile Manifesto (at least, that’s what a couple of the drafters have told me). Many of the current fads seem to start from the Agile Manifesto. I do think there’s more direct influence from CATB among programmers and comp-sci types, and it has shown up of various lists of most seminal papers, but if most managers regularly made a habit of listening to programmers and comp-sci types when they chose development policies the world would look different than it does.
I think thats a little unfair. I think it’s more accurate to say that (at least some of) the new methodologies have taken a similar set of inputs and experiences and ended up at much the same place after taking a circuitous route. And I think you can see this by examining past the superficial to the nuts and bolts of how they work (kind of like how we can make a fair guess as to genealogy of tcp stacks by how they respond to christmas tree packets).
Best example I can think of is that although agile and XP are very conceptually compatible with the ideals of open source, you would have to play fast and lose with the XP principles to apply them to an open source project? Why? XP really wants everything on-site. Open Source is the diametric opposite of that.
The reason for this divergence is obvious. XP (and the fundamentals of Agile) came to this point from a perspective of a communication disconnect. Everyone was throwing “design” documents over the development wall(in both directions) and no-one has a bloody clue what they mean. So the overriding theme of XP is improving communication. Since the highest communication bandwidth you can get is talking face to face, thats what XP really wants.
For development purposes, open source had communication licked before it even existed. As far as open source is concerned the developer IS the customer. The reason why open source is built around remote work is because the chances of getting a critical mass of volunteer developers all co-located is almost certainly nil. Comparatively XP has no problem getting whatever mass of developers they like, so long as the money holds out.
P.S. i’m basically talking about Agile-like processes(e.g. Scrum, XP) which, from my perception, are the new sexy in that space. YMMV.
>I think it’s more accurate to say that (at least some of) the new methodologies have taken a similar set of inputs and experiences and ended up at much the same place after taking a circuitous route.
There’s truth to that, too. CATB influenced the “agile” crowd, but the tradition and concerns CATB articulates wasn’t at the center of their history. I’ve had some interesting conversations with three of the key people in that crowd and have a pretty exact model of what happened.
“I always point to non-US numbering of floors in buildings to explain the zero-index thingy to noobs.”
That’s a misunderstanding. Although “ground floor”, “first floor”, “second floor” may sound like 0-based indexing, in fact what it means that the “ground floor” is not part of the array at all, because the “ground floor” is considered an istance of a different class than from the all other floors which are “hanging in the air”, this is why there are usually different class names (nouns) for them and not just different array indices, f.e. in Austria the ground floor would be Erdgeschoss or Parterre, but all the other floors are Etages or Stocks. So basically there is one instance of the Erdgeschoss class plus a 1-indexed array of Etages.
@esr: Are you certain you’re not just being modest? I mean, it’s pretty hard to deny the parallels, particularly with the Agile manifesto, as they are very obvious.
Principles behind the Agile Manifesto (PBAM)
…
Cathedral and the Bazaar (CATB)
PBAM
CATB
PBAM
CATB
PBAM
CATB
Another iteration of the “Release early, release often” mantra. You make the statement in a more roundabout way:
PBAM
CATB
PBAM
CATB
>@esr: Are you certain you’re not just being modest?
Since you mention it, no, I’m not certain.
But, even supposing I thought it were true, what good would it do for me to run around claiming to be the grandfather of the Agile Manifesto? I’m already as famous as I want to be; the important thing is that I influenced those people in a good direction, not whether I get public credit for doing so. And if I tried to collect that credit, what I know I’d get is another ration of shit from the legion of idiots who think my ego is the size of Betelgeuse.
No thanks. Indeed do my tentacles spread far and wide, bwahaha, but it is sometimes better that the world remain unsuspecting. Less hassle that way.
hardly an original idea there, eric.
did you borrow it without attribution as you did recently with the wikipedia quote?
>hardly an original idea there, eric.
Reaching pretty hard, there, aren’t we? Don’t strain yourself.
In fact, I’m completely unsurprised that Aho came up with that notion independently of me. I know of at least one other person who got there independently of both of us. It would be hard to avoid having the same insight above a certain minimum level of mathematical literacy that isn’t actually very high.
It would be hard to avoid having the same insight above a certain minimum level of mathematical literacy that isn’t actually very high.
Yes, “function composition is pipeline sequencing” is mathematical folklore. You’d know this simply by looking at a commutative diagram, but this is also why many category theorists write function composition from left to right, and why the Z notation includes “outlined semicolon” as a left-to-right composition operator. Note that Xah Lee’s post did not mention monads, but see Dan Piponi on Commutative monads, diagrams and knots for a related discussion.
>The short answer is that Lua was designed and intended for a user/programmer community who thought that 1-based was more natural.
I watched the video. They inherited this perversity from FORTRAN via civil engineers.
Gaaaaah. All too often, just when you think an old, bad, design choice is dead with a stake through its heart, the revenant reaches from its grave to corrupt the living…
> As for newbies, when you stop talking about application packages and start talk about programming languages, you expect your target audience to be grown-up enough to be able to adjust to the new convention.
In other words, you are even more bothered by Lua’s syntax, namely that it isn’t lisp-like…. (1-based indexing is a small sin by comparison.)
Languages get acceptance by solving problems for users better than those users’ alternatives. Lua was actually successful long before computer folks heard of it. 1-based indexing is part of that.
Excellent work, ESR. Someday you will become very good at programming in Haskell, and perhaps even make some open source Killer Apps with it. We can hardly wait.
What sort of non-trivial programs can one make with Haskell? That Haskell is well suited for, that is.
>> It would be hard to avoid having the same insight above a certain minimum level of mathematical literacy that isn’t actually very high.
> Yes, “function composition is pipeline sequencing†is mathematical folklore.
So, you claim to have the same idea, and claim to be a mathematician, but that idea is ‘mathematical folklore’.
I also find it interesting that you didn’t answer my question.
Oh yes, definitely. :) But counting from zero is an easy hurdle for people to overcome; embracing parenthetical syntax, code-as-data, and macros is… a bit harder. :)
Great essay, esr.
I’m a bit late at the party, but I was a little stunned by the simultaneously ignorant and pretentious nonsense being spread by
“T” above at http://esr.ibiblio.org/?p=1796#comment-250787 and by the breathtakingly careless and uninformed “Roger Phillips” throughout. sclv makes most of the points I would have wanted to at http://esr.ibiblio.org/?p=1796#comment-250850
But the darcs bullshit is especially cretinous. darcs is a C++ program ported by the author to Haskell, and the ‘cargo cult mathematics’ embodied in it already existed in the C++ version. It was ported to Haskell on account of the advantages the latter gives to the formulation of ideas of the quite abstract and formal type Roundy had. The various analogies he used in coming up with the darcs idea were quite clearly founded on genuine mathematical and physical understanding, and it is simply a criminal act to compare his actions with ‘air guitar’ math. The kind of person who would say that can only be projecting: if I ever saw anything aptly described as ‘air guitar math’ it’d be the remarks of T and Roger Phillips above.
esr, re Darcs and version control, you may want to check out ‘A Principled Approach to Version Control’ by Andres Löh. Get it here: http://people.cs.uu.nl/andres/VersionControl.html
“I prefer Larry Wall (not snobish linguist)over Dijkstra (snobbish mathematician) any day.”
I prefer intelligent knowledgeable people over ignorant morons like Tom DeGisi.
And I wrote that before I clicked on his name and discovered he’s a Tea Partyer.
“On the gripping hand there is no year zero, either.”
Yeah, because we celebrate our first birthday on the day we’re born.
Imbecile.
I don’t understand why people say Haskell has no variables. It has variables in the totally ordinary sense, both mathematical and as in other languages. You just cannot assign to them. In the terminology of C, they are all “const.” But a const lexical variable is not the same thing as a constant. Saying that these are not variables is just going to mislead people who don’t know anything about the language.