萌香を使えば京大にも入れるの巻

萌香で京大の入試問題を力技の巻

おまえにハートブレイク☆オーバードライブ - 小粋な数学入試問題 より

......って引用しようと思ったけど数式が画像とか引用がめんどくさいので元記事読んでください。

んでこれの設問の2。これが萌香があれば解けちゃうんです。ソースはこちら

「レンジ を 「(開始 終点)
      「もし (開始 終点 >)
              '()
             「開始 「(開始 1.0 +) 終点 の レンジ」 の コンス」」
           の 仕事」 と 定義」


「階乗 を 「(a b)
        「もし (b 0.1 <=)   ;; たぶん無いけど丸め誤差とかがあったときのため
              1.0
             「(a (b 1.0 -) の 階乗) a *」」
       の 仕事」 と 定義」


「f を 「(n)
     「n の 7 の 剰余」
    の 仕事」 と 定義」


「g を 「(n)
        (3 に
           ((+
             0
             (「(num) 「num の n の 階乗」 の 仕事」 に
              「1 7 の レンジ」 を マップ)
          の 右畳み込み) の f)
           を かける)  仕事」 と 定義」



「「(n) 「n と 表示」
        「":" と 表示」
        「(n の g) と 表示」
        「改行」              の 仕事」 に
  「1 15 の レンジ」 を マップ」

 

これを実行すると6と12のところで18点ゲット。 fの性質よりmaxの点が18なので答案用紙に6と書けば、この問題はパーヘクツですよあなた !!

なんで中途半端な15までなのかって ?..........

萌香は数値をすべてRubyのFloatで保持しているため Cのdouble型の精度となります。そうすると仮数部が53 bitなため2^53を超えるところ 10^16のところで正確な計算ができなくなってしまい、 20のところで7^20が出て、これが10^16を超えるので正確な計算ができなくなりおかしな数字が出てしまう結果となります。これは ここ(遥か彼方の彼方から - 小粋な数学入試問題をcodepadで組んでみた) のプログラムもおんなじ原因じゃないかと思ってたらすでに指摘があった.....

ちなみにRuby版が

#!/usr/local/bin/ruby


def pow(x, y)
  result = 1
  (1..y).each do |dummy|
    result = result * x
  end

  return result
end


def f(n)
  return n % 7
end


def g(n)
  return 3 * (f((1..7).map{|num| pow(num, n)}.inject(0){|sum, num| sum + num}))
end



(1..100).each do |num|
  puts "#{num}:#{g(num)}"
end

Scheme(Gauche)版が

#!/usr/local/bin/gosh

(use srfi-1)

(define pow
  (lambda (x y)
    (if (= 1 y)
	x
	(* x (pow x (- y 1))))))

(define f
  (lambda (n)
    (modulo n 7)))

(define g
  (lambda (n)
    (* 3 
       (f (fold + 0 (map (lambda (num) (pow num n))
			 (iota 7 1)))))))


(map (lambda (num)
       (format #t "~a: ~a\n" num (g num)))
     (iota 100 1))

となります。

 

どちらも100程度まではなんの問題もなく動きます。 Bignumなんかいらね、とか思ってたのですが、この程度でも必要になってくるのですね。

プログラム中の末尾再帰に関するメモ

「萌香」のコードを整理しようと思ってコードを読んだんですが、「末尾再起の最適化に関するメモ」というコメントがなにを書いてるんだかさっぱりわからない。ポルナレフAAを貼りたくなるぐらい何がなんだかわからない。なんか悪い薬でもやってたんだろうか。

きっと末尾再帰っぽいことがようやくできて舞い上がっていたんだろう。黒歴史として早く葬りたい。

解読してみる。

--- begin 本文 ---
末尾再帰の最適化に関するメモ

本プログラムには変数のフレームのスタックと継続のスタックが存在します。
Lexical scopeのクロージャなので、クロージャの再帰呼出しではフレームの
スタックが積まれることはありません。
(その呼出しへの参照が残っていた場合、そこに保持されている。)

クロージャの呼出し時に
フレームの退避 --> クロージャの実行 --> フレームの復帰
と行うと、クロージャの実行時に末尾再帰呼出しがあった場合
フレームの退避 --> クロージャの実行 -->
フレームの退避 --> クロージャの実行 --> フレームの復帰 --> フレームの復帰
となります。
ここで、フレームの退避はlexical scopeクロージャの場合フレームの
新規作製であり、作製されたフレームはクロージャの実行の終了とともに
GCによって回収されるようになります。

結局クロージャの実行時にフレームの復帰の継続がどんどん増えていくことに
なります。
フレームの復帰は最後のものだけ行えばよく、
末尾再帰の場合、フレームの復帰の継続を作製する場合、次の継続に
フレームの復帰があった場合継続の作製は行う必要はありません。

以上のことから、フレーム復帰の継続の作製を抑制すれば末尾再帰の
最適化になることになります。
--- end 本文 ---

--- 本プログラムには変数のフレームのスタックと継続のスタックが存在します。
これは単なる事実。ここでいう継続のスタックで保持されているものには次の関数呼び出しで使われる引数の保持先(return valueの戻し先)等様々なものがある。(わかりにくくてすみません。あとで整理する。)　なので厳密な「継続のスタック」ではないかも知れない。

--- Lexical scopeのクロージャなので、クロージャの再帰呼出しではフレームのスタックが積まれることはありません。
「クロージャの再帰呼び出し」ではなく「クロージャの呼び出し」。ちなみに現在の実装ではフレームを積んでおきながら、呼び出しと同時にクロージャ定義時のフレームの参照に変更している。あとでなおす。

--- (その呼出しへの参照が残っていた場合、そこに保持されている。)
「その」と「そこ」が何を指しているかわからない。

--- クロージャの呼出し時にフレームの退避 --> クロージャの実行 --> フレームの復帰と行うと、クロージャの実行時に末尾再帰呼出しがあった場合フレームの退避 --> クロージャの実行 -->フレームの退避 --> クロージャの実行 --> フレームの復帰 --> フレームの復帰となります。
ここで、フレームの退避はlexical scopeクロージャの場合フレームの新規作製であり、作製されたフレームはクロージャの実行の終了とともにGCによって回収されるようになります。
ここでいう「フレームの退避」はフレームチェインに新しいフレームを作成すること。(新しいフレームは既存のフレームチェインにつなげられる) なんで「退避」と言う言葉を使ったのかわからない。 今考えると「フレームの退避」「フレームの復帰」は必要ないっぽい。(現在見えている変数フレームは継続スタックに保持されているじゃん) あとでなおす。

--- 結局クロージャの実行時にフレームの復帰の継続がどんどん増えていくことになります。フレームの復帰は最後のものだけ行えばよく、末尾再帰の場合、フレームの復帰の継続を作製する場合、次の継続にフレームの復帰があった場合継続の作製は行う必要はありません。

--- 以上のことから、フレーム復帰の継続の作製を抑制すれば末尾再帰の最適化になることになります。
現在の実装ではフレームの復帰が連続する場合その継続の作成を抑制しているがフレームの復帰は必要ないっぽい。あとでなおす。

Blog作りました

萌え指向プログラミング言語「萌香」を公開してから１年経ちました。

この一年何もしてないように見えていろいろやってたんですよ。エイトクィーンの記事を書こうと悪戦苦闘してたのですがなかなかうまく書けなくって。人にわかる文章書くのって難しいですね。

ほんとは一周年のときにエイトクィーンの記事くらいは書きたかったのですが、あきらめて中途半端ですが順列の作成プログラムをアップするだけにしました。(一応エイトクィーンのプログラムも出来てたはずなのですがどっかいっちゃった。)

今後ともよろしくお願いします。