3 ms·
Are they suggesting writing code that you can't later understand or debug? Does this actually work out for Haskellers? I mean, I guess I'll believe you if you
by jrochkind1 7y ago
Are they suggesting writing code that you can't later understand or debug?
Does this actually work out for Haskellers? I mean, I guess I'll believe you if you tell me it does, Haskell is different enough from the kind of programming I do that I don't think I know anything at all about it.
- jeremyjh 7y agoSome of the type-machinery code (hint, it has words like "hoist" or "lift" that describe type operations, not data operations) is like that, and its really not a problem because it does the only thing it can do given the types, and the things it does have nothing to do with your business domain or I/O so its never going to change unless a library you are using changes. When that happens its annoying but you just play type tetris again until the red squiggly lines go away and then you are fine for another few years. It isn't something I'd really brag about though as its really hard to explain the benefits of this stuff to non-Haskellers and you can end up wasting infinite amounts of time polishing these abstractions instead of getting work done.
- jrochkind1 7y ago> because it does the only thing it can do given the types Okay, this may be (probably is) a stupid question, because I know no Haskell whatsoever, but... if there's really only one thing it can do given the types, why does the code have to be there at all? Why can't you just write "Do the only thing you can do given these types"? If it's code humans aren't meant to read anyway, and it really is the only thing that could be done... why can't the compiler just do it without you having to put the non-human-intelligible code in your source files?
- syrak 7y agoThis is an interesting question. Technically there is more than one possible implementation, but you would also have to go out of your way to get it wrong. Automatically determining what constitutes "going out of your way" so that the code can be generated automatically is an active area of research (program synthesis), but as this post already shows, for "simple" cases, we're getting pretty close. As the post mentions, there are certain dead giveaways of an incorrect implementation, such as unused variables. Conversely one may still have some rough idea of the desired code to guide the implementation. The point is not about entirely removing one's mind from the process, but to allow oneself to only think about the choices that matter, which are few. Alternatively, another way to look at the problem is that these types, while already being quite precise, are still not as precise as they could be, because the type system is not sufficiently expressive. And even with the ability to describe the desired properties to uniquely determine the implementation: - it may not be obvious that the implementation is in fact uniquely determined; - a solution, unique or not, may not be easy to find automatically. Program synthesis is essentially the same problem as proof search (c.f. Curry-Howard correspondence); knowing that there is a proof of Fermat's last theorem is not sufficient to construct an actual proof of it from scratch. For these reasons, it may still be desirable to nail down the implementation explicitly even if it is hard to read. It's also worth considering the fact that polysemy (the package that the controversial snippet at the beginning of the post comes from) is very much an implementation of a state-of-the-art effect system using state-of-the-art features of Haskell's type system, so it can be expected that the abstractions to make this code more digestible (for the right audience) are still missing, because no one has ever thought of how to express them yet.
- pavas 7y agoThis comes down to the concept of 'proof'. How do you know that the code you wrote does what you think it does? You construct some sort of proof in your mind, but for any non-trivial code you have to follow certain operational rules[1] because you can't hold the whole code in your mind all at once. That is you work on smaller parts of it, proving to yourself that it works like you expect, and put those parts together using operational rules that you just have to assume are correct. Like if you have {f(a,b) => a+b}, you can conclude in your mind that {f(1,2) == 3} (but you're really doing a whole lot of rule-application under the covers). What if the code you wrote gave you guarantees about the things that it did, as long as you trust the compiler/proof-checker/other tools that used to verify the correctness of the code? This is basically what testing does-it gives you proof. As long as the things you test are "pure" or functional in the sense that they will do the same thing every time, given that they are given the same inputs, you have proof that the code is correct. The problem with testing is that you can't test everything because of combinatorial explosion. However, there's a trick to this where you can collapse states together and prove something using that collapsed state. For example, you collapse all 32-bit positive integers {1,2,3,...} into the state {N} and now as long as you prove something that holds for {N} you also proved something that holds for all 2^31-1 positive integers. You just have to be very careful and very precise about what you're doing, and that's where your compiler comes in to help. (So this next part is kinda butchering the math behind it and all sorts of programming language theory, apologies in advance.) You can kind of think of the state {N} as a type [2], and {1,2,3,...} as instantiations of that type. You can do something like "prove" that if you're given {f(a,b) => a+b} and {a=1, b=2} then you can conclude {f(1,2) == 3}, and throw that under some test. The test instantiation where you run 'assertEquals(f(1,2), 3)' is basically a concrete instance of your proof that 'f' does what it should. You just have to trust that your runtime environment is behaving correctly (no bugs). You can also consider functions that can be defined in your language as types (e.g. f: int -> int, a function that takes an int and gives you an int). That's the 'function signature' or 'function declaration'--it's type. And you can consider instantiations of this type to be the same thing as a function definition --where you define what the function does. As long as your function definition doesn't throw any compiler errors (that is, it passes your type-checker and there are no bugs in your toolchain), then you have provided an instance of a proof that the function definition is of the type of the function declaration. This might not sound like much ("great, the function definition has a certain type...didn't we already know that?"), but as long as your function definitions are pure functions (no external state change), you've just guaranteed type safety in your program [3]. Your program will never crash because you input a string when you should've input an int (hello JavaScript...). The type-checker won't allow you to write such a program. You can get a lot more guarantees than what I just mentioned, and there is a ton of active research in this area [4]. So to answer your first question, yes, they are suggesting writing code that you don't necessarily understand because you "offload" parts of your understanding to the compiler (type-checker). It's like when you do an automated refactor--if your code and the auto-refactoring tool are written correctly you can just trust that it did the right thing and doesn't cause any bugs. As for your second question, I can't answer it because I haven't used Haskell. [1] https://en.wikipedia.org/wiki/Operational_semantics https://en.wikipedia.org/wiki/Operational_semantics [2] https://en.wikipedia.org/wiki/Type_theory#Basic_concepts https://en.wikipedia.org/wiki/Type_theory#Basic_concepts [3] https://en.wikipedia.org/wiki/Type_safety https://en.wikipedia.org/wiki/Type_safety [4] https://en.wikipedia.org/wiki/Static_program_analysis https://en.wikipedia.org/wiki/Static_program_analysis