不動点コンビネータの箇所を読んでいて、そういえば以前Lazy Kというプログラム言語を調べたことを思い出し、復習してみました。(えっ、10年も前だった)

http://bitlife.me/archives/tag/lazy-k

Lazy K は、わずかSKIという3文字でプログラムが記述可能です。(実質IをSKKに変換できるので2文字)
数値や条件分岐、ループも表現できるしくみを持っていることから、可能となります。
SKIは以下のλ計算を表します。

S = λxyz.xz(yz)
K = λxy.x
I = λx.x

このルール駆使して、三文字に置き換えていくようです。
難しい概念ゆえ、文章読むだけでなく動かしてみないと理解できない、ということからいろいろ試しました。

当時と同じ環境を作ってまずは動作確認をしてみました。

(lazy-def ‘(test x) ‘(cdr x))
(print-as-cc (laze ‘test))

SI(K(KI))

記事通りできました。こういうの残しておくと楽ですね。
ここで　Lazyコマンドに渡すべくSKI文字列をいろいろとschemeプログラムを作って試しましたが、なかなか思い通り動いてくれません。サンプルもありますが、schemeからコンバートしたもので結局バイナリーファイルを眺めているようで、schemeとlazy-kの関係性みたいなものがわかりませんでした。

http://legacy.e.tir.jp/wiliki?%CB%DD%CC%F5%3A%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0%B8%C0%B8%ECLazy_K
http://esoteric.sange.fi/essie2/download/lazy-k.zip　(lazyコマンド、サンプル一式)

そのような中、schemeとの橋渡しになるような記事があり、とても参考になりました。

「究極の関数型言語による至高のHello, world!」
https://rst76.hatenablog.com/entry/20121204/1354629448

ここではHello,Worldという文字列を出力するための仕組みが説明されていますが、これでも長いため、たった一文字”H”だけ出力するプログラムにしてみました。

(load “lazier.scm”)
(load “prelude.scm”)
(load “prelude-numbers.scm”)
(lazy-def ‘(hello input) ‘(cons 72 end-of-output))
(print-as-cc (laze ‘hello))

コマンド

lazy -e “K(S(SI(K(S(K(SII(S(S(KS)K)I)))(S(S(KS)K)(S(S(KS)K)(S(SII)I(S(S(KS)K)I)))))))(K(K(SII(SII(S(S(KS)K)I))))))”

結果

H

たった一文字表示でこれだけかかります。
結局、lazy-kで出力させる(プログラム結果を見る)ということは、チャーチ数で文字コードを表現してやる必要があり、最初のサンプルが動いたことから(‘(test x) ‘(cdr x))、ロジック部分だけ考えればなんとかなると思っていたことはかなり甘かったといえます。

そこで本質的なことを理解する必要があると思い、調べていたところ下記がとても参考になりました。
「おとうさん、ぼくにもYコンビネータがわかりましたよ！」
https://nowokay.hatenablog.com/entries/2009/04/09#1239268405

また、λ計算の変換方法については下記がとても詳しいかったです。
「高階ことりちゃんと学ぶSKIコンビネータ」
http://www.tatapa.org/~takuo/kotori_ski/

最後に、コンビネータによる繰り返しを確認しました。
https://www.fixedpoint.jp/2007/02/14/y.html

(define Z
(lambda (f)
((lambda (x) (f (lambda (y) ((x x) y))))
(lambda (x) (f (lambda (y) ((x x) y)))))))

;Value: z

1 ]=> (define fact
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))

;Value: fact

1 ]=> ((Z fact) 5)

;Value: 120

ZはZコンビネータといい、Yコンビネータが無限ループしてしまうため、その変形です。
よくある再帰プログラミングの代表的な例の階乗計算ですが、注目すべき部分は無名関数でゆえ自分自身を呼び出せていません。これをZコンビネータに適用することにより繰り返し処理を実現しています。
それがどうした、と言われればそれまでですが、私はこれでコンビネータと言われる意味が理解できた気がしました。
コンビネータが表現しているものそのものは直感的でないのですが、組み合わせるとその働きがはっきりするといった触媒的なものにも感じます。
しかしネット上に意外と情報が多かったのは、興味を持つ人が多いということなのでしょう。
私ももっと探求していきたいです。

そこで、インタプリタでないコンパイラ言語のCでもeval()関数もどきができないか、やってみたらどうなるか、GWの自由研究みたいなのりでやってみました。

仕組みは、文字列で与えられたCコードを、ファイルに書き出し、これを外部コマンドでコンパイルしてダイナミックライブラリにします。これをランタイムで呼び出し実行します。

サンプルコードと、ビルドスクリプト(Pythonプログラム)をGithubにアップしました。
https://github.com/systemsblue/Eval-C-Function
ここでは、ビルドスクリプトとランタイムに生成されるファイルについて説明したいと思います。

環境 : Ubuntu 14.04
evalc_gen.h

int evalc(char *eval){
	void (*func)(__PSTRC *);
	void *so;
	__PSTRC ps;
	ps.p1 = p1;
	ps.p2 = p2;
	ps.pstr1 = pstr1;
	FILE *fp;

	fp = fopen("./sotemp.c", "w");
	fprintf(fp, __eval_fmt, eval);
	fclose(fp);
	system("cc -w -fPIC --share -o ./sotemp.so ./sotemp.c");

	so = dlopen("./sotemp.so", RTLD_LAZY);
	if(!so){
		fprintf(stderr, "%s\n", dlerror());
		return -1;
	}

	func = dlsym(so, "__feval");

	if(!func){
		fprintf(stderr, "%s\n", dlerror());
		return -2;
	}

	(*func)(&ps);
	dlclose(so);
	p1 = ps.p1;
	p2 = ps.p2;
	return 0;
}

ビルドスクリプトを実行すると、このヘッダーファイルが生成されます。
サンプルコードを解析して、evalc関数の最初と最後に、パラメータをI/O部分を記述しています。
サンプルソースの、
sample.c

int /*SO*/ p1;
int /*SO*/ p2;

char /*SO*/ pstr1[100];
char pstr2[100];

#include /*SO*/ "evalc_gen.h"

/*SO*/とコメントされている部分が処理対象となります。
evalc_gen.hは、生成ヘッダファイル名を指定します。生成された後読み込まれるもので、パラメータより後に記述します。

fprintf(fp, __eval_fmt, eval);

は、テンプレート__eval_fmtに対して、コードを書きこみます。

sotemp.c

#include<stdio.h>
#include<string.h>
typedef struct{
	int p1;
	int p2;
	char *pstr1;
} __PSTRC;
void __feval(__PSTRC *ps){
	int p1 = ps->p1;
	int p2 = ps->p2;
	char *pstr1; pstr1 = ps->pstr1;
	strcpy(pstr1, "AAAA");
	ps->p1 = p1;
	ps->p2 = p2;
}

ダイナミックライブラリの関数定義です。これはプログラム実行時に生成されます。evalc()の呼び出し分作成されます。(上書き)
sample.c

        // Eval code
        evalc("p1 /= 2; p2 -= 100");

        printf("p1 : %d  p2 : %d\n", p1, p2);

        // Eval code
        evalc("strcpy(pstr1, \"AAAA\");");

実行結果

制約条件としては、変数はグローバルで、型はポインタを使うのはcharのみです。
実用的かどうかはわかりませんが、自分ルールで作ってみるのは楽しいものです。

環境 : guile 2.0.9 / Ubuntu 14.04
circular.scm

#!/usr/bin/guile -s
!#

(use-modules (srfi srfi-1))

(define (lv ls n)
        (begin (display (car ls)) (display " ") 
        (if (= n 1)
                -1
                (lv (cdr ls) (- n 1)))))

(define (circular! ls)
	(let loop ((ls1 ls) (ls2 ls))
		(if (null? ls1)
			(set-cdr! ls2 ls)
			(loop (cdr ls1) ls1)))) 

(define (insert! ls ls1 nn)
        (let loop ((ls ls)(n 0))
                (if (= (- nn 1) n)
                        (let ((a (append ls1 (cdr ls))))
                                (set-cdr! ls '())
                                (append! ls a))
                        (loop (cdr ls)(+ n 1)))))

(define nl '(1 2 3 4 5))
(circular! nl)
(display (lv nl 20))
(newline)
(insert! nl '(a b) 3)
(display (lv nl 20))
(newline)

lvは、無限リストをあつかうため指定した数分だけ表示するというListView機能を用意しました。circlular!はリストをリング状にして循環させるもので、終端のセルのCDR部を先頭セルに書き換えます。
inser!は、指定位置に任意リストを挿入します。!は破壊的変更を意味します。
以前とりあげた順列を利用した総音程音列といい、このようなある法則にしたがったデータを作成するとき、やはりLisp言語は向いていると感じました。

実行結果

環境 : DrRacket6.1.1 / Windows 7

(require plot)
(require plot/typed)
(require 2htdp/batch-io)

(define xs '(1 2 3 4 5 6 7 8 9 10))
(define ys (map (lambda (x) (* x x)) xs))
(plot (points (map vector xs ys)))

(define xy (read-csv-file/rows "/temp/data.csv" (lambda (x) (cons (string->number (car x)) (cons (string->number (car (cdr x))) '())))))
(plot (points xy))

x,yの値を別々のリストで保持しているときの実行結果が以下です。

CUIとGUIを混同したような、画面になります。(Mathematicaライク)ドラッグで拡大できたりします。

次はCSVファイルからデータを読みこんだ場合です。

0,2
1,4
2,6
3,8
4,6
5,4
6,2
7,4
8,6
9,8
10,10

文字列として読み込むので、数値に変換しています。

Lispでデータ処理をするときに、途中結果を手軽に見るのに便利そうです。
なによりもRacketはドキュメントが充実しているので、とても使いやすいです。
ドキュメントからも描画関係の機能がとても豊富なのがわかります。
かなり遊べそうです。

例)
音列 : C D# D A F G C# A# B E G# F#
音程 : 3 11 7 8 2 6 9 1 5 4 10

参考) https://itunes.apple.com/jp/app/yin-le-dian-zhuo-mu-calc/id319666478?mt=8

またLISPというのは、List Processorの略で、カッコの構文が特徴的なリスト処理が得意の古いプログラム言語です。今回はLISP系の言語でよく使われているSchemeを使います。この言語は学習レベルでは使ったことがありますが、実用では現在の高級言語の方が向いているため、あまり使う機会がありませんでした。しかしある特定の処理に関しては、とても効率的に記述できるため、今もよく使われるています。最近のデータ処理の分野で、再び脚光を浴びているといえます。(私感ですが・・)

まず12個の音をすべてならべる順列のプログラムが必要になります。
そこから総音程の条件にあった音列のみをとりだすという手順ですすめます。

順列の生成には下記サイトを参考にしました。

参考) http://www.geocities.jp/m_hiroi/func/abcscm11.html

まずこのプログラムを見て、バックトラックの実装がこんなシンプルなコードで、できるのだろうか、という疑問がわきました。
これがLISPのすごいところです。念のためその挙動を確かめるプログラムを作ってみました。

環境 : DrRacket 6.1.1 / Windows 8.1

#lang racket
(require srfi/1)

(define (remove-item x ls)
    (remove (lambda (a) (equal? a x)) ls))

(define (perm ls a dp)
    (if (null? ls)
        (begin (display (reverse a)) (newline))
        (for-each
            (lambda (n)
                (display (format "i: ~a ~a /~a \n" ls n dp))
                (perm (remove-item n ls) (cons n a) (+ dp 1))
                (display (format "o: ~a ~a /~a \n" ls n dp)))
            ls)))

(perm '(1 2 3) '() 1)

実行結果

i: (1 2 3) 1 /1 ※
i: (2 3) 2 /2
i: (3) 3 /3
(1 2 3)
o: (3) 3 /3
o: (2 3) 2 /2
i: (2 3) 3 /2
i: (2) 2 /3
(1 3 2)
o: (2) 2 /3
o: (2 3) 3 /2
o: (1 2 3) 1 /1
i: (1 2 3) 2 /1 ※
i: (1 3) 1 /2
i: (3) 3 /3
(2 1 3)
o: (3) 3 /3
o: (1 3) 1 /2
i: (1 3) 3 /2
i: (1) 1 /3
(2 3 1)
o: (1) 1 /3
o: (1 3) 3 /2
o: (1 2 3) 2 /1
i: (1 2 3) 3 /1 ※
i: (1 2) 1 /2
i: (2) 2 /3
(3 1 2)
o: (2) 2 /3
o: (1 2) 1 /2
i: (1 2) 2 /2
i: (1) 1 /3
(3 2 1)
o: (1) 1 /3
o: (1 2) 2 /2
o: (1 2 3) 3 /1

一番右の数字は、再帰の深さで※の部分で次の入力データを読み込んでいます。

では、実際に音列を生成するプログラムを作成してみます。
できるだけシンプルにするため、リストの再利用を考えず、生成したらすぐに表示するようにしています。

#lang racket
(require srfi/1)

(define (ss ls ls1 ls2)
  (if (null? ls)
      ls2
      (ss (cdr ls)
          (cons (car ls) ls1)
          (cons (remainder (fold + 0 ls1) 12) ls2))))

(define (chk ls)
  (call/cc (lambda (ret)
  (for-each (lambda (n)
              (if (memv n ls) '() (ret #f))) 
            '(0 1 2 3 4 5 6 7 8 9 10 11)) #t )))

(define (tonerow ls a)
    (if (null? ls)
        (if (chk (ss a '() '())) 
        (begin (display a) (display (ss a '() '())) (newline)) '())
        (for-each
            (lambda (n)
                (tonerow (remove (lambda (a) (equal? a n)) ls) (cons n a)))
            ls)))

(tonerow '(1 2 3 4 5 6 7 8 9 10 11 12) '())

ss関数は、音列を足して音程のリストを作ります。chk関数で、すべての音程が含まれているかチェックします。
これを再帰を使わずにやると、12階層のループを使うことになりプログラムはこんなに簡単に書けません。最初にC言語でこのプログラムを作ったときは、ループでやったのですが、当時の最新コンパイラMS-C v5.1(Microsoft)では、ネストが深すぎでコンパイルが不可能でした。Turbo-C(Borland)では可能だった記憶があります。

ただこのプログラムは実行に約45分かかりました。(最近購入した標準的なノートPC)

実行結果 (3858行)

(9 5 8 10 11 6 3 7 4 2 1 12)(6 5 3 11 4 1 7 8 10 2 9 0)
(9 5 11 6 3 10 8 7 4 2 1 12)(6 5 3 11 4 8 10 7 1 2 9 0)
(10 3 8 11 6 5 9 7 4 2 1 12)(6 5 3 11 4 7 2 8 9 1 10 0)
・・・・
(2 9 4 1 6 7 3 5 8 10 11 12)(6 7 9 1 8 5 10 4 3 11 2 0)
(3 7 1 6 9 2 4 5 8 10 11 12)(6 7 9 1 8 4 2 5 11 10 3 0)
(3 7 4 2 1 6 9 5 8 10 11 12)(6 7 9 1 8 11 5 4 2 10 3 0)

そこで、ChickenSchremeを使って、C言語にトランスレートしてコンパイルしてみました。
(ちなみにcsiというREPL環境もあります)
上記コードの先頭を(require-extension srfi-1)に変更したものをtwelve.scmとします。

環境 : Ubuntu 14.04(DrRacketを動かしたPC上のVirtualBox)

apt-get install chicken-bin

chicken twelve.scm
cc -o twelve twelve.c -I/usr/include/chicken -lchicken
./twelve > twelve.txt

インストールもコンパイルも簡単にできました。
これでも実行時間は約30分くらいでした。(VMということであまり参考になる計測方法ではありません)
また機会があれば、他の処理系も使ってきちんと計測したいと思います。