?

Log in

No account? Create an account
The C preprocessor scares the hell out of me. - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

The C preprocessor scares the hell out of me. [Feb. 10th, 2010|01:10 am]
Lindsey Kuper
[Tags|, , ]

I spent about eight hours today trying to reason about call-by-denotation. I don't recommend you do the same.

LinkReply

Comments:
[User Picture]From: oniugnip
2010-02-10 06:33 am (UTC)
For improved portability, the C preprocessor supports trigraphs.

They help readability too! I lose track of all those {s. ??< is just easier to look at.

<3
(Reply) (Thread)
[User Picture]From: pixelherder
2010-02-10 10:40 am (UTC)
But where else do you get to talk about painting code blue?

Though if you really want to see horrible, twisted, insanity-inducing abuses of the C preprocessor, though, I give you preprocessor metaprogramming.
(Reply) (Thread)
[User Picture]From: lindseykuper
2010-02-10 03:23 pm (UTC)
Ow, it hurts. Okay, so here's a program that returns 2 under pretty much any evaluation strategy but call-by-denotation, under which it returns 1.
(let ([f (lambda (y)
           (let ([x 0])
             y))])
  (let ([x 1])
    (f (+ x 1))))
The corresponding C program would be something like:
#define f(y) x = 0; answer = y

int cbd1() {
  int answer;
  int x = 1;
  f(1 + x);
  return answer;
}

int main() {
  printf("cbd1: %d (expected 1)\n", cbd1());
  return 0;
}
But that's not the weirdest thing about CBD. More bizarre is that I can write
((let ([x 3])
   (lambda (y) y))
 x)
which, under pretty much any other evaluation strategy, would be an error because the last x is unbound. Under CBD, it evaluates to 3! But I don't know how to write the corresponding C...do you?
(Reply) (Parent) (Thread)
[User Picture]From: pixelherder
2010-02-10 06:52 pm (UTC)
I'm a novice at PL theory, but given that the let-expression evaluates to a function closure, wouldn't that require another preprocessor macro? Mixing macro semantics and C function call semantics like you did above seems dangerous. Wouldn't you want to write it all as one big chain of macros for as long as possible. Then you'd get something like this, which works:
#define lambda(y) answer = y
#define let(y) { int x = 3; lambda(y); }
#define expr() let(x)
int main() {
    int answer;
    expr();
    printf( "expr: %d (expected 3)\n", answer );
    return answer;
}
Or did I misunderstand the question?
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2010-02-10 09:40 pm (UTC)
Oh, OK...I think that my problem was that I was trying to simplify the let by translating it to ((lambda (x) (lambda (y) y)) 3) and then I couldn't figure out how to express that. Looking at yours, I now see that I could just do this:
#define lambda(y) answer = y 
#define let(y) { int x = 3; lambda(y); }
int main() {
    int answer;
    let(x);
    printf( "expr: %d (expected 3)\n", answer );
    return answer;
}
which I like because it makes the unbound x obvious. Dangerous, I guess, is what I'm going for here.
(Reply) (Parent) (Thread)
[User Picture]From: oniugnip
2010-02-10 06:20 pm (UTC)
So, thinking about cpp macros versus having a call-by-denotation interpreter...

In the case of macros in C, what's happening at preprocessing time is just textual substitution; after that substitution happens, nothing weird is going on. It's just as if you wrote this in the first place:

int cbd1() {
  int answer;
  int x = 1;
  // macro invocation was here.
  x = 0; answer = 1 + x;
  return answer;
}


So invoking f before run-time looks like a regular C function call (syntactically), but it's not one.

Does your CBD interpreter do something analogous to that in Scheme? (given that it's actually running in Scheme, with its CBV, does it have to?) Is the interpreter understandable by the PL layperson?
(Reply) (Thread)
[User Picture]From: lindseykuper
2010-02-10 08:12 pm (UTC)
To be honest, I'm not actually sure CBD accurately describes the semantics of TeX and cpp. It works out to something similar, certainly.

I would post my CBD interpreter, but we're having students actually do it as a homework assignment, so I can't! I can describe what it does, though. Suppose your program is int x = 5; f(1 + x). Under CBD, when you get to the f(1 + x), you create a "box" containing, roughly, "eval(1 + x)", but you leave out that "where x equals 5" bit. If f's formal parameter is, say, y, then every time y occurs in f's body, you pop open that box, run the code inside, and use the result. So I guess my interpreter is doing textual substitution, modulo the box.

By contrast, under call-by-name, the 1 + x evaluates to a box containing something like "eval(1 + x) in the environment where x equals 5". (If you think this box sounds kind of like a closure, you're right.) If f's formal parameter is, say, y, then every time y occurs in f's body, you pop open that box, run the code inside given the saved environment, and use the result. (Haskell's call-by-need is an optimization of this, in which you only evaluate the box's contents the first time and then save the evaluated result back in the box. You still have to "open the box" for each occurrence of y, but there's no need to re-evaluate what's inside.)

Under call-by-reference, you'd create a box containing 6. And under call-by-value, you create, uh, 6. The fact that the interpreter itself is written in a CBV language is kind of a red herring here, I think.
(Reply) (Parent) (Thread)