News for hackers. Stuff that matters.
Re:Idris 2: Quantitative Type Theory in Practice by dwohnitmok on Monday January 24, 2022 @02:08AM (#30054454)
A sibling comment correctly lays out what the type means, and I'll elaborate a little more here.

> how the data is stored

Thinking of how concretely the data is stored is a little bit tricky. I find it easier to build an intuition by looking at what kind of values the type signature lets us build, and which values are disallowed.

  runLengthOfAnEmptyList : RunLength []
  runLengthOfAnEmptyList = Empty

  -- Note that 1 is shorthand for (S Z)
  runLengthOfAListWithOneElement : RunLength [ 1 ]
  runLengthOfAListWithOneElement = Run 0 1 Empty

  -- The definition of RunLength places restrictions on how to
  -- construct it.
  -- For example, this will not compile.
  runLengthOfAListWithOneElementBrokenVersion : RunLength [ 1 ]
  runLengthOfAListWithOneElementBrokenVersion = Run 1 1 Empty
  --
  -- This violates the type signature of RunLength
  -- Notice Run 1 1 Empty which has changed the 0 to a 1
  --
  -- As a reminder this is the definition of Run
  -- Run : ( n : Nat ) -> ( x : ty ) -> ( rle : RunLength more ) ->
  --    RunLength ( rep ( S n ) x ++ more )
  --
  -- n is set to 1, x is set to 1, and Empty means that more is set to []
  -- Making the necessary substitutions results in:
  -- RunLength ( rep ( S n ) x ++ more ) -- No substitutions yet
  -- RunLength ( rep ( S 1 ) 1 ++ [] )   -- S 1 is the same thing as S (S Z)
  -- RunLength ( 1 :: 1 :: [] ++ [] )    -- Substituting rep ( S 1 ) 1
  -- RunLength ( 1 :: 1 :: [] )          -- ++ [] doesn't change our list at all
  -- RunLength [ 1, 1 ]                  -- Syntax sugar for 1 :: 1 :: []
  --
  -- But this is a contradiction! Since we said in our type annotation that we
  -- should have RunLength [ 1 ], not RunLength [ 1, 1 ]!

However I agree with you that this style of dependently typed programming is confusing and ultimately in my view, a bad representation of how dependent types should be used in production code (if any full-spectrum dependently typed language gains enough adoption to be used in large production projects).

Here's the same idea in an alternative, but (roughly) equivalent, encoding, which hopefully lays it out more clearly.

  RuntimeEncodedList : Type -> Type
  RuntimeEncodedList t = List (Nat, t)

  uncompress : RuntimeEncodedList t -> List t
  uncompress runtimeEncodedList = case runtimeEncodedList of
    [] => []
    (n, elem) :: restOfList => rep (n + 1) elem ++ uncompress restOfList

  compress : List t -> RuntimeEncodedList t
  compress = ...

  uncompressIsTheInverseOfCompress :
    uncompress (compress xs) = xs
  uncompressCorrectlyUncompressesEmptyLists = ...
I hope this is a much plainer and easier to understand representation, with a similarly strong invariant. The `...` are of course eliding a lot, but my point is that they can be elided, without really affecting comprehension of the overall code (which is not the case with the other representation).

This also nicely avoids a problem I see in a lot of dependently code where the structural representation of data structures are intertwined with the invariants they are supposed to uphold. Not only does this result in increasingly confusing code as the invariants get more sophisticated and also awkwardly privileges certain invariants over others, it makes modifying the representation in even the smallest ways a nightmarish test of resolve. This is because everywhere you want to create the data structure, you must also prove that the invariants hold. Sometimes this proof is trivial, sometimes this proof is difficult. But you must always do this, you cannot bail out with some sort of "believe me" escape hatch where you maybe use some sort of external solver to prove it instead, because you can now potentially crash or even segfault your program, even if your code would otherwise fulfill the invariant through some other reasoning the compiler cannot see, since the proof is an integral part of the runtime representation of the data structure.

This sort of proof burden means that it can be a Herculean task to swap out the underlying representation of the data structure for a more efficient one (e.g. you're going to be in for a hard time if you've written code with the `RunLength` type and all of a sudden, for speed reasons, you'd prefer an underlying representation of run length encoded types that groups all the run lengths in one array and stores all the actual values in another array). At least having zero multiplicity annotations on parts of the dependently typed data structure makes things a bit easier.

I instead advocate for a clean separation where the overwhelming majority of data types in a dependently-typed program should be non-dependently-typed and dependent types used instead merely to state properties about those data types independently.

Re:Idris 2: Quantitative Type Theory in Practice by throwaway17_17 on Monday January 24, 2022 @02:58AM (#30054684)
The line of thought you are expressing here really reminds me of the work on Zombie, a research language that Stephanie Weirich, among many others, worked on. In particular was the dissertation research by Chris Casinghino. He gave a talk at Boston Haskell [1] that has some really well argued points that argue for your perspective in many respects.

1 — https://m.youtube.com/watch?v=_2jrmgO_Gq0

Re:Idris 2: Quantitative Type Theory in Practice by dwohnitmok on Monday January 24, 2022 @03:12AM (#30054773)
Ooooo... even on a brief skim through this looks like a great talk (although I guess that's an easier thing to say when the speaker mainly agrees with your own viewpoint). Will watch in more detail. Thanks!
Re:Idris 2: Quantitative Type Theory in Practice by skybrian on Monday January 24, 2022 @05:02PM (#30064677)
Isn't it a bit odd that the type signature "contains" the uncompressed data? There would seem to be no point in compressing data this way.

I suppose laziness makes it somewhat more practical. The concrete type may only exist conceptually.

It's also unclear what constraint is being enforced. Proving that all run-length encodings decompress to some list doesn't seem interesting? This is just as true of your encoding. I suppose it would be more interesting if not every possible value of the compressed data structure were valid, such as if it contained a cached checksum that needed to match the data. We could show that all compress functions compute the checksum correctly.

But couldn't do that by having a single compress function and proving that it works? Why have more than one?

Also, it seems like verifying such a checksum would be weird. In the presence of data corruption, you would have a proof that that checksum matches the data, but by computing the checksum you could show that it doesn't match the data.

Apparently type-checking proofs aren't really about concretely showing that data is consistent? If you rely on the proof, you assume correct data rather than verifying it. A sufficiently smart compiler might optimize away your attempted verification?

Re:Idris 2: Quantitative Type Theory in Practice by dwohnitmok on Tuesday January 25, 2022 @02:30AM (#30069176)
> Isn't it a bit odd that the type signature "contains" the uncompressed data? There would seem to be no point in compressing data this way.

I agree it's a bit tricky to understand (which is why I don't like that representation), but this has nothing to do with laziness (Idris is a strict language). It's a more general phenomenon that values in a type signature do not actually have to exist at runtime. It's purely a notational thing that lives in the type-checkers "brain" and has no runtime representation. At runtime, `compress` really does compress the list without keeping a copy of it anywhere. For any type `MyType someValue`, there's no a priori reason `someValue` should actually have any runtime representation. See e.g.

  data MyType : Int -> Type
    TheOnlyThingOfMyType : MyType 5

  -- There's no way to actually access the 5 at runtime
  -- It only lives in type signatures
  someValue : MyType 5
  someValue = TheOnlyThingOfMyType

  -- This addition takes place at compile time, not runtime
  someOtherValue : MyType (4 + 1)
  someOtherValue = TheOnlyThingOfMyType

  thisFailsToCompile : MyType (4 + 2)
  thisFailsToCompile = TheOnlyThingOfMyType
There is likewise no reason to believe something like `SomeOtherType String` actually has a string in it anywhere (this pattern is known as a phantom type) without knowing more about `SomeOtherType`. All the type parameter does is constrain how functions can be called that involve the overall type. In this sense `List String` having an actual `String` you can pull out of it at runtime can be thought of as the exception rather than the norm (and indeed isn't always the case, e.g. if you have an empty list).

In this case, you can use `RunLength`'s list parameter to state more invariants, even if the list doesn't exist at runtime.

  -- If two lists compress to the same thing, then they must've been the same to begin with
  compressionIsLossless : RunLength xs = RunLength ys -> xs = ys
  -- Here follows the proof of that statement
  -- If the proof looks confusing, https://shuangrimu.com/posts/language-agnostic-intro-to-dependent-types.html might help
  compressionIsLossless runLengthsAreEqual = case runLengthsAreEqual of
    Refl => Refl
Switching back to my representation...

> But couldn't do that by having a single compress function and proving that it works? Why have more than one?

I only have one compress function (I was just too lazy to write it out and used ellipses instead).

> Proving that all run-length encodings decompress to some list doesn't seem interesting? This is just as true of your encoding.

The constraint is fairly simple, but very strong (although I made a typo where the name associated with the type signature and the actual implementation's name are different, d'oh):

  uncompressIsTheInverseOfCompress : uncompress(compress xs) = xs
  uncompressIsTheInverseOfCompress = ... -- Too lazy to write out the actual proof at the moment
This is the fundamental property all lossless compression schemes must satisfy.

You could also of course add all sorts of other properties.

  -- Even though it won't inflate list length, it can result in more memory usage due to the tuples
  compressWontInflateSize : (length (compress xs) <= length xs) = True
  compressWontInflateSize = ... -- Again too lazy to write out the proof

  -- Idris doesn't have a general exists statement so we need to provide a
  -- concrete example
  compressMakesAtLeastOneListSmaller : (length (compress [1, 1, 1]) <= length [1, 1, 1])) = True
  compressMakesAtLeastOneListSmaller = Refl
  -- This proof is easy, just tell Idris to actually do the calculation (at compile-time, not run-time!)
> Apparently type-checking proofs aren't really about concretely showing that data is consistent? If you rely on the proof, you assume correct data rather than verifying it. A sufficiently smart compiler might optimize away your attempted verification?

I'm not sure what you mean here. In order to show that your data is consistent you need to describe what you mean by consistency somehow. You can do that either within the definition of a type itself (which I do not like) or you can do that by explaining how different functions are supposed to relate to each other (e.g. how compress, uncompress, and length should be related to each other), which I like more.

As for "optimizing away verification," that's the point of Idris' 0 multiplicity. It marks something as "compile-time-only" that has no runtime representation and hence no runtime performance impact.

Re:Idris 2: Quantitative Type Theory in Practice by atennapel on Monday January 24, 2022 @03:33AM (#30054879)
I haven't written enough dependently typed programs to know what's best, but just an argument in favour of the OP version :): I agree that your version is easier to understand. But with the other version the types at least guide you in the implementation of the compress/uncompress. In your version you can return any `List t`.
Re:Idris 2: Quantitative Type Theory in Practice by dwohnitmok on Monday January 24, 2022 @04:20AM (#30055170)
For the sake of discussion I'm going to say something stronger than I believe, but which I don't think gets enough airtime so I want to expose its most extreme version. Having sufficient type direction such that there is only one possible implementation of a function is a bad thing. It represents a tightly constrained data type that will be painful to make even the smallest changes to down the road and duplicates code for no real benefit.

The definition of `RuntimeLength` does not do away with the need to define `uncompress`, all it does is move it into the definition of `RuntimeLength`. In fact my version of `RuntimeEncodedList` and `uncompress` is less overall code than `RuntimeLength` and `uncompress`. Indeed the only reason the compiler can synthesize `uncompress` is because it duplicates `RuntimeLength`! So really the compiler hasn't reduced the amount of work that needs to be done. Just like I could've messed up my definition of `uncompress`, its equivalent in `RuntimeLength` could also have been written incorrectly. We haven't reduced the amount of code that needs to be checked by a human for correctness (in the absence of other invariants), only moved it from a function definition to a data type definition.

By moving it into a function, however, we can then selectively add as many additional properties as we want (such as the `uncompress(compress xs) == xs` invariant), without having to worry about privileging one over any other.

Re:Idris 2: Quantitative Type Theory in Practice by atennapel on Monday January 24, 2022 @05:35AM (#30055812)
Thank you for your comment, I haven't thought about it from this point of view before. What do you think about simpler datatypes like Vector? This can also be seen as a `List` with the constraint that `Vector n A = (l : List A) * length l = n`.
Re:Idris 2: Quantitative Type Theory in Practice by dwohnitmok on Tuesday January 25, 2022 @03:29AM (#30069575)
I personally balk even against sized vectors. It's too easy to accidentally find yourself writing out long proofs for arithmetic theorems that could easily be verified some other way (e.g. using a SAT solver). Although Idris 2 makes great strides here with zero multiplicity annotations on the vector lengths which makes bailing out a more feasible option.

Instead of

  append : Vector n a -> Vector m a -> Vector (n + m) a
I'd prefer just

  append : List a -> List a -> List a
and a separate theorem

  appendSumsLength : (xs : List a) -> (ys : List a) -> length (append xs ys) = length xs + length ys
Sure it's wordier in the short-term, but I think it pays dividends in longer term maintenance.

To be clear though this is a minority position. Other programmers will argue that putting the size parameter in the data type itself makes a lot of proofs essentially trivial and that at least in the case of sized vectors, the issue of "privileging a single invariant" is less of an issue, because the only defining feature of a polymorphic list is its length. I personally disagree with the merits of this trade-off for most production code, but that's starting to get into the weeds.