Recursive loop
Yohichi OHTSUKA
こんにちは、大塚＠forth入門者です。
: ex
.
.
.
ex
.
;
のような再帰呼び出しの無限ループを書きましたが、
このような書き方はまずいのでしょうか？
（リターンスタックがオーバーフローするとか？）
メモリの少ない、UNIXでないマシンです。
Yohichi OHTSUKA
こんにちは、大塚＠forth入門者です。
先程の投稿をした後、すぐ検証してみました。
: ex ex ;
この ex 呼び出しって、ただのジャンプなの？
ku...@gssm.otsuka.tsukuba.ac.jp
ke...@pp.iij4u.or.jpさん:
> 再帰呼び出しである以上、どこかで呼び出しをやめないといけないの
> は、FORTHであれなんであれ同じだと思います。再帰とループは別物
> です。
いや…forth文明は知りませんけど、LispとかMLとか系統の多くの言
語処理系はtail recursive optimizationとして末尾再帰を単なる先頭
へのジャンプに変換しますよ。そしてプログラマもそのことを前提とし
てプログラムを書きます。そういう文明もあるわけ。
ですから少くとも「なんであれ」は違うんでは。 久野
P.S. 簡単に検出できて安全な最適化なんだからCとかでもやって欲しい
ような気がする…規格でできないのかしらん?
Shinji KONO
In article <8f4393$1p...@utogw.gssm.otsuka.tsukuba.ac.jp> ,
ku...@gssm.otsuka.tsukuba.ac.jp writes
>P.S. 簡単に検出できて安全な最適化なんだからCとかでもやって欲しい
> ような気がする…規格でできないのかしらん?
いくつかそれをするコンパイラはあります。が、オプションで指定
する方が普通のようです。
int fact(int i,int j)
{
if (i<=0) return j;
else return fact(i-1,j*i);
}
を -O でコンパイルすると、
fact:
pushl %ebp
movl %esp,%ebp
movl 8(%ebp),%edx
movl 12(%ebp),%eax
.L8:
testl %edx,%edx
jle .L6
imull %edx,%eax
decl %edx
jmp .L8
.align 4
.L6:
leave
ret
となります。
> いや…forth文明は知りませんけど、LispとかMLとか系統の多くの言
>語処理系はtail recursive optimizationとして末尾再帰を単なる先頭
>へのジャンプに変換しますよ。そしてプログラマもそのことを前提とし
>てプログラムを書きます。そういう文明もあるわけ。
というか、それをしないと実用的なコンパイラと言われないですね。
stack が爆発して、GC しまくるので...
---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科
Majima Kenichi
再帰呼び出しである以上、どこかで呼び出しをやめないといけないのは、
FORTHであれなんであれ同じだと思います。
再帰とループは別物です。
ここに再帰のサンプルがありました。
http://lab.ee.uec.ac.jp/text/forth/prog/recursion.txt
Yohichi OHTSUKAさんは<8f308a$h0e$1...@nn-tk104.ocn.ad.jp>でこうおっしゃい
ました。
リターンスタックにアドレスを積んでいるので、ただのジャンプではありま
せん。（サブルーチン）コールの方が近いと思います。
--
/*******************************
Majima Kenichi
ke...@pp.iij4u.or.jp
*******************************/
Yohichi OHTSUKA
こんにちは、大塚＠forth入門者です。
In article <8f41ak$bd$1...@news00.iij4u.or.jp>
Majima Kenichi <ke...@pp.iij4u.or.jp> writes:
> >
> >: ex ex ;
> >
> >この ex 呼び出しって、ただのジャンプなの？
>
> リターンスタックにアドレスを積んでいるので、ただのジャンプではありま
> せん。（サブルーチン）コールの方が近いと思います。
>
実際にコンパイルされたコードを調べてみたら、
リターンアドレスをスタックに積むコールの無限ループになっていました。
Yohichi OHTSUKA
大塚＠forth入門者です。
ちょっと言葉の修正を、
私> 実際にコンパイルされたコードを調べてみたら、
私> リターンアドレスをスタックに積むコールの無限ループになっていました。
コールの繰り返しであり、閉じていないのでループではないですね！
ジャンプならループか。
ku...@gssm.otsuka.tsukuba.ac.jp
ke...@pp.iij4u.or.jpさん:
> 1) tail recursive optimization
> 2) 末尾再帰
> についてお教え願えないでしょうか。
どうも説明不足ですいません。Forthが書けないのでCで例を書きます
けど、
int lookup(char *s, char c) {
if(*s == '\0')
return 0;
else if(*s == c)
return 1;
else
return lookup(s+1, c); /**/
}
つまり文字列sの中に文字cがあるかどうか調べるという再帰関数を作っ
たとします。/**/のlookupの呼び出しは
(1) 自分自身への呼び出しであり、
(2) 戻ってきた後することは返値をそのまま自分の返値として
returnするだけ。
です。このような性質を持つ再帰呼び出しを「末尾再帰」(tail
recursion)と呼びます。tail recursion optimizationというのは、
末尾再帰を呼び出しのかわりに引数の置き換え+先頭へのジャンプに
書き換えるという最適化を言います。上の例なら次のようになります。
int lookup(char *s, char c) {
top:
if(*s == '\0')
return 0;
else if(*s == c)
return 1;
else {
s = s + 1; c = c; goto top; }
}
このような最適化はプログラムの意味を変更せず、なおかつ関数呼び出
し/戻りのオーバヘッドが削減できるため大変効果的です。また、見た
目は再帰でありながらループになっちゃうのでいくら多数回回ってもス
タックがあふれることもありません※。
で、Lisp系やML系の言語では※を前提として末尾再帰なコードを書く
のは「あたりまえ」のスタイルだ、という話でした。
さらにおまけですが、上の条件(1)を削除して、(2)を満たす場合は引
数を渡した上でその関数の先頭に直接ジャンプするという最適化もあり
です。これは何と言う名前で呼ぶんだっけかな。
> 簡単じゃなかったら、うぅん、知らなくても生きてはいかれそうですね。
で、簡単だったでしょうか? :-) 久野
sasaki tadao
Yohichi OHTSUKA wrote:
> こんにちは、大塚＠forth入門者です。
>
> : ex
> ex
> .
> ;
>
> のような再帰呼び出しの無限ループを書きましたが、
> このような書き方はまずいのでしょうか？
> （リターンスタックがオーバーフローするとか？）
> メモリの少ない、UNIXでないマシンです。
佐々木です。
標準的なFORTHでは、
: ex ... ex ;
としても、再帰にはなりません。
以前に、“ex”が定義されていれば、それを呼び出すコードになるので、
無限ループにはなりません。
定義されていなければ、未定義が原因でエラーになります。
FORTH で再帰呼び出しをするには、“RECURSE” を使用します。
再帰で無限ループになると、リターンスタックがオーバーフロー
します。
Majima Kenichi
> いや…forth文明は知りませんけど、LispとかMLとか系統の多くの言
>語処理系はtail recursive optimizationとして末尾再帰を単なる先頭
>へのジャンプに変換しますよ。そしてプログラマもそのことを前提とし
>てプログラムを書きます。そういう文明もあるわけ。
え、そうなんですか、と驚きたかったのですが、肝心なキーワードが２つと
もよくわかりませんでした。
再帰から抜けるコードを明示的に記述しなくてもよい言語仕様になってい
る、ということらしいことは推測できるのですが。
もし簡単に説明できるのであれば、
1) tail recursive optimization
2) 末尾再帰
についてお教え願えないでしょうか。
簡単じゃなかったら、うぅん、知らなくても生きてはいかれそうですね。
# 軟弱者ですみません。
Hoshi Takanori
In article <18644.9...@rananim.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> いくつかそれをするコンパイラはあります。が、オプションで指定
> する方が普通のようです。
gcc などに -O をつけないと、「最適化は一切するな」という
指示になります。(よね？)
で、特定の最適化に関して、「オプションで指定...」というのは、
その最適化専用のオプションを指定する必要がある、というふうに
解釈するのがふつーだと思うのですが...
ほし
ku...@gssm.otsuka.tsukuba.ac.jp
> で、特定の最適化に関して、「オプションで指定...」というのは、
> その最適化専用のオプションを指定する必要がある、というふうに
> 解釈するのがふつーだと思うのですが...
河野さんもそういう意味で書いたんじゃないのかな。それであわてて
gccのmanページを見たら
-mtail-call
というオプションを指定したときだけ末尾再帰の最適化をやると書いて
ありますね。それで疑問なんですが、「この最適化が正しくない場合の
検出は完全ではない(からこのオプションはデフォルトではない)」とあ
るんですが、、、
どういう難しさがあるんでしょうね? 久野
ku...@gssm.otsuka.tsukuba.ac.jp
私:
> -mtail-call
これはi960用のコード生成でのみ利用されると書いてあります。で、
マニュアルの記述はマシン独立最適化部分でも同様の最適化をするよう
に読めるのですが、どうなんでしょうね?
ちなみにgcc 2.7.xのmanページです。 久野
Shinji KONO
In article <8f7n0n$2e...@utogw.gssm.otsuka.tsukuba.ac.jp> ,
ku...@gssm.otsuka.tsukuba.ac.jp writes
> 河野さんもそういう意味で書いたんじゃないのかな。それであわてて
>gccのmanページを見たら
と思ったんだけど、factorial ぐらいだと -O で末尾最適化される
みたいですね。
> どういう難しさがあるんでしょうね? 久野
return recursive(....) で、本当に処理が終るかどうかを検出す
るのがめんどうとか? alloca() とか、auto_ptr とかはちょっと困
りますよね。逆に、
recursive(....);
break;
...
}
if() ....;
...
return();
とかあった時に、本当に終了するのかどうか良く分からないとか...
Hoshi Takanori
＃ x86 の gcc-2.7.2.3 で試したところ、河野さんのおっしゃる
＃ 通り、gcc -O で tail recursion の最適化が行なわれました。
＃ また、-mtail-call は Invalid option になりました。
In article <8f7n76$2e...@utogw.gssm.otsuka.tsukuba.ac.jp>
ku...@gssm.otsuka.tsukuba.ac.jp writes:
> これはi960用のコード生成でのみ利用されると書いてあります。で、
> マニュアルの記述はマシン独立最適化部分でも同様の最適化をするよう
> に読めるのですが、どうなんでしょうね?
>
> ちなみにgcc 2.7.xのmanページです。 久野
gcc の info (Node: Passes) によると、RTL generation の段階で
tail recursion も検出されるそうです。さらに、tail-recursive
な関数は inline 展開も可能 (！) だそうです。
で、-mtail-call ですが、gcc の場合、-m で始まるオプションは
各 cpu に特化したものなので、i960 固有の問題があるということ
ではないでしょうか？
ほし
UEHARA, Junji
In article <8f4393$1p...@utogw.gssm.otsuka.tsukuba.ac.jp>
ku...@gssm.otsuka.tsukuba.ac.jp writes:
| P.S. 簡単に検出できて安全な最適化なんだからCとかでもやって欲しい
| ような気がする…規格でできないのかしらん?
テールリカーシブコールによるループに対して、ループアンローリングやベク
トル化などの最適化を施すのか否か、という問題がありますよね。それを行う
場合、関数間をまたがった最適化が前提になるので、それをやる実装とやらな
い実装が出てきそうです。そうなった場合、一般にはループはループ構文でやっ
たほうがより最適化が期待できる、という不文律が普及しそうです。そうなっ
た場合に、移植を暗黙に・明示的に前提とした開発でテールリカーシブコール
が積極的に使われるかどうか疑問です。それを補ってあまりあるメリットがテー
ルリカーシブコールで書くことについてあればいいのですが、ていうか、可読
性・理解性の観点からはどうなんでしょう、逆に関数呼び出しで書くことでか
えってわかりにくくなったりはしませんでしょうか？関数名を考えるのも面倒だし..。
# やはりlambdaも導入する鹿..。
--
§NTTS○FT 技術開発部エレクトロニックコマース技術センター 上原 潤二 §
PGP Key fingerprint = B7 C0 CB 1F 1C 88 69 2A 25 36 8A EE 93 A3 61 72
UEHARA, Junji
In article <8f7k4q$2e...@utogw.gssm.otsuka.tsukuba.ac.jp> ku...@gssm.otsuka.tsukuba.ac.jp writes:
| さらにおまけですが、上の条件(1)を削除して、(2)を満たす場合は引
| 数を渡した上でその関数の先頭に直接ジャンプするという最適化もあり
| です。これは何と言う名前で呼ぶんだっけかな。
一般に、関数自分自身、他の関数を問わず、(2)を満たす場合、末尾再帰的呼
び出しと呼びます。特に(1)を満たす場合、自己末尾再帰的呼び出しと呼びま
す。自己末尾再帰的呼び出しを末尾再帰的呼び出しと言うこともあります。
という説明が何かの教科書に書いてありました。
Kiyokazu SUTO
<8f7k4q$2e...@utogw.gssm.otsuka.tsukuba.ac.jp>
by ku...@gssm.otsuka.tsukuba.ac.jp :
> さらにおまけですが、上の条件(1)を削除して、(2)を満たす場合は引
> 数を渡した上でその関数の先頭に直接ジャンプするという最適化もあり
> です。これは何と言う名前で呼ぶんだっけかな。
「Revised(5) Report on the Algorithmic Language」では「Proper tail
recursion」という用語を使っています。
# 「tail merge」という言葉もどっかで見たことがあるような。
--
須藤 清一 <su...@ks-and-ks.ne.jp>
http://pub.ks-and-ks.ne.jp/pgp-public-key.html
(ところでjlug.*を知っていますか？)
Kazuo Fox Dohzono
In article <8f7n0n$2e...@utogw.gssm.otsuka.tsukuba.ac.jp>
ku...@gssm.otsuka.tsukuba.ac.jp writes:
> -mtail-call
これ, i960 用のオプションですね. ということで
> どういう難しさがあるんでしょうね?
アーキテクチャに依存した部分ではないかと想像します (-mtail-call につい
ては).
あと,
| This man page is not kept up to date except when volun-
| teers want to maintain it.
ということですのでなるべく info に頼るのがよろしいでしょう.
--
Kazuo Fox Dohzono / doh...@hf.rim.or.jp
[12],(6,9),0,0,2
ku...@gssm.otsuka.tsukuba.ac.jp
ueh...@po.ntts.co.jpさん:
> テールリカーシブコールによるループに対して、ループアンローリングやベク
> トル化などの最適化を施すのか否か、という問題がありますよね。
施せばいいと思うけどなー。
> それを行う場合、関数間をまたがった最適化が前提になるので、それ
> をやる実装とやらない実装が出てきそうです。
そりゃ最適化は処理系によって違うでしょう。
私が最初に言いたかったのはLisp文明やML文明ではtail recursive
optiomizationは当然と考えられているという話でして…
> それを補ってあまりあるメリットがテールリカーシブコールで書くこ
> とについてあればいいのですが、ていうか、可読性・理解性の観点か
> らはどうなんでしょう、逆に関数呼び出しで書くことでかえってわか
> りにくくなったりはしませんでしょうか？関数名を考えるのも面倒だ
> し..。
だから言語にループ構文がないとかあっても全般に再帰関数使いまく
りだからそれに合わせたいとか…これも気分の問題ではあります。
> # やはりlambdaも導入する鹿..。
それは馬くないかもよ..。 久野
P.S. Cで、ですよね。「z = (int x){ return x+1 }(3);」とか?
UEHARA, Junji
In article <8f85cn$2i...@utogw.gssm.otsuka.tsukuba.ac.jp> ku...@gssm.otsuka.tsukuba.ac.jp writes:
| だから言語にループ構文がないとかあっても全般に再帰関数使いまく
| りだからそれに合わせたいとか…これも気分の問題ではあります。
| > # やはりlambdaも導入する鹿..。
|
| それは馬くないかもよ..。 久野
|
| P.S. Cで、ですよね。「z = (int x){ return x+1 }(3);」とか?
そですね。ループ構文はlambdaを使った#defineマクロで定義し鱒。
と思ったら、無名関数を再帰呼び出しするやりかたを忘れてしまった。
不動点関数を使うんでしたっけ。
ku...@gssm.otsuka.tsukuba.ac.jp
> そですね。ループ構文はlambdaを使った#defineマクロで定義し鱒。
> と思ったら、無名関数を再帰呼び出しするやりかたを忘れてしまった。
> 不動点関数を使うんでしたっけ。
それはlabel/labelsのこと鴨。
(labels ((foo (x) .... (bar ...))
(bar (y) .... (foo ...)))
(foo 3))
しかしそこまでして無名にしなくても… 久野
KATAYAMA Yoshio
ku...@gssm.otsuka.tsukuba.ac.jp writes:
> さらにおまけですが、上の条件(1)を削除して、(2)を満たす場合は引
>数を渡した上でその関数の先頭に直接ジャンプするという最適化もあり
>です。これは何と言う名前で呼ぶんだっけかな。
アメリカ人のコンパイラーのコンサルタントは tail transfer と呼ん
でいました。
--
片山＠ＰＦＵ
Kazuo Fox Dohzono
In article <HOSHI.00M...@srapc332.sra.co.jp>
ho...@sra.co.jp (Hoshi Takanori) writes:
> gcc の info (Node: Passes) によると、RTL generation の段階で
> tail recursion も検出されるそうです。
でも, ちょっと buggy です :-)
int
ipow (int *p, int i, int j)
{
if (i <= 0) return *p = j;
else return ipow (p, i-1, i*j);
}
だと検出してくれますが,
void
ipow (int *p, int i, int j)
{
if (i <= 0) *p = j;
else ipow (p, i-1, i*j);
}
だと駄目です.
ku...@gssm.otsuka.tsukuba.ac.jp
> でも, ちょっと buggy です :-)
...
> だと検出してくれますが,
...
> だと駄目です.
なるほど面白い。私も説明するときreturnする例を出してしまいまし
たが、GCCでこれを実装した人もそっちが頭にあったんでしょうかね?
私の説明も手直しすべきなのか… 久野
Shinji KONO
In article <8f9qs5$djl$1...@netnews.rim.or.jp> ,
doh...@hf.rim.or.jp (Kazuo Fox Dohzono) writes
>でも, ちょっと buggy です :-)
まぁ、コンパイラは安全側に持っていくものだから...
>void
>ipow (int *p, int i, int j)
>{
> if (i <= 0) *p = j;
> else ipow (p, i-1, i*j);
>}
>だと駄目です.
おお、不思議だ。return 値がないと最適化しないという単純な
ことなのかな。
Majima Kenichi
>> 1) tail recursive optimization
>> 2) 末尾再帰
>> についてお教え願えないでしょうか。
>
>けど、
いえ、MLなんて名前しか知らない言語で書かれたら困っちゃいますが。
よろしくお願いします。
なるほど、たしかに呼び出しは単純なジャンプになるし、スタックも使わな
いし、どんなに深く呼び出していても戻るときはジャンプ１回ですみますね。
賢い人がいたものです。
# 最後の 'c = c' は、説明のためにあえて書いてくださったんですよね。
> で、Lisp系やML系の言語では※を前提として末尾再帰なコードを書く
>のは「あたりまえ」のスタイルだ、という話でした。
ところで、大塚さんの最初の質問に対してわたくしが「どこかで呼び出しを
やめないといけないのは、FORTHであれなんであれ同じ」と答えたことがこの
スレッドの発端だと思うのですが、上のCの例で見ると、if文で再帰呼び出し
をやめていますよね。
lispやMLだと、このif文相当の記述も不要になるということですか？
あと、この末尾再帰の最適化は、インタプリタでも実装可能なのですか？
コンパイラなら想像できるのですが、インタプリタでこのような最適化をど
うやってすればよいのか、よくわかりません。
lispってインタプリタが多そうな気がするので、ちょっと気になりました。
> で、簡単だったでしょうか? :-) 久野
説明は大変わかりやすかったです。ありがとうございます。
Shinji KONO
In article <8fbt0m$sdu$1...@news00.iij4u.or.jp> ,
Majima Kenichi <ke...@pp.iij4u.or.jp> writes
> lispやMLだと、このif文相当の記述も不要になるということですか？
そうです!
> あと、この末尾再帰の最適化は、インタプリタでも実装可能なのですか？
> コンパイラなら想像できるのですが、インタプリタでこのような最適化をど
>うやってすればよいのか、よくわかりません。
> lispってインタプリタが多そうな気がするので、ちょっと気になりました。
可能です。LISP は特に関数呼出しが重いのが多かったし、stack
の消費を押えるのも重要だったので、インタプリタでも重要な技術
でした。
インタプリタでも、関数呼出し時にスタックの操作はおこなうので、
末尾再帰最適化は、その操作を省略することに相当します。
Sparc の UTI-LISP では、register window の操作が重いので、(動かない
時は良いのだが、動かして register window がoverflow するとひどい目に
あう)、なるべく、register window の操作をおくらせるなんてことを
していたようです。和田英一先生は、LISP はインタプリタが高速である
必要があると考えていたようですね。
ku...@gssm.otsuka.tsukuba.ac.jp
> ところで、大塚さんの最初の質問に対してわたくしが「どこかで呼び出しを
> やめないといけないのは、FORTHであれなんであれ同じ」と答えたことがこの
> スレッドの発端だと思うのですが、上のCの例で見ると、if文で再帰呼び出し
> をやめていますよね。
そりゃそうです。
> lispやMLだと、このif文相当の記述も不要になるということですか？
いいえ、そうじゃないです。ああ、ようやく分かりました。つまり、
まじまさんの疑問はこのif文が不要になるかという質問だったのに、私
はスタックあふれなしに何回でも呼べるという説明をしていたので食い
違っていたのですね。大変失礼しました。
> あと、この末尾再帰の最適化は、インタプリタでも実装可能なのです
> か？コンパイラなら想像できるのですが、インタプリタでこのような
> 最適化をどうやってすればよいのか、よくわかりません。
呼ぶ瞬間にそれは現在実行しているものと同じかどうか分かりますよ
ね。また、その呼び出しがreturnの中ないし順次実行の末尾にあること
も分かりますよね。だから可能だと思います。
しかし、インタプリタではこの最適化をやっていないがコンパイラだ
とやっている、という処理系はありそうな気がしてきました。
うーん、知ってる人います? 久野
ku...@gssm.otsuka.tsukuba.ac.jp
KURODA Hisao
> しかし、インタプリタではこの最適化をやっていないがコンパイラだ
> とやっている、という処理系はありそうな気がしてきました。
>
> うーん、知ってる人います? 久野
わたしの使ったことのあるLucid Common LispとAllegro Common Lispは
そうでした。
;;CLOSで末尾再帰期待して書くと痛い目にあうんですよね;_;
--
;;; $Id: .signature,v 1.3 1996/09/20 07:06:26 kuroda Exp $
(define (くろだ ひさお)
(email kur...@msi.co.jp))
BEPPU, Masamichi
sasaki tadao さんは、
<3915F9BE...@ga.sony.co.jp> において書きました…
>FORTH で再帰呼び出しをするには、“RECURSE” を使用します。
"RECURSE"…、知りませんでした。
私が FORTH 処理系を 8 年前に X68000 向けに実装した（@Niftyのプログラミ
ング言語フォーラム:FPLからダウンロード可能です）時に、参考にした
古い FIG-FORTH には無いんですよね、このワード。
無い場合は、これに相当するワードを自前で、定義することになります。
処理系に依存しますが、多くの場合簡単に実現できると思います。
たとえば、私の処理系では以下のようにして、ワード myself として実現して
います。
: myself ( --- ) ( 再帰的表現を可能にするワード )
latest lfa>cfa , ; immediate
これによって、現在コンパイル中のワードの実行開始アドレスを自分自身
に書き込むことができます。
各ワードを説明するには、処理系の辞書構造から説明しないといけないので、
ここでは省略します。
以上は、処理系によっては再帰用ワードを作成可能であるという実例です。
では。
＃最近の FORTH 処理系は扱ったことが無いので、ほとんど浦島太郎です。
--
BEPPU, Masamichi @ KOZO KEIKAKU ENGINEERING Inc.
e-mail: mas...@kke.co.jp
sasaki tadao
"BEPPU, Masamichi" wrote:
> 別府政通です。はじめまして。
>
> sasaki tadao さんは、
> <3915F9BE...@ga.sony.co.jp> において書きました…
>
> >FORTH で再帰呼び出しをするには、“RECURSE” を使用します。
>
> "RECURSE"…、知りませんでした。
> 無い場合は、これに相当するワードを自前で、定義することになります。
> 処理系に依存しますが、多くの場合簡単に実現できると思います。
>
> たとえば、私の処理系では以下のようにして、ワード myself として実現して
> います。
>
> : myself ( --- ) ( 再帰的表現を可能にするワード )
> latest lfa>cfa , ; immediate
>
>
> 各ワードを説明するには、処理系の辞書構造から説明しないといけないので、
> ここでは省略します。
>
> 以上は、処理系によっては再帰用ワードを作成可能であるという実例です。
>
> では。
昔は、無かったようですが、現在のＡＮＳＩ では、規定されています。
ＦＯＲＴＨに興味がある人なら下記のサイトは、一度は見ておいたほうが良いで
す。
http://www.taygeta.com/
ANSI FORTH のドキュメントは、以下から入手できます。
http://www.taygeta.com/forth/
win32forth と言う、ＯＯＰ な ＦＯＲＴＨも入手できます。
ーーーーーーーーーーーーーーーーーーーーーーーー
ところで、こんなワードはどうでしょうか。
: Coop R> R> SWAP >R >R ;
これをどう使うかと言うと、例えば、
: X ." a " Coop ." z " ;
: Q1 X ." b " Coop ." A-B-Z" ;
: Q2 X ." c " Coop ." A-C-Z" ;
Ｑ１を実行すると、 a b z A-B-Z
Ｑ２を実行すると、 a c z A-C-Z
となります。
コルーチンと言うんだったかな？
残念なことは、do ... loop のなかで使えないことですが、
それでも便利ですよ。
Yohichi OHTSUKA
こんにちは、大塚＠forth入門者です。
私が使用しているforthは8bitマシンに載ったものなので、
標準的なFORTHの仕様とは違うかも知れません。
forthの入門書を読んで入った者ではないので、
その辺りの違いが解らないでいます。
初歩的な質問なのですが、
標準的なFORTHの、ワードのコンパイルという言葉と、
マシン語に変換するコンパイルという言葉は違うのでしょうか？
oka...@cs.ehime-u.ac.jp
<8f7k4q$2e...@utogw.gssm.otsuka.tsukuba.ac.jp>の記事において
ku...@gssm.otsuka.tsukuba.ac.jpさんは書きました。
>> (1) 自分自身への呼び出しであり、
>> (2) 戻ってきた後することは返値をそのまま自分の返値として
>> returnするだけ。
#include <stdio.h>
#include <stdlib.h>
struct well { int depth; struct well *under; };
int dig(int n, struct well *p)
{
p->depth = n;
p->under = malloc(sizeof(struct well));
if (p->under) return dig(n + 1, p->under);
return n;
};
int main()
{
struct well ground;
int depth;
depth = dig(0, &ground);
printf("%d\n", depth);
/* 末尾再帰のとき free できるのか? */
return 0;
}
こんなプログラムだとどう解釈したらよいのでしょう? ちなみに、
gcc のオプション無しでコンパイルして実行すると、Segmentation
fault になってしまいました。(スタックが溢れた?)
#(私信) ホームページの話をすっぽかしてしまってすいません。
--
Email: oka...@cs.ehime-u.ac.jp
oka...@cs.ehime-u.ac.jp
<8fdtvp$ke7$1...@csgw2.cs.ehime-u.ac.jp>の記事において
私は書きました。
>> こんなプログラムだとどう解釈したらよいのでしょう? ちなみに、
ああ、血迷っていました。malloc された領域が再利用される
わけではないですね。
# しかし、ローカル変数のポインタを渡してやることはできるの
# ですよね。なんとなくヤバイ気がする。
--
Email: oka...@cs.ehime-u.ac.jp
BEPPU, Masamichi
"Yohichi OHTSUKA" <yoht...@beige.ocn.ne.jp> wrote in message
news:<8fd9qa$t3e$1...@nn-tk104.ocn.ad.jp>...
>
> 私が使用しているforthは8bitマシンに載ったものなので、
> 標準的なFORTHの仕様とは違うかも知れません。
> forthの入門書を読んで入った者ではないので、
> その辺りの違いが解らないでいます。
長期出張の身で手元に資料がないので、私も詳しい違いは
わからないのですが、
８３年版標準 FORTH の場合は、FORTH83(またはFORTH-83)という
確認用ワードがあったと思います。
ANSI-FORTH にも同様なワードがあるかもしれません。
> 初歩的な質問なのですが、
> 標準的なFORTHの、ワードのコンパイルという言葉と、
> マシン語に変換するコンパイルという言葉は違うのでしょうか？
Java を思い浮かべていただけると理解が早いと思います。
ワードのコンパイルは、javac で *.java ファイルをコンパイルして
バイトコード(*.classファイル) を得る作業に相当します。
これで、実在のマイクロプロセッサに依存しない仮想のマイクロ
プロセッサ（VM:バーチャルマシン）用のマシン語を得ることでき
ます。
一方、マシン語へのコンパイルは、java の場合、ネイティブ・コード・
コンパイラにかけて、実在するマイクロプロセッサ向けのマシンコード
を生成する作業に相当します。一部のFORTH 処理系にも同様な、
ネイティブ・コード・コンパイラを持つものがあります。
ほかによい説明を思いつかないので、こんなとこですが、わかります
でしょうか？
BEPPU, Masamichi
"sasaki tadao" <ta...@ga.sony.co.jp> wrote in message
news:391A2915...@ga.sony.co.jp...
>
> 昔は、無かったようですが、現在のＡＮＳＩ では、規定されています。
> ANSI FORTH のドキュメントは、以下から入手できます。
> http://www.taygeta.com/forth/
なるほど…。
４年ほど前に ANS FORTH のドラフトを入手して
いたのですが、まだドラフトなのですね。 (^^;
> ところで、こんなワードはどうでしょうか。
＜省略＞
> コルーチンと言うんだったかな？
> 残念なことは、do ... loop のなかで使えないことですが、
面白いですね。ループ時に使用できるワードを作ってみるのも
一興かも知れません。
Majima Kenichi
>> sasaki tadao さんは、
>> <3915F9BE...@ga.sony.co.jp> において書きました…
>>
>> >FORTH で再帰呼び出しをするには、“RECURSE” を使用します。
>
>
知りませんでした。
わたくしがFORTHの勉強をしたのは、今から１０年位前（受験生だったとき
＞別の勉強しろよ）現実逃避ツールとして共立出版のベージュの本を持ち歩い
ていたころなので、そのころはなかったのかもしれません。
最近の（最新じゃなくてもいいです）FORTHについて、日本語のまとまった
資料や書籍をご存知だったらお教え願えませんでしょうか。
なんか、いちからやり直した方がよさそうなので。
# fj.comp.lang.forthがこんなににぎわうなんて。
Yohichi OHTSUKA
In article <8fehc5$lo8$1...@dosv008002.kke.co.jp>
"BEPPU, Masamichi" <mas...@kke.co.jp> writes:
> > 初歩的な質問なのですが、
> > 標準的なFORTHの、ワードのコンパイルという言葉と、
> > マシン語に変換するコンパイルという言葉は違うのでしょうか？
>
> Java を思い浮かべていただけると理解が早いと思います。
>
> ワードのコンパイルは、javac で *.java ファイルをコンパイルして
> バイトコード(*.classファイル) を得る作業に相当します。
> これで、実在のマイクロプロセッサに依存しない仮想のマイクロ
> プロセッサ（VM:バーチャルマシン）用のマシン語を得ることでき
> ます。
>
> 一方、マシン語へのコンパイルは、java の場合、ネイティブ・コード・
> コンパイラにかけて、実在するマイクロプロセッサ向けのマシンコード
> を生成する作業に相当します。一部のFORTH 処理系にも同様な、
> ネイティブ・コード・コンパイラを持つものがあります。
>
> ほかによい説明を思いつかないので、こんなとこですが、わかります
> でしょうか？
Javaは名前ぐらいなのですが、別府さんが解説してくれたことは、
だいたい解りました。
ということは、
標準的なFORTHコンパイラの流れは、
FORTHソース ----> マイクロプロセッサに依存しない ------> 各マシン語コード
実行コード
と考えてよいのでしょうか？
更に続きますが、
FORTHを起動して対話的にワードを入力して実行している時は、上の
マイクロプロセッサに依存しない実行コードが処理されて動いて
いると考えてよいのでしょうか？
最後に、
標準的なFORTHで、Cコンパイラみたいにライブラリ、スタートアップルーチン
をリンクしてa.outを作るみたいな自立型のコードを吐くことは出来るので
しょうか？
この場合どのようなワードが割り当てられているのでしょうか？
＃ ？マークばかりですみません。
sasaki tadao
佐々木です。
Yohichi OHTSUKA wrote:
> >In article <8fehc5$lo8$1...@dosv008002.kke.co.jp>
> > "BEPPU, Masamichi" <mas...@kke.co.jp> writes:
> >
> >
> >標準的なFORTHコンパイラの流れは、
> >
> >FORTHソース ----> マイクロプロセッサに依存しない ------> 各マシン語コード
> > 実行コード
> >
> >と考えてよいのでしょうか？
むしろ、次のようになっています。
FORTHソース ---+---> マイクロプロセッサに依存しないコード（ハイレベルワード）
|
+---> 各マシン語コード（ローレベルワード）
“：”で定義されるワードは、ハイレベルワードです。
“CODE”で定義されるワードも有って、これは、ローレベルワードと呼んでいます。
> >
> >更に続きますが、
> >FORTHを起動して対話的にワードを入力して実行している時は、上の
> >マイクロプロセッサに依存しない実行コードが処理されて動いて
> >いると考えてよいのでしょうか？
対話的かどうかは、ワードの実行には関係しませんね。対話する部分もFORTHの
ワードの一つにすぎません。
ハイレベルワードの中身は、他のワードへのポインタ（ポインタのポインタの
場合もある。むしろこちらが多い。）がリストになった物です。
このリストを手繰っていくと、そのうちに、ローレベルワードに行き着くので、
そこで、マシン語として実行されます。
＃モトローラの６８０９では、この手繰る動作が１命令で実行できたので、
＃サブルーチンコールより高速でした。
＃（オートインクリメント付きのレジスタ間接ジャンプ）
ワードの中身が、他のワードへのポインタの場合、「ダイレクト スレッド コード」
と呼ばれ、ポインタのポインタの場合、「インダイレクト スレッド コード」と
呼ばれています。
標準的でないFORTHの場合、ハイレベルワードを
call aaa
call bbb
の様に、マシン語として実行できる形にするものも有りました。
標準的なワードは、この call 部分を取り除いて、 aaa、bbbの
部分だけをならべたものと考えれば良いでしょう。
> >
> >最後に、
> >標準的なFORTHで、Cコンパイラみたいにライブラリ、スタートアップルーチン
> >をリンクしてa.outを作るみたいな自立型のコードを吐くことは出来るので
> >しょうか？
> >この場合どのようなワードが割り当てられているのでしょうか？
> >
> >＃ ？マークばかりですみません。
標準のワードは無いと思いますが、“win32forth”では、“turnkey”と言う
ワードが用意されていて、独立したアプリケーションが作れます。
＃コマンドラインが使えるなら、立ち上げたいワードをコマンドで入力すれば
＃いいんで、BATファイルから実行すれば、同じ事。
Yohichi OHTSUKA
こんにちは、大塚＠forth入門者です。
佐々木さん、私の質問に関する回答ありがとうございます。
お陰で、まだ消化不良の部分はあるのですが、標準的なFORTHの
実体像というものが見えてきました。
http://www-lab.ee.uec.ac.jp/subject/text/forth/struct-unix/st5.html と
佐々木さんの説明を読んでイメージしました。
In article <391BAFBE...@ga.sony.co.jp>
sasaki tadao <ta...@ga.sony.co.jp> writes:
>
> 標準的でないFORTHの場合、ハイレベルワードを
> call aaa
> call bbb
> の様に、マシン語として実行できる形にするものも有りました。
> 標準的なワードは、この call 部分を取り除いて、 aaa、bbbの
> 部分だけをならべたものと考えれば良いでしょう。
>
私が現在使用しているFORTHはこのタイプです。
Tetsuro TANAKA
た．ニュースグループに fj.comp.lang.lisp も加えます．
> インタプリタでも、関数呼出し時にスタックの操作はおこなうので、
> 末尾再帰最適化は、その操作を省略することに相当します。
> Sparc の UTI-LISP では、register window の操作が重いので、(動かない
> 時は良いのだが、動かして register window がoverflow するとひどい目に
> あう)、なるべく、register window の操作をおくらせるなんてことを
> していたようです。和田英一先生は、LISP はインタプリタが高速である
> 必要があると考えていたようですね。
この話の流れからすると，SPARC用の UtiLisp(UtiLisp/C) のインタプリタが
末尾再帰最適化をおこなっていたかと誤解する人もいるかもしれないので補足
します．UtiLisp/Cを作る際にインタプリタの高速実行に重点を置いたのは確
かですが，末尾再帰最適化はおこなっていませんでした．それは以下の理由に
よります．
・ UtiLispは CommonLispやSchemeと違い，変数は動的スコープを基本として
います．そのため，末尾再帰の際にどの変数束縛を開放して良いのかの判断を
おこなわなくてはいけなくなるため，コストがかかります．
以下の toy program を見て下さい．
(defun trec (x)
(print `(,x ,y))
(cond ((0= x) 1)
(t (lets ((y (1- y))) ; (a)
(trec (1- x)))))) ; (b)
(defun test ()
(lets ((y 5))
(trec 3))) ; (c)
最初の trecの呼出時(c)で x に 3 を束縛し，次の lets(a) で y に 4を束
縛します．letsの中の trec(b) は末端再帰なので，静的スコープのLispでは，
すべての束縛をクリアした上で，x に 2 を束縛すればいいのですが，動的ス
コープなので，y の束縛は残しておかなければなりません．一般的な連想リス
トや束縛スタックを使った変数束縛の実現法では，後から発生した束縛を残し
たまま，前の束縛を開放するのはコストがかかります．
・ UtiLisp/CはSPARCプロセッサで実行する際の速度を重視しながらも，移植
性も考慮して大部分をC言語で実装しました．C言語で記述して末尾再帰最適化
を実現するには，
1. Cの関数を継続(continuation)を返す形で記述して，インタプリタのメイ
ンループは
for(;;){
cont = (*cont)();
}
のように tiny(mini) interpreter で記述する．
2. Lispインタプリタ全体を1つのC関数にして，コントロールスタックを自分
で管理して，call をスタックのpushとgoto文に置き換える．
3. C言語の出力した アセンブリ言語のファイルをフィルタにより call を使
わない形に書き換える．
などの方法がありますが，これらはインタプリタ全体の書き換えが必要になり，
全体での速度向上につながるかどうかわからなかったので採用しませんでした．
> Sparc の UTI-LISP では、register window の操作が重いので、(動かない
> 時は良いのだが、動かして register window がoverflow するとひどい目に
> あう)、なるべく、register window の操作をおくらせるなんてことを
> していたようです。
この部分ですが，実はあまり大したことはしていませんでした．内部から他
の関数を呼び出さない関数が，save, restoreをしないことを利用して，エラー
処理を関数呼び出しでおこなう代わりに，bus error等を発生させて signal
で捕まえるに書いたというだけです．
この工夫は UtiLisp/C を開発した 1988 年当時の SPARC プロセッサの特性，
当時のSunOS のレジスタウィンドウ処理のもとでは有効でしたが，現在ではほ
とんど性能には影響していないでしょう．
--
-
東京大学情報基盤センター 田中哲朗
http://www.tanaka.ecc.u-tokyo.ac.jp/~ktanaka/