In case the community decides to build a Haskell editor/IDE from scratch, how do you imagine its layout design? What particular features you want to find in it? How do you imagining the debugging procedure being handled with the tool? ...
In case you are comfortable with an existing tool, would you share your configurations so others can benefit from it.submitted by BanX
[link] [88 comments]
SubproblemsConsider sorting algorithms. A large class of sorting algorithms, including quicksort, break a sequence of values into two pieces. The two pieces are smaller so they are easier to sort. We sort those pieces and then combine them, using some kind of merge operation, to give an ordered version of the original sequence. Breaking things down into subproblems is ubiquitous and is useful far outside of mathematics and computing: in cooking, in finding our path from A to B, in learning the contents of a book. So I don’t need to say much more here.
Quotient problemsThe term quotient is a technical term from mathematics. But I want to use the term loosely to mean something like this: a quotient problem is what a problem looks like if you wear a certain kind of filter over your eyes. The filter hides some aspect of the problem that simplifies it. You solve the simplified problem and then take off the filter. You now ‘lift’ the solution of the simplified problem to a solution to the full problem. The catch is that your filter needs to match your problem so I’ll start by giving an example where the filter doesn’t work.
Suppose we want to add a list of integers, say: 123, 423, 934, 114. We can try simplifying this problem by wearing a filter that makes numbers fuzzy so we can’t distinguish numbers that differ by less than 10. When we wear this filter 123 looks like 120, 423 looks like 420, 934 looks like 930 and 114 looks like 110. So we can try adding 120+420+930+110. This is a simplified problem and in fact this is a common technique to get approximate answers via mental arithmetic. We get 1580. We might hope that when wearing our filters, 1580 looks like the correct answer. But it doesn’t. The correct answer is 1594. This filter doesn’t respect addition in the sense that if a looks like a’ and b looks like b’ it doesn’t follow that a+b looks like a’+b’.
To solve a problem via quotient problems we usually need to find a filter that does respect the original problem. So let’s wear a different filter that allows us just to see the last digit of a number. Our original problem now looks like summing the list 3, 3, 4, 4. We get 4. This is the correct last digit. If we now try a filter that allows us to see just the last two digits we see that summing 23, 23, 34, 14 does in fact give the correct last two digits. This is why the standard elementary school algorithms for addition and multiplication work through the digits from right to left: at each stage we’re solving a quotient problem but the filter only respects the original problem if it allows us to see the digits to the right of some point, not digits to the left. This filter does respect addition in the sense that if a looks like a’ and b looks like b’ then a+b looks like a’+b’.
Another example of the quotient approach is to look at the knight’s tour problem in the case where two opposite corners have been removed from the chessboard. A knight’s tour is a sequence of knight’s moves that visit each square on a board exactly once. If we remove opposite corners of the chessboard, there is no knight’s tour of the remaining 62 squares. How can we prove this? If you don’t see the trick you can get get caught up in all kinds of complicated reasoning. So now put on a filter that removes your ability to see the spatial relationships between the squares so you can only see the colours of the squares. This respects the original problem in the sense that a knight’s move goes from a black square to a white square, or from a white square to a black square. The filter doesn’t stop us seeing this. But now it’s easier to see that there are two more squares of one colour than the other and so no knight’s tour is possible. We didn’t need to be able to see the spatial relationships at all.
(Note that this is the same trick as we use for arithmetic, though it’s not immediately obvious. If we think of the spatial position of a square as being given by a pair of integers (x, y), then the colour is given by x+y modulo 2. In other words, by the last digit of x+y written in binary. So it’s just the see-only-digits-on-the-right filter at work again.)
Wearing filters while programmingSo now think about developing some code in a dynamic language like Python. Suppose we execute the line:
a = 1
The Python interpreter doesn’t just store the integer 1 somewhere in memory. It also stores a tag indicating that the data is to be interpreted as an integer. When you come to execute the line:
b = a+1
it will first examine the tag in a indicating its type, in this case int, and use that to determine what the type for b should be.
Now suppose we wear a filter that allows us to see the tag indicating the type of some data, but not the data itself. Can we still reason about what our program does?
In many cases we can. For example we can, in principle, deduce the type of
if we know the types of a, b, c, d. (As I’ve said once before, it’s hard to make any reliable statement about a bit of Python code so let's suppose that a, b, c and d are all either of type int or type float.) We can read and understand quite a bit of Python code wearing this filter. But it’s easy to go wrong. For example consider
if a>1 then: return 1.0else: return 1
The type of the result depends on the value of the variable a. So if we’re wearing the filter that hides the data, then we can’t predict what this snippet of code does. When we run it, it might return an int sometimes and a float other times, and we won’t be able to see what made the difference.
In a statically typed language you can predict the type of an expression knowing the type of its parts. This means you can reason reliably about code while wearing the hide-the-value filter. This means that almost any programming problem can be split into two parts: a quotient problem where you forget about the values, and then problem of lifting a solution to the quotient problem to a solution to the full problem. Or to put that in more conventional language: designing your data and function types, and then implementing the code that fits those types.
I chose to make the contrast between dynamic and static languages just to make the ideas clear but actually you can happily use similar reasoning for both types of language. Compilers for statically typed languages, give you a lot of assistance if you choose to solve your programming problems this way.
A good example of this at work is given in Haskell. If you're writing a compiler, say, you might want to represent a piece of code as an abstract syntax tree, and implement algorithms that recurse through the tree. In Haskell the type system is strong enough that once you’ve defined the tree type the form of the recursion algorithms is often more or less given. In fact, it can be tricky to implement tree recursion incorrectly and have the code compile without errors. Solving the quotient problem of getting the types right gets you much of the way towards solving the full problem.
And that’s my main point: types aren’t simply a restriction mechanism to help you avoid making mistakes. Instead they are a way to reduce some complex programming problems to simpler ones. But the simpler problem isn’t a subproblem, it’s a quotient problem.Dependent typesDependently typed languages give you even more flexibility with what filters you wear. They allow you to mix up values and types. For example both C++ and Agda (to pick an unlikely pair) allow you to wear filters that hide the values of elements in your arrays while allowing you to see the length of your arrays. This makes it easier to concentrate on some aspects of your problem while completely ignoring others.
NotesI wrote the first draft of this a couple of years ago but never published it. I was motivated to post by a discussion kicked off by Voevodsky on the TYPES mailing list http://lists.seas.upenn.edu/pipermail/types-list/2014/001745.html
This article isn’t a piece of rigorous mathematics and I’m using mathematical terms as analogies.
The notion of a subproblem isn’t completely distinct from a quotient problem. Some problems are both, and in fact some problems can be solved by transforming them so they become both.
More generally, looking at computer programs through different filters is one approach to abstract interpretation http://en.wikipedia.org/wiki/Abstract_interpretation. The intuition section there (http://en.wikipedia.org/wiki/Abstract_interpretation#Intuition) has much in common with what I’m saying.
(Full error text available upon request. Error text trimmed due to max character limit.)
What I was doing (following the instructions in "Beginning Haskell"):
1. Installed XCode
2. Installed XCode command line tools
3. Installed Eclipse
4. Installed EclipseFP
5. Restarted Eclipse
6. Checked the boxes for "Install optional helper executables (...)" and "Install for current user only"
7. Voila, errors!
While I am a Haskell beginner, I do know my way around a few other programming languages. From this small body of knowledge I make the following observations:
* If you want your language to be taken as more than an academic language, don't have errors in commonly used code (the exceptions package has had this exact same error for at least two months now).
* There is a distinct lack of resources targeted at any level of expertise other than Haskell guru for working through problems such as the one above (a.k.a., I know this is the wrong place to post this but I am doing so anyhow out of desperation).
[link] [37 comments]
is it books you read, courses, meetings, projects you worked on...etcsubmitted by pyThat
[link] [28 comments]
The problem is that I haven't found any good tutorials or explanations of Fay. Does anyone know any good resources for Fay, or should I just study the examples that are provided in the package?submitted by Judde10
[link] [4 comments]
I've been thinking about all the Haskell PVP discussion that's been going on lately. It should be no secret by now that I am a PVP proponent. I'm not here to debate the PVP in this post, so for this discussion let's assume that the PVP is a good thing and should be adopted by all packages published on Hackage. More specifically, let's assume this to mean that every package should specify upper bounds on all dependencies, and that most of the time these bounds will be of the form "< a.b".
Recently there has been discussion about problems encountered when packages that have not been using upper bounds change and start using them. The recent issue with the HTTP package is a good example of this. Roughly speaking the problem is that if foo-1.2 does not provide upper bounds on it's dependency bar, the constraint solver is perpetually "poisoned" because foo-1.2 will always be a candidate even long after bar has become incompatible with foo-1.2. If later foo-3.9 specifies a bound of bar < 0.5, then when bar-0.5 comes out the solver will try to build with foo-1.2 even though it is hopelessly old. This will result in build errors since bar has long since changed its API.
This is a difficult problem. There are several immediately obvious approaches to solving the problem.
- Remove the offending old versions (the ones missing upper bounds) from Hackage.
- Leave them on Hackage, but mark them as deprecated/blacklisted so they will not be chosen by the solver.
- Go back and retroactively add upper bounds to the offending versions.
- Start a new empty Hackage server that requires packages to specify upper bounds on all dependencies.
- Start a new Hackage mirror that infers upper bounds based on package upload dates.
All of these approaches have problems. The first three are problematic because they mess with build reproducibility. The fourth approach fragments the community and in the very best case would take a lot of time and effort before gaining adoption. The fifth approach has problems because correct upper bounds cannot always be inferred by upload dates.
I would like to propose a solution I call implicit blacklisting. The basic idea is that for each set of versions with the prefix a.b.c Cabal will only consider a single one: the last one. This effectively means that all the lower versions with the prefix a.b.c will be implicitly blacklisted. This approach should also allow maintainers to modify this behavior by specifying more granular version bounds.
In our previous example, suppose there were a number of 0.4 versions of the bar package, with 0.4.3.3 being the last one. In this case, if foo specified a bound of bar < 0.5, the solver would only consider 0.4.3.3. 0.4.3.2 and 0.4.3.1 would not be considered. This would allow us to completely hide a lack of version bounds by making a new patch release that only bumps the d number. If that release had problems, we could address them with more patch releases.
Now imagine that for some crazy reason foo worked with 0.4.3.2, but 0.4.3.3 broke it somehow. Note that if bar is following the PVP, that should not be the case. But there are some well-known cases where the PVP can miss things and there is always the possibility of human error. In this case, foo should specify a bound of bar < 0.4.3.3. In this case, the solver should respect that bound and only consider 0.4.3.2. But 0.4.3.1 would still be ignored as before.
Implicit blacklisting has the advantage that we don't need any special support for explicitly marking versions as deprecated/blacklisted. Another advantage is that it does not cause any problems for people who had locked their code down to using specific versions. If foo specified an exact version of bar == 0.4.3.0, then that will continue to be chosen. Implicit blacklisting also allows us to leave everything in hackage untouched and fix issues incrementally as they arise with the minimum amount of work. In the above issue with HTTP-4000.0.7, we could trivially address it by downloading that version, adding version bounds, and uploading it as HTTP-4000.0.7.1.
All in all, I think this implicit blacklisting idea has a number of desirable properties and very few downsides. It fixes the problem using nothing but our existing infrastructure: version numbers. It doesn’t require us to add new concepts like blacklisted/deprecated flags, out-of-band “revision” markers to denote packages modified after the fact, etc. But since this is a complicated problem I may very well have missed something, so I'd like to hear what the community thinks about this idea.