Irenic language comparisons and questions: Ada and Rust; AoC 2023 Day 13

[cantanima]

Preface

(You can probably skip this w/out losing anything very meaningful. Sorry it’s so long, but I wasn’t sure )

As the 2023 Advent of Code was starting up, @JeremyGrosser encouraged discussion on solutions in different languages. This interests me, as I usually complete the puzzles in Ada, but use Rust at work, and I had been thinking of switching for this year. So, thanks to @JeremyGrosser for giving me yet another justification to stick with Ada!

So far, I’ve completed all 25 puzzles in Ada (49 if you count each part separately) and the first 13 (26) in Rust. Each informs the other, and has prompted a few questions. Here are a couple.

Questions

Well after solving day 13 in Ada with “traditional” for loops and if statements, I went back and translated the Ada solution to a Rust solution.

However, it wasn’t idiomatic Rust, so I reworked it, eliminating every for loop and if statement for which a qualified iterator would do the job. (What I call a “qualified iterator” is what a lot of Rustaceans call “functional programming.”)

Ada 2012 and Ada 2022 offer expression-based constructs such as declare expressions, quantified expressions, and 'Reduce expressions. While reworking the Rust, I wondered if they might help make my solutions clearer and more concise.

I managed to pull it off, and I rather like the result, but I’m interested in feedback, especially:

1. Was this an inappropriate use case for declare expressions, quantified expressions, etc.?
2. Even if not, is there a more elegant solution?

If you want to refer to the current code, it’s here. Commit history is here.

Why on earth would you do this?

As an Italian saying goes, Così mi gira la testa. Literally, “That’s how my head turns.” (Or “spins”, if you prefer.) If nothing else, I want to learn the new tools.

(You can probably skip this part without losing anything too meaningful.)

Part 1 asks you to find a line of symmetry in a map.

You note down the patterns of ash (.) and rocks (#) that you see as you walk (your puzzle input); perhaps by carefully analyzing these patterns, you can figure out where the mirrors are!

For example:

#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

…
In [this] first pattern, the reflection is across a vertical line between two columns; arrows on each of the two columns point at the line between the columns:

123456789
    ><   
#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.
    ><   
123456789

In this pattern, the line of reflection is the vertical line between columns 5 and 6.

Ada solution

I really like this solution, which relies on quantified expressions.

   function Detect_Horizontal_Axis (M : Map) return Axis_Of_Symmetry is
   begin
      for Row in 2 .. M'Last (1) loop
         if (for all Offset in 1 .. Natural'Min (Row - 1, M'Last (1) - Row + 1) =>
              (for all Col in 1 .. M'Last (2) =>
                 M (Row - Offset, Col) = M (Row + Offset - 1, Col)))
         then
            return Axis_Of_Symmetry'(Valid => True, Value => Row - 1);
         end if;
      end loop;
      return Axis_Of_Symmetry'(Valid => False);
   end Detect_Horizontal_Axis;

Rust solution

Lots of qualified iteration.

fn detect_horizontal_axis(map: &Map) -> Option<usize> {
    (0..map.rows)
        .skip(1)
        .find(|row| {
            (1..=*row.min(&(map.rows - row))).all(|offset| {
                (0..map.cols).all(|col| {
                    map.values[row - offset][col]
                        == map.values[row + offset - 1][col]
                })
            })
        })
}

Comments and thoughts

1. Both were formatted with “standard” formatters, so someone influential thinks this is how these programs should look. … well, mostly: I reformatted the resulting Ada slightly for a better apples-to-apples comparison. (removed blank lines, combined a couple of lines into one)
2. The Ada code used a 2-dimensional array with indefinite ranges for the Map type. Rust doesn’t allow indefinite array ranges, and map sizes varied in the problem, so I opted for a type with fields for the map (a vector of vectors) and its dimensions.
3. Rust’s functional approach was harder to debug than a for-based approach in either Ada or Rust. I couldn’t get good debug information easily.
4. I had to debug, because I had mis-translated the array indices. Like most languages, Rust insists that you index an array or vector over one and only one type; in this case, usize, or, 0..some_ginormous_number.
5. That said, Rust’s functional approach was easier to debug than Ada’s expressions, because I can embed println!'s in the former, but as far as I can tell I cannot embed Put_Lines in the latter.
6. Subjective, but: I find the Ada more readable. Lots of little things, but the pain points in reading the Rust were: dereferencing borrowed values, having to specify that, yes, I do indeed want the right endpoint of a range (=*row.min...), and using .all(...) instead of for all ... => ..., etc.

As usual, Part 2 twists Part 1 into a new direction.

Upon closer inspection, you discover that every mirror has exactly one smudge: exactly one . or # should be the opposite type.

In each pattern, you’ll need to locate and fix the smudge that causes a different reflection line to be valid. (The old reflection line won’t necessarily continue being valid after the smudge is fixed.)

Here’s the above example again:

#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

…
The first pattern’s smudge is in the top-left corner. If the top-left # were instead ., it would have a different, horizontal line of reflection:

1 ..##..##. 1
2 ..#.##.#. 2
3v##......#v3
4^##......#^4
5 ..#.##.#. 5
6 ..##..##. 6
7 #.#.##.#. 7

Original Ada solution

I didn’t find an easy way to use quantified expressions. More on that below!

function Find_Horizontal_Axis (M : Map) return Axis_Of_Symmetry is
begin
   for Row in 2 .. M'Last (1) loop
      declare
         Result                    : Axis_Of_Symmetry;
         Number_Of_Inconsistencies : Natural := 0;
      begin
         for Offset in
           1 ..
             Natural'Min
               (Row - 1,
                M'Last (1) - Row + 1) when Number_Of_Inconsistencies <= 1
         loop
            for Col in 1 .. M'Last (2) loop
               if M (Row - Offset, Col) /= M (Row + Offset - 1, Col) then
                  Number_Of_Inconsistencies := @ + 1;
                  if Number_Of_Inconsistencies = 1 then
                     --  we have at least one location that does not reflect
                     Result := (Valid => True, Value => Row - 1);
                  else
                     --  alas, we have two locations that do not reflect
                     exit;
                  end if;
               end if;
            end loop;
         end loop;
         if Number_Of_Inconsistencies = 1 then
            return Result;
         end if;
      end;
   end loop;
   return Axis_Of_Symmetry'(Valid => False);
end Find_Horizontal_Axis;

Rust solution

Unlike the Ada, the Rust solution is very similar to that for Part 1.

fn find_horizontal_axis(map: &Map) -> Option<usize> {
    (0..map.rows).skip(1).find(|row| {
        (1..=*row.min(&(map.rows - row))).map(|offset| {
            (0..map.cols).filter(|col| {
                map.values[row - offset][*col] != map.values[row + offset - 1][*col]
            }).count()
        }).sum::<usize>() == 1
    }).map(|(row, _)| row)

Comments and thoughts

1. Again, standard formatter, with the Ada slightly modified.
2. Both use the same types as above.
3. Here I find the Rust more readable:
   • The goal is clear from the code: “I want to .find a row that, after I .count the number of elements that differ, .sum to 1.”
     • While .map and .filter don’t appear in that sentence, they help illuminate what’s going on, and Rustaceans are very familiar with them.
     • The goal is not so immediately clear from the Ada code. It requires a bit more intellectual effort.
   • The Option type is a standard tool in Rust, so it’s clear from the signature that the client can receive either Some(row) or None. It isn’t immediately obvious the function signature in Ada that you might receive an invalid Axis_Of_Symmetry.

More expression-like Ada

As indicated in the section Questions, I wondered how the expression constructions of Ada 2012 and Ada 2022 might make this look. Preferably, clearer and more concise.

   type Inconsistency_Tracker is record
      M               : Map_Access;
      Inconsistencies : Natural;
      Index           : Positive;
   end record;

   type Offset_Tracker is record
      Tracker : Inconsistency_Tracker;
      Offset  : Positive;
   end record;

   function Add_When_Different_Col
     (Accumulator : Offset_Tracker; Col : Natural)
   return Offset_Tracker is
     (declare
         M renames Accumulator.Tracker.M;
         Row renames Accumulator.Tracker.Index;
         Offset renames Accumulator.Offset;
      begin
      (Offset => Offset,
       Tracker =>
         (M => M, Index => Row,
          Inconsistencies => Accumulator.Tracker.Inconsistencies +
            (if M (Row - Offset, Col) = M (Row + Offset - 1, Col)
            then 0
            else 1))));

   function Count_Row_Inconsistencies
     (Accumulator : Inconsistency_Tracker; Offset : Natural)
      return Inconsistency_Tracker
   is
   (Offset_Tracker'([for Col in Accumulator.M'Range (2) => Col]'Reduce
      (Add_When_Different_Col, (Accumulator, Offset))).Tracker);

   function Find_Horizontal_Axis (M : Map_Access) return Axis_Of_Symmetry is
   begin
      for Row in 2 .. M'Last (1) loop
         declare
            Reduction : constant Inconsistency_Tracker
               := [for Offset in 1 .. Natural'Min
                     (Row - 1, M'Last (1) - Row + 1) => Offset]'Reduce
                        (Count_Row_Inconsistencies,
                           (M => M, Inconsistencies => 0, Index => Row));
         begin
            if Reduction.Inconsistencies = 1 then
               return Axis_Of_Symmetry'(Valid => True, Value => Row - 1);
            end if;
         end;
      end loop;
      return Axis_Of_Symmetry'(Valid => False);
   end Find_Horizontal_Axis;

Observations

• It took quite a few hours of effort, mostly because I was learning.
• The formatting is not the default, because the language formatter in codium/vscode crashes on declare expressions as well as those of the form [for Row ... => Row]'Reduce. I tried to mimick the default formatter’s behavior, but you can blame me if the formatting is painful.
• IMHO the result is a bit easier to follow than the original, but not much – and it’s definitely arguable. I think the formatter (me mimicking the crashed formatter) made some questionable choices, and those make it harder to read.
• I would have liked to use anonymous functions in the 'Reduce expressions, much like Rust, but I think I had to separate them out, so I did (Add_When_Different_Col, Count_Row_Inconsistencies). Even though I didn’t like it, it’s better as a result.
• It ended up longer! 'Reduce expressions require an accumulator type, and I couldn’t think of a straightforward way to use a built-in type when you have to track rows, offsets, and columns. I ended up making two new types, and by my count, that’s the cause. If this weren’t a one-time use, that overhead should be negligible.
• The main difficulty turned out to be telling the reduction function which Map is being studied. I thought of several approaches:

  1. Copy each Map into the accumulator type.

     Didn’t try. Didn’t want to. Too much overhead.

  2. Use a “global”-ish variable to track the current Map.

     Worked, but I try to avoid using variables exterior to a subprogram. (FWIW Rust forbids global variables.)

  3. Nest reduction functions so they can access the current Map, index, and offset.

     Worked, and it’s not a big deal here, but reduction functions are often broadly usable. Nesting them makes them available only to the containing subprogram.

  4. Copy an 'Access to the current map into the accumulator type.

I settled on the fourth approach, but it was challenging. I had to change a vector’s element type from Map to access constant Map, as t it I couldn’t find a way to 'Access the vector’s elements within a subprogram, then pass that access to another subprogram, without hitting errors like non-local pointer cannot point to local object – which I didn’t get, since the object I was trying to point to was a parameter; i.e., not local to the subprogram.

Conclusions

If you’ve made it this far, (1) thank you! (2) Don’t forget that I wanted feedback! I’ll repeated the Questions from above:

1. Was this an inappropriate use case for declare expressions, quantified expressions, etc.?
2. Even if not, is there a more elegant solution?

But I’ll take any feedback, including: “Dood, don’t pollute our forum with language comparisons, however irenic you may intend.”

[JC001]

Thanks for the interesting comparisons. I don’t know Rust, and found your Rust examples impossible to understand. Conversely, I suspect a Rust user who doesn’t know Ada would find our Ada versions easier to understand. This is not surprising, given that Ada has an explicit design goal of emphasizing ease of reading over ease of writing. I don’t know if Rust has any explicit design goals, but that doesn’t seem to be one of them.

I only did part 1 (part 2 looked like it would not have an acceptable fun-to-effort ratio). I used an indefinite vector of String rather than a 2D array, so I used 1D array comparison rather than element-by-element comparison. If you’d done that, it would have eliminated your second for all. I used two for loops, but seeing your version made me realize that the 2nd loop could have been a for all expression. I like quantized expressions, and use them in expressions and functional situations, but it seems I tend not to think of them in imperative situations like this (had I used a function rather than a procedure that might have made the difference). I need to work on that.

As far as your part 2 solution, I find Ada 23’s reductions rather opaque, especially when combined with list comprehensions [(for I in ... => ...) aggregates] and your original version easier to understand.

“Too much overhead”: I suspect you’re mistaken. In-memory copies are very fast, and usually not significant. I have had solutions to some AoC problems that made many copies of such large data structures, and they produced their answers without uncomfortable delays. I’m not sure if it would have simplified your solution much.

[Lucretia]

@JC001

I don’t know if Rust has any explicit design goals

Be a replacement for C++.

[Micronian2]

Hi, I really enjoy reading all your posts, including this one. For #1 I think your use of the various Ada expression constructs was good. However, for #2 I agree with @JC001 that your original version was much easier to digest.

It’s really good to see a comparison done by someone who has a good amount of experience of both languages.

[OneWingedShark]

@cantanima

That said, Rust’s functional approach was easier to debug than Ada’s expressions, because I can embed println!'s in the former, but as far as I can tell I cannot embed Put_Lines in the latter.

Try this:

Generic
   Type Result(<>) is private;
   with Function Image(Object : Result) return String is <>;
Function Debug_Value( Object : Result ) return Result;
----
Function Debug_Value( Object : Result ) return Result is
  Text : String renames Image( Object );
Begin
   Return Value : Result := Object is
     Ada.Text_IO.Put_Line( Text );
   End return;
End Debug_Value;

[cantanima]

Thanks to everyone for the great replies!

@JC001

I don’t know Rust, and found your Rust examples impossible to understand. Conversely, I suspect a Rust user who doesn’t know Ada would find our Ada versions easier to understand.

I agree with the second sentiment. I can’t agree or disagree with the first because I’ve been working with Rust for more than 2 years now.

But I’m definitely sympathetic to it, and this exercise has surprised me: in general, I find the Ada both easier to read and often enough easier to write. I do wonder if that’s because I’m starting from the Ada and then translating to Rust, or if it’s because my first real class on programming was in Pascal, and after the relative sanity and good training that language gives you, teaching myself C for a job was traumatic. I’ve never come to like C or its derivatives; there seems to be a devil-may-care attitude with pointers that extends even to Java, whereas Kotlin and Rust are pretty nice despite their similarities to C syntax.

@JC001

I don’t know if Rust has any explicit design goals, but that doesn’t seem to be one of them.

I think it does, but the closest “explicit” statement I’ve seen several times is this, both on the home page and on this roadmap: (emphasis in original)

Rust’s goal is to empower everyone to build reliable and efficient software.

That doesn’t strike me as very precise, though.

Also on the home page is a list of these three characteristics of /rationales for the language:

• Performance
• Reliability
• Productivity

…so, yeah, “Readability” is not one of them. I’d try to defend it by saying it’s more readable than C or C++, but that’s a really low bar.

To be fair once I get into the syntax I generally find Rust pretty easy to follow, though things like ..=* are a pain.

@JC001

I used an indefinite vector of String rather than a 2D array, so I used 1D array comparison rather than element-by-element comparison. If you’d done that, it would have eliminated your second for all.

You’re right, of course. Shoulda thunka that myself, especially as I have done that elsewhere, and was delighted that I could do it in Ada.

@JC001

I find Ada 23’s reductions rather opaque, especially when combined with list comprehensions [(for I in ... => ...) aggregates] and your original version easier to understand.

In the immediate afterglow of succeeding at my task, I was rather pleased with that code, but the more I look at it, the more I agree with you.

I was thinking earlier today that a rethink might help, but I don’t know if I’ll get to that. I’m of a mind to move to Day 14 in Rust.

@JC001

“Too much overhead”: I suspect you’re mistaken. In-memory copies are very fast, and usually not significant.

Certainly in the case of small matrices like this.

@Lucretia

@JC001

I don’t know if Rust has any explicit design goals

Be a replacement for C++.

Influential members of the C++ community aspire to replace C++. They’re even talking about safety being a design goal. Alas, the idea is to replace it with more C++.

@OneWingedShark

Try this:

Ah, I see! Thanks, I will try to store that somewhere useful.

[zertovitch]

Looks like a good advertisement for Ada

[waleedmebane]

I’m new to Ada, and I’ve also written very little Rust, but I know C++ and OCaml. This post is very informative. I just have to take some time to understand it, and I’m sure I will learn a lot from it!

[cantanima]

@all

I’m working day 14 in Rust, and I just thought of a couple of important qualifiers to this whole discussion:

1. I’m translating an algorithm first implemented in Ada to Rust, and while I’m trying to use idiomatic Rust, I suppose it’s possible that, were I to start in Rust, I might land on a different algorithm (for whatever reason) or write it differently. In particular, …

2. …while I’ve made an effort to use Rust’s qualified iterators, one doesn’t have to do that. As noted above, both solutions could be implemented in Rust using more traditional for-loop notation. My impression from my team & from what I’ve read (including hints from clippy, the most common Rust linter) is that qualified iterators are idiomatic as long as they convey the meaning clearly.

   In other words, there’s a good argument to be made that I’m not actually writing idiomatic Rust.

That said, I did poll my coworkers the other day, showing them the two Rust solutions I had written for day 13. For reference, I’ll include them below, but in short: everyone who replied was unanimously in favor of the qualified iterator approach (sample size: 4, so obviously not representative of the entire Rust community, but at least two of my coworkers have been die-hard Rustaceans for years).

Via for loops

    for row in 1..map.rows {
        let mut has_symmetry = true;
        for offset in 1..=row.min(map.rows - row) {
            has_symmetry = true;
            if (0..map.cols).any(|col| {
                map.values[row - offset][col]
                    != map.values[row + offset - 1][col]
            }) {
                has_symmetry = false;
                break;
            }
        }
        if has_symmetry {
            return Some(row);
        }
    }
    None

Qualified iterators

(For the sake of accuracy, I’m including the version in the survey, which is less streamlined than the version above, but otherwise identical.)

    map.values
        .iter()
        .enumerate()
        .skip(1)
        .find(|(row, _)| {
            (1..=*row.min(&(map.rows - row))).all(|offset| {
                (0..map.cols).all(|col| 
                map.values[row - offset][col] == map.values[row + offset - 1][col])
            })
        })
        .map(|(row, _)| row)

[zertovitch]

Wow! It will be fun in a couple of years to decypher legacy Rust code…

[JC001]

@cantanima

I find the Ada both easier to read and often enough easier to write. I do wonder if that’s because I’m starting from the Ada and then translating to Rust,

Normally, if you do a project in X and then repeat it in Y, the experience you gained from the first attempt makes the second attempt easier. If you’re doing them first in Ada and then in Rust, and still find it easier in Ada than in Rust, then I think that says something significant about the languages, if only that they’re so dissimilar that doing it in Ada doesn’t teach you anything useful for doing it in Rust.

Too bad you didn’t do some of them in Rust first.

@cantanima

@JC001

I used an indefinite vector of String rather than a 2D array, so I used 1D array comparison rather than element-by-element comparison. If you’d done that, it would have eliminated your second for all.

You’re right, of course. Shoulda thunka that myself, especially as I have done that elsewhere, and was delighted that I could do it in Ada.

I wasn’t finding fault with your approach; it makes finding a vertical axis simpler. I was just trying to establish an equivalent comparison between the two to use in what I said next.