4

今後の Haskell 試験に向けて復習していますが、過去の論文の問題の 1 つが理解できません。Googleは何も役に立たない

fst(x, y) = x
square i = i * i

i) Haskells の遅延評価を使用して、次の式のソースを削減します。

fst(square(3+4), square 8)

ii) ソースリデュース、厳密な評価を使用、同じ式

iii) 遅延評価の利点と厳密評価の利点を 1 つ挙げてください

私が理解していないのは、ソース削減とは何ですか?

4

2 に答える 2

10

リダクションはラムダ計算からの用語で、1 つの用語を同等の用語に置き換えるセマンティクス保存変換を含みます。あなたが与えた例では、最も重要な種類の削減は

  • その定義による名前の置換 (equals を equals に置換するインスタンス)。
  • 関数適用のベータ削減。

ベータ還元はラムダ計算の基本的な規則であり、Haskell のような純粋で怠惰な言語では、常にセマンティクスが保持されます。ベータ ルールとは、次のようなものです。

(\x. e) m

をeに置き換えることができます。(置換は、 inの空きインスタンスを「キャプチャ」しないようにする必要があります。)mxxm

インストラクターが次のように削減を組み合わせることを望んでいる可能性は十分にあります。

  1. 適用される関数が名前である関数アプリケーションを見つけます。
  2. 名前をその定義に置き換えます。これはラムダ抽象化になります。
  3. アプリケーションをベータ削減します。
  4. このすべてを 1 ステップで実行します。

多くの場合、削減するアプリケーションを選択できることに注意してください。たとえば、あなたが与えた用語には、 の2つのアプリケーションがsquareあり、そのうちの1つはfstこの方法で削減できます。(+ の適用も還元できますが、定数を含む還元には別の規則が必要です。)

質問から、あなたのインストラクターは、各タームが正常な形になるまで繰り返し減数 することを望んでいることがわかりました。「source reduce」の「source」という言葉は不必要です。リダクションとは、ある言語でソース用語を操作することを意味します。私は次のように質問を表現したでしょう：

  • Haskell の遅延評価に対応する簡約戦略を使用して、次の式を弱頭正規形に簡約します。一連の削減の各ステップを示します。

  • 厳密な関数型言語での評価に対応する簡約戦略を使用して、次の式を頭部標準形に簡約します。

私はおそらく恥ずかしがらずに、削減戦略に名前を付けることにしました: call-by-need 削減戦略と call-by-value 削減戦略です。

于 2010-05-22T14:31:10.097 に答える
7

質問の構造からすると、おそらく「手で式を評価する」という意味です。

head (map primeTest (enumFromTo 1000 2000))

遅延 (必要な場合にのみ評価する) 評価では、

  head (map primeTest (enumFromTo 1000 2000))
= head (map primeTest (1000 : enumFromTo 1001 2000))
= head (primeTest 1000 : map primeTest (enumFromTo 1001 2000))
= primeTest 1000
= False

厳密な (最初にすべてを評価する) 評価

  head (map primeTest (enumFromTo 1000 2000))
= head (map primeTest (1000 : enumFromTo 1001 2000))
= ...
= head (map primeTest [1000, 1001, ..., 2000])
= head (primeTest 1000 : map primeTest [1001, 1002, ..., 2000])
= head (False : map primeTest [1001, 1002, ..., 2000])
= ...
= head [False, False, ..., False]
= False

私が見つけた唯一の関連する場所はhttp://www.cs.bham.ac.uk/internal/modules/2009/11582.htmlで、「ソース削減」が「プログラミング手法」としてリストされています。(O_O)

于 2010-05-22T11:45:15.810 に答える