lurk101
Posts: 356
Joined: Mon Jan 27, 2020 2:35 pm

Re: A Birthday Present for Fido

Wed Oct 14, 2020 4:30 pm

hippy wrote:
Wed Oct 14, 2020 4:23 pm
If they'd used '@' for indirection or some other syntax for that, there wouldn't have been a problem.
They were using teletypes for IO. Not sure what the available character set looked like.

hippy
Posts: 8923
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A Birthday Present for Fido

Wed Oct 14, 2020 4:33 pm

jahboater wrote:
Tue Oct 13, 2020 8:57 pm
They [nested functions] are just normal functions, usually small service functions, that are of no interest outside of the surrounding function.
The usual programming rule of reducing visibility as far as possible is one motivation.
+1 limiting scope and access is my basis for using nested functions.

Anyway ... back to Fido ...

ejolson
Posts: 6354
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Wed Oct 14, 2020 4:53 pm

lurk101 wrote:
Wed Oct 14, 2020 4:30 pm
hippy wrote:
Wed Oct 14, 2020 4:23 pm
If they'd used '@' for indirection or some other syntax for that, there wouldn't have been a problem.
They were using teletypes for IO. Not sure what the available character set looked like.
The teletype keyboard looks like

Image

Note that @ appears on the P key. What is missing are { and }, which explains why C has trigraph representations for these characters. I've heard Fido argue that those trigraphs make the begin and end structures in C code visually easier for a dog to parse.

Heater
Posts: 17137
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Wed Oct 14, 2020 5:11 pm

When C++ removed trigraphs from the language in C++17 it gave me hope for the sanity of the whole project.
Memory in C++ is a leaky abstraction .

User avatar
jahboater
Posts: 6522
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Wed Oct 14, 2020 5:22 pm

ejolson wrote:
Wed Oct 14, 2020 4:17 pm
However, to emphasise what I stated above, rather than { and } I still find do, begin and end easier to type--
#define begin {
#define end }

:)
Pi4 8GB and Pi4 4GB running Raspberry Pi OS 64-bit

ejolson
Posts: 6354
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Wed Oct 14, 2020 5:51 pm

jahboater wrote:
Wed Oct 14, 2020 5:22 pm
ejolson wrote:
Wed Oct 14, 2020 4:17 pm
However, to emphasise what I stated above, rather than { and } I still find do, begin and end easier to type--
#define begin {
#define end }

:)
That's the idea. I think the definition of end should include a semicolon before the closing bracket. A similar set of macros were used by Stephen Bourne when writing the Unix shell of the same name. I'm not sure a similar trick can be performed for the trigraphs, so that might be a complete loss.

Fortunately, Fido's birthday present is almost finished. Do you think we need a Github repository like everyone else to hold the Wumpus codes, or would that unnecessarily add to the entropy of the universe?

lurk101
Posts: 356
Joined: Mon Jan 27, 2020 2:35 pm

Re: A Birthday Present for Fido

Wed Oct 14, 2020 5:55 pm

I don't see how this single addition significantly adds to the overall chaos. It might be interesting to see if pull requests would ensue?
Last edited by lurk101 on Wed Oct 14, 2020 5:59 pm, edited 1 time in total.

User avatar
Paeryn
Posts: 3150
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A Birthday Present for Fido

Wed Oct 14, 2020 8:04 pm

ejolson wrote:
Wed Oct 14, 2020 5:51 pm
jahboater wrote:
Wed Oct 14, 2020 5:22 pm
ejolson wrote:
Wed Oct 14, 2020 4:17 pm
However, to emphasise what I stated above, rather than { and } I still find do, begin and end easier to type--
#define begin {
#define end }

:)
That's the idea. I think the definition of end should include a semicolon before the closing bracket. A similar set of macros were used by Stephen Bourne when writing the Unix shell of the same name. I'm not sure a similar trick can be performed for the trigraphs, so that might be a complete loss.
Trigraphs are translated before anything else and they are always translated everywhere with no regard to context (that includes inside strings). If you define a macro to expand to part of a trigraph and try to use it with the end of a trigraph then the three characters won't count as a trigraph so below begin correctly becomes { but qq> doesn't become } because qq is expanded after the trigraph translation phase happened.

Code: Select all

#define begin ??<
#define qq ??
int main(void)
begin
  return 0;
qq>
On a good point, gcc doesn't translate trigraphs by default. Instead it will just warn you that it saw a trigraph sequence, you have to pass -trigraphs to the compiler if you want to use them.
She who travels light — forgot something.
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!

lurk101
Posts: 356
Joined: Mon Jan 27, 2020 2:35 pm

Re: A Birthday Present for Fido

Wed Oct 14, 2020 10:57 pm

ejolson wrote:
Wed Oct 14, 2020 2:49 pm
Could anyone remove the bug in this 42 year old program so it doesn't randomly get stuck in an infinite loop?
Not much to be said about that particular cave generator other than it's severely broken, failing to generate a viable cave most of the time. If I had to guess the author's intent it would be this. Generates first time every time and Hamiltonian to boot.

Code: Select all

/*
 *  wumpus
 *  stolen from PCC Vol 2 No 1
 *
 *  This version has been updated to compile cleanly using gcc on
 *  the Raspberry Pi and enhanced to allow the random number seed
 *  to be specified directly for regression testing purposes.
 */

#include <stdio.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;
}

exchange(t)
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;

    for (i = 0; i < NROOM; i++, p++)
        for (j = 0; j < NTUNN; j++)
            room[i].tunn[j] = -1;
    k = 0;
    for (i = 0; i < NROOM - 1; i++, k = j) {
        do j = rnum(NROOM);
        while (j == k || room[j].tunn[0] >= 0 || room[j].tunn[1] >= 0);
        room[k].tunn[0] = j;
        room[j].tunn[1] = k;
    }
    room[k].tunn[0] = 0;
    room[0].tunn[1] = k;
    for (i = 0; i < NROOM; i++, k = j) {
        if (room[i].tunn[2] < 0)
        {
            do j = rnum(NROOM);
            while (j == i || room[j].tunn[2] >= 0 || j == room[i].tunn[0] || j == room[i].tunn[1]
                || i == room[j].tunn[0] || i == room[j].tunn[1]);
            room[i].tunn[2] = j;
            room[j].tunn[2] = i;
        }
        exchange(room[i].tunn);
        exchange(room[i].tunn + 1);
        exchange(room[i].tunn);
    }
    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]();
}

User avatar
jahboater
Posts: 6522
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 12:20 am

lurk101 wrote:
Wed Oct 14, 2020 10:57 pm
Not much to be said about that particular cave generator other than it's severely broken, failing to generate a viable cave most of the time. If I had to guess the author's intent it would be this. Generates first time every time and Hamiltonian to boot.
Nice!
I had to declare exchange() void before it compiled cleanly with gcc 10.2
Pi4 8GB and Pi4 4GB running Raspberry Pi OS 64-bit

lurk101
Posts: 356
Joined: Mon Jan 27, 2020 2:35 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 1:23 am

K&R didn't have void.

As for the algorithm, it's far from ideal. It relies on repeated invocations of rnum(20) till it finds an available room. This gets expensive when there are just a few rooms left. Given @ejolson's goal of running this in interpreted Pascal on an emulated PET I'm not sure this would be any faster than just repeatedly trying an algorithm that doesn't work all of the time. Fixing the issue requires additional plumbing and I'm not sure it's worth it.

Pascal had sets and set operators as I recall but does Waterloo Pascal on the PET have them? They'd be useful applied here.

ejolson
Posts: 6354
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Thu Oct 15, 2020 2:29 am

lurk101 wrote:
Thu Oct 15, 2020 1:23 am
As for the algorithm, it's far from ideal. It relies on repeated invocations of rnum(20) till it finds an available room. This gets expensive when there are just a few rooms left. Given @ejolson's goal of running this in interpreted Pascal on an emulated PET I'm not sure this would be any faster than just repeatedly trying an algorithm that doesn't work all of the time. Fixing the issue requires additional plumbing and I'm not sure it's worth it.

Pascal had sets and set operators as I recall but does Waterloo Pascal on the PET have them? They'd be useful applied here.
Of course it has sets! They didn't call it a SuperPET for nothing. The full documentation for microPascal is available at

https://archive.org/details/Super_PET_W ... icroPascal

I just finished a Zoom conference with the dog developer. Fido is quite excited about having a birthday soon. I suspect an end to being banned from all computers, rather than the prospect of playing Hunt the Wumpus, is the main cause for celebration. At any rate, I received a very wobbly looking C program through the chat feature with the request to try it out.

These were the results:

Code: Select all

$ ./fido 
Degree of graph: 3
Number of vertices: 6
Building a graph of degree 3 on 6 vertices.
There will be 9 edges in the graph.
Image

Code: Select all

$ ./fido 
Degree of graph: 4
Number of vertices: 6
Building a graph of degree 4 on 6 vertices.
There will be 12 edges in the graph.
Image

Code: Select all

$ ./fido 
Degree of graph: 4 
Number of vertices: 7
Building a graph of degree 4 on 7 vertices.
There will be 14 edges in the graph.
Image

which looks pretty promising. But then I tried

Code: Select all

$ ./fido 
Degree of graph: 3
Number of vertices: 20
Building a graph of degree 3 on 20 vertices.
There will be 30 edges in the graph.
Image

Astonished that the graph was not connected, I asked, but the super pet only barked something about how super bats and other super beings were able to move to any room they like even if there is no path. My idea is to randomly shuffle the edges until the resulting graph is connected. This should allow the creation of mazes which correspond to graphs which are neither traceable nor Hamiltonian.

ejolson
Posts: 6354
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Thu Oct 15, 2020 5:26 am

lurk101 wrote:
Wed Oct 14, 2020 10:57 pm
ejolson wrote:
Wed Oct 14, 2020 2:49 pm
Could anyone remove the bug in this 42 year old program so it doesn't randomly get stuck in an infinite loop?
Not much to be said about that particular cave generator other than it's severely broken, failing to generate a viable cave most of the time. If I had to guess the author's intent it would be this. Generates first time every time and Hamiltonian to boot.
I added a routine to output some graphviz format files for drawing the mazes. For the seeds 3141, 2718 and 1178, respectively, I obtained

Image

Image

Image

Woohoo! Those mazes look playable to me. I wonder where's the Wumpus.

To get the map output, simply press g instead of entering a move. Then mouse the resulting output into a file for processing with the neato program in graphvis using a comand such as

$ neato -Gstart=rand -Tsvg -o maze.svg maze.dot

For reference, the modified code is

Code: Select all

/*
 *  wumpus
 *  stolen from PCC Vol 2 No 1
 *
 *  This version has been updated to compile cleanly using gcc on
 *  the Raspberry Pi and enhanced to allow the random number seed
 *  to be specified directly for regression testing purposes.
 */

#include <stdio.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,
    MKMAP,
    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(t)
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;

    for (i = 0; i < NROOM; i++, p++)
        for (j = 0; j < NTUNN; j++)
            room[i].tunn[j] = -1;
    k = 0;
    for (i = 0; i < NROOM - 1; i++, k = j) {
        do j = rnum(NROOM);
        while (j == k || room[j].tunn[0] >= 0 || room[j].tunn[1] >= 0);
        room[k].tunn[0] = j;
        room[j].tunn[1] = k;
    }
    room[k].tunn[0] = 0;
    room[0].tunn[1] = k;
    for (i = 0; i < NROOM; i++, k = j) {
        if (room[i].tunn[2] < 0)
        {
            do j = rnum(NROOM);
            while (j == i || room[j].tunn[2] >= 0 || j == room[i].tunn[0] || j == room[i].tunn[1]
                || i == room[j].tunn[0] || i == room[j].tunn[1]);
            room[i].tunn[2] = j;
            room[j].tunn[2] = i;
        }
        exchange(room[i].tunn);
        exchange(room[i].tunn + 1);
        exchange(room[i].tunn);
    }
    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;
    case 'g':
        return MKMAP;
    }
    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
mkmap_state()
{
    int i,j;
    printf("graph maze {\n  overlap=false; splines=true; sep=1.0\n");
    for(i=0; i<NROOM; i++) {
        for(j=0; j<NTUNN; j++) {
            if(i<room[i].tunn[j])
                printf("  %d -- %d\n",i+1,room[i].tunn[j]+1);
        }
    }
    printf("}\n");
    return AGAIN;
}

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, mkmap_state
};

int
main(void)
{
    enum states state = START;
    for (;;)
        state = states[state]();
}
I also added back in the missing void to silence the compiler.

Heater
Posts: 17137
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 6:57 am

jahboater wrote:
Tue Oct 13, 2020 8:57 pm
Heater wrote:
Tue Oct 13, 2020 8:11 pm
They seem very limited seeing as one cannot return them from where they were created.
Why on earth would you want to do that?
I have never tried to, nor wanted to, nor see the point of, passing pointers to them outside of their scope.
Why have block structure and scope rules if you just want to circumvent them?
It sounds as daft as returning the address of an object on the stack - a common beginner fault.
Good question.

In many languages there is the idea that code is data. That is to say functions can be thought of as values or data items. To be created and passed around though parameters, returned from other functions, stored in data structures and so on.

This is the notion of "first class functions" first brought to the world in 1958 with Lisp. Now a days championed by the Lisp like languages Racket, Common Lisp, Scheme and Clojure etc. And the "Functional Programming" languages like Haskell.

Even C++ felt the need for first class functions, hence the arrival of lambdas into the language. As did Javascript, Python and Rust.

As to "why on earth would you want to do that", I'm no champion of the functional programming style. Mostly it gives me headache. But it is a way to compose functions into higher level functions and compose those into your complete program. Which is kind of neat and even I have found it useful.

Mostly I create nested/inner functions like that to be used as threads. Where they will likely be running longer than the function that created them. Very much out of scope of their parent.

So GCC's nested functions are a neat way to contain the scope of things and organize code, as you say. But they are extremely limited when compared to the world of first class functions. So limited that C has not accepted them as part of the language.
Memory in C++ is a leaky abstraction .

User avatar
jahboater
Posts: 6522
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 9:11 am

Heater wrote:
Thu Oct 15, 2020 6:57 am
So GCC's nested functions are a neat way to contain the scope of things and organize code, as you say. But they are extremely limited when compared to the world of first class functions.
The thing is, C is a procedural or imperative language, not a functional language. If I wanted the functional paradigm I would use Haskell or some such instead. I'm not convinced that adding lamda's to C++ was an attempt by the standards committee to change C++ into a functional language. Though you can do a lot with function pointers (arrays of event handlers for example), I would not use them to try and change the basic nature of the language. To say nested functions are limited and useless because you cant use them to make C behave like Haskell is crazy.
Heater wrote:
Thu Oct 15, 2020 6:57 am
So limited that C has not accepted them as part of the language.
Have you got a reference for that?
I suspect they are not included for different, more mundane, reasons (like no influential body has seriously proposed them, or perhaps the overheads of allowing access to the parent function's stack didn't fit with C's efficiency expectations, or it was too much change for C's glacially slow evolution, or weak compilers may not be able to support them, or Denis Ritchie didn't include them - and that's good enough).

Incidentally, you may happily return the address of a nested function from the parent, but if that nested function accesses the stack or the arguments of its parent, and you call the nested function after its parent has returned, then its obviously going to fail badly. Just like returning the address of something on the stack - daft. You could declare the nested function "pure" and it would likely work.
Pi4 8GB and Pi4 4GB running Raspberry Pi OS 64-bit

Heater
Posts: 17137
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 10:07 am

jahboater wrote:
Thu Oct 15, 2020 9:11 am
To say nested functions are limited and useless because you cant use them to make C behave like Haskell is crazy.
To be fair to myself I did not say nested functions in C were useless, after all I did say "neat way to contain the scope of things and organize code", or that I wanted C to behave like Haskell. Only that nested functions in C are of limited utility.
Heater wrote:
Thu Oct 15, 2020 6:57 am
So limited that C has not accepted them as part of the language.
Have you got a reference for that?
I suspect they are not included for different, more mundane, reasons (like no influential body has seriously proposed them, or perhaps the overheads of allowing access to the parent function's stack didn't fit with C's efficiency expectations, or it was too much change for C's glacially slow evolution, or weak compilers may not be able to support them, or Denis Ritchie didn't include them - and that's good enough).

It's a fair cop. No I don't have a reference to that. Just a reasonable speculation.

Personally I'm very happy with the glacially slow evolution of C. I see no reason to be made more complex than it is. We have plenty of other languages derived from C doing that: D, C++, Zig, Rust, etc.
jahboater wrote:
Thu Oct 15, 2020 9:11 am
Incidentally, you may happily return the address of a nested function from the parent, but if that nested function accesses the stack or the arguments of its parent, and you call the nested function after its parent has returned, then its obviously going to fail badly. Just like returning the address of something on the stack - daft. You could declare the nested function "pure" and it would likely work.
Indeed, as I demonstrated in this thread already: viewtopic.php?f=41&t=287943&start=25#p1741575

Interestingly hippy reports that it does run and produce the correct result on his Pi. And I just found it works on a Jetson Nano as well!

These results suggest to me that it's a good idea not to include nested functions in C. Why add yet another way for people to shoot themselves in the foot?
Memory in C++ is a leaky abstraction .

User avatar
jahboater
Posts: 6522
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 10:19 am

Heater wrote:
Thu Oct 15, 2020 10:07 am
These results suggest to me that it's a good idea not to include nested functions in C. Why add yet another way for people to shoot themselves in the foot?
By exactly the same argument, we should not include local variables in C either .....
In case someone "might" return the address of one of them .... no.

Its such a pathologically rare case that people might want return the address of an impure nested function, let alone use it out of context, that I doubt the compiler even bothers to check.
Heater wrote:
Thu Oct 15, 2020 10:07 am
Personally I'm very happy with the glacially slow evolution of C. I see no reason to be made more complex than it is. We have plenty of other languages derived from C doing that: D, C++, Zig, Rust, etc.
Agreed!
And with more than half the worlds software written in C, the standards people have to be ultra ultra careful when introducing new features.
Last edited by jahboater on Thu Oct 15, 2020 10:30 am, edited 1 time in total.
Pi4 8GB and Pi4 4GB running Raspberry Pi OS 64-bit

Heater
Posts: 17137
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 10:29 am

hippy wrote:
Wed Oct 14, 2020 3:53 pm
Heater wrote:
Tue Oct 13, 2020 7:53 pm
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 $ 
Be careful.

The program as given also compiles and runs producing the correct result on my Jetson Nano.

But add another call to "function()" and it fails:

Code: Select all

$ cat junk.c
#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);
    x = function(42);
    printf("%d\n", x);
    x = function(42);
    printf("%d\n", x);
    x = function(42);
    printf("%d\n", x);
}
Produces:

Code: Select all

$ gcc -Wall -o junk junk.c
$ ./junk
84
Illegal instruction (core dumped)
$
hippy wrote:
Wed Oct 14, 2020 3:53 pm
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 ?
I was using gcc version 8.2.0 on my PC.

Certainly if one uses nested functions one is no longer using the C language.

Also certainly if you use C or GCC's extended C in ways that are not specified to work you are in the land of "undefined behavior" anything can happen.
Memory in C++ is a leaky abstraction .

User avatar
jahboater
Posts: 6522
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 10:48 am

Heater wrote:
Thu Oct 15, 2020 10:29 am
Also certainly if you use C or GCC's extended C in ways that are not specified to work you are in the land of "undefined behavior" anything can happen.
Yes.
I believe that any access to the parents local variables and arguments is done by passing an invisible pointer to the parents stack frame.
After the parent returns, its stack frame is gone and the pointer is obviously invalid.
However, by pure luck, the contents of the old stack frame might still exist untouched, so the reference might work.

Crazy to even attempt this in my book :)

Is this why the captures for lamda functions are so explicit?

When translating C to C++, I just convert any nested functions into named lamda's - works fine.
Pi4 8GB and Pi4 4GB running Raspberry Pi OS 64-bit

Heater
Posts: 17137
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 11:00 am

jahboater wrote:
Thu Oct 15, 2020 10:48 am
I believe that any access to the parents local variables and arguments is done by passing an invisible pointer to the parents stack frame.
I heard rumor that nested functions could be a security risk. Something to do with having the executable code on the stack, which is a no-no.

So I got curious as to how this worked and ended up on this GCC page about "trampolines" https://gcc.gnu.org/onlinedocs/gccint/Trampolines.html

Which does indeed talk of such a security hazard and how GCC closes it.
jahboater wrote:
Thu Oct 15, 2020 10:48 am
Crazy to even attempt this in my book :)
Yeah, well, you know me. Just by way of demonstration mind.
Memory in C++ is a leaky abstraction .

Heater
Posts: 17137
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 11:15 am

jahboater wrote:
Thu Oct 15, 2020 10:48 am
Is this why the captures for lamda functions are so explicit?
I have no idea really.

From my reading around I gather that in C++ a lambda is actually compiled as an object. That object must contain copies of whatever the lambda captures. Hence having to spell out what is captured by the lambda. I guess that object exists on the heap and is callable, by virtue of providing it with an "operator()" method.

As such one could do what a lambda does in C++ manually by creating such an object for oneself. The lambda syntax is just syntactic sugar.

Interestingly Rust does much the same but does not require one to spell out what is captured. It just figures it out from the variable references used inside the lambda.
jahboater wrote:
Thu Oct 15, 2020 10:48 am
When translating C to C++, I just convert any nested functions into named lamda's - works fine.
Cool. A good enough reason to write all new code in C++ instead of C.
Memory in C++ is a leaky abstraction .

lurk101
Posts: 356
Joined: Mon Jan 27, 2020 2:35 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 2:52 pm

ejolson wrote:
Thu Oct 15, 2020 5:26 am
I also added back in the missing void to silence the compiler.
Your PDP-11 won't compile this anymore.

How do you expect fuzzing to work with a number of different cave generators?

ejolson
Posts: 6354
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Thu Oct 15, 2020 4:07 pm

lurk101 wrote:
Thu Oct 15, 2020 2:52 pm
ejolson wrote:
Thu Oct 15, 2020 5:26 am
I also added back in the missing void to silence the compiler.
Your PDP-11 won't compile this anymore.

How do you expect fuzzing to work with a number of different cave generators?
I think you may have started with the ANSI C modifications for your state machine as rline, rnum and others seem to use typed argument lists. I'll try the PDP-11 emulator and check what needs to be changed. Is there a strict K&R compatibility switch in gcc on the Pi that can be used instead?

You are right having different graph generation algorithms will prevent a robot from playing two different codes in lock step. If the graph generating algorithms are different, one could load the maze from a file and reinitialise the random number generator before starting the robot.

On the other hand, if training a deep learning neural network, it would be interesting to see how the resulting AI performs if the graph generator is switched. That would detect whether the neural network, for example, was learning where the Wumpus was from the pattern of rooms or whether it was actually developing strategies.
Last edited by ejolson on Thu Oct 15, 2020 4:39 pm, edited 1 time in total.

User avatar
jahboater
Posts: 6522
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 4:23 pm

Heater wrote:
Thu Oct 15, 2020 11:00 am
I heard rumor that nested functions could be a security risk. Something to do with having the executable code on the stack, which is a no-no.
All the stuff about trampolines is for when someone takes the address of a nested function.
For general usage, its really quite simple:

Code: Select all

int
main( int argc, char *argv[] )
{
  int __attribute__((noinline))
  square( int n )
  {
    return n * n;
  }

  printf( "Square: %d\n", square(argc) );
}
(the attribute stuff is a desperate attempt to stop the optimizer removing the whole thing!)
This emits:

Code: Select all

    .text
    .type   square.0, @function
square.0:
    movl    %edi, %eax  
    imull   %edi, %eax  
    ret
Its created a unique name to make it invisible (the .0 bit) and placed the function in the code (.text) segment as normal.
Now thats a simple "pure" function.
If we access the parent's locals:

Code: Select all

int
main( int argc, char *argv[] )
{
  int __attribute__((noinline))
  square( int n )
  {
    return n * argc;
  }

  printf( "Square: %d\n", square(argc) );
}
we get:

Code: Select all

    .text
    .type   square.0, @function
square.0:
    movl    (%r10), %eax   <========= retrieve argc from the start of main()'s stack frame
    imull   %edi, %eax  
    ret
    .size   square.0, .-square.0
    .section    .rodata.str1.1,"aMS",@progbits,1
.LC0:
    .string "Square: %d\n"
    .globl  main
    .type   main, @function
main:
    subq    $24, %rsp
    leaq    32(%rsp), %rax
    movq    %rsp, %r10   <=========  leave ptr to main()'s stack frame in r10 (simply copy the stack pointer)
    movl    %edi, (%rsp)
    movq    %rax, 8(%rsp)
    call    square.0          <========  call the local function
    movl    $.LC0, %edi
    movl    %eax, %esi
    xorl    %eax, %eax
    call    printf
Its not in the style of C to have hidden pointers.
And worse, argc would normally be in a register (rdi), its had to be placed in the stack so that the local function may access it.
The local function will be using rdi of course, as per the ABI.
Such shenanigans may be why Mr Ritchie didn't include nested functions!

I don't see any obvious risk here.
The risk only comes when people take the address of the nested function.
Its not a reason avoid using them for the normal case.
Last edited by jahboater on Thu Oct 15, 2020 4:57 pm, edited 4 times in total.
Pi4 8GB and Pi4 4GB running Raspberry Pi OS 64-bit

lurk101
Posts: 356
Joined: Mon Jan 27, 2020 2:35 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 4:26 pm

ejolson wrote:
Thu Oct 15, 2020 4:07 pm
You are right having different graph generation algorithms will completely change the game. This prevents a robot from playing two different codes in lock step. If the graph generating algorithms are different, one could load the maze from a file and reinitialise the random number generator before starting the robot.
Prior to fuzzing, compliance testing is required no?

I was thinking of using your graphing output to verify that the generated caves are Euler graphs.

Return to “Other projects”