Created
January 23, 2017 15:49
-
-
Save matthew-ball/995ba4ff7ad21d677ff3c1d288ede3ad 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 <stdlib.h> | |
#include <string.h> | |
#include <ctype.h> | |
#include <unistd.h> | |
#define MALLOC_CHECK(ptr) ({ if (!ptr) { fprintf(stderr, "[%s] malloc failed\n", __func__); exit(EXIT_FAILURE); }}) | |
typedef enum { VARIABLE, LAMBDA, APPLICATION } type_t; | |
typedef struct _term_t term_t; | |
typedef struct { | |
char *name; | |
} variable_t; | |
typedef struct { | |
size_t arguments_count; | |
term_t **arguments; | |
term_t *body; | |
} lambda_t; | |
typedef struct { | |
term_t *left; | |
term_t *right; | |
} application_t; | |
typedef union { | |
variable_t variable; | |
lambda_t lambda; | |
application_t application; | |
} data_t; | |
typedef struct _term_t { | |
type_t type; | |
data_t data; | |
} term_t; | |
#define VARIABLE_NAME(ptr) ((ptr)->data.variable.name) | |
#define LAMBDA_ARGS_COUNT(ptr) ((ptr)->data.lambda.arguments_count) | |
#define LAMBDA_ARGS(ptr) ((ptr)->data.lambda.arguments) | |
#define LAMBDA_BODY(ptr) ((ptr)->data.lambda.body) | |
#define APPLICATION_LEFT(ptr) ((ptr)->data.application.left) | |
#define APPLICATION_RIGHT(ptr) ((ptr)->data.application.right) | |
term_t *alloc_term() { | |
term_t *ptr = malloc(sizeof(ptr)); | |
MALLOC_CHECK(ptr); | |
return ptr; | |
} | |
term_t *variable_term(const char *name) { | |
term_t *ptr = alloc_term(); | |
ptr->type = VARIABLE; | |
VARIABLE_NAME(ptr) = malloc(strlen(name) + 1); | |
MALLOC_CHECK(VARIABLE_NAME(ptr)); | |
strcpy(VARIABLE_NAME(ptr), name); | |
return ptr; | |
} | |
term_t *lambda_term(term_t **arguments, size_t arguments_count, term_t *body) { | |
term_t *ptr = alloc_term(); | |
ptr->type = LAMBDA; | |
LAMBDA_ARGS_COUNT(ptr) = arguments_count; | |
LAMBDA_ARGS(ptr) = arguments; | |
LAMBDA_BODY(ptr) = body; | |
return ptr; | |
} | |
term_t *application_term(term_t *left, term_t *right) { | |
term_t *ptr = alloc_term(); | |
ptr->type = APPLICATION; | |
APPLICATION_LEFT(ptr) = left; | |
APPLICATION_RIGHT(ptr) = right; | |
return ptr; | |
} | |
void print_term(const term_t *term); | |
void print_variable(const term_t *term) { | |
printf("%s", VARIABLE_NAME(term)); | |
} | |
void print_lambda(const term_t *term) { | |
size_t i, count = LAMBDA_ARGS_COUNT(term); | |
printf("(\\"); | |
for (i = 0; i < count; i++) { | |
print_term(LAMBDA_ARGS(term)[i]); | |
if (i < count - 1) { | |
printf(" "); | |
} | |
} | |
printf(". "); | |
print_term(LAMBDA_BODY(term)); | |
printf(")"); | |
} | |
void print_application(const term_t *term) { | |
printf("("); | |
print_term(APPLICATION_LEFT(term)); | |
printf(" "); | |
print_term(APPLICATION_RIGHT(term)); | |
printf(")"); | |
} | |
void print_term(const term_t *term) { | |
switch (term->type) { | |
case VARIABLE: print_variable(term); break; | |
case LAMBDA: print_lambda(term); break; | |
case APPLICATION: print_application(term); break; | |
default: | |
fprintf(stderr, "[%s] unknown term type\n", __func__); | |
exit(EXIT_FAILURE); | |
} | |
} | |
void free_term(term_t *term) { | |
switch (term->type) { | |
case VARIABLE: | |
free(term); break; | |
case LAMBDA: | |
{ | |
int i; | |
for (i = 0; i < LAMBDA_ARGS_COUNT(term); i++) { | |
free(LAMBDA_ARGS(term)[i]); | |
} | |
} | |
free(LAMBDA_BODY(term)); | |
free(term); | |
break; | |
case APPLICATION: | |
free(APPLICATION_LEFT(term)); | |
free(APPLICATION_RIGHT(term)); | |
free(term); | |
break; | |
} | |
} | |
#define MAX_BUFFER 1024 | |
term_t *next_token(FILE *input) { | |
char buffer[MAX_BUFFER]; | |
size_t index = 0; | |
int ch = getc(input); | |
while (isspace(ch)) { | |
ch = getc(input); | |
} | |
if (ch == '\n' || ch == '\t') { | |
ch = getc(input); | |
} | |
if (ch == EOF) { | |
exit(EXIT_SUCCESS); | |
} | |
if (ch == ')') { | |
return variable_term(")"); | |
} | |
if (ch == '(') { | |
return variable_term("("); | |
} | |
if (ch == '\\') { | |
return variable_term("\\"); | |
} | |
if (ch == '.') { | |
return variable_term("."); | |
} | |
while (!isspace(ch) && ch != ')' && ch != '.') { | |
buffer[index++] = ch; | |
ch = getc(input); | |
} | |
if (ch == '.') { | |
ungetc(ch, input); | |
} | |
buffer[index++] = '\0'; | |
return variable_term(buffer); | |
} | |
term_t *evaluate_term(term_t *term) { | |
return term; | |
} | |
term_t *read_term(FILE *input) { | |
term_t *token = next_token(input); | |
if (strcmp(VARIABLE_NAME(token), ")") == 0) { | |
return NULL; | |
} else if (strcmp(VARIABLE_NAME(token), "(") == 0) { | |
token = next_token(input); | |
if (strcmp(VARIABLE_NAME(token), "\\") == 0) { | |
term_t **arguments = malloc(sizeof(arguments) * 1); | |
size_t arguments_count = 0; | |
MALLOC_CHECK(arguments); | |
token = next_token(input); | |
while (strcmp(VARIABLE_NAME(token), ".") != 0) { | |
if (arguments_count > 1) { | |
arguments = realloc(arguments, sizeof(arguments) * arguments_count); | |
MALLOC_CHECK(arguments); | |
} | |
arguments[arguments_count++] = token; | |
token = next_token(input); | |
} | |
return lambda_term(arguments, arguments_count, read_term(input)); | |
} else { | |
return application_term(token, read_term(input)); | |
} | |
} | |
return token; | |
} | |
void repl(FILE *input) { | |
do { | |
printf("evaluate> "); | |
print_term(evaluate_term(read_term(input))); | |
printf("\n"); | |
} while(1); | |
} | |
int main(int argc, char *argv[]) { | |
FILE *input = (argc > 1) ? fopen(argv[1], "r") : stdin; | |
repl(input); | |
fclose(input); | |
/* term_t *x = variable_term("x"); */ | |
/* term_t *y = variable_term("y"); */ | |
/* printf("variable: "); */ | |
/* print_term(x); */ | |
/* printf("\n"); */ | |
/* term_t *application = application_term(x, y); */ | |
/* printf("application: "); */ | |
/* print_term(application); */ | |
/* printf("\n"); */ | |
/* term_t **args = malloc(sizeof(args) * 2); */ | |
/* MALLOC_CHECK(args); */ | |
/* args[0] = x; */ | |
/* args[1] = y; */ | |
/* term_t *lambda = lambda_term(args, 2, application); */ | |
/* printf("lambda: "); */ | |
/* print_term(lambda); */ | |
/* printf("\n"); */ | |
/* free_term(x); */ | |
/* free_term(y); */ | |
/* free_term(application); */ | |
/* //free_term(lambda); */ | |
return EXIT_SUCCESS; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment