IS CS-2024S-04

题目来源：Problem 4 日期：2024-08-17 题目主题：CS-Programming Languages-Call-by-Value vs. Call-by-Name

解题思路

在这道题中，我们主要研究了函数 $f(x)$ 在不同调用策略下的行为。为了回答所有问题，我们首先需要理解如何在 C 语言风格的伪代码中用“值调用”（call-by-value）来执行 $f(x)$ 函数。然后，我们将这些分析扩展到“名调用”（call-by-name）的情况下，并最终寻找在不同调用策略下表现不同的程序示例。

Solution

1. Number of Calls of the Function $f$ During the Evaluation of $f(2)$

First, let’s evaluate $f(2)$ step by step:

$$f(2)\to f(f(0))\to f(1)\to f(f(-1))\to f(0)\to 1$$

To summarize:

• $f(2)$ calls $f(0)$,
• $f(0)$ directly returns $1$,
• $f(f(0))$ is equivalent to $f(1)$ which involves 3 calls as shown in the question statement.

Thus, the total number of calls during the evaluation of $f(2)$ is 5.

2. Showing that the Return Value of $f(n)$ is 1 for Every Non-Negative Integer $n$

Let’s prove this statement by induction on $n$.

Base Case: For $n=0$, we have:

$$f(0)=0+1=1$$

So, $f(0)=1$.

Inductive Step: Assume that $f(k)=1$ for all $k<n$ where $n$ is some positive integer. Consider $f(n)$:

$$f(n)\to f(f(n-2))$$

By the inductive hypothesis, $f(n-2)=1$ (since $n-2\ge 0$). Hence,

$$f(f(n-2))=f(1)=1$$

Therefore, by induction, $f(n)=1$ for all non-negative integers $n$.

3. Number of Calls of the Function $f$ During the Evaluation of $f(n)$ in Terms of $n$

To determine the number of calls during $f(n)$, observe the recursive pattern:

$$f(n)=1+\text{number of calls of }f(n-2)$$

Let $C(n)$ represent the number of calls for $f(n)$. We have:

$$C(n)=1+C(n-2)$$

Starting with the base cases:

$$C(0)=1,C(1)=3$$

So for even $n=2k$:

$$C(2k)=1+C(2k-2)=1+(1+C(2k-4))=\dots =1+k$$

Thus,

$$C(n)=2^{(n/2+1)}-1\text{for }n\text{ even}$$

For odd $n$:

$$C(2k+1)=C(2k)+C(0)$$

So we can express it as:

$$C(n)=3\cdot 2^{(n-1)/2}-2\text{for }n\text{ odd}$$

4. Number of Calls of the Function $f$ with Call-by-Name Strategy in Terms of $n$

When using call-by-name, the function argument is not evaluated at the moment of the function call, but instead, every occurrence of the argument in the function body is replaced by the original expression.

For the function $f$, this results in exponential growth in calls because each nested call of $f$ introduces additional nested calls. Specifically:

$$f(n)\to f(f(n-2))\to f(f(f(n-4)))$$

Each $f(k)$ introduces an entirely new evaluation of $f(k-2)$. This results in a number of function calls that grows exponentially with $n$. This is much larger than the linear or polynomial number of calls observed with the call-by-value strategy.

5. Example of a Program that Does Not Terminate with Call-by-Value but Terminates with Call-by-Name

Consider the following function:

int g(int x, int y)
{
    if (x <= 0) return 1;
    else return g(x - 1, y) + g(x - 1, y);
}

If we call this with:

g(2, some_function())

Here, if some_function() has an infinite loop, the program will not terminate under call-by-value, because some_function() will be evaluated before entering g. However, under call-by-name, some_function() will only be evaluated when y is actually used in the function body, which may never occur if x <= 0 condition is met first, leading to termination.

知识点

递归函数编程语言调用策略值调用名调用

难点思路

在解决这道题目时，主要的难点在于理解不同调用策略如何影响递归函数的计算次数和返回值。尤其是对于 call-by-name 策略，理解参数传递的延迟计算（lazy evaluation）如何导致不同的函数行为。

解题技巧和信息

• 对于递归函数，可以利用归纳法证明递归终止条件和返回值的一致性。
• 需要熟悉 call-by-value 和 call-by-name 两种调用策略的差异，尤其是它们如何影响函数调用的次数和执行顺序。

重点词汇

• Call-by-Value: 值调用
• Call-by-Name: 名调用
• Recursion: 递归
• Evaluation Strategy: 计算策略

参考资料

1. Programming Languages: Concepts and Constructs (Chapter on Evaluation Strategies)
2. Types and Programming Languages, Benjamin C. Pierce (Chapter on Operational Semantics)