1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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
|
// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
// SPDX-License-Identifier: MIT
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <schedule.h>
#include <reduce.h>
#include <lib/pqueue.h>
#include <log.h>
#include <parse.h>
#include <map.h>
// queue of beta-redexes: ([X], Y)
static struct pqueue *queue;
static pqueue_pri_t get_pri(void *a)
{
struct term *term = a;
return term->priority;
}
static void set_pri(void *a, pqueue_pri_t pri)
{
struct term *term = a;
term->priority = pri;
}
static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr)
{
return next < curr;
}
static size_t get_pos(void *a)
{
struct term *term = a;
return term->position;
}
static void set_pos(void *a, size_t position)
{
struct term *term = a;
term->position = position;
}
// skewed random number generator
// prefers smaller numbers
static size_t choose_position(void)
{
size_t size = pqueue_size(queue);
return size - (size_t)sqrt(((size_t)rand() % (size_t)pow(size, 2)));
}
static pqueue_pri_t calculate_priority(struct term *term)
{
// TODO: Try different formulas (hyperfine)
return (parse_get_max_depth() - term->depth + 1) * term->refs;
}
void schedule_add(struct term *term)
{
if (!term_is_beta_redex(term))
return;
set_pri(term, calculate_priority(term));
pqueue_insert(queue, term);
}
void schedule_remove(struct term *term)
{
if (!pqueue_size(queue) || !term_is_beta_redex(term))
return;
int error = pqueue_remove(queue, term);
assert(!error);
}
void schedule(void)
{
while (pqueue_size(queue)) {
debug("queue size: %zu\n", pqueue_size(queue));
map_dump(map_all_terms(), 1);
// TODO: check finished programs
size_t position = choose_position();
struct term *term = pqueue_pop_at(queue, position);
reduce(term);
}
debug("no more redexes!\n");
}
void schedule_sync_priorities(void)
{
size_t iter = 0;
void *iter_val;
while (hashmap_iter(map_all_terms(), &iter, &iter_val)) {
struct term *term = *(struct term **)iter_val;
if (!term_is_beta_redex(term))
continue;
pqueue_change_priority(queue, calculate_priority(term), term);
}
}
void schedule_initialize(void)
{
srand(time(0));
size_t size = hashmap_count(map_all_terms()) + 42;
queue = pqueue_init(size, cmp_pri, get_pri, set_pri, get_pos, set_pos);
}
void schedule_destroy(void)
{
pqueue_free(queue);
}
|
