ski.c

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