From Newsgroup: comp.programming

[Crossposted and and Followup-To: comp.programming]

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >[email protected] (Dan Cross) writes:

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

Tim Rentsch <[email protected]> writes:

That's good to know but what is a good resource to learn the Rust >>>>language? I've looked at the Rust book several times and each
time come away rather frustrated.

If you mean "The Rust Programming Language", I came away from it >>>disillusioned.

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

I think what you mean to say is that you couldn't find a way to
implement that in the manner you were accustomed to thinking
about the problem, given your prior experience.

My goal was to implement search tree insertion as efficiently and
compactly as in Pascal, C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

An intersting way to write it; I understand you're trying to
reuse `search` in `insert`, below, and thus why you want to
return `rootp`.

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);

I know you said this was untested; clearly you should not
indirect the result of `search` here.

struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these
languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

I also knew Java solutions to the problem:

1) Special-case the root (which you typically have to do in Java
anyway, and otherwise always keep a pointer to the last tree node
around, and also keep the knowledge about the last left-or-right
decision around (or take it again). This all leads to quite a bit of
code that is duplicated relative to the code above.

2) Recurse into the tree and rewrite all the links to the subtrees
along the spine of the search. This is not quite as duplicative as 1)
(but the root still has to be handled separately), but it performs
several writes instead of just one, and the recursion is not a tail >recursion, so is relatively expensive.

Or, 3) Simply reimplement the comparison in `insert`; it's a
trivial amount of code.

I chose a variant of (1) for my implementation, but only because
it was easy, not because it was required. No unsafe code or
fancy reference counting here.

BEGIN `tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree { root: None }
}

/// Searches the tree for the given key, and returns
/// `Some(&value)` if it's here, otherwise returns None.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// tree.insert(2, 200);
/// tree.insert(1, 100);
/// assert_eq!(tree.search(&0), None);
/// assert_eq!(tree.search(&1), Some(&100));
/// assert_eq!(tree.search(&2), Some(&200));
/// ```
pub fn search(&self, key: &K) -> Option<&V> {
let mut root = &self.root;
while let Some(node) = root {
match key.cmp(&node.key) {
Ordering::Less => root = &node.left,
Ordering::Equal => return Some(&node.value),
Ordering::Greater => root = &node.right,
}
}
None
}

/// Inserts the given `value` into the tree with the given
/// `key`. Returns true if the node was inserted, or false
/// if the key was already in the tree.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// assert_eq!(tree.insert(1, 100), true);
/// assert_eq!(tree.insert(1, 200), false);
/// assert_eq!(tree.insert(2, 100), true);
/// ```
pub fn insert(&mut self, key: K, value: V) -> bool {
let mut root = &mut self.root;
loop {
let Some(node) = root else {
root.replace(Node::new(key, value));
return true;
};
match key.cmp(&node.key) {
Ordering::Less => root = &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => root = &mut node.right,
}
}
}

/// Print the tree, if it is not empty.
pub fn print(&self) {
if let Some(node) = &self.root {
node.print();
}
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: Option<Box<Node<K, V>>>,
right: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: None,
right: None,
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
if let Some(left) = &self.left {
left.print();
}
println!("key = {:?}, value = {:?}", self.key, self.value);
if let Some(right) = &self.right {
right.print();
}
}
}

END `tree.rs`<---

Note that there's more code here than in your C code, but this
also does a lot more; this is generic over any key and value
types where the key type implements a total ordering, and where
both types implement the `Debug` trait (so they can be printed).

Just to be fancy I added some comments, and note that the
examples in thosee comments are actually unit tests that are run
with `cargo test`.

There is also a pre-order `print` routine. With a trivial
driver program, this prints:

term% cat src/main.rs
use tree::Tree;

pub fn main() {
let mut tree = Tree::<i32, i32>::new();
tree.insert(2, 200);
tree.insert(1, 100);
tree.insert(3, 300);
tree.print();
println!("tree.search(0) = {:?}", tree.search(&0));
println!("tree.search(1) = {:?}", tree.search(&1));
}
term% cargo run
Compiling tree v0.1.0 (/Users/cross/xfer/tree)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.12s
Running `target/debug/tree`
key = 1, value = 100
key = 2, value = 200
key = 3, value = 300
tree.search(0) = None
tree.search(1) = Some(100)
term%

I wanted something with the benefits of the Pascal/C/Forth variant,
not something like the Java variants. I don't know if that counts as
"manner you were accustomed to thinking about the problem".

I would say that it does. You wanted to do something that is
familiar from Pascal or Modula-2, but that is annoying to
express in Rust. However, that doesn't mean that there is not a
similar way to effect the same thing in Rust.

And I learned this technique in Pascal or Modula-2 (probably from one
of Wirth's books), and had no problem transferring the knowledge into
C or Forth, on the contrary: In C and Forth I could turn search into a
loop (in Pascal it has to be a tail-recursive function, because you
can only produce references to variables and fields through reference >parameters).

For a language that aspires to take over from C for systems
programming, I expect that one can use this technique, too.

See above. The core of the `search` and `insert` algorithms are
similar to the ones you sketched, though the pointer-to-pointer
to a node is not returned by `search`. If that is what you mean
by "technique" then you're right; doing that in Rust is
inconvenient because it violates the borrow checker's rules
about the existence of multiple simultaneous mutable references
to an object. But I claim that is just a detail, and not a
terribly interesting one at that; certainly not an impediment to
substituting Rust for C in systems programming.

Even so, as I said, one _can_ use the same technique using a
smallish-bit of `unsafe` code. This version is more faithful to
your original:

BEGIN `unsafe_tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: *mut Node<K, V>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree {
root: std::ptr::null_mut(),
}
}

fn search(&mut self, key: &K) -> &mut *mut Node<K, V> {
let mut nodep = &mut self.root;
while let Some(node) = unsafe { nodep.as_mut() } {
match key.cmp(&node.key) {
Ordering::Less => nodep = &mut node.left,
Ordering::Equal => break,
Ordering::Greater => nodep = &mut node.right,
}
}
nodep
}

pub fn insert(&mut self, key: K, value: V) {
let inodep = self.search(&key);
if let Some(node) = unsafe { inodep.as_mut() } {
node.value = value;
} else {
let node = Node::new(key, value);
*inodep = std::boxed::Box::leak(node);
}
}

pub fn print(&self) {
unsafe { self.root.as_ref() }.map(|root| root.print());
}
}

impl<K: Debug + Ord, V: Debug> Drop for Tree<K, V> {
fn drop(&mut self) {
let _root = unsafe { std::boxed::Box::from_raw(self.root) };
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: *mut Node<K, V>,
right: *mut Node<K, V>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: std::ptr::null_mut(),
right: std::ptr::null_mut(),
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
unsafe { self.left.as_ref() }.map(|left| left.print());
println!("key = {:?}, value = {:?}", self.key, self.value);
unsafe { self.right.as_ref() }.map(|right| right.print());
}
}

impl<K: Debug + Ord, V: Debug> Drop for Node<K, V> {
fn drop(&mut self) {
if !self.left.is_null() {
let _left = unsafe { std::boxed::Box::from_raw(self.left) };
}
if !self.right.is_null() {
let _right = unsafe { std::boxed::Box::from_raw(self.right) };
}
}
}

#[cfg(test)]
mod tests {
use super::*;
#[test]
fn raw_insert_works() {
let mut tree = Tree::new();
tree.insert(1, 100);
tree.insert(3, 300);
tree.insert(2, 200);
drop(tree);
}
}

END `unsafe_tree.rs`<---

I stripped comments for brevity, but added explicit `Drop` impls
to avoid leaking memory. The seemingly useless test here allows
me to exercise this under `miri` to check for memory safety
violations manipulating raw pointers with `unsafe`:

term% cargo +nightly miri test
Finished `test` profile [unoptimized + debuginfo] target(s) in 0.00s
Running unittests src/lib.rs (target/miri/aarch64-apple-darwin/debug/build/tree/6797a5ad52527de9/out/tree-6797a5ad52527de9)

running 1 test
test otree::tests::raw_insert_works ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.16s

Running unittests src/main.rs (target/miri/aarch64-apple-darwin/debug/build/tree/6121d361cfb78277/out/tree-6121d361cfb78277)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.03s

Doc-tests tree

running 2 tests
test src/lib.rs - Tree<K,V>::insert (line 51) ... ok
test src/lib.rs - Tree<K,V>::search (line 25) ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.11s

all doctests ran in 0.14s; merged doctests compilation took 0.03s
term%

So, we can see that it is possible to use the same technique you
are familiar with.

The difference is that, with Rust, you usually don't _want_ to
do it this way, since there's a completely safe alternative that
leverages the type system to prohibit memory leaks, dangling
pointers, and so on, by construction.

Frankly, unless I was doing something very odd, I wouldn't write
my own binary search tree at all; the standard library's
collections implementations are pretty good, and then there are
third-party libraries like Hashbrown and Crossbeam that are
best-in-class across the industry.

But that is separate from whether it can be done or not.

Sure, and as I found out later, it can be done.

Indeed; see above.

In fact, in Rust you can use approximately the same
techniques you would use in Pascal, C, or (probably) Forth: raw
pointers are a part of the language, and you can simply use them
with `unsafe` code, and it would be no more "unsafe" than in C
or Pascal. One might argue that that defeats the purpose of the
language, and you'd be right to a point. The difference is that
in C or Pascal, the entire program is what Rust would call
"unsafe", whereas generally this can be restricted to just a few
lines of carefully audited code in Rust.

Given that I do not understand the automagic stuff done by the Rust
compiler enough to get this kind of tree insertion past the borrow
checker, even though it is possible, I don't trust my capabilities to
audit unsafe Rust.

Is it significantly different than doing so in C, Pascal, or
Forth? See the second program, above; the use of `unsafe` in
the bits that correspond to your sketch in C is constrained to
two places that indirect raw pointers.

It is true that I think it is more difficult to write _correct_
`unsafe` code in Rust than in, say, C, because the language is
more demanding of the programmer. But in return for that
investment in effort, you get substantally more type and memory
safety.

FWIW, for things like containers of various kinds (trees, hash
tables, linked-lists, growable arrays, etc), production programs
usually use an existing library or crate instead of rolling
their own.

When I saw that this technique cannot be implemented in Java, I
wondered why Java was not having references to fields (answer:
probably because that would make garbage collection more costly and/or
less precise), that this technique is needed for relatively few
things, mostly stuff that's in libraries. And I wondered how these
library methos are implemented (at one point I guessed that they
implemented these parts of their libraries in C, but when I actually
look, the implementation of what I looked at was in Java, IIRC along
the lines of 1)).

For a language that aspires to replace C for systems programming,
giving the Java answer is not good enough, though.

Fortunately for Rust, that's not what it does.

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker.

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference >>>counting after all. However, the problem in this case is the usual
thing with type inference: There is so much going on that happens >>>automagically (in particular automatic dereferencing in Rust), and the >>>Rust compiler does not know where you went wrong, so the error message
is unhelpful (while for the simpler cases the compiler usually guesses >>>right and gives very helpful, to-the-point error messages).

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

Sounds like you're in what we'd call the, "fighting the borrow
checker" stage. It may be that you end up really not liking
Rust or feeling that other languages are better, but I wager
that just about anyone who has seriously used the language has
gone through similar things.

I wonder about that.

It's so common that "fighting the borrow checker" is the
community's slogan to describe it. Another common phenomenon
for those who put in the work and come out the other side of
that is that one finds the discipline it imposes on how one
thinks of one's programs makes one a better programmers in
unsafe languages, like C.

From the books I read, I get the impression that
Rust used to have less automagic stuff, and much of the automagic was
added later, as a convenience for the programmers who already knew the >language. So the Rust programmers of the early days formed a mental
model based on "Pedestrian Rust" (i.e., with less automagic), and when
they see a program with more automagic, and need to understand some >conveniently short piece of Rust code in detail, they form a mental
model of the code in Pedestrian Rust. But how can a Rust programmer
who starts now learn Pedestrian Rust and how it relates to the modern >language. There are hints in the books I read, but not enough to get
a firm foundation.

Early Rust was very different, and much closer to a managed
language with garbage collection, green threads, a heavy-weight
runtime, etc. Put another way, the trend has been less and less
"automagic" (as you put it) and making things more explicit over
time.

You keep conflating things you are not familiar with in a
language you are not familiar with, with the idea that those
things are "automagic." But really there is no magic here, and
I suspect the answer to your question about how one learns to
adapt their mental model of Rust is to first stop thinking of it
as magical.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

[email protected] (Dan Cross) writes:

[Crossposted and and Followup-To: comp.programming]

Given that I don't subscribe to c.p, I kept comp.arch in the
Newsgroups.

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

My goal was to implement search tree insertion as efficiently and
compactly as in Pascal, C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

An intersting way to write it; I understand you're trying to
reuse `search` in `insert`, below, and thus why you want to
return `rootp`.

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);

I know you said this was untested; clearly you should not
indirect the result of `search` here.

struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these
languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

I also knew Java solutions to the problem:

1) Special-case the root (which you typically have to do in Java
anyway, and otherwise always keep a pointer to the last tree node
around, and also keep the knowledge about the last left-or-right
decision around (or take it again). This all leads to quite a bit of
code that is duplicated relative to the code above.

2) Recurse into the tree and rewrite all the links to the subtrees
along the spine of the search. This is not quite as duplicative as 1)
(but the root still has to be handled separately), but it performs
several writes instead of just one, and the recursion is not a tail >>recursion, so is relatively expensive.

Or, 3) Simply reimplement the comparison in `insert`

That goes along with 1), but I forgot to mention it.

it's a trivial amount of code.

There's the rub. I don't consider a factor of ~2 trivial, even if it
is only 20 lines of code. And in particular, "simply reimplement"
means that the same thing occurs several times in the code, and in
maintainance one must remember to change all of the occurences.

Fortunately, that's not necessary in Rust. But the fact that you did
not find it tells me that Rust is hard even for experienced Rust
programmers.

I chose a variant of (1) for my implementation, but only because
it was easy, not because it was required. No unsafe code or
fancy reference counting here.

BEGIN `tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree { root: None }
}

/// Searches the tree for the given key, and returns
/// `Some(&value)` if it's here, otherwise returns None.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// tree.insert(2, 200);
/// tree.insert(1, 100);
/// assert_eq!(tree.search(&0), None);
/// assert_eq!(tree.search(&1), Some(&100));
/// assert_eq!(tree.search(&2), Some(&200));
/// ```
pub fn search(&self, key: &K) -> Option<&V> {
let mut root = &self.root;
while let Some(node) = root {
match key.cmp(&node.key) {
Ordering::Less => root = &node.left,
Ordering::Equal => return Some(&node.value),
Ordering::Greater => root = &node.right,
}
}
None
}

/// Inserts the given `value` into the tree with the given
/// `key`. Returns true if the node was inserted, or false
/// if the key was already in the tree.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// assert_eq!(tree.insert(1, 100), true);
/// assert_eq!(tree.insert(1, 200), false);
/// assert_eq!(tree.insert(2, 100), true);
/// ```
pub fn insert(&mut self, key: K, value: V) -> bool {
let mut root = &mut self.root;
loop {
let Some(node) = root else {
root.replace(Node::new(key, value));
return true;
};
match key.cmp(&node.key) {
Ordering::Less => root = &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => root = &mut node.right,
}
}
}

/// Print the tree, if it is not empty.
pub fn print(&self) {
if let Some(node) = &self.root {
node.print();
}
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: Option<Box<Node<K, V>>>,
right: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: None,
right: None,
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
if let Some(left) = &self.left {
left.print();
}
println!("key = {:?}, value = {:?}", self.key, self.value);
if let Some(right) = &self.right {
right.print();
}
}
}

END `tree.rs`<---

Note that there's more code here than in your C code, but this
also does a lot more; this is generic over any key and value
types where the key type implements a total ordering, and where
both types implement the `Debug` trait (so they can be printed).

If I don't need any of that, does it get smaller? I don't think so.

Here's my attempt, and I expect that experienced Rust programmers will
find ways to improve on it. It includes a lookup function:

-------------------
use std::cmp::Ordering;

pub struct Tree<K: Ord, V> {
root: Subtree<K, V>,
}

type Subtree<K,V> = Option<Box<Node<K,V>>>;

struct Node<K: Ord, V> {
key: K,
val: V,
left: Subtree<K, V>,
right: Subtree<K, V>,
}

impl<K: Ord,V> Tree<K,V> {
pub fn new() -> Self {
Tree { root: None }
}

pub fn insert(&mut self, key: K, val: V) {
let mut t = &mut self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => {node.val = val; return;},
Ordering::Less => t = &mut node.left,
Ordering::Greater => t = &mut node.right,
};
};
*t = Some(Box::new(Node {key, val, left: None, right: None}))
}

pub fn lookup(&self, key: K) -> Option<&V> {
let mut t = &self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => return Some(&node.val),
Ordering::Less => t = &node.left,
Ordering::Greater => t = &node.right,
};
};
None
}
}

fn main() {
let mut q1 = Tree::new();
q1.insert(2,"abc".to_string());
q1.insert(3,"def".to_string());
q1.insert(1,"ghi".to_string());
q1.insert(3,"jkl".to_string());
println!("{:?}",q1.lookup(1));
println!("{:?}",q1.lookup(2));
println!("{:?}",q1.lookup(3));
}
----------------------------

Like your code and Java code, this has a separate type Tree with a
field root and with its own new function, while in C a "struct tree *"
variable can serve as root pointer; and this leads to an additional
line each in insert and lookup. Can we do without most of that
(havibf a constructor is useful) and just use Subtree instead of Tree?

insert now integrates search, because I could not satisfy the compiler
with a separate search; maybe a more experience Rust programmer can
separate it out again. The advantage is that there is no need to
combine the found and notfound cases in one return value in search,
only to handle them as separate cases in insert. But at least there
is no duplication of the comparison code.

The integration of search in insert led to a duplication of most of
the search code in lookup. However, requiring a mutable reference is
not necessary for the lookup code, so a search that takes a mutable
reference and returns a mutable reference is too restrictive for
lookup. But maybe a more experienced Rust programmer can write a
generic search that takes an &mut tree for insert, and a & for lookup.

Of course, if search is factored out, both clients have to explicitly
check for both outcomes and have code for both. But that's probably
preferable to duplicating the search.

though the pointer-to-pointer
to a node is not returned by `search`. If that is what you mean
by "technique" then you're right; doing that in Rust is
inconvenient because it violates the borrow checker's rules
about the existence of multiple simultaneous mutable references
to an object.

Yes, that's what I meant by "technique". And it's possible in safe
Rust, but I had a very hard time finding it (and for a while thought
that it is not possible). The fact that you thought it is not
possible in safe Rust means that it is not just my inexperience at
fault here.

But I claim that is just a detail, and not a
terribly interesting one at that; certainly not an impediment to
substituting Rust for C in systems programming.

I think that, in order to be the rightful heir, safe Rust should be
able to do everything one can do in the other language that's not
inherently unsafe, and do it without needing to duplicate code of
other nastyness. You may wonder about "inherently unsafe": I have no definition for that yet, but I would not kno why inserting a node into
a search tree would ever fall into that category,

Even so, as I said, one _can_ use the same technique using a
smallish-bit of `unsafe` code.

That's cool, but given that I have difficulty understanding why the
compiler complained about my version with separate search, I feel very uncomfortable in asserting to the compiler that my use of unsafe
features is safe once we leave the unsafe block.

Frankly, unless I was doing something very odd, I wouldn't write
my own binary search tree at all; the standard library's
collections implementations are pretty good

And I actually don't use binary search trees anyway, neither
self-written nor from libraries, because hash tables tend to be the
better alternative, except when I want to know the next-higher element
or somesuch. But being able to have a reference to a field is also
useful when implementing hash tables.

But anyway, the libraries have to be written in some language, and
given that Rust fans tell us to rewrite all C code in Rust, I would
expect that the library should be written in Rust, and, in particular
in safe Rust (otherwise, why rewrite it in Rust?).

And actually, we teach our students how to write this stuff (even in
Java), because we think it teaches them something useful. And at
least one Rust fan thinks so, too, and wrote "Learn Rust With Entirely
Too Many Linked Lists", where I found out how to implement the
mentioned technique in safe Rust.

Given that I do not understand the automagic stuff done by the Rust >>compiler enough to get this kind of tree insertion past the borrow
checker, even though it is possible, I don't trust my capabilities to
audit unsafe Rust.

Is it significantly different than doing so in C, Pascal, or
Forth? See the second program, above; the use of `unsafe` in
the bits that correspond to your sketch in C is constrained to
two places that indirect raw pointers.

I may be able to shut up the compiler and get an executable with
"unsafe", but will the resulting program work? And I can have the
same assurance in C or Forth, so why should I switch to Rust to get
that?

It's so common that "fighting the borrow checker" is the
community's slogan to describe it.

Sounds to me like "the community" has found a convenient cliche to
avoid thinking about why people have difficulties with Rust, and why
these difficulties may increase as Rust advances.

From the books I read, I get the impression that
Rust used to have less automagic stuff, and much of the automagic was
added later, as a convenience for the programmers who already knew the >>language. So the Rust programmers of the early days formed a mental
model based on "Pedestrian Rust" (i.e., with less automagic), and when
they see a program with more automagic, and need to understand some >>conveniently short piece of Rust code in detail, they form a mental
model of the code in Pedestrian Rust. But how can a Rust programmer
who starts now learn Pedestrian Rust and how it relates to the modern >>language. There are hints in the books I read, but not enough to get
a firm foundation.

Early Rust was very different, and much closer to a managed
language with garbage collection, green threads, a heavy-weight
runtime, etc. Put another way, the trend has been less and less
"automagic" (as you put it) and making things more explicit over
time.

What I mean is the automatic dropping, and the fact that the Box stuff
only occurs in the type declarations, but is automatically
dereferenced or otherwise automatically handled; "let x = ..."
produces a type automatically (but I guess you could put a type
declaration there, though).

You keep conflating things you are not familiar with in a
language you are not familiar with, with the idea that those
things are "automagic." But really there is no magic here, and
I suspect the answer to your question about how one learns to
adapt their mental model of Rust is to first stop thinking of it
as magical.

The language hides a number of things with automation, and given that
I have no good mental model for that, following Clarke's third law
("Any sufficiently advanced technology is indistinguishable from
magic."), I refer to that automatic stuff as "automagic stuff". I
don't think it's magic, it just tries to be indistinguishable. It
shouldn't.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >[email protected] (Dan Cross) writes:

[Crossposted and and Followup-To: comp.programming]

Given that I don't subscribe to c.p, I kept comp.arch in the
Newsgroups.

Ok. If it doesn't bother the regulars, then I guess that's
fine. It seems off-topic, but sure.

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

My goal was to implement search tree insertion as efficiently and >>>compactly as in Pascal, C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

An intersting way to write it; I understand you're trying to
reuse `search` in `insert`, below, and thus why you want to
return `rootp`.

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);

I know you said this was untested; clearly you should not
indirect the result of `search` here.

struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these >>>languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

I also knew Java solutions to the problem:

1) Special-case the root (which you typically have to do in Java
anyway, and otherwise always keep a pointer to the last tree node
around, and also keep the knowledge about the last left-or-right
decision around (or take it again). This all leads to quite a bit of >>>code that is duplicated relative to the code above.

2) Recurse into the tree and rewrite all the links to the subtrees
along the spine of the search. This is not quite as duplicative as 1) >>>(but the root still has to be handled separately), but it performs >>>several writes instead of just one, and the recursion is not a tail >>>recursion, so is relatively expensive.

Or, 3) Simply reimplement the comparison in `insert`

That goes along with 1), but I forgot to mention it.

It is an important distinction.

it's a trivial amount of code.

There's the rub. I don't consider a factor of ~2 trivial, even if it
is only 20 lines of code.

Repeating the conditional is 5 lines, including the closing
brace on a ine by itself. The `while` surrounding it is another
2, again including the closing brace.

And in particular, "simply reimplement"
means that the same thing occurs several times in the code, and in >maintainance one must remember to change all of the occurences.

It's a loop around a match over a conditional expression:

while let Some(node) = root {
root = match key.cmp(&node.key) {
Ordering::Less => &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => &mut node.right,
};
}

And in fact it _has_ to be different in a way, because the
reference must be mutable, whereas for searching as a lookup,
that is not necessary.

You could wrap that in a macro if you really wanted to.

Fortunately, that's not necessary in Rust. But the fact that you did
not find it tells me that Rust is hard even for experienced Rust
programmers.

I do not know what you are referring to when you write, the
"fact that you did not find it"; did you not notice that I gave
you _two_ programs, one of which was pretty much the same as the
C program you gave? What, exactly, are you referring to?

I chose a variant of (1) for my implementation, but only because
it was easy, not because it was required. No unsafe code or
fancy reference counting here.

BEGIN `tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree { root: None }
}

/// Searches the tree for the given key, and returns
/// `Some(&value)` if it's here, otherwise returns None.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// tree.insert(2, 200);
/// tree.insert(1, 100);
/// assert_eq!(tree.search(&0), None);
/// assert_eq!(tree.search(&1), Some(&100));
/// assert_eq!(tree.search(&2), Some(&200));
/// ```
pub fn search(&self, key: &K) -> Option<&V> {
let mut root = &self.root;
while let Some(node) = root {
match key.cmp(&node.key) {
Ordering::Less => root = &node.left,
Ordering::Equal => return Some(&node.value),
Ordering::Greater => root = &node.right,
}
}
None
}

/// Inserts the given `value` into the tree with the given
/// `key`. Returns true if the node was inserted, or false
/// if the key was already in the tree.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// assert_eq!(tree.insert(1, 100), true);
/// assert_eq!(tree.insert(1, 200), false);
/// assert_eq!(tree.insert(2, 100), true);
/// ```
pub fn insert(&mut self, key: K, value: V) -> bool {
let mut root = &mut self.root;
loop {
let Some(node) = root else {
root.replace(Node::new(key, value));
return true;
};
match key.cmp(&node.key) {
Ordering::Less => root = &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => root = &mut node.right,
}
}
}

/// Print the tree, if it is not empty.
pub fn print(&self) {
if let Some(node) = &self.root {
node.print();
}
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: Option<Box<Node<K, V>>>,
right: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: None,
right: None,
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
if let Some(left) = &self.left {
left.print();
}
println!("key = {:?}, value = {:?}", self.key, self.value);
if let Some(right) = &self.right {
right.print();
}
}
}

END `tree.rs`<---

Note that there's more code here than in your C code, but this
also does a lot more; this is generic over any key and value
types where the key type implements a total ordering, and where
both types implement the `Debug` trait (so they can be printed).

If I don't need any of that, does it get smaller? I don't think so.

Here's my attempt, and I expect that experienced Rust programmers will
find ways to improve on it. It includes a lookup function:

-------------------
use std::cmp::Ordering;

pub struct Tree<K: Ord, V> {
root: Subtree<K, V>,
}

type Subtree<K,V> = Option<Box<Node<K,V>>>;

struct Node<K: Ord, V> {
key: K,
val: V,
left: Subtree<K, V>,
right: Subtree<K, V>,
}

impl<K: Ord,V> Tree<K,V> {
pub fn new() -> Self {
Tree { root: None }
}

pub fn insert(&mut self, key: K, val: V) {
let mut t = &mut self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => {node.val = val; return;},
Ordering::Less => t = &mut node.left,
Ordering::Greater => t = &mut node.right,
};
};
*t = Some(Box::new(Node {key, val, left: None, right: None}))
}

pub fn lookup(&self, key: K) -> Option<&V> {
let mut t = &self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => return Some(&node.val),
Ordering::Less => t = &node.left,
Ordering::Greater => t = &node.right,
};
};
None
}
}

This is essentially the same program I just presented to you;
you added a type alias, changed `insert` to set the value, and
used `*t` instead of `.replace` for inserting a new node, used
ersatz formatting (ie, not `rustfmt`), and omitted the comments.

I find it strange that you claim this as different from what I
presented to you, except in trivial details, while also telling
me that I "did not find" something.

Are you sure you actually ready my post, and the programs in it?

fn main() {
let mut q1 = Tree::new();
q1.insert(2,"abc".to_string());
q1.insert(3,"def".to_string());
q1.insert(1,"ghi".to_string());
q1.insert(3,"jkl".to_string());
println!("{:?}",q1.lookup(1));
println!("{:?}",q1.lookup(2));
println!("{:?}",q1.lookup(3));
}
----------------------------

Like your code and Java code, this has a separate type Tree with a
field root and with its own new function, while in C a "struct tree *" >variable can serve as root pointer; and this leads to an additional
line each in insert and lookup. Can we do without most of that
(havibf a constructor is useful) and just use Subtree instead of Tree?

Sure. I do not think it is an interesting exercise, though.

insert now integrates search, because I could not satisfy the compiler
with a separate search; maybe a more experience Rust programmer can
separate it out again. The advantage is that there is no need to
combine the found and notfound cases in one return value in search,
only to handle them as separate cases in insert. But at least there
is no duplication of the comparison code.

I fail to see how your program is very different from mine,
aside from using the type alias for `Subtree`. The comparison
is clearly duplicated in your code. Perhaps you are commenting
on a hypothetical where that does not happen, as in my second
example?

The integration of search in insert led to a duplication of most of
the search code in lookup. However, requiring a mutable reference is
not necessary for the lookup code, so a search that takes a mutable
reference and returns a mutable reference is too restrictive for
lookup. But maybe a more experienced Rust programmer can write a
generic search that takes an &mut tree for insert, and a & for lookup.

If it offends you that much, you could use a macro.

By analogy, in your C, how would it affect things if you wanted
to `const` qualify the tree pointer for lookups?

Of course, if search is factored out, both clients have to explicitly
check for both outcomes and have code for both. But that's probably >preferable to duplicating the search.

See my second program in the post you responded to.

though the pointer-to-pointer
to a node is not returned by `search`. If that is what you mean
by "technique" then you're right; doing that in Rust is
inconvenient because it violates the borrow checker's rules
about the existence of multiple simultaneous mutable references
to an object.

Yes, that's what I meant by "technique". And it's possible in safe
Rust, but I had a very hard time finding it (and for a while thought
that it is not possible). The fact that you thought it is not
possible in safe Rust means that it is not just my inexperience at
fault here.

I did not say that it was "not possible"; indeed, I can think of
any number of ways to do it, using interior mutability, arcs,
etc. I said it was inconvenient, and I would argue not very
interesting.

You seem to be claiming you have a solution to this, but have
yet to present that code; your program above was basically a
copy of my program, and your commentary suggests you couldn't
figure out a different way to write it yourself.

But I claim that is just a detail, and not a
terribly interesting one at that; certainly not an impediment to >>substituting Rust for C in systems programming.

I think that, in order to be the rightful heir, safe Rust should be
able to do everything one can do in the other language that's not
inherently unsafe, and do it without needing to duplicate code of
other nastyness.

I think that criteria is both silly and arbitrary, and has no
basis in actual practice. You are asserting that an arbitrary
implementation detail of this one program is a useful yardstick
by which to measure a language's applicability to an entire
problem domain, and then defined your criteria so that it
excludes the most obvious translation.

You may wonder about "inherently unsafe": I have no
definition for that yet, but I would not kno why inserting a node into
a search tree would ever fall into that category,

Actually, I think perhaps it's the other way around: you do not
seem to know what "unsafe" means in a Rust context. It is
merely a statement that the compiler cannot infer that the
"unsafe" code meets the language's memory safety criteria, and
that the programmer is asserting that it does; that is exactly
the same as every line in a C program.

Even so, as I said, one _can_ use the same technique using a
smallish-bit of `unsafe` code.

That's cool, but given that I have difficulty understanding why the
compiler complained about my version with separate search, I feel very >uncomfortable in asserting to the compiler that my use of unsafe
features is safe once we leave the unsafe block.

I'm afraid that sounds like a problem for you to deal with, not
a problem with Rust.

Frankly, unless I was doing something very odd, I wouldn't write
my own binary search tree at all; the standard library's
collections implementations are pretty good

And I actually don't use binary search trees anyway, neither
self-written nor from libraries, because hash tables tend to be the
better alternative, except when I want to know the next-higher element
or somesuch. But being able to have a reference to a field is also
useful when implementing hash tables.

But anyway, the libraries have to be written in some language, and
given that Rust fans tell us to rewrite all C code in Rust, I would
expect that the library should be written in Rust, and, in particular
in safe Rust (otherwise, why rewrite it in Rust?).

I'm not sure how useful it is to try to explain this, since your
thoughts on the matter appear to have already calcified.

But the reason is that locality of reasoning is a powerful tool
when building reuseable components. Does the Rust standard
library use `unsafe` code? Yes, it does. However, it wraps
that in a safe facade, and competent Rust programmers seek to
minimize it. The `unsafe` code is then heavily audited; this
does not guarantee bug freedom, but no one serious ever claimed
that it did. However, it _does_ make debugging dramatically
easier: if a program dumps core at some point down the road,
it's likely that the crash originated in `unsafe` code in a
library, and that becomes the focus for looking for the bug.

And actually, we teach our students how to write this stuff (even in
Java), because we think it teaches them something useful. And at
least one Rust fan thinks so, too, and wrote "Learn Rust With Entirely
Too Many Linked Lists", where I found out how to implement the
mentioned technique in safe Rust.

Yes. Gankra was also the driving force behind the strict
pointer provenance work. You may enjoy her writing on, "the
tower of weakenings."

Given that I do not understand the automagic stuff done by the Rust >>>compiler enough to get this kind of tree insertion past the borrow >>>checker, even though it is possible, I don't trust my capabilities to >>>audit unsafe Rust.

Is it significantly different than doing so in C, Pascal, or
Forth? See the second program, above; the use of `unsafe` in
the bits that correspond to your sketch in C is constrained to
two places that indirect raw pointers.

I may be able to shut up the compiler and get an executable with
"unsafe", but will the resulting program work? And I can have the
same assurance in C or Forth, so why should I switch to Rust to get
that?

Because with C and Forth you can't just wrap the unsafe bits
behind a safe interface that consumers can rely on, placing the
burden on all users to ensure safety, whereas in Rust, you can.

Consider the arguments in in your Tree example; the tree itself
is a pointer to a pointer to the root. What if that pointer is
garbage? What if it's dangling? In Rust, `&self` is guaranteed
to be a valid, non-nil reference to a live object, and moreover
you are guaranteed that no other thread is trying to mutate that
object while you're holding that ref. Neither C nor Forth can
give you any such guarantee. Similarly, `&mut self` guarantees
that no other reference to the object exists. Visibility
similarly gives you control; by wrapping, say, a raw pointer
inside of an `struct` as a non-public member, you can guarantee
that the same pointer is the one used in multiple, subsequent
function calls: as written, your C code has two functions that
share no relationship save that one calls the other. I could
cal `insert`, and then go and muck with the tree myself, so that
its ordering constraints are violated, and then call `insert`
again and have a tree that didn't respect the BST properties. I
could pass a random garbage `root` pointer and cause the program
to crash. And so on.

Do I really need to go on, here?

It's so common that "fighting the borrow checker" is the
community's slogan to describe it.

Sounds to me like "the community" has found a convenient cliche to
avoid thinking about why people have difficulties with Rust, and why
these difficulties may increase as Rust advances.

Bluntly, I think you are not really in a position to make that
claim, and are inventing excuses to justify your preconceptions
and biases.

From the books I read, I get the impression that
Rust used to have less automagic stuff, and much of the automagic was >>>added later, as a convenience for the programmers who already knew the >>>language. So the Rust programmers of the early days formed a mental >>>model based on "Pedestrian Rust" (i.e., with less automagic), and when >>>they see a program with more automagic, and need to understand some >>>conveniently short piece of Rust code in detail, they form a mental
model of the code in Pedestrian Rust. But how can a Rust programmer
who starts now learn Pedestrian Rust and how it relates to the modern >>>language. There are hints in the books I read, but not enough to get
a firm foundation.

Early Rust was very different, and much closer to a managed
language with garbage collection, green threads, a heavy-weight
runtime, etc. Put another way, the trend has been less and less >>"automagic" (as you put it) and making things more explicit over
time.

What I mean is the automatic dropping, and the fact that the Box stuff
only occurs in the type declarations, but is automatically
dereferenced or otherwise automatically handled; "let x = ..."
produces a type automatically (but I guess you could put a type
declaration there, though).

Drop and box as a smart pointer is simply "RAII", which has been
in C++ since the 1980s. Hindley and Milner created the type
inference rules you are referring to here in the 1970s.

You keep conflating things you are not familiar with in a
language you are not familiar with, with the idea that those
things are "automagic." But really there is no magic here, and
I suspect the answer to your question about how one learns to
adapt their mental model of Rust is to first stop thinking of it
as magical.

The language hides a number of things with automation, and given that

No, it really doesn't.

I have no good mental model for that, following Clarke's third law
("Any sufficiently advanced technology is indistinguishable from
magic."), I refer to that automatic stuff as "automagic stuff". I
don't think it's magic, it just tries to be indistinguishable. It
shouldn't.

Sorry, but I see no evidence that you have taken the time to
actually understand that the things you attribute to automation
are actually rather explicit; you're a smart guy, and I'm quite
sure you could do it if you wanted; it's really all rather
obvious once you dig into it a little bit. Given that, and that
you continue to assert that it's "automagic" I can tell that you
simply don't want to, perhaps because it is different from what
you are used to.

Hint: when an object goes out of scope, it is "dropped." A type
can register a "drop handler" by implementing the `Drop` trait.
For a smart pointer like `Box`, that simply frees the thing it
points to. Same with a Mutex: the `lock()` operation returns a
`MutexGuard` object that holds the lock. When it goes out of
scope, its `drop()` method unlocks the mutex. Cf, https://cliffle.com/blog/rust-mutexes/

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

[email protected] (Dan Cross) writes:

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >>[email protected] (Dan Cross) writes:

[Anton Ertl:]

I do not know what you are referring to when you write, the
"fact that you did not find it"; did you not notice that I gave
you _two_ programs, one of which was pretty much the same as the
C program you gave? What, exactly, are you referring to?

I was referring to your safe Rust solution. However, I did not look
at it closely enough, especially at your insert, to realize that what
you had done is to turn search into lookup, and that you do not call
search from insert, like the C version does.

I just saw that there is a similar match in your insert as in search
(and the non-recursive Java version would also have that) and set out
to refine an existing linked-list implementation with insertion at the
end into a tree insertion that does not repeat the match, and I used
your match code from search for the parts that the linked-list
implementation does not do.

The list variant has the walk to the end separated from the actual
insertion, and the C tree variant also does it that way, and I wanted
the Rust version to do the same, but could not get it past the Rust
compiler. The insertion code did not look particularly nice, either,
checking for something that is alreadu known in the search code. so
to work around the compiler problem, I eventually decided to inline
the search code into insert, and I could get that to compile.

For testing I then added a lookup, which was derived from the search
part of insert, without mut stuff, so it's full circle back at your
search.

Anyway, yes, your insert does not work the Java version, but like the
C version with search() inlined into insert(), and like the insert I
finally arrived at.

Which leads to the question? Can an experienced Rust programmer do a
search that works like the C search(), and an insert that calls
search() and then uses the reference to either update a node or insert
a new one?

Like your code and Java code, this has a separate type Tree with a
field root and with its own new function, while in C a "struct tree *" >>variable can serve as root pointer; and this leads to an additional
line each in insert and lookup. Can we do without most of that
(havibf a constructor is useful) and just use Subtree instead of Tree?

Sure. I do not think it is an interesting exercise, though.

I tried it for a while, and did not get anything but more and more
compiler errors.

The integration of search in insert led to a duplication of most of
the search code in lookup. However, requiring a mutable reference is
not necessary for the lookup code, so a search that takes a mutable >>reference and returns a mutable reference is too restrictive for
lookup. But maybe a more experienced Rust programmer can write a
generic search that takes an &mut tree for insert, and a & for lookup.

If it offends you that much, you could use a macro.

Good to know that there is this option.

By analogy, in your C, how would it affect things if you wanted
to `const` qualify the tree pointer for lookups?

C works perfectly fine without "const", so why would I want to do that?

By contrast, Rust is picky about "mut". If I add it everywhere where
the syntax allows it (which might be the analogon of leaving "const"
away), the borrow checker will complain about programs that it
accepted before adding all the "mut"s.

I think that, in order to be the rightful heir, safe Rust should be
able to do everything one can do in the other language that's not >>inherently unsafe, and do it without needing to duplicate code of
other nastyness.

I think that criteria is both silly and arbitrary, and has no
basis in actual practice. You are asserting that an arbitrary
implementation detail of this one program is a useful yardstick
by which to measure a language's applicability to an entire
problem domain,

Not one detail, the collection of all the details. This is one.

You may wonder about "inherently unsafe": I have no
definition for that yet, but I would not kno why inserting a node into
a search tree would ever fall into that category,

Actually, I think perhaps it's the other way around: you do not
seem to know what "unsafe" means in a Rust context. It is
merely a statement that the compiler cannot infer that the
"unsafe" code meets the language's memory safety criteria, and
that the programmer is asserting that it does;

I understand that.

that is exactly
the same as every line in a C program.

The decisive difference is that in a C program there is no end to an
unsafe block, where I have to satisfy safety criteria that are beyond
my experience level.

I'm afraid that sounds like a problem for you to deal with, not
a problem with Rust.

Sure, and the way I deal with that is to not use unsafe Rust.

What I mean is the automatic dropping, and the fact that the Box stuff
only occurs in the type declarations, but is automatically
dereferenced or otherwise automatically handled; "let x = ..."
produces a type automatically (but I guess you could put a type
declaration there, though).

Drop and box as a smart pointer is simply "RAII", which has been
in C++ since the 1980s. Hindley and Milner created the type
inference rules you are referring to here in the 1970s.

And?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

Which leads to the question? Can an experienced Rust programmer do a
search that works like the C search(), and an insert that calls
search() and then uses the reference to either update a node or insert
a new one?

IIUC it can but at the cost of making `search` take a `&mut` reference.
I get the impression that you'd otherwise need "mutability
polymorphism", i.e. a single piece of code that can be instantiated
either for `&` or for `&mut`. You can probably avoid writing the code
twice, tho, by abusing macros (aka "template polymorphism").


=== Stefan
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >[email protected] (Dan Cross) writes:

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >>>[email protected] (Dan Cross) writes:

[Anton Ertl:]

I do not know what you are referring to when you write, the
"fact that you did not find it"; did you not notice that I gave
you _two_ programs, one of which was pretty much the same as the
C program you gave? What, exactly, are you referring to?

I was referring to your safe Rust solution. However, I did not look
at it closely enough, especially at your insert, to realize that what
you had done is to turn search into lookup, and that you do not call
search from insert, like the C version does.

Clearly.

Forgive my saying it, but bluntly, this calls into question your
entire reading of my post.

I just saw that there is a similar match in your insert as in search
(and the non-recursive Java version would also have that) and set out
to refine an existing linked-list implementation with insertion at the
end into a tree insertion that does not repeat the match, and I used
your match code from search for the parts that the linked-list
implementation does not do.

The list variant has the walk to the end separated from the actual
insertion, and the C tree variant also does it that way, and I wanted
the Rust version to do the same, but could not get it past the Rust
compiler. The insertion code did not look particularly nice, either, >checking for something that is alreadu known in the search code. so
to work around the compiler problem, I eventually decided to inline
the search code into insert, and I could get that to compile.

For testing I then added a lookup, which was derived from the search
part of insert, without mut stuff, so it's full circle back at your
search.

Anyway, yes, your insert does not work the Java version, but like the
C version with search() inlined into insert(), and like the insert I
finally arrived at.

Yes. I take it that here, you are describing the process by
which you arrived at the program you posted in your response to
me.

Which leads to the question? Can an experienced Rust programmer do a
search that works like the C search(), and an insert that calls
search() and then uses the reference to either update a node or insert
a new one?

Given that you did not read the first program in my post
carefully, I wonder whether you read the _second_ program in my
post carefully, or rather, closed over it like the first. I
suggest having a look at that.

Like your code and Java code, this has a separate type Tree with a
field root and with its own new function, while in C a "struct tree *" >>>variable can serve as root pointer; and this leads to an additional
line each in insert and lookup. Can we do without most of that
(havibf a constructor is useful) and just use Subtree instead of Tree?

Sure. I do not think it is an interesting exercise, though.

I tried it for a while, and did not get anything but more and more
compiler errors.

*shrug* Is it useful as anything other than an academic
exercise?

The integration of search in insert led to a duplication of most of
the search code in lookup. However, requiring a mutable reference is
not necessary for the lookup code, so a search that takes a mutable >>>reference and returns a mutable reference is too restrictive for
lookup. But maybe a more experienced Rust programmer can write a
generic search that takes an &mut tree for insert, and a & for lookup.

If it offends you that much, you could use a macro.

Good to know that there is this option.

By analogy, in your C, how would it affect things if you wanted
to `const` qualify the tree pointer for lookups?

C works perfectly fine without "const", so why would I want to do that?

Are you joking? What if you have a `const struct tree` and want
to take a pointer to it?

More generally this is the sort of thing I'm referring to; Rust
is a different language than C, with different semantics, and
it imposes different constraints on programs than C. One can,
if motivated, find some program that one can express in C, but
that cannot be expressed the exact same way in Rust. But why is
that notable? One could well invert this: I can define some
program that I express in Rust and ask why it cannot be
expressed in the exact same way in C. But by itself, that's not
terribly interesting; what matters more is whether there are
problems, or perhaps more importantly categories of _problems_,
that are expressible in one and not the other. I don't think
there really are; the solutions might differ in some ways, but
that's to be expected because the languages themselves are
different.

By contrast, Rust is picky about "mut". If I add it everywhere where
the syntax allows it (which might be the analogon of leaving "const"
away), the borrow checker will complain about programs that it
accepted before adding all the "mut"s.

That's right. The language imposes semantic constraints on
mutability and references; see my other post about this. But
surely this is not surprising?

I think that, in order to be the rightful heir, safe Rust should be
able to do everything one can do in the other language that's not >>>inherently unsafe, and do it without needing to duplicate code of
other nastyness.

I think that criteria is both silly and arbitrary, and has no
basis in actual practice. You are asserting that an arbitrary >>implementation detail of this one program is a useful yardstick
by which to measure a language's applicability to an entire
problem domain,

Not one detail, the collection of all the details. This is one.

All what details? Your statemtn was that, "safe Rust shoudl be
able to do everything one can do in the other language that's
not inherently unsafe". But missing here is your definition of
what you mean by, "unsafe". I gave you Rust's definition: the
safety of a program is determined by whether or not the compiler
can infer that the program upholds the rules of the language vis
borrows, mutability, lifetimes, and so on; that is, whether the
borrow checker can do its job. But there are cases where the
programmer has some insight into the context of the program that
the borrow checker just can't see into; hence, `unsafe` as a
part of the language.

You may wonder about "inherently unsafe": I have no
definition for that yet, but I would not kno why inserting a node into
a search tree would ever fall into that category,

Actually, I think perhaps it's the other way around: you do not
seem to know what "unsafe" means in a Rust context. It is
merely a statement that the compiler cannot infer that the
"unsafe" code meets the language's memory safety criteria, and
that the programmer is asserting that it does;

I understand that.

Forgive me, but I'm not so sure. Under that definition, the
entirety of a C program is `unsafe`; it's up to the programmer
to uphold the invariants of the language, and there isn't much
in the way of requirements on the _language itself_ to help you
out. In this way, you seem to be putting a greater burden on
Rust than you do on C.

that is exactly
the same as every line in a C program.

The decisive difference is that in a C program there is no end to an
unsafe block, where I have to satisfy safety criteria that are beyond
my experience level.

In seeming contradiction to what I wrote above, I think that it
_is_ harder to write correct `unsafe` Rust code than to write
correct C code, which is one reason Rust programmers try to
isolate `unsafe` code as much as possible. The flip side is
that, if you do, the language gives you hard guarantees that you
can rely on to write correct programs; entire categories of
errors are eliminated by construction.

The thing that you wrote that does not follow is that `unsafe`
Rust code is never allowed to _violate_ those safety criteria;
it's just that the programmer takes on burden of upholding them,
with less assistance from the language. It is not an escape
hatch to YOLO your program.

I'm afraid that sounds like a problem for you to deal with, not
a problem with Rust.

Sure, and the way I deal with that is to not use unsafe Rust.

*shrug* That's on you, not on Rust.

What I mean is the automatic dropping, and the fact that the Box stuff >>>only occurs in the type declarations, but is automatically
dereferenced or otherwise automatically handled; "let x = ..."
produces a type automatically (but I guess you could put a type >>>declaration there, though).

Drop and box as a smart pointer is simply "RAII", which has been
in C++ since the 1980s. Hindley and Milner created the type
inference rules you are referring to here in the 1970s.

And?

...and so it's not "automagic". It's simply an application of
well-known, pre-existing, techniques.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

In article <[email protected]>,
Stefan Monnier <[email protected]> wrote:

Which leads to the question? Can an experienced Rust programmer do a
search that works like the C search(), and an insert that calls
search() and then uses the reference to either update a node or insert
a new one?

IIUC it can but at the cost of making `search` take a `&mut` reference.
I get the impression that you'd otherwise need "mutability
polymorphism", i.e. a single piece of code that can be instantiated
either for `&` or for `&mut`. You can probably avoid writing the code
twice, tho, by abusing macros (aka "template polymorphism").

...or using interior mutability with e.g., a `Cell`.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

On Sun, 11 Oct 2026 14:26:48 -0400, Stefan Monnier wrote:

You can probably avoid writing the code twice, tho, by abusing
macros (aka "template polymorphism").

Why would that be “abusing”? Aren’t macros designed for just such a purpose?
--- Synchronet 3.22a-Linux NewsLink 1.2