ラムダ計算 正規順序 http://www.kb.ecei.tohoku.ac.jp/~sumii/class/keisanki-software-kougaku-2005/lambda.pdf を参考にした

a.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

////////////////////////////////////////////////////////////////
// types
////////////////////////////////////////////////////////////////

enum exp_tag {
  exp_var, exp_lam, exp_app
};

struct exp {
  enum exp_tag tag;
  union {
    int var;
    struct exp *lam;
    struct {
      struct exp *e1;
      struct exp *e2;
    } app;
  } body;
};

typedef struct exp *exp;

////////////////////////////////////////////////////////////////
// utils
////////////////////////////////////////////////////////////////

void not_NULL(void *p) {
  if (!p) {
    printf("NULL :(\n");
    exit(EXIT_FAILURE);
  }
}

void fail(void) {
  printf(":(\n");
  exit(EXIT_FAILURE);
}

exp new_var(int v) {
  exp tmp = malloc(sizeof(struct exp));
  tmp->tag = exp_var;
  tmp->body.var = v;
  return tmp;
}

exp new_lam(exp e) {
  exp tmp = malloc(sizeof(struct exp));
  tmp->tag = exp_lam;
  tmp->body.lam = e;
  return tmp;
}

exp new_app(exp e1, exp e2) {
  exp tmp = malloc(sizeof(struct exp));
  tmp->tag = exp_app;
  tmp->body.app.e1 = e1;
  tmp->body.app.e2 = e2;
  return tmp;
}

exp shallow_copy(exp e) {
  exp tmp = malloc(sizeof(struct exp));
  *tmp = *e;
  return tmp;
}

exp copy(exp e) {
  switch (e->tag) {
    case exp_var:
      return shallow_copy(e);
    case exp_lam:
      return new_lam(copy(e->body.lam));
    case exp_app:
      return new_app(copy(e->body.app.e1),copy(e->body.app.e2));
    default:
      fail();
  }
}

void deep_free(exp e) {
  switch (e->tag) {
    case exp_var:
      free(e);
      break;
    case exp_lam:
      deep_free(e->body.lam);
      free(e);
      break;
    case exp_app:
      deep_free(e->body.app.e1);
      deep_free(e->body.app.e2);
      free(e);
      break;
  }
}

int depth(exp e) {
  if (!e) {
    return 0;
  }
  switch (e->tag) {
    case exp_var:
      return 1;
    case exp_lam:
      return 1+depth(e->body.lam);
    case exp_app:
      {
        int d1 = depth(e->body.app.e1);
        int d2 = depth(e->body.app.e2);
        int d = (d1 < d2) ? d2 : d1;
        return 1+d;
      }
    default:
      fail();
  }
}

////////////////////////////////////////////////////////////////
// pretty print
////////////////////////////////////////////////////////////////

void pp_exp_rec(int prec, exp e) {
  not_NULL(e);
  switch (e->tag) {
    case exp_var:
      printf("%d", e->body.var);
      break;
    case exp_lam:
      if (0 < prec) {
        printf("(");
      }
      printf("\\");
      pp_exp_rec(0, e->body.lam);
      if (0 < prec) {
        printf(")");
      }
      break;
    case exp_app:
      if (1 < prec) {
        printf("(");
      }
      pp_exp_rec(1, e->body.app.e1);
      printf(" ");
      pp_exp_rec(2, e->body.app.e2);
      if (1 < prec) {
        printf(")");
      }
      break;
    default:
      fail();
  }
}

void pp_exp(exp e) {
  pp_exp_rec(0, e);
  printf("\n");
}

void pp_exp_debug(exp e) {
  pp_exp_rec(0, e);
  printf("\n");
}

////////////////////////////////////////////////////////////////
// parser
////////////////////////////////////////////////////////////////

void skip_spaces(char **strp) {
  not_NULL(strp);
  for (; isspace(**strp); (*strp)++)
    ;
}

void syntax_error(char **strp) {
  not_NULL(strp);
  printf("syntax error: %s\n", *strp);
  exit(EXIT_FAILURE);
}

exp parse_factor(char **);
exp parse_expr(char **);

exp parse_var(char **strp) {
  not_NULL(strp);
  int v = 0, success = 0;
  for (; isdigit(**strp); (*strp)++) {
    success = 1;
    v *= 10;
    v += **strp - '0';
  }

  if (!success) {
    return NULL;
  }
  skip_spaces(strp);
  return new_var(v);
}

exp parse_lam(char **strp) {
  not_NULL(strp);
  if (**strp != '\\') {
    return NULL;
  }
  (*strp)++;
  skip_spaces(strp);

  exp e = parse_expr(strp);
  if (!e) {
    syntax_error(strp);
  }
  skip_spaces(strp);
  return new_lam(e);
}

exp parse_factor(char **strp) {
  not_NULL(strp);
  exp ret;
  ret = parse_var(strp);
  if (ret) {
    return ret;
  }

  ret = parse_lam(strp);
  if (ret) {
    return ret;
  }

  if (**strp == '(') {
    (*strp)++;
    skip_spaces(strp);
    ret = parse_expr(strp);
    if (!ret || **strp != ')') {
      syntax_error(strp);
    }
    (*strp)++;
    skip_spaces(strp);
    return ret;
  }

  return NULL;
}

exp parse_expr(char **strp) {
  not_NULL(strp);
  exp ret = parse_factor(strp);
  if (!ret) {
    return NULL;
  }

  for (;;) {
    exp e = parse_factor(strp);
    if (!e) {
      return ret;
    }

    ret = new_app(ret,e);
  }
}

exp parse(char **strp) {
  not_NULL(strp);
  skip_spaces(strp);
  exp ret = parse_expr(strp);
  if (!ret || **strp != '\0') {
    syntax_error(strp);
  }
  return ret;
}

////////////////////////////////////////////////////////////////
// eval
////////////////////////////////////////////////////////////////

void shift_rec(int d, int c, exp e) {
  not_NULL(e);
  switch (e->tag) {
    case exp_var:
      if (e->body.var >= c) {
        e->body.var += d;
      }
      break;
    case exp_lam:
      shift_rec(d,c+1,e->body.lam);
      break;
    case exp_app:
      shift_rec(d,c,e->body.app.e1);
      shift_rec(d,c,e->body.app.e2);
      break;
  }
}

void shift(int d, exp e) {
  shift_rec(d,0,e);
}

exp subst_rec(int i, exp e1, exp e2) {
  not_NULL(e2);
  switch (e2->tag) {
    case exp_var:
      if (i == e2->body.var) {
        free(e2);
        return copy(e1);
      } else {
        return e2;
      }
    case exp_lam:
      shift(1,e1);
      e2->body.lam = subst_rec(i+1,e1,e2->body.lam);
      shift(-1,e1);
      return e2;
    case exp_app:
      e2->body.app.e1 = subst_rec(i,e1,e2->body.app.e1);
      e2->body.app.e2 = subst_rec(i,e1,e2->body.app.e2);
      return e2;
    default:
      fail();
  }
}

exp subst(int i, exp e1, exp e2) {
  exp ret = subst_rec(i,e1,e2);
  deep_free(e1);
  return ret;
}

exp step(exp e);

// `app' must be equal to `new_app(e1,e2)'.
exp apply(exp app, exp e1, exp e2) {
  not_NULL(e1);
  switch (e1->tag) {
    case exp_lam:
      {
        exp new_e1 = e1->body.lam;
        shift(1,e2);
        new_e1 = subst(0,e2,new_e1);
        shift(-1,new_e1);
        free(e1);
        return new_e1;
      }
    case exp_var:
    case exp_app:
      {
        exp tmp;
        tmp = step(e1);
        if (tmp) {
          app->body.app.e1 = tmp;
          return app;
        }
        tmp = step(e2);
        if (tmp) {
          app->body.app.e2 = tmp;
          return app;
        }
        return NULL;
      }
    default:
      fail();
  }
}

exp step(exp e) {
  not_NULL(e);
  switch (e->tag) {
    case exp_var:
      return NULL;
    case exp_lam:
      {
        exp tmp = step(e->body.lam);
        if (tmp) {
          e->body.lam = tmp;
          return e;
        } else {
          return NULL;
        }
      }
    case exp_app:
      return apply(e, e->body.app.e1, e->body.app.e2);
    default:
      fail();
  }
}

exp eval(exp e) {
  not_NULL(e);
  exp ret;
  for (exp i = e; i; i = step(i)) {
    ret = i;
  }
  return ret;
}

////////////////////////////////////////////////////////////////
// main
////////////////////////////////////////////////////////////////

int main(void) {
  char str[1024], *p = str;
  fgets(str, 1024, stdin);
  exp e = parse(&p);
  pp_exp(e);
  e = eval(e);
  pp_exp(e);
  return EXIT_SUCCESS;
}

a.hs

-- http://www.kb.ecei.tohoku.ac.jp/~sumii/class/keisanki-software-kougaku-2005/lambda.pdf
import Control.Applicative

data Exp
  = Var Int
  | Lam Exp
  | App Exp Exp
  deriving (Show)

shift' :: Int -> Int -> Exp -> Exp
shift' d c e@(Var v)
  | v < c = e
  | otherwise = Var (v+d)
shift' d c (Lam e) = Lam $ shift' d (c+1) e
shift' d c (App e1 e2) = App (shift' d c e1) (shift' d c e2)

shift :: Int -> Exp -> Exp
shift d e = shift' d 0 e

-- [ i -> e1 ] e2
subst :: Int -> Exp -> Exp -> Exp
subst i e1 e2@(Var v)
  | i == v = e1
  | otherwise = e2
subst i e1 (Lam e2) = Lam (subst (i+1) (shift 1 e1) e2)
subst i e1 (App e21 e22) = App (subst i e1 e21) (subst i e1 e22)

step :: Exp -> Maybe Exp
step e@(Var _) = empty
step (Lam e) = Lam <$> step e
step (App e1 e2) =
  case e1 of
    Lam e1' -> pure $ shift (-1) (subst 0 (shift 1 e2) e1')
    _ -> ((`App`e2) <$> step e1) <|> ((e1`App`) <$> step e2)

rep :: Exp -> Exp
rep e = maybe e rep $ step e

sample

(\0 (\\0(1(\\0))(\\1(3(\\0)1 0))) (\0(\\0)(\\0)) (\\1)) (\\1(1(1 0)))

pred 3の計算