Factor で階乗。然して再帰に就いて抄 - c4se記：さっちゃんですよ☆

連鎖性 concatnative のprogramming言語の一つFactorに就いて書いた。
cf. 関数合成型 ( Forth 系) 言語 Factor への入り口 http://c4se.hatenablog.com/entry/2013/12/26/044415
幾つか間違ってゐる。例へば変数はstaticなものもdynamicなものも使へた。兎も角、

再帰 recursion

兎も角、

id:itochan
再起関数が面白そう。　と思うのは、「5」は「5をstackへpushする関数」って書いてて、合成関数「5 *」でそのpushをはしょってるから（最適化？）。 n! みたいのの関数の説明が見たい。　…factorだけに。
http://b.hatena.ne.jp/entry/c4se.hatenablog.com/entry/2013/12/26/044415

と云ふcommentが有った。多分此の興味はあてが外れて、遅延束縛 lazy binding な言語や場面では再帰の名称で困ることは無い。動的型付け (実行時型付け) で遅延束縛ならば再帰は問題に成らない。Factorはwordの指す値に就いて (integer, fixnum, ratio, array, string 等) は動的型付けだ。問題に成るとしたら、stack効果宣言は静的型付けだと解釈できる。stackから何を幾つとって幾つかへすか、だ。ただこの意味でも「型推論」は行われないから、問題は起らないと言へる。macroが展開されてしまへば、其の後動的にwordが定義される事もない気がするから、macro展開 + word定義 -> stack効果宣言検証とphaseを分けられれば、compile時遅延束縛と言へる。此の辺の事情を静的型付けの言語で見てみる。
C#を使ふ (C#はVimで書かう！)。

class RecurClass
{
    static void Main()
    {
        System.Console.WriteLine(new RecurClass().Recur(15));
    }

    private int Recur(int n)
    {
        if (n % 2 == 0)
            return n;
        else
            return Recur(n - 1);
    }
}

using System;

class RecurClass
{
    static void Main()
    {
        Func<int, int> recur = null;
        recur = (n) =>
        {
            if (n % 2 == 0)
                return n;
            else
                return recur(n - 1);
        };
        Console.WriteLine(recur(15));
    }
}

一つ目の、再帰関数をmethodとして定義した方は、遅延束縛が効いてゐる (さっきから「遅延束縛」と云ふ語を可成り広義に使ってゐる)。methodの定義phaseとlocal変数の定義phaseは、compile中で別れてゐるのだ。証拠が有る。lambda式を使った二つ目の方では、同じことができてゐない。再帰関数の記述する前に、変数の型を宣言しておかなければならない。nullを代入してるのが其れだ。此うしないとcompileは通らない。local変数同士は遅延束縛されないからだ。
JavaScriptでは洞ちらも問題に成らない。遅延束縛だからだ。

console.log(recur(15));

function recur(n) {
  if (n % 2 === 0)
    return n;
  else
    return recur(n - 1);
}

var recur = function (n) {
  if (n % 2 === 0)
    return n;
  else
    return recur(n - 1);
};

console.log(recur(15));

此の問題は関数型言語では少し違ふかたちで出る。F#を使ふ (F#もVimで書かう！)。

module recur

let rec recur n =
  match n % 2 with
  |0 -> n
  |_ -> recur (n - 1)

printf "%d" (recur 15)

letとletrecを区別してゐる訳だ。letとは語の置き換えであり、letrecは不動点演算子だから別物なのだ。実はletを無くして全てletrecにしてしまっても世界はまわる。letrecが有ればletが無くてもprogramming言語は作れる。Haskellは然ふした。
letをletrecに統合する影響を、わたしは未だ測れてゐない。遅延評価 lazy evaluation / 正格評価 eager evaluation と関係が有ると云ふ話しを読んだことがある (遅延束縛との類似から、ありさうな話ではある)。ML系 (ML, OCaml, F# 等) は全てletとletrecを区別する。Scheme (Lisp) もだ。わたしの持ってゐるprogram意味論の教科書も区別してゐるが、此れはletを単純な操作のままにしておきたいからだらう、此の文脈ではletrecは多くのことをやり過ぎる。

Factorで階乗

で、実際に書いてみる。lexcialな変数を使ふ。[| n | n ]の奴だ。他の記法も有った。

! Copyright (C) 2013 Sachirou Inoue.
! Public Domain
USING: io kernel locals math math.parser ;
IN: factorial

: factorial_rec ( n n -- n ) dup 0 = [ drop ] [
  [| n m | n m * m 1 - factorial_rec ] call
] if ;

: factorial ( n -- n ) dup 0 < [ drop 0 ] [ 1 swap factorial_rec ] if ;

: factorial_demo ( -- ) 10 factorial number>string print ;

MAIN: factorial_demo

[ ]で括ってるのが例の、引用 quotation って奴だ。後置記法だと言へば、なんとなく読めるとおもふ。IN: factorialは、module (?) を宣言してゐる、よく解ってゐない。MAIN: がentry pointだが、此所に複数のwordを書く事はできない、実行するwordを定義する事。dupはstackの先頭を複製、dropはstackの先頭を破棄、swapはstackの先頭と二番目を交換する。ifは一つのbooleanと二つのquotationをとり、どちらかのquotationを実行する。ただのwordだと思って問題ないとおもふ、実際にはnativeに実装されてゐるやうだ。
因みに空白は重要だ。
"factor"って語、検索しづらいのな(〃l _ l)

@ne_sachirou math.parserってボキャブラリにnumber>stringってのがありました。USE: math.parserしてから5 number>string print
— minori (@ympbyc) December 29, 2013

でもFactorのreference内を検索できるので、なんとか成りさうだ。
因みに階乗はmath.factorialsに定義済みで、

USE: math.factorials
10 factorial .

で使へる。定義は

USING: kernel math math.ranges memoize sequences ;
IN: math.factorials
MEMO: factorial ( n -- n! )
    dup 1 > [ [1,b] product ] [ drop 1 ] if ;

ださうだ。今のわたしには読めない。

letとletrecに就いて更にmemo

後で参照する用途にmemoしておく。
cf. Scheme で変数の束縛 - let, let*, letrec, 名前付きlet, letrec* | すぐに忘れる脳みそのためのメモ http://jutememo.blogspot.jp/2012/11/scheme-let-let-letrec-let-letrec.html
cf. let が再帰でない理由というかメリット - Oh, you `re no (fun _ → more) http://d.hatena.ne.jp/camlspotter/20091018/1255867603
cf. OCaml の let と let rec はなぜ別扱いになっているのか、決定版、もしくは OCaml 暦十何年だったか忘れたけど仕事で Haskell を一年使ってみた - Oh, you `re no (fun _ → more) http://d.hatena.ne.jp/camlspotter/20110509/1304933919
cf. Island Life - let地獄 http://blog.practical-scheme.net/shiro?20110509-too-many-lets
cf. letとletrecが必要なのはなぜか - 飲む、寝る。 http://d.hatena.ne.jp/nomnel/20120712/1342085066
cf. letrecと不動点方程式とトレース付き圏 - 檜山正幸のキマイラ飼育記 http://d.hatena.ne.jp/m-hiyama/20120825/1345875871
cf. letとletrec 再論 - 檜山正幸のキマイラ飼育記 http://d.hatena.ne.jp/m-hiyama/20131005/1380943740