CPS Transformation [Scala] - PullRequest
Новая
       23

CPS Transformation [Scala]

0 голосов
/ 26 июня 2018

Я пытаюсь преобразовать некоторые функции в CPS в Scala, используя примеры, которые я нашел в Интернете на других языках.

У нас была только одна лекция по CPS, и все должно быть очень просто, но все же я не совсем понимаю, как правильно выполнять преобразования.

Это примеры, которые я нашел в Интернете, и я пытаюсь сделать это в Scala. 

pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)

add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)

sqrt' :: Float -> ((Float -> a) -> a)
sqrt' a = \cont -> cont (sqrt a)

pyth' :: Float -> Float -> (Float -> a) -> a
pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\anb -> sqrt' anb cont)))

Теперь я начал с pow2 ', который выглядит так: 

def pow2_k(a:Float, k:(Float => Float)) : Float =
    (a*a)

def pow2_cont(n: Float) = pow2_k(n, (x: Float) => x)

Сначала у меня было k(a*a) вместо простого (a*a), что привело к странным результатам.

Затем я попытался добавить ', который на данный момент выглядит следующим образом: 

def add_k(a:Float, b:Float, k:(Float, Float => Float)) : Float =
    (a+b)

def add_k_cont(n:Float,m:Float) = add_k(n,m (x: Float, y:Float => (n+m)))

Это явно неправильно. У меня проблемы с написанием правильного продолжения. Кто-нибудь знает хороший сайт, бумагу, видео и т. Д., Который объясняет преобразование CPS и продолжения? Большинство из найденных мной либо слишком короткие и без примеров, либо слишком сложные. Я чувствую, что это не так сложно для этих простых функций, которые я пытаюсь преобразовать ...

Спасибо.

1 Ответ

0 голосов
/ 26 июня 2018 
def pow2_k[A](f: Float, k: Float => A): A = k(f * f)

def pow2_cont(n: Float): Float = pow2_k(n, identity)

scala> pow2_cont(2.0f)
res0: Float = 4.0

scala> pow2_k(4.0f, println)
16.0

Вероятно, самый простой способ представить преобразование CPS - это:

  • Возьмите функцию, которой нет в CPS 

    def square(f: Float): Float = f * f

  • Сделать функцию универсальной в типе A; добавить второй параметр функции из типа результата вашей старой функции в A; и измените тип результата вашей функции на A

    def cpsSquare[A](f: Float, ret: Float => A): A = ???

  • Везде, где ваша функция «возвращала» значение (обратите внимание, конечно, что return в Scala имеет странную семантику, так что return - это действительно плохой запах кода), передавайте это значение, которое будет возвращено функции (что я назвал эту функцию ret намекает на то, что происходит) 

    def cpsSquare[A](f: Float, ret: Float => A): A = ret(f * f)

По сути, в CPS вместо возврата значения вы вызываете переданную функцию (продолжение) со значением, которое возвращаете.

...