6 ms·

It has global type inference, there's nothing dynamic in the language. You can specify type restrictions to allow overloading methods, for example, or doing mul

It has global type inference, there's nothing dynamic in the language. You can specify type restrictions to allow overloading methods, for example, or doing multiple dispatch. But in the general case you don't specify types (except for generic type arguments) and the compiler figures out everything.

kibwen 11y ago
I'm curious how possible it is in practice to write large software that relies exclusively on global type inference. Does the compiler itself go without ever explicitly specifying a type?
- asterite 11y ago
  Yes, you can browse the source code if you want, check it out and compile the compiler. It has between 30k and 60k lines of code (because you have to consider it also includes the standard library) and on a Macbook Pro 2015 it takes less than 10 seconds to compile (in non-release mode). We'll have to wait until we get project that's larger than the compiler, but we believe there's still room for performance improvements.
  - logicchains 11y ago
    It seems to have a fair slew of type-system features, so how does it manage to compile so fast, compared to for instance the Rust compiler, which doesn't do global type inference?
    - kibwen 11y ago
      The current slowness of the Rust compiler is largely due to putting more developer attention into improving the runtime speed of fully-optimized binaries. Hence, regardless of which mode it's in, the compiler does a lot of unnecessary work that a debug-mode binary doesn't need or benefit from. There's also simply a ton of low-hanging fruit lying around: we're only two weeks out from 1.0 and the nightly compiler is already reportedly 30% faster for code compiling in the wild. There's another 10% compilation speed reduction coming from work around optimizing linking. There's also work towards parallel codegen coming along nicely (https://github.com/rust-lang/rust/pull/26018 https://github.com/rust-lang/rust/pull/26018) which reports a 30% reduction in compilation time. In the longer run there are plans for incremental compilation which should drastically reduce the amount of work that gets unnecessarily repeated with each compilation cycle (https://github.com/rust-lang/rfcs/pull/594 https://github.com/rust-lang/rfcs/pull/594). In the even longer run there are plans to fully parallelize the compiler phases and also to pre-optimize code before it gets to LLVM in order to reduce the sheer quantity of IR that we shovel into it. TL;DR: Crystal manages much faster compilation than Rust because Rust's compiler developers may have deprioritized optimizing the compiler for a bit too long. :)
      - bjeanes 11y ago
        Thanks for linking to those RFCs. The planned or in-progress work for Rust compilation speed is very exciting. I can't wait to reap the benefits!
    - asterite 11y ago
      It's because we spent some time thinking the algorithms and optimizing them, and whenever we make changes to the compiler we make sure the times remain pretty much the same (it's hard because the compiler's size grows so the times inevitably grow, at least for the compiler). And from time to time we profile and optimize further, we like speed. I believe with time Rust can achieve a similar performance, maybe even better because they will be able to do incremental compilation (maybe, I'm not sure how will they do that with parameterized types). There's also the thing that most of the things in Crystal are lazy: if you don't invoke a method there are no type checks to be done for it. This means that you only pay for what you use (in terms of compile speed) but also what you don't use doesn't end up being in the resulting executable.
      - tatterdemalion 11y ago
        > most of the things in Crystal are lazy: if you don't invoke a method there are no type checks to be done for it Does this mean that if a library doesn't have complete test coverage compile-time errors could be discovered only by clients?
        asterite 11y ago
        Almost. You at least need to exercise the code at compile time. For example you could write dummy usage tests like this: typeof(MyClass.new.some_method(1, 2, 3)) That basically says "the above compiles and has some type", so you don't have to test what that method really does, just that it compiles. I don't think it's a big problem, though. In Ruby it's the same: unless you exercise your code you don't know if it works. Now, think of a classically compiled language like C and C++: if it compiles, does it mean that it works? I doubt you'd release your code without at least a few tests (or a small test-app) to try it.
- reagency 11y ago
  GHC does global type inference, and has very sophisticated types.
  - kibwen 11y ago
    My point was specifically in regard to the feasibility of omitting the types in all cases. I see types often in Haskell code, likely because the community regards that as a best practice (in contrast to Crystal).
    - tel 11y ago
      Best practice and it's required to make certain more advanced type features work. It's the same with Crystal. Their generics require type annotations.
    - Vulume 11y ago
      In Haskell types are used a lot as documentation and to make static guarantees about the program logic, not just runtime safety. If you're only worrying about illegal operations you practically don't need signatures.
  - agrafix 11y ago
    ...and is a slow compiler compared to for example Go :-(
    - dmbaturin 11y ago
      OCaml has separate compilation, a REPL, and it's very fast. None of those things is incompatible with global type inference (although particular type systems can be).
      - seanmcdirmid 11y ago
        Doesn't OCaml require everything to be defined before used though?
    - Vulume 11y ago
seanmcdirmid 11y ago
What algorithm are you using? How do you deal with subtyping and paramatricity?
- tel 11y ago
  They have a couple posts on their inference algorithm, but I confess I haven't read them.
- asterite 11y ago
  The algorithm isn't very easy to explain in a few words. We don't use any well-known algorithm. It has some bits of the cartesian-product algorithm, but just tiny bits. There's some info here: http://crystal-lang.org/2013/09/23/type-inference-part-1.html http://crystal-lang.org/2013/09/23/type-inference-part-1.htm... http://crystal-lang.org/2014/04/27/type-inference-rules.html http://crystal-lang.org/2014/04/27/type-inference-rules.html About subtyping and paramtricity, I'm not sure what's that, but the compiler just keeps track of all the types and forms unions, except in one case which is this one (a union of references with a base type): http://crystal-lang.org/docs/syntax_and_semantics/virtual_and_abstract_types.html http://crystal-lang.org/docs/syntax_and_semantics/virtual_an...
  - seanmcdirmid 11y ago
    If you are using Agesen-style CPA, then it is more of a global analysis (type recovery) then type inference. I would be a bit worried about scaling, but if you've put 50kloc through it, maybe you've figured it out? I'm working on my own type-less type inference system that I'll share more about soon.
  - dmbaturin 11y ago
    Do you have a (more or less) formal description of the type system?

kibwen 11y ago

I'm curious how possible it is in practice to write large software that relies exclusively on global type inference. Does the compiler itself go without ever explicitly specifying a type?

asterite 11y ago
Yes, you can browse the source code if you want, check it out and compile the compiler. It has between 30k and 60k lines of code (because you have to consider it also includes the standard library) and on a Macbook Pro 2015 it takes less than 10 seconds to compile (in non-release mode). We'll have to wait until we get project that's larger than the compiler, but we believe there's still room for performance improvements.
- logicchains 11y ago
  It seems to have a fair slew of type-system features, so how does it manage to compile so fast, compared to for instance the Rust compiler, which doesn't do global type inference?
  - kibwen 11y ago
    The current slowness of the Rust compiler is largely due to putting more developer attention into improving the runtime speed of fully-optimized binaries. Hence, regardless of which mode it's in, the compiler does a lot of unnecessary work that a debug-mode binary doesn't need or benefit from. There's also simply a ton of low-hanging fruit lying around: we're only two weeks out from 1.0 and the nightly compiler is already reportedly 30% faster for code compiling in the wild. There's another 10% compilation speed reduction coming from work around optimizing linking. There's also work towards parallel codegen coming along nicely (https://github.com/rust-lang/rust/pull/26018 https://github.com/rust-lang/rust/pull/26018) which reports a 30% reduction in compilation time. In the longer run there are plans for incremental compilation which should drastically reduce the amount of work that gets unnecessarily repeated with each compilation cycle (https://github.com/rust-lang/rfcs/pull/594 https://github.com/rust-lang/rfcs/pull/594). In the even longer run there are plans to fully parallelize the compiler phases and also to pre-optimize code before it gets to LLVM in order to reduce the sheer quantity of IR that we shovel into it. TL;DR: Crystal manages much faster compilation than Rust because Rust's compiler developers may have deprioritized optimizing the compiler for a bit too long. :)
    - bjeanes 11y ago
      Thanks for linking to those RFCs. The planned or in-progress work for Rust compilation speed is very exciting. I can't wait to reap the benefits!
  - asterite 11y ago
    It's because we spent some time thinking the algorithms and optimizing them, and whenever we make changes to the compiler we make sure the times remain pretty much the same (it's hard because the compiler's size grows so the times inevitably grow, at least for the compiler). And from time to time we profile and optimize further, we like speed. I believe with time Rust can achieve a similar performance, maybe even better because they will be able to do incremental compilation (maybe, I'm not sure how will they do that with parameterized types). There's also the thing that most of the things in Crystal are lazy: if you don't invoke a method there are no type checks to be done for it. This means that you only pay for what you use (in terms of compile speed) but also what you don't use doesn't end up being in the resulting executable.
    - tatterdemalion 11y ago
      > most of the things in Crystal are lazy: if you don't invoke a method there are no type checks to be done for it Does this mean that if a library doesn't have complete test coverage compile-time errors could be discovered only by clients?
      - asterite 11y ago
        Almost. You at least need to exercise the code at compile time. For example you could write dummy usage tests like this: typeof(MyClass.new.some_method(1, 2, 3)) That basically says "the above compiles and has some type", so you don't have to test what that method really does, just that it compiles. I don't think it's a big problem, though. In Ruby it's the same: unless you exercise your code you don't know if it works. Now, think of a classically compiled language like C and C++: if it compiles, does it mean that it works? I doubt you'd release your code without at least a few tests (or a small test-app) to try it.
reagency 11y ago
GHC does global type inference, and has very sophisticated types.
- kibwen 11y ago
  My point was specifically in regard to the feasibility of omitting the types in all cases. I see types often in Haskell code, likely because the community regards that as a best practice (in contrast to Crystal).
  - tel 11y ago
    Best practice and it's required to make certain more advanced type features work. It's the same with Crystal. Their generics require type annotations.
  - Vulume 11y ago
    In Haskell types are used a lot as documentation and to make static guarantees about the program logic, not just runtime safety. If you're only worrying about illegal operations you practically don't need signatures.
- agrafix 11y ago
  ...and is a slow compiler compared to for example Go :-(
  - dmbaturin 11y ago
    OCaml has separate compilation, a REPL, and it's very fast. None of those things is incompatible with global type inference (although particular type systems can be).
    - seanmcdirmid 11y ago
      Doesn't OCaml require everything to be defined before used though?
  - Vulume 11y ago

seanmcdirmid 11y ago

What algorithm are you using? How do you deal with subtyping and paramatricity?

tel 11y ago
They have a couple posts on their inference algorithm, but I confess I haven't read them.
asterite 11y ago
The algorithm isn't very easy to explain in a few words. We don't use any well-known algorithm. It has some bits of the cartesian-product algorithm, but just tiny bits. There's some info here: http://crystal-lang.org/2013/09/23/type-inference-part-1.html http://crystal-lang.org/2013/09/23/type-inference-part-1.htm... http://crystal-lang.org/2014/04/27/type-inference-rules.html http://crystal-lang.org/2014/04/27/type-inference-rules.html About subtyping and paramtricity, I'm not sure what's that, but the compiler just keeps track of all the types and forms unions, except in one case which is this one (a union of references with a base type): http://crystal-lang.org/docs/syntax_and_semantics/virtual_and_abstract_types.html http://crystal-lang.org/docs/syntax_and_semantics/virtual_an...
- seanmcdirmid 11y ago
  If you are using Agesen-style CPA, then it is more of a global analysis (type recovery) then type inference. I would be a bit worried about scaling, but if you've put 50kloc through it, maybe you've figured it out? I'm working on my own type-less type inference system that I'll share more about soon.
- dmbaturin 11y ago
  Do you have a (more or less) formal description of the type system?