A Birthday Present for Fido

[lurk101]

Neither are if() while() switch() functions

Hmm. You're right! Just a stylistic thing for return then, I guess?

[jahboater]

I think it might be just ancient history. There were other odd quirks in the past, like:
=+ which they changed to += at some point.
In B, I remember that functions were not recognized as such if there was a gap between the name and the open bracket!

[lurk101]

A working version of the Wumpus state machine. I've tried to keep it as K&Rish as possible.

Question: Does the init function guarantee a Hamiltonian graph?

Code: Select all

/*
 *  wumpus
 *  stolen from PCC Vol 2 No 1
 */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define NBAT  3
#define NROOM 20
#define NTUNN 3
#define NPIT  3

struct room
{
    int tunn[NTUNN];
    int flag;
} room[NROOM];

struct room* p;

const char* intro =
  "\n"
  "Welcome to 'Hunt the Wumpus.'\n"
  "\n"
  "The Wumpus lives in a cave of %d rooms.\n"
  "Each room has %d tunnels leading to other rooms.\n"
  "\n"
  "Hazards:\n"
  "\n"
  "Bottomless Pits - Some rooms have Bottomless Pits in them.\n"
  " If you go there, you fall into the pit and lose!\n"
  "Super Bats - Some other rooms have super bats.\n"
  " If you go there, a bat will grab you and take you to\n"
  " somewhere else in the cave where you could\n"
  " fall into a pit or run into the . . .\n"
  "\n"
  "Wumpus:\n"
  "\n"
  "The Wumpus is not bothered by the hazards since\n"
  "he has sucker feet and is too big for a bat to lift.\n"
  "\n"
  "Usually he is asleep.\n"
  "Two things wake him up:\n"
  " your entering his room\n"
  " your shooting an arrow anywhere in the cave.\n"
  "If the wumpus wakes, he either decides to move one room or\n"
  "stay where he was.  But if he ends up where you are,\n"
  "he eats you up and you lose!\n"
  "\n"
  "You:\n"
  "\n"
  "Each turn you may either move or shoot a crooked arrow.\n"
  "\n"
  "Moving - You can move to one of the adjoining rooms;\n"
  " that is, to one that has a tunnel connecting it with\n"
  " the room you are in.\n"
  "\n"
  "Shooting - You have 5 arrows.  You lose when you run out.\n"
  " Each arrow can go from 1 to 5 rooms.\n"
  " You aim by telling the computer\n"
  " The arrow's path is a list of room numbers\n"
  " telling the arrow which room to go to next.\n"
  " The list is terminated with a 0.\n"
  " The first room in the path must be connected to the\n"
  " room you are in.  Each succeeding room must be\n"
  " connected to the previous room.\n"
  " If there is no tunnel between two of the rooms\n"
  " in the arrow's path, the arrow chooses one of the\n"
  " three tunnels from the room it's in and goes its\n"
  " own way.\n"
  "\n"
  " If the arrow hits the wumpus, you win!\n"
  " If the arrow hits you, you lose!\n"
  "\n"
  "Warnings:\n"
  "\n"
  "When you are one or two rooms away from the wumpus,\n"
  "the computer says:\n"
  "   'I smell a Wumpus'\n"
  "When you are one room away from some other hazard, it says:\n"
  "   Bat    - 'Bats nearby'\n"
  "   Pit    - 'I feel a draft'\n";

#define BAT  1
#define PIT  2
#define WUMP 4

int arrow, loc, wloc, tchar, randx;

enum states {
    START = 0,
    INSTRUCTION,
    INIT,
    SETUP,
    LOOP,
    AGAIN,
    MOVE,
    SHOOT,
    MWUMP,
    DONE,
    LEAVE,
    NUM_STATES
};

int
rnum(int n)
{
    randx = randx * 1103515245U + 12345U;
    return (int)(((double)((randx >> 16) & 077777) / 32768.0) * n);
}

int
tunnel(int i)
{
    struct room* p;
    int c = 20, n, j;

    for (;;)
    {
        n = rnum(NROOM);
        if (n == i)
            if (--c > 0)
                continue;
        p = room + n;
        for (j = 0; j < NTUNN; j++)
            if (p->tunn[j] == -1) {
                p->tunn[j] = i;
                return n;
            }
    }
}

char
rline(void)
{
    char r;
    int c, leave_state();

    while ((c = getchar()) == ' ')
        ;
    r = (char)c;
    while (c != '\n' && c != ' ') {
        if (c == EOF || c == '\0')
            leave_state();
        c = getchar();
    }
    tchar = (char)c;
    return r;
}

int
rin()
{
    int n = 0, c = getchar(), leave_state();

    while (c != '\n' && c != ' ') {
        if (c < '0' || c>'9') {
            while (c != '\n') {
                if (c == EOF || c == 0)
                    leave_state();
                c = getchar();
            }
            return 0;
        }
        n = n * 10 + c - '0';
        c = getchar();
    }
    return n;
}

int
near(ap, ahaz)
struct room* ap;
int ahaz;
{
    int i;

    for (i = 0; i < NTUNN; i++)
        if (room[ap->tunn[i]].flag & ahaz)
            return 1;
    return 0;
}

exchange(int t[2])
{
    if (t[0] < t[1])
        return;
    t[0] = t[0] ^ t[1];
    t[1] = t[0] ^ t[1];
    t[0] = t[0] ^ t[1];
}

int
start_state()
{
    printf("Instructions? (y-n) ");
    return (rline() == 'y') ? INSTRUCTION : INIT;
}

int
leave_state()
{
    puts("\nGame over");
    exit(0);
}

int
instruction_state()
{
    printf(intro, NROOM, NTUNN);
    return INIT;
}

int
init_state()
{
    /*
     * initialize the room connections
     */
    int i, j, k;

    p = room;
    for (i = 0; i < NROOM; i++) {
        for (j = 0; j < NTUNN; j++)
            p->tunn[j] = -1;
        p++;
    }
    k = 0;
    for (i = 1; i < NROOM; ) {
        j = rnum(NROOM);
        p = room + j;
        if (j == k || p->tunn[0] >= 0 || p->tunn[1] >= 0)
            continue;
        p->tunn[1] = k;
        room[k].tunn[0] = j;
        k = j;
        i++;
    }
    p = room;
    for (i = 0; i < NROOM; i++) {
        for (j = 0; j < NTUNN; j++) {
            if (p->tunn[j] < 0)
                p->tunn[j] = tunnel(i);
            if (p->tunn[j] == i)
                return INIT;
            for (k = 0; k < j; k++)
                if (p->tunn[j] == p->tunn[k])
                    return INIT;
        }
        exchange(p->tunn);
        exchange(p->tunn + 1);
        exchange(p->tunn);
        p++;
    }
    return SETUP;
}

int
setup_state()
{
    /*
     * put in player, wumpus, pits and bats
     */
    int i;
    
    arrow = 5;
    p = room;
    for (i = 0; i < NROOM; i++) {
        p->flag = 0;
        p++;
    }
    for (i = 0; i < NPIT; ) {
        p = room + rnum(NROOM);
        if ((p->flag & PIT) == 0) {
            p->flag |= PIT;
            i++;
        }
    }
    for (i = 0; i < NBAT; ) {
        p = room + rnum(NROOM);
        if ((p->flag & (PIT | BAT)) == 0) {
            p->flag |= BAT;
            i++;
        }
    }
    i = rnum(NROOM);
    wloc = i;
    room[i].flag |= WUMP;
    for (;;) {
        i = rnum(NROOM);
        if ((room[i].flag & (PIT | BAT | WUMP)) == 0) {
            loc = i;
            break;
        }
    }
    return LOOP;
}

int
loop_state()
{
    /*
     *  main loop of the game
     */
    int i, nearwump;

    printf("You are in room %d\n", loc + 1);
    p = room + loc;
    if (p->flag & PIT) {
        printf("You fell into a pit\n");
        return DONE;
    }
    if (p->flag & WUMP) {
        printf("You were eaten by the wumpus\n");
        return DONE;
    }
    if (p->flag & BAT) {
        printf("Theres a bat in your room\n");
        loc = rnum(NROOM);
        return LOOP;
    }
    nearwump = 0;
    for (i = 0; i < NTUNN; i++)
        if (near(&room[p->tunn[i]], WUMP))
        {
            nearwump = 1;
            break;
        }
    if (nearwump || near(p, WUMP))
        printf("I smell a wumpus\n");
    if (near(p, BAT))
        printf("Bats nearby\n");
    if (near(p, PIT))
        printf("I feel a draft\n");
    printf("There are tunnels to");
    for (i = 0; i < NTUNN; i++)
        printf(" %d", p->tunn[i] + 1);
    printf("\n");
    return AGAIN;
}

int
again_state()
{
    printf("Move or shoot (m-s) ");
    switch (rline()) {
    case 'm':
        return MOVE;
    case 's':
        return SHOOT;
    }
    return AGAIN;
}

int
move_state()
{
    int i, j;

    if (tchar == '\n')
        printf("which room? ");
    i = rin() - 1;
    for (j = 0; j < NTUNN; j++)
        if (i == p->tunn[j])
        {
            loc = i;
            if (i == wloc)
                return MWUMP;
            return LOOP;
        }
    printf("You hit the wall\n");
    return AGAIN;
}

int
shoot_state()
{
    int i, j, k;

    if (tchar == '\n')
        printf("Give list of rooms terminated by 0\n");
    for (i = 0; i < 5; i++) {
        j = rin() - 1;
        if (j == -1)
            break;
        for (;;)
        {
            int found = 0;
            for (k = 0; k < NTUNN; k++)
                if (j == p->tunn[k]) {
                    found = 1;
                    break;
                }
            if (found)
                break;
            j = rnum(NROOM);
        }
        p = room + j;
        if (j == loc) {
            printf("You shot yourself\n");
            return DONE;
        }
        if (p->flag & WUMP) {
            printf("You slew the wumpus\n");
            return DONE;
        }
    }
    if (--arrow == 0) {
        printf("That was your last shot\n");
        return DONE;
    }
    return MWUMP;
}

int mwump_state()
{
    int i;

    p = room + wloc;
    p->flag &= ~WUMP;
    i = rnum(NTUNN + 1);
    if (i != NTUNN)
        wloc = p->tunn[i];
    room[wloc].flag |= WUMP;
    return LOOP;
}

int
done_state()
{
    printf("Another game? (y-n) ");
    if (rline() != 'y')
    {
        printf("\n");
        return LEAVE;
    }
    printf("Same room setup? (y-n) ");
    return (rline() == 'y') ? SETUP : INIT;
}

int (*states[NUM_STATES])() = {
    start_state, instruction_state, init_state, setup_state, loop_state,
    again_state, move_state, shoot_state, mwump_state, done_state, leave_state
};

int
main(void)
{
    randx = time(NULL);
    enum states state = START;
    for (;;)
        state = states[state]();
}

[ejolson]

A working version of the Wumpus state machine. I've tried to keep it as K&Rish as possible.

Question: Does the init function guarantee a Hamiltonian graph?

Given the publication date of PCC volume 2 number 1, I think the wump.c code we've been discussing was written around 1972. This, places it about 4 years before K&R C was finished and 6 years before the first edition of the well-known book. The coding style and use of the =+ sum operator makes me suspect it is one of the oldest surviving C programs.

From reading the code, my understanding is that the wump.c random graph generator makes traceable graphs which are not necessarily Hamiltonian. The difference, is that a traceable graph contains a path which visits all vertices once while a Hamiltonian graph contains a cycle which visits all vertices once. Note that the BASIC program for the PDP-8 appears to create random Hamiltonian graphs. It would be nice to know whether the PDP-8 exhibited the same infinite loop bug, presumably for certain sequences of random numbers, that my BBC BASIC adaptation does. I'll know more after translating the same code to Waterloo microBASIC for the SuperPET.

The state machine looks interesting. I'll give it a try soon to see if it plays in a dynamically equivalent way to the original. Recently I've been thinking about how to design a Wumpus-playing robot. What I'd prefer is a configurable parser based on regular expressions that allows the robot to randomly play any of a number of similar Wumpus programs to check whether they are dynamically equivalent. Since SNOBOL went out of fashion some time ago, would Perl be the right tool for this? That would save me from writing it in C.

[ejolson]

A working version of the Wumpus state machine.

I added an additional state to set the random number seed and it seems to play the same as the original. I'll know better after my Wumpus fuzzer is finished. Here is the slightly modified code.

Code: Select all

/*
 *  wumpus
 *  stolen from PCC Vol 2 No 1
 */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define NBAT  3
#define NROOM 20
#define NTUNN 3
#define NPIT  3

struct room
{
    int tunn[NTUNN];
    int flag;
} room[NROOM];

struct room* p;

const char* intro =
  "\n"
  "Welcome to 'Hunt the Wumpus.'\n"
  "\n"
  "The Wumpus lives in a cave of %d rooms.\n"
  "Each room has %d tunnels leading to other rooms.\n"
  "\n"
  "Hazards:\n"
  "\n"
  "Bottomless Pits - Some rooms have Bottomless Pits in them.\n"
  " If you go there, you fall into the pit and lose!\n"
  "Super Bats - Some other rooms have super bats.\n"
  " If you go there, a bat will grab you and take you to\n"
  " somewhere else in the cave where you could\n"
  " fall into a pit or run into the . . .\n"
  "\n"
  "Wumpus:\n"
  "\n"
  "The Wumpus is not bothered by the hazards since\n"
  "he has sucker feet and is too big for a bat to lift.\n"
  "\n"
  "Usually he is asleep.\n"
  "Two things wake him up:\n"
  " your entering his room\n"
  " your shooting an arrow anywhere in the cave.\n"
  "If the wumpus wakes, he either decides to move one room or\n"
  "stay where he was.  But if he ends up where you are,\n"
  "he eats you up and you lose!\n"
  "\n"
  "You:\n"
  "\n"
  "Each turn you may either move or shoot a crooked arrow.\n"
  "\n"
  "Moving - You can move to one of the adjoining rooms;\n"
  " that is, to one that has a tunnel connecting it with\n"
  " the room you are in.\n"
  "\n"
  "Shooting - You have 5 arrows.  You lose when you run out.\n"
  " Each arrow can go from 1 to 5 rooms.\n"
  " You aim by telling the computer\n"
  " The arrow's path is a list of room numbers\n"
  " telling the arrow which room to go to next.\n"
  " The list is terminated with a 0.\n"
  " The first room in the path must be connected to the\n"
  " room you are in.  Each succeeding room must be\n"
  " connected to the previous room.\n"
  " If there is no tunnel between two of the rooms\n"
  " in the arrow's path, the arrow chooses one of the\n"
  " three tunnels from the room it's in and goes its\n"
  " own way.\n"
  "\n"
  " If the arrow hits the wumpus, you win!\n"
  " If the arrow hits you, you lose!\n"
  "\n"
  "Warnings:\n"
  "\n"
  "When you are one or two rooms away from the wumpus,\n"
  "the computer says:\n"
  "   'I smell a Wumpus'\n"
  "When you are one room away from some other hazard, it says:\n"
  "   Bat    - 'Bats nearby'\n"
  "   Pit    - 'I feel a draft'\n";

#define BAT  1
#define PIT  2
#define WUMP 4

int arrow, loc, wloc, tchar, randx;

enum states {
    START = 0,
    INSTRUCTION,
    INIT,
    GETSEED,
    SETUP,
    LOOP,
    AGAIN,
    MOVE,
    SHOOT,
    MWUMP,
    DONE,
    LEAVE,
    NUM_STATES
};

int
rnum(int n)
{
    randx = randx * 1103515245U + 12345U;
    return (int)(((double)((randx >> 16) & 077777) / 32768.0) * n);
}

int
tunnel(int i)
{
    struct room* p;
    int c = 20, n, j;

    for (;;)
    {
        n = rnum(NROOM);
        if (n == i)
            if (--c > 0)
                continue;
        p = room + n;
        for (j = 0; j < NTUNN; j++)
            if (p->tunn[j] == -1) {
                p->tunn[j] = i;
                return n;
            }
    }
}

char
rline(void)
{
    char r;
    int c, leave_state();

    while ((c = getchar()) == ' ')
        ;
    r = (char)c;
    while (c != '\n' && c != ' ') {
        if (c == EOF || c == '\0')
            leave_state();
        c = getchar();
    }
    tchar = (char)c;
    return r;
}

int
rin()
{
    int n = 0, c = getchar(), leave_state();

    while (c != '\n' && c != ' ') {
        if (c < '0' || c>'9') {
            while (c != '\n') {
                if (c == EOF || c == 0)
                    leave_state();
                c = getchar();
            }
            return 0;
        }
        n = n * 10 + c - '0';
        c = getchar();
    }
    return n;
}

int
near(ap, ahaz)
struct room* ap;
int ahaz;
{
    int i;

    for (i = 0; i < NTUNN; i++)
        if (room[ap->tunn[i]].flag & ahaz)
            return 1;
    return 0;
}

void
exchange(int t[2])
{
    if (t[0] < t[1])
        return;
    t[0] = t[0] ^ t[1];
    t[1] = t[0] ^ t[1];
    t[0] = t[0] ^ t[1];
}

int
start_state()
{
    printf("Instructions? (y-n) ");
    return (rline() == 'y') ? INSTRUCTION : GETSEED;
}

int
leave_state()
{
    puts("\nGame over");
    exit(0);
}

int
instruction_state()
{
    printf(intro, NROOM, NTUNN);
    return GETSEED;
}

int
init_state()
{
    /*
     * initialize the room connections
     */
    int i, j, k;

    p = room;
    for (i = 0; i < NROOM; i++) {
        for (j = 0; j < NTUNN; j++)
            p->tunn[j] = -1;
        p++;
    }
    k = 0;
    for (i = 1; i < NROOM; ) {
        j = rnum(NROOM);
        p = room + j;
        if (j == k || p->tunn[0] >= 0 || p->tunn[1] >= 0)
            continue;
        p->tunn[1] = k;
        room[k].tunn[0] = j;
        k = j;
        i++;
    }
    p = room;
    for (i = 0; i < NROOM; i++) {
        for (j = 0; j < NTUNN; j++) {
            if (p->tunn[j] < 0)
                p->tunn[j] = tunnel(i);
            if (p->tunn[j] == i)
                return INIT;
            for (k = 0; k < j; k++)
                if (p->tunn[j] == p->tunn[k])
                    return INIT;
        }
        exchange(p->tunn);
        exchange(p->tunn + 1);
        exchange(p->tunn);
        p++;
    }
    return SETUP;
}

int
setup_state()
{
    /*
     * put in player, wumpus, pits and bats
     */
    int i;
    
    arrow = 5;
    p = room;
    for (i = 0; i < NROOM; i++) {
        p->flag = 0;
        p++;
    }
    for (i = 0; i < NPIT; ) {
        p = room + rnum(NROOM);
        if ((p->flag & PIT) == 0) {
            p->flag |= PIT;
            i++;
        }
    }
    for (i = 0; i < NBAT; ) {
        p = room + rnum(NROOM);
        if ((p->flag & (PIT | BAT)) == 0) {
            p->flag |= BAT;
            i++;
        }
    }
    i = rnum(NROOM);
    wloc = i;
    room[i].flag |= WUMP;
    for (;;) {
        i = rnum(NROOM);
        if ((room[i].flag & (PIT | BAT | WUMP)) == 0) {
            loc = i;
            break;
        }
    }
    return LOOP;
}

int
loop_state()
{
    /*
     *  main loop of the game
     */
    int i, nearwump;

    printf("You are in room %d\n", loc + 1);
    p = room + loc;
    if (p->flag & PIT) {
        printf("You fell into a pit\n");
        return DONE;
    }
    if (p->flag & WUMP) {
        printf("You were eaten by the wumpus\n");
        return DONE;
    }
    if (p->flag & BAT) {
        printf("Theres a bat in your room\n");
        loc = rnum(NROOM);
        return LOOP;
    }
    nearwump = 0;
    for (i = 0; i < NTUNN; i++)
        if (near(&room[p->tunn[i]], WUMP))
        {
            nearwump = 1;
            break;
        }
    if (nearwump || near(p, WUMP))
        printf("I smell a wumpus\n");
    if (near(p, BAT))
        printf("Bats nearby\n");
    if (near(p, PIT))
        printf("I feel a draft\n");
    printf("There are tunnels to");
    for (i = 0; i < NTUNN; i++)
        printf(" %d", p->tunn[i] + 1);
    printf("\n");
    return AGAIN;
}

int
again_state()
{
    printf("Move or shoot (m-s) ");
    switch (rline()) {
    case 'm':
        return MOVE;
    case 's':
        return SHOOT;
    }
    return AGAIN;
}

int
move_state()
{
    int i, j;

    if (tchar == '\n')
        printf("which room? ");
    i = rin() - 1;
    for (j = 0; j < NTUNN; j++)
        if (i == p->tunn[j])
        {
            loc = i;
            if (i == wloc)
                return MWUMP;
            return LOOP;
        }
    printf("You hit the wall\n");
    return AGAIN;
}

int
shoot_state()
{
    int i, j, k;

    if (tchar == '\n')
        printf("Give list of rooms terminated by 0\n");
    for (i = 0; i < 5; i++) {
        j = rin() - 1;
        if (j == -1)
            break;
        for (;;)
        {
            int found = 0;
            for (k = 0; k < NTUNN; k++)
                if (j == p->tunn[k]) {
                    found = 1;
                    break;
                }
            if (found)
                break;
            j = rnum(NROOM);
        }
        p = room + j;
        if (j == loc) {
            printf("You shot yourself\n");
            return DONE;
        }
        if (p->flag & WUMP) {
            printf("You slew the wumpus\n");
            return DONE;
        }
    }
    if (--arrow == 0) {
        printf("That was your last shot\n");
        return DONE;
    }
    return MWUMP;
}

int mwump_state()
{
    int i;

    p = room + wloc;
    p->flag &= ~WUMP;
    i = rnum(NTUNN + 1);
    if (i != NTUNN)
        wloc = p->tunn[i];
    room[wloc].flag |= WUMP;
    return LOOP;
}

int
done_state()
{
    printf("Another game? (y-n) ");
    if (rline() != 'y')
    {
        printf("\n");
        return LEAVE;
    }
    printf("Same room setup? (y-n) ");
    return (rline() == 'y') ? SETUP : INIT;
}

int
getseed_state()
{
    if(tchar == '\n')
        printf("What is the random seed? ");
    randx = rin();
    return INIT;
}

int (*states[NUM_STATES])() = {
    start_state, instruction_state, init_state, getseed_state,
    setup_state, loop_state, again_state, move_state, shoot_state,
    mwump_state, done_state, leave_state
};

int
main(void)
{
    enum states state = START;
    for (;;)
        state = states[state]();
}

It's quite amusing how all the goto statements disappeared. Since Rust is lacking in goto statements altogether, I expect the same technique could be used for a Rust version on the Pi.

[ejolson]

Here is a Hamiltonian graph created by the PDP-8 BASIC program translated to run on the SuperPET using Waterloo microBASIC.



A corresponding Wumpus hunt is





For reference the BASIC code for the SuperPET is

Code: Select all

    1 print "for help type 'help wumpus' as an os8 command"
    2 print "enter a random number";
    3 input m
    4 print "here we go----"
    5 print "down"
    6 print " o"
    7 print "  w"
    8 print "down"
    9 print
   10 dim a(20),b(20),c(20),d(20)
   20 dim q$(20),p$(10)
   25 read q$
   30 m=rnd(m)
   40 for z=1 to 20
   50   a(z)=0
   60   b(z)=0
   70   c(z)=0
   80   d(z)=0
   90 next z
  100 r0=.02
  105 b0=0
  110 l0=0
  120 for z=1 to 20
  130   if a(z)<>0 then 190
  140   f=int(20*rnd)+1
  150   if f=z then 140
  160   if a(f)<>0 then 140
  170   a(z)=f
  180   a(f)=z
  190 next z
  200 for z=1 to 20
  210   if b(z)<>0 then 280
  220   f=int(20*rnd)+1
  230   if f=z then 220
  240   if a(z)=f then 220
  250   if b(f)<>0 then 220
  260   b(z)=f
  270   b(f)=z
  280 next z
  290 for x=1 to 20
  300   if d(x)<>0 then 410
  310   if x=1 then 340
  320   b(y)=x
  330   b(x)=y
  340   y=x
  350   d(y)=1
  360   y=a(y)
  370   d(y)=1
  380   if b(y)=x then 410
  390   y=b(y)
  400   goto 350
  410   d(x)=0
  420 next x
  430 b(y)=1
  440 b(1)=y
  450 for z=1 to 20
  460   if c(z)<>0 then 540
  470   f=int(20*rnd)+1
  480   if f=z then 470
  490   if f=a(z) then 470
  500   if f=b(z) then 470
  510   if c(f)<>0 then 470
  520   c(z)=f
  530   c(f)=z
  540 next z
  550 for x=1000 to 10000 step 9000
  560   for z=1 to 3
  570     f=int(20*rnd)+1
  580     if d(f)>=x then 570
  590     d(f)=d(f)+x
  600     gosub 2130
  610   next z
  620 next x
  630 f=int(20*rnd)+1
  640 x=100000
  650 d(f)=d(f)+x
  660 gosub 2130
  670 w=f
  680 f=a(w)
  690 gosub 2130
  700 f=b(w)
  710 gosub 2130
  720 f=c(w)
  730 gosub 2130
  740 h=int(20*rnd)+1
  750 if d(h)>=1000 then 740
  760 for s=5 to 1 step -1
  770   if l0=0 then 777
  772   gosub 1740
  774   print "i see that tunnels a b and c lead to rooms";
  776   print value$(a(h));b(h);"and";c(h);"respectively"
  777   if rnd>.04 then 779
  778   gosub 2191
  779   j=d(h)
  780   if j>=1000 then 1240
  790   goto 1090
  800   if j=0 then 890
  810   if j=int(j/10)*10 then 830
  820   print "i hear squeaking, ";
  830   j=int(j/10)
  840   if j=int(j/10)*10 then 860
  850   print "i feel a draft, ";
  860   if j<10 then 880
  870   print "i smell a wumpus ";
  880   print
  890   print "you are in room";h;"move through tunnel";
  895   h1=h
  900   input p$
  905   if p$="q" then 2310
  910   if p$<>"a" then 940
  920   h=a(h)
  930   goto 770
  940   if p$<>"b" then 970
  950   h=b(h)
  960   goto 770
  970   if p$<>"c" then 1000
  980   h=c(h)
  990   goto 770
 1000   if p$="shoot" then 1470
 1010   if p$<>"map" then 1040
 1020   gosub 2200
 1030   goto 779
 1040   if p$<>"lights on" then 1070
 1050   l0=1
 1060   goto 770
 1070   if p$<>"lights off" then 770
 1075   l0=0
 1080   goto 770
 1090   if rnd>r0 then 800
 1100   print "you tripped on a ";q$;" in room";h;
 1110   f=int(20*rnd)+1
 1120   if f=a(h) then 1150
 1130   if f=b(h) then 1150
 1140   if f<>c(h) then 1110
 1145   if f=h then 1110
 1150   print "and have tumbled into room";f
 1160   if r0<.2 then 1190
 1165   if rnd<.5 then 1190
 1170   print "you are getting clumsier by the minute"
 1180   print "you seem to be stumbling around ";
 1182   print value$(r0*100);"% of the time"
 1190   r0=r0+.02
 1200   h=f
 1210   if d(h)>=100000 then 1430
 1220   gosub 1740
 1230   goto 770
 1240   j=int(j/1000)
 1250   if j>=10 then 1300
 1260   print "there is a super-bat in room ";
 1262   print value$(h);".  flap--flap ouch!!"
 1270   h=int(20*rnd)+1
 1280   if d(h)>999 then 1270
 1283   if h=h1 then 1270
 1290   goto 770
 1300   if j>=100 then 1430
 1310   print "you fell into the bottomless pit in room";h
 1320   if j-10<>0 then 2050
 1330   if d(h)<>int(d(h)/10)*10 then 2070
 1340   print "play again (yes or no)";
 1350   restore
 1360   input p$
 1370   print
 1380   if p$="yes" then 40
 1390   if p$<>"map" then 1420
 1400   gosub 2200
 1410   goto 1340
 1420   stop
 1430   print "you have been devoured by the wumpus in room";h
 1440   goto 1340
 1450   print "you shot yourself"
 1460   goto 1340
 1470   print "the arrow zings in ";
 1480   k=h
 1490   k1=h
 1500   for r=1 to 5
 1510     print "to room";
 1520     input m
 1530     if m=a(k) then 1600
 1540     if m=b(k) then 1600
 1550     if m=c(k) then 1600
 1560     if m=0 then 1700
 1570     r=6
 1580     m=int(20*rnd)+1
 1590     goto 1530
 1600     if r<=5 then 1626
 1620     print "the arrow went astray"
 1624     goto 1630
 1626     if m=k1 then 1570
 1630     if m=h then 1450
 1640     if d(m)<100000 then 1670
 1650     print "you have slain the wumpus"
 1655     s=s-1
 1660     goto 1340
 1670     if int(d(m)/1000)=int(d(m)/10000)*10 then 1678
 1671     print "you picked off an innocent super-bat"
 1672     x=-1000
 1673     f=m
 1674     gosub 2130
 1675     d(m)=d(m)-1000
 1676     b0=b0+1
 1677     goto 1700
 1678     k1=k
 1680     k=m
 1690   next r
 1700   gosub 1740
 1710 next s
 1720 print "you have exhausted your supply of arrows -- the show's over"
 1730 goto 1340
 1740 if rnd>.5 then 2000
 1750 print "roar**thud**thud**rruummbbllee**thwump**zzzzzzzzzzz"
 1760 x=-100000
 1770 f=w
 1780 gosub 2130
 1790 f=a(w)
 1800 gosub 2130
 1810 f=b(w)
 1820 gosub 2130
 1830 f=c(w)
 1840 gosub 2130
 1850 d(w)=d(w)-100000
 1860 f=int(20*rnd)+1
 1870 if f=a(w) then 1900
 1880 if f=b(w) then 1900
 1890 if f<>c(w) then 1860
 1900 x=100000
 1910 d(f)=d(f)+x
 1920 w=f
 1930 gosub 2130
 1940 f=a(w)
 1950 gosub 2130
 1960 f=b(w)
 1970 gosub 2130
 1980 f=c(w)
 1990 gosub 2130
 2000 read q$
 2010 if q$<>"end" then 2040
 2020 restore
 2030 goto 2000
 2040 return
 2050 print "you have been snatched up by a super-bat"
 2060 goto 1270
 2070 print "there is a bat in an adjacent room -- he's flying this way!"
 2080 if rnd>.25 then 2110
 2090 print "you struck your head on a ";q$;" good-byyeee"
 2100 goto 1340
 2110 print "phewww!!!  ";
 2120 goto 2050
 2130 f1=a(f)
 2140 d(f1)=d(f1)+x/1000
 2150 f1=b(f)
 2160 d(f1)=d(f1)+x/1000
 2170 f1=c(f)
 2180 d(f1)=d(f1)+x/1000
 2190 return
 2191 if b0<0 then 2199
 2192 b0=b0-1
 2193 f=int(20*rnd)+1
 2194 if int(d(f)/1000)<>int(d(f)/10000)*10 then 2193
 2195 x=1000
 2196 d(f)=d(f)+x
 2197 gosub 2130
 2198 print "another super-bat has been born.  looks like a strong one!"
 2199 return
 2200 z=1
 2205 print "GRAPH MAZE {"
 2210 print "  OVERLAP=FALSE; SPLINES=TRUE; SEP=1.0"
 2215 if z>a(z) then 2225
 2220 print " ";z;"--";a(z)
 2225 if z>b(z) then 2235
 2230 print " ";z;"--";b(z)
 2235 if z>c(z) then 2245
 2240 print " ";z;"--";c(z)
 2245 z=z+1
 2250 if z<=20 then 2215
 2255 print "}"
 2280 return
 2290 data "corpse","dead bat","broken arrow","stalagmite","pebble"
 2291 data "wumpus claw","ledge","lunch bag","dog"
 2300 data "end"
 2310 end

Note, to get the program to run, rnd(0) was to be changed to rnd and some formatting changes were made to account for differences in how semicolons are interpreted in print statements.

Edit: If the images are not showing for you, and as of today they don't for me when using Chrome on my phone, try a different browser. It appears someone at Google thought it'd be a good idea to prevent a page secured by TLS to load images that aren't also cryptographically secured. You can click the images to view them separately and they load just fine using Firefox. I'm looking into getting a TLS certificate for that server, but it is likely to be difficult.

[jalih]

"entry" is not a keyword or reserved word in C.

It was a reserved word, but was dropped later on... Not suprising since, Ritchie worked on Multics operating system early on.

Old C reference manual.

[ejolson]

"entry" is not a keyword or reserved word in C.

It was a reserved word, but was dropped later on... Not suprising since, Ritchie worked on Multics operating system early on.

Old C reference manual.

Thanks for posting that link.

It's interesting that page 28 indicates the grammar rule

return ( expression ) ;

confirming the suspicion already voiced that early C required parenthesis for the return statement as present in the Hunt the Wumpus code included with historic versions of Unix.

[jahboater]

"entry" is not a keyword or reserved word in C.

It was a reserved word, but was dropped later on... Not suprising since, Ritchie worked on Multics operating system early on.

Old C reference manual.

Lots on interesting stuff in that document, thanks for posting.

I see that 01289 was a valid octal literal with the digits 8 and 9 having the values 10 and 11

Right from the start, the C library functions were documented in the UNIX man pages.

Looks like the GCOS implementation and the UNIX implementation were done at the same time by different people.
When I used the language B on GCOS (Honeywell 6000 mainframe), it was most definitely a compiler not an interpreter as the doc says it was; presumably it was referring to UNIX.

[Heater]

"entry" is not a keyword or reserved word in C.

It was a reserved word, but was dropped later on...

Well I never.

I was wonder what they had in mind as a use for it. So had a look at IBM's "A Guide to PL/I for FORTRAN Users" http://bitsavers.org/pdf/ibm/360/pli/SC ... _May68.pdf

Seems it does indeed give a procedure multiple entry points. They have a great example of a random number generator that may or may not need seeding:

Code: Select all

SETRND: PROCEDURE (I, J);
        DECLARE (MIER, MICAND) STATIC;
        MIER = I; MICAND = J;
        RETURN;
GETRND: ENTRY;
        MICAND = MIER * MICAND;
        RETURN (MICAND);
END; 

Neat ha?

[Heater]

"entry" is not a keyword or reserved word in C.

It was a reserved word, but was dropped later on...

Well I never.

I was wondering what they had in mind as a use for it in C. So had a look at IBM's "A Guide to PL/I for FORTRAN Users" to see how it was used there. http://bitsavers.org/pdf/ibm/360/pli/SC ... _May68.pdf

Seems it does indeed give a procedure multiple entry points. They have a great example of a random number generator that may or may not need seeding:

Code: Select all

SETRND: PROCEDURE (I, J);
        DECLARE (MIER, MICAND) STATIC;
        MIER = I; MICAND = J;
        RETURN;
GETRND: ENTRY;
        MICAND = MIER * MICAND;
        RETURN (MICAND);
END; 

Used like so:

Code: Select all

CALL SETRND (M, N);
x = GETRND; 

Neat ha?

[Paeryn]

BTW, return is not a function! It irks when you see something like this: return(0).

Neither are if() while() switch() functions, but they require the brackets.

Brackets are needed in those for syntactic disambiguation, otherwise the parser would choke if the body starts with a token which is also valid as part of the conditional expression e.g.

Code: Select all

void calc(int *data, int *some_total)
{
  while *data > 10
    *some_total += *data++;
}

The parser would see the body of the loop as being part of the condition making it look as though you were trying to multiply an int by an int* and that the left operand of += is now no longer an lvalue i.e. it would be parsed something like

Code: Select all

while ((*data > 10 * some_total) += *data++)
  ;

[lurk101]

It's quite amusing how all the goto statements disappeared.

They're still there, just obfuscated. In the end it all turns into conditional branches.

[ejolson]

Brackets are needed in those for syntactic disambiguation, otherwise the parser would choke if the body starts with a token which is also valid as part of the conditional expression e.g.

Code: Select all

void calc(int *data, int *some_total)
{
  while *data > 10
    *some_total += *data++;
}

The parser would see the body of the loop as being part of the condition making it look as though you were trying to multiply an int by an int* and that the left operand of += is now no longer an lvalue i.e. it would be parsed something like

Code: Select all

while ((*data > 10 * some_total) += *data++)
  ;

That makes sense. One difficulty I have with golang--coauthored by the same Ken Thompson who wrote wump.c--are the ambiguities which result from the implicit semicolon sprinkling phase of the language parser. They also took the parenthesis out of the for loops. I guess the idea was the least notation needed by a computer must be the easiest to parse for a human. In my opinion, all of these syntactic changes were gratuitous and did not address the problem with C++ that golang was trying to solve.

My experience is notation is an important factor related to thinking. Without good notation, a complicated algorithm can be impossible to create and quite difficult to turn into code. As shown by COBOL and now golang (along with features in many modern languages), confusing notation makes the program harder to read, write, understand and debug.

For an example of an algorithm that's nearly impossible to understand because of the notation used to express it, please consider the routine in the PDP-8 code for Hunt the Wumpus which ensures the generated graph is Hamiltonian. Could anyone remove the bug in this 42 year old program so it doesn't randomly get stuck in an infinite loop?

[lurk101]

Old C reference manual.

Interesting that floats and doubles were defined and sized essentially the same as they are today thus avoiding the ambiguity present in C for int and long sizing.

Still scratching my head as to why the wumpus random function, given the same seed, will return the same sequence either compiled (or interpreted) for 16 bit or 32 bit.

[ejolson]

Old C reference manual.

Interesting that floats and doubles were defined and sized essentially the same as they are today thus avoiding the ambiguity present in C for int and long sizing.

Still scratching my head as to why the wumpus random function, given the same seed, will return the same sequence either compiled (or interpreted) for 16 bit or 32 bit.

Could this be because randx was declared as a long on the PDP-11 but as an int on the Raspberry Pi?

It takes care to ensure that algorithm produces the same random numbers on different platforms. More details about generating historical random numbers which can't be influenced using Jedi mind tricks with a Raspberry Pi are discussed at

viewtopic.php?p=1738151#p1738151

I think position independent 6809 code could be written into an array in Waterloo microPascal and then called by address using the sysproc routine. While a bit messy, this appears better than other techniques that involve reserving a block of memory before launching the integrated development environment.

Have you looked at the assembler? I think all one needs are routines for 32-bit multiplication and addition in order to significantly improve the speed of the random graph generator.

[lurk101]

Could anyone remove the bug in this 42 year old program so it doesn't randomly get stuck in an infinite loop?

Ack! Another assignment. I smell a college professor nearby.

[ejolson]

Could anyone remove the bug in this 42 year old program so it doesn't randomly get stuck in an infinite loop?

Ack! Another assignment. I smell a college professor nearby.

Haha! It looks like we cross posted while I was making another request for help.

[hippy]

It's not clear to me that nested functions in C are much use. For example, going along with our "function maker function" idea above, we would like to write that in C. Like so:

Code: Select all

#include <stdio.h>

// Define function pointer type
typedef int(*func_t)(int);

func_t make_function(int n)
{
    int nested_funtion(int m)
    {
        return n + m;
    }
    return nested_funtion;
}

int main()
{
    func_t function = make_function(42);
    int x = function(42); 
    printf("%d\n", x);
}

Which compiles without warning but of course that segfaults! Good old C

It compiled and ran fine with GCC for me on my Pi; no segfault to be seen ...

Code: Select all

pi@Pi3B:~/apps/zpu $ gcc -o heater heater.c
pi@Pi3B:~/apps/zpu $ ./heater
84
pi@Pi3B:~/apps/zpu $ 

Maybe you were using a different compiler to compile your 'C program' which isn't actually C, and must therefore be considered an entirely different language to C as per Python 3 ?

[ejolson]

It's not clear to me that nested functions in C are much use. For example, going along with our "function maker function" idea above, we would like to write that in C. Like so:

Code: Select all

#include <stdio.h>

// Define function pointer type
typedef int(*func_t)(int);

func_t make_function(int n)
{
    int nested_funtion(int m)
    {
        return n + m;
    }
    return nested_funtion;
}

int main()
{
    func_t function = make_function(42);
    int x = function(42); 
    printf("%d\n", x);
}

Which compiles without warning but of course that segfaults! Good old C

It compiled and ran fine with GCC for me on my Pi; no segfault to be seen ...

Code: Select all

pi@Pi3B:~/apps/zpu $ gcc -o heater heater.c
pi@Pi3B:~/apps/zpu $ ./heater
84
pi@Pi3B:~/apps/zpu $ 

Maybe you were using a different compiler to compile your 'C program' which isn't actually C, and must therefore be considered an entirely different language to C as per Python 3 ?

Woohoo! That's fantastic. I smell a Wumpus function generator generating function nearby. Please be careful of the super bats and bottomless pits.

[hippy]

Brackets are needed in those for syntactic disambiguation, otherwise the parser would choke if the body starts with a token which is also valid as part of the conditional expression e.g.

Code: Select all

void calc(int *data, int *some_total)
{
  while *data > 10
    *some_total += *data++;
}

I believe it depends on the parser being used. Other languages don't have that problem and none of the parsers I've written ever have.

Unless allowing "<expr> ::= <expr> <expr>" for some bizarre reason there would be an operator required between the two <expr> and most parsers would see the absence of that as the end of the expression.

Edit : I belatedly realised what you mean; whether the * is a multiply operator or an indirection - I've always held that C is a poorly designed language!

I can well imagine original C specified some things simply to make parsing or code generation easier. Some of those things have persisted while others have disappeared as the C language evolved and turned into a different C language to what there was originally.

[Heater]

Brackets are needed in those for syntactic disambiguation,...

Only if you decide on an irregular syntax to start with.

Decisions, decisions. There are so many decisions to be made when deigning a programming language. It's amazing we ever end up with something consistent and coherent.

C decided that it should support single statements as what happens after "if". As well as multiple statements in a block surrounded by curlies "{...}".

As a result it required round brackets around the "if" clause.

Rust on the other hand decided that whatever is subject to "if" is required to be surrounded by curlies. Even if it is only a single statement. Which means it no longer needs braces around the "if" clause.

Similarly for other constructs.

Python decided that line endings and white space were significant. That means it can dispose of braces, curlies and semicolons.

Javascript decided that semicolons were a good idea but we could get away without them. Which can lead to non-obvious results.

Lisp bypassed all of that crap and decided to have brackets all over the place.

[ejolson]

Brackets are needed in those for syntactic disambiguation, otherwise the parser would choke if the body starts with a token which is also valid as part of the conditional expression e.g.

Code: Select all

void calc(int *data, int *some_total)
{
  while *data > 10
    *some_total += *data++;
}

I believe it depends on the parser being used. Other languages don't have that problem and none of the parsers I've written ever have.

Unless allowing "<expr> ::= <expr> <expr>" for some bizarre reason there would be an operator required between the two <expr> and most parsers would see the absence of that as the end of the expression.

I can well imagine original C specified some things simply to make parsing or code generation easier. Some of those things have persisted while others have disappeared as the C language evolved and turned into a different C language to what there was originally.

This problem seems to originate from using the same symbol as a unary or binary operator depending on context. In my opinion placing a keyword such as do or begin after the conditional, as in Pascal, is both easy to read and type.

Edit: I see the post I was replying to has been edited, so never mind. However, to emphasise what I stated above, rather than { and } I still find do, begin and end easier to type--mostly because the characters needed are likely to be in the same position on the keyboard--from a 3270 display terminal to a SuperPET to a Pi. This even holds for AZERTY. Who was that Dvorak guy anyway?

[lurk101]

Could anyone remove the bug in this 42 year old program so it doesn't randomly get stuck in an infinite loop?

Ack! Another assignment. I smell a college professor nearby.

Haha! It looks like we cross posted while I was making another request for help.

How many arrows do I get?

[hippy]

C decided that it should support single statements as what happens after "if". As well as multiple statements in a block surrounded by curlies "{...}".

As a result it required round brackets around the "if" clause.

I would argue that it's more because of the decision to use '*' for multiple purposes which causes an ambiguity if one doesn't force the expression to be within brackets or the if clause to be within braces.

True, once they settled on having the ambiguity, settled on allowing non-braced statements, that then forced enclosure of expressions within parenthesis.

If they'd used '@' for indirection or some other syntax for that, there wouldn't have been a problem.