code.c 11.7 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, int root_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
40
                thunk->_args[basethunk->desc->arity + i] 
                        = create_thunk(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a);
41
42
43
            }

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

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

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

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

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

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

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
90
91
92
            if (var->base.local_type == VAR_LOCAL) 
            {
                Thunk* basethunk = eval(local(frame_ptr, var->index));
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
93

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
94
95
96
                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
97

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
                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
                        push_a(create_thunk(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a));
                    } 
                    
                    expr = ((FunEntry*) slice)->body;
                    frame_ptr = new_frame_ptr;
                    continue;                    
                }
                else
                {
                    Thunk* thunk = updateF(get_dst(root_frame_ptr), slice);
135

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

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
138
139
140
                    for (int i = 0; i < basethunk->desc->arity; i++) {
                        thunk->_args[i] = basethunk->_args[i];
                    }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
141

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

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

164
                    ((PrimEntry*) slice)->exec(root_frame_ptr);
165
                    destroy_stack_frame(root_frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
166
167
                    return;
                }
168
                else if (slice->type == FT_FUN) {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
169

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
170
                    int new_frame_ptr = stack_top_a;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
171

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

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

                    for (int i = 0; i < expr->nr_args; i++) {
195
196
                        thunk->_args[i] 
                                = create_thunk(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
197
198
                    }
                    
199
200
                    set_return(root_frame_ptr, thunk);
                    destroy_stack_frame(root_frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
201
                    return;                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
202
                }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
203
204
            }
            break;
205
206
207
        }            
        case CT_VAR:
            if (expr->local_type == VAR_LOCAL) {
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
236
237
238
239
240
241
                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);
                }                
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
                
                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
266
267
        case CT_SELECT:
        {
268
            push_a(NULL);
269
            exec(((SelectEntry*) expr)->expr, frame_ptr, stack_top_a);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
270
            Thunk* pattern = eval(pop_a());
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
271

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
272
273
274
            assert(is_hnf(pattern));
            assert(pattern->desc->type == FT_ADT);            
            
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
275
276
277
278
            bool handled = false;
            
            for (int i = 0; i < expr->nr_cases; i++) {
                SelectCaseEntry* caseEntry = &((SelectEntry*) expr)->cases[i];
279
                
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
280
281
282
283
284
285
286
                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]);
287
                    }                  
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
288
289
290
291
292
293
294
295
296
297
                }
                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
298
299
            }

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
300
301
302
303
304
305
306
307
308
309
            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
310

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