2016年5月20日金曜日

ノイマンの自然数(非負整数)生成プログラムについて

結城浩さんの一連のツイート に触発されて、「ノイマンの自然数(あるいは非負整数)」表現を生成するプログラムを色々書いてしまった。(要するに現実逃避:-)

まずはProlog (処理系は SWI-Prolog を使用)

nnn(0, []).
nnn(X, L) :-
    length(L, X),
    append(M, [M], L),
    succ(Y, X),
    nnn(Y, M).

これは、双方向に使えます。例えば、「?- nnn(2, X).」のようにすると整数からノイマンの形式に、また、「?- nnn(X, [[], [[]]]).」のようにすれば、ノイマンの形式に対応する整数が得られます。 しかも「?- nnn(X, Y).」とすれば、まず0について、「;」でバックトラックすると1, 2, 3, 4と次々に生成します。

次にCommon Lisp (処理系は CLISP を使用)

(defun nnn (x)
    (if (zerop x)
        nil
        (let ((m (nnn (1- x))))
            (append m (list m)))))

Prologに比べると当たり前過ぎてイマイチ面白くない(こらこら:-)

と、ここまでは「再帰的な構造しているから、プログラムも再帰呼び出し必須だよなぁ」と思ってたんですが、ふと、「COBOL で書けないかな?」と思いついたけど、流石に COBOL は最近触ってないし、可変長データ構造のサポートの現状がわからないので、「そうか、再帰を使わずに繰り返しで書ければ COBOL でも実質書けると言えるか」と思い、Common Lispで再帰を使わずに書いてみました。

(defun nnni (x)
    (prog ((i 0) (r nil))
        loop
        (if (>= i x) (return r))
        (setq r (append r (list r)))
        (setq i (1+ i))
        (go loop)))

いやぁ、 Lisp とは名ばかりなキチャナイプログラムになりました。繰り返しのスタイルが古臭いのは勘弁してください:-)

で、ここまでで一旦掲載。この後他の言語等追加するかもしれません。

それさえもおそらくは現実逃避:-)

以下、追加第1陣(2016/5/20 01:45頃)

さて、非再起な手続き型といえば古のMS-BASICですが、それっぽいものでプチコンV1.2が手元にあったので、それでも組んでみました。あまり頑張ってません:-)

画面ではコードが一部切れているので、手で転記すると、、、

INPUT X
IF X==0 THEN PRINT "{}":END
I=0
R$="{{}}"
@LOOP
IF I>=X-1 THEN PRINT R$:END
R$=MID$(R$,0,LEN(R$)-1)+","+R$+"}"
I=I+1
GOTO @LOOP

となります。(久々の手コピー:-)

というわけで、この辺にしときましょう。


(2016/5/20 23:37頃)
プチコンのBASICプログラムに冗長な行が1行あったので、削除しました。


(2016/5/21 0:40頃)
COBOLでやってみるとか(old)awk、bashではなくshとか、色々考えたんですけど、少し変な言語ということで、Windowsのバッチファイルで書いてみました:-)

ただ世の中でバッチファイルというと16ビット時代からの COMMAND.COM で実行する *.BAT と思われるようですが、今や64ビット時代なので:-)、32ビットWindowsからずっと使えている CMD.EXE で実行する *.CMD として作成しました。というか、 *.BAT では流石に無理があります:-)

@echo off
set /p x=?
if %x% equ 0 (
  echo {}
  goto :end
)
set i=0
set r={{}}
:loop
set /a x1=%x%-1
if %i% geq %x1% (
  echo %r%
  goto :end
)
set r=%r:~0,-1%,%r%}
set /a i=%i%+1
goto :loop
:end

これを越える「変な」言語とすれば、vimではなく元祖viぐらいしかのこってないかもしれない:-)