Last active
September 30, 2021 16:07
-
-
Save bitmappergit/5167fe8f2a5db82335d9d559be62feab to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdbool.h> | |
#include <stdlib.h> | |
#include <gc.h> | |
typedef enum { | |
APP, | |
CON, | |
COMB, | |
} tag_t; | |
typedef enum { | |
S = 'S', | |
K = 'K', | |
I = 'I', | |
B = 'B', | |
C = 'C', | |
Y = 'Y', | |
P = ',', | |
TAIL = ']', | |
HEAD = '[', | |
NIL = 'N', | |
IF = '?', | |
TRUE = 'T', | |
FALSE = 'F', | |
} comb_t; | |
typedef struct term_t { | |
tag_t tag; // union type tag | |
union { | |
struct { | |
struct term_t* left; // left branch | |
struct term_t* right; // right branch | |
}; | |
comb_t comb; // combinator literal | |
}; | |
} term_t; | |
term_t* root; | |
static inline term_t* new() { | |
return GC_MALLOC(sizeof(term_t)); | |
} | |
void read_file(term_t* val, FILE* file) { | |
int inp = fgetc(file); | |
switch (inp) { | |
case '`': | |
val->tag = APP; | |
val->left = new(); | |
read_file(val->left, file); | |
val->right = new(); | |
read_file(val->right, file); | |
break; | |
case '#': | |
val->tag = CON; | |
val->left = new(); | |
read_file(val->left, file); | |
val->right = new(); | |
read_file(val->right, file); | |
break; | |
case '\n': | |
break; | |
default: | |
val->tag = COMB; | |
val->comb = inp; | |
break; | |
} | |
} | |
void print_term(term_t* val) { | |
switch (val->tag) { | |
case APP: | |
putchar('`'); | |
print_term(val->left); | |
print_term(val->right); | |
break; | |
case CON: | |
putchar('`'); | |
print_term(val->left); | |
print_term(val->right); | |
break; | |
default: | |
putchar(val->comb); | |
break; | |
} | |
} | |
bool does_reduce(term_t* val) { | |
while (true) { | |
if (val->tag == APP) { | |
if (val->left->tag == APP) { | |
if (val->left->left->tag == APP) { | |
switch (val->left->left->left->comb) { | |
case S: return true; | |
case B: return true; | |
case C: return true; | |
default: break; | |
} | |
} else { | |
switch (val->left->left->comb) { | |
case K: return true; | |
case Y: return true; | |
default: break; | |
} | |
} | |
} else { | |
switch (val->left->comb) { | |
case I: return true; | |
case HEAD: return true; | |
case TAIL: return true; | |
default: break; | |
} | |
} | |
val = val->left; | |
} else if (val->tag == CON) { | |
val = val->right; | |
} else { | |
return false; | |
} | |
} | |
} | |
int to_num(term_t* val) { | |
int number = 0; | |
while (true) { | |
if (val->tag == CON && val->left->tag == COMB) { | |
val = val->right; | |
number += 1; | |
} else { | |
return number; | |
} | |
} | |
} | |
term_t* spine[8192 * 8]; | |
unsigned int sp = 0; | |
term_t* pop() { | |
return spine[sp--]; | |
} | |
void push(term_t* val) { | |
spine[++sp] = val; | |
} | |
static inline void step(term_t* val) { | |
if (val->tag == APP) { | |
if (val->left->tag == APP) { | |
if (val->left->left->tag == APP) { | |
switch (val->left->left->left->comb) { | |
case S: { term_t* x = val->left->left->right; | |
term_t* y = val->left->right; | |
term_t* z = val->right; | |
val->left = new(); | |
val->left->tag = APP; | |
val->left->left = x; | |
val->left->right = z; | |
val->right = new(); | |
val->right->tag = APP; | |
val->right->left = y; | |
val->right->right = z; | |
break; | |
} | |
case B: { term_t* f = val->left->left->right; | |
term_t* g = val->left->right; | |
term_t* x = val->right; | |
val->left = f; | |
val->right = new(); | |
val->right->tag = APP; | |
val->right->left = g; | |
val->right->right = x; | |
break; | |
} | |
case C: { term_t* f = val->left->left->right; | |
term_t* g = val->left->right; | |
term_t* x = val->right; | |
val->right = g; | |
val->left = new(); | |
val->left->tag = APP; | |
val->left->left = f; | |
val->left->right = x; | |
break; | |
} | |
default: break; | |
} | |
} else { | |
switch (val->left->left->comb) { | |
case K: *val = *val->left->right; | |
break; | |
case P: val->left = val->left->right; | |
val->tag = CON; | |
break; | |
case Y: { term_t* f = val->left->right; | |
term_t* x = val->right; | |
val->left->tag = APP; | |
val->left->left = f; | |
val->left->right = val->left; | |
val->right = x; | |
break; | |
} | |
default: break; | |
} | |
} | |
} else { | |
switch (val->left->comb) { | |
case I: *val = *val->right; | |
break; | |
case HEAD: *val = *val->right->left->left->right; | |
break; | |
case TAIL: *val = *val->right->left->right; | |
break; | |
default: break; | |
} | |
} | |
} | |
} | |
unsigned int steps = 0; | |
void reduce() { | |
while (true) { | |
if (does_reduce(spine[sp])) { | |
if (spine[sp]->tag == CON) { | |
push(spine[sp]->right); | |
} else { | |
push(spine[sp]->left); | |
} | |
} else { | |
pop(); | |
} | |
if (sp) { | |
step(spine[sp]); | |
} else { | |
return; | |
} | |
steps++; | |
} | |
} | |
int main(int argc, char* argv[]) { | |
if (argc <= 1) { | |
printf("no file provided\n"); | |
return 1; | |
} else { | |
GC_INIT(); | |
FILE* f = fopen(argv[1], "r"); | |
root = new(); | |
read_file(root, f); | |
fclose(f); | |
push(root); | |
reduce(); | |
printf("number: %d\nsteps: %d\n", to_num(root), steps); | |
print_term(root); | |
putchar('\n'); | |
return 0; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment