code.c 11.3 KB
Newer Older
1
2
#include <stdio.h>
#include <stdlib.h>
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
3
#include <stdbool.h>
4

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
5
#include "debug.h"
6
#include "code.h"
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
7
#include "mem.h"
8
9
#include "desc.h"

10
struct Thunk* create_thunk(Code* expr, int frame_ptr)
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
11
{
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
12
    assert(expr != NULL);
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    
    switch (expr->type) {
    case CT_APP:
    {
        // TODO: check over application
        // TODO: enforce strictness in ADT/Record

        VarEntry* var = &((AppEntry*) expr)->var;

        if (var->base.local_type == VAR_LOCAL) 
        {
            Thunk* basethunk = eval(local(frame_ptr, var->index));

            Desc* slice =
                    get_slice(basethunk->desc->type == FT_SLICE ?
                              ((SliceEntry*) basethunk->desc)->forward_ptr : basethunk->desc, basethunk->desc->arity + expr->nr_args);

30
            Thunk* thunk = updateF(NULL, slice);
31
32
33
34
35
36
37
38

            assert(thunk->desc->arity == basethunk->desc->arity + expr->nr_args);            

            for (int i = 0; i < basethunk->desc->arity; i++) {
                thunk->_args[i] = basethunk->_args[i];
            }

            for (int i = 0; i < expr->nr_args; i++) {
39
                thunk->_args[basethunk->desc->arity + i] 
40
                        = create_thunk(((AppEntry*) expr)->args[i], frame_ptr);
41
42
            }

43
            return thunk;
44
45
46
        }
        else
        {
47
            Thunk* thunk = updateF(NULL, get_slice(var->f, expr->nr_args));
48
49
50
51

            assert(thunk->desc->arity == expr->nr_args);

            for (int i = 0; i < expr->nr_args; i++) {
52
                thunk->_args[i] = create_thunk(((AppEntry*) expr)->args[i], frame_ptr);
53
54
            }

55
            return thunk;                    
56
        }
57
58
59
    }        
    case CT_VAR:
        if (expr->local_type == VAR_LOCAL) {
60
            return forward_to(NULL, local(frame_ptr, ((VarEntry*) expr)->index));
61
62
63
64
65
        }else{
            return updateF(NULL, get_slice(((VarEntry*) expr)->f, 0));
        }
    case CT_LIT:
        return updateT(NULL, &((LitEntry*) expr)->thunk);        
66
67
    }
}
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
68

69
70
void exec(Code* expr, int frame_ptr, int root_frame_ptr)
{
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
71
72
    while(1)
    {
73
        assert(expr != NULL);
74
75
        assert(stack_top_a < STACK_SIZE_A);
        
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
76
77
        switch (expr->type) {
        case CT_APP:
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
78
        {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
79
80
            // TODO: check over application
            // TODO: enforce strictness in ADT/Record
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
81

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
82
            VarEntry* var = &((AppEntry*) expr)->var;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
83

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
84
85
86
            if (var->base.local_type == VAR_LOCAL) 
            {
                Thunk* basethunk = eval(local(frame_ptr, var->index));
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
87

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
88
89
90
                Desc* slice =
                        get_slice(basethunk->desc->type == FT_SLICE ?
                                  ((SliceEntry*) basethunk->desc)->forward_ptr : basethunk->desc, basethunk->desc->arity + expr->nr_args);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
91

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
                if(slice->type == FT_PRIM)
                {
                    for (int i = 0; i < basethunk->desc->arity; i++) {
                        // TODO: eval
                        push_a(basethunk->_args[i]);
                    }
                    
                    for (int i = 0; i < expr->nr_args; i++) {
                        push_a(NULL);
                        exec(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a);
                    } 
                    
                    ((PrimEntry*) slice)->exec(root_frame_ptr);
                    destroy_stack_frame(root_frame_ptr);
                    return;                    
                }
                else if(slice->type == FT_FUN)
                {
                    int new_frame_ptr = stack_top_a;                    
                    
                    for (int i = 0; i < basethunk->desc->arity; i++) {
                        // TODO: eval
                        push_a(basethunk->_args[i]);
                    }
                    
                    for (int i = 0; i < expr->nr_args; i++) {
                        // TODO: eval
119
                        push_a(create_thunk(((AppEntry*) expr)->args[i], frame_ptr));
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
120
121
122
123
124
125
126
127
128
                    } 
                    
                    expr = ((FunEntry*) slice)->body;
                    frame_ptr = new_frame_ptr;
                    continue;                    
                }
                else
                {
                    Thunk* thunk = updateF(get_dst(root_frame_ptr), slice);
129

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
130
                    assert(thunk->desc->arity == basethunk->desc->arity + expr->nr_args);            
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
131

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
132
133
134
                    for (int i = 0; i < basethunk->desc->arity; i++) {
                        thunk->_args[i] = basethunk->_args[i];
                    }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
135

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
136
137
                    for (int i = 0; i < expr->nr_args; i++) {
                        thunk->_args[basethunk->desc->arity + i] 
138
                                = create_thunk(((AppEntry*) expr)->args[i], frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
139
140
141
142
143
                    }
                    
                    set_return(root_frame_ptr, thunk);
                    destroy_stack_frame(root_frame_ptr);
                    return;                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
144
145
                }
            }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
146
147
148
            else
            {
                Desc* slice = get_slice(var->f, expr->nr_args);
149
                
150
                if (slice->type == FT_PRIM) {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
151
152
153
                    Thunk args[expr->nr_args];

                    for (int i = 0; i < expr->nr_args; i++) {
154
                        push_a(&args[i]);                        
155
                        exec(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
156
157
                    }

158
                    ((PrimEntry*) slice)->exec(root_frame_ptr);
159
                    destroy_stack_frame(root_frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
160
161
                    return;
                }
162
                else if (slice->type == FT_FUN) {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
163

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
164
                    int new_frame_ptr = stack_top_a;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
165

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
166
                    for (int i = 0; i < expr->nr_args; i++) {
167
                        
168
169
                        if(is_strict_fun_arg((FunEntry*) slice, i))
                        {
170
                            push_a(NULL);
171
172
173
174
                            exec(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a);
                        }
                        else
                        {
175
                            push_a(create_thunk(((AppEntry*) expr)->args[i], frame_ptr));  
176
                        }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
177
                    }
178
                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
179
180
181
182
183
                    expr = ((FunEntry*) slice)->body;
                    frame_ptr = new_frame_ptr;
                    continue;
                }
                else {
184
                    Thunk* thunk = updateF(get_dst(root_frame_ptr), slice);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
185
186
187
188

                    assert(thunk->desc->arity == expr->nr_args);

                    for (int i = 0; i < expr->nr_args; i++) {
189
                        thunk->_args[i] 
190
                                = create_thunk(((AppEntry*) expr)->args[i], frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
191
192
                    }
                    
193
194
                    set_return(root_frame_ptr, thunk);
                    destroy_stack_frame(root_frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
195
                    return;                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
196
                }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
197
198
            }
            break;
199
200
201
        }            
        case CT_VAR:
            if (expr->local_type == VAR_LOCAL) {
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
                Thunk* thunk = local(frame_ptr, ((VarEntry*) expr)->index);
                                
                while (thunk->desc == (Desc*) __FORWARD_PTR__) {
                    thunk = thunk->_forward_ptr;
                }

                forward_to(get_dst(root_frame_ptr), thunk);
                set_return(root_frame_ptr, thunk);
                
                if (thunk->desc->type == FT_FUN) {
                    
                    // Destroy stack frame before eval, it is not needed any more
                    // Greatly reduces stack usage
                    destroy_stack_frame(root_frame_ptr);                    
                    frame_ptr = stack_top_a;
                    // Here frame_ptr == root_frame_ptr
                    
                    for (int i = 0; i < thunk->desc->arity; i++) {
                        // TODO: handle strictness
                        push_a(thunk->_args[i]);
                    }
                    
                    expr = ((FunEntry*) thunk->desc)->body;
                    continue;
                }
                else if(thunk->desc->type == FT_PRIM) {

                    for (int i = 0; i < thunk->desc->arity; i++) {
                        // TODO: handle strictness
                        push_a(thunk->_args[i]);
                    }

                    ((PrimEntry*) thunk->desc)->exec(root_frame_ptr);
                }                
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
                
                destroy_stack_frame(root_frame_ptr);
                return;
            }else{
                // Safe to destroy, the next call has no arguments
                destroy_stack_frame(root_frame_ptr);
                
                Desc* slice = get_slice(((VarEntry*) expr)->f, 0);
                
                if(slice->type == FT_FUN)
                {
                    expr = ((FunEntry*)slice)->body;
                    continue;
                }
                else
                {                    
                    set_return(root_frame_ptr, updateF(get_dst(root_frame_ptr), slice));
                    return;
                }
            }
        case CT_LIT:
            set_return(root_frame_ptr, updateT(get_dst(root_frame_ptr), &((LitEntry*) expr)->thunk));
            destroy_stack_frame(root_frame_ptr);
            return;               
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
260
261
        case CT_SELECT:
        {
262
            push_a(NULL);
263
            exec(((SelectEntry*) expr)->expr, frame_ptr, stack_top_a);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
264
            Thunk* pattern = eval(pop_a());
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
265

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
266
267
268
            assert(is_hnf(pattern));
            assert(pattern->desc->type == FT_ADT);            
            
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
269
270
271
272
            bool handled = false;
            
            for (int i = 0; i < expr->nr_cases; i++) {
                SelectCaseEntry* caseEntry = &((SelectEntry*) expr)->cases[i];
273
                
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
274
275
276
277
278
279
280
                if (caseEntry->type == SC_CONS) {
                    // Pattern match
                    if ((Desc*) caseEntry->cons != pattern->desc) continue;

                    // Put the constructor arguments to the stack if matches
                    for (int i = 0; i < pattern->desc->arity; i++) {
                        push_a(pattern->_args[i]);
281
                    }                  
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
282
283
284
285
286
287
288
289
290
291
                }
                else if (caseEntry->type == SC_LIT) {
                    printf("Exec: Unhandled entry type in CT_SELECT (SC_LIT)");
                    exit(-1);
                }
                
                // must be SC_DEFAULT now
                handled = true;
                expr = caseEntry->body;
                break;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
292
293
            }

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
294
295
296
297
298
299
300
301
302
303
            if(handled) continue;
            
            printf("Exec: no select cases matches");
            print(pattern, false);
            exit(-1);
        }
        case CT_IF:
        {        
            Thunk tmp;
            tmp.desc = (Desc*) __BOOL__;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
304

305
            push_a(&tmp);
306
            exec(((IfEntry*) expr)->cond, frame_ptr, stack_top_a);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
307
            Thunk* cond = eval(pop_a());
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
308
            
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
309
310
311
312
313
314
315
316
            if (readB(cond)) {
                expr = ((IfEntry*) expr)->texpr;
                continue;                
            }
            else {
                expr = ((IfEntry*) expr)->fexpr;
                continue;     
            }
317
        }     
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
318
319
320
        default:
            printf("Exec: Unhandled CODE type");
            exit(-1);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
321
        }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
322
    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
323
    }
324
}