A Birthday Present for Fido

[ejolson]

In Hunt the Wumpus it would have been natural to use multiple entry to play a sequence of games without changing the maze. While it wasn't too difficult to code this functionality by passing a flag back and forth, it's not clear how that improved code readability. Maybe that's the point behind the goto madness in the Wumpus code Ken wrote for Unix.

With nothing to do on a rainy Covid Monday and as an exercise in futility I tackled this very problem. The code can be de-spaghettied easily using a state machine. Arbitrary code segment reentry is done without resorting to GOTOs. No need for exotic features.

Sounds great. Do you have an example you could post?

[lurk101]

Before embarking upon a study of the legacy programming environments on purpose-built educational computing devices...

I doubt the intent was education. They accidentally became educational tools but purpose-built? I don't think so.

[ejolson]

Before embarking upon a study of the legacy programming environments on purpose-built educational computing devices...

I doubt the intent was education. They accidentally became educational tools but purpose-built? I don't think so.

Both the SuperPET and the Raspberry Pi were built to teach programming. The fact that the Pi turned out to be useful for other things, according to legend, was a surprise to the original designers. What I find more surprising is that the SuperPET didn't enjoy the same kind of popularity. Maybe price was a factor, as Commodore didn't market it as the MicroMainframe 9000 for only US$ 35.

It's also possible that the above code for Hunt the Wumpus is the only game ever written in microPascal for the SuperPET.

[lurk101]

In Hunt the Wumpus it would have been natural to use multiple entry to play a sequence of games without changing the maze. While it wasn't too difficult to code this functionality by passing a flag back and forth, it's not clear how that improved code readability. Maybe that's the point behind the goto madness in the Wumpus code Ken wrote for Unix.

With nothing to do on a rainy Covid Monday and as an exercise in futility I tackled this very problem. The code can be de-spaghettied easily using a state machine. Arbitrary code segment reentry is done without resorting to GOTOs. No need for exotic features.

Sounds great. Do you have an example you could post?

Unfinished... I think. But you get the idea.

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 <time.h>
#include <stdlib.h>
#include <stdbool.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;

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"
  "\n"
};

static unsigned int randx;

#define BAT  01
#define PIT  02
#define WUMP 04

int arrow, loc, wloc, tchar;

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)
{
    int c = 20, n, j;

    while (1)
    {
        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;

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

int
rin(void)
{
    int n, c;

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

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

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

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

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) ");
    if (rline() == 'y')
        return SETUP;
    return 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]();
}

[Heater]

I'm not sure I understand how a generator works.

In Rust a generator is not just any old function lying around in global space. It is an anonymous function, a lambda. As such it is a value that must be assigned to a variable.

By virtue of containing a "yield" keyword the lambda gets compiled into an object containing state machine with a "resume" method to advance the state. The state is any variables captured by the lambda.

The state machine returns an enumeration which can be "Complete" or "Yielded" both of which can carry actual output values.

Code: Select all

#![feature(generators, generator_trait)]
use std::ops::Generator;
use std::pin::Pin;

fn main() {
    let mut n:i64 = 42;

    // Generators are lambdas, the "move" here captures the variable n.
    // The generator is compiled into a state machine.
    let mut generator = move || {
        loop {
            if n == 1 {
                // return from a generator will return the "Yielded" type with a value.
                return 1;
            } else if n % 2 == 0 {
                n = n /2;
            } else {
                n = n * 3 + 1;
            }
            // yield from a generator will return the "Complete" type with a value.
            yield n;
        }
    };

    loop {
        // Calling resume on a generator advances is's state machine
        // Calling resume on a generator that has completed will cause a panic.
        let x = Pin::new(&mut generator).resume(());
        println!("x = {:?}", x);
    }
}

Produces:

Code: Select all

$ ./generator
x = Yielded(21)
x = Yielded(64)
x = Yielded(32)
x = Yielded(16)
x = Yielded(8)
x = Yielded(4)
x = Yielded(2)
x = Yielded(1)
x = Complete(1)
thread 'main' panicked at 'generator resumed after completion', generator.rs:11:25
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Is it reentrant? Is it thread safe? What happens if the same generator is simultaneously called from two different threads? What happens if it is called again from a signal handler after having been interrupted before returning one of the generated sequence of return values?

By virtue of being a value stored in a variable a Rust generator is subject to all the data anti-aliasing rules as any other object. So it cannot be shared around threads unless it is wrapped in a mutex.

Signals are a whole can of worms that I don't think Rust caters for at the moment. Apparently it did a few years back but they yanked it out as it was not very good. Can be done with some "unsafe" code, plenty of crates provide for that.

[Heater]

[*] Pascal's nested function definitions seem to be called closures by other students and the pseudo-intellectual elite.

A closure and a nested function are very different things.

A closure/lambda captures variables outside of itself but within it's scope. A function does not. Consider:

Code: Select all

fn make_function (n: i64) -> fn (i64) -> i64 {
    fn nested_function (m: i64) -> i64  {
        n + m                                                           // Error!
    }
    nested_function
}

fn make_lambda (n: i64) -> Box<dyn Fn(i64) -> i64> {
    let lambda_function = move |m| {
        n + m
    };
    Box::new(lambda_function)
}

fnmain() { 
    let function = make_function(5);
    let x = function(7);
    println!("x = {:?}", x);

    let function = make_lambda(5);
    let x = function(7);
    println!("x = {:?}", x);
}

Fails to compile with "can't capture dynamic environment in a fn item" because nested_function cannot capture the "n".
No such problem for the lambda/closure.

Did Pascal capture variables like that? As I recall Pascal did not allow functions to return their nested functions to callers. No such problem with lambdas/closures.

[jahboater]

A closure/lambda captures variables outside of itself but within it's scope. A function does not. Consider:

I thought the normal scope rules apply for nested functions, at least they do in C. Maybe its different in Rust.

[Heater]

A closure/lambda captures variables outside of itself but within it's scope. A function does not. Consider:

I thought the normal scope rules apply for nested functions, at least they do in C. Maybe its different in Rust.

There are no nested functions in C.

[ejolson]

[*] Pascal's nested function definitions seem to be called closures by other students and the pseudo-intellectual elite.

A closure and a nested function are very different things.

A closure/lambda captures variables outside of itself but within it's scope. A function does not. Consider:

Code: Select all

fn make_function (n: i64) -> fn (i64) -> i64 {
    fn nested_function (m: i64) -> i64  {
        n + m                                                           // Error!
    }
    nested_function
}

fn make_lambda (n: i64) -> Box<dyn Fn(i64) -> i64> {
    let lambda_function = move |m| {
        n + m
    };
    Box::new(lambda_function)
}

fnmain() { 
    let function = make_function(5);
    let x = function(7);
    println!("x = {:?}", x);

    let function = make_lambda(5);
    let x = function(7);
    println!("x = {:?}", x);
}

Fails to compile with "can't capture dynamic environment in a fn item" because nested_function cannot capture the "n".
No such problem for the lambda/closure.

Did Pascal capture variables like that? As I recall Pascal did not allow functions to return their nested functions to callers. No such problem with lambdas/closures.

My understanding is historical versions of Pascal don't allow passing references to functions around, so creating an add by m function generator function isn't possible for many reasons. It seems Delphi--an enhanced form of Pascal--does support closures with a syntax very similar to nested functions.

http://interactiveasp.net/blogs/spgilmo ... -2010.aspx

I haven't programmed in Delphi ever, but closures turned out sightly useful when making functions with rescaled domains for a numerical quadrature routine in Julia. I wonder what they could be used for in the context of Hunt the Wumpus.

Could a closure be used to create a function that creates procedures with different AIs that Hunt for Wumpi?

Is there a way to use closures to avoid mutable variables while generating a random 3-valence graph on 20 vertices?

[jahboater]

A closure/lambda captures variables outside of itself but within it's scope. A function does not. Consider:

I thought the normal scope rules apply for nested functions, at least they do in C. Maybe its different in Rust.

There are no nested functions in C.

I use them all the time in C.
That's missing the point of course.
Also Python, Pascal, Algol 68, etc seem to follow the normal block scope rules - simple and easy to remember (but slightly harder to implement if the nested function does actually refer to something further up the stack).

[hippy]

There are no nested functions in C.

Supposedly not, but they do seem to exist and work ...

Code: Select all

pi@Pi3B:~/apps/zpu $ cat main.c
#include <stdio.h>

void main()
{
    void NestedSubroutine()
    {
        void DeeperNestedSubroutine()
        {
             printf("Yay! Nested subroutines work!\n");
        }
        DeeperNestedSubroutine();
    }
    NestedSubroutine();
}

Code: Select all

pi@Pi3B:~/apps/zpu $ gcc -o main main.c
pi@Pi3B:~/apps/zpu $ ./main
Yay! Nested subroutines work!
pi@Pi3B:~/apps/zpu $

[Heater]

That is a GCC extension. Not C.

[jahboater]

That is a GCC extension. Not C.

GCC is ubiquitous ...
and other tier 1 compilers copy GCC.
Anyway here is a Python example I found showing the inner function using an outer functions argument.

Code: Select all

def outer(num1):
    def inner_increment(num1):  # Hidden from outer code
        return num1 + 1
    num2 = inner_increment(num1)
    print(num1, num2)

[ejolson]

With nothing to do on a rainy Covid Monday and as an exercise in futility I tackled this very problem. The code can be de-spaghettied easily using a state machine. Arbitrary code segment reentry is done without resorting to GOTOs. No need for exotic features.

Sounds great. Do you have an example you could post?

Unfinished... I think. But you get the idea.

Interesting. I hadn't thought to structure the code in that way. Are you missing a return before LEAVE in rin and rline?

[Heater]

That is a GCC extension. Not C.

GCC is ubiquitous ...
and other tier 1 compilers copy GCC.

Clang does not support nested functions in C.

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

Meanwhile it seems clang has "Blocks" which can be used to create lambdas and return them from functions, much more useful: https://en.wikipedia.org/wiki/Blocks_(C ... extension)

Unfortunately my clang does not have a "Blocks.h"

[Heater]

Out of curiosity I thought I'd see how our "function maker_function" would look in the new fangled C++11.

Code: Select all

#include <functional>

auto make_lambda (int m) {
    auto lambda_function = [m](int n) {
        return (m + n);
    };
    return lambda_function;
}

int main () {
    auto function = make_lambda(5);
    int x = function(7);
    printf("%d\n", x);
}

Not bad at all.

[Heater]

I use them all the time in C.

I'm curious to know what you use them for. They seem very limited seeing as one cannot return them from where they were created. I have never seen anyone using nested functions in C.

Also Python, Pascal, Algol 68, etc seem to follow the normal block scope rules - simple and easy to remember (but slightly harder to implement if the nested function does actually refer to something further up the stack).

Algol68 has first class functions but can one return a nested function to a caller in Pascal?

[jalih]

[*] Pascal's nested function definitions seem to be called closures by other students and the pseudo-intellectual elite.

A closure and a nested function are very different things.

A closure/lambda captures variables outside of itself but within it's scope. A function does not.

Sounds like a broken nested function implementation! Not so with PL/I... Multiple entry points for procedures are also supported by using entry statement (is entry a reserved word also on C compilers but not used?).

[Heater]

Sounds like a broken nested function implementation!

I was thinking about this...

The decision in C is that there are no nested functions. Likely because it's an extra complexity that is not very useful. Especially as one cannot return function from function, which would be even more complex.

GCC has a nested function extension. Nested functions can access anything in their scope, as we might expect. But that means they cannot be returned or stored in structs or passed around because that is UB and will likely segfault. See above.

C++ is the same. But to provide properly useful nested functions they implemented lambdas. Now we have first class functions.

Meanwhile in Rust there is nested functions. You can return functions from functions, you can store them in structs and pass them around. They are "First class functions". But, in order to do that functions are limited to not being able to use anything outside their definition. As we would expect of mathematical functions. They have also provided lambdas that can capture from their surrounding scope. Best of both worlds!

Not so with PL/I... Multiple entry points for procedures are also supported by using entry statement (is entry a reserved word also on C compilers but not used?).

I have never looked at PL/1. Rumor I have heard is that it includes every possible language feature in some gigantic mess.

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

[jahboater]

Clang does not support nested functions in C.

I said tier 1 compilers.

[jahboater]

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.

I'm curious to know what you use them for.

They 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.
Another handy feature is that they have efficient access to the outer functions local variables and arguments.
This may reduce the number arguments being passed around or reduce the need for global's.
Generally the code gets smaller, simpler and safer.

[Heater]

Clang does not support nested functions in C.

I said tier 1 compilers.

Huh?

Are there any compilers other than GCC on your tier 1 compiler list?

Clang is top notch and used by all of Apple and all of Google. What tier does that put it on?

[jahboater]

I meant compilers like ICC.
Clang copies nearly all of the GCC extensions except nested functions.
Surprisingly clang supports the complex extended inline assembler stuff from GCC.
I don't know why they don't support nested functions, but its enough reason for me not to use it.
(and the messy install).

[lurk101]

Sounds great. Do you have an example you could post?

Unfinished... I think. But you get the idea.

Interesting. I hadn't thought to structure the code in that way. Are you missing a return before LEAVE in rin and rline?

rline is not a state function. It would not be appropriate to return LEAVE there. Unfinished. I also notice that I am often given the coice of 3 identical passages. Needs work.

BTW, return is not a function! It irks when you see something like this: return(0). Legal, but denotes a lack of understanding and is surprising from Ken Thompson.

[jahboater]

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.
I have vague memories from B that return() was the same. Maybe a first cut of C did too, I don't know.