line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package Language::MinCaml::TypeInferrer; |
2
|
2
|
|
|
2
|
|
11
|
use strict; |
|
2
|
|
|
|
|
3
|
|
|
2
|
|
|
|
|
69
|
|
3
|
2
|
|
|
2
|
|
11
|
use Carp; |
|
2
|
|
|
|
|
4
|
|
|
2
|
|
|
|
|
120
|
|
4
|
2
|
|
|
2
|
|
10
|
use Language::MinCaml::Type; |
|
2
|
|
|
|
|
4
|
|
|
2
|
|
|
|
|
17
|
|
5
|
|
|
|
|
|
|
|
6
|
|
|
|
|
|
|
sub new { |
7
|
0
|
|
|
0
|
|
|
my $class = shift; |
8
|
0
|
|
|
|
|
|
return bless {}, $class; |
9
|
|
|
|
|
|
|
} |
10
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
sub error { |
12
|
0
|
|
|
0
|
|
|
croak "typing error!"; |
13
|
|
|
|
|
|
|
} |
14
|
|
|
|
|
|
|
|
15
|
|
|
|
|
|
|
sub deref_type { |
16
|
0
|
|
|
0
|
|
|
my($self, $type) = @_; |
17
|
0
|
|
|
|
|
|
my $kind = $type->kind; |
18
|
|
|
|
|
|
|
|
19
|
0
|
0
|
|
|
|
|
if ($kind eq 'Fun') { |
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
20
|
0
|
|
|
|
|
|
my @new_args = (); |
21
|
0
|
|
|
|
|
|
for my $arg (@{$type->children->[0]}) { |
|
0
|
|
|
|
|
|
|
22
|
0
|
|
|
|
|
|
push(@new_args, $self->deref_type($arg)); |
23
|
|
|
|
|
|
|
} |
24
|
0
|
|
|
|
|
|
$type->children->[0] = \@new_args; |
25
|
0
|
|
|
|
|
|
$type->children->[1] = $self->deref_type($type->children->[1]); |
26
|
|
|
|
|
|
|
} |
27
|
|
|
|
|
|
|
elsif ($kind eq 'Tuple') { |
28
|
0
|
|
|
|
|
|
my @new_elems = (); |
29
|
0
|
|
|
|
|
|
for my $elem (@{$type->children->[0]}) { |
|
0
|
|
|
|
|
|
|
30
|
0
|
|
|
|
|
|
push(@new_elems, $self->deref_type($elem)); |
31
|
|
|
|
|
|
|
} |
32
|
0
|
|
|
|
|
|
$type->children->[0] = \@new_elems; |
33
|
|
|
|
|
|
|
} |
34
|
|
|
|
|
|
|
elsif ($kind eq 'Array') { |
35
|
0
|
|
|
|
|
|
$type->children->[0] = $self->deref_type($type->children->[0]); |
36
|
|
|
|
|
|
|
} |
37
|
|
|
|
|
|
|
elsif ($kind eq 'Var') { |
38
|
0
|
0
|
|
|
|
|
if ($type->children->[0]) { |
39
|
0
|
|
|
|
|
|
$type->children->[0] = $self->deref_type($type->children->[0]); |
40
|
0
|
|
|
|
|
|
return $type->children->[0]; |
41
|
|
|
|
|
|
|
} |
42
|
|
|
|
|
|
|
else { |
43
|
0
|
|
|
|
|
|
croak "This must not happen."; |
44
|
|
|
|
|
|
|
} |
45
|
|
|
|
|
|
|
} |
46
|
|
|
|
|
|
|
|
47
|
0
|
|
|
|
|
|
return $type; |
48
|
|
|
|
|
|
|
} |
49
|
|
|
|
|
|
|
|
50
|
|
|
|
|
|
|
sub deref_ident_type { |
51
|
0
|
|
|
0
|
|
|
my($self, $ident) = @_; |
52
|
0
|
|
|
|
|
|
return [$ident->[0], $self->deref_type($ident->[1])]; |
53
|
|
|
|
|
|
|
} |
54
|
|
|
|
|
|
|
|
55
|
|
|
|
|
|
|
sub deref_node { |
56
|
0
|
|
|
0
|
|
|
my($self, $node) = @_; |
57
|
0
|
|
|
|
|
|
my $kind = $node->kind; |
58
|
|
|
|
|
|
|
|
59
|
0
|
0
|
0
|
|
|
|
if ($kind eq 'Not' || $kind eq 'Neg' || $kind eq 'FNeg') { |
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
60
|
0
|
|
|
|
|
|
$node->children->[0] = $self->deref_node($node->children->[0]); |
61
|
|
|
|
|
|
|
} |
62
|
|
|
|
|
|
|
elsif ($kind eq 'Add' || $kind eq 'Sub' || $kind eq 'Eq' |
63
|
|
|
|
|
|
|
|| $kind eq 'LE' || $kind eq 'FAdd' || $kind eq 'FSub' |
64
|
|
|
|
|
|
|
|| $kind eq 'FMul' || $kind eq 'FDiv' || $kind eq 'Array' |
65
|
|
|
|
|
|
|
|| $kind eq 'Get') { |
66
|
0
|
|
|
|
|
|
$node->children->[0] = $self->deref_node($node->children->[0]); |
67
|
0
|
|
|
|
|
|
$node->children->[1] = $self->deref_node($node->children->[1]); |
68
|
|
|
|
|
|
|
} |
69
|
|
|
|
|
|
|
elsif ($kind eq 'If' || $kind eq 'Put') { |
70
|
0
|
|
|
|
|
|
$node->children->[0] = $self->deref_node($node->children->[0]); |
71
|
0
|
|
|
|
|
|
$node->children->[1] = $self->deref_node($node->children->[1]); |
72
|
0
|
|
|
|
|
|
$node->children->[2] = $self->deref_node($node->children->[2]); |
73
|
|
|
|
|
|
|
} |
74
|
|
|
|
|
|
|
elsif ($kind eq 'Let') { |
75
|
0
|
|
|
|
|
|
$node->children->[0] = $self->deref_ident_type($node->children->[0]); |
76
|
0
|
|
|
|
|
|
$node->children->[1] = $self->deref_node($node->children->[1]); |
77
|
0
|
|
|
|
|
|
$node->children->[2] = $self->deref_node($node->children->[2]); |
78
|
|
|
|
|
|
|
} |
79
|
|
|
|
|
|
|
elsif ($kind eq 'LetRec') { |
80
|
0
|
|
|
|
|
|
$node->children->[0]->{ident} = $self->deref_ident_type($node->children->[0]->{ident}); |
81
|
0
|
|
|
|
|
|
my @new_let_args = (); |
82
|
0
|
|
|
|
|
|
for my $let_arg (@{$node->children->[0]->{args}}) { |
|
0
|
|
|
|
|
|
|
83
|
0
|
|
|
|
|
|
push(@new_let_args, $self->deref_ident_type($let_arg)); |
84
|
|
|
|
|
|
|
} |
85
|
0
|
|
|
|
|
|
$node->children->[0]->{args} = \@new_let_args; |
86
|
0
|
|
|
|
|
|
$node->children->[0]->{body} = $self->deref_node($node->children->[0]->{body}); |
87
|
0
|
|
|
|
|
|
$node->children->[1] = $self->deref_node($node->children->[1]); |
88
|
|
|
|
|
|
|
} |
89
|
|
|
|
|
|
|
elsif ($kind eq 'App') { |
90
|
0
|
|
|
|
|
|
$node->children->[0] = $self->deref_node($node->children->[0]); |
91
|
0
|
|
|
|
|
|
my @new_app_args = (); |
92
|
0
|
|
|
|
|
|
for my $app_arg (@{$node->children->[1]}) { |
|
0
|
|
|
|
|
|
|
93
|
0
|
|
|
|
|
|
push(@new_app_args, $self->deref_node($app_arg)); |
94
|
|
|
|
|
|
|
} |
95
|
0
|
|
|
|
|
|
$node->children->[1] = \@new_app_args; |
96
|
|
|
|
|
|
|
} |
97
|
|
|
|
|
|
|
elsif ($kind eq 'Tuple') { |
98
|
0
|
|
|
|
|
|
my @new_elems = (); |
99
|
0
|
|
|
|
|
|
for my $elem (@{$node->children->[0]}) { |
|
0
|
|
|
|
|
|
|
100
|
0
|
|
|
|
|
|
push(@new_elems, $self->deref_node($elem)); |
101
|
|
|
|
|
|
|
} |
102
|
0
|
|
|
|
|
|
$node->children->[0] = \@new_elems; |
103
|
|
|
|
|
|
|
} |
104
|
|
|
|
|
|
|
elsif ($kind eq 'LetTuple') { |
105
|
0
|
|
|
|
|
|
my @new_elem_idents = (); |
106
|
0
|
|
|
|
|
|
for my $elem_ident (@{$node->children->[0]}) { |
|
0
|
|
|
|
|
|
|
107
|
0
|
|
|
|
|
|
push(@new_elem_idents, $self->deref_ident_type($elem_ident)); |
108
|
|
|
|
|
|
|
} |
109
|
0
|
|
|
|
|
|
$node->children->[0] = \@new_elem_idents; |
110
|
0
|
|
|
|
|
|
$node->children->[1] = $self->deref_node($node->children->[1]); |
111
|
0
|
|
|
|
|
|
$node->children->[2] = $self->deref_node($node->children->[2]); |
112
|
|
|
|
|
|
|
} |
113
|
|
|
|
|
|
|
|
114
|
0
|
|
|
|
|
|
return $node; |
115
|
|
|
|
|
|
|
} |
116
|
|
|
|
|
|
|
|
117
|
|
|
|
|
|
|
sub occur { |
118
|
0
|
|
|
0
|
|
|
my($self, $left_type, $right_type) = @_; |
119
|
|
|
|
|
|
|
|
120
|
0
|
0
|
0
|
|
|
|
if ($right_type->kind eq 'Fun') { |
|
|
0
|
0
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
121
|
0
|
|
|
|
|
|
for my $arg_type (@{$right_type->children->[0]}) { |
|
0
|
|
|
|
|
|
|
122
|
0
|
0
|
|
|
|
|
return 1 if $self->occur($left_type, $arg_type); |
123
|
|
|
|
|
|
|
} |
124
|
|
|
|
|
|
|
|
125
|
0
|
|
|
|
|
|
return $self->occur($left_type, $right_type->children->[1]); |
126
|
|
|
|
|
|
|
} |
127
|
|
|
|
|
|
|
elsif ($right_type->kind eq 'Tuple') { |
128
|
0
|
|
|
|
|
|
for my $elem_type (@{$right_type->children->[0]}) { |
|
0
|
|
|
|
|
|
|
129
|
0
|
0
|
|
|
|
|
return 1 if $self->occur($left_type, $elem_type); |
130
|
|
|
|
|
|
|
} |
131
|
|
|
|
|
|
|
|
132
|
0
|
|
|
|
|
|
return 0; |
133
|
|
|
|
|
|
|
} |
134
|
|
|
|
|
|
|
elsif ($right_type->kind eq 'Array') { |
135
|
0
|
|
|
|
|
|
return $self->occur($left_type, $right_type->children->[0]); |
136
|
|
|
|
|
|
|
} |
137
|
|
|
|
|
|
|
elsif ($right_type->kind eq 'Var' && $left_type == $right_type) { |
138
|
0
|
|
|
|
|
|
return 1; |
139
|
|
|
|
|
|
|
} |
140
|
|
|
|
|
|
|
elsif ($right_type->kind eq 'Var' && $right_type->children->[0]) { |
141
|
0
|
|
|
|
|
|
return $self->occur($left_type, $right_type->children->[0]); |
142
|
|
|
|
|
|
|
} |
143
|
|
|
|
|
|
|
else { |
144
|
0
|
|
|
|
|
|
return 0; |
145
|
|
|
|
|
|
|
} |
146
|
|
|
|
|
|
|
} |
147
|
|
|
|
|
|
|
|
148
|
|
|
|
|
|
|
sub unify { |
149
|
0
|
|
|
0
|
|
|
my($self, $left_type, $right_type) = @_; |
150
|
|
|
|
|
|
|
|
151
|
0
|
0
|
|
|
|
|
return if $left_type == $right_type; |
152
|
|
|
|
|
|
|
|
153
|
0
|
0
|
0
|
|
|
|
if (($left_type->kind eq 'Unit' && $right_type->kind eq 'Unit') |
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
154
|
|
|
|
|
|
|
|| ($left_type->kind eq 'Bool' && $right_type->kind eq 'Bool') |
155
|
|
|
|
|
|
|
|| ($left_type->kind eq 'Int' && $right_type->kind eq 'Int') |
156
|
|
|
|
|
|
|
|| ($left_type->kind eq 'Float' && $right_type->kind eq 'Float')) { |
157
|
|
|
|
|
|
|
} |
158
|
|
|
|
|
|
|
elsif ($left_type->kind eq 'Fun' && $right_type->kind eq 'Fun') { |
159
|
0
|
0
|
|
|
|
|
$self->error unless @{$left_type->children->[0]} == @{$right_type->children->[0]}; |
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
160
|
|
|
|
|
|
|
|
161
|
0
|
|
|
|
|
|
for my $index (0..$#{$left_type->children->[0]}) { |
|
0
|
|
|
|
|
|
|
162
|
0
|
|
|
|
|
|
$self->unify($left_type->children->[0]->[$index], |
163
|
|
|
|
|
|
|
$right_type->children->[0]->[$index]); |
164
|
|
|
|
|
|
|
} |
165
|
|
|
|
|
|
|
|
166
|
0
|
|
|
|
|
|
$self->unify($left_type->children->[1], $right_type->children->[1]); |
167
|
|
|
|
|
|
|
} |
168
|
|
|
|
|
|
|
elsif ($left_type->kind eq 'Tuple' && $right_type->kind eq 'Tuple') { |
169
|
0
|
0
|
|
|
|
|
$self->error unless @{$left_type->children->[0]} == @{$right_type->children->[0]}; |
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
170
|
|
|
|
|
|
|
|
171
|
0
|
|
|
|
|
|
for my $index (0..$#{$left_type->children->[0]}) { |
|
0
|
|
|
|
|
|
|
172
|
0
|
|
|
|
|
|
$self->unify($left_type->children->[0]->[$index], |
173
|
|
|
|
|
|
|
$right_type->children->[0]->[$index]); |
174
|
|
|
|
|
|
|
} |
175
|
|
|
|
|
|
|
} |
176
|
|
|
|
|
|
|
elsif ($left_type->kind eq 'Array' && $right_type->kind eq 'Array') { |
177
|
0
|
|
|
|
|
|
$self->unify($left_type->children->[0], $right_type->children->[0]); |
178
|
|
|
|
|
|
|
} |
179
|
|
|
|
|
|
|
elsif ($left_type->kind eq 'Var' && $right_type->kind eq 'Var' |
180
|
|
|
|
|
|
|
&& $left_type->children->[0] && $right_type->children->[0] |
181
|
|
|
|
|
|
|
&& $left_type->children->[0]->kind eq $right_type->children->[0]->kind) { |
182
|
|
|
|
|
|
|
} |
183
|
|
|
|
|
|
|
elsif ($left_type->kind eq 'Var' && $left_type->children->[0]) { |
184
|
0
|
|
|
|
|
|
$self->unify($left_type->children->[0], $right_type); |
185
|
|
|
|
|
|
|
} |
186
|
|
|
|
|
|
|
elsif ($right_type->kind eq 'Var' && $right_type->children->[0]) { |
187
|
0
|
|
|
|
|
|
$self->unify($left_type, $right_type->children->[0]); |
188
|
|
|
|
|
|
|
} |
189
|
|
|
|
|
|
|
elsif ($left_type->kind eq 'Var' && !$self->occur($left_type, $right_type)) { |
190
|
0
|
|
|
|
|
|
$left_type->children->[0] = $right_type; |
191
|
|
|
|
|
|
|
} |
192
|
|
|
|
|
|
|
elsif ($right_type->kind eq 'Var' && !$self->occur($right_type, $left_type)) { |
193
|
0
|
|
|
|
|
|
$right_type->children->[0] = $left_type; |
194
|
|
|
|
|
|
|
} |
195
|
|
|
|
|
|
|
else { |
196
|
0
|
|
|
|
|
|
$self->error; |
197
|
|
|
|
|
|
|
} |
198
|
|
|
|
|
|
|
|
199
|
0
|
|
|
|
|
|
return; |
200
|
|
|
|
|
|
|
} |
201
|
|
|
|
|
|
|
|
202
|
|
|
|
|
|
|
sub infer_rec { |
203
|
0
|
|
|
0
|
|
|
my($self, $node, %env) = @_; |
204
|
0
|
|
|
|
|
|
my $kind = $node->kind; |
205
|
|
|
|
|
|
|
|
206
|
0
|
0
|
0
|
|
|
|
if ($kind eq 'Unit') { |
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
0
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
207
|
0
|
|
|
|
|
|
return Type_Unit(); |
208
|
|
|
|
|
|
|
} |
209
|
|
|
|
|
|
|
elsif ($kind eq 'Bool') { |
210
|
0
|
|
|
|
|
|
return Type_Bool(); |
211
|
|
|
|
|
|
|
} |
212
|
|
|
|
|
|
|
elsif ($kind eq 'Int') { |
213
|
0
|
|
|
|
|
|
return Type_Int(); |
214
|
|
|
|
|
|
|
} |
215
|
|
|
|
|
|
|
elsif ($kind eq 'Float') { |
216
|
0
|
|
|
|
|
|
return Type_Float(); |
217
|
|
|
|
|
|
|
} |
218
|
|
|
|
|
|
|
elsif ($kind eq 'Not') { |
219
|
0
|
|
|
|
|
|
$self->unify(Type_Bool, $self->infer_rec($node->children->[0], %env)); |
220
|
|
|
|
|
|
|
|
221
|
0
|
|
|
|
|
|
return Type_Bool(); |
222
|
|
|
|
|
|
|
} |
223
|
|
|
|
|
|
|
elsif ($kind eq 'Neg') { |
224
|
0
|
|
|
|
|
|
$self->unify(Type_Int, $self->infer_rec($node->children->[0], %env)); |
225
|
|
|
|
|
|
|
|
226
|
0
|
|
|
|
|
|
return Type_Int(); |
227
|
|
|
|
|
|
|
} |
228
|
|
|
|
|
|
|
elsif ($kind eq 'Add' || $kind eq 'Sub') { |
229
|
0
|
|
|
|
|
|
$self->unify(Type_Int, $self->infer_rec($node->children->[0], %env)); |
230
|
0
|
|
|
|
|
|
$self->unify(Type_Int, $self->infer_rec($node->children->[1], %env)); |
231
|
|
|
|
|
|
|
|
232
|
0
|
|
|
|
|
|
return Type_Int(); |
233
|
|
|
|
|
|
|
} |
234
|
|
|
|
|
|
|
elsif ($kind eq 'FNeg') { |
235
|
0
|
|
|
|
|
|
$self->unify(Type_Float, $self->infer_rec($node->children->[0], %env)); |
236
|
|
|
|
|
|
|
|
237
|
0
|
|
|
|
|
|
return Type_Float(); |
238
|
|
|
|
|
|
|
} |
239
|
|
|
|
|
|
|
elsif ($kind eq 'FAdd' || $node->kind eq 'FSub' |
240
|
|
|
|
|
|
|
|| $kind eq 'FMul' || $kind eq 'FDiv') { |
241
|
0
|
|
|
|
|
|
$self->unify(Type_Float, $self->infer_rec($node->children->[0], %env)); |
242
|
0
|
|
|
|
|
|
$self->unify(Type_Float, $self->infer_rec($node->children->[1], %env)); |
243
|
|
|
|
|
|
|
|
244
|
0
|
|
|
|
|
|
return Type_Float(); |
245
|
|
|
|
|
|
|
} |
246
|
|
|
|
|
|
|
elsif ($kind eq 'Eq' || $kind eq 'LE') { |
247
|
0
|
|
|
|
|
|
$self->unify($self->infer_rec($node->children->[0], %env), |
248
|
|
|
|
|
|
|
$self->infer_rec($node->children->[1], %env)); |
249
|
|
|
|
|
|
|
|
250
|
0
|
|
|
|
|
|
return Type_Bool(); |
251
|
|
|
|
|
|
|
} |
252
|
|
|
|
|
|
|
elsif ($kind eq 'If') { |
253
|
0
|
|
|
|
|
|
$self->unify($self->infer_rec($node->children->[0], %env), |
254
|
|
|
|
|
|
|
Type_Bool()); |
255
|
0
|
|
|
|
|
|
my $stat_type = $self->infer_rec($node->children->[1], %env); |
256
|
0
|
|
|
|
|
|
$self->unify($stat_type, $self->infer_rec($node->children->[2], %env)); |
257
|
|
|
|
|
|
|
|
258
|
0
|
|
|
|
|
|
return $stat_type; |
259
|
|
|
|
|
|
|
} |
260
|
|
|
|
|
|
|
elsif ($kind eq 'Let') { |
261
|
0
|
|
|
|
|
|
$self->unify($node->children->[0]->[1], |
262
|
|
|
|
|
|
|
$self->infer_rec($node->children->[1], %env)); |
263
|
0
|
|
|
|
|
|
$env{$node->children->[0]->[0]} = $node->children->[0]->[1]; |
264
|
|
|
|
|
|
|
|
265
|
0
|
|
|
|
|
|
return $self->infer_rec($node->children->[2], %env); |
266
|
|
|
|
|
|
|
} |
267
|
|
|
|
|
|
|
elsif ($kind eq 'Var') { |
268
|
0
|
|
|
|
|
|
my $ident_name = $node->children->[0]; |
269
|
|
|
|
|
|
|
|
270
|
0
|
0
|
|
|
|
|
if (exists $env{$ident_name}) { |
271
|
0
|
|
|
|
|
|
return $env{$ident_name}; |
272
|
|
|
|
|
|
|
} |
273
|
|
|
|
|
|
|
else { |
274
|
0
|
|
|
|
|
|
$self->error; |
275
|
|
|
|
|
|
|
} |
276
|
|
|
|
|
|
|
} |
277
|
|
|
|
|
|
|
elsif ($kind eq 'LetRec') { |
278
|
0
|
|
|
|
|
|
my $ident = $node->children->[0]->{ident}; |
279
|
0
|
|
|
|
|
|
my $let_args = $node->children->[0]->{args}; |
280
|
0
|
|
|
|
|
|
my $body = $node->children->[0]->{body}; |
281
|
0
|
|
|
|
|
|
$env{$ident->[0]} = $ident->[1]; |
282
|
0
|
|
|
|
|
|
my @arg_types = (); |
283
|
0
|
|
|
|
|
|
my %tmp_env = %env; |
284
|
|
|
|
|
|
|
|
285
|
0
|
|
|
|
|
|
for my $arg (@$let_args) { |
286
|
0
|
|
|
|
|
|
push(@arg_types, $arg->[1]); |
287
|
0
|
|
|
|
|
|
$tmp_env{$arg->[0]} = $arg->[1]; |
288
|
|
|
|
|
|
|
} |
289
|
|
|
|
|
|
|
|
290
|
0
|
|
|
|
|
|
$self->unify($ident->[1], |
291
|
|
|
|
|
|
|
Type_Fun(\@arg_types, $self->infer_rec($body, %tmp_env))); |
292
|
|
|
|
|
|
|
|
293
|
0
|
|
|
|
|
|
return $self->infer_rec($node->children->[1], %env); |
294
|
|
|
|
|
|
|
} |
295
|
|
|
|
|
|
|
elsif ($kind eq 'App') { |
296
|
0
|
|
|
|
|
|
my $app_ident_type = $self->infer_rec($node->children->[0], %env); |
297
|
0
|
|
|
|
|
|
my $app_args = $node->children->[1]; |
298
|
0
|
|
|
|
|
|
my @arg_types = (); |
299
|
|
|
|
|
|
|
|
300
|
0
|
|
|
|
|
|
for my $arg (@$app_args) { |
301
|
0
|
|
|
|
|
|
push(@arg_types, $self->infer_rec($arg, %env)); |
302
|
|
|
|
|
|
|
} |
303
|
|
|
|
|
|
|
|
304
|
0
|
|
|
|
|
|
my $tmp_type = Type_Var(); |
305
|
0
|
|
|
|
|
|
$self->unify($app_ident_type, Type_Fun(\@arg_types, $tmp_type)); |
306
|
|
|
|
|
|
|
|
307
|
0
|
|
|
|
|
|
return $tmp_type; |
308
|
|
|
|
|
|
|
} |
309
|
|
|
|
|
|
|
elsif ($kind eq 'Tuple') { |
310
|
0
|
|
|
|
|
|
my @elem_types = (); |
311
|
|
|
|
|
|
|
|
312
|
0
|
|
|
|
|
|
for my $elem (@{$node->children->[0]}) { |
|
0
|
|
|
|
|
|
|
313
|
0
|
|
|
|
|
|
push(@elem_types, $self->infer_rec($elem, %env)); |
314
|
|
|
|
|
|
|
} |
315
|
|
|
|
|
|
|
|
316
|
0
|
|
|
|
|
|
return Type_Tuple(\@elem_types); |
317
|
|
|
|
|
|
|
} |
318
|
|
|
|
|
|
|
elsif ($kind eq 'LetTuple') { |
319
|
0
|
|
|
|
|
|
my @elem_types = (); |
320
|
0
|
|
|
|
|
|
my %tmp_env = %env; |
321
|
|
|
|
|
|
|
|
322
|
0
|
|
|
|
|
|
for my $elem_ident (@{$node->children->[0]}) { |
|
0
|
|
|
|
|
|
|
323
|
0
|
|
|
|
|
|
push(@elem_types, $elem_ident->[1]); |
324
|
0
|
|
|
|
|
|
$tmp_env{$elem_ident->[0]} = $elem_ident->[1]; |
325
|
|
|
|
|
|
|
} |
326
|
0
|
|
|
|
|
|
$self->unify(Type_Tuple(\@elem_types), |
327
|
|
|
|
|
|
|
$self->infer_rec($node->children->[1], %env)); |
328
|
|
|
|
|
|
|
|
329
|
0
|
|
|
|
|
|
return $self->infer_rec($node->children->[2], %tmp_env); |
330
|
|
|
|
|
|
|
} |
331
|
|
|
|
|
|
|
elsif ($kind eq 'Array') { |
332
|
0
|
|
|
|
|
|
$self->unify($self->infer_rec($node->children->[0], %env), Type_Int()); |
333
|
|
|
|
|
|
|
|
334
|
0
|
|
|
|
|
|
return Type_Array($self->infer_rec($node->children->[1], %env)); |
335
|
|
|
|
|
|
|
} |
336
|
|
|
|
|
|
|
elsif ($kind eq 'Get') { |
337
|
0
|
|
|
|
|
|
my $tmp_type = Type_Var(); |
338
|
|
|
|
|
|
|
|
339
|
0
|
|
|
|
|
|
$self->unify(Type_Array($tmp_type), |
340
|
|
|
|
|
|
|
$self->infer_rec($node->children->[0], %env)); |
341
|
0
|
|
|
|
|
|
$self->unify(Type_Int(), |
342
|
|
|
|
|
|
|
$self->infer_rec($node->children->[1], %env)); |
343
|
|
|
|
|
|
|
|
344
|
0
|
|
|
|
|
|
return $tmp_type; |
345
|
|
|
|
|
|
|
} |
346
|
|
|
|
|
|
|
elsif ($kind eq 'Put') { |
347
|
0
|
|
|
|
|
|
my $tmp_type = $self->infer_rec($node->children->[2], %env); |
348
|
|
|
|
|
|
|
|
349
|
0
|
|
|
|
|
|
$self->unify(Type_Array($tmp_type), |
350
|
|
|
|
|
|
|
$self->infer_rec($node->children->[0], %env)); |
351
|
0
|
|
|
|
|
|
$self->unify(Type_Int(), |
352
|
|
|
|
|
|
|
$self->infer_rec($node->children->[1], %env)); |
353
|
|
|
|
|
|
|
|
354
|
0
|
|
|
|
|
|
return Type_Unit(); |
355
|
|
|
|
|
|
|
} |
356
|
|
|
|
|
|
|
else { |
357
|
0
|
|
|
|
|
|
croak "This must not happen."; |
358
|
|
|
|
|
|
|
} |
359
|
|
|
|
|
|
|
} |
360
|
|
|
|
|
|
|
|
361
|
|
|
|
|
|
|
sub infer { |
362
|
|
|
|
|
|
|
my($self, $root_node, %type_env) = @_; |
363
|
|
|
|
|
|
|
my $top_level_type = $self->infer_rec($root_node, %type_env); |
364
|
|
|
|
|
|
|
|
365
|
|
|
|
|
|
|
$self->unify($top_level_type, Type_Unit()); |
366
|
|
|
|
|
|
|
$self->deref_node($root_node); |
367
|
|
|
|
|
|
|
|
368
|
|
|
|
|
|
|
return; |
369
|
|
|
|
|
|
|
} |
370
|
|
|
|
|
|
|
|
371
|
|
|
|
|
|
|
1; |