问题1323--本次比赛的白给题

1323: 本次比赛的白给题

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交

题目描述

说到白给,能联想到的是「免费」,而免费的英文是「free」,free 还有个意思是「自由的」。所以这题我们就来聊聊约束变量(bound variables)和自由变量(free variables)。
对于集合 S = {x | x > 2} 中的所有的 x,我们可以对它进行更名(renaming),比如可以将所有的 x 都改名为 y:S' = {y | y > 2}。在这种情形下,S = S'。这样的一个变量 x 就被我们叫作「约束变量」,这样对约束变量更名的操作被叫作 α-变换α-conversion)。
反之,对于这样的一个式子:a = 2, S = {x | x > a},对于这个集合中的 a,如果对它做更名,比如:a = 2, S' = {x | x > b},这样的一个集合 S' 不再等于原来的 S,这样的变量 a 就被叫作「自由变量」。同时我们可以说,这样的集合 S 捕获(capture)了自由变量 a。

非形式化地,我们举例 C++11 的 lambda expression:
int a = 2;
auto closure = [a](int x) {
    return x > a;
};
这样的一个叫作 closure 的谓词(predicate),完成了对自由变量 a 的捕获。

下面,我们非形式化地对某一个语言 L 做不完全的定义:
对多参数的函数定义:
# x y : x + y
表示定义一个函数,接收两个参数,返回它们的「和」。
使用分号来分割同一函数中的多个语句:
# a b : a ; b
为避免歧义,如果有多条语句的函数定义中包含嵌套的函数定义,那么这个嵌套的函数定义一定是出现在尾部的。

那么,我们可以很容易用语言 L 定义对自由变量的捕获:
# a : # x : x > a
这样我们说,内层的函数捕获了自由变量 a。

下面我会给你多层函数嵌套,请你给出每一层函数定义中出现的自由变量。

输入

一个由语言 L 编写的函数定义表达式。表达式中的所有符号(包括运算符和变量名)均使用空格分割,并保证定义的变量名都唯一,且均为小写字母组成。
假设函数的内部只会再嵌套最多一个函数定义。

输出

推出每一层函数定义中捕获的自由变量,有多个时按字典序输出。具体见样例输出和说明。

样例输入 Copy

# a : # b : a ; b ; # x y : b + x + y + a

样例输出 Copy

1
2 a
3 a b

提示

样例说明:
对于函数定义式:# a : # b : a ; b ; # x y : b + x + y + a
我们可以对该表达式稍微做一下格式化:
# a :
  # b :
    a ;
    b ;
    # x y :
      b + x + y + a
这样我们可以很容易看出每一层函数使用了那些变量。明显的,第 2 层函数使用了第 1 层函数定义的参数 a,所以第 2 层函数捕获了自由变量 a。
类似的第 3 层函数捕获了自由变量 b 和 a,但是要按字典序输出,所以输出 a b。

来源/分类