A C++ Trick Question Post

2 pointsposted 5 hours ago
by birdculture

1 Comments

_rend

5 hours ago

Spoiler:

Yeah, this is an unfortunate problem in most non-GC languages with implicit destructors. See, e.g., Swift

    enum Node {
        case none
        indirect case next(Node)
    }
    
    func example(_ n: Int) {
        var head = Node.none
        for _ in 0 ..< n {
            head = .next(head)
        }
    }
    
    example(100000)
    // Terminated due to signal: SEGMENTATION FAULT (11)
or Rust

    struct Node {
        next: Option<Box<Node>>
    }
    
    impl Node {
        fn new(next: Node) -> Self {
            Node { next: Some(Box::new(next)) }
        }
    }
    
    fn example(n: isize) {
        let mut head = Node { next: None };
        for _ in 0 .. n {
            head = Node::new(head);
        }
    }
    
    fn main() {
        example(100000)
        // thread 'main' (24909708) has overflowed its stack
        // fatal runtime error: stack overflow, aborting
        // Terminated due to signal: ABORT TRAP (6)
    }
I'm not aware of languages (esp. systems languages) that can either guarantee some form of tail-call optimization for destructors, or that make an attempt to recognize recursive data structures and accommodate them in some way. (The latter is likely a losing proposition, anyway.)