Saturday, February 25, 2006

The ambiguous operator, pt. 1

This was originally intended as my programming and mathematics blog but I never got around to any programming here, until today.

My recent interest in logic is partly motivated by a desire to understand the paper Call by Name is Dual to Call by Value. I suspect the paper is almost trivial, but that you have to be very familiar with the prerequisites before you can appreciate its triviality. (Ie. I'm using the mathematician's definition of trivial of course :-) )

Now I don't understand that paper yet, but on the seventh page there is a story about the Devil. Below I have a computational representation of the story written in C. The idea is, what must the functions devilChoice() and devilCheats() do in order to allow the devil to capture this soul? devilChoice() must return A or B.


#define A 0
#define B 1

int my_main() {
  int choice;

  static int devilMoney = 0;
  static int suckerMoney = 0;
  static int suckerKarma = 0;

  printf("Devil says:\n");
  printf("Here's my offer.\n");
  printf("I will choose either A or B\n");
  printf("If A I'll give you $1000000000\n");
  printf("If B I'll give you any wish for $1000000000\n");
  printf("Do you accept\n");

  printf("Sucker says: 'yes'.\n");
  choice = devilChoice();

  switch (choice)
  {
  case A:
        if (devilMoney<1000000000)
        {
         printf("Devil is unable to pay up.\n");
         printf("Devil is in big trouble...\n");
         exit(1);
        }
        printf("Devil gives 1000000000 to sucker\n");
        suckerMoney += 1000000000;
        devilMoney -= 1000000000;
        break;
    case B:
        printf("Sucker begs, borrows, steals $1000000000\n");
        suckerMoney += 1000000000;
        suckerKarma -= 1000000000;

        printf("Sucker gives money to Devil\n");
        devilMoney += 1000000000;
        suckerMoney -= 1000000000;

        printf("Sucker is about to make wish...\n");
        printf("'I wish to go to heaven'\n");
        devilCheats();
        printf("Sucker goes to heaven and devil loses a soul\n");
        exit(1);
        break;
    }

    if (suckerKarma<0)
    {
        printf("Sucker goes to hell with $%d\n",suckerMoney);
    }
}

(Hmmm...syntax colouring didn't work out quite as well as I wanted.)

In fact, I'm going to leave this as an exercise and give a possible solution another day. But the title of this post gives a clue - and of course the paper proposes a solution too. The code doesn't need to be 100% portable.

PS You don't need to ask. I have a solution in not quite 100% portable C. But of course I cheat. But is there an interesting cheat?

1 comment:

Peter said...

Was this what you had in mind? Maybe not, but it works!

int devilChoice() {

  static int is_first_call = 1;

  if (is_first_call) {

    printf("The Devil chooses B.\n");

    is_first_call = 0;

    return B;

  } else {

    printf("The Devil chooses A.\n");

    return A;

  }

}

void devilCheats() {

  /* Please forgive the pun... */

  printf("The Devil says, 'But wait!  I want to recurse.'\n");

  my_main();

  printf("The Devil says, 'Still recursing, are we?  I think not....'\n");

  exit(0);

}

Blog Archive