Mutability and Recursion

help
#1

I'm having trouble with attempting to mutably borrow a variable, but I think there should be a way to do it.

fn var_mut_at(&mut self, level: usize, name: &str) -> Option<&mut Var> {
        // Mutably borrowed here!
        let var = self.stack[level].map.get_mut(name); 
        if let Some(Var::Level(at)) = var {
            // Compiler complains about a second mutable borrow here!
            self.var_mut_at(*at, name)
        } else {
            var
        }
    }

There's a stack of structs; each struct contains a HashMap<String,Var>. Given a stack level and a name, I look up the Var at the level, returning a mutable reference to the Var. Sometimes the Var indicates that the item needs to be looked up further down the stack, so the method calls itself recursively...and therein lies the problem.

I presume there's an idiomatic way to do this?

Mutability in a recursive function
#2

No idea if there is an idiomatic way to do this I'm afraid. I think recursive functions probably tend towards immutable vars for reasons like this :slight_smile:

Does self need to be mutated? If the goal is to return an Option<Var> that suggests (to me) that you don't want to mutate self in the process but I could be wrong!

#3

It's my understanding that if I don't borrow self as mut then I can't return the result as mut, which is precisely what I'm wanting to do.

The Var is a variable in an interpreter. Sometimes I want to get() it so I can use its value, and sometimes I want to get_mut() it so I can set its value. (I have a var_at function that does the same thing, but returns an immutable Var. It works fine.)

If this were just a normal HashMap, I'd just use its get() and get_mut() methods and be happy; but it's a more complicated data structure that I need to search through in order to find the Var I want.

#4

The whole problem about this, is that basing only on its signature, the var_mut_at my do anything with self - it may for example purge whole stack. However rust needs statically prove, that until there is alife var borrow, self cannot change (because var could be invalidated).

Obviously in this case you can trivially see, that if you went into first if branch, whole second branch can be ignored, because its basically deadcode from this point, but Rust typesystem doesn't know it. Polonius is one of way for maybe deal with such cases in future.

#5

I've got several operations that need to acquire an &mut Var and do something with it. Right now each one has a function that takes the name and any other data needed to complete the operation, does the lookup internally, and makes the change. What I'm wanting to do is abstract out the lookup so that I don't need to repeat that logic over and over.

Perhaps there's a way to do it using closures? Something like this:

fn var_mut_at<F>(&mut self, level: usize, name: &str, func: F) 
    where F: FnMut(&mut Var)
{
   let var: &mut Var = .....;
   func(var);
}

I haven't really completely grokked closures yet, so they don't come naturally

#6

I cannot be sure but this seems like a problem to me. And unnecessary as well.

If I understand your top level struct has some kind of stack of structs as a member which it passes to itself, via "self", all the way down the recursive rabbit hole.

Why do that? Why not make use of the processor stack you are using anyway and comes for free. Instead of putting those structs on a stack that you are maintaining yourself just create new ones locally at each recursion level and pass them as parameters. The recursive calls will then create and destroy them as they are made automatically.

I have no idea if that is at all helpful. Just thinking aloud.

Meanwhile I have this horribly recursive calculation with it's associated data structures that I was surprised to find gave no cause for the borrow checker to fight me, maybe there is some inspiration in there somewhere:

const PNUM: usize = 1300;
const FNUM: usize = 10;
const SMAX: i64 = 100_000_000;

struct Primes {
    primes: Vec<i64>,
}

impl Primes {
    fn new() -> Primes {
        let mut primes = Primes {
            primes: vec![0; PNUM],
        };

        let mut p: i64;
        let mut r: i64;
        primes.primes[0] = 2;
        primes.primes[1] = 3;
        let mut pn: i64 = 2;
        let mut in_: i64 = 1;

        fn isprime(p: i64, in_: &mut i64, primes: &[i64]) -> bool {
            for i in 1..*in_ {
                if p % primes[i as usize] == 0 {
                    return false;
                }
            }
            let mut i = *in_;
            while primes[i as usize] * primes[i as usize] <= p {
                if p % primes[i as usize] == 0 {
                    return false;
                }
                i += 1;
            }
            *in_ = i - 1;
            true
        }

        p = 5;
        while pn < PNUM as i64 {
            if isprime(p, &mut in_, &primes.primes) {
                primes.primes[pn as usize] = p;
                pn += 1;
            }
            p += 2;
        }

        if p <= SMAX / p + 1 {
            panic!("The maximum prime {} is too small!", p);
        }

        r = 1;
        for i in 0..(FNUM - 1) {
            if primes.primes[i] > SMAX / r + 1 {
                return primes;
            }
            r *= primes.primes[i];
        }
        panic!("Distinct primes {} in factorisation too few!", FNUM);
    }
}

struct Factors {
    s: i64,
    fmax: i64,
    i: i64,
    p: Vec<i64>,
    n: Vec<i64>,
}

impl Factors {
    fn new(size: usize) -> Factors {
        Factors {
            s: 2,
            fmax: 0,
            i: 0,
            p: vec![0; size],
            n: vec![0; size],
        }
    }
}

struct Tatami {
    isn: i64,
    factors: Factors,
    primes: Primes,
    smin: i64,
    z: Vec<i64>,
}

impl Tatami {
    fn new(primes: Primes) -> Tatami {
        Tatami {
            isn: 0,
            factors: Factors::new(FNUM),
            primes,
            smin: SMAX + 2,
            z: vec![0; FNUM],
        }
    }

    fn sigma(&mut self) -> i64 {
        let mut r = self.factors.n[0];
        for i in 1..=self.factors.fmax {
            r *= self.factors.n[i as usize] + 1;
        }
        r
    }

    fn free(&mut self, k: i64, l: i64) -> bool {
        let n: i64 = l / k;
        let lmin: i64 = (k + 1) * n + 2;
        let lmax: i64 = (k - 1) * (n + 1) - 2;
        (lmin <= l) && (l <= lmax)
    }

    fn t(&mut self) -> i64 {
        let mut r = 0;
        loop {
            let mut found: bool = false;
            for i in 0..=self.factors.fmax {
                if self.z[i as usize] < self.factors.n[i as usize] {
                    self.z[i as usize] += 1;
                    found = true;
                    break;
                }
                self.z[i as usize] = 0;
            }
            if !found {
                break;
            }
            let mut k = 1;
            let mut l = 1;
            for i in 0..=self.factors.fmax {
                k *= self.factors.p[i as usize].pow(self.z[i as usize] as u32);
                l *= self.factors.p[i as usize]
                    .pow(self.factors.n[i as usize] as u32 - self.z[i as usize] as u32);
            }
            if k <= l {
                r += self.free(k, l) as i64;
            }
        }
        r
    }

    fn work(&mut self) {
        let s = self.factors.s;
        let mut r = self.sigma();
        if r >= self.isn {
            r = self.t();
            if (r == self.isn) && (s < self.smin) {
                self.smin = s;
            }
        }
        let mut fmax = self.factors.fmax as usize;
        let pmax = SMAX / s + 1;
        let i = self.factors.i;
        let mut p = self.primes.primes[i as usize];
        if p <= pmax {
            self.factors.n[fmax] += 1;
            self.factors.s = s * p;
            self.work();
            self.factors.n[fmax] -= 1;
        }
        fmax += 1;
        self.factors.n[fmax] = 1;
        for j in i + 1..PNUM as i64 {
            p = self.primes.primes[j as usize];
            if p > pmax {
                break;
            }
            self.factors.p[fmax] = p;
            self.factors.s = s * p;
            self.factors.i = j;
            self.factors.fmax = fmax as i64;
            self.work();
        }
        self.factors.n[fmax] = 0;
    }

    fn inv(&mut self, n: i64) -> i64 {
        self.isn = n;
        self.factors = Factors::new(FNUM);
        self.factors.p[0] = self.primes.primes[0];
        self.factors.n[0] = 1;
        self.factors.i = 0;
        self.factors.s = 2;
        self.factors.fmax = 0;
        self.work();
        if self.smin < SMAX {
            self.smin
        } else {
            -1
        }
    }
}

fn main() {
    let n = 200;
    let primes = Primes::new();
    let mut tatami = Tatami::new(primes);
    println!("T({})={}", tatami.inv(n), n);
}
#7

Did... Did you write that just now? Or did you Blue Peter us? (Here's one I made earlier...)

#8

Alas! I'm implementing a TCL interpreter, and I need this behavior; just relying on the processor stack won't do. The objects in the "stack" are variable scopes, and variable scopes can be interlinked in interesting ways in TCL.

In your case, I think the thing that saves you from the borrow checker is that your data types are Copy.

#9

Looks like using closures might be a way to do it; at least, I have some code that compiles. I'm not at all sure that it's a clear way to do it.....

#10

Ha! I don't recall Valerie Singleton ever saying that :slight_smile:

I cannot claim to have written that at all really. It is a solution to problem #256 on Project Euler
#256 Tatami-Free Rooms - Project Euler It was originally written in C by E.J.Olson from the University of Nevada Reno: http://fractal.math.unr.edu/~ejolson/pi/tatami/src/limited.c

As part of my Rust education and ongoing coding challenges we have I transcribed his code to Rust as an exercise. It outperforms the original C by the way!

#11

Nice!

#12

Not sure what you mean. In my example there is no copying of those arrays that are passed down the recursion chain.

Sounds to me like it might be an idea to move that stack thing out of the top level struct altogether.

#13

You will be please to hear that I now have a string of equivalent codes in C and Rust. All of which perform better in Rust than C on my x86-64 PC.

Sadly they all fare slightly worse than C on ARM. Which is the topic of my thread here:
What's up with the Rust compiler for ARM?

#14

Your code will compile under the next generation borrow checker:

Polonius

Since it is currently experimental, you can only use it with the nightly-only -Zpolonius rust flag. So what I like to do in this situation is the following pattern (beware that doctests only work on lib.rs crates, not on main.rs):

fn var_mut_at (self: &'_ mut Self, level: usize, name: &'_ str)
  -> Option<&'_ mut Var>
{
    let var: Option<&mut Var> =
        self.stack[level]
            .map
            .get_mut(name)
    ;
    #[cfg(not(feature = "polonius"))]
    let var: Option<&mut Var> = unsafe {
        ::core::mem::transmute(var)
    };
    doc_test! {
        assert!(
            ::std::process::Command::new("cargo")
                .arg("+nightly")
                .arg("rustc")
                .arg("--features").arg("polonius")
                .arg("--")
                .arg("-Zpolonius")
                .status()
                .expect("Failed to run command")
                .sucess()
        );
    }
    if let Some(&mut Var::Level(at)) = var {
        self.var_mut_at(at, name)
    } else {
        var
    }
}

  • Playground

  • If you test it on your machine (with

    [features]
polonius = []

    on your Cargo.toml), you will see that cargo test --doc passes, meaning that cargo +nightly rustc --features polonius -- -Z polonius succeeds.

1 Like
#15

That's good to know! A question about ::core::mem::transmute: the docs say it copies the bits. Since in this case it's copying var back to var, does it really copy the bits, or does the compiler just re-interpret them?

#16

The situation is a lot more complicated than it looks. Each level of the stack represents a TCL stack level containing the definitions of the variables at that level of the stack. But a TCL procedure can introspect and add variables to any level of the stack. It's incredibly dynamic.

It's always reasonable to say, "Yes, you have this problem now—but if you changed your data structures/algorithms you wouldn't." In this case, though, I don't see how to get around it.

#17

In practice (especially when in --release), such type-level shenanigans are expected to be optimized out and be indeed zero cost.

1 Like
#18

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.