5

I am writing a lambda calculus in F#, but I am stuck on implementing the beta-reduction (substituting formal parameters with the actual parameters).

(lambda x.e)f
--> e[f/x]

example of usage:

(lambda n. n*2+3) 7
--> (n*2+3)[7/n]
--> 7*2+3

So I'd love to hear some suggestions in regards to how others might go about this. Any ideas would be greatly appreciated.

Thanks!

4

1 に答える 1

4

式の表現が次のように見えると仮定すると

type expression = App of expression * expression
                | Lambda of ident * expression
                (* ... *)

のすべての自由なオカレンスをinにsubst (x:ident) (e1:expression) (e2:expression) : expression置き換える関数があり、通常の順序で評価したい場合、コードは次のようになります。xe1e2

let rec eval exp =
  match exp with
  (* ... *)
  | App (f, arg) -> match eval f with Lambda (x,e) -> eval (subst x arg e)

subst関数は次のように動作する必要があります。

関数適用の場合、両方の部分式で再帰的に自分自身を呼び出す必要があります。

ラムダの場合、ラムダの引数名が置換する識別子と同じでない限り、ラムダの本体式でそれ自体を呼び出す必要があります (この場合、識別子はその内部のどこにも自由に表示できないため、ラムダをそのままにしておくことができます)。

変数の場合、変数の名前が識別子と等しいかどうかに応じて、変数を変更せずに返すか、置換式を返す必要があります。

于 2010-10-28T09:35:37.660 に答える