Posted by Daniel Lyons
Thu, 06 Sep 2007 03:52:00 GMT
Recently I had a kind-of debate with a kind-of friend about programming. It came to basically one thing: do you value readability?
I certainly do. I think one of the things that makes programming interesting is that we’re trying to express something to a computer and another human being at the same time. All programming failures fall on one side or the other of that balancing act.
The argument for readability cannot be absolute though. A hundred lines of Python may be more readable than 20 lines of Haskell. So we have to ask ourselves some more questions besides pure readabilit. We have to ask ourselves if we are following the elements of style. Can we “omit needless words?”
- Does this code communicate in 20 lines the same thing as 100 lines of Python?
- Do we gain from the conciseness?
- Does it take the same amount of time to understand?
- Do we want to constrain all of our developers to the same standard?
The allure of functional programming is that it is both more rigorous and more concise. When you understand a fold, you are tempted to use it even in languages where its application will be awkward or difficult, such as Ruby. This template substitution probably has appeared on my blog before; normally this would be coded as an imperative loop, but I chose to use Array#inject which is basically a fold:
vars.inject(@template.clone) do |template, (region, value)|
template.gsub(/%#{region}%/, value.to_s)
end
In OCaml this would probably have looked a lot more concise than it does in Ruby, and it would be considered more readable. So you have to consider your audience too. Haskell’s audience is smarter than Java’s, or at least thinking in a more high-level way. Though, really, you should try to learn Haskell, it’ll make you smarter. (Or if you’re really vindictive you’ll at least bring the average down.)
So my operative concept is not readability anymore. It’s conciseness. Concise not like Perl or APL, concise like “omit needless words.” It may take you longer to figure out than comparable 5x larger Python code, but it won’t take you 5x longer, and you won’t be falling asleep.
And why do you believe your code is so important anyway? I’d bet 99.9% of code in this world is couch paintings. It seems so important right now. In five years, is it going to be important? Or is it going to already have been rewritten by then? So much code is treated like an investment when it is written as so much slapdash cut-and-paste filler. Other code is written elegantly and perfectly and winds up forgotten because nobody knew how to treat it like an investment. The entities most qualified to treat code as an investment seem to have practices that encourage the quality being the lowest. Hiring lots of developers, outsourcing, having corporate policies about language choice and a complete lack of code reviews have a strong negative effect on code quality.
If we really wanted to treat code as an investment, wouldn’t we want to revel in it a bit more? Read it, really take the time to enjoy it, pass the tricks around the organization? Treat the code like a member of the company rather than a process or, worse, the result of some process like so much insect shit?
And while we’re on the subject, I no longer believe any project really needs more than three developers.
Tags rants | no comments
Posted by Daniel Lyons
Thu, 06 Sep 2007 03:07:00 GMT
I don’t hate a lot of things, though the quantity and ardor seems to increase with every year. I want to share a few of those things with you now, so you can get to know me a little better than you already do.
The top three things I hate are:
- The wrong technology (MySQL and PHP)
- The wrong reasons (couch painting)
- Polyamory (more crap must be better)
Some technological equal-opportunists say things like “every technology has an appropriate use.” Guess what? Some technology doesn’t.
Let’s not beat around the bush. You shouldn’t be using MySQL or PHP. Not on this project, not on the next project, not now, not ever. I don’t care what monstrous shit they’ve stapled onto MySQL to try and make it look like a database or what monstrous object system they’ve stapled onto PHP to make it look like a real programming language. Neither of these things are real, they’re both charlatans and if you’re tempted to use them for a technological reason you don’t understand the problem and you should ask someone who does.
MySQL pretends to be a database. It is no such thing. It is an SQL front-end for a hair-removal tool. Dr. Codd’s Physical Data Independence says your view of the data should be independent of the physical representation of the data on disk. So which integer do you want, the 1-bit, 2-bit, 4-bit, 8-bit, 16-bit, 32-bit or 64-bit? Nevermind, let’s talk about the tables, those are pure relational entities, right? Oh wait, you wanted transactions? I guess you’d better use the InnoDB table type (what happens if you start a transaction and some of your tables are InnoDB and others aren’t?) Nevermind, let’s talk about SQL the standard. How would you like a TIMESTAMP column, that’s standard SQL? Oh wait, that one automagically changes when you update the row, you actually wanted a DATETIME. Want to concatenate some strings? Better remember that the concatenation operator is treated as logical OR in MySQL, or you’re going to see a bunch of 0’s where you expect strings (I know, instead I’ll use the handy CONCAT function!) Does this sound like hell yet? If not, MySQL is for you!
PHP is great, assuming you aren’t the slightest bit interested in consistent functionality across more than one server, like restating things over and over again, prefer your languages guess at what you meant when they can’t quite tell, and have configuration files. Off the top of your head, how many languages can you think of that have configuration files? Did you know PHP doesn’t ever free memory in the core, because it was never meant to be running longer than a fraction of a second? Or that you can define functions inside functions, but they’re actually defined in the enclosing scope (you like warnings, right?) Try accessing an array returned by a function without sticking it in a variable first sometime. And the joy of having dictionaries that are arrays at the same time never ends! What about SQL, PHP’s supposed to have that down, right? Of course there’s the PEAR DB module, which is deprecated, the MDB2 module, which doesn’t work properly on PHP 4, and ADODB, which everyone was using for years before PEAR existed. Oh, and let’s not forget that PHP will helpfully escape those strings on the way in, unless you’ve disabled that in the configuration, or locally with a .htacess, or at the top of the script with a setvariable function call. And my, what consistency in naming conventions! I hope you have a fast link to php.net.
Do not use this software for your own projects unless your husband or wife thinks you would be hotter bald, wrinkled and angry.
Oh, but you don’t have a choice about your deployment software, do you, because your son who’s good with computers already bought you hosting on a $5 a month shared plan, and whatever I write has to work on that thing. This is called the wrong reason. You didn’t call me when you were thinking about writing the app, you called me after you started. This is like calling your plumber with your toilet on the lawn and a kitchen sink on the floor in your bathroom where your toilet should be, and saying, “No, I already bought this sink, you have to make this work.”
Firstly: no, I don’t. This analogy is really much closer to Windows. You called me up and said, “Daniel, you’re good with computers; what kind of computer should I get?” And I said you should get a Mac. You gave me some excuses. I told you to get a Mac anyway. Instead, you bought this PC and now you’re on the phone with me. Why? Because you didn’t do what I said, when I told you what would happen if you got another PC, and you got one anyway, and lo and befucking hold, I was fucking right. What were your reasons again?
- The price. $600 is too much? You can’t afford a computer. Nevermind the fact you spent $1500 on a PC. Doesn’t Apple tell you about their financing?
- You can’t upgrade it. That’s bullshit on a stick. Did you ever upgrade that PC? Of course not. You didn’t do shit with it. You bought another stick of RAM two months before you decided it was toast. Nobody who upgrades their shit for real calls me up asking for help. You want to play upgrade-the-PC? Have a great time. Call me when it’s broken and it’s your peril.
- “But I need compatibility with X!” Have you ever looked at a Mac? For $80 they come with programs that are fully compatible with X. Or for free, if you like NeoOffice. You know something else? Macs run Windows better than Windows computers do, with Parallels or VMWare or whatever. Try that, I dare you. In six months you’ll never run it and you won’t miss it.
- “But what about emailing documents!” What is this, 1989?
- “But my games!” Oh, that’s funny, I thought you had work to do. Because that’s what I was talking about. You want a video game system, buy one. I’m not here to help you get your fix.
There’s a reason all the artists and programmers are using Macs. We know quality when we see it. If you’re using Windows you’re making a statement to the world: I don’t deserve a real computer. Well, stop inflicting it on those of us that do, and get over your $600 sticker shock. Get a fucking Mac already.
Same thing goes for your database. If you need a database, chances are, you have data you want to keep and query. If you need a database, you need PostgreSQL. Not MySQL, not SQLite, a real G-ddamn database.
If you have a program to write, you need to pick the right tool for the job. Sometimes that’s Ruby, sometimes that’s Haskell. There are other languages, sure, but it’s never PHP and it’s never C++.
Would you let your car dealer determine what outfits you wear to work? Of course not. Then why do you let your ISP determine what you write your applications in? They’re your applications, not your ISP’s, for fuck’s sake. When you call up your ISP and ask about PostgreSQL you should hear one of two things:
- Oh, actually we recommend all our customers use PostgreSQL because it’s faster and doesn’t lose their data.
- It’s installed, have fun. We don’t give a damn what you’re up to.
If you instead hear one of these responses, get a new ISP:
- We recommend MySQL, because it’s [faster, better, more reliable, some other lie]
- We only support MySQL. (Who’s asking about support, asshole?)
- Let me transfer you to someone who can answer your question.
So you got the wrong ISP. So what? You dated the wrong people in high school. Now you know better. Quit trying to justify your stupidity by hand-waving, referencing other companies, or talking about popularity. Yeah, it’s true, doing things the right way is hard.
I don’t really have a good segue to polyamory but that’s a rant for another time anyhow.
Tags rants, technology | no comments
Posted by Daniel Lyons
Thu, 06 Sep 2007 02:38:00 GMT
I have a number of rants in me that I haven’t had time to get out. But let’s talk about one of them for right now. Let’s talk about what it means to be ACID compliant.
ACID stands for Atomic, Consistent, Isolated and Durable. It refers to transaction support in some kind of data storage mechanism. According to my twisted view of open source databases, I think it became a big deal because for many years it was something PostgreSQL had that MySQL did not. Of course nowadays MySQL does have transactions and ACID compliance, assuming you put the correct non-SQL-92 conforming magic runes at the end of your table definitions, your copy of MySQL was compiled to support it, and you don’t mind losing the highly-touted screaming fast performance characteristics of MySQL’s stupider table “type.”
Each of these terms means something in particular referring to the way your system deals with transactions.
Atomic means that everything you do in your transaction either applies or it doesn’t. To the user, it means if part of what you’re doing fails, the whole thing fails. But it also means that if the whole thing succeeds and the database crashes, it either has all of the changes or none of them. All of the work in the transaction is one little bundle to the database, even if something goes wrong.
Consistent means, once you begin a transaction, your view of the data in the database will not change, even if other people are making changes at the same time. If you read the list of users at the beginning of the transaction, wait 900 years and read them again, you’ll see the same list of users, even if someone else has come along and deleted them, or the usual creation/deletion churning has occurred in the intervening time. Your view is completely static until you commit the transaction. Other people’s changes do not leak in.
Isolated means that your changes to the database cannot be perceived by other users until your whole transaction is complete. If you start a transaction and empty the users table, wait 900 years and then commit, in the intervening time, everybody else has still been able to log in and use their accounts. Your changes don’t leak out.
Durability means once you commit, your changes are permanent. Permanent in the sense of mortality. Permanent as in only a hardware failure can muddle them, and even then it cannot undo them.
There are a number of interesting things about ACID compliance. One that comes to mind is ACID compliance is not automatically inherited by systems built on ACID compliant systems. Suppose you have a database for keeping personnel data. Suppose Joe wants to give the programmers a raise and some extra vacation time. Suppose Joe goes down the list manually editing each programmer’s record in the payroll database. If the system is dumb, it will treat each change as its own transaction. If the check writing program comes along and starts running while Joe is going down the list of programmers, some of them will get checks with the raise and some will not. The check writing program is getting an inconsistent view of the data because the application wasn’t written to use the database in a way that guaranteed isolation.
Tags database, theory | no comments
Posted by Daniel Lyons
Sun, 02 Sep 2007 22:51:00 GMT
This is my response to the question as asked on programming.reddit.com.
Depends on the kind. In terms of functional programming, I understand a combinator to be just a less frightening word for higher-order function. So a combinator is a function that combines the behavior of another function with its own. A good example is filter, which just removes certain items from a list. You make a short boolean function that tells you whether or not an item is worth keeping and combine it with filter and some list, and you get the list of items you wanted.
The effect is best illustrated in Haskell where you can call a function with fewer arguments than it requires. This is usually called currying. Supposing our function for determining whether or not an item is interesting is just called interesting, you can create a new function which just gives you back the list of interesting items in a list like this:
neatItems = filter interesting
For the sake of argument, suppose you consider every number one less than a number evenly divisible by three to be “interesting.”
interesting x = x `mod` 3 == 2
Try it out:
neatItems [1..10] -- produces [2,5,8]
The fun doesn’t stop here! Functional languages provide functions with no name for those times when you need to pass something to a combinator but don’t want to bother making it a name. This is usually called an anonymous function or a lambda abstraction. This means you can make neatItems without going to the trouble of defining interesting first, if (for example) you would never use it except in this function anyway:
neatItems = filter (\x -> x `mod` 3 == 2)
Incidentally, whenever you define a function that takes one or more parameters without specifying their names by using combinators, as above, you’re using what’s called points-free style. To facilitate points-free style, you can switch between names and operators in Haskell quite easily by inserting parentheses and back-tics. Haskell lets you use any binary function in-line as an operator if you put back-tics around it, or an operator as a prefix function if you surround it with parentheses, such as (-).
If you want to “curry” an operator, such as to produce a function that multiplies by two, you just put the value inside the parentheses on the side you want. Thanks to basic arithmetic, (2*) and (*2) are the same, but the variable which is “curried” is different depending on the form (the first in the first, second in the second). A “curried” operator is called a section, and I have no idea why.
Another common combinator is (.), the dot operator. Dot lets you string together functions. Suppose you have a function which takes bread and makes toast, and another function which takes toast and butters it. You could glue these two functions together with (.) and arrive at a new function which takes bread and makes buttered toast:
butteredToast = butter . toast
We can now take the above example of filter to its logical extreme by defining our “interesting” test function with sections and the dot operator:
neatItems = filter ((==2) . (`mod`3))
Now there’s no points in that function at all. It’s not exactly a win for readability in this case, however. :) A slight improvement can be made by eliminating some of those parentheses with the ($) operator, which just takes everything on the right-hand side and slaps it into parentheses as an argument to the left-hand side:
neatItems = filter $ (==2) . (`mod`3)
Eh. Still not a lot better. I’d probably take the lambda abstraction over that unless I was feeling feisty.
Combinators come up more frequently in making libraries, much like dynamic method resolution in Ruby. A great example is Parsec, which is a parser combinator library. By introducing its own BNF-style operators, Parsec lets you define parsers in a BNF-reminiscent domain specific language. It’s also good for testing because you can separately test each constituent part’s parse directly rather than being stuck with parsing whole documents. It’s also quite fast. An example from Write Yourself a Scheme in 48 Hours:
parseNumber = liftM (Number . read) $ many1 digit
parseExpr = parseAtom <|> parseString <|> parseNumber
It looks like you’re just defining a kind of token. Actually you’re defining a function with a pretty rough specification, but that’s not your problem as the API’s user. All you have to know is how to use it to parse, which looks like this:
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right _ -> "Found value"
I hope this answered your question!
Tags haskell | no comments
Posted by Daniel Lyons
Thu, 30 Aug 2007 09:34:00 GMT
Plan 9’s emacs(1) manual page.
Tags humor, plan9 | 1 comment
Posted by Daniel Lyons
Thu, 09 Aug 2007 05:59:00 GMT
My wonderful arch nemesis Kirit Sælensminde is up to his dastardly old tricks again. Erlang must be officially in the cool now, or else no one would be trying to demonstrate that their language of choice (or invention, to Kirit’s credit) maps perfectly onto it, or vice-versa.
Let’s talk about the semantic differences:
- Erlang messages are one-way. All OO languages have call-return semantics.
- Erlang’s functions and message passing systems are fully orthogonal.
Erlang is much, much weirder than your run-of-the-mill OO language. But of course we can dig out examples that are different from your run-of-the-mill language—my favorite example is Io. In Io, you can prefix your message with @ to get a transparent future, or @@ to send an asynchronous message altogether. (Of course, let’s forget for a second that Io is implemented with user threads, so it doesn’t scale anything remotely like what Erlang does on huge quantities of processors.) But in Erlang, if you want to return something, you have to send a new message back to the caller. Or two messages. Or none, or whatever.
While we’re thinking of languages with interesting semantics, find me one in which the methods work in a completely different way from the functions. In a decent OO language, you can’t even make a function that isn’t hooked up to a class or an instance.
Also, there are liberties you get with Erlang that you would never get with OO; because the state is just whatever you happen to pass through the listening function. You can call completely different functions when you’re done handling this request, transforming or dropping your state on the floor altogether. This is how you get live code replacement—because there is a boundary between your “behavior” and your “state,” unlike OO where the whole point is to mingle the two ideas.
Then of course we also have implementation differences:
- Starting an Erlang process is cheaper than whatever you’re doing (threads, fork/exec, whatever).
- Sending an Erlang message is cheaper than executing a method.
I think I’m really getting at two ideas simultaneously and I fear I may be muddying the water. The first is that there’s nothing surprising about computational equivalences between Erlang and OO language X. After all, in C++ all those fancy method invocations wind up being function calls inside the compiler, which in turn wind up being jumps or whatever in the binary. What is surprising and obnoxious is the thought that this computational equivalence implies that language X ought to be as great as Erlang (or whatever other language we’re talking about). We’re not ever comparing the totality of language X and Y, just whatever subsets of each that happen to make the discovery of this equivalence easy.
If there’s nothing new about Erlang’s message passing system, then why doesn’t every OO language have the parallelism benefits Erlang has? Joe asserts that the reason is because Erlang is a functional programming language free of destructive assignment, and, by extension, most of what you think of as being state in an imperative language. Isn’t the whole point of OO that your objects have state and behavior and can be carried around as a unit? If Erlang is OO, it somehow wound up there starting from completely different pieces.
Supposing that Erlang is OO but it got there a completely different way, what makes you think Erlang has any ramifications for language X? It seems possible (putting it mildly) that there is more to a programming language than simply what can be proven about it mathematically. That there are aesthetic concerns and pragmatic concerns well outside what can be proven with math. While we were talking about Erlang from an OO perspective, did we mention the utility of its bit syntax? The closest comparison I’ve seen to it is Haskell’s BitSyntax library and even that’s terrible in comparison. And don’t get me started about aesthetics. An anonymous object with a method on it might be “equivalent” to a lambda abstraction, but look at these two things and tell me with a straight face you wouldn’t prefer the OCaml version to the Java version:
// Java
addWindowListener(
new WindowAdapter() {
public void windowClosing( WindowEvent e ) {
System.exit(0);
}
});
(* OCaml *)
addWindowListener (fun e -> System.exit 0)
Erlang is here, now, alive and kicking, gaining in mindshare and popularity every day. It beats the crap out of basically everything else when it comes to concurrency. It has a reasonably large built-in library, it’s been field-tested and really delivered. So what’s with the rush to talk about taking its features to other languages? This is really puzzling to me because Erlang is among my top six languages for implementing damn near anything. I’d vastly prefer it to, say, JavaScript, which is the foundation for Mahlee. JavaScript is a potentially fine language but, as usual from the curly brace contingency, it eschews expressiveness for something like backwards compatibility with menial programmers. Of course semantically I love it, but I love Io so much more I can hardly think about JavaScript. I see it as a web development necessity made tolerable by Prototype, which really is just Ruby for JavaScript when you get down to it.
The rush to pirate the #1 interesting feature from Erlang into various other languages is indicative to me of two things:
- Everyone wants easy concurrency right now, and
- People do not fully appreciate either the mathematical, pragmatic or the artistic value of a programming language.
If people really were interested in a language as a mathematical principle, then they would only program in languages that map directly onto mathematical formalisms, and they’d chafe at the places where the mapping isn’t perfect. Instead, we rely on math when it’s convenient for us, and discard it the rest of the time.
If people really were interested in a language pragmatically, they would see the value of the language as being a holistic experience. I think there are some truly pragmatic programmers in this world using C, C#, C++, Python and Ruby simply because the combination of the language and the library is best for them. It’s extremely contrary to pragmatism, however, to look at other languages solely in terms of collections of ideas which can be stolen. Languages that are assembled this way are rarely beautiful and never mathematical. In general they come out looking like C++.
If people had a taste for languages as an art form, they would certainly find Erlang to be too beautiful in its own right to want to rush out and copy it. And even if they did, for some reason, desire to do that (perhaps because of some great idea which is impossible in Erlang or merits its own language) they would at least have the artistry to not make it another hard to read, hard to parse nightmare like a curly-brace language. I would, in all seriousness, expect it to look more like Haskell. I’d even take a Ruby/Python hybrid, personally, having the keywords and flexibility of Ruby combined with syntactically meaningful indentation/whitespace.
To return to the topic, it’s very easy to look at Erlang’s message passing and attribute the performance and reliability of Erlang to it. This is an error. Erlang’s performance is not a pure math result, but rather a combination of having a very strong theory supported by a very strong implementation and an environment that encourages coding to a certain aesthetic standard that maximizes the utility of the implementation and theory. Threading can be done correctly, beautifully, and so forth but nothing about threading itself or its implementation in threaded languages in any way encourages this—and threading today is considered expert knowledge, practiced very conservatively by most developers if at all, with the vast majority preferring to write unthreaded code or for systems such as web servers backed by relational databases which mitigate the complexity. Ruby, like Io, uses green threads internally yet by the grace of web servers and databases is used to serve millions of concurrently-generated pages daily by everyone using Rails. (And it’s worth pointing out that its user threading is much poorer than Io’s, which is actually quite good for what it is).
Erlang does everything in its power to help you and encourage you to write concurrent programs the right way. Some of this is syntactic—your messages can be of arbitrary complexity and pattern matching makes it quite simple to decide what to do with a given message. Some of this is semantic—you cannot assign to a variable that’s already bound. Some of it is in the standard library, like OTP, which makes it easy to write servers and monitor them. The whole infrastructure is conspiring with the programmer to the same end. It would be a lie to tell someone, “well, you’ve used OO, that’s message passing, that’s basically the same” because they haven’t experienced it in truth. From this perspective saying “Erlang is OO” is completely meaningless because it’s so much less and so much more than OO is. And simultaneously, to say “If you have asynchronous messages, then you have Erlang” would also be a lie, because it’s like pointing to the engine of a car and saying it’s all there is to it.
A language is so much more.
Tags erlang, functional, kirit, mahlee, oop, programming | 2 comments
Posted by Daniel Lyons
Tue, 07 Aug 2007 20:02:00 GMT
If someone searches for something and winds up on your site, does it look like this?
This is completely unreadable. Like probably over 95% of visitors to your site, I showed up because I made a google query and you said something relevant about it. Instead of being able to read it, I’m staring at goddamn keyword confetti. You just cornholed my eyes. Google told me you had great stuff to share with me about whatever it is I’m searching for, but you decided to impress me with your HTTP_REFERER parsing rather than just giving me the goddamn content.
If I want to see the keywords highlighted, I’ll use Google Toolbar or I’ll search with my browser. As an actual user of the internet, I can and do read. Often. You do not have to mangle the layout for people who do not read.
I don’t know who started this fad, but they need to take a little lead in the face.
Tags design, engines, hate, rants, search, violence, web | 2 comments
Posted by Daniel Lyons
Tue, 07 Aug 2007 05:33:00 GMT
Earlier today I thought I’d solidify my understanding of zippers, at least with lists. I’m pretty eluded by the concept for other data structures for right now but I’m liking the idea of it for lists (though not exactly seeing the whole point of it yet).
So I wrote up a quick implementation in Haskell included here:
module Listzip where
import List
data Zipper a = Zipper [a] a [a]
deriving (Show, Eq)
at n l = Zipper prefix item postfix where
(prefix,item,postfix) = doBreak n l []
doBreak 0 (x:xs) acc = (List.reverse acc, x, xs)
doBreak n (x:xs) acc = doBreak (n-1) xs (x:acc)
next (Zipper pre i (x:xs)) = Zipper (pre ++ [i]) x xs
prev (Zipper pre i post) = Zipper (init pre) (last pre) (i:post)
I realized it might be handy to have that be a functor so I can fmap it, so I added a couple more lines:
instance Functor Zipper where
fmap f (Zipper pre i post) = Zipper (fmap f pre) (f i) (fmap f post)
toList (Zipper pre i post) = pre ++ [i] ++ post
That’s cool, because now I can do things like this:
*Listzip> fmap (**2) $ at 4 [1..10]
Zipper [1.0,4.0,9.0,16.0] 25.0 [36.0,49.0,64.0,81.0,100.0]
Baird and I got to talking about things to do with hardware. Knowing what I know about the Warren Abstract Machine, it should be not particularly hard to make Prolog run on a pretty simple piece of hardware. All you need that’s weird is some kind of searchable “database” and a couple of stacks. So then I found myself coding up my zipper again in Prolog:
%% a general list zipper for prolog
zip_at(0, [H|T], Acc, zipper(RAcc, H, T)) :- !, reverse(Acc, RAcc).
zip_at(N, [H|T], Acc, Result) :-
N0 is N - 1,
zip_at(N0, T, [H|Acc], Result).
next(zipper(Left, Item, [H|Right]), zipper(Result, H, Right)) :-
append(Left, [Item], Result).
prev(zipper(Left, Item, Right), zipper(NewLeft, NewItem, [Item|Right])) :-
append(NewLeft, [NewItem], Left).
I think that’s pretty neat. When I was testing it I noticed something else though:
?- zip_at(1, [1,2,3,4,5], [], X), next(X, Y), prev(Y, X).
X = zipper([1], 2, [3, 4, 5]),
Y = zipper([1, 2], 3, [4, 5]) ;
No
?- zip_at(1, [1,2,3,4,5], [], X), prev(Y, X).
X = zipper([1], 2, [3, 4, 5]),
Y = zipper([1, 2], 3, [4, 5]) ;
No
?- zip_at(1, [1,2,3,4,5], [], X), prev(X, Y).
X = zipper([1], 2, [3, 4, 5]),
Y = zipper([], 1, [2, 3, 4, 5]) ;
This is the first time I’ve ever managed to successfully make Prolog code that can be instantiated on either variable! As you can see, if I reverse the variable order on prev, it gives me next’s behavior. Which means prev can be shortened to:
prev(X, Y) :- next(Y, X).
I thought those predicates looked pretty similar!
When Prolog works, it’s so cool!
Tags haskell, prolog | 1 comment
Posted by Daniel Lyons
Mon, 06 Aug 2007 08:55:00 GMT
I’ve been thinking about glue code a lot lately.
As a lazy programmer, I chafe at how much of my time is spent writing glue between two different systems. These two systems usually are pretty similar or I wouldn’t be bridging them. For example, for one client, I’m bridging a templating system and an API for sending email. Obvious. Another client is getting the ubiquitous bridge between the database and HTML for editing. It seems like an awful lot of this code is basically duplicated effort.
The advanced programming languages of today seem, to me, to be focused on helping you be more abstract. In some cases, this pays off immediately in terms of reducing glue. C++ may not have lambda abstractions, but at least I don’t have to write my own quicksort for my weird data structure or weird data types. In a sense, the code that normally would go between quicksort and your linked list or your array or whatever would be glue. In the best case scenario. In the average case, you’d probably wind up rewriting it altogether.
Lambda abstraction is in my opinion fundamental. Without it, there are things you simply cannot abstract out. The Y combinator may not be the most practical tool, but it’s an excellent demonstration of how powerful the tool is. There’s no way in C to abstract out recursion. Yet every language with lambda can. So there is, at least in theory, a whole category of glue that you have to duplicate in languages which lack lambda or equivalent abstraction mechanisms.
Haskell and Forth don’t have much in common, but both have a simplifying concept at the core which enables powerful abstraction of glue code. In Haskell, every function essentially is of one parameter, returning either another function of one parameter or one value. This, plus a general amenability to functional abstraction through higher-order functions like map and flip, makes it easy to stuff a function into a situation it wasn’t intended for. In PHP, you’d have to write a new function in the best case scenario, or more likely just repeat the same loop all over again.
Forth uses the simplifying concept of a stack as input and output. Does some word use a different API than is convenient for you? Just mangle the stack a little bit.
In a sense, object orientation also provides you with this power. You have an object which expects some API on some other object, but you have something that doesn’t quite fit? No problem, just inherit the right thing, fill in the methods you need and you’re set. Yet, looking at it now, from these other sides of the fence, I have to wonder if this is more powerful or more general or just wordier.
I see there being a lot of computation taking place simply to translate one thing into a different format. This has bothered me a lot for a long time. I’m no longer convinced that that step can be avoided—but if it cannot, is it at least possible to step out from between the two formats and let the computer perform the translation, without having to manually glue these systems together? It seems like many of the gains of functional programs are simply that they prevent you from being more involved in the process than you have to be. How far can we take this concept?
Tags languages, programming | no comments
Posted by Daniel Lyons
Thu, 02 Aug 2007 06:58:00 GMT
To relax after fixing the house I coded this quickie in Haskell:
atlanticCityMethod :: Float -> Float -> Float -> Float
atlanticCityMethod x m u = (u*m)/n
where
iterates = take (fromEnum m) $ iterate (\x -> (2 - x) / (3 - 4*x)) x
nearZero u x = (-u)/2 < x && x < u/2
n = fromIntegral $ length $ filter (nearZero u) iterates
I think this pretty concisely captures the specification:
Here’s the slowest, most inefficient method known for computing p: Choose an arbitrary initial value x (real) and iterate the mapping x → (2-x)/(3-4x) for a total of M times. Count the number of iterates that fall within a small interval around zero. For example, let N denote the number of iterates that fall between -u/2 and +u/2 for some small u. Then the limiting value of the ratio uM/N is p (for sufficiently large M as u goes to zero).
Observations:
- This algorithm is so shitty I can’t tell if it’s actually working with reasonable input (
atlanticCityMethod 1029 1000000 0.00005 produced 3.125 for me, but what do I know?)
- Don’t like that lambda? Do the Arrow twist:
((2-) &&& ((4*) >>> (3-))) >>> (uncurry (/))
This works just as well, but is twice as long and much harder to read. I guess points-free sometimes comes at a cost.
- The auto-derived type was much stranger than the ones I guessed it would want. Haskell inferred this type signature:
atlanticCityMethod :: (Ord b, Fractional b, Enum b) => b -> b -> b -> b
- Haskell mode’s indentation is really smart, but it still pisses me off by choosing the inner-most indentation by default. I think it would be better if it chose the previous level of indentation by default. Maybe there’s an easy way to do this, but I don’t know it.
- Want to see a screenshot of my Haskell with pretty lambdas?
- Incidentally, Justin Dressel pointed out that Haskell sometimes can work with Unicode input, at least according to the Haskell` page.
Tags emacs, haskell, pi | no comments
