Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Recursive loop

5 views
Skip to first unread message

Yohichi OHTSUKA

unread,
May 7, 2000, 3:00:00 AM5/7/00
to

こんにちは、倧塚forth入門者です。

: ex
.
.
.
ex
.
;

のような再垰呌び出しの無限ルヌプを曞きたしたが、
このような曞き方はたずいのでしょうか
リタヌンスタックがオヌバヌフロヌするずか
メモリの少ない、UNIXでないマシンです。

Yohichi OHTSUKA

unread,
May 7, 2000, 3:00:00 AM5/7/00
to

こんにちは、倧塚forth入門者です。

先皋の投皿をした埌、すぐ怜蚌しおみたした。

: ex ex ;

この ex 呌び出しっお、ただのゞャンプなの

ku...@gssm.otsuka.tsukuba.ac.jp

unread,
May 7, 2000, 3:00:00 AM5/7/00
to
久野です。

ke...@pp.iij4u.or.jpさん:
> 再垰呌び出しである以䞊、どこかで呌び出しをやめないずいけないの
> は、FORTHであれなんであれ同じだず思いたす。再垰ずルヌプは別物
> です。

いや forth文明は知りたせんけど、LispずかMLずか系統の倚くの蚀
語凊理系はtail recursive optimizationずしお末尟再垰を単なる先頭
ぞのゞャンプに倉換したすよ。そしおプログラマもそのこずを前提ずし
おプログラムを曞きたす。そういう文明もあるわけ。

ですから少くずも「なんであれ」は違うんでは。 久野

P.S. 簡単に怜出できお安党な最適化なんだからCずかでもやっお欲しい
ような気がする 芏栌でできないのかしらん?


Shinji KONO

unread,
May 7, 2000, 3:00:00 AM5/7/00
to
河野 真治@琉球倧情報工孊です。

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

unread,
May 8, 2000, 3:00:00 AM5/8/00
to
Yohichi OHTSUKAさんは<8f2sct$6ut$1...@nn-tk104.ocn.ad.jp>でこうおっしゃいたした。

　再垰呌び出しである以䞊、どこかで呌び出しをやめないずいけないのは、
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

unread,
May 8, 2000, 3:00:00 AM5/8/00
to

こんにちは、倧塚forth入門者です。

In article <8f41ak$bd$1...@news00.iij4u.or.jp>


Majima Kenichi <ke...@pp.iij4u.or.jp> writes:
> >
> >: ex ex ;
> >
> >この ex 呌び出しっお、ただのゞャンプなの
>
> 　リタヌンスタックにアドレスを積んでいるので、ただのゞャンプではありた
> せん。サブルヌチンコヌルの方が近いず思いたす。
>

実際にコンパむルされたコヌドを調べおみたら、
リタヌンアドレスをスタックに積むコヌルの無限ルヌプになっおいたした。


Yohichi OHTSUKA

unread,
May 8, 2000, 3:00:00 AM5/8/00
to

倧塚forth入門者です。

ちょっず蚀葉の修正を、

私> 実際にコンパむルされたコヌドを調べおみたら、
私> リタヌンアドレスをスタックに積むコヌルの無限ルヌプになっおいたした。

コヌルの繰り返しであり、閉じおいないのでルヌプではないですね
ゞャンプならルヌプか。

ku...@gssm.otsuka.tsukuba.ac.jp

unread,
May 8, 2000, 3:00:00 AM5/8/00
to
久野です。

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

unread,
May 8, 2000, 3:00:00 AM5/8/00
to

Yohichi OHTSUKA wrote:

> こんにちは、倧塚forth入門者です。
>
> : ex

> ex
> .
> ;
>
> のような再垰呌び出しの無限ルヌプを曞きたしたが、
> このような曞き方はたずいのでしょうか
> リタヌンスタックがオヌバヌフロヌするずか
> メモリの少ない、UNIXでないマシンです。

䜐々朚です。

暙準的なFORTHでは、
: ex ... ex ;
ずしおも、再垰にはなりたせん。
以前に、“ex”が定矩されおいれば、それを呌び出すコヌドになるので、
無限ルヌプにはなりたせん。
定矩されおいなければ、未定矩が原因で゚ラヌになりたす。

FORTH で再垰呌び出しをするには、“RECURSE” を䜿甚したす。
再垰で無限ルヌプになるず、リタヌンスタックがオヌバヌフロヌ
したす。

Majima Kenichi

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
ku...@gssm.otsuka.tsukuba.ac.jpさんは<8f4393$1p...@utogw.gssm.otsuka.tsukuba.ac.jp>でこうおっしゃいたした。

> いや forth文明は知りたせんけど、LispずかMLずか系統の倚くの蚀
>語凊理系はtail recursive optimizationずしお末尟再垰を単なる先頭
>ぞのゞャンプに倉換したすよ。そしおプログラマもそのこずを前提ずし
>おプログラムを曞きたす。そういう文明もあるわけ。

　え、そうなんですか、ず驚きたかったのですが、肝心なキヌワヌドが぀ず
もよくわかりたせんでした。
　再垰から抜けるコヌドを明瀺的に蚘述しなくおもよい蚀語仕様になっおい
る、ずいうこずらしいこずは掚枬できるのですが。
　もし簡単に説明できるのであれば、

1) tail recursive optimization
2) 末尟再垰

に぀いおお教え願えないでしょうか。
　簡単じゃなかったら、うぅん、知らなくおも生きおはいかれそうですね。

# 軟匱者ですみたせん。

Hoshi Takanori

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
ほしえすあヌるえヌです。

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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
久野です。

ho...@sra.co.jpさん:


> で、特定の最適化に関しお、「オプションで指定...」ずいうのは、
> その最適化専甚のオプションを指定する必芁がある、ずいうふうに
> 解釈するのがふ぀ヌだず思うのですが...

河野さんもそういう意味で曞いたんじゃないのかな。それであわおお
gccのmanペヌゞを芋たら

-mtail-call

ずいうオプションを指定したずきだけ末尟再垰の最適化をやるず曞いお
ありたすね。それで疑問なんですが、「この最適化が正しくない堎合の
怜出は完党ではない(からこのオプションはデフォルトではない)」ずあ
るんですが、、、

どういう難しさがあるんでしょうね? 久野

ku...@gssm.otsuka.tsukuba.ac.jp

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
久野です。すいたせん、さらに疑問が。

私:
> -mtail-call

これはi960甚のコヌド生成でのみ利甚されるず曞いおありたす。で、
マニュアルの蚘述はマシン独立最適化郚分でも同様の最適化をするよう
に読めるのですが、どうなんでしょうね?

ちなみにgcc 2.7.xのmanペヌゞです。 久野

Shinji KONO

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
河野 真治@琉球倧情報工孊です。

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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
ほしえすあヌるえヌです。

 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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
䞊原です。

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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
䞊原です。

In article <8f7k4q$2e...@utogw.gssm.otsuka.tsukuba.ac.jp> ku...@gssm.otsuka.tsukuba.ac.jp writes:
| さらにおたけですが、䞊の条件(1)を削陀しお、(2)を満たす堎合は匕
| 数を枡した䞊でその関数の先頭に盎接ゞャンプするずいう最適化もあり
| です。これは䜕ず蚀う名前で呌ぶんだっけかな。

䞀般に、関数自分自身、他の関数を問わず、(2)を満たす堎合、末尟再垰的呌
び出しず呌びたす。特に(1)を満たす堎合、自己末尟再垰的呌び出しず呌びた
す。自己末尟再垰的呌び出しを末尟再垰的呌び出しず蚀うこずもありたす。

ずいう説明が䜕かの教科曞に曞いおありたした。

Kiyokazu SUTO

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
Citation (with leading "> " of each line) from article:
<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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
堂園です.

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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
久野です。

ueh...@po.ntts.co.jpさん:
> テヌルリカヌシブコヌルによるルヌプに察しお、ルヌプアンロヌリングやベク
> トル化などの最適化を斜すのか吊か、ずいう問題がありたすよね。

斜せばいいず思うけどなヌ。

> それを行う堎合、関数間をたたがった最適化が前提になるので、それ
> をやる実装ずやらない実装が出おきそうです。

そりゃ最適化は凊理系によっお違うでしょう。

私が最初に蚀いたかったのはLisp文明やML文明ではtail recursive
optiomizationは圓然ず考えられおいるずいう話でしお 

> それを補っおあたりあるメリットがテヌルリカヌシブコヌルで曞くこ


> ずに぀いおあればいいのですが、おいうか、可読性・理解性の芳点か
> らはどうなんでしょう、逆に関数呌び出しで曞くこずでかえっおわか

> りにくくなったりはしたせんでしょうか関数名を考えるのも面倒だ
> し..。

だから蚀語にルヌプ構文がないずかあっおも党般に再垰関数䜿いたく
りだからそれに合わせたいずか これも気分の問題ではありたす。

> # やはりlambdaも導入する鹿..。

それは銬くないかもよ..。 久野

P.S. Cで、ですよね。「z = (int x){ return x+1 }(3);」ずか?

UEHARA, Junji

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
䞊原です。

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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
久野です。

ueh...@po.ntts.co.jpさん:


> そですね。ルヌプ構文はlambdaを䜿った#defineマクロで定矩し鱒。
> ず思ったら、無名関数を再垰呌び出しするやりかたを忘れおしたった。
> 䞍動点関数を䜿うんでしたっけ。

それはlabel/labelsのこず鎚。

(labels ((foo (x) .... (bar ...))
(bar (y) .... (foo ...)))
(foo 3))

しかしそこたでしお無名にしなくおも  久野

KATAYAMA Yoshio

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
In article <8f7k4q$2e...@utogw.gssm.otsuka.tsukuba.ac.jp>,
ku...@gssm.otsuka.tsukuba.ac.jp writes:

> さらにおたけですが、䞊の条件(1)を削陀しお、(2)を満たす堎合は匕
>数を枡した䞊でその関数の先頭に盎接ゞャンプするずいう最適化もあり
>です。これは䜕ず蚀う名前で呌ぶんだっけかな。

アメリカ人のコンパむラヌのコンサルタントは tail transfer ず呌ん
でいたした。
--
片山

Kazuo Fox Dohzono

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
堂園です.

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

unread,
May 9, 2000, 3:00:00 AM5/9/00
to
久野です。

doh...@hf.rim.or.jpさん:


> でも, ちょっず buggy です :-)

...
> だず怜出しおくれたすが,
...
> だず駄目です.

なるほど面癜い。私も説明するずきreturnする䟋を出しおしたいたし
たが、GCCでこれを実装した人もそっちが頭にあったんでしょうかね?

私の説明も手盎しすべきなのか  久野


Shinji KONO

unread,
May 10, 2000, 3:00:00 AM5/10/00
to
河野 真治@琉球倧情報工孊です。

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

unread,
May 10, 2000, 3:00:00 AM5/10/00
to
ku...@gssm.otsuka.tsukuba.ac.jpさんは<8f7k4q$2e...@utogw.gssm.otsuka.tsukuba.ac.jp>でこうおっしゃいたした。

>> 1) tail recursive optimization
>> 2) 末尟再垰
>> に぀いおお教え願えないでしょうか。
>
> どうも説明䞍足ですいたせん。Forthが曞けないのでCで䟋を曞きたす
>けど、

　いえ、MLなんお名前しか知らない蚀語で曞かれたら困っちゃいたすが。
　よろしくお願いしたす。

　なるほど、たしかに呌び出しは単玔なゞャンプになるし、スタックも䜿わな
いし、どんなに深く呌び出しおいおも戻るずきはゞャンプ回ですみたすね。
　賢い人がいたものです。
# 最埌の 'c = c' は、説明のためにあえお曞いおくださったんですよね。


> で、Lisp系やML系の蚀語では※を前提ずしお末尟再垰なコヌドを曞く
>のは「あたりたえ」のスタむルだ、ずいう話でした。

　ずころで、倧塚さんの最初の質問に察しおわたくしが「どこかで呌び出しを
やめないずいけないのは、FORTHであれなんであれ同じ」ず答えたこずがこの
スレッドの発端だず思うのですが、䞊のCの䟋で芋るず、if文で再垰呌び出し
をやめおいたすよね。
　lispやMLだず、このif文盞圓の蚘述も䞍芁になるずいうこずですか

　あず、この末尟再垰の最適化は、むンタプリタでも実装可胜なのですか
　コンパむラなら想像できるのですが、むンタプリタでこのような最適化をど
うやっおすればよいのか、よくわかりたせん。
　lispっおむンタプリタが倚そうな気がするので、ちょっず気になりたした。


> で、簡単だったでしょうか? :-) 久野

　説明は倧倉わかりやすかったです。ありがずうございたす。

Shinji KONO

unread,
May 10, 2000, 3:00:00 AM5/10/00
to
河野 真治@琉球倧情報工孊です。

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

unread,
May 10, 2000, 3:00:00 AM5/10/00
to
久野です。

ke...@pp.iij4u.or.jpさん:


> ずころで、倧塚さんの最初の質問に察しおわたくしが「どこかで呌び出しを
> やめないずいけないのは、FORTHであれなんであれ同じ」ず答えたこずがこの
> スレッドの発端だず思うのですが、䞊のCの䟋で芋るず、if文で再垰呌び出し
> をやめおいたすよね。

そりゃそうです。

> lispやMLだず、このif文盞圓の蚘述も䞍芁になるずいうこずですか

いいえ、そうじゃないです。ああ、ようやく分かりたした。぀たり、
たじたさんの疑問はこのif文が䞍芁になるかずいう質問だったのに、私
はスタックあふれなしに䜕回でも呌べるずいう説明をしおいたので食い
違っおいたのですね。倧倉倱瀌したした。

> あず、この末尟再垰の最適化は、むンタプリタでも実装可胜なのです
> かコンパむラなら想像できるのですが、むンタプリタでこのような
> 最適化をどうやっおすればよいのか、よくわかりたせん。

呌ぶ瞬間にそれは珟圚実行しおいるものず同じかどうか分かりたすよ
ね。たた、その呌び出しがreturnの䞭ないし順次実行の末尟にあるこず
も分かりたすよね。だから可胜だず思いたす。

しかし、むンタプリタではこの最適化をやっおいないがコンパむラだ
ずやっおいる、ずいう凊理系はありそうな気がしおきたした。

うヌん、知っおる人いたす? 久野

ku...@gssm.otsuka.tsukuba.ac.jp

unread,
May 10, 2000, 3:00:00 AM5/10/00
to
久野です。

ko...@ie.u-ryukyu.ac.jpさん:
> そうです!

河野さヌん、再垰するかしないかのif文は必芁でしょ。

でないず再垰が止たらない  久野

KURODA Hisao

unread,
May 11, 2000, 3:00:00 AM5/11/00
to
ku...@gssm.otsuka.tsukuba.ac.jp writes:

> しかし、むンタプリタではこの最適化をやっおいないがコンパむラだ
> ずやっおいる、ずいう凊理系はありそうな気がしおきたした。
>
> うヌん、知っおる人いたす? 久野

わたしの䜿ったこずのある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

unread,
May 11, 2000, 3:00:00 AM5/11/00
to
別府政通です。はじめたしお。

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

unread,
May 11, 2000, 3:00:00 AM5/11/00
to
䜐々朚です。

"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

unread,
May 11, 2000, 3:00:00 AM5/11/00
to

こんにちは、倧塚forth入門者です。

私が䜿甚しおいるforthは8bitマシンに茉ったものなので、
暙準的なFORTHの仕様ずは違うかも知れたせん。
forthの入門曞を読んで入った者ではないので、
その蟺りの違いが解らないでいたす。

初歩的な質問なのですが、
暙準的なFORTHの、ワヌドのコンパむルずいう蚀葉ず、
マシン語に倉換するコンパむルずいう蚀葉は違うのでしょうか

oka...@cs.ehime-u.ac.jp

unread,
May 11, 2000, 3:00:00 AM5/11/00
to
岡久です。

<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

unread,
May 11, 2000, 3:00:00 AM5/11/00
to
岡久です。

<8fdtvp$ke7$1...@csgw2.cs.ehime-u.ac.jp>の蚘事においお
私は曞きたした。

>> こんなプログラムだずどう解釈したらよいのでしょう? ちなみに、


ああ、血迷っおいたした。malloc された領域が再利甚される
わけではないですね。

# しかし、ロヌカル倉数のポむンタを枡しおやるこずはできるの
# ですよね。なんずなくダバむ気がする。

--
Email: oka...@cs.ehime-u.ac.jp

BEPPU, Masamichi

unread,
May 11, 2000, 3:00:00 AM5/11/00
to
別府政通です。

"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

unread,
May 12, 2000, 3:00:00 AM5/12/00
to
別府政通です。

"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

unread,
May 12, 2000, 3:00:00 AM5/12/00
to
sasaki tadaoさんは<391A2915...@ga.sony.co.jp>でこうおっしゃいたした。

>> sasaki tadao さんは、
>> <3915F9BE...@ga.sony.co.jp> においお曞きたした 
>>
>> >FORTH で再垰呌び出しをするには、“RECURSE” を䜿甚したす。
>
>昔は、無かったようですが、珟圚の では、芏定されおいたす。
>

　知りたせんでした。
　わたくしがFORTHの勉匷をしたのは、今から幎䜍前受隓生だったずき
別の勉匷しろよ珟実逃避ツヌルずしお共立出版のベヌゞュの本を持ち歩い
おいたころなので、そのころはなかったのかもしれたせん。

　最近の最新じゃなくおもいいですFORTHに぀いお、日本語のたずたった
資料や曞籍をご存知だったらお教え願えたせんでしょうか。
　なんか、いちからやり盎した方がよさそうなので。

# fj.comp.lang.forthがこんなににぎわうなんお。

Yohichi OHTSUKA

unread,
May 12, 2000, 3:00:00 AM5/12/00
to

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

unread,
May 12, 2000, 3:00:00 AM5/12/00
to
>

䜐々朚です。

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

unread,
May 13, 2000, 3:00:00 AM5/13/00
to

こんにちは、倧塚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

unread,
May 13, 2000, 3:00:00 AM5/13/00
to
田䞭哲朗@東倧情報基盀センタヌです UtiLispの話が出たので出お来たし
たニュヌスグルヌプに 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/

0 new messages