untyped.c

#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;
}