少年コンパイラ、成年コンパイラ

2009/11/19 by demuyan · コメントする
カテゴリー: プログラミング 
  このエントリーを含むはてなブックマーク この記事をクリップ！ コメントを見る

Donald Knuth(ドナルド クヌース)と言えばTeXで有名な方。

その昔、クヌースがAlgol60という言語を評価するにあたって、あるコードを書き、次のように述べたという。

私はこのシンプルなルーチンを書いた。これが少年期のコンパイラと成年期のコンパイラを区別するかもしれない

ちなみにAlgol60は、今でこそあまり目にする機会が無い言語だが、C,Pascal,JavaやPerl等のスクリプト言語など様々な言語に影響を与えた言語として有名である。

クヌースの定義としては、”再帰、ローカル変数無し”で、シンプルにコードが書けるかどうかで、コンパイラの成熟度を少年期と成年期に区別したようだ。

これがクヌースオリジナルのAlgol 60で書かれたもの。シンプル。

begin
  real procedure A (k, x1, x2, x3, x4, x5);
  value k; integer k;
  begin
    real procedure B;
    begin k:= k - 1;
          B:= A := A (k, B, x1, x2, x3, x4);
    end;
    if k <= 0 then A:= x4 + x5 else B;
  end;
  outreal (A (10, 1, -1, -1, 1, 0));
end;

同じアルゴリズムを他の言語で書くとこのようになる。Man or boy test – Rosetta Codeには、アルゴリズムの解説、多数の言語に移植されたコードが掲載されているが、ここでは普段よく目にする言語のコードを掲載。

それぞれの言語の特徴が出て、比べて見ていると面白く、また意外な発見があったりする。

C言語

/* man-or-boy.c */
#include <stdio.h>
#include <stdlib.h>
 
// --- thunks
typedef struct arg {
  int       (*fn)(struct arg*);
  int        *k;
  struct arg *x1, *x2, *x3, *x4, *x5;
} ARG;
 
// --- lambdas
int f_1 (ARG* _) { return -1; }
int f0  (ARG* _) { return  0; }
int f1  (ARG* _) { return  1; }
 
// --- helper
int eval(ARG* a) { return a->fn(a); }
#define ARG(...) (&(ARG){ __VA_ARGS__ })
#define FUN(...) ARG(B,&k,__VA_ARGS__)
 
// --- functions
int B(ARG* a) {
  int A(ARG*);
  int k = *a->k -= 1;
  return A( FUN(a,a->x1,a->x2,a->x3,a->x4) );
}
 
int A(ARG* a) {
  return *a->k <= 0 ? eval(a->x4)+eval(a->x5) : B(a);
}
 
int main(int argc, char **argv) {
  int k = argc == 2 ? strtol(argv[1],0,0) : 10;
  printf("%d\n", A( FUN(ARG(f1),ARG(f_1),ARG(f_1),ARG(f1),ARG(f0)) ));
}

C言語(gcc拡張を利用)

gcc version 4.1.2 20070925 (Red Hat 4.1.2-27)

#include <stdio.h>
#define INT(body) ({ int lambda(){ body; }; lambda; })
main(){
  int a(int k, int xl(), int x2(), int x3(), int x4(), int x5()){
    int b(){
      return a(--k, b, xl, x2, x3, x4);
    }
    return k<=0 ? x4() + x5() : b();
  }
  printf(" %d\n",a(10, INT(return 1), INT(return -1), INT(return -1), INT(return 1), INT(return 0)));
}

C# 2.0

 
using System;
 
delegate T Func<T>();
 
class ManOrBoy
{
    static void Main()
    {
        Console.WriteLine(A(10, C(1), C(-1), C(-1), C(1), C(0)));
    }
 
    static Func<int> C(int i)
    {
        return delegate { return i; };
    }
 
    static int A(int k, Func<int> x1, Func<int> x2, Func<int> x3, Func<int> x4, Func<int> x5)
    {
        Func<int> b = null;
        b = delegate { k--; return A(k, b, x1, x2, x3, x4); };
        return k <= 0 ? x4() + x5() : b();
    }
}

C# 3.0

using System;
 
class ManOrBoy
{
    static void Main()
    {
        Console.WriteLine(A(10, () => 1, () => -1, () => -1, () => 1, () => 0));
    }
 
    static int A(int k, Func<int> x1, Func<int> x2, Func<int> x3, Func<int> x4, Func<int> x5)
    {
        Func<int> b = null;
        b = () => { k--; return A(k, b, x1, x2, x3, x4); };
        return k <= 0 ? x4() + x5() : b();
    }
}

Java

public class ManOrBoy
{
    interface Arg
    {
        public int run();
    }
 
    public static int A(final int k, final Arg x1, final Arg x2, final Arg x3, final Arg x4, final Arg x5)
    {
        if (k <= 0)
            return x4.run() + x5.run();
        else {
            Arg b = new Arg() {
                    int m = k;
                    public int run()
                    {
                        m--;
                        return A(m, this, x1, x2, x3, x4);
                    }
                };
            return b.run();
        }
    }
 
    public static void main(String[] args)
    {
        System.out.println(A(10,
                             new Arg() { public int run() { return 1; } },
                             new Arg() { public int run() { return -1; } },
                             new Arg() { public int run() { return -1; } },
                             new Arg() { public int run() { return 1; } },
                             new Arg() { public int run() { return 0; } }));
    }
}

JavaScript

function A(k,x1,x2,x3,x4,x5) {
  var B = function() { return A(--k, B, x1, x2, x3, x4) }
  return k<=0 ? x4()+x5() : B()
}
function K(n) {
  return function() { return n }
}
alert( A(10, K(1), K(-1), K(-1), K(1), K(0) ) )

Perl

sub A {
    my ($k, $x1, $x2, $x3, $x4, $x5) = @_;
    my($B);
    $B = sub { A(--$k, $B, $x1, $x2, $x3, $x4) };
    $k <= 0 ? &$x4 + &$x5 : &$B;
}
 
print A(10, sub{1}, sub {-1}, sub{-1}, sub{1}, sub{0} ), "\n";

PHP

PHP 5.3

function A($k,$x1,$x2,$x3,$x4,$x5) {
    $b = function () use (&$b,&$k,&$x1,&$x2,&$x3,&$x4) {
        $k--; return A($k,$b,$x1,$x2,$x3,$x4);
    };
    return $k <= 0 ? $x4() + $x5() : $b();
}  
 
echo A(10, function () { return  1; },
           function () { return -1; },
           function () { return -1; },
           function () { return  1; }, 
           function () { return  0; }) . "\n";

Ruby

def a(k, x1, x2, x3, x4, x5)
  b = lambda { k -= 1; a(k, b, x1, x2, x3, x4) }
  k <= 0 ? x4[] + x5[] : b[]
end
 
puts a(10, lambda {1}, lambda {-1}, lambda {-1}, lambda {1}, lambda {0})
プログラミング作法
プログラミング作法Brian Kernighan

おすすめ平均
stars良著です。
stars入門書の次の次の次くらいに！
stars繰り返し読む必要あり
stars絶対にお勧めの本です
stars良いプログラマになりたいあなたに

Amazonで詳しく見る by G-Tools

こちらもあわせてどうぞ

Tags:

Comments

コメントをどうぞ...





Trackback URL

Get Adobe Flash playerPlugin by wpburn.com wordpress themes