Any SML coders able to translate this to Python?

[Marko Rauhamaa]

Chris Angelico <rosuav at gmail.com>:

> On Thu, Sep 6, 2018 at 2:29 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>> Marko Rauhamaa <marko at pacujo.net> (Marko Rauhamaa):
>>> Steven D'Aprano <steve+comp.lang.python at pearwood.info>:
>>>> I have this snippet of SML code which I'm trying to translate to Python:
>>>>
>>>> fun isqrt n = if n=0 then 0
>>>>              else let val r = isqrt (n/4)
>>>>                   in
>>>>                     if n < (2*r+1)^2 then 2*r
>>>>                     else 2*r+1
>>>>                   end
>>> [...]
>>> You must make sure "r" doesn't leak outside its syntactic context so:
>>>
>>> def isqrt(n):
>>>     if n == 0:
>>>         return 0
>>>     else:
>>>         def f2398478957():
>>>             r = isqrt(n//4)
>>>             if n < (2*r+1)**2:
>>>                 return 2*r
>>>             else:
>>>                 return 2*r+1
>>>         return f2398478957()
>>
>> Actually, this is a more direct translation:
>>
>>    def isqrt(n):
>>        if n == 0:
>>            return 0
>>        else:
>>            def f2398478957(r):
>>                if n < (2*r+1)**2:
>>                    return 2*r
>>                else:
>>                    return 2*r+1
>>            return f2398478957(isqrt(n//4))
>>
>
> I don't understand why you created that nested function instead of
> something simple like renaming the variable. Is there a difference
> here?

Yes, in understanding the semantics of "let."

"let" is used to introduce local bindings in some functional programming
languages. I must admit I'm not fully versed in ML but it looks like the
analogue in Lisp variants. This is how the above function would be
written in Scheme:

   (define (isqrt n)
      (if (= n 0)
          0
          (let ((r (isqrt (quotient n 4))))
            (if (< n (expt (1+ (* 2 r)) 2))
                (* 2 r)
                (1+ (* 2 r))))))

Now, Lisp's "let" can be implemented/defined using "lambda":

   (let ((X A) (Y B) ...) . BODY)

   =>

   ((lambda (X Y ...) . BODY) A B ...)

which gives us:

   (define (isqrt n)
      (if (= n 0)
          0
          ((lambda (r)
            (if (< n (expt (1+ (* 2 r)) 2))
                (* 2 r)
                (1+ (* 2 r))))
           (isqrt (quotient n 4)))))

Python does have a limited form of "lambda" and even a conditional
expression so--as others have mentioned--this particular function could
be translated pretty directly into Python using its lambda.

More generally and idiomatically, though, Python's functions are named.
So that explains the version I give above.


Marko