C - プログラミング概念入門(高階プログラミング, パスカルの三角形の変種)

21st Century C: C Tips from the New School
(O'Reilly Media)
Ben Klemens (著)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• C (プログラミング言語)
• LLVM/Clang (コンパイラ, Xcode - Apple)

コンピュータプログラミングの概念・技法・モデル(IT Architect' Archiveクラシックモダン・コンピューティング6) (IT Architects’Archive CLASSIC MODER)(セイフ・ハリディ (著)、ピーター・ヴァン・ロイ (著)、Peter Van-Roy (著)、 Seif Haridi (著)、羽永 洋　(翻訳) 、翔泳社、原書: Concepts, Techniques, and Models of Computer Programming(CTM))の第1章(プログラミング概念入門)、1.18(練習問題)、6.(高階プログラミング)をC言語で考えてみる。

6.(高階プログラミング)

コード(BBEdit, Emacs)

sample6.h

typedef struct list {
  double head;
  struct list *tail;
} list;

list* list_new(double *in);
void list_free(list *l);

void list_print(list *in);

list* list_cons(double a, list *in);
double list_car(list *in);
list* list_cdr(list *in);

typedef double (*func_type)(double, double);

list* generic_pascal(func_type op, int n);
list* op_list(func_type op, list *in1, list *in2);
list* shift_left(list *in);
list* shift_right(list *in);
double sub(double, double);
double mul(double, double);
double mull(double, double);

sample6.c

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

#include "sample6.h"

list* list_new(double *in) {
  list *out = NULL;
  list *tail = NULL;
  for (int i = 0; !isnan(in[i]); i++) {
    if (!tail) {
      tail = malloc(sizeof(list));
      out = tail;
    } else {      
      tail->tail = malloc(sizeof(list));
      tail = tail->tail;;
    }
    *tail = (list){.head=in[i],.tail=NULL};
  }
  return out;
}

void list_free(list *l) {
  list *tail = NULL;
  for (; l != NULL; l = tail) {
    tail = l->tail;
    free(l);
  }
}

void list_print(list *in) {
  int flag = 1;
  printf("(");
  for (list *i = in; i != NULL; i = i->tail)
    if (flag) {
      printf("%i", (int)i->head);
      flag = 0;
    } else {
      printf(" %i", (int)i->head);
    }
  printf(")\n");
}

list* list_cons(double a, list *in) {
  list *out = malloc(sizeof(list));
  *out = (list){.head=a,.tail=in};
  return out;
}

double list_car(list *in) {
  assert(in != NULL);
  return in->head;
}

list* list_cdr(list *in) {
  assert(in != NULL);
  return in->tail;
}

list* generic_pascal(func_type op, int n) {
  if (n == 1) return list_new((double[]){1, NAN});
  list *l = generic_pascal(op, n - 1);
  return op_list(op, shift_left(l), shift_right(l));
}
  
list* op_list(func_type op, list *in1, list *in2) {
  if (in1) {
    double h1 = in1->head;
    list *t1 = in1->tail;
    if (in2) {
      double h2 = in2->head;
      list *t2 = in2->tail;
      return list_cons(op(h1, h2), op_list(op, t1, t2));
    }
  }
  return NULL;
}

list* shift_left(list *in) {
  if (in) return list_cons(in->head, shift_left(in->tail));
  else return list_new((double[]){0, NAN});
}

list* shift_right(list *in) {
  return list_cons(0, in);
}

double sub(double x, double y) {
  return x - y;
}

double mul(double x, double y) {
  return x * y;
}

double mull(double x, double y) {
  return (x + 1) * (y + 1);
}

int main() {
  func_type funcs[] = {sub, mul, mull};
  for (int i = 0; i < 3; i++)
    for (int n = 1; n <= 5; n++) {
      printf("n=%i\n", n);
      list *l = generic_pascal(funcs[i], n);
      list_print(l);
      list_free(l);
    }  
}

入出力結果(Terminal)

$ crun.sh sample6
clang-mp-3.5 -g -Wall -I/Users/kamimura/root/include `pkg-config --cflags gsl glib-2.0 libxml-2.0` `curl-config --cflags` -include ~/root/include/allheads.h -Wno-initializer-overrides -fms-extensions -std=c11    sample6.c  `pkg-config --libs gsl glib-2.0 libxml-2.0` `curl-config --libs ` -lxml2 -lpthread -L/opt/local/lib -lgmp -o sample6
n=1
(1)
n=2
(1 -1)
n=3
(1 -2 1)
n=4
(1 -3 3 -1)
n=5
(1 -4 6 -4 1)
n=1
(1)
n=2
(0 0)
n=3
(0 0 0)
n=4
(0 0 0 0)
n=5
(0 0 0 0 0)
n=1
(1)
n=2
(2 2)
n=3
(3 9 3)
n=4
(4 40 40 4)
n=5
(5 205 1681 205 5)
$