code.c 11.6 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
    
    switch (expr->type) {
    case CT_APP:
    {
        // TODO: check over application
        // TODO: enforce strictness in ADT/Record

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
20
        if (expr->dyn_app) 
21
        {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
22
23
            Thunk* basethunk = local(frame_ptr, ((AppEntry*)expr)->var.index);
            if(!((AppEntry*)expr)->var.base.strict) basethunk = eval(basethunk);
24
            
25
26
27
28
            Desc* slice =
                    get_slice(basethunk->desc->type == FT_SLICE ?
                              ((SliceEntry*) basethunk->desc)->forward_ptr : basethunk->desc, basethunk->desc->arity + expr->nr_args);

29
            Thunk* thunk = createF(slice);
30
31
32
33
34
35
36
37

            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++) {
38
                thunk->_args[basethunk->desc->arity + i] 
39
                        = create_thunk(((AppEntry*) expr)->args[i], frame_ptr);
40
41
            }

42
            return thunk;
43
44
45
        }
        else
        {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
46
            Thunk* thunk = createF(((AppEntry*) expr)->f);
47
48
49
50

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

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

54
            return thunk;                    
55
        }
56
57
    }        
    case CT_VAR:
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
58
59
60
        return local(frame_ptr, ((VarEntry*) expr)->index);
    case CT_THUNK:
        return &((ThunkEntry*) expr)->thunk;        
61
62
    }
}
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
63

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

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
77
            if (expr->dyn_app)
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
78
            {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
79
80
                Thunk* basethunk = local(frame_ptr, ((AppEntry*)expr)->var.index);
                if(!((AppEntry*)expr)->var.base.strict) basethunk = eval(basethunk);
81
                
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
82
83
84
                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
85

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
86
87
88
                if(slice->type == FT_PRIM)
                {
                    for (int i = 0; i < basethunk->desc->arity; i++) {
89
                        push_a(eval(basethunk->_args[i]));
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
90
91
92
93
94
95
96
97
98
99
100
101
102
103
                    }
                    
                    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;                    
104
                    int argmask = 1;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
105
106
                    
                    for (int i = 0; i < basethunk->desc->arity; i++) {
107
                        
108
                        if(((FunEntry*) slice)->strictness & argmask)
109
110
111
112
113
114
115
                        {
                            push_a(eval(basethunk->_args[i]));
                        }
                        else
                        {
                            push_a(basethunk->_args[i]);
                        }
116
117
                        
                        argmask <<= 1;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
118
119
120
                    }
                    
                    for (int i = 0; i < expr->nr_args; i++) {
121
                        
122
                        if(((FunEntry*) slice)->strictness & argmask)
123
124
125
126
127
128
129
130
                        {
                            push_a(NULL);
                            exec(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a);
                        }
                        else
                        {
                            push_a(create_thunk(((AppEntry*) expr)->args[i], frame_ptr));
                        }
131
132
                        
                        argmask <<= 1;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
133
134
135
136
137
138
139
140
141
                    } 
                    
                    expr = ((FunEntry*) slice)->body;
                    frame_ptr = new_frame_ptr;
                    continue;                    
                }
                else
                {
                    Thunk* thunk = updateF(get_dst(root_frame_ptr), slice);
142

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

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
145
146
147
                    for (int i = 0; i < basethunk->desc->arity; i++) {
                        thunk->_args[i] = basethunk->_args[i];
                    }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
148

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
149
150
                    for (int i = 0; i < expr->nr_args; i++) {
                        thunk->_args[basethunk->desc->arity + i] 
151
                                = create_thunk(((AppEntry*) expr)->args[i], frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
152
153
154
155
156
                    }
                    
                    set_return(root_frame_ptr, thunk);
                    destroy_stack_frame(root_frame_ptr);
                    return;                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
157
158
                }
            }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
159
160
            else
            {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
161
                Desc* slice = ((AppEntry*) expr)->f;
162
                
163
                if (slice->type == FT_PRIM) {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
164
165
166
                    Thunk args[expr->nr_args];

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

171
                    ((PrimEntry*) slice)->exec(root_frame_ptr);
172
                    destroy_stack_frame(root_frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
173
174
                    return;
                }
175
                else if (slice->type == FT_FUN) {
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
176

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
177
                    int new_frame_ptr = stack_top_a;
178
179
                    int argmask = 1;
                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
180
                    for (int i = 0; i < expr->nr_args; i++) {
181
                        
182
                        if(((FunEntry*) slice)->strictness & argmask)
183
                        {
184
                            push_a(NULL);
185
186
187
188
                            exec(((AppEntry*) expr)->args[i], frame_ptr, stack_top_a);
                        }
                        else
                        {
189
                            push_a(create_thunk(((AppEntry*) expr)->args[i], frame_ptr));  
190
                        }
191
192
                        
                        argmask <<= 1;
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
193
                    }
194
                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
195
196
197
198
199
                    expr = ((FunEntry*) slice)->body;
                    frame_ptr = new_frame_ptr;
                    continue;
                }
                else {
200
                    Thunk* thunk = updateF(get_dst(root_frame_ptr), slice);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
201
202
203
204

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

                    for (int i = 0; i < expr->nr_args; i++) {
205
                        thunk->_args[i] 
206
                                = create_thunk(((AppEntry*) expr)->args[i], frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
207
208
                    }
                    
209
210
                    set_return(root_frame_ptr, thunk);
                    destroy_stack_frame(root_frame_ptr);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
211
                    return;                    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
212
                }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
213
214
            }
            break;
215
216
        }            
        case CT_VAR:
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
217
218
219
220
221
222
        {
            Thunk* thunk = local(frame_ptr, ((VarEntry*) expr)->index);

            if(((VarEntry*) expr)->base.strict)
            {
                assert(is_hnf(thunk));
223
224

                set_return(root_frame_ptr, thunk);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
225
226
227
                destroy_stack_frame(root_frame_ptr);
                return;                    
            }
228

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
            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

                int argmask = 1;
245

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
246
247
248
249
                for (int i = 0; i < thunk->desc->arity; i++) {

                    if(((FunEntry*) thunk->desc)->strictness & argmask)
                    {
250
                        push_a(eval(thunk->_args[i]));
251
                    }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
252
253
254
255
                    else
                    {
                        push_a(thunk->_args[i]);
                    }
256

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
257
                    argmask <<= 1;
258
                }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
259
260
261

                expr = ((FunEntry*) thunk->desc)->body;
                continue;
262
            }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
            else if(thunk->desc->type == FT_PRIM) {

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

                ((PrimEntry*) thunk->desc)->exec(root_frame_ptr);
            }                

            destroy_stack_frame(root_frame_ptr);
            return;
        }
        case CT_THUNK:
        {
            // TODO: set forward
            set_return(root_frame_ptr, &((ThunkEntry*) expr)->thunk);
279
280
            destroy_stack_frame(root_frame_ptr);
            return;               
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
281
        }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
282
283
        case CT_SELECT:
        {
284
            push_a(NULL);
285
            exec(((SelectEntry*) expr)->expr, frame_ptr, stack_top_a);
286
            Thunk* pattern = pop_a();
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
287

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
288
289
290
            assert(is_hnf(pattern));
            assert(pattern->desc->type == FT_ADT);            
            
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
291
292
293
294
            bool handled = false;
            
            for (int i = 0; i < expr->nr_cases; i++) {
                SelectCaseEntry* caseEntry = &((SelectEntry*) expr)->cases[i];
295
                
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
296
297
298
299
300
301
302
                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]);
303
                    }                  
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
304
305
306
307
308
309
310
311
312
313
                }
                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
314
315
            }

Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
316
317
318
319
320
321
322
323
324
325
            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
326

327
            push_a(&tmp);
328
            exec(((IfEntry*) expr)->cond, frame_ptr, stack_top_a);
329
            Thunk* cond = pop_a();
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
330
            
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
331
332
333
334
335
336
337
338
            if (readB(cond)) {
                expr = ((IfEntry*) expr)->texpr;
                continue;                
            }
            else {
                expr = ((IfEntry*) expr)->fexpr;
                continue;     
            }
339
        }     
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
340
341
342
        default:
            printf("Exec: Unhandled CODE type");
            exit(-1);
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
343
        }
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
344
    
Laszlo Domoszlai's avatar
Laszlo Domoszlai committed
345
    }
346
}