3 ms·

From the programmer's perspective C is not a stack based language the way that, say, Forth is, because (as you note) there are no explicit push and pop instruct

From the programmer's perspective C is not a stack based language the way that, say, Forth is, because (as you note) there are no explicit push and pop instructions. But from an implementor's perspective, evaluating C function calls and arithmetic expressions is very stack oriented, which is why in the cited paper some Bell Labs researchers in the early 1980s were trying to build stack machine CPUs to execute C code. Given your Lisp experience, just think about how you'd translate various C expressions to Lisp ones, and how Lisp expressions map to stack operations, and you'll see C's stack based nature come out. (I.e. the abstract syntax trees (ASTs) a C compiler builds can naturally be represented as Lisp-like expressions.) C: y = a*x + foo(b); Lisp: (setq y (+ (* a x) (foo b))) Example stack instructions for the above (many variations possible): PUSH a PUSH x MUL PUSH b PUSH foo CALL ADD PUSH y SETQ ; or MOV or whatever your arch wants to call it Dennis Ritchie added the register storage qualifier keyword to primeval C (and also auto, inherited from B) to make the earliest C compilers easier to write, because bug-free register allocation is a very hard problem and Ritchie's earliest PDP had only a few kilobytes of core to hold both the C compiler's code and the chunk of program text being currently translated, so a complicated register allocator was out of the question.

gary_0 5y ago
C is just implicit about how it pushes each function-local variable onto the stack. No amount of compiler optimization can hide it completely -- recurse too much or use up all the space, and you'll get a stack overflow. And just below C, all mainstream ABIs are designed around a stack too (with a designated stack pointer register, etc).
- kazinator 5y ago
  C has activation frames allocated in a LIFO discipline for supporting recursive functions, implemented using a stack; but I think that is not what we mean by "stack language".
kazinator 5y ago
What you are showing is not a purebred stack machine; it's a machine with stack-based temporary calculations that rely on randomly accessed operands. The first C that I used was like this. It was actually a tiny, toy subset of C powering a programming game called C Robots by Tim Poindexter. I think that's how I first heard about Yacc, too. Anyway, if you want to defend the hypothesis that C is a stack language under the hood from an implementor's POV, it would help to show how expressions involving function calls and variables translate to something resembling canonical, point-free Forth. The local variables must turn into anonymous stack locations accessed implicitly. If a variable is used as an operand, and is still live (has a next use), you must DUP it to keep a copy in the stack. Lisp isn't a stack machine either. Lisp expressions can map to stack operations, and easily so if we can have random access to off-stack operands, but do not have to. My own TXR Lisp uses a register-based VM. 1> (disassemble (compile-toplevel '(set y (+ (* a x) (foo b))))) ** expr-1:1: warning: unbound variable y ** expr-1:1: warning: unbound variable a ** expr-1:1: warning: unbound variable x ** expr-1:1: warning: unbound variable b ** expr-1:1: warning: unbound function foo data: syms: 0: y 1: sys:b+ 2: sys:b* 3: a 4: x 5: foo 6: b code: 0: 90040003 getlx t4 3 1: 90050004 getlx t5 4 2: 20020003 gcall t3 2 t4 t5 3: 00040002 4: 00000005 5: 90050006 getlx t5 6 6: 20010004 gcall t4 5 t5 7: 00050005 8: 20020002 gcall t2 1 t3 t4 9: 00030001 10: 00000004 11: 94020000 setlx t2 0 12: 10000002 end t2 instruction count: 8 #<sys:vm-desc: 8c0dc50> The registers are allocated on the native stack, in a frame whose size is determined at compile time and sized to fit using alloca() at run-time. Local variables (not seen here) turn into v registers, treated uniformly with t registers. We don't see t1 and t0 above because t0 is a read-only register that holds nil, and t1 is the assembler temporary. With locals: 4> (disassemble (compile-toplevel '(let ((x 1) y (a 4) (b 3)) (set y (+ (* a x) (foo b)))))) ** expr-4:1: warning: unbound function foo data: 0: 1 1: 4 2: 3 syms: 0: sys:b+ 1: sys:b* 2: foo code: 0: 20020004 gcall t4 1 d1 d0 1: 04010001 2: 00000400 3: 20010005 gcall t5 2 d2 4: 04020002 5: 20020009 gcall t9 0 t4 t5 6: 00040000 7: 00000005 8: 10000009 end t9 instruction count: 4 #<sys:vm-desc: 8c72ce0> I don't have constant folding through variables working. So gcall t4 1 d1 d0 is still doing the (* a x) multiplication, though directly on the d1 d0 registers that hold these values. Ideally, this The original unoptimized code is generated like this: 5> (let ((*opt-level* 0)) (disassemble (compile-toplevel '(let ((x 1) y (a 4) (b 3)) (set y (+ (* a x) (foo b))))))) ** expr-6:1: warning: unbound function foo data: 0: 1 1: 4 2: 3 syms: 0: + 1: * 2: foo code: 0: 04020004 frame 2 4 1: 2C800400 movsr v00000 d0 2: 2C820401 movsr v00002 d1 3: 2C830402 movsr v00003 d2 4: 20020004 gcall t4 1 v00002 v00000 5: 08020001 6: 00000800 7: 20010005 gcall t5 2 v00003 8: 08030002 9: 20020801 gcall v00001 0 t4 t5 10: 00040000 11: 00000005 12: 2C020801 movsr t2 v00001 13: 10000002 end t2 14: 10000002 end t2 instruction count: 10 #<sys:vm-desc: 8923d90> The optimization eliminated the variable frame allocation "frame 2 3" and its matching "end t2", and mapped all the v registers belonging to that frame to new t registers. It propagated the d0, d1 and d2 values, eliminating some of those registers. v00001 became t9, and the "movsr t2 t9" was eliminated, which involved changing the subsequent "end t2" to "end t9". Another thing we see is the reduction of the + and * functions to internal binary-only variants sys:b+ and sys:b, but that's not done as a pass over the code; the initial instruction selection does that, sensitive to opt-level*. I'm not sure how easy this kind of work is on stack machines.

gary_0 5y ago

C is just implicit about how it pushes each function-local variable onto the stack. No amount of compiler optimization can hide it completely -- recurse too much or use up all the space, and you'll get a stack overflow. And just below C, all mainstream ABIs are designed around a stack too (with a designated stack pointer register, etc).

kazinator 5y ago
C has activation frames allocated in a LIFO discipline for supporting recursive functions, implemented using a stack; but I think that is not what we mean by "stack language".

kazinator 5y ago

What you are showing is not a purebred stack machine; it's a machine with stack-based temporary calculations that rely on randomly accessed operands. The first C that I used was like this. It was actually a tiny, toy subset of C powering a programming game called C Robots by Tim Poindexter. I think that's how I first heard about Yacc, too. Anyway, if you want to defend the hypothesis that C is a stack language under the hood from an implementor's POV, it would help to show how expressions involving function calls and variables translate to something resembling canonical, point-free Forth. The local variables must turn into anonymous stack locations accessed implicitly. If a variable is used as an operand, and is still live (has a next use), you must DUP it to keep a copy in the stack. Lisp isn't a stack machine either. Lisp expressions can map to stack operations, and easily so if we can have random access to off-stack operands, but do not have to. My own TXR Lisp uses a register-based VM. 1> (disassemble (compile-toplevel '(set y (+ (* a x) (foo b))))) ** expr-1:1: warning: unbound variable y ** expr-1:1: warning: unbound variable a ** expr-1:1: warning: unbound variable x ** expr-1:1: warning: unbound variable b ** expr-1:1: warning: unbound function foo data: syms: 0: y 1: sys:b+ 2: sys:b* 3: a 4: x 5: foo 6: b code: 0: 90040003 getlx t4 3 1: 90050004 getlx t5 4 2: 20020003 gcall t3 2 t4 t5 3: 00040002 4: 00000005 5: 90050006 getlx t5 6 6: 20010004 gcall t4 5 t5 7: 00050005 8: 20020002 gcall t2 1 t3 t4 9: 00030001 10: 00000004 11: 94020000 setlx t2 0 12: 10000002 end t2 instruction count: 8 #<sys:vm-desc: 8c0dc50> The registers are allocated on the native stack, in a frame whose size is determined at compile time and sized to fit using alloca() at run-time. Local variables (not seen here) turn into v registers, treated uniformly with t registers. We don't see t1 and t0 above because t0 is a read-only register that holds nil, and t1 is the assembler temporary. With locals: 4> (disassemble (compile-toplevel '(let ((x 1) y (a 4) (b 3)) (set y (+ (* a x) (foo b)))))) ** expr-4:1: warning: unbound function foo data: 0: 1 1: 4 2: 3 syms: 0: sys:b+ 1: sys:b* 2: foo code: 0: 20020004 gcall t4 1 d1 d0 1: 04010001 2: 00000400 3: 20010005 gcall t5 2 d2 4: 04020002 5: 20020009 gcall t9 0 t4 t5 6: 00040000 7: 00000005 8: 10000009 end t9 instruction count: 4 #<sys:vm-desc: 8c72ce0> I don't have constant folding through variables working. So gcall t4 1 d1 d0 is still doing the (* a x) multiplication, though directly on the d1 d0 registers that hold these values. Ideally, this The original unoptimized code is generated like this: 5> (let ((*opt-level* 0)) (disassemble (compile-toplevel '(let ((x 1) y (a 4) (b 3)) (set y (+ (* a x) (foo b))))))) ** expr-6:1: warning: unbound function foo data: 0: 1 1: 4 2: 3 syms: 0: + 1: * 2: foo code: 0: 04020004 frame 2 4 1: 2C800400 movsr v00000 d0 2: 2C820401 movsr v00002 d1 3: 2C830402 movsr v00003 d2 4: 20020004 gcall t4 1 v00002 v00000 5: 08020001 6: 00000800 7: 20010005 gcall t5 2 v00003 8: 08030002 9: 20020801 gcall v00001 0 t4 t5 10: 00040000 11: 00000005 12: 2C020801 movsr t2 v00001 13: 10000002 end t2 14: 10000002 end t2 instruction count: 10 #<sys:vm-desc: 8923d90> The optimization eliminated the variable frame allocation "frame 2 3" and its matching "end t2", and mapped all the v registers belonging to that frame to new t registers. It propagated the d0, d1 and d2 values, eliminating some of those registers. v00001 became t9, and the "movsr t2 t9" was eliminated, which involved changing the subsequent "end t2" to "end t9". Another thing we see is the reduction of the + and * functions to internal binary-only variants sys:b+ and sys:b, but that's not done as a pass over the code; the initial instruction selection does that, sensitive to opt-level*. I'm not sure how easy this kind of work is on stack machines.