昨日、とある場所でこんな話で盛り上がった。
逆ポーランド計算機を作ろうと思ったんだけど、どうも結果が期待通りにならない。ソースコードを見せて貰うと以下の様なコードだった。
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
int stack[MAX_SIZE];
int stack_pointer = 0;
void push(int data){
stack[stack_pointer++] = data;
}
int pop(){
return stack[--stack_pointer];
}
int pop1(int n){
printf("pop %d\n", n);
return stack[--stack_pointer];
}
int main(void){
char s[MAX_SIZE];
int a, b;
while( scanf("%s", s) != EOF ){
switch (s[0]) {
case '+':
push(pop() + pop());
break;
case '-':
/*
* "3 4 -"などを与えると
* -1ではなく1となってしまう
* push(-pop() + pop());
*
*/
a = pop();
b = pop();
push(b - a);
break;
case '*':
push(pop() * pop());
break;
default:
push(atoi(s));
break;
}
}
printf("%d\n", pop());
return 0;
}
このコードはちゃんと動作する。足し算と掛け算は間違いなく動作するだろう。でもコメント部に書いてあるコードを有効にすると結果が変わる。
push(-pop() + pop());
もちろん皆さん知ってはいるだろうが、これはスタックから取り出す順に依存する。このコードを書いた人は「3 4 -」という入力を「3 - 4」として処理したいが為に、先に4を取り出して符号を逆転し、3を取り出して加算する事で-1を得るという動作を期待した。引数の評価順が
左から右である事を期待したんですね。
push(-4 + 3);
しかしこれをgccでコンパイルして実行すると結果は -1 ではなく 1 が得られるんです。なんと gcc は上記のコードを
push(pop() - pop());
に戻してコンパイルしてるんです。試しにpop1.c
#include <stdio.h>
int a[] = {3, 4}, p = sizeof(a) / sizeof(a[0]);
int
pop() {
return a[--p];
}
int
main(int argc, char* argv[]) {
printf("%d\n", -pop() + pop());
return 0;
}
pop2.c
#include <stdio.h>
int a[] = {3, 4}, p = sizeof(a) / sizeof(a[0]);
int
pop() {
return a[--p];
}
int
main(int argc, char* argv[]) {
printf("%d\n", pop() - pop());
return 0;
}
上記 pop1.c と pop2.c を「gcc -S」でアセンブリ出力して比較して見たら全く同じ出力内容になりました。
.file "pop1.c"
.globl a
.data
.align 4
.type a, @object
.size a, 8
a:
.long 3
.long 4
.globl p
.align 4
.type p, @object
.size p, 4
p:
.long 2
.text
.globl pop
.type pop, @function
pop:
pushl %ebp
movl %esp, %ebp
movl p, %eax
subl $1, %eax
movl %eax, p
movl p, %eax
movl a(,%eax,4), %eax
popl %ebp
ret
.size pop, .-pop
.section .rodata
.LC0:
.string "%d\n"
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
andl $-16, %esp
pushl %ebx
subl $28, %esp
call pop
movl %eax, %ebx
call pop
movl %ebx, %edx
subl %eax, %edx
movl $.LC0, %eax
movl %edx, 4(%esp)
movl %eax, (%esp)
call printf
movl $0, %eax
addl $28, %esp
popl %ebx
movl %ebp, %esp
popl %ebp
ret
.size main, .-main
.ident "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-3)"
.section .note.GNU-stack,"",@progbits
最適化オプションは付けていないので、デフォルトの動作としてこうなります。gcc のバージョンは 4.7.2 です。この最適化をやめるオプションを軽く探してみましたが見つけられませんでした。
これ、実は clang や MSVC だとこの最適化は行われなくて左から評価が行われる為、どちらも結果は -1 となります。
これは僕の推測なのですが、gccはたぶん、
-pop+pop について
- 左pop
- 符号逆転
- 右pop
- 加算
- 本来右pop
- 本来左pop
- 加算
int
main(int argc, char* argv[]) {
int c = 1;
printf("%d\n", -pop()*c + pop());
return 0;
}
こうすれば評価順をちょっとだけ強制できるけど、これも最適化次第では消されてしまうかもしれないしなによりダサい。
もちろんC/C++関数引数の評価順序 - yohhoyの日記しかしながら論理演算は左から右に評価される事を期待している為、この様な副作用のあるコードを書くと処理系によっては足をすくわれる事になるという、なんとも面白い事例でした。
プログラミング言語C/C++では、関数実引数の評価順序は未規定(unspecified)となっている。
http://d.hatena.ne.jp/yohhoy/20120304/p1
気になったので他の言語ではどうなのか調べてみましたが
perl も
my @a = (3, 4);
print ((-pop @a) + (pop @a));
ruby も
a = [3, 4]
puts (-a.pop + a.pop)
python も
a = [3, 4]
print (-a.pop() + a.pop())
javascript も
log = typeof console != 'undefined' ? console.log : print;
var a = [1, 2];
log(-a.pop() + a.pop());
java も
import java.util.Stack;
public class poptest {
public static void main(String[] args) {
Stack<Integer> st = new Stack<Integer>();
st.push(1);
st.push(2);
System.out.println(-st.pop() + st.pop());
}
}
vim script も(誰も聞いてない)
let s:a = [3, 4]
function! s:pop()
let r = s:a[-1]
let s:a = s:a[:-2]
return r
endfunction
echo (-s:pop() + s:pop())
-1 でした。lisp だと
(setq x '(4 3))
(+ (- (pop x)) (pop x))
こう書けば -1 ですかね。副作用のある処理を式として列挙記述するのはやめましょう。
