# Are inferred types "frozen" for crystal shards and the standard library?
**URL:** https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434
**Category:** Crystal Contrib
**Created:** [December 2, 2019, 8:58pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434 "2019-12-02T20:58:11Z")
**Posts on this page:** 12
**Page:** 1
### Author:  [@ndbroadbent](https://forum.crystal-lang.org/u/ndbroadbent)
#### Post date: [December 2, 2019, 8:58pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/1 "2019-12-02T20:58:11Z")
I’ve started reading through some of the code in the standard library. I saw that a lot of methods already have type definitions, but I found [a few cases that rely on type inference](https://github.com/crystal-lang/crystal/blob/5444a06b3238930a47c401a40ba05b92923f0cd7/src/json/from_json.cr#L11-L14).
I was wondering if the types in the standard library and shards are treated differently to application code, or is there currently no distinction?
When I’m developing and testing an application, I’m only going to be modifying my application source code, and the standard library and any Crystal shards will never change. So would it make sense to perform a first pass on the standard library + shards, where we “lock down” the inferred types for any of these static files? (Or we could say: bake / freeze / crystallize?) And could this even been done as a pre-release step whenever a developer publishes a new Crystal shard? (E.g. Maybe a `crystal tool format` option that “expands” all of the inferred types and writes out new crystal files into a build directory?)
As an example, I’m looking at [json/from\_json.cr:11](https://github.com/crystal-lang/crystal/blob/5444a06b3238930a47c401a40ba05b92923f0cd7/src/json/from_json.cr#L11-L14):
```auto
def Object.from_json(string_or_io)
parser = JSON::PullParser.new(string_or_io)
new parser
end
```
So it makes sense that I get this type error:
```auto
$ crystal eval 'require "json"; Array.from_json(123)'
Showing last frame. Use --error-trace for full trace.
In /usr/local/Cellar/crystal/0.31.1/src/json/pull_parser.cr:49:20
49 | @lexer = Lexer.new input
^--
Error: no overload matches 'JSON::Lexer.new' with type Int32
Overloads are:
- JSON::Lexer.new(string : String)
- JSON::Lexer.new(io : IO)
- JSON::Lexer.new()
```
I can see that the type error is actually coming from the typed [`Lexer.new input`](https://github.com/crystal-lang/crystal/blob/5444a06b3238930a47c401a40ba05b92923f0cd7/src/json/lexer.cr#L4-L10) inside the call to [`JSON::PullParser.new(string_or_io)`](https://github.com/crystal-lang/crystal/blob/5444a06b3238930a47c401a40ba05b92923f0cd7/src/json/pull_parser.cr)
So if I open `/usr/local/Cellar/crystal/0.31.1/src/json/pull_parser.cr:49:20` and add the type annotation:
```auto
def initialize(input : String | IO)
```
Then that moves the error further down the chain:
```auto
In /usr/local/Cellar/crystal/0.31.1/src/json/from_json.cr:12:29
12 | parser = JSON::PullParser.new(string_or_io)
^--
Error: no overload matches 'JSON::PullParser.new' with type Int32
Overloads are:
- JSON::PullParser.new(input : String | IO)
```
And then again for `/usr/local/Cellar/crystal/0.31.1/src/json/from_json.cr:12:29`:
```auto
def Object.from_json(string_or_io : String | IO) : self
parser = JSON::PullParser.new(string_or_io)
new parser
end
```
```auto
$ crystal eval 'require "json"; Array.from_json(123)'
Showing last frame. Use --error-trace for full trace.
error in line 1
Error: no overload matches 'Array(T).from_json' with type Int32
Overloads are:
- Array(T).from_json(string_or_io, &block)
- Object.from_json(string_or_io, root : String)
- Object.from_json(string_or_io : String | IO)
```
I actually find this error message much more obvious than the original error that talks about `@lexer = Lexer.new input`. And this would allow the standard library developers to still use type inference wherever it’s convenient. But all of the inferred types in the standard library could become expanded and “frozen”.
Is Crystal already doing this behind the scenes? If not, what would be some of the downsides?
---
### Author:  [@asterite](https://forum.crystal-lang.org/u/asterite)
#### Post date: [December 2, 2019, 9:25pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/2 "2019-12-02T21:25:16Z")
> [@ndbroadbent](#):
>
> So would it make sense to perform a first pass on the standard library + shards, where we “lock down” the inferred types for any of these static files?
So, Crystal is pretty unique about how it types things.
If you feed it this:
```crystal
def Object.from_json(string_or_io)
parser = JSON::PullParser.new(string_or_io)
new parser
end
```
you might think, based on how other languages work (particularly Haskell or Elm, where you can omit the types of arguments and the compiler will infer them), that the compiler will infer the type of that method and conclude that `string_or_io` is `String | IO`.
However, that’s **not** how Crystal works.
The way Crystal works is that methods are always untyped. The compiler doesn’t know their type, and there’s no need to know their type. They only get a type, and this type is not assigned to the method but rather to an **instantiation** of a method (think C++ templates, or generics), when you **call** a method. Just then the compiler will go ahead and infer the type of the body. But argument types are never inferred.
That’s why there’s no “lock down” types from shards or from anything.
And all of this is of course related to “why it’s difficult to do incremental compilation in Crystal”.
---
### Author:  [@ndbroadbent](https://forum.crystal-lang.org/u/ndbroadbent)
#### Post date: [December 2, 2019, 10:29pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/3 "2019-12-02T22:29:41Z")
Thanks for your reply! I think I am starting to understand what you mean, but I am still a bit confused, so I would like to talk about this concrete example.
Given the following source code:
```auto
# https://github.com/crystal-lang/crystal/blob/master/src/json/lexer.cr#L3-L10
abstract class JSON::Lexer
def self.new(string : String)
StringBased.new(string)
end
def self.new(io : IO)
IOBased.new(io)
end
```
```auto
# https://github.com/crystal-lang/crystal/blob/master/src/json/pull_parser.cr#L48-L49
class JSON::PullParser
def initialize(input)
@lexer = Lexer.new input
```
```auto
# https://github.com/crystal-lang/crystal/blob/master/src/json/from_json.cr#L11-L14
def Object.from_json(string_or_io)
parser = JSON::PullParser.new(string_or_io)
```
And this code from an application:
```auto
# src/main.cr
require "json"
Array.from_json(123)
```
Crystal will fail with this type error:
```auto
Error: no overload matches 'JSON::Lexer.new' with type Int32
```
So Crystal needed to do perform some type inference through this chain:
- `Array.from_json(123)` =\>
- `Object.from_json(string_or_io)` =\>
- `JSON::PullParser.new(string_or_io)` =\>
- `@lexer = Lexer.new input`
- `abstract class JSON::Lexer; self.new(string : String)`
- `abstract class JSON::Lexer; self.new(string : IO)`
In this case, would the Crystal type-checking algorithm have better performance if `Object.from_json` was given a type annotation of `String | IO`? E.g. Would it be able to find the type error immediately and fail faster? And in the case where there are no type conflicts, would these explicit type annotations speed up the type-checking phase?
(I guess I was assuming that explicit type annotations do help to improve performance and reduce the amount of time and memory used for type inference, but that might be totally wrong!)
So even if the current compiler / type inference algorithm doesn’t look at methods until they are called, what if there was a separate type inference algorithm that was optimized for this case, so it did know how to infer all of these method types by working backwards:
- `Object.from_json(string_or_io : String | IO)` =\>
- `JSON::PullParser.new(string_or_io: String | IO)` =\>
- `@lexer = Lexer.new input`
- `abstract class JSON::Lexer; self.new(string : String)`
- `abstract class JSON::Lexer; self.new(string : IO)`
So:
- If this kind of type inference engine did exist, and
- it was able to emit code (or AST nodes) that included as much type information as possible, and
- this pre-compilation step could be run once during the first compilation, and then cached (or even run in advance before releasing a new shard or crystal version)
Then would this help to speed up the type inference and type checking phases?
Thanks again for your time!
---
### Author:  [@girng\_github](https://forum.crystal-lang.org/u/girng_github)
#### Post date: [December 3, 2019, 4:07am UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/4 "2019-12-03T04:07:55Z")
> [@asterite](#):
>
> The way Crystal works is that methods are always untyped. The compiler doesn’t know their type, and there’s no need to know their type.
Typed method restrictions: Hold my tide pod!! 
---
### Author:  [@asterite](https://forum.crystal-lang.org/u/asterite)
#### Post date: [December 3, 2019, 11:39am UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/5 "2019-12-03T11:39:28Z")
> [@ndbroadbent](#):
>
> In this case, would the Crystal type-checking algorithm have better performance if `Object.from_json` was given a type annotation of `String | IO` ? E.g. Would it be able to find the type error immediately and fail faster? And in the case where there are no type conflicts, would these explicit type annotations speed up the type-checking phase?
So in the lack of type annotations the compiler will just try to type the method and error if it fails (what you see when it gets to the Lexer). If there’s a type annotation the process is slightly slower: we first have to check that the types actually match those in the restriction. So adding type annotations is actually slower to compile! But I didn’t benchmark this, I know it because in one case it’s no-op and in the other there’s some matching going on. However, I believe these times are insignificant.
And yes, if you put `String | IO` as a type restriction then you will get the error at the `Object` level, not at the `Lexer` level.
> [@ndbroadbent](#):
>
> So even if the current compiler / type inference algorithm doesn’t look at methods until they are called, what if there was a separate type inference algorithm that was optimized for this case, so it did know how to infer all of these method types by working backwards:
That’s not compatible with how the current language works.
Take this example:
```crystal
module Moo
abstract def moo
end
class Foo
include Moo
def moo
1
end
end
class Bar
include Moo
def moo
"hello"
end
end
def say_moo(moo : Moo)
moo.moo
end
puts typeof(say_moo(Foo.new))
puts typeof(say_moo(Bar.new))
```
The output is:
```plaintext
Int32
String
```
The type restriction `moo : Moo` is just that, a restriction (that’s why we call it like that). It doesn’t give `moo` the type `Moo` and let’s the compiler infer what’s the type of `moo.moo` from all possible instantiations. If it did that, the type you would get in both cases is `Int32 | String`.
I’m not saying it’s not something that we could do, it’s just that if we go that route the language changes and it becomes a bit less intuitive.
I think what you propose might be possible, though it relies on most users adding full type annotations to their methods. For example, imagine I do this:
```crystal
class Foo
def foo
10
end
end
def something(x : Foo)
x.foo
end
```
Easy: `Foo#foo` has the type `Int32` so we can type this.
Now someone inherits `Foo`:
```crystal
class Bar(T) < Foo
def initialize(@x : T)
end
def foo
@x.baz
end
end
```
Now we don’t know what’s the type of `foo` for this subclass because it’s generic.
Maybe the problem is that `T` is not constrained to some type that defines a `baz` method for which we could know the type. We could maybe change that by introducing interfaces…
I think that, as soon as we try to type something prematurely we’ll run into the situation where we’d like all boundaries (methods, instance vars, args, return types) to be typed so we can be sure that we can type things. Relying on users putting type annotations everywhere is not a good idea.
In some cases some methods can’t be typed. For example `Enumerable#sum`. You can do `[1, 2, 3].sum` but you can’t do `['a', 'b'].sum`. `sum` is defined for all `Enumerable` but it actually works for those where there’s a `zero` method on the class and a `+` method on each element. But all of this is implicit, it works with duck typing. If we want to type that we need to introduce protocols or interfaces or traits, and then the language becomes more complex.
So maybe some methods with some type restrictions could be fully typed, it’s still not clear to me exactly how to do it in a sound way.
---
### Author:  [@fxn](https://forum.crystal-lang.org/u/fxn)
#### Post date: [December 3, 2019, 12:07pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/6 "2019-12-03T12:07:04Z")
> [@asterite](#):
>
> The way Crystal works is that methods are always untyped. The compiler doesn’t know their type, and there’s no need to know their type. They only get a type, and this type is not assigned to the method but rather to an **instantiation** of a method (think C++ templates, or generics), when you **call** a method. Just then the compiler will go ahead and infer the type of the body. But argument types are never inferred.
Ary, could you please illustrate the difference in inference return/argument with one or two very simple methods? Does Crystal generate concrete overloads for all call sites of a method?
---
### Author:  [@asterite](https://forum.crystal-lang.org/u/asterite)
#### Post date: [December 3, 2019, 1:03pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/7 "2019-12-03T13:03:45Z")
> [@fxn](#):
>
> Ary, could you please illustrate the difference in inference return/argument with one or two very simple methods? Does Crystal generate concrete overloads for all call sites of a method?
Sure!
So for this:
```crystal
def double(x)
x + x
end
```
if you call it like `double(1)` then the compiler will generate an instantiation for that:
```crystal
def double:Int32(x : Int32)
x + x
end
```
If you call it with `double("foo")` it will do a similar thing:
```crystal
def double:String(x : String)
x + x
end
```
The names I put there are the actual names the compiler end up generating, and you can see them if you do `--emit llvm-ir` and check the generated `.ll` code.
I’ll actually briefly talk about this on Thursday in the Chicago meetup, but not much more than that (for this topic, I’ll talk about many topics but not very deep in each of them).
---
### Author:  [@fxn](https://forum.crystal-lang.org/u/fxn)
#### Post date: [December 3, 2019, 1:25pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/8 "2019-12-03T13:25:18Z")
Thank you :).
I see. So the compiler is like: this program needs a `double` that receives an `Int32`, and I am going to make that possible unless proved wrong.
You know what? Sounds like “convergence”, or even “crystallization” 😀 to me. “Inference” suggests something more directed, bottom-up, perhaps wrongly, though, since I am not familiar with this topic.
So, when you get a binary, that’s one particular instantiation of everything that satisified all constraints. And the compilation of one library together with some other client code would generally result in a different set of method instances.
Is that the reason why [the prelude](https://github.com/crystal-lang/crystal/blob/master/src/prelude.cr) is compiled everytime a program is compiled?
---
### Author:  [@asterite](https://forum.crystal-lang.org/u/asterite)
#### Post date: [December 3, 2019, 1:44pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/9 "2019-12-03T13:44:48Z")
Yes, indeed! That’s exactly how things work.
And you are right about calling it “type inference” being a bit misleading. We are not inferring anything, we are just typing things top-down. Well, there is quite a fair amount of logic involved in computing these types, specially with `is_a?`, `if`, and creating union types, but nothing is “inferred”, just computed… I guess.
That said, for a given program we could remember which were the instantiations, and later when you compile that same program we could try to reuse those instantiations. The tricky part is determining when we can reuse them.
---
### Author:  [@ndbroadbent](https://forum.crystal-lang.org/u/ndbroadbent)
#### Post date: [December 3, 2019, 1:53pm UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/10 "2019-12-03T13:53:38Z")
Thanks very much, this is really helpful! I’m also looking forward to watching the talk at the Chicago meetup!
---
### Author:  [@Didactic.Drunk](https://forum.crystal-lang.org/u/Didactic.Drunk)
#### Post date: [December 4, 2019, 1:29am UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/11 "2019-12-04T01:29:41Z")
> [@asterite](#):
>
> The way Crystal works is that methods are always untyped. The compiler doesn’t know their type, and there’s no need to know their type. They only get a type, and this type is not assigned to the method but rather to an **instantiation** of a method (think C++ templates, or generics), when you **call** a method. Just then the compiler will go ahead and infer the type of the body. But argument types are never inferred.
Oh great sage @asterite! the gentlest of key fondlers, please offer wisdom to this poor rails abuser.
If I were implementing incremental compilation I’d view it as a application caching problem. Why would that not work for a compiler?
Example:
```auto
# In foo.cr
def foo(arg)
bar(arg)
end
# In bar.cr
def bar(arg)
p typeof(arg)
end
# In controller.cr
foo 1
# In model.cr
foo "2"
```
When `bar.cr` is changed it recursively invalidates all dependants `[foo.cr, controller.cr, model.cr]`.
Most of the time is spent working on application level changes. The shards are fixed and argument types don’t change often which should make the majority of argument calls cachable.
Where have I strayed in my thinking?
---
### Author:  [@asterite](https://forum.crystal-lang.org/u/asterite)
#### Post date: [December 4, 2019, 3:41am UTC](https://forum.crystal-lang.org/t/are-inferred-types-frozen-for-crystal-shards-and-the-standard-library/1434/12 "2019-12-04T03:41:30Z")
You didn’t stray in your thinking. I think we are you saying is possible, we just need to formally specify what a method’s dependencies are and when they can change.
For example, if I define a new file `baz.cr` that I now require, and do this:
```crystal
def bar(x : Int32)
"haha!"
end
```
Well, now foo.cr anb controller.cr need to be recompiled because they changed, **even though `bar.cr` didn’t change**.
Like that, there are many cases that make it hard.
```crystal
macro some_macro
{{ SomeType.subclasses.size }}
end
def bar
some_macro
end
```
Now whenever someone subclasses `SomeType` we need to recompile `bar`.
We also have macro `run` which allows arbitrary execution of code at compile-time. Can we avoid running it over and over on each compilation? I don’t know.
Then the killer problem is generics. Imagine this:
```crystal
module Moo
abstract def moo
end
class Foo
include Moo
def moo
puts "moo!"
end
end
class MooHolder
def initialize(@moo : Moo)
end
def moo
@moo.moo
end
end
MooHolder.new(Foo.new).moo
```
When do we need to recompile `MooHolder#moo`? It seems that if a new type includes `Moo` we need to recompile it. For example:
```crystal
class Bar
include Moo
def moo
puts "Miau!"
end
end
MooHolder.new(Bar.new).moo
```
However, what is a generic type includes `Moo`?
```crystal
class Gen(T)
include Moo
def initialize(@x : T)
end
def moo
@x.moo
end
end
```
The way modules work in Crystal, the compiler needs to know all of the including types, and all actual instances, to be able to do the multi-dispatch. But how do you know the actual instances? For example if I add somewhere deep in my code:
```crystal
MooHolder.new(Gen.new(1))
```
then `MooHolder#moo` should be recomputed. And to do that we essentially need to type the entire program to find these occurrences.
So to be able to cache things we need to type the entire program. Hmm…?
We went over similar discussions with Brian and Juan in an office room in Manas like 3 or 4 years ago (probably more because time passes so fast). One idea was that we could require method return types for generics if the include a module that you want to include like that. But we weren’t sure that’s all that needed to change and how annoying would that be (what if someone includes a module in a type of your own?).
Anyway, if someone wants to go ahead and try to tackle this then go ahead, just beware that the language is actually pretty complex and “dynamic” at compile-time, so computing what are the dependencies of a method is not a trivial task.