This example does not fit my experience of "exploratory" programming. Here the author implements DPLL from a textbook, and while there is a gap to fill between pseudo-code and Haskell, the problem is already well-defined. Think-upfront-then-code works quite well in those cases. Having compiler feedbacks surely helps to get it right.
But exploratory to me means that the problem is not really well defined or understood in the first place. Just as you draft things on paper to get a clear idea of what you want to do, you can use your programming language to express parts of the problem more or less clearly. That also means not being afraid of getting things wrong in the process and being able to code generically. Now, with some languages, you can't explore. I tried in Ada, which I actually happen to like, but every choice was a commitment that would take much time to adapt later, so I actually sticked to pen and paper. I think it can be easier with ML type systems, where it might be easier to have loosely coupled definitions, but I am not sure.
Yeah, I agree this is a poor example of exploratory programming.
I actually do think Haskell does a good job for exploratory programming, though. Whether I'm writing Haskell or C or Python, as I code I'm making decisions about how to represent and organize things. When some of those decisions inevitably turn out to be the wrong ones, I have to figure out what code needs to change in tandem. Tests can help reveal incorrect behavior, but far better to have a tool that can point at the specific inconsistent expressions and tell something about what's wrong with them.
This is interesting, and I'm curious and respectful of Haskell, but when I read a post like this, while I appreciate many of the strengths of static type checking, it just makes my head hurt to see what this guy goes through to please the compiler, and I'm left thinking that I'd just rather stick to a dynamic functional language like Clojure or Erlang and sketch ideas out more quickly. Maybe I'm just not patient enough for Haskell.
I think the approach taken by the author is simply the wrong one. Writing a huge amount of code without any clue what the types are going to be is just silly.
Haskell makes it very easy for you if you work with it in a more interactive fashion, asking it to infer types for you as you go along. One of the best features for doing this is Typed Holes [0].
I think in this case it's a reasonable approach to writing the `dpll` function because that function doesn't actually care about the specifics of the types. This is a nice example of encapsulation and implementation hiding, a concept familiar to object-oriented and functional programmers alike. He could have easily gotten it to compile by stubbing things out as follows:
data Clauses = Clauses
data Symbols = Symbols
data Model = Model
isTrueIn = undefined
isFalseIn = undefined
findPureSymbol = undefined
minus = undefined
including = undefined
findUnitClause = undefined
I think it's more a question of personal preference than right or wrong.
The trick is to realize that the incremental incorrect output you get from the compiler is roughly equivalent to the incorrect output you'd get from the failed runtime.
Personally I'd start from smaller functions up but it's not like there's no feedback.
Or rather, you're going to need to fix that code anyways, so might as well use the thing that tells you what to do.
I personally find fixing type errors far more enjoyable than debugging, and even if I didn't, I think one can argue that fixing type errors is a more predictable workflow and therefore contributes less uncertainty for time budgeting.
If you're prototyping and exploring, most likely you're not going to need to fix that code anyways, so it would be a waste of time (unless you're already efficient with Haskell dev).
I'm a big believer in exploring problem spaces with loose, flexible tools that let you get to the point ASAP and ignore unrelated stuff. If you're then going to build a long-lived, high-availability production system, then take what you learned and harden your design using tools built for long-lived, high-availability production systems (e.g. static typing, formal methods, etc.).
GHC is there to please you, not the other way around. It enables you to practically turn any runtime error into a compile time error, if you choose your types carefully.
I write a lot of Haskell these days, and whenever I'm faced with a compiler error I don't understand, it always ends with finding out that my data model was inaccurate. Two ends weren't fitting together, because I hadn't fully understood what those two ends actually were.
You're setting up a false dichotomy. You can find statically typed languages in-between Haskell and dynamic languages that are less demanding from the developer than Haskell is (my language of choice these days is Kotlin, which offers the best of both worlds in my opinion).
That's pretty much how Haskell development works. It doesn't compile until it's what you want. TDD in Haskell and Ruby are similar, but in Haskell the T is types.
This doesn't match my Haskell workflow at all. Usually, it compiles every small change, with much stubbed out with `undefined` until I get to it. When it doesn't compile, it's surprising and I learn something about the assumptions I've made.
To be clear, I am certainly not saying that my approach is the only (or best) one. Just that when it builds (relative to completeness) is very much at the discretion of the programmer, and despite jokes about "if it builds, it works" not everyone has that dial set all the way to one extreme.
I write Haskell for a living and that's never been the approach I've taken. For me writing Haskell is like a conversation with the compiler, you write a bit, you listen a bit - back and forth - unless you're refactoring you don't go too long without compiling.
Yes, I understand the expression. What I'm asking is precisely what things he did that example that he would not have had to do if he were using a dynamic language like Ruby or Python. In other words, I'd like to understand specifically what you think are the extra costs he paid for using a static language.
I love the concept and idea behind Haskell, and even reading this piece was very cool. But as much as I can sort of guess at what's happening, the steps being taken to simplify the original pseudocode still seem like some kind of space magic.
I see stuff like "Learn you a Haskell" and whatnot, but it all seems so theoretical compared to, say, writing a web server or parsing CSV or building a programming language with Haskell. I get monads. But I don't get how to bridge the gap between my knowledge and what I see here.
Writing code. Failing. Trying again and again. Slowly, at some point, it starts clicking, and before you know it, you're much more productive than you used to be in Ruby or whatever else, and then you're cursed by lambda.
It may be easy to use but hard to install if you don't want to depend on binary downloads. Since I always prefer source compilation for reproducible installations on new platforms I tried to install an up-to-date Haskell platform on Debian 7 to use stack. After being stuck in the cabal hell again I tried several upgrades and downgrads of ghc just to make a cabal upgrade. Nothing worked. I couldn't even compile the built-in cabal-install of ghc. At least this should work.
Haskell is a really nice language, and I admire the work of the developers who provide GHC for free, but installation from source is really immature and painful, at least on Linux. If the Haskell platform were just self-hosting ...
That's an interesting point. I've never tried to build it directly from source. I'm not sure if this actually addresses what you want to do, but maybe you could start with the prebuilt binaries and then do `stack upgrade`, which will fetch and build the latest release from source?
I will say that I won't touch the Haskell platform with a 10 foot pole. I had nothing but issues with it in the past and it drove me away from using Haskell for years prior to finding stack.
> start with the prebuilt binaries and then do `stack upgrade`
Thanks but in this case I could also download the newest binaries instantly. The point is that I don't want to be dependent on any binaries. Compilation from scratch doesn't work.
Btw Rust has the same problem - it also depends on binary upgrades. Nim (nim-lang.org) proves how easy self-hosting can be - which also means how easy porting to other platforms can be.
There's not a huge gap between understanding types and monads and stuff like that and being able to write useful code. You just have to try things so you can learn the ecosystem and the idioms people use. I found multiple times learning Haskell that I'd re-invented a concept someone else had already turned into a popular library.
Building a website is a good place to start. Haskell has several very good web frameworks. "Very good" means fast, correct, and well-designed. I don't recommend Snap for beginners; it uses too many strange idioms that aren't used elsewhere in Haskell.
I personally use Happstack because it's very straightforward; it just gives you a monad in which you can do "web stuff" like inspect the URL, read cookies, send back HTTP responses, etc. You can start doing everything the "manual" way, like passing around state in arguments or doing janky text formatting yourself. As you get fed up with that, you can gradually integrate things like monad transformers, custom monads with typeclass derivation, various high-performance formatting libs like blaze, aeson, heist, etc. If you do database stuff you can learn about weird template Haskell and typeclass stuff with Persistent and Esqueleto.
Refactoring haskell like that would be a lot easier when you implement a function you're familiar with. Take for example parsing CSV. What i noticed, what haskell feels to me, is that for a different kind of problem you seem to be using a different part of the language. In a simple OO-kind of language you just have classes, objects, methods, and so on. And you build patterns on top of that to express certain idioms (see GoF and what not). In haskell you have to enable a language extension or use a slight variation of a language construct (like "data .. where" could be such a variation to just "data") [1]. Do you really need all those design patterns? For good software practises .. likely. But just to get it to work you can do without a lot of "features", at the cost of boilerplate, maintainability, performance and so on.
I found it easier to just start using certain language constructs and libraries, even though i didn't really have the feeling that i understood them. When you know what to use for your problem, open the documentation on it and look at the types. Then play a bit of "fit the type"-game with the compiler. You can already get a long way with that. To figure out which language features or library to use for your particular problem take a look at a book like real world haskell. After reading through a bunch of stuff and asking around a bit you will have a clue whether to use monad X, Y or Z for what you are trying to solve. The knowledge of how to do nice refactering will come over time. This is muscle memory you will train automatically. So maybe you will ask the wrong question when you are focused on refactering code rather than solving your problem. The way the author refactors his own code seems to be new to him also. A lot of people prefer to start out with expressing their problem in the types first, before writing functions.
You might consider Rust instead. It has a nontrivial type system, but the benefits are a lot more clear.
I hypothesize that if you're still interested in Haskell after that that you may find it easier to learn. Don't know if many people have walked that path, though.
It's the purity that's the challenge; you can basically construct your types just as accurate or inaccurate as you want. But purity forces you to understand a couple of things first, in order to be productive (eg. monads, monad transformers, type classes).
In my view, Haskell is in the opposite spectrum of Rust when it comes to performance over abstraction. Haskell abstracts everything away, and only manages to get good performance because of purity (I would argue), while Rust wants to be close to the metal, preferring performance over abstraction (e.g. with zero cost abstractions).
I've realized that all my programming is exploratory. Every time I implement something, I end up knowing more about what I've implemented, enabling me to create an even better implementation the second time. This cycle repeats until I'm satisfied with the result, or I need to go to the bathroom.
The real challenge to writing code is understanding the nature of what you're trying to express, down to its smallest, intuitively correct constituents. While you are in this state of understanding, the code writes itself.
I don't use haskell very much, but I'm curious what the use is of defining
type Symbol = String
Why not just have -> String -> in the function's type? The only thing I see this gains is forcing you to add extra boilerplate everywhere converting strings to "Symbol"s
It is just a type alias as far as I know. I suppose it adds more 'annotation' to your program, in addition if you decide to change the type of Symbol to be an Int or String String then you have a single reference to change initially.
"type" simply defines a synonym. You use it similarly to how you'd use a typedef in C. You don't need to convert anything, it just gives a more meaningful name to an existing type.
While this is indeed interesting, I feel I should point out Haskell is one of the worst languages out there for writing a SAT silver which performs remotely well, as all modern algorithms work fundamentally on in-place modification of data structures, so you just have to put your whole program in the IO monad.
> so you just have to put your whole program in the IO monad
You have to put the bits that actually modify things in IO or ST. While it's better Haskell style to keep as much as pure as you can, when you do need to modify things Haskell still works just fine.
I'm not a Haskell expert, but I am a sat expert, and worked with good Haskell programmers. We managed to get decent performance, but what we ended up with looked a lot like a C program translated into Haskell, so it wasn't clear we had really gained anything. Memory safety I suppose.
"Like C, but with memory safety and QuickCheck" sounds like a pretty good language for a SAT solver... "Idiomatic Haskell won't produce a very fast SAT solver" is something that doesn't surprise me.
Why would that make it the worst? The IO monad isn't some dirty thing. Imperative programming in Haskell can be a wonderful experience even compared to traditional imperative languages. I use the "imperative" term lightly here.
sometimes when I get stuck on a small part I let the compiler suggest types. this is different workflow than sitting back and trying to figure it all out yourself.
I also have never understood the argument “In dynamic typed language X you can just start prototyping, but in static typed language Y you have to fight the type system just to get it to compile”
If your types aren’t lined up but it compiles, even in a dynamic typed language, you’re program won’t behave as expected, i.e. you are likely to have a bug.
e.g. object + int, and it compiles.
How does one really save time by not worrying about these things? I almost always start coding from the core data structures up, even when prototyping. A seemingly opposite approach as OPs post, not saying my method is THE correct method :)
Yeah, that's kind of misguided. The biggest advantages of dynamic languages when doing "exploratory" programming are late binding, built-in syntax for commonly used data structures and duck typing. Those allow you to scaffold a lot of stuff pretty quickly, try the bit of code that you care actually care about, and then decide from there whether you want to do a full implementation or just use the snippet you wrote.
Compare that to a language like older Java, where you need to build a class no matter what, most likely you need to implement a few interfaces and add a lot of exception handling just to get the scaffolding in place, and if you want to initialize something as simple as a hash map you have to do it the painstakingly, line by line way. Sure, your prototype may (or may not, depending on how serious you were about handling those exceptions) be more solid, but it took you double the time to get there, which is basically the opposite of what prototyping should be.
With all that said, and being a huge Python fan, I still feel like strongly typed languages should be a requirement for bigger projects that you plan to maintain for years. Python, as great as it is, starts hurting a lot at a larger scale. I'm really looking forward to using something like MyPy once my projects start being Python 3+ by default.
I have had to run vardumps on some large Python/JS code bases trying to figure out what the behavior was because it was unclear what the variables being passed in was. Definitely a pain as the project grows larger. I used to not understand why people who use Ruby/JS/Python were not fans of massive refactoring, until I owned a large PHP code base and saw first hand how hard it was to refactor. Search/Replace only gets you so far. Compared to of course, the powerful refactoring tools you get in a Java language via IDE.
I a big fan of strong type systems; but can see where the concept of fighting the type system comes up with people who are used to dynamically typed languages.
For example, consider the Haskell Maybe datatype. If you are used to a dynamically typed language, then it may feel like you are fighting the type system to cast between `Maybe x` and `x`. Indeed, in some cases these casts serve no purpose other than satisfying the type system because you, as the programmer, knows that the value cannot be nothing; so not having a cast "ought" to be the same as omitting a null pointer check.
However, once you get used to strong typing, you realize that the only way you would get a Maybe type is if (to a first approximation) some programmer thought that there was a chance that the value would be nothing. In this case, it is probably a bug to not deal with the possibility anywhere, and the type system is warning you of this. If you happen to be sure that the value can never be Nothing, then you can use an unsafe cast and make it clear to future developers that you did not forget about the case, but rather were confident that it could never happen.
Also, when you are prototyping, you might want to run code even if it has some bugs.
I definitely see your point about "too much" enforcement, specifically with the case of error handling. In Java, I could just bubble everything up, default exit-early, and worry about proper handling later. I'm sure a similar argument could be stated for having to create simple data classes vs tuples or dynamic objects, or even number types. So I do agree there is a middle ground here. For example, Java will be friendly towards number casting whereas Haskell is very exacting.
I am someone who mostly works with dynamic languages. When I find myself "fighting the type system" and having a hard time prototyping, I am specifically trying to figure out what my data types need to be. In some situations I find myself in a situation where in order to define my data type I need to know what the data is, but to know what the data is I need to define it's type. With a dynamic language you generally have an ability to get the data, pretty print it, then crash. Then you can go and define proper data types for the data you're working with.
While this is a true 80th level hipsterism and snowflackery, it is also a beautiful case to realize that there was reasons behind choosing Common Lisp as the primary language for AI.
The Common Lisp code is almost as easy to read as the pseudocode of the book and it is absolutely unnecessary to go through all that type clutter and fancy compositions to satisfy the type-checker. There is zero advantage in doing all this static typing acrobatics.
The AIMA supplementary Common Lisp code is definitely worth looking and it is the case study for demonstrating the advantages of dynamic typing.
BTW, AIMA python code is also very nice, short and clear but order of magnitude slower compared to the compiled native code state-of-the-art implementations of Common Lisp produce.
But exploratory to me means that the problem is not really well defined or understood in the first place. Just as you draft things on paper to get a clear idea of what you want to do, you can use your programming language to express parts of the problem more or less clearly. That also means not being afraid of getting things wrong in the process and being able to code generically. Now, with some languages, you can't explore. I tried in Ada, which I actually happen to like, but every choice was a commitment that would take much time to adapt later, so I actually sticked to pen and paper. I think it can be easier with ML type systems, where it might be easier to have loosely coupled definitions, but I am not sure.