const, literal 和编译时计算

ajoo · #1 (**permalink**) 2003-11-18

一。const

c++的const概念，个人感觉非常重要。但是，总觉得还是不够彻底。
当你写下面这个代码的时候：

代码:

int f(const A& a, A* b);
A a;
int i;
......
f(a,b);

我们敢肯定a真的没有变化吗？敢肯定i没有变化吗？
如果b凑巧指向了对象a，那么，a就还是可能变化。
同样，我们也不知道f函数内部是否会改动i变量。
这一切仍然象没有const控制一样地需要程序员自己来保证。

究根结底，我们虽然在函数的入口可以限制对每个参数的读写访问，但是，对更加难以控制的全局环境，语言并没有提供控制。你虽然可能被限制写某一个参数，但是没有办法限制你去写一个静态变量，去写一个全局变量，或者去改变堆的状态。

下面，考虑一个对全局环境的const控制方案。规则如下：

代码:

T f(T1 t, const T2& t)const;

c++里面成员方法签名后面跟的const表示this指针是const的。
而这个const对静态方法和全局函数没有意义。

而cg中，这个const对静态函数，全局函数，成员函数都是有意义的。它的意义代表：对除了这些参数之外的全局名字只允许const操作。
对跟c++中的const方法等价的如operator==的原型如下：

代码:

bool const.operator==(const This& other)const;

第一个const表示this是const的，第二个const表示other是const的。最后一个const表示环境是const的。

所谓全局名字，代表的是这个函数scope外面定义的对象。它也包括全局堆。

一个const函数只能调用其它的const函数。

从原始操作开始，我们来递归定义const操作：
1。所有读操作都是const操作。
2。赋值是const操作。这可能有点奇怪。实际上int类型的赋值的原型如下：

代码:

int& operator=(const int& other) const;

这个const符合我们前面的定义，除了参数（包括this）之外，不改变其它的外部定义的对象。赋值操作只改变this，不改变外部环境，所以是const的。
3。于是，所有+=, -=, ++等操作都是对环境const的。虽然它们的this不是const的。
4。new不是const的。因为它改变了全局堆的状态。
5。动态数组的拼接不是const的，因为它虽然不改变参与计算的对象的状态，但是它改变全局堆的状态。
动态数组相加的原型如下：

代码:

T[] const.operator+(const T[] const& other);//不是const的。

6。对指针解引用取左值是非const的。实际上，指针的解引用原型如下：

代码:

T& const.operator->();//取可写引用
const T& const.operator->()const;//取只读引用

于是：

代码:

void f(int* p)const{
   *p = 10;//失败，在const环境下，*p返回const int&
   int i = *p;//成功。这是一个const操作。
}

7。const函数必须保证不能修改外部环境，因此，它不能对函数外的名字或者全局堆调用非const操作。也不能调用非const函数。

代码:

void f();
int g_i;
int& g()const{
    f();//失败。f()不是const的。
  for(int i=0;i<100;i++);//成功，i是g()函数内部定义的名字，所以可以改变。
  int* i = 1.new();//失败，new不是const的。
  g_i = 10;//失败。g_i是g()外部定义的名字。
  return g_i;//失败，在const函数中，所有外部名字都认为是const的。所以g_i北认为是const int。不能当作左值返回。
}

总的来说，这个额外添加的const就象是把外部环境看作一个参数对象之后对这个对象的一个修饰。

有了这个const，我们就可以得到fp意义上的真正的无副作用的函数了。同时，也不需要牺牲命令式语言中很方便的for loop等construct。

回到开头提到的例子中，如果我们把f()函数改成const的，我们就可以确信i和a都不会改变：

代码:

int f(const A& a, A* b)const;
A a;
int i;
......
f(a,b);

二。literal
c++中const可以表示一个本来就不可变的常量，如1, "abc"等，也可以用来表示一个变量，只不过不能通过这个用const限制的名字来改变。

这在模板的编译期计算时就显得模糊了两种应该区分开的概念。
模板的参数必须要在编译时可知。
c++通过编译器自动推导来区分这两者，语法上不提供区分的方法。

cg中提供literal关键字来区分常变量和常量。

一个literal的名字，其值必须是编译时可知的。而const的名字则未必。
只有literal的名字，即常量才可以用作模板的参数。

下面从原始操作开始定义literal。
1。所有字面整形常量都是literal的。
2。所有字面指针常量，如int*.null都是literal。
3。所有字符串常量，如"hello world"都是literal。字符串常量的类型是const char[k] （这个k是这个字符串的长度）
4。数组literal。如[1,2,3]是const int[3]类型的literal。
5。数组literal的下标读是literal。如"hello"[0]是值为'h'的const char类型的literal。
6。对指针的解引用不属于literal。所以*p, p[0]都不是literal。
7。所有带非const操作的表达式都不是literal。
8。一个literal名字必须初始化。而且必须用literal表达式初始化。
8。动态数组literal。如：

代码:

literal const char[] name = "hello";

注意，只有const T[]才可能成为literal。

代码:

literal char[] name = "hello";//编译失败。因为"hello"的类型是const char[5]，不存在从const T[k]到T[]的合法转换。

9。对变量取地址不是literal。因为这在编译时没有办法求值。
10。literal名字可以用来赋值给或者初始化const名字。但是const名字不能用来赋值给literal名字。

支持literal函数。
一个literal函数原型的例子如下：

代码:

literal T1 f(T2 t2, T3 t3);

在上面这个例子中，f函数内部必须符合以下规则：
1。只能使用literal操作。这就意味着，不能对指针解引用，不能使用赋值操作等non-const操作。
2。可以调用全局函数，或者成员函数。但是只能调用literal函数。
3。类里面定义的constructor都是literal的。这是因为construct内部只允许初始化操作和其它literal操作。
4。对数组的只读循环可以通过foreach来做。如：

代码:

literal char find(const char[] arr, char x){
  for(int i=0;i<arr.length;i++){//失败。i++不是literal操作。
     if(arr[i]==x)return arr[i];
  }
  foreach(c | arr){//对arr树组中的每一个元素c做循环。成功。
    if(c==x) return c;
  }
  assert false;
}

5。用foreach还可以做下面的循环：

代码:

literal int find(const char[] arr, char x){
  foreach(i | arr.length){//让i从0循环到arr.length-1
    if(arr[i]==x)return i;
  }
  assert false;
}

总结一下：
literal函数是要求最苛刻的函数。完全就是fp里面的函数和数学里面的函数的概念。它要求内部不能有任何non-const动作，也不能有指针的解引用和对象的取地址。它只能调用literal函数。（包括构造函数）
const函数要求不能对函数外面的环境，这包括全局堆。但是它可以改变函数内部变量的状态。
const函数可以调用其它const函数，也可以调用literal函数。

三。编译时计算。

有了literal函数，我们就可以大大增强我们的编译时计算的能力。
literal函数的特点保证了：
1。如果传入的参数都是literal的话，返回值也肯定是编译时可知的literal。
2。如果传入的参数不是literal的话，返回值可以在运行时获得。

这展示了一个把c++中meta-programming和普通运算统一的前景。
比如说，经常用作meta-programming例子的阶乘。c++中，对静态和动态你需要写两个版本的代码。模板代码无法使用在运行时，而普通的函数代码却不能用在编译时。（虽然有些优化可以对普通函数做静态展开，但是，它的结果不能参与其它的编译时计算）

在cg中，我们可以这样写factorial:

代码:

literal int fact(int i, int s){
  if(i==1)return s;
  else return fact(i-1, s*i);
}
literal int factorial(int i){
  return fact(i, 1);
}

我们可以在模板中直接使用factorial(1), factorial(10)作为参数，也可以在运行时调用factorial

。现在，只需要维护一份代码。而且，这样的代码比meta-programming的代码容易写，也容易读很多。

c++模板的另一个局限是，只能用整形类型作为参数，所有的自定义对象都不能作为参数。
这在cg中也不再是个障碍。既然constructor的结果静态可知，literal函数的结果也静态可知，那么，我完全可以定义这样的模板：

代码:

forall<T, T obj>
class X{......}
literal mobj = MyClass(factorial(10));
X<MyClass, mObj> x;

四。literal的另一种可能的命令式模型。
上面提到的literal模型要求literal函数是fp式的纯functional函数。这很符合现在嵌在c++中的meta-programming的模型。但是，c++，cg毕竟是一个imperative的语言。不支持gc导致无法支持closure,lamda等fp中的重要支柱。如果literal函数不支持imperative的功能，能达到多大的灵活性只怕是个问题。
c++中是对meta-programming和常规计算要写两套代码。
如果在cg中要对literal的functional和imperative各写一套代码，可能也好不到哪里去。
另一个literal的模型是，要求literal函数是const函数的一个子集，literal函数内部不能使用取地址，指针解引用，只能调用literal函数。
但是，象const函数一样，不限制对函数内部定义的名字的修改。对参数的读写控制由参数的类型决定。
这样，literal函数内部也可以是命令式的。可以支持for循环。factorial函数就可以用c++程序员更熟悉的命令式方式这样写：

代码:

int factorial(int x) literal{
  int sum = 1;
  for(int i=1;i<=x;i++){
    sum *= i;
  }
  return sum;
}

operator=的原型就是literal的：

代码:

T& operator=(const T& other) literal;

这样一来，对literal函数的限制更少，灵活性更大。不过，编译器内部嵌入的解释器就需要更强大，更复杂。超过了现在c++内部的解释器。
利弊如何，还有待斟酌。但是我的感觉是，两种模型都是可以实现的。

polyrandom · #2 (**permalink**) 2003-11-18

C99里面的restricted是一个解决方案。
而且B.S.说今后C++也会支持。

ajoo · #3 (**permalink**) 2003-11-18

引用:

作者: pora

C99里面的restricted是一个解决方案。
而且B.S.说今后C++也会支持。

restricted好象只是为了解决象memcpy这种指针指向的buffer的问题吧？感觉就是优化相关的。

跟副作用，编译时计算关系不大吧？

bs说会支持什么？"restricted"？

polyrandom · #4 (**permalink**) 2003-11-18

和你的那个const的例子有关。
B.S.说的就是restricted。

ajoo · #5 (**permalink**) 2003-11-18

就是说此restricted非彼restricted？
c99的restricted好象跟我这个const不同的。

polyrandom · #6 (**permalink**) 2003-11-18

什么彼此的

ppp看不懂

restricted当然和你的const不同，但是可以解决你第一个例子里面的问题。

ajoo · #7 (**permalink**) 2003-11-18

不敢苟同。解决不了根本问题的。

polyrandom · #8 (**permalink**) 2003-11-18

引用:

作者: ajoo

不敢苟同。解决不了根本问题的。

可以解决你例子提到的问题（可以肯定没改变）。至于你说的“根本问题”，我就不知道了，呵呵。

ajoo · #9 (**permalink**) 2003-11-19

不可以的。
你怎么保证一个全局的静态变量没有改变？
而且，你即使可以保证b没有指向a，能够保证b里面的某一个子对象没有指向a？能够保证经过八道弯之后b没有最后绕到a？能够保证某一个全局list里面没有a？

而且，我这个模型里面的目的不是限制aliasing，而是限制变化。这是两个不同的目标。

ajoo · #10 (**permalink**) 2003-11-19

据我的理解,C99的restrict指针好像是一个performance hint，不作为类型系统里面的强制的。
比如说：

代码:

char* restrict p1 = ...;
char* restrict p2 = p1+10;

是否真正重叠，还是要靠程序员来保证。如果两个restrict指针重叠了，结果是undefined。

这和const强调的“不允许改变”完全是两码事。
要是靠程序员保证，const根本就不需要存在了。

polyrandom · #11 (**permalink**) 2003-11-19

你的第一个例子里的那六个点让我浮想联翩。

housisong · #12 (**permalink**) 2003-11-19

literal的概念很不错！

ajoo · #13 (**permalink**) 2003-11-19

引用:

作者: pora

你的第一个例子里的那六个点让我浮想联翩。

为啥浮想联翩？

ajoo · #14 (**permalink**) 2003-11-21

const, literal这种很细粒度的类型约束似乎总是会造成一些很不灵活的地方。

先拿c++作例子。
比如说，我需要给我的一个类作一个接受一个泛形回调的成员函数：

代码:

class C{
  int i;
public:
  template<typename F>
  void call(F f){
    f(i);
  }
};

此处，这个F可以是：

代码:

struct Printor{
  void operator()(int i)const{
    cout << i;
  }
};

也可以是：

代码:

struct Inc{
  void operator()(int& i)const{
    i++;
  }
};

到现在都没有问题。
但是，问题在于，如果我有以下代码：

代码:

C getC();
getC().call(Printor());//不合法，因为临时对象不能用作non const。
void f(const C& c){
  c.call(Printor());//也是失败。call()不是const的。
}

问题的关键在于，因为我们不知道F是否会改变i，所以，只能保守地把它声明为非const的。但是，有些时候，我传入的F我自己知道是immutable的，但是因为类型系统的原因，这个call还是non-const的。

如果使用静态函数，可以如此解决：

代码:

	template<typename T, typename F>
	static void call(T& t, F f){
		f(t.i);
	}

但是，这毕竟不是相同的静态语义。很难说它可以代替所有的成员函数的场合。

使用traits可能也能通过判断F:

perator()到底接受的是不是const来解决问题，但是，复杂度只怕太高。而且，也不能很容易地扩展多个参数的更复杂的情况。

这个literal和环境const也有类似的问题。

比如说：

代码:

template<typename F>
int call(F f){
//这里是否是const呢？call()函数自己不主动更改环境。但是，不能排除f(i)改变环境。这完全取决于参数F类型。
    return f(i);
}

比如说：

代码:

struct Nop{
  int operator()(int i)literal{return i;}//这个是literal函数。
};

而

代码:

struct Printor{
  int operator()(int i){//io被认为是改变环境的，所以这不是const, 也不是literal。
    cout<<i<<endl;
    return i;
  }
}

所以, call()函数是否改变环境，是literal还是const完全取决于参数F。
可是，在类型上，却很难表达这种依赖性的const/literal。
经过一次回调的函数call()就丢失了本来可能具有的const/literal属性。这种类型信息的丢失让人很不舒服。
而且，比c++的const函数还要让人头疼的是，这个const/literal无法通过静态函数绕开。
似乎唯一的办法就是把同样的代码给const, literal和普通函数各自重复一遍。

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式

相似的主题
主题	主题作者	版面	回复	最后发表
捕捉鼠标输入的方法	bankrock	技术杂烩	33	2005-06-16 03:32 PM
Huge Integer	wqqafnd	技术杂烩	48	2005-01-07 04:44 PM
搜索文件的iterator	SpitFire	技术杂烩	2	2004-06-01 01:08 PM
allaboutprogram.com C++ 初学者FAQ	codinggirl	技术杂烩	4	2004-03-22 11:51 AM
ABP C++ FAQ02-------------essential const	codinggirl	技术杂烩	1	2003-12-18 09:59 AM