2015年6月11日木曜日

SysRPLで再帰大作戦

SysRPLで再帰処理を書くにはどうするのか、気になって居りました。

ここでは、再帰処理による階乗計算の例を示しておきます。

!NO CODE
!RPL

::
  { LAM n } BIND

  LAM n %0 %> 
  ITE 
    ::  LAM n DUP %1 %- ID facto %*  ;
    ::  %1 ;
  ABND
;
@


これをASM でコンパイルし、スタックに載っているSysRPLコードを「'facto' STO 」とやって保存すると使える様になります。CK2とか使っていないので、パラメタは決め打ちです。実数として明確にスタックに数を置き、引き続いてfacto と打ち込みます。
例えば、70の階乗を求めるには、「70. facto」とやってやります。70の後に少数点をつけて実数とするのです。

実は、局所変数に関数定義を束縛し、呼び出すという技法があります。

SysRPL Recursion Question - comp.sys.hp48
https://groups.google.com/forum/#!topic/comp.sys.hp48/JrtXN0bz1QU

上記ではAckermann functionの例が出ておりますが、こちらでは上と同じく階乗の例を示しておきます。

!NO CODE
!RPL

::
  '
  :: 
    { LAM n } BIND
    LAM n %0=
    ITE
      :: %1 ;
      :: LAM n %1- LAM facto EVAL LAM n %* ;
    ABND
  ;
  { LAM facto } BIND
  LAM facto EVAL
  ABND
;
@

冒頭の「'」は、以降のプログラム節 (「::」と「;」で括られたもの) をQuoteする、というものです。これにより、

  :: 
    { LAM n } BIND
    LAM n %0=
    ITE
      :: %1 ;
      :: LAM n %1- LAM facto EVAL LAM n %* ;
    ABND
  ;

の部分を実行(評価)せずに、「そのまま」の状態でスタックに置く、というイメージです。続く「{ LAM facto } BIND」によって局所変数(シンボル)facto に束縛します。
更に「LAM facto EVAL」で、factoシンボルに束縛されたプログラム節をEVALにて評価する事で、実行します。
最後は「ABND」で、BINDで束縛した局所シンボルスコープを脱し、プログラムの終了という具合です。

4 件のコメント:

Sentaro さんのコメント...

akatuki様、一気におつかれさまです!

階乗はプロ電やポケコン買ったらまず試しに書くプログラムでしたけど、50Gでの再帰処理、とても参考になります。
ありがとうございます!(^^)

SysRPLの方は最近覚えたての名無しのローカル変数ですが、プログラム部分しかダメな感じですね。
さすがにfactoの方は名前無しには出来ないみたいです(^^;

階乗は昔から69までしかできなかったのが70以上いけるのが海外製電卓の強みですよね。
CASIOも海外のClaspadでは指数が499まで拡張されてますけど、国内では相変わらず99までなのが惜しいところです。

akatuki さんのコメント...

Sentaro 様、こんばんは !

> 階乗はプロ電やポケコン買ったらまず試しに書くプログラムでしたけど、50Gでの再帰処理、とても参考になります。
> ありがとうございます!(^^)

いえいえ、こちらこそ。

> SysRPLの方は最近覚えたての名無しのローカル変数ですが、プログラム部分しかダメな感じですね。
> さすがにfactoの方は名前無しには出来ないみたいです(^^;

再帰処理で、関数名を必要しますからネ。
でも、何か面白いメカを考える「思い付き」がありそうです。

> 階乗は昔から69までしかできなかったのが70以上いけるのが海外製電卓の強みですよね。
> CASIOも海外のClaspadでは指数が499まで拡張されてますけど、国内では相変わらず99までなのが惜しいところです。

これは、50Gとかが、ある意味「キレていた」のだと思うのです。かなり前の製品ですから。
でも、既に「種まき」は終わったので、これからはここまで計算できる製品が増えてくる、と期待したいです。


ちなみに、CASモードのApproxのチェックを入れて計算すると、階乗はreal型で計算するので、253!が上限になってしまいますが、approxのチェックを外すとZINTで計算するので、もっと多くの桁で計算しますネ (ZINTの計算サービスに階乗計算がありました)。上限を調べていないので、どこまで計算するのか ? これも暇つぶしにはもってこい ... ?

Sentaro さんのコメント...

akatuki様、こんばんは!

>これは、50Gとかが、ある意味「キレていた」のだと思うのです。かなり前の製品ですから。

かなり前の世代から499まで使えていたのですよね。
TIは68KのTI-89から499になった感じでしょうか。
昔の機種からずっと見渡すとHPとTIの電卓開発競争は面白いです。


>ちなみに、CASモードのApproxのチェックを入れて計算すると、階乗はreal型で計算するので、253!が上限になってしまいますが、approxのチェックを外すとZINTで計算するので、もっと多くの桁で計算しますネ (ZINTの計算サービスに階乗計算がありました)。上限を調べていないので、どこまで計算するのか ? これも暇つぶしにはもってこい ... ?

全部の桁が正確に出るのが最初はびっくりでしたけど、多桁整数はCAS電卓ならではの特徴ですよね。
ってことで、approxチェックを外して何桁までいけるかやってみました。
実機だとかなり時間かかったのでエミュの方で時間短縮して(^^;
1000、2000と通過したので一気に10000としてみたらInteger too largeでエラーになりました。
ちょい減らして9999ならOkなので9999までっぽいですね。

akatuki さんのコメント...

Sentaro 様、こんばんは !

> かなり前の世代から499まで使えていたのですよね。
> TIは68KのTI-89から499になった感じでしょうか。
> 昔の機種からずっと見渡すとHPとTIの電卓開発競争は面白いです。

当方、TI-83+しか使っていないので良う判らんですが、TI-89辺りからというのは、恐らくその様です。
いま、HP28Sのマニュアルを見たら、この頃から499になっておりました。

> 全部の桁が正確に出るのが最初はびっくりでしたけど、多桁整数はCAS電卓ならではの特徴ですよね。

これは当方も驚いちゃったのですヨ。整数限定とは言え、きっちりと答が返って来るものですから。

> ってことで、approxチェックを外して何桁までいけるかやってみました。
> 実機だとかなり時間かかったのでエミュの方で時間短縮して(^^;

あっ、もうやっちゃったの !

> 1000、2000と通過したので一気に10000としてみたらInteger too largeでエラーになりました。
> ちょい減らして9999ならOkなので9999までっぽいですね。

ウーン。
9999が上限という辺り、「ここで打ち止め」という仕様の様ですネ。