東北大学工学研究科電気・情報系 2016年8月実施専門科目問題5 計算機2

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

日本語版

Fig. 5(a) の構文を持つプログラミング言語を考える。 $f(x_1,\ldots,x_k)=e$ によって定義されている関数呼出式 $f(e_1,\ldots,e_k)$ の評価方法として，以下の $2$ つの戦略を考える。

戦略 1：まず各 $e_i$ ，ただし $1\le i\le k$ ，を評価し，その値を $x_i$ とする。そして，関数の本体 $e$ を評価する。
戦略 2： $e_1,\ldots,e_k$ は評価せずに，関数の本体 $e$ 中の各 $x_i$ ，ただし $1\le i\le k$ ，の全ての出現を $e_i$ で置き換えた式 $e'$ を求める。そして，その式 $e'$ を評価する。

ただし，いずれの戦略においてもその他の式の評価方法は以下の通りである。

式	評価方法
$n$	評価結果は $n$ となる。
$(e_1+e_2)$	まず $e_1$ と $e_2$ を評価し，その結果をそれぞれ $n_1$ と $n_2$ とする。すると全体の式の評価結果は $n_1+n_2$ となる。
$(e_1-e_2)$	まず $e_1$ と $e_2$ を評価し，その結果をそれぞれ $n_1$ と $n_2$ とする。すると全体の式は評価結果は $n_1-n_2$ となる。
$(\mathrm{ifz}\ e_1\ \mathrm{then}\ e_2\ \mathrm{else}\ e_3)$	まず $e_1$ を評価する。その評価結果が $0$ であれば $e_2$ を評価し，そうでなければ $e_3$ を評価する。

たとえば，Fig. 5(b) のプログラムで定義された関数の下で，式 $f(1)$ は戦略 $1$ の下では

f(1)\to g(1,1)\to g(0,2)\to2

と評価され，戦略 $2$ の下では

f(1)\to g(1,1)\to g(1-1,1+1)\to1+1\to2

と評価される。このプログラムに関する以下の問に答えよ。

(1) 戦略 $1$ の下で $f(2)$ および $f(3)$ を評価せよ。評価の過程も示せ。

(2) 戦略 $1$ の下で，式 $e$ の評価で実行される加算の回数を $\#\operatorname{add1}(e)$ とおく。非負整数 $n$ に対し $\#\operatorname{add1}(f(n))$ を $n$ を用いて表せ。

(3) 戦略 $2$ の下で $f(2)$ を評価せよ。評価の過程も示せ。さらに，そのときに実行される加算の回数を数えよ。

(4) 戦略 $2$ の下で，式 $e$ の評価で実行される加算の回数を $\#\operatorname{add2}(e)$ とおく。非負整数 $n$ に対し $\#\operatorname{add2}(f(n))$ を $n$ を用いて表せ。

(5) あるプログラムの下の式 $e$ で， $\#\operatorname{add1}(e)>\#\operatorname{add2}(e)$ となるものが存在するか否かを判定し，その根拠を示せ。

Fig. 5(a)

プログラム
    p ::= d1 ... dn
関数定義
    d ::= f(x1,...,xn) = e
式
    e ::= n                          （整数定数）
        | x                          （変数）
        | (e1 - e2)                  （整数減算）
        | (e1 + e2)                  （整数加算）
        | f(e1,...,en)               （関数呼出し）
        | (ifz e1 then e2 else e3)    （条件分岐）

関数定義 “ $f(x_1,\ldots,x_n)=e$ ” において， $e$ 中に出現する変数の集合は $\{x_1,\ldots,x_n\}$ の部分集合であるとする。

Fig. 5(b)

f(x)   = g(x, 1)
g(x,y) = (ifz x then y else g((x - 1), (y + y)))

题目描述

语言表达式包括整数、变量、加减法、函数调用和条件式 ifz e1 then e2 else e3；条件值为零时求值 e2，否则求值 e3。两种函数调用策略为：

策略 1：先求实参值，再代入形参求值函数体。
策略 2：将未经求值的实参表达式代入函数体中对应变量的每次出现，再求值所得表达式；不共享重复求值结果。

考虑程序

f(x) = g(x, 1)
g(x, y) = ifz x then y else g(x - 1, y + y)

用策略 1 计算 $f(2),f(3)$ ，给出过程。
$\#add_1(e)$ 表示策略 1 计算 $e$ 时执行的加法次数。对 $n\ge0$ 求 $\#add_1(f(n))$ 。
用策略 2 计算 $f(2)$ ，并给出加法次数。
对 $n\ge0$ 求策略 2 的加法次数 $\#add_2(f(n))$ 。
是否存在某程序及表达式 $e$ ，使 $\#add_1(e)>\#add_2(e)$ ？说明理由。

Kai

(1)

f(2)\to g(2,1)\to g(1,2)\to g(0,4)\to\boxed4,

f(3)\to g(3,1)\to g(2,2)\to g(1,4)\to g(0,8)\to\boxed8.

(2)

每次递归先计算一次 $y+y$ ，共递归 $n$ 次，所以

\boxed{\#add_1(f(n))=n.}

(3)

策略 2 延迟实参求值，得到

f(2)\to g(2,1)\to g(2-1,1+1) \to g((2-1)-1,(1+1)+(1+1)).

末次条件求值为零，返回并计算 $(1+1)+(1+1)=4$ ，共执行 $\boxed3$ 次加法。

(4)

令 $Y_0=1,Y_{k+1}=Y_k+Y_k$ 。返回的表达式为 $Y_n$ ，它是含 $2^n$ 个叶子的满二叉加法树。因此

A_0=0,\quad A_{n+1}=2A_n+1,\qquad \boxed{\#add_2(f(n))=2^n-1.}

条件中只有减法，不增加此计数。

(5)

存在。例如定义 $h(x)=0$ ，取 $e=h(1+1)$ 。策略 1 先计算实参，执行一次加法；策略 2 中形参在函数体中未出现，不计算实参。因此

\boxed{\#add_1(e)=1>0=\#add_2(e).}

Author​

Description​

日本語版​

题目描述​

Kai​

(1)​

(2)​

(3)​

(4)​

(5)​

Author

Description

日本語版

题目描述

Kai

(1)

(2)

(3)

(4)

(5)