1

：の形式の式が与えられた場合(* 3 (+ x y))、どのように式を評価して形式に入れることができ(+ (* 3 x) (* 3 y))ますか？（注：一般的な場合、3は任意の定数であり、「x」または「y」は単一変数または他のS式の項である可能性があります（例(+ 2 x)）。

元の式の項目（アトム？）を再帰的に評価し、それらが定数であるか用語であるかを判別するラムダ式を作成するにはどうすればよいですか？用語の場合、その用語のリスト内の各項目のタイプを判別するために、再帰的に再度評価する必要があります。

繰り返しますが、私にとっての問題の核心は、定義の再帰的な「カーネル」です。

式の最も深い部分の最後の単一のアトムに到達すると、それを決定するベースケースが明らかに必要になります。次に、「バックアップ」を再帰的に実行し、ルールに従って適切な形式で式を作成します。

Java / C ++のバックグラウンドから来ているので、Schemeでこれを構文的に行う方法を理解するのは非常に困難です。

4

2 に答える 2

4

元の問題から少し関連性のある問題に簡単に迂回してみましょう。次のように与えられたとします。次のような「文字列構築」式を取り、(* 3 "hello")それを「hellohellohello」に「評価」するエバリュエーターを作成するとします。私たちが仕事をしたい他の例には、次のようなものが含まれます

(+ "rock" (+ (* 5 "p") "aper"))     ==> "rockpppppaper"
(* 3 (+ "scis" "sors"))             ==> "scissorsscissorsscissors"

このような問題に取り組むには、入力の形状を正確に指定する必要があります。基本的に、データ型について説明します。入力は「文字列式」になると言います。str-exprsそれらを略して呼びましょう。次に、であるとはどういう意味かを定義しましょうstr-expr。

Astr-exprは次のいずれかです。

  1. <string>
  2. (+ <str-expr> <str-expr>)
  3. (* <number> <str-expr>)

str-exprこの表記法により、 sはすべてこれらの3つの形状のいずれかに適合すると言おうとしています。

データの形状がわかったら、処理する関数を作成するためのより良いガイドがありますstr-exprs。これらの3つの選択肢をケース分析する必要があります。

;; A str-expr is either:
;;      a plain string, or
;;     (+ str-expr str-expr), or
;;     (* number str-expr)

;; We want to write a definition to "evaluate" such string-expressions.

;; evaluate: str-expr -> string
(define (evaluate expr)
  (cond
    [(string? expr)
     ...]
    [(eq? (first expr) '+)
     ...]
    [(eq? (first expr) '*)
     ...]))

ここで、「...」は入力するものです。

実際、「...」についてもう少し記入する方法を知っています。2番目と3番目のケースでは、内部部分自体がstr-exprsであることがわかっています。これらは再発が発生する可能性のある主要な場所です。データはそれ自体で記述されているため、それらを処理するプログラムもおそらく自分自身を参照する必要があります。要するに、str-exprsを処理するプログラムは、ほぼ確実にこの形に従います。

(define (evaluate expr)
  (cond
    [(string? expr)
     ... expr 
     ...]
    [(eq? (first expr) '+)
     ... (evaluate (second expr))
     ... (evaluate (third expr))
     ...]
    [(eq? (first expr) '*)
     ... (second expr) 
     ... (evaluate (third expr))
     ...]))

これは、実際の作業を行うことなくすべてです。データの形状からわかるので、この部分を純粋に理解することができます。これをすべてうまくいくように残りの「...」を入力することは、実際にはそれほど悪くはありません。特に、作成したテストケースも考慮する場合はそうです。（コード）

あなたの質問の中心にあるのはこの種の標準的なデータ分析/ケース分析であり、HTDPなどのカリキュラムで広範囲にカバーされているものです。これはSchemeまたはRacket固有ではありません。Javaで同じ種類のデータ分析を行い、他の多くの場所でも同じ種類のアプローチが見られます。Javaでは、ケース分析に使用される低メカニズムは、おそらく動的ディスパッチを使用して、異なる方法で実行される可能性がありますが、コアとなるアイデアはすべて同じです。データを記述する必要があります。データ定義を取得したら、それを使用して、そのデータを処理するためにコードがどのように見える必要があるかをスケッチするのに役立てます。テストケースを使用して、スケッチの塗りつぶし方法を三角測量します。

于 2013-01-31T00:43:07.480 に答える
1

あなたはあなたの問題を分解する必要があります。まず、HtDP（www.htdp.org）のアプローチに従います。あなたのインプットは何ですか？それらを正確に指定できますか？この場合、これらの入力は自己参照になります。

次に、出力フォームを指定します。実際、上記のテキストはこれについて少しあいまいです。出力フォームがどのように見えるかはわかっていると思いますが、完全にはわかりません。

次に、一連のテストを記述します。これらは、入力用語の構造に基づいている必要があります。最も単純なものから始めて、そこから上に向かって作業します。

優れた一連のテストができたら、関数の実装は非常に簡単です。行き詰まったら喜んでお手伝いさせていただきます！

于 2013-01-30T23:28:30.593 に答える