3 ms·
> reinventing a run-time type checker It's not a runtime type checker, but a spec (not a type[1]!) that tools can use to check in different ways. ------------
by pron 10y ago
> reinventing a run-time type checker
It's not a runtime type checker, but a spec (not a type[1]!) that tools can use to check in different ways.
------------
[1]: A spec is a proposition; a type is a judgment (that corresponds to a proposition). E.g., you can have a type: `data A = 1 | 2 | 3`, and `data B = 3 | 4 | 5`, but then testing `a < b` (assuming `a:A b:B`) may not be straightforward (depending on the language), while a spec of `A = {1, 2, 3}, B = {1, 2, 3}, a ∈ A, b ∈ B` does let you test `a < b`.
- lomnakkus 10y agoTypes are propositions. See Curry-Howard.
- pron 10y agoTypes encode propositions (see Curry-Howard) but are logical judgments in the language's logic. The expression `a:A` does not have a boolean truth value (like a logical proposition), but is rather a judgment. In my example above, the value of the expression `a ∈ B` is true iff a = 3 and false otherwise, but the expression `a:B` is just not a well-formed expression. In other words, you could create a type that corresponds to a proposition, but type assignment is distinct from a proposition (e.g. the proposition `b1 < b2`, assuming `b1,b2:B`) in the language. More precisely, you could say that types encode propositions at the type level (even if the language allows the same data-level syntax in type definitions, as in Idris), while propositions at the data level are distinct, while specs are data level propositions.
- catnaroek 10y ago`x:T` is a typing judgment. A typing judgment is not a type, even if one of its constituent parts (`T`) is a type. What you call “data-level propositions” is really just “data-level abstract syntax representation of propositions”. Propositions really are types. (Though, of course, there are types that are not propositions.) And your example is simply not valid Haskell.
- pron 10y ago> A typing judgment is not a type You are absolutely right. `x` is a proof object of `T` in the logic induced by the language, but I didn't want to get to that level of technicality, just to show the difference between data-level propositions and type-level ones. That's why I added the second paragraph, but in the process confused matters; sorry. > Propositions really are types. Types have a syntactic meaning that determines the well-formedness of an expression. Once you talk about types, you must talk about a language; a type cannot exist without a language because it is a syntactic construct, but a proposition can: it is a set (of programs, or Turing machines if you like; people in the verification community may say it's a set of states in a Kripke structure). Now, you could say that given the proposition (or the set) P, you can construct type P in language L that expresses it, but P would still not be a data-level expression in L. You can then argue about whether or not this matters, but you can't deny that the two expressions of proposition, i.e., the dynamic `x < 10` and `T`, are distinct and "live" in two separate worlds. When data-level propositions are concerned, this is not the case. E.g., in TLA+, an untyped logic (TLA+ZFC), the program and the propositions are the very same objects and not at all just a "data-level abstract syntax representation of propositions". > And your example is simply not valid Haskell. It wasn't meant to be (I haven't written a Haskell program in over 15 years). Sadly, unlike standard logic and set notation, there isn't a standard notation for typed LC with data types, or any typed logic for that matter (not one that I'm familiar with), so you have to use something with a meaning people would understand or define a syntax every time.
- catnaroek 10y ago> but a proposition can: it is a set Set theories are normally built on top of the apparatus of logic, so a proposition can't be a set. > (of programs, or Turing machines if you like; people in the verification community may say it's a set of states in a Kripke structure) Ah, I see. You aren't talking about general propositions. You're talking about assertions about program states that can be checked dynamically, but want to verify statically. You can't represent an arbitrary proposition as a data structure, but it's of course a-whole-nother matter if you can decide the proposition's truth value by evaluating a Java expression of type `boolean`. The `boolean` expression itself is still not a proposition, though. > but you can't deny that the two expressions of proposition, i.e., the dynamic `x < 10` and `T`, are distinct and "live" in two separate worlds. Most programming languages don't have propositions at all, for a very good reason: a proposition is the type of a programmer-supplied proof that has no runtime computational relevance, and how to integrate proofs into programming is still a research question whose answer language designers can't wait for. In Java, “the dynamic `x < 10`” is just a `boolean` expression - not a proposition! > E.g., in TLA+, an untyped logic (TLA+ZFC), the program and the propositions are the very same objects and not at all just a "data-level abstract syntax representation of propositions". In TLA+, or any other external program logic, the program itself is just a syntactic object. And by extension so is any `boolean` expression the program might contain. OTOH, if Java had propositions, you could carry out your reasoning internally, side-stepping the need to encode propositions as abstract syntax for a metalanguage to see.
- catnaroek 10y agoIt's more accurate to say that some types are propositions. More precisely, a type is a proposition if and only if any two inhabitants of it are equal.
- catnaroek 10y agoConfusing types with typing judgments is wrong. A type is just one of the constituent parts of a typing judgment.