How to make rust usable in schools

There is the problem that a i64 can't be represented exactly within a f64, nor a f64 within a i64, so you really do need to be aware of which type you're using, and the limitations of that type for arithmetic.

Lua used to be just f64, which is at least consistent, but then in 5.3 added hidden i64 as an optimization. So if you're just using integers, it stays on integers, but it converts otherwise. But ... guess what, if you add one to the last integer, it wraps ... but if it had got converted to a f64 at some point, it doesn't. So:

> 0x7FFFFFFFFFFFFFFF + 1
-9223372036854775808
> 0x7FFFFFFFFFFFFFFF + 1.1
9.2233720368548e+18

So now there is inconsistent behaviour which depends on how that value was produced, i.e. now everyone has to remember this little glitch, at least if there's a chance they might pass this threshold with their calculations. It seems to me that it's better to be in control of the type really.

Regarding x++, for a pointer-based language like C, it makes sense as it compiles straight down to operations in machine code (e.g. 68000 especially had auto-increment built in). But Rust is not pointer based, because pointers are really dangerous unless constrained. So the equivalent with a slice would be p= &p[1..] for example, i.e. it has to be written another way anyway to be safe. So I don't miss it. You don't need it so much anyway. Even if you do need it, it's just a little bit of boilerplate in the name of safety, and the safety is worth it.

10 Likes

If you ends up adding an integer to a float, you should stop and check how you came to this. This is not a normal situation, thus it should be painful. Only after appropriate check is performed and you really sure that a conversion is justified, you can add the explicit conversion.

P. S. Unary increment/decrement operator is EVIL. It is a target for abusing and a source of logical bugs.

5 Likes

Possibly related: https://internals.rust-lang.org/t/pre-proposal-math-working-group/13274

I wouldn’t go so far as to say it should be painful, but it is nice that it is visible. Especially now that casts are defined to be saturating, it seems very clear when and how conversions are happening.

From a teaching perspective, maybe initially contrived examples which only deal with one numeric type could be used, and then later expand to teaching how conversion between different types works and why it is useful.

Do what? How does that work exactly now then?

Here's the relevant post in blog. In short:

  • floats too large or too small (by value, not by exponent) to fit into the target type are clamped to the maximum/minimum values correspondingly;
  • NaNs are converted to zeroes.
2 Likes

Ah thanks.

So basically, as it says, it used to be that if you cast [using as] a floating point number that's large to an integer that's small, you get undefined behavior. And such similar cases. This has now been defined.

The solution sounds good to me. If you want to get as close to infinity as possible in a u8 you have 255, and so on. At least better than ending up with a random number.

I'd add that as a note to the end of my old “as” considered harmful thread but that seems to have timed out a been locked. "as" considered harmful?

I don't recalling any describing the old undefined behavior exactly in that thread.

2 Likes

ccgauche It is not a good idea to teach Rust at schools of course if you are meaning primary school - the Rust lang is not designed for educational purpouses by its creators. So it is silly to change the lang design for the reasons you state only

Programming courses for me became available in 8th grade (age: ~13 years) and IMO, starting much earlier wouldn't be a good idea, anyway. We had some general computer courses in 5th/6th grade, but those didn't involve programming.

Maybe, with visual programming, you could start earlier and lower the entrance barrier, but I only see the latter purpose as helpful. People still have to finish their special education (~3 years) after high school to be able to get a job as a developer.

That being said, different countries = different rules. I can only speak for my own experience in Germany/Berlin, not for anyone else and especially not for anyone outside Germany.

Time for me to slowly get back to the original topic: Rust has a steep learning curve, because it is a very pedantic and flexible programming language. There are so many ways to solve bigger problems, it's intimidating.

Also, please, never ever teach anyone how to make a linked list with Rust in their first year of programming. That'd be crazy. You can do that with GC languages, instead.

It's generally a good idea to show off several languages, that each have their own strengths and weaknesses. Just use another language that suits your needs, if you think the language is lacking in something. That's just natural, since all languages have trade-offs. There is no single programming language to rule them all.

It's not clear to me why anyone would want to teach high schoolers about linked lists in their first steps in programming. As I described above in my first years of programming we never heard of such things. Our programming tasks were related to the maths/physics we were doing at the time.

On the other, the other day I found I had knocked up a directed acyclic graph in Rust, as used in the old Hunt the Wumpus Game, and it was dead easy. All my nodes were are in a vector and all the links are just indices. No problem. I would expect teenage beginners to programming to grasp that pretty easily. No more difficult that doing same in Python or whatever.

2 Likes

Perhaps when we discuss "linked lists" in Rust we should distinguish between "pointer-based linked lists", which in Rust require very advanced skill and are fraught with potential UB, and "index-based link lists" (e.g., indexing into a Vec used as arena storage), which are trivial in Rust.

Or, there's the good ol' singly linked list, which is trivial to implement in Rust safely (Option<Box<Node>>).

Why?

The linked list, as a concept, is independent of how one actually realizes it.

And what is the conceptual difference between "pointer based" and "index based"?

After all, memory is just a big array, and pointers are just indices into that array.

The kind of indexes represented by Rust's raw pointers are not bounds-checked though :slight_smile: Hence, raw pointers are hard to use correctly, they have a potential of resulting in UB. The difference here is not conceptual any more – it's purely practical.

2 Likes

I'd say the differences are asymptotic runtime behavior as well as cache locality due to the way they're allocated.
A real linked list has each node allocated when consed to that list. So adding an element requires allocating. In addition, consing to or removing from the front is O(1), adding to or removing from the back is O(n) because you need to traverse the list to find its end.

In contrast, an index/arena based list isn't a linked list at all, it's a vec in terms of characteristics. Adding to or removing from the front is O(n) because pre-existing elements need to be moved, removing from the back is O(1) and assuming the arena is large enough, so is adding to the back. And oherwise it is O(n).

It is, but how you divvy up that array can matter quite a bit.

I currently teach to my students python for algorithms and oCaml for functional programming. This is why I think rust can be a good choice because of his functional and imperative nature. Rust is simple and practical compared to other multiparadigm alternatives. My students have between 15 and 18. So only having one langage for them to learn would be a good thing! They are very confused when I start to teach them oCaml. They try to think in python which is not possible in oCaml.

1 Like

Yeah, I think that the number model of Rust is simply designed better for actually controlling the CPU than thinking in more abstract number and math terms. Still, this could be a good place for a crate to fill in and make numbers more "virtual" and just try to make them work as much like you would expect from a math perspective. Maybe there could be a macro like expr! that allows you to put in math expressions and it will handle the numbers more naturally. For example:

assert_eq!(expr!(3.2 + 5), 8.2);

And in this case it wouldn't complain that you can't add an f32 and an i32.

My claim is that the notion of a linked list is about a set of items (nodes) that refer to other similar items (links) in such a way as to form a chain of linked nodes (list). It's about how one indicates the end of that chain. It's about how one, algorithmically, extends that chain or inserts new nodes in the middle or removes nodes, etc.

As such the linked list, conceptually, is nothing to do with "cons" and "cdr". It has nothing to do with memory addresses, raw pointers, array indices etc. They are just a means of implementing the notion of a linked list. A linked list could as well be a bunch of objects in a JSON document, a bunch of hyperlinked web pages or a pile of rocks with numbers on them!

That is just cruel :slight_smile:

Nothing need be moved when implementing a linked list vector/array. If you are inserting at the front by moving all the elements up then you have not implemented a linked list. In fact if you move all the elements in the array you have broken all the links as now all the elements contain the wrong index for their successor. As surely as moving all the nodes of a C style linked list around in memory, all the pointers become invalid.

In the simplest array based linked list new nodes are inserted, at the front, back or in the middle of the list by writing the new node into the next free array element and fixing up the head index or whatever node indices required to maintain the list. Removing nodes from from the list is just a matter of adjusting the head index or fiddling with successor link of a node.

Of course that "leaks" array elements as nodes are unlinked from the list. Fixing that is the subject of lesson 2 :slight_smile:

2 Likes

That's precisely what I said earlier. The arena-based version isn't a linked list at all, it's a Vec with another name.

1 Like

As nobody has posted code samples or detailed pseudocode, referring to “the arena-based version” is incorrect: There are many potential ways to implement a linked-style structure with an arena-style allocator, and each one will have different properties.

If you want to talk about some specific data structure, it’s probably best to provide some concrete description to ensure everyone is talking about the same thing.