Scheme 中置式から後置式へ

Question

こんばんは。こちらのカテゴリには初投稿になります。
ただいまScheme習いたて、はじめたばかりの大学一年生です。
二つ、どうしてもわからない問題があります。
問A　中置式リストを後置式リストに変換する関数を定義せよ
問B　後置式の数式リストmとリスト表現のスタックsを受け取り、sを用いてmを実行し、最終のsを返す関数stackMを定義せよ

という二問です。
Ａに関しては、
;; revP : list -> list
;; (revP (list 2 * (list 4 - 1)) should return (list 2 4 1 - *)
(define (revP l)
         (cond
           [(empty? l) empty]
           [else (cond
                   [(number? (first l)) (cons (first l) (revP (rest l)))]
                   [else ....]
まで考えましたが、これでは当然のごとくまったく動きません。。

Ｂに関して、
;; stackM : list, list -> list
;; (stackM (list 2 4 1 - *)) should return (list 6)
(define (stackM m s)
         (cond
           [(empty? m) empty]
           [(number? (first m))  ]
           [else....]))
と３つに分けるところまではヒントを見てわかったのですが、これから先どうすればいいのかわからないです。。

どなたかできればどうすればいいのかという方針をお教えいただけないでしょうか？かれこれ２時間以上考えていますがまったく出てきません。。　どうかよろしくお願いいたします。
最後に、長文の質問を最後までお読みくださりありがとうございました。

cametan_42 · Accepted Answer

随分モダンな書き方ですね。
Aに関して言うと、僕は後置記法は良く知りませんし、ましてや「演算子順位文法」なんて知らないんですが、次のコードが要求満たしてるのかしら?
確かめてみてください。

(define (revP l)
　(define (foo exp opr opd)
　　(cond
　　　[(empty? exp)
　　　　(append (reverse opd) opr)]
　　　[(number? (first exp))
　　　　(foo (rest exp) opr (cons (first exp) opd))]
　　　[(member (first exp) '(+ - * /))
　　　　(foo (rest exp) (cons (first exp) opr) opd)]
　　　[else
　　　　(foo (rest exp) opr
　　　　　　(append (reverse (foo (first exp) '() '())) opd))]))
　(foo l '() '()))

ここでのインデントは全角スペースなんで、コピペするんだったら気を付けてください。
実行例は次の通りです。

> > (revP '(2 * (4 - 1)))
(2 4 1 - *)
> (revP '((1 + 2) * (3 + 4)))
(1 2 + 3 4 + *)
> 

list関数使って入力しろ、って事なのかしら?
まあ、その場合は適当に改造して下さい(笑)。

こう言う場合の解説って難しいんですよね。

「ただいまScheme習いたて、はじめたばかりの大学一年生です。」

と言う情報だけじゃ、ちょっと良く分からん、と(笑)。
上のコードの場合、局所手続き使ってますけど、局所手続きとか習ってるんでしょうか?また、本当に「はじめたばかり」だとすると、確かに難しい問題だよな、とか思います。
まあ、不明な点があったらまた投稿して下さい。
コード自体は「一旦眺めてみれば」そんなに難しく無いんで、わりに分かりやすいんじゃないのかな、と思います。

cametan_42 · Answer

＞教科書は書き忘れましたが、「How to Design Programs」となっています。ちなみに授業はこれに沿ってやっているだけで生徒で実際にこの本を持っている人はいないです。

ああ、なるほど。実際「How to Design Programs」ご利用してるわけなんですね。
実はSICPってのは「コンピュータ科学の古典的名著」とは言われてるんですが、反面、これは「プログラミングの本ではない」と言う批判もある本なんです。ましてや「Schemeを使ったプログラミングを学ぶ本ではない」と言われていて……。
まあ、ある種、賛否両論なんですよ。
確かに、実際にSICPってのはむしろ「Schemeをアセンブリ言語代わりにして」コンピュータの動作を勉強しよう、って本なんですね。アセンブリがSchemeに置き換わってるだけで、内容は実に難しい。
んで、このSICPに対する「問題報告」の論文があるんです。

The Structure and Interpretation of the Computer Science Curriculum:
http://people.cs.uchicago.edu/~robby/pubs/papers/htdp-sicp-fdpe2002.pdf

この論文の著者名見てほしいんですが……そうなんです。この論文の著者達が「How to Design Programs」の著者達、なんです。
言わば、「How to Design Programs」ってのはSICPの問題点に気付いた利用者達が「プログラミング入門書」を作ろう、としたある種「挑戦」なんです。

＞Aについてですが、下のように途中まではできました。

はいはい。
でも形式的には最初に提示された形式の方が良いですね。迷いがありません。
こっちの形式では、個人的には「eはいらない」と思います。
つまり、こっちを土台としましょう。

＞(define (revP l)
＞(cond
＞[(empty? l) empty]
＞[else (cond
＞[(number? (first l)) (cons (first l) (revP (rest l)))]
＞[else ....]

まあ、「empty?」はともかくとして、emptyと言う容れ物は未定義なんで、これを空リスト'()として雛形としてみます。

(define (revP l)
　(cond
　　[(empty? l) '()]
　　[(number? (first l)) (cons (first l) (revP (rest l)))]
　　[else (revP (cdr l))...]

＞ここまで打って気づいたのですが、これってlの最初の要素がリストだったらうまく動きませんね。。。どうにかこれを回避できないでしょうか？

うん、その前に。
条件的には

1.lが空だったら?
2.(first l)が数値だったら?
3.その他

と考えています。
まあ、悪くないんですが、この場合「その他」が大雑把ですよね。
何故なら、(first l)が演算子の場合とリストの場合、と最低限「あと二つ」の状況が考えられるからです。
従って、「演算子順位文法」の正確さを今後将来的に詰めるにせよ、スタート地点としての条件分けは現時点、「最低限でも4つ」必要なんです。
まずここを解決しないとなりません。

＞どうにかこれを回避できないでしょうか？

結論から言うと「出来ます」。(first l)がリストの場合ですよね?
単純に言うと、

1.再帰の枠組みでrevPを(first l)に適用してしまう。
2.同時に再帰の枠組みでrevPを(rest l)にも適用してしまう。
3.1と2の計算で得られたリストを結合(append)してしまう。

これが方針です。
あんま最近は呼ばれないんですが、こう言う再帰を古い用語で「car-cdr再帰」と呼びます。それはリストのcar(first)にもcdr(rest)にも「同時に」再帰を適用するから、です。今風に言えばfirst-rest再帰とでも呼べば良いのでしょうか?呼びませんが(笑)。
実際にコード見た方が早いでしょう。最初の提示コードの方針に則れば、次のように書けるんです。

(define (revP l)
　(cond
　　[(empty? l) '()]
　　[(number? (first l)) (cons (first l) (revP (rest l)))]
　　[(member (first l) '(+ - * /)) (append (revP (rest l)) (list (first l)))]
　　[else (append (revP (first l)) (revP (rest l)))] ;ここが car-cdr 再帰
   ))

4番目のelse節を見てください。リストlをfirstとrestに分けて、同時にrevPを再帰呼び出しして、結果をappendで繋げています。これがここで使用できるテクニックです。
これで上手く動くのか?動くんですね、実は(笑)。
最低限、出題の数式やWikipediaの例くらいだったら問題無く動作します。

> (revP '(2 * (4 - 1)))
(2 4 1 - *)
> (revP '((1 + 2) * (3 + 4)))
(1 2 + 3 4 + *)
> 

もう一回復習です。
通常のリスト再帰の場合、抽象的には、リストのrestに対して再帰して、何らかの結果をconsするなりappendするなり、のパターンが多いです。「何らかの結果を」と言うところがミソで、つまり、ここが「リストのfirstに対しての再帰」でも全然構わない、と言うのがこの問題のポイントです。と言うか、tomotomo2309jpさん自作のコードの設計上でのポイントになる、って事ですね。
まあ、効率は正直な話あんま良く無いんですが(もっと言っちゃうと、課題を解いて出来るコードはどの道あまり効率良くなりそうにないんですが)、car-cdr再帰は時には非常に強力な解法を与えてくれるので、覚えておいた方が良いテクニックだと思いますよ。

cametan_42 · Answer

＞そこで早速#5でいただいた定義式をDr.Schemeに打ち込んでRunを押してみたのですが、evalが未定義ですとのエラーが表示されました。

う～ん、それはおかしいですね。
evalってのはLisp系言語の根底モデルの関数なんで「絶対ある」筈なのです。
(実際、ANSI Common Lispなんかではevalそのものは実装上「特に何が何でも必要のある関数」では無くなってるらしいんですが、いずれにせよ、Schemeなんかの「教育用Lisp」では概念説明上「絶対にある」手続きです)
DrSchemeのヴァージョンは何でしょうか?また、DrSchemeでは[言語の選択...]ってのがある筈なんですけど、多分Pretty Bigを選んだ方がいいと思います。
僕はMzScheme(DrScheme、と言うかPLT SchemeのCLI版)4.1.3使用してて、提示コードは問題無く走ってるんで、恐らく走る筈だと思います。また、[言語の選択...]でR5RSを選択すると、tomotomo2309jpさんが記述した「モダンなスタイル」のSchemeコーディングだと走らない可能性があるんで([]が認識不可、として引っかかる)、Pretty Bigを選んだ方が無難でしょう。

注:ちなみに、提示コードは本当は古き良きcar、cdr、cadr、null?等を使って組み立てたんですが、tomotomo2309jpさんの記述に合わせて、全てEmacsでわざわざ置換して「モダンスタイル」に変更したモノです。Schemeユーザーはfirst、rest、second、empty?ってあんま使わないんじゃないのか、と思います。微小ですが、「旧来のスタイル」の方が文字数が少ない＝タイピング量が減る、からです。意味は「モダンスタイル」の方が明解ではあるんですけどね(笑)。

＞いま大学の図書館で「Structure and Interpretation of Computer Programs」をみてevalに関する記述を探してみたのですが、洋書な上、evalの定義式もかなり複雑なもので、理解できませんでした。

ああ、第4章でしょ?
tomotomo2309jpさんは偉いです。早速本調べて、ってのはなかなか出来る事じゃありません。頭が下がります。
んで、定義式書いてるんでしょうが、実際問題SICPの第4章ってのは「LispでLispを作ろう」、現代っぽく言うと「仮想マシンの設計」やってんです。
従って、そこ見ても「理解出来ない」と言うのはtomotomo2309jpさんの責任じゃないです。初心者には複雑過ぎるんです。

＞SICPではevalは二つの引数を要求するものでした。evalとはどのようなものなのでしょうか？

単純に言うと、S式とそれが定義された環境の二つを引数にして取るんですが、SICPは脇に置いておいて、恐らく次の文書辺りで理解に対しては十二分なんじゃないのかな、と思います。

フォームと評価:
http://www.stdio.h.kyoto-u.ac.jp/~hioki/gairon-enshuu/SchemeNotes/eval-quote.html

eval使ったのは、Lisp系の入門書にも色々あって、最初に概念モデルとしてevalを導入段階で説明する教科書と、「もっと難しいLispモデルの真髄」と言う扱いで後半で扱う教科書と、2タイプあるんですよ。んで、tomotomo2309jpさんの大学ではどっちなんだろ?ってちょっと分からなかったんですね。
>>#4の方でも示唆されていましたが、本来あんまevalそのものは「積極的に」使うべきものでもないんです。「評価(evaluate)」を概念的に説明する関数なんで。また、eval使うとコードが汚く(笑)見えるのも事実なんです。
僕の場合は、「Scheme習いたてだ」ってんで、Wikipediaの「レジスタ上での計算部分」を面倒無く提示出来ないか、と、要するにあくまで「手抜き」の意味で使ったんで、本来あまり褒められたやり方じゃない、と思います(笑)。だから、「evalが分からん」と言うのなら、無理して理解しないで結構です。
一応、例えば単なるS式、評価を止める(クオート付きの)S式、evalの使用例を以下に提示してみます。

> (+ 1 2) ;単なるS式は
3　　　　　;自動で評価(evaluate)される
> '(+ 1 2) ;引用符(クオート)すると、
(+ 1 2)　　;評価は避けられる
> (eval '(+ 1 2))
3

3番目見ると分かりますが、要するにevalってのは「強制評価の為の」関数です。

＞ちなみに今は「Advanced student」を使っています。

ああ、やっぱそうでしょう。
[How to Design Programs]のカテゴリに含まれる選択言語は、MIT Pressの教科書、

How to Design Programs:
http://www.htdp.org/

の「副教材」目的のパッケージじゃなかったかしら?だからテキスト準拠の制限かかってるんじゃなかったかな?そして、そのテキストを使わないとあまり意味が無いような気がします。
だから、通常使用する場合は、制限を開放した「Pretty Big」使った方が良いでしょう。

cametan_42 · Answer

>>#4

＞「演算子の優先順位をどう取り扱うか」について全く触れられていません. 
＞#1 では「普通の式」を想定して「演算子順位文法」に触れたんだけど, そうでないならまたそれなりに考える必要があります.

そう。実はそうなんですよね。
ですから、「Scheme習いたて、はじめたばかりの大学一年生」である以上、どこまでが出題意図なのかちょっと分かんなかった、ってのがあります。
つまり、本格的に「演算子順位文法」が必要なのか、それとも題材的にリストの要素をreverseと同様に「並べ替えろ」だけが出題意図なのか。
本当に「Scheme習いたて、はじめたばかりの大学一年生」なら、恐らくそこまで複雑な出題意図は無いだろう、と読みました。
まあ、Bの出題に関しても触れましたが、全体的に「穴がある」問題なのは間違い無いです。従って、Wikipediaの例も照らし合わせながらどうなんだ、とやってたわけです(笑)。

＞「正確に 2個」です. 

そうでしょうね。Wikipedia見てても「そうならざるを得ないだろう」とは思いました。

と言うわけで、

＞"局所手続き"というものがどのようなものなのか

これは>>#4の方で書かれていた通りです。defineの中にdefine突っ込んだ形、ですね。
一応、どんな教科書使ってるのか不明だったんで、どう書こうかな、って悩んだんですが、大学で使われる由緒正しい教科書、SICPの表現例に合わせました。が、一般には局所関数、とかローカル関数、って言った方が通りが良いかもしれません。また、defineの中にdefineを突っ込んだ形はSICPの中でも比較的早く登場するんで、その形に準じました。
一般に、Lisp系言語では、プログラムの単位を「関数」と表現しますが、Schemeではどう言うわけか、正確には「手続き」(プロシージャ)と表現します。この二つは工学上の概念は若干違うんですが、一般には同じ、と考えてまあいいでしょう。出題でも「関数」と表現されていますね。
例えば#3のコードは次のように書いても全く同じように動作します。

(define (stackM m)
  (foo m '()))

(define (foo m s)
  (cond
   [(empty? m) s]
   [(number? (first m))
    (foo (rest m) (cons (first m) s))]
   [else
    (foo (rest m) (cons (eval (list (car m) (cadr s) (car s))) (cddr s)))]))

これだと初心者的に「見慣れた形」でしょう。
ただし、#3との違いと言うのは、上記の形で書くと、手続きfooを直接呼び出せる事です。当たり前ですよね。

> (foo '(2 4 1 - *) '())
(6)
> 

一方、#3のスタイルで書くと、fooは直接には「呼び出せません」。これがdefineの内側にdefineをぶち込む効果で、文字通り手続きを「局所化」してるんです。つまり、局所手続き状態のfooは「手続きstackM内に"於いて"のみ有効な」手続きとなる。まさしく「ローカル」な手続きになる、んです。

defineの中にdefineぶち込むのが気持ち悪い場合は、代わりにこう言う風にも書けます。

(define (stackM m)
　(letrec ((foo
　　　　　　(lambda (m s)
　　　　　　　(cond
　　　　　　　　[(empty? m) s]
　　　　　　　　[(number? (first m))
　　　　　　　　　(foo (rest m) (cons (first m) s))]
　　　　　　　　[else
　　　　　　　　　(foo (rest m)
　　　　　　　　　　(cons (eval (list (car m) (cadr s) (car s))) (cddr s)))]))))
　　(foo m '())))

こう言う「letrec」と言う専用に局所関数を作り出すものもあります。
(既に習ってるかしら?)

Tacosan · Answer

実はこの問題, 致命的な欠点を抱えています. つまり「演算子の優先順位をどう取り扱うか」について全く触れられていません. しかも例がしょぼいのでどうしていいか全く分かりません.
たとえば 2+3*4 を 14 とするか 20 とするか, あるいは 1-2-3 を -4 とするか 2 とするかによって, 後の話がまったく違ってきます. #1 では「普通の式」を想定して「演算子順位文法」に触れたんだけど, そうでないならまたそれなりに考える必要があります.
なお, 後置式 (逆ポーランド記法) や前置式 (ポーランド記法) では基本的に演算子ごとに被演算子の個数が決まっています＞#3. 「2引数＊まで＊」ではなく「正確に 2個」です. なぜなら「そうしないとどこまでが演算子なのかわからない」からです. Lisp などでは可変個の引数を取れますが, これは「引数を含めてカッコでくくっているので区別ができる」という事情によります.
なお, 局所手続きというのは「特定の手続きの中でのみ使える手続き」です. #2 や #3 で define構文の中に define構文が入っていますが, このようにすると「中の define構文で定義されたものを外で使うことはできない」ようになります.
あと, 演算子まで含めて list でつくるなら eval も不要だったりしますね.

cametan_42 · Answer

え～と、Bの方はAに比べると簡単なんですが……。
ちょっと問題の方が不明瞭なんですよね。
と言うのも、本文見る限り、

＞後置式の数式リストmとリスト表現のスタックsを受け取り、sを用いてmを実行

って書いてるんで「二引数関数かな?」と思いきや、例示では

＞(stackM (list 2 4 1 - *)) should return (list 6)

ってんで、これじゃ一引数関数です。
「どっちやねん?」って事ですね(笑)。
しょーがないんで、Wikipediaの

逆ポーランド記法:
http://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95

の「計算動作」を参考にして実装、です。
SchemeなんかのLisp系言語では、加算、減算、乗算、除算、なんかの基本演算子は、好きなだけ引数取れるんですが、どうやら逆ポーランド記法の例見る限り、「二引数まで」と言う限度があるみたいですね。
つまり、縛りとしては、

1 2 3 +

なんてのはダメなんでしょう。
まあ、かと言って別にエラー返すようにはしませんでしたが、それはさておき、レジスタの計算代わりにeval使っていいのかな?これもちょっと分かりません(笑)。大学が何狙って何を使わせたいのか不明なんで、しょーがないんで、eval使ってデッチ上げます(笑)。

(define (stackM m)
　(define (foo m s)
　　(cond
　　　[(empty? m) s]
　　　[(number? (first m))
　　　　(foo (rest m) (cons (first m) s))]
　　　[else
　　　　(foo (rest m) (cons (eval (list (first m) (second s) (first s))) (cddr s)))]))
　(foo m '()))

これも全角インデントなんで、コピペするなら気をつけて下さい。
また、これも局所手続き使用してます。この辺もテクニックはAの回答と同様です。
実行例は以下の通り。

> (stackM '(2 4 1 - *))
(6)
> (stackM '(1 2 + 3 4 + *))
(21)
> 

とまあ、こんな感じでしょうか。

Tacosan · Answer

B は「自分で計算できれば」簡単.
A の方はむずかしくて, 「演算子順位文法」なんかを参考にするのがよいかと.

Scheme 中置式から後置式へ

随分モダンな書き方ですね。

＞教科書は書き忘れましたが、「How to Design Programs」となっています。

＞そこで早速#5でいただいた定義式をDr.Schemeに打ち込んでRunを押してみたのですが、evalが未定義ですとのエラーが表示されました。

>>#4

実はこの問題, 致命的な欠点を抱えています. つまり「演算子の優先順位をどう取り扱うか」について全く触れられていません. しかも例がしょぼいのでどうしていいか全く分かりません.

え～と、Bの方はAに比べると簡単なんですが……。

B は「自分で計算できれば」簡単.

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング