The Crystal Programming Language Forum

Compiler issue with non-existent NIL conditions

There is a bug, or an improvement, depending on how you want to see it.

This:

def foo
  (2..).each do |x|
    return 1
  end
end

typeof(foo) # => Int32 | Nil

The bug is that for a loop that never ends, the compiler think it ends, then we get Nil in the type.

The compiler knows (2..).each { ... } will never end. It can even know that at compile time (the E in Range(B, E) is Nil, there are already some checks around that). If there’s no end, we can generate while true as a loop. Then the compiler knows the loop never ends. Then the type of foo becomes Int32.

Just replace std code with my code here and you’ll see that the code from @jzakiya start to compile without modifications: Compiler issue with non-existent NIL conditions

Maybe a bug, maybe a feature request, I don’t know. Something can be done to improve the situation.

This compiles|runs using loop do ... versus (2..).each do |pow|.
WHY?
They are functionally equivalent (to a user), but obviously not to the compiler.

def palindromegen(digit, count)
  nums = [] of UInt64
  nn  = digit * 11
  num = 0.to_u64
  pow = 1
  loop do pow += 1        # replaces: (2..).each do |pow|
    base = 10_u64**(pow >> 1)
    n1   = base * digit
    n2   = base * (digit + 1)
    n1.step(to: n2 - 1, by: 10) do |n1|
      ns = (n1 // 10).to_s
      (n1..n1 + 9).each_with_index do |pal, i|
        num = (pal.to_s + pal.to_s.reverse).to_u64      if pow.odd?
        num = (ns + "0" + ns.reverse).to_u64 + base * i if pow.even?
        nums << num if num % nn  == 0
        return nums if nums.size == count
      end
    end
  end
end

count = 20
puts "First 20 palindromic gapful numbers 100 ending with:"
(1..9).each { |digit| print "#{digit} : #{palindromegen(digit, count)}\n" }
count = 100
puts "\nLast 15 of first 100 palindromic gapful numbers ending in:"
(1..9).each { |digit| print "#{digit} : #{palindromegen(digit, count).last(15)}\n"

This also compiles|runs using (2..).select do |pow|

def palindromegen(digit, count)
  nums = [] of UInt64
  nn  = digit * 11
  num = 0.to_u64
  (2..).select do |pow|
    base = 10_u64**(pow >> 1)
    n1   = base * digit
    n2   = base * (digit + 1)
    n1.step(to: n2 - 1, by: 10) do |n1|
      ns = (n1 // 10).to_s
      (n1..n1 + 9).each_with_index do |pal, i|
        num = (pal.to_s + pal.to_s.reverse).to_u64      if pow.odd?
        num = (ns + "0" + ns.reverse).to_u64 + base * i if pow.even?
        nums << num if num % nn  == 0
        return nums if nums.size == count
      end
    end
  end
end

This also works.

def palindromegen(digit, count)
  nums = [] of UInt64
  nn  = digit * 11
  num = 0.to_u64
  pow = 1
  while true
    pow += 1
    base = 10_u64**(pow >> 1)
    n1   = base * digit
    n2   = base * (digit + 1)
    n1.step(to: n2 - 1, by: 10) do |n1|
      ns = (n1 // 10).to_s
      (n1..n1 + 9).each_with_index do |pal, i|
        num = (pal.to_s + pal.to_s.reverse).to_u64      if pow.odd?
        num = (ns + "0" + ns.reverse).to_u64 + base * i if pow.even?
        nums << num if num % nn  == 0
        return nums if nums.size == count
      end
    end
  end
end

So there’s something intrinsically different to the compiler about (2..).each.

If you don’t make an effort to understand how the language works, and why it does what it does, you will keep complaining forever.

Or even read our replies here.

That’s what we’ve been telling you all along! :-)

This is a fruitless back-and-forth because you’re not focusing on what I’m raising, as a language user.

I consider the behavior in this example of the endless range form (2..).each a bug because it doesn’t behave as I expect and as I desire it to behave!.

You don’t care that I consider it a bug, or even just undesirable behavior, so I as a user have to bear the consequences of what I consider is a poor design decision, which can be fixed.

So there’s no point for me to discuss this anymore since I figured out how to write equivalent functional code that performs as I want.

I’m pretty sure he’s agreeing with you in that regard :laughing:. And I tend to agree that this specific case could be improved.

Hey @jhass I like your struct implementation, and ran it over all the outputs examples. It has comparable speed with my version (+|- 1|2 secs), and shows off Crystal’s OOP ability. Do you mind if I post it on Rosetta Code? I’ll list you as it contributor in that thread.

BTW: I corrected a minor error in a loop: 9.times should be 10.times

Sure, consider it CC0. I hope it can inspire future solutions and show how naming is important :)

2 Likes

FYI: final version posted to Rosetta Code.

struct PalindromicGapfuls
  include Enumerable(UInt64)

  @nn : Int32

  def initialize(@digit : Int32)
    @nn = @digit * 11                    # digit gapful divisor
  end

  def each
    (2..).each do |power|
      base    = 10_u64 ** (power >> 1)  # value of middle digit position
      this_lo = base * @digit           # starting half for this digit: 10.. to  90.. 
      next_lo = base * (@digit + 1)     # starting half for next digit: 20.. to 100..
      this_lo.step(to: next_lo - 1, by: 10) do |front_half|   # d_10; d_20; d_30; ...
        if power.odd?                   # for even number of total digits: ab..ba
          front_half.upto(front_half + 9) do |upper_half|     # d_n0 to d_n9
            palindrome_half = upper_half.to_s
            palindrome = (palindrome_half + palindrome_half.reverse).to_u64
            yield palindrome if palindrome % @nn == 0
          end
        else                           # for odd number of total digits: ab..m..ba
          palindrome_half = (front_half // 10).to_s
          palindrome = (palindrome_half + "0" + palindrome_half.reverse).to_u64
          # increase palindome middle digit from ---0--- to ---9---
          10.times do
            yield palindrome if palindrome % @nn == 0
            palindrome += base
          end
        end
      end
    end
  end
end

count, keep = 20, 20
puts "First 20 palindromic gapful numbers ending with:"
1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
  
count, keep = 100, 15
puts "\nLast 15 of first 100 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
     
count, keep = 1_000, 10
puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }

count, keep = 100_000, 1
puts "\n100,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }

count, keep = 1_000_000, 1
puts "\n1,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }

count, keep = 10_000_000, 1
puts "\n10,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }

Why did you rename @gap to @nn? I agree it’s not a good name, mainly because I had no real context on what this is even solving, but better than @nn certainly. If you feel the need to explain what it is in a comment, rename the variable instead. Code is write once, read often. So from the comment, sounds like @gap_divisor or something might be a good name.

What does lo stand for? I avoid abbreviations that are not 110% clear in the context.

I’m not sure why you feel the need to choose different variable names for upper_half and palindrome_half, reassigning there does not create a union since the variable is not captured anywhere. It’s the same value, just in different representations that are never needed at the same time. I even considered to just add a .map(&.to_s) initially, but wanted to avoid allocating the two iterators.

Also actually let’s use .skip(count - keep).first(keep) and maybe extract the printing to a method instead of copy pasting it five times. The initial two variants seems different enough to keep as is, but looking at those it seems too similar too often.

In general I harmonized all 3 versions (my 2 and yours) and used names that best (to me) conceptually portrayed|explained their roles in the algorithm, and ended up using 95% of your naming conventions. @gap is misleading, and @nn better, by showing the form of the divisor for each digit (considered @dd, but eh…). Basically, I wanted to use short|concise|clear names. The comments are more important than the names, like this_lo|next_lo, which really didn’t need to be changed from n1|n2 in my original versions, because they’re only used once. Ultimately, I chose the names that made the most sense to me, and made me smile. :smiley:

Tried .skip(count - keep).first(keep) too, but it provided no performance|memory advantages I could detect, so I kept the shorter code. (Though good to know it’s doable.)

I also added the Ruby versions, which are about a 98% literal translation.

The bottom line is, this was a good learning exercise for me. I think all the versions now are much easier to comprehend, and illustrate different capabilities of Crystal|Ruby. And I’m finished with this task.