You are viewing pozorvlak

Beware of the Train - Onageristic speculation [entries|archive|friends|userinfo]
pozorvlak

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| My moblog Hypothetical, the place to be My (fairly feeble) website ]

Onageristic speculation [Feb. 12th, 2008|10:26 am]
Previous Entry Add to Memories Share Next Entry
[Tags|, , , , , , , , , , , ]

I'm going to make what should be an uncontroversial statement: if you don't understand and use monads, you are at best a quarter of a Haskell programmer. A corollary of this is that, since using monad transformers is the only (or at least the approved) way to use two or more monads together, if you don't understand and use monad transformers you are at best half a Haskell programmer.

[Another corollary is that I am, at best, about an eighth of a Haskell programmer: though I understand monads well on a theoretical level, I invariably emerge defeated from any attempt to bend them to my will.]

But we'll come back to that later.

Something I've been thinking about for a while is this whole business of designing languages to make programs shorter. There are two factors here, of which only one has a good name that I'm aware of: so let's say that a language is terse if its tokens are short (\ instead of lambda, for instance), and concise if it requires few tokens to express the same algorithm. As antonyms, let's take sesquipedalian and verbose1: so a language is sesquipedalian if all its tokens are long (call-with-current-continuation instead of call/cc), and verbose if it requires more tokens than usual to express algorithms on average. Terseness depends to an extent on the programmer, but most languages have community norms about whether you should call your variables loopCounter or i, and these are usually influenced by the keywords of the language itself.

These axes are independent: Perl is terse and fairly concise, Common Lisp (and to some extent Haskell) is sesquipedalian and concise, C is terse and verbose, and Java (everyone's favourite whipping boy) is sesquipedalian and fairly verbose (but nothing like as badly as, say, COBOL). Python is approximately as concise as Perl, but less terse. It's often remarked that APL, J etc are extremely terse; what's often overlooked is that they're also extremely concise. In my recent post about code-walking in various languages, the K solution was the shortest, even after the tokens were written out as full words to correct for the effects of terseness. This is fairly typical, in my limited experience.

That's an interesting data point - it would be interesting to know why. Let's compare them to some other concise languages to see if there's a common theme. The two concise languages that immediately spring to (my) mind are Lisp and Smalltalk2. What makes them concise? The obvious answer is "metaprogramming", for which Lisp and Smalltalk are famous, but there's another answer: they're both monistic languages. In Smalltalk, everything is an object. In Lisp, everything (well, almost everything) is an s-expression. And it works for the APL family too: in APL, everything is an array3. This means that you're dealing with a monoid of types and functions rather than a category, and monoids are much easier to deal with. My guess is that that makes it a lot easier to come up with a small, orthogonal, reusable set of operators, out of which your programs can be constructed simply. If the function you need is in the standard library, you don't have to write it. Now compare that with a language like Pascal: up until a minute ago, the type you're using didn't exist, so you need to write all the code to manipulate it. And since it's a one-off, you're probably not going to spend the time polishing your operator set until it's optimal4.

Is monistic design always a good thing? No - think about B, which had only one type (the machine word). Representing all your data as raw machine words was, by all accounts, a pain in the neck, which is why C was developed. But representing your data as s-expressions or arrays or objects is usually fairly easy. From this point of view, the concision of the APL family is not a mystery: Iverson chose a highly expressive basic structure for his single type, and a damn-near-optimal set of operators for it. I actually have a paper sitting in my "to read" folder called "About the Completeness of APL": not completeness in the sense of Turing completeness, but in the sense that any generic folding/spindling/mutilating of arrays can be expressed as a finite sequence of APL operators (I don't know if, or how, that's a stronger result than Turing completeness, which is why the paper's in my "to read" folder).

Of course, no single choice of data representation can be the One True Thing: sometimes you really do want a hash rather than an alist, or a record with named slots rather than a pair of arrays. But a good choice can get you a long way, and a language that makes the right things easy and the rest at least possible is a major win.

Let's think about Perl. Everything is a scalar. Unless it's an array. Or a hash. Or a glob. OK, that's four types: we can live with that. And globs are pretty rare anyway. We can set up a reasonable category of basic operators shuffling between three points, and the extra representational flexibility is handy. Note, incidentally, that Paul Graham has gone down this route with Arc, which has built-in hashes (which always seemed like second-class citizens in previous Lisps - correct me if I'm wrong, please).

Now let's think about Haskell again. At first sight, Haskell falls into the Pascal trap: programmers are encouraged to declare their own types for everything, and strong typing and lack of reflection makes it hard to write generic operators that work for many types5. And yet the language is fairly concise. Huh? Is everyone just ignoring "good" practice and doing everything with lists, like they were using a crippled version of Lisp? Well, yes, and it's noticeable how good Haskell's list-manipulation libraries are, but there's more to it than that.

Here's what I think is going on. Like I said above, you are at best a quarter of a Haskell programmer if you don't understand and use monads. But what is a monad? Well, as a category theorist6 I think of monads as (a generalisation of) algebraic theories - that is, as APIs (I have a post about this idea half-written). As a programmer, the interesting thing about monads is not that you can swap them in and out when you want to change your model of computation half-way through development (I'd love to hear of even a single case where that's happened) - it's the fact that you can write useful utilities like seq and liftM2 and friends, that work across all monads. A simple, orthogonal, highly reusable set of operators, abstracted across APIs.

So I think the Haskell people are doing something very interesting: they've pushed the monism up a level. Everything is a List or a Maybe or an IO or a Hoojimaflip or an AquaTeenHungerForce or whatever: but all of those things are monads. So you get the orthogonality benefits of monism, without the loss of representational flexibility. You have to write a bit more code when you declare your datatypes, but maybe this can be a good trade-off.

An onager, by the way, is a wild ass.

1 There really ought to be a word that means "would never use a twopenny word when a half-crown word would do", but I can't think of one. English grads? Edit: sesquipedalian! Of course! Thanks, fanf! (Originally, I used "prolix")
2 I actually came up with this list by thinking about languages whose users were the most passionate. But they're also extremely concise, which I think is a large part of the reason for the passion. If I were focusing purely on concision, I should probably consider Forth, but I don't know enough about it.
3 J has "boxed arrays" too, which are something like two-dimensional s-expressions, but let's leave those aside for now.
4 You might want to raise this objection against Smalltalk, too: objects are members of classes, which are something like types. Now, I've hardly used Smalltalk, so I'm probably talking out of my elbow, but: since everything is an object, and the language has powerful reflection features and duck typing, we can in fact write generic operators that work for objects of many or all classes. But maybe I'm entirely wrong about Smalltalk programming: in which case, please delete all references to the language from my argument.
5 Do you find yourself wanting to go out and strangle small fluffy animals every time you have to type out an instance declaration that would be entirely unnecessary in a duck-typed language? I do. Particularly when it doesn't work and spits out some ludicrous error message at me, telling me that I've encountered another stupid corner case of the typeclass system.
6 I learned to my surprise the other day that I'm a member of the Geometry and Topology research group, and not the algebra research group as I'd always assumed - apparently universal algebra is now considered a branch of geometry!
linkReply

Comments:
[User Picture]From: michiexile
2008-02-12 12:08 pm (UTC)

(Link)

Of course you're in Geometry and Topology. It is well-known, after all, that since Category Theory stems from Topology, you cannot possibly do CT and NOT be a topologist.

Or something.
[User Picture]From: pozorvlak
2008-02-12 01:28 pm (UTC)

(Link)

I think it's more that my supervisor is a topologist, on some level at least - his current research is about calculating Euler characteristics of categories, as part of a larger project of dealing with self-similar objects (such as fractals) using category theory.
[User Picture]From: michiexile
2008-02-12 08:27 pm (UTC)

(Link)

That project of Leinster's sounds insanely cool. You able to summarize it in more technical terms for me?
[User Picture]From: pozorvlak
2008-02-12 08:58 pm (UTC)

(Link)

Not all that well - I haven't looked into it in all that much detail. The basic idea is to approach self-similarity from the top down, rather than the bottom up: that is, instead of providing a rule to calculate if each point is in the set, you say "this set is composed of n copies of itself, glued together like this...". Rigorously, you express this as a functor: you form a category of spaces with some specified attaching points, and then construct the endofunctor which takes a space and returns n copies of it glued together according to the instructions. If I'm remembering right, this functor is actually a comonad. The space you're interested in is then the initial algebra (or maybe the terminal coalgebra) for that endofunctor. This can be made to work for at least some Julia sets, and probably all of them: you also get things like the Cantor set, Koch snowflake, and various others arising out of it. Perhaps more interestingly, you get things like the real interval [0,1] and L1[0,1] arising in this manner, neatly skipping all the steps that you usually have to go through to construct them (and in the case of L1[0,1], you get integration arising as the unique norm-preserving map to R).

Tom's hope is that characterising fractals in this way will allow us to calculate things like their homology and homotopy groups which are hard to calculate from a bottom-up perspective.

There's an overview paper here, which is a few years old and pre-dates the Euler characteristic stuff. The Euler characteristic paper has some unpleasantly technical sections, but is mostly pretty readable: see here. And you really should read his paper Objects of Categories as Complex Numbers, not because it's anything to do with self-similarity, but just because it's so damn cool :-)
[User Picture]From: jonjonc
2008-02-12 10:58 pm (UTC)

(Link)

Sounds a bit like iterated function systems?
[User Picture]From: pozorvlak
2008-02-12 11:17 pm (UTC)

(Link)

Yes, they're definitely in the same ballpark: neither I nor Tom know precisely what the connection is, though :-)
[User Picture]From: necaris
2008-02-12 12:18 pm (UTC)

(Link)

C is terse and verbose
Which makes wonders like the IOCCC possible ;-)
[User Picture]From: thesz
2008-02-12 01:01 pm (UTC)

(Link)

Do you find yourself wanting to go out and strangle small fluffy animals every time you have to type out an instance declaration that would be entirely unnecessary in a duck-typed language?

Rarely, if ever. And I earn a living coding Haskell.

I did a count on some of my haskell files. I wrote 19 instances, mostly for Show/Eq/Ord and some 5 instances for my own Byteable class. Complete line count is over 6000 LOC.

So - no, I didn't.
[User Picture]From: pozorvlak
2008-02-12 01:53 pm (UTC)

(Link)

So, you didn't have to write many instances (I'm genuinely surprised how few - shows what I know), but do you have to keep a bag of kittens on your desk for when you do need to write an instance declaration? :-)
From: (Anonymous)
2008-02-12 07:53 pm (UTC)

Automatic derivation

(Link)

I wouldn't be surprised if the reason he didn't have to write so many is because the 'deriving (..)' feature covers most of what you want (and libraries like DrIFT can derive even more beyond just what GHC can). It's quite nifty.
[User Picture]From: pozorvlak
2008-02-12 09:12 pm (UTC)

Re: Automatic derivation

(Link)

GHC can never derive the classes I want to use, even when it would be easy to do so programmatically :-( I haven't tried DrIFT. What would be cool is if you could add a bit of Template Haskell or something to be executed whenever someone tried to derive an instance of your class.
[User Picture]From: fanf
2008-02-12 01:09 pm (UTC)

(Link)

An interesting post!

What you call "monistic languages" I have called "eigenlanguages".

There really ought to be a word that means "would never use a twopenny word when a half-crown word would do", but I can't think of one. English grads?

I'm not an English grad, but you might be looking for the word "sesquipedalian".

Regarding B (and BCPL) I believe that one of the main motivations for adding types to C was to make the language work better on a small machine with byte addressing. BCPL came from big machines with word addressing, so awkward string handling and floats the same size as ints came with its territory.

[User Picture]From: pozorvlak
2008-02-12 01:52 pm (UTC)

(Link)

Now that is an interesting post! I took the term "monistic" from philosophy, in which monism is the belief that there's only one kind of substance in the universe (leading contenders being Mind and Matter). Though I don't think we're talking about quite the same thing: an eigenlanguage, as far as I can tell, is a language which has exactly one idea, and strips out everything not necessary for the expression of that one idea. So monism would be one approach to designing eigenlanguages, but there are probably others. And your eigenlanguage has not only one datatype, but also only one data structure! I can't decide if that distinction's significant: I suppose a monistic language with many variables would also be implicitly manipulating a symbol table, but a "universal" datatype that can't represent symbol tables isn't going to be much good!

Sesquipedalian - perfect, thanks! I thought it referred exclusively to the words, but on looking it up I see that it can also be applied to their users.
[User Picture]From: fanf
2008-02-12 02:10 pm (UTC)

(Link)

I think there are different degrees to which a language can be monistic. (Hmm that's a more convenient adjective than one can get from "eigenlanguage".)

One of the key early ideas of the computer revolution was monistic: treating code and data in the same way. However most languages have a Harvard architecture, not a von Neumann architecture. Notable exceptions are Lisp and Forth. In the process of its shotgun marriage, my language lost this property.

More generally, if you want a language to be useful you can't push a single concept too far.

Another example is the use of combinator reduction in early normal-order languages (especially Miranda). Though S and K are a sufficient basis for implementing the lambda calculus, they aren't very efficient, so practical graph reduction engines used several additional combinators. (After a while they worked out how to compile code into custom "supercombinators" which made the simple but beautiful SK machines obsolete.)
From: evan
2008-02-12 06:02 pm (UTC)

(Link)

As a programmer, the interesting thing about monads is not that you can swap them in and out when you want to change your model of computation half-way through development (I'd love to hear of even a single case where that's happened)

During an ICFP contest: part of a programming challenge was discovering the extent of the problem you're trying to solve. So the initial hurdles needed you to just find the one specific combination of pieces, if one was available -- the Maybe monad. Then in later problems, it turned out you needed to try all possible combinations; I switched to the List monad, and that was pretty amazing.
I wrote more about the problem here: http://community.livejournal.com/evan_tech/192659.html

However, I agree this sort of thing is rare. I find I most commonly switch between Maybe and Either String (from Control.Error), and also from IO (while refining an algorithm) to a more specific monad, like Writer or State.
From: evan
2008-02-12 06:11 pm (UTC)

(Link)

In general, from skimming your posts on this, I think your frustration may stem from having a model of thinking about the world -- e.g., phrases like "lack of reflection" -- that are just not compatible with the Haskell world view. I like to think of it as if the code and data are on separate planes of existence; like how in math an integer can't reach out and talk about functions because they're just fundamentally different beasts.

I don't mean to claim these views are "bad" or "short-sighted", just that when in Haskell, you have to do as the Haskellers do. And if another view works better for you, more power to you; I'm happy to use Perl to solve a problem when it's the easiest way.
[User Picture]From: pozorvlak
2008-02-12 09:21 pm (UTC)

(Link)

But code is data! And thus code can be calculated for you...

You're right, a large part of my frustration is because I don't share Haskell's unusual world-view. I recognise that there are good things there, but getting it involves having to give up other good things that I've learned to value (like dynamic typing, or the "code is data" axiom and all that flows from it). It's a struggle. I'd like to get better, but getting better would involve writing lots of Haskell code until it clicks, and writing even trivial amounts of Haskell code currently involves spending all day beating my head out over compiler errors until I want to go out and drown things.

I don't mean to claim these views are "bad" or "short-sighted"
Thank you :-) All too many Haskellers would claim exactly that, and probably insult my intelligence and personal hygiene into the bargain. I know any community has its idiots and fanboys, but Haskell does seem to have rather a lot of them :-(

[Maybe I'm getting a bad reaction because I'm being too antagonistic? I don't think so: I often get a bad reaction even when I try hard to be polite.]
[User Picture]From: pozorvlak
2008-02-12 09:23 pm (UTC)

(Link)

NB: a lot of Haskell users are extremely helpful and friendly, including most of the ones who comment here - it's mostly elsewhere (Reddit, other blogs) that I've encountered the stupid and rude ones.
[User Picture]From: michiexile
2008-02-13 08:30 am (UTC)

(Link)

These reactions actually surprise me. Ok, I almost only interact with the Haskellite scene on LJ and on IRC, but one of the things I find remarkable with the community is the friendliness and helpfulness I perceive among them.

As a contrast, almost all contact I've had with Ruby programmers so far has been confrontative, protectionistic and partially downright ugly. Even though I had legitimate n00b questions, I fled #ruby as soon as I possibly could. I got more help out of #haskell with my Ruby questions....

All that said, Haskell is quite a change in worldview, and the Already Converted can be a bit .. bombastic in their advocacy at points.
From: (Anonymous)
2008-02-13 01:48 pm (UTC)

(Link)

That's a dang shame... #ruby-lang used to be a really nice place.

#rails used to be the wasteland.
From: (Anonymous)
2008-02-12 09:40 pm (UTC)

(Link)

Code is data, sure, and well supported by Haskell -- what else are functions constructed and passed around at runtime?

Not all data is code, however.
[User Picture]From: pozorvlak
2008-02-12 09:46 pm (UTC)

(Link)

They're code of a very specific type. I'm used to scripting languages, passing around closures is not a big deal :-)

And, to quote Sriram Krishnan, "The progression of a Lisp programmer: The newbie realizes that the difference between code and data is trivial. The expert realizes that all code is data. And the true master realizes that all data is code."
From: evan
2008-02-12 11:44 pm (UTC)

(Link)

Like any religion, the Haskell community will inevitably attract people who want to believe in the one true way. But that's also true of you in your "code is data" axiom, which you seem to be reluctant to relax, even in the interest of expanding your perspective.

Another way of looking at many of the bargains Haskell makes is that you're collaborating with the compiler: "If you guarantee not to have side effects in this function", it will say, "I'll agree to optimize your code in a way that's impossible in those other languages, and also less you express it more succinctly than previously thought possible." Or similarly with static typing (which is a rathole of an argument that I'm way beyond arguing).

I'm a little surprised you've encountered insults in the Haskell community. One of the nice meta-effects of how difficult it is to become a Haskell programmer is that the people who are really good at it tend to be too intelligent to resort to petty insults (like the "static thinker" jest so often trotted out by the Lisp community). But I think no group is beyond fundamentalism; in my experience, Haskellers just tend to be more erudite when going about it. :)
From: (Anonymous)
2008-02-12 06:14 pm (UTC)

Lack of reflection

(Link)

Regarding the "lack of reflection", I'm finding more and more in production systems that the SYB-style Data.Generics reflection is extraordinarily useful.

An example, derive Data on some type, and you can reflect
some data into its AST, then use that to write a custom database query for different constructors of the type.

Haskell has reflection, built in, and its useful.

-- dons
[User Picture]From: pozorvlak
2008-02-12 09:28 pm (UTC)

Re: Lack of reflection

(Link)

Cool! Can you point me at some example code where you use it?

It's good to see the "boilerplate problem" getting attention - for me, it's practically a showstopper.
From: mtbc100
2008-02-25 04:40 pm (UTC)

Re: Lack of reflection

(Link)

I think last time I used it I wanted to see where a particular fragment of a nested algebraic datastructure appeared within a different larger one as one of its parts. (It was a thing that was meant to recognize certain user-specified patterns appearing – once it had found a match, it'd act.) I hope that was at least a little coherent.
[User Picture]From: bronxelf_ag001
2008-02-12 07:11 pm (UTC)

(Link)

I have no idea what any of this means.

Aside from now feeling like an idiot, I still find it really fascinating. Lexicon is such weird stuff.
[User Picture]From: pozorvlak
2008-02-12 09:54 pm (UTC)

(Link)

Don't worry about it - I'm sure you could lose me equally easily talking about any of your areas of expertise :-)

[Short version: since the range of possible data is infinite, programming languages usually give you some basic types, and you then construct the data representations you want out of those basic types. The precise choice of basic types varies from language to language. Having only one basic type sounds stupid, but if done intelligently can actually be a pretty good idea, as it allows you to build up libraries of code that can be used everywhere. The Haskellers, I think, are doing something a bit more subtle: they have many basic types, but most of the important ones are all of one - er, let's say "substance", so they've pushed the "only one" bit further up the chain.

This is deeply pointless abstruse stuff, and it's all wild-ass speculation anyway :-) ]
[User Picture]From: necaris
2008-02-13 12:03 am (UTC)

(Link)

This is deeply abstruse stuff

So much so that even some programmers don't grok it -- but then, I've never touched Haskell with a bargepole.

I must admit, though, that the "code is data" axiom is one I love and wish I could use more -- function pointers in C, anyone?
[User Picture]From: michiexile
2008-02-13 08:34 am (UTC)

(Link)

This, if anything, calls for An Anecdote From My Wild Past.

I was working with a previously built crypto library. It would simulate C++-style objects including inheritance by cleverly crafted function pointer lists being handed around all over the place. In this way, the functions calling the library procedures could be made reasonably agnostic about what, exactly, the crypto algorithm underneath was doing.

This all worked quite great until one day a customer asked for Position-Independent-Code and the simulator happily obliged while the real-hardware-compiler choked. Hard.

Thus, three days before world launch of the product, I was sitting late one evening trying to rewrite the entire crypto library from using function pointers to using memory offsets for accessing the functions.
[User Picture]From: pozorvlak
2008-02-13 06:14 pm (UTC)

(Link)

Eeek! I'm guessing this code had an inadequate test suite, so you weren't sure how much you were breaking?

Did you manage it?
[User Picture]From: michiexile
2008-02-13 10:42 pm (UTC)

(Link)

I wasn't sure what I was breaking. I ended up breaking a lot. What was worse was that we had some self-referential measures involved, that I needed to modify; and we weren't allowed to let the customers so much as peek on our source code.

So, at 2.30 am when I was reasonably done, I ended up not checking it in.

And not bringing it back with me.

Which made for great fun when the next fix had to be rolled out. And we had to hotswap the security system on the cell phones, invalidating ALL keypairs already in use.

Not my proudest moment.
[User Picture]From: elvum
2008-02-12 10:17 pm (UTC)

(Link)

Perl: scalars, arrays, hashes and globs, yes, but also subroutines (yes, they're a variable type) and IO handles.

http://www252.pair.com/comdog/mastering_perl/Chapters/08.symbol_tables.html

Sometimes I think Perl has all the makings of a perfectly decent statically typed language... ;-)
[User Picture]From: pozorvlak
2008-02-12 10:27 pm (UTC)

(Link)

Coderefs are scalars :-) Then again, ref(sub { print "I am an anonymous function" }) would return CODE, and ref(\2) would return SCALAR, so maybe you're right. And by the ref test, IO handles are just a form of scalar, though I agree that they're stored separately in the symbol table so you can have a scalar called $FOO and a filehandle called FOO.

Meh. The notion of "type" doesn't make all that much sense in Perl :-)
From: feraldrinker
2008-03-07 05:18 am (UTC)

(Link)

I imagine most Haskellers would rather write an instance declaration than risk runtime errors, but more importantly code is about reading, not writing; surely you'd rather read code with an explicit instance declaration?
[User Picture]From: pozorvlak
2008-03-07 09:48 am (UTC)

(Link)

Interesting point: OTOH, I usually manage when reading code in duck-typed languages :-) In general, I prefer not to tell the computer anything it ought to be able to work out for itself. But on typing, metamoof put it well in this comment a while back: "The whole point is to ignore the type of the object... Given that it's impossible to prove a python program's type correctness, we prefer to not bother, and get on with stuff that actually matters."
[User Picture]From: pozorvlak
2008-03-07 09:52 am (UTC)

(Link)

The real point of that footnote, actually, is that I've had really bad experiences with the typeclass system, which seems to be one of the most ad-hoc and fragile parts of the language. Not to mention that it's easy to paint yourself into a corner with it, like the way you can't define a (+) operator without also defining (-) and (*) operators. The fact that the dynamic languages have shown it's possible to do entirely without such a system, and gain flexibility while doing so, merely adds to the annoyance :-(
From: (Anonymous)
2014-02-04 06:35 am (UTC)

(Link)

Wonderful beat ! I would like to apprentice
whilst you amend your web site, how could i subscribe for
a weblog web site? The account aided me a applicable deal.
I were tiny bit familiar of this your broadcast provided shiny clear
concept
From: (Anonymous)
2014-02-22 09:28 am (UTC)

(Link)

hі!,I like ƴour writing very so much! share we communicate extra approximately your post oո AOL?
I need a specіaliѕt in this аrea to resolve my problem.
Mɑybe that's you! Taking a look ahead to look you.
From: (Anonymous)
2014-03-15 10:50 pm (UTC)

(Link)

Feel secure knowing that only your pet can enter and exit without letting
in raccoons, skunks, and other creatures. Research shows that although
buyers sometimes prefer their self-designed dog houses,
they often complain of high prices involved. It is made to operate in
the same way a heating and cooling system placed
in your home would act.