@popovitsj Has a good inclination.
SML uses pattern matching to determine which version of the function definition to use.
fun sqrt x s = if ((s*s) <= x) then s | sqrt x s = if (s*s) > x then sqrt x (s - 1);
Is non-deterministic, and SML doesn't have the facility to backtrack and try another definition if the one it tries fails (i.e. like Prolog).
In this scenario you can just use
fun sqrt x s = if s * s <= x then s else sqrt x (s-1);
This function is logically valid only if you are passing it a value that when originally passed will fail the if expression.
I haven't tested this but I believe it should help.