Sort function with sfc random numbers fails with optimizations enabled

[Caid11]

The following code works with -O0, but fails at -O1 and above:

import std/core/undiv

import std/num/int32
import std/num/random

// Taken from https://github.com/koka-community/std
fun sort(l: list<a>, ?cmp: (a, a) -> e order): e list<a>
  match l
    Nil -> Nil
    Cons(h, Nil) -> Cons(h, Nil)
    Cons(pivot, rst) -> 
      val (smaller, greater) = rst.partition fn(it) { cmp(it, pivot) == Lt }
      return sort(smaller.pretend-decreasing) ++ Cons(pivot, sort(greater.pretend-decreasing))

// fun sort(l: list<a>, ?cmp: (a, a) -> e order): <div|e> list<a>
//   match l
//     Nil -> Nil
//     Cons(h, Nil) -> Cons(h, Nil)
//     Cons(pivot, rst) -> 
//       val (smaller, greater) = rst.partition fn(it) {
//         mask<div>
//           cmp(it, pivot) == Lt
//         }
//       return sort(smaller) ++ Cons(pivot, sort(greater))

// Generate a shuffled list of numbers from 0 to input size - 1
fun shuffle(l: list<a>, seed : int) : _e list<a>
  var rnd-state := sfc-init(seed)

  l.map(fn(n) 
    val rnd-step = rnd-state.sfc-step()
    rnd-state := rnd-step.rstate()
    val arg = rnd-step.rnd()
    //(n, 1.int32)
    (n, arg)
  )
    .sort(?cmp=fn((_,x : int32), (_,y : int32)) int32/cmp(x, y))
    .map(fn((x,_)) x)

fun main()
  val l = list(1,10).shuffle(1)
  println(l[0])

The error is:

command failed:
 ".koka/v3.1.3/clang-cl-drelease-37622a/main__main"

Eliminating pretend-decreasing (which the docs state is unsafe) doesn't solve the issue. Interestingly, if I switch shuffle so it doesn't use the result of rnd-step.rnd, the failure goes away. Removing the call to sort also fixes the failure, so I suspect the issue is happening because of some interaction between the two.

My configuration's details:

• OS: Windows 11
• Compiler: clang version 18.1.8
• Koka version: source build at dev commit 70f5609

[Caid11]

I found it also fails with an xorshift implementation, so it's unlikely that the problem is with sfc:

import std/core/undiv

import std/num/int32

struct xorshiftState
  a : int32

fun step( s : xorshiftState ) : xorshiftState
  val x1 = s.a.or( s.a.shl( 13 ) )
  val x2 = x1.or( x1.shr( 17 ) )
  val x3 = x2.or( x2.shl( 5 ) )
  XorshiftState( x3 )

// Taken from https://github.com/koka-community/std
fun sort(l: list<a>, ?cmp: (a, a) -> e order): e list<a>
  match l
    Nil -> Nil
    Cons(h, Nil) -> Cons(h, Nil)
    Cons(pivot, rst) -> 
      val (smaller, greater) = rst.partition fn(it) { cmp(it, pivot) == Lt }
      return sort(smaller.pretend-decreasing) ++ Cons(pivot, sort(greater.pretend-decreasing))

// fun sort(l: list<a>, ?cmp: (a, a) -> e order): <div|e> list<a>
//   match l
//     Nil -> Nil
//     Cons(h, Nil) -> Cons(h, Nil)
//     Cons(pivot, rst) -> 
//       val (smaller, greater) = rst.partition fn(it) {
//         mask<div>
//           cmp(it, pivot) == Lt
//         }
//       return sort(smaller) ++ Cons(pivot, sort(greater))

// Generate a shuffled list of numbers from 0 to input size - 1
fun shuffle(l: list<a>, seed : int) : _e list<a>
  var rnd-state := XorshiftState( seed.int32 )

  l.map(fn(n) 
    rnd-state := rnd-state.step()
    (n, rnd-state.a)
  )
    .sort(?cmp=fn((_,x : int32), (_,y : int32)) int32/cmp(x, y))
    .map(fn((x,_)) x)

fun main()
  val l = list(1,10).shuffle(1)
  println(l[0])

[TimWhiting]

I've noticed that clearing the build folder (.koka) and rebuilding causes this problem to go away on the first recompile. This makes me think that it has something to do with the incremental building / interface files and maybe the inline specialization.

[daanx]

Strange -- maybe use pub fun main ? I'll look into it soon.