5 ms·
Church vs. Curry Types
- karmakaze 3y agoI can't tell if there's anything here I should be trying to learn. Best I can tell it's choosing obtuse naming for Static and Dynamic typing. > Summary: Static vs dynamic typing debates often flounder because the debators see from two different perspectives without knowing it. Learning to identify the two perspectives can calm the discussion. The tension between the two perspectives has led to Gradual Typing and other technologies. I'm not buying this. The best pragmatic answer for myself is that static types is better in large or across teams. Dynamic typing is good for solo or early development by a small team. Gradual typing is the best you can get when a product developed with dynamic typing grows to be developed by many.
- awkward 3y agoIt's comparing static typing as exists in Haskell or OCaml to static typing as exists in C++ or Typescript. To dynamically type a program in the first group, you would have to manually make a giant type that includes everything and use that everywhere. In the second, you can program dynamically by turning the safety off.
- deleted 3y ago[deleted]
- hardlianotion 3y agoAre you sure you meant C++ in the second group? In Typescript you can program dynamically, perhaps. In C++, you'd have to cast everything brutally, which I don't think most would call programming dynamically, or do what you propose for OCaml.
- awkward 3y agoCasting at all really solidly puts it in that group. The idea that there’s a program and a type system and you tell the type system when it’s diverged from the program doesn’t really work in the other group of languages.
- hardlianotion 3y ago(Complete rewrite) I think this may be true in theory but not a practical way to think about c++, as the language fights you if you try to use in that way.
- beders 3y agoThe ability to reason about code, to split it into modules that can be developed independently etc. is not dependent on having a static type system. It is dependent on having a specification. "Types" is just one form of, in many languages quite limited, specs.
- nyssos 3y ago> "Types" is just one form of, in many languages quite limited, specs. That's the "Curry types" perspective described in the article, yes. "Church types" are syntax, not specification. In Haskell, for example main = print (5 + "foo") isn't a program that fails to conform to its spec, it's just not a program. It has no meaning and no behavior, not wrong behavior. You can (but should never) `unsafeCoerce` `5` to `String` or `"foo"` to `Int` and get something broken out - but they'll be different broken things, and neither will in any sense be the compiled form of the `main` function above.
- ltr_ 3y agoI agree with your sentiment and resonate with some of my opinions on languages (been reading about TT and abstract math in general for a while as a hobby) my opinions so far (subject to change as i read more): dynamic typing = just one type [0]. yes, good to test ideas quick, to develop quick gigs that i don't care about and tiny snippets/scripts, i use js for that. gradual typing = guaranteed mess evolving large code bases, I guess the gradual typing thing in practice never happen and when it happens your IDE becomes red and your compiler errors explode, i don't recall where i read about that but it made sense to me, i used groovy to take advantage of the optional typing but i was the only dev in that project. sound type system + parametric polymorphism = the best thing around, although i prefer to have explicit type annotations. no formal math object behind a language = the language does not exist, just , absurd rules ,idioms and syntactic mess that you have to remember and tied to specific monkey patched implementations to compensate incoherent foundations, sadly unavoidable, as most, if not all popular languages do not exist,. Yes, I've been reading Harper a lot. [0] https://existentialtype.wordpress.com/2011/03/19/dynamic-languages-are-static-languages https://existentialtype.wordpress.com/2011/03/19/dynamic-lan... edit: formatting
- throwaway81523 3y ago> I can't tell if there's anything here I should be trying to learn. Best I can tell it's choosing obtuse naming for Static and Dynamic typing. No not at all, both are static. Church style typing means all the terms are annotated with their types. In practice, languages like Haskell have some type inference, so the compiler figures out some of the annotations for you (or even all of them, in easy cases) instead of making you annotate everything, but inside the compiler every term is marked with a type (whether supplied by you or inferred by the compiler). In Curry style typing, there are no annotations at all, and the type inference algorithm has to figure everything out itself. In the most general case, this problem is Turing-complete, i.e. undecideable. Part of the challenge in projects like Liquid Haskell is to automate as much inference as possible without running up against this barrier.
- karmakaze 3y agoThe way the article describes Curry style typing seems like dynamic/optional/gradual types to me. > Curry-style types is when a system of types is applied that is not part of the semantics of the language. This is what Clojure has in core.typed. The meaning of a Clojure program is not dependent on it passing the type checker---it can be run without it. The type checker simply alerts you to type errors in your code. Note that you could consider your type checker to be your own head, which, as flawed as it may be, is what most Clojure programmers use. The types could be anywhere outside of the language. I'm not familiar with Clojure/core.typed--how is it different than TypeScript (or JavaScript with the type checker in your head)? It seems that if the type check fails it does so statically, but often it doesn't fail statically but rather at runtime. I can see that is a distinction but understanding this difference doesn't offer much practical value.
- awkward 3y agoThis is a great distinction! With typescript getting wider use, I've found myself frustrated by the limitations of bolt on type systems. Knowing how deep the divide is from languages with fully inferrable types gives me more appreciation for how much work went into the current state of inferencing tools.
- shepherdjerred 3y agoI found TypeScript to be _incredible_ once you use a runtime validation library like Zod or io-ts. TypeScript itself has a great type system, but the culture in TS is to use `any` at the boundaries of your app, e.g. in parsing HTTP requests, local storage, URL routes -- any data outside of the type system. This greatly reduces how much a type system can help you. Zod, io-ts, and other similar library, allow you to enforce type constraints at runtime in a very sleek, easy way, and they don't require you to write your types twice, either. I've found that this makes TypeScript feel almost as safe as languages with much better type systems, e.g. Haskell.
- DylanSp 3y agoThe Typescript team has been pushing the use of `unknown` instead of `any` for typing data at the boundaries of your app; how much of that has shown up in the ecosystem? EDIT: I definitely agree with your general point, for the record.
- shepherdjerred 3y agounknown definitely helps, but it doesn't solve the problem. You still need to get the data from unknown -> your type. Most people will resort to casting, which is unsafe. Runtime type libraries let you know _for sure_ that the type is correct. example: https://tinyurl.com/yc74stm6 https://tinyurl.com/yc74stm6 I adopted this pattern at work for all of our API calls, local storage, route parameters, etc.. The result was the app was fully typed, and we handled every case of invalid data in a reasonable way. When data is invalid, we can provide a sane default value.
- malcolmgreaves 3y agoIt's wonderful to see an article about this topic that's grounded in rigorous thought. And that references the long, rich history of folks who have worked hard to articulate the problems and solutions one encounters when programming. From my experience and training, I'm biased towards the Church-style of thought for representing all programs. My reasoning is simple: ultimately, we write programs to solve a problem. The implementation of the program is a secondary concern to producing a correct solution. An incorrect solution is just about as useful as a program that immediately exits after starting. [1] Using the type-oriented perspective to programming shifts the paradigm from *how* a computer program works to *what* it is accomplishing. When we're sure we have the "what" correct, we can then perform transformations on our program to optimize its implementation to achieve different second-order properties on the "how." Do we need this to run faster? Do we need this to use less memory? Do we need this to re-use a pool of threads or network connections? Do we need this to use SIMD instructions because that's what our hardware supports? The possibilities for "how" can be seemingly endless: they're always use-case specific. However, when we're thinking about solutions, we necessarily must be focused on achieving a singular goal: the problem is solved. When we use types to represent our program semantics, we gain an awesome level of problem-solving ability. We can ensure that our program semantics really do solve our problem. We don't need to wait for an actual execution of our program to determine whether or not we've solved it. In a laymen's sense of the term, we gain an exponential speed-up in our ability to make correct programs. It makes insanely complex problems solvable. And it makes the simple ones trivial. We stop wasting our time focusing on re-solving every detail that needs to go into the execution of our program. Instead, we are able to build upon foundations that _we know work_. Could we get to where we are today if we had to to write every new program in hardware-specific assembly? Implement every piece of functionality going down to the level of "how will my processor be able to execute this?" Of course not! We've realized this in many cases: when we use compilers, we transform a solution defined in one space to an equivalent solution defined in another; we implement our web app endpoints using the types and semantics of WSGI; we make our complex distributed systems on the back of infrastructure with well-documented components that specify the types of things that they support and what they provide. We're surrounded by examples of successful large systems that rely explicitly on defining types. Ultimately, it's my strongly held belief that for the software industry to mature to genuine engineering, it's imperative for our collective thought to embrace mathematical rigor. This is not to gatekeeper others: everyone can learn. We must believe that we can understand this well enough to teach absolutely _anyone_ who is willing to put in the time and effort to understand. If we're serious, we need to graduate from the notion that we're only writing programs to we're coding up solutions to our problems. Where we define and reason about the problem at a conceptual, abstract level and then move towards reusing and combining solutions from Computer Science. -- [1] And it may be _less useful_ than that: consider a program that produces _ever so slightly wrong_ results. Is it feasible to always verify that its output is always correct _each time that it is run_? If one needs to do that work, then is it actually automated? If it's not automated, why put in the effort to program a machine to perform the work?
- ChrisArchitect 3y ago(2018)
- layer8 3y agoI don’t think this is necessarily a binary distinction. Even in a statically-typed language, so ostensibly with Church types, you can imagine a refined type system being added as type annotations. For example, many statically-typed languages do not support range constraints on their built-in numeric types, and such constraints could be added as type annotations, analogous to type annotations in a dynamically-typed language. A real-life example of this are linters with linter annotations in comments. So instead of a dichotomy it is really a lattice of possible type refinements. And the top of the lattice corresponds to the single-type view of dynamically-typed languages. The concrete language chooses a particular point in the lattice as its universally enforced typing level. (Or sometimes just by-default enforced, if there are escapes like “unsafe”.) But the choice is among all points in the lattice, not just two points. As a side node, it is etymologically amusing that Haskell doesn’t have Curry types.
- zokier 3y ago> I don’t think this is necessarily a binary distinction. Even in a statically-typed language, so ostensibly with Church types, you can imagine a refined type system being added as type annotations. Considering author provides LiquidHaskell as example, I'd imagine they'd agree with this sentiment > As a side node, it is etymologically amusing that Haskell doesn’t have Curry types. If I understand correctly, LiquidHaskell corrects that :)
- mrkeen 3y agoI'm so lost. (I'm firmly in the static-typing camp, coming from an internal philosophy of "computers are supposed to do things as fast as possible, and not make mistakes".) > Intrinsic types are great because you are guaranteed to have a mathematically-sound safety net at all times. Sounds great, even if I take it with the usual grain of salt. > Extrinsic types are useful because you can apply multiple type systems to your code If I don't get the mathematically-sound safety net, why would I apply 1 type system to my code, let alone n?
- layer8 3y agoThis lets different parts of your code use different type systems, so to speak, by picking and choosing which annotations you specify. Another real-life example is the “unsafe” mode some statically-typed languages have, which effectively switches to a laxer type system.
- zokier 3y ago> Another real-life example is the “unsafe” mode some statically-typed languages have, which effectively switches to a laxer type system. Are you referring to Rust here? Because I believe unsafe there doesn't change type checking or type system in any way
- layer8 3y ago“Unsafe” disables borrow checking in Rust, which is part of the type system. C# also has a (different) “unsafe”.
- neonsunset 3y agoConceptually speaking they are quite close: both let you write code C-style with raw pointers within unsafe blocks. Similar to Rust, C# also has a subset of Unsafe and Marshal APIs which explicitly indicate their risk for bypassing compiler or language checks when either you know what you are doing or when whatever goal they achieve is not expressible with safe code.
- arxanas 3y agoIt's interesting to note that extrinsic typing is not limited to retrospectively-designed typecheckers. One of the big philosophical differences between Haskell and OCaml is that Haskell permits (encourages) type-directed compilation, while OCaml's type annotations don't affect the program semantics (although they affect whether the program compiles). But both are far away from modern-day retrofitted gradual type systems.
- deleted 3y ago[deleted]
- dllthomas 3y agoSomewhat related playing in the space: https://www.youtube.com/watch?v=3U3lV5VPmOU https://www.youtube.com/watch?v=3U3lV5VPmOU
- epgui 3y agoI don’t think the two pictures are isomorphic. The word “isomorphic” means that it is a bijection that preserves structure from one set to another, but I don’t really see that here beyond a superficial aesthetic similarity. One thing that is isomorphic is mathematical proofs and well-typed computer programs. Without the “well typed” part, you are left with a proof that may or may not be correct and that may or may not make sense.
- throwaway17_17 3y agoI don’t think the article’s characterization of ‘types a la Curry’/extrinsic types is the commonly used understanding in discussions about Type Theories. While the article claims the extrinsic types are ‘not part of the semantics of the language’, I can not agree. My experience in the area leads to extrinsic types which are described better in the following way: extrinsic types are those types which may be ascribed to a syntactic construct in a formal language. In other words, while the types are not present as annotations in the formal syntax of language terms, the fact that every term is of some type is built into the semantics of the formal type theory. One of the best descriptions and formal treatments of Curry-style types in in ‘Functors are Type Refinement Systems’ by Melliès and Zeilberger [1]. That paper is discussed in detail and the formal definitions and properties of Church vs Curry types are explored in Zeilbergers OPLSS lectures on Type Refinement. 1 - http://noamz.org/papers/funts.pdf http://noamz.org/papers/funts.pdf 2 - Zeilberger at OPLSS in 2016, 4 lectures
- nickm12 3y agoI didn't find this post very illuminating. It needs some actual examples of typed code and how the different interpretations would apply. The linked Wikipedia article actually did have an example, and it helped me understand a bit better, but it was in terms of the lambda calculus, so I'm still not entirely seeing how this applies to static and dynamic type system debate. Also: (2018)
- somewhereoutth 3y agoTo make this a bit more concrete, imagine you were passing the identity function into another function or context, but then using it both with an Int term, and a Bool term. Thus by inference that identity function has the type Int->Int, and Bool->Bool. Under Curry, this is ok, but under Church, it is not. I don't think it has much to do with static vs dynamic, or indeed type labels.