Thread overview
Halp! type system (__expand_field_0 error), compile time/runtime questions (AoC-2017 puzzle spoilers inside)
Dec 14
aliak
Dec 14
aliak
Dec 14
aliak
Dec 15
aliak
December 14
Warning: following has Advent of Code 2017 (day 14 and day 10) spoilers incase you are doing those challenges. And apologies for the slightly long post, I'm unsure how much information is needed here and am a bit clueless. Any help would be much appreciated.

=====

Ok, so I'm trying to get through these daily code puzzles with D. Most of my troubles so far have come from trying to coax the type system in to behaving how I want/expect, and parsing input data at compile time. My background is a fair amount of C++ in the past, and these days Swift (just incase it helps with explaining things)

(fun little tidbit, we're a decent size group at work doing these challenges in many languages and D is usually second in performance after C! :) - other contenders include python, go, scala, scheme, elixr, elm, javascript, fortran(!), kotlin, and quite a few more - one nut job actually decided to do a different language every day this month)

So for executing each of these puzzles (they all have two parts) I have the following setup:

app.d:

  import _day14;
  enum data = process(import("day14.txt")); // load input file
  void main() { solveA(data); solveB(data) }

So input processing is compile time, and solutions are executed at runtime (i think?). Today's problem involves a custom hash function that was developed on day 10 of the calendar.

So in my "_14.d" file I have this at the top:

  // takes a string, hashes it and returns 32 character hex string
  module _14;
  import _10: knotHashHex = solveB;

Today's problem requires this hex string to be converted in to binary (i.e. each hex char to 4 binary chars) - I am aware that an optimization here would be to use bits instead of chars but meh :p. So I have this defined:

  // Takes "af49cb351fa..." -> "0010010111011..."
  alias knotHash = (string input)
    => knotHashHex(input)
        .map!binary // converts a dchar to a binary string so 'f' -> "1111"
        .join;

So my app first calls "process" on the input data (which is a random string for today) and then the output of that goes in to solveA and solveB of my day14 module. My "process" function for today is this:

  // size "immutable size = 128;"
  // The puzzle requires a 128x128 grid of 1's and 0's so we reuse the input string
  //   each round and just append a "-i" to it.
  auto process(string input) {
    return size
        .iota
        .map!(i => input ~ "-" ~ i.text)
        .array
        .map!knotHash
  }

So the output type of this function is:
  MapResult!(function (string input) => join(map(solveB(input))), string[])

My solveA part works fine, you're supposed to count the number of 1's in the grid so it's a simple:

  auto solveA(ReturnType!process grid) {
    return grid
        .join
        .count!q{a == '1'};
  }

The next part is where I start to have problems. It involves a recursive depth-first-search approach so I have a function that recurses:

  void visit(ref string[] grid, int i, int j, ref bool[size][size] visited) {
    // check stuff and call visit again
  }

And my solveB looks like this:

  auto solveB(ReturnType!process grid) {
    auto arrayGrid = grid.array; // convert to string[]
    // more code then at some point I call:
    visit(arrayGrid, i, j, visited);
  }

So up to here everything works. But now I don't like that I have a "grid.array" inside solveB but not in solveA. Seems asymmetrical. So I figured I could just change my "process" function above to return an array directly by just adding a ".array" to the pipeline.

Then I get this error:

  Error: couldn't find field __expand_field_0 of type ulong in Tuple(0LU, 117)

117 is the ascii code for 'u' btw, which happens to be the first character in my random input string. This error is coming from inside my day 10's "solveB" function (which is imported in day 14 as "knotHashHex"). It comes from here:

  int[] rotate(int[] list, int[] lengths) {
    auto range = list.cycle;
    foreach (skip, length; lengths.enumerate) { // <-- here is error
      //  do stuff to range
    }
    return list;
  }

So it says something about ulong and expanding a tuple type. But I'm having a hard time with this error message.

Questions: What does it mean? It can't expand field 0 (the ulong) in to my skip variable? Why not? And most importantly, why is it having trouble here during my "process" function, but not screaming when I call "grid.array" in my "solveB" function? What am I doing wrong?

So anyway, Halp!


December 14
On Thursday, 14 December 2017 at 15:28:22 UTC, aliak wrote:
>   int[] rotate(int[] list, int[] lengths) {
>     auto range = list.cycle;
>     foreach (skip, length; lengths.enumerate) {
>       //  do stuff to range
>     }
>     return list;
>   }

Ok srsly, I got things to at least compile by changing the above rotate function to use a for loop instead lengths.enumerate:

  int[] rotate(int[] list, int[] lengths) {
    auto range = list.cycle;
    for (int skip = 0; skip < lengths.length; ++skip) {
         // do stuff to range
    }
    return list;
  }

uhh ... ??
December 14
On 12/14/17 10:28 AM, aliak wrote:
> Then I get this error:
> 
>    Error: couldn't find field __expand_field_0 of type ulong in Tuple(0LU, 117)
> 
> 117 is the ascii code for 'u' btw, which happens to be the first character in my random input string. This error is coming from inside my day 10's "solveB" function (which is imported in day 14 as "knotHashHex"). It comes from here:
> 
>    int[] rotate(int[] list, int[] lengths) {
>      auto range = list.cycle;
>      foreach (skip, length; lengths.enumerate) { // <-- here is error
>        //  do stuff to range
>      }
>      return list;
>    }
> 
> So it says something about ulong and expanding a tuple type. But I'm having a hard time with this error message.
> 
> Questions: What does it mean? It can't expand field 0 (the ulong) in to my skip variable? Why not? And most importantly, why is it having trouble here during my "process" function, but not screaming when I call "grid.array" in my "solveB" function? What am I doing wrong?
> 

So enumerate returns as its element type a Tuple. Specifically, it's going to be a Tuple!(size_t, int), since you are enumerating an array of ints.

I'm not sure why you are having the error, compiling your code above works perfectly fine for me. It would help to know:

a) which version of the compiler you are using?
b) if the above actually does compile for you, what is the minimal code that does not?

All that aside, you may not realize, this works as well:

foreach(skip, length; lengths)

as arrays have special treatment in the compiler.

-Steve
December 14
On Thursday, 14 December 2017 at 16:38:26 UTC, Steven Schveighoffer wrote:
> So enumerate returns as its element type a Tuple. Specifically, it's going to be a Tuple!(size_t, int), since you are enumerating an array of ints.
>
> I'm not sure why you are having the error, compiling your code above works perfectly fine for me. It would help to know:
>
> a) which version of the compiler you are using?

Tried with dmd v2.077.1. Also with LDC 1.6 (which uses dmd v2.076.1)

> b) if the above actually does compile for you, what is the minimal code that does not?

Yes of course, here's a minimal program that does not compile for me:

  import std.stdio, std.algorithm, std.range, std.array;

  int rotate(int[] lengths) {
    foreach(skip, length; lengths.enumerate) {}
    return 0;
  }

  auto knotHash(string input) {
    return [1].rotate();
  }

  auto data = ["string"]
    .map!knotHash
    .array;

  void main() {}


The above code, however, will compile with any of the following changes, and I don't understand why for any of them:
1) remove .enumerate
2) move the auto data inside the body of main
3) remove the call to .array

> All that aside, you may not realize, this works as well:
>
> foreach(skip, length; lengths)

Sweet, thanks! Yeah that works too.

Another thing I realized is that if I switch from .enumerate to the foreach you suggest (in my non minimized example) the compile time increases by A LOT. From about 1 second to 70 seconds.


December 14
On 12/14/17 5:56 PM, aliak wrote:
> On Thursday, 14 December 2017 at 16:38:26 UTC, Steven Schveighoffer wrote:
>> b) if the above actually does compile for you, what is the minimal code that does not?
> 
> Yes of course, here's a minimal program that does not compile for me:
> 
>    import std.stdio, std.algorithm, std.range, std.array;
> 
>    int rotate(int[] lengths) {
>      foreach(skip, length; lengths.enumerate) {}
>      return 0;
>    }
> 
>    auto knotHash(string input) {
>      return [1].rotate();
>    }
> 
>    auto data = ["string"]
>      .map!knotHash
>      .array;
> 
>    void main() {}
> 

Ahh. So the difference you were missing is that when you assign a static global an initializer, that initializer is evaluated at *compile time* using CTFE. That is, your entire algorithm is executed at compile-time, and at runtime you just see the final results as an array.

If you assign it inside a function, it's done at runtime.

So the CTFE interpreter doesn't like something to do with your chain of ranges. This is not totally unexpected, as the CTFE engine has lots of quirks that make it sometimes puke on valid CTFE-able code.

To answer your questions below:

> 
> The above code, however, will compile with any of the following changes, and I don't understand why for any of them:
> 1) remove .enumerate

enumerate is probably the culprit. I think possibly CTFE doesn't properly handle Tuples correctly.

> 2) move the auto data inside the body of main

This makes it run at runtime, not compile-time.

> 3) remove the call to .array

And this is even more interesting :) Map is lazy, so what you have done when you remove the array call is generate a map struct, and assign it to data. This means that it didn't actually run enumerate or knotHash at all! It just has a struct with a string "string" in it, and is ready to run knotHash as soon as you want to iterate it. This is why it doesn't fail in this case.

When .array is present, it evaluates all the elements in the range eagerly, therefore running everything at compile time, and reaching the error with enumerate that CTFE cannot handle something.

> 
>> All that aside, you may not realize, this works as well:
>>
>> foreach(skip, length; lengths)
> 
> Sweet, thanks! Yeah that works too.
> 
> Another thing I realized is that if I switch from .enumerate to the foreach you suggest (in my non minimized example) the compile time increases by A LOT. From about 1 second to 70 seconds.

CTFE has a really ...interesting property that it never mutates data. So every loop, it allocates another integer, for instance. Most of the time, if a D program is taking a long time compile, it's using a lot of CTFE (see just about every dconf talk about how CTFE being slow sucks :)

This makes it really really bad at looping over large sets of data. Stefan Koch is working on fixing a lot of the problems with CTFE.

Note that I don't think enumerate is any faster in CTFE, either that 1 second means that it is the lazy version (which doesn't really do much at compile-time), or it is the version that doesn't compile.

At this time, I'd recommend doing your task at runtime anyway. Hopefully I have shed some more light on how things are working here.

-Steve
December 15
On Friday, 15 December 2017 at 01:43:04 UTC, Steven Schveighoffer wrote:
> So the CTFE interpreter doesn't like something to do with your chain of ranges. This is not totally unexpected, as the CTFE engine has lots of quirks that make it sometimes puke on valid CTFE-able code.

:(

> At this time, I'd recommend doing your task at runtime anyway. Hopefully I have shed some more light on how things are working here.
>
> -Steve

Hah yeah, I'll have to switch to runtime for quite a few of the tasks. But yes you've explained everything! thanks a lot for taking the time :) I guess I'll report the issue with enumerate since maybe it's something that should be fixed eventually.