CPS (continuation passing style) in scala

[Jim Newton]

Can someone comment (or explain) how to do continuation passing style in a strongly typed language like scala?

The curious thing is that if every expression is in tail position, then no function actually returns.  

I say "actually" because according to the type inference, the return type is the disjunction of all the types of the

expressions in tail position.   However, it seems to me that if a function never returns, the the type of

the expression in tail position is not relevant. 

If I must know and declare the return value types of CPS transformed functions, doesn't that make

it impossible to write a CPS compliment program?

Two examples would be a varient of IF which takes a boolean value and two continuations, one 

to call if the boolean is true, and the other to call if the boolean is false, or a hash table accessor 

which takes a hash table, a perspective key, and two continuations, one 0-ary to call if the key is 

not found in the table, and one 1-ary to call with the value if the key is found in the table.

Perhaps this question really doesn't make sense since the JVM prohibits tail-call-optimization between 

different global functions.

[Bardur Arantsson]

On 07/26/2016 11:53 AM, Jim Newton wrote:
> Can someone comment (or explain) how to do continuation passing style in
> a strongly typed language like scala?
> The curious thing is that if every expression is in tail position, then
> no function actually returns.
> I say "actually" because according to the type inference, the return
> type is the disjunction of all the types of the
> expressions in tail position. However, it seems to me that if a
> function never returns, the the type of
> the expression in tail position is not relevant.

To indicate that a function never returns you'd use Nothing as the
return type.

Regards,

[som-snytt]

http://www.scala-lang.org/old/node/2096

http://blog.bruchez.name/2011/09/continuations-in-scala.html

https://github.com/scala/scala-continuations

[Jim Newton]

As per "Nothing", I could't figure out how to make Nothing work, but using a paramertized type seems to 

work, at least at the compiler love.

def foo[T,S](a:T, cont:T=>S): S ={
  cont(a)
}
def bar = foo(12,println)

However it seems if doesn't return the disjunction of its then and else part.  The following does't compile.

Perhaps Either is not really a disjoined type???

def foo[T,S,U](a:T, b:T=>Boolean, tcont:T=>S, econt:()=>U): Either[S,U] ={
  if ( b(a) ) tcont(a)
  else econt()
}

def bar = foo(12,println) 

[Roland Kuhn]

Hi Jim,

Scala is probably less magic than you assume: if you promise to return an Either, you’ll actually have to return something of that type—and neither S nor U have this property. Either has just two subtypes called Left and Right, so you’d wrap your true case in Left(…) and your false case in Right(…) to make it compile.

On a sidenote: Either is typically used the other way around in Scala, meaning that the error case is Left and the nominal case is Right.

And on a really tangential note, it might not make a lot of sense to try to use Scala as if it were something like Lisp, these two languages are very different—this would be especially confusing when using dot-less notation in Scala which has a completely different semantic meaning than argument lists in Lisp. Also, CPS is not possible in the style you are trying out, you’ll soon run into StackOverflowErrors due to the lack of true tailcalls on the JVM.

Regards,

Roland

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jasper-M]

You can type foo as follows. The logical thing to do when you have two values of different types and your method returns one or the other, is to have the return type be the least upper bound of both types.

def foo[T,S,U >: S](a:T, b:T=>Boolean, tcont:T=>S, econt:()=>U): U ={

  if ( b(a) ) tcont(a)

  else econt()

}

Op woensdag 27 juli 2016 17:22:26 UTC+2 schreef Jim Newton:

[Jim Newton]

That's an interesting suggestion indeed.

What's surprising, which I will probably have bad dreams about, is that the disjunction of A and B is not a supertype of A nor of B.

What I'm used to in Lisp is that if A and B are types, then (or A B) is a super type of both A and B and (and A B) is a subtype of both A and B.

Understanding these surprises is enlightening.

[Jasper-M]

I think in dotty, the future scala 3 if you will, the kind of type disjunction you want does indeed exist

Op donderdag 28 juli 2016 17:19:35 UTC+2 schreef Jim Newton:

[Naftoli Gugenheim]

You can look at the source code for Either, it's just a class in the standard library