From book ‘Learning Concurrent Programming In Scala’:
“The declarative programming style is increasingly common in sequential programming too.
Languages such as Python, Haskell, Ruby, and Scala express operations on their collections
in terms of functional operators and allow statements such as filter all negative integers from
this collection. This statement expresses a goal rather than the underlying implementation,
allowing to it easy to parallelize such an operation behind the scene.”
How does this style help writing more parallel programs?
Briefly, it is easy to see what can be parallelized, indeed order dependent definitions are unrepresentable.
For example, in fully declarative scala code
lazy val c = a + b
lazy val a = 1
lazy val b = 2
println(c) // 3
We cannot make the mistake of computing c before a and b as it makes no sense. On the other hand, if we had
var a = 1
var b = 2
var c = a + b
var b = 4 // evil operation
println(c) // 5
we can reverse the last two operations and get a perfectly valid definition but the wrong result.
2 Likes
At the risk of repeating what has been explained many times before …
More in detail, here is some code both at the language level and library level.
It is instructive to read the comments.
Warning somewhat advanced library level code
object SeqAndParApp extends App {
//
// language level meaning (fixed)
//
// first z and then y
{
val z = 1
val y = 2
val x = z + y + 1
val res0 = x
println(s"res0 == $res0")
}
// first y and then z
{
val y = 2
val z = 1
val x = z + y + 1
val res1 = x
println(s"res1 == $res1")
}
// think of z and y together (not really true)
{
val (z, y) = (1, 2)
val x = z + y + 1
val res2 = x
println(s"res2 == $res2")
}
// think of z and y together (not really true)
{
val (y, z) = (2, 1)
val x = z + y + 1
val res3 = x
println(s"res3 == $res3")
}
// first z and then y
{
val z = 1
val y = z + 1
val x = z + y + 1
val res4 = x
println(s"res4 == $res4")
}
// does not compile
// // first y and then z
// {
// val y = z + 1
// val z = 1
// val x = z + y + 1
// val res5 = x
// println(s"res5 == $res5")
// }
//
// library level level meaning (flexible)
//
// Warning: uses advanced Scala features!!!
import scala.language.higherKinds
//
// type classes
//
trait Res[M[+ _]] {
def res[Z](z: Z): M[Z]
}
trait Par[M[+ _]] {
// independent composition
// allows an implementation exploiting parallelism
def par[Z, Y](mz: M[Z])(my: M[Y]): M[(Z, Y)]
}
trait Seq[M[+ _]] extends Res[M] with Par[M] {
// dependent composition
// does not allow an implementation exploiting parallelism
def seq[Z, Y](mz: M[Z])(z2my: Z => M[Y]): M[Y]
// Seq is
// - more powerful than Par
// - less flexible than Par
override def par[Z, Y](mz: M[Z])(my: M[Y]): M[(Z, Y)] =
seq(mz) { z =>
seq(my) { y =>
res((z, y))
}
}
}
//
// corresponding operators
//
object ops {
implicit class ParOp[M[+ _]: Par, Z](mz: M[Z]) {
def par[Y](my: M[Y]): M[(Z, Y)] = implicitly[Par[M]].par(mz)(my)
}
implicit class SeqOp[M[+ _]: Seq, Z](mz: M[Z]) {
def seq[Y](z2my: Z => M[Y]): M[Y] = implicitly[Seq[M]].seq(mz)(z2my)
}
}
//
// Id example
//
case class Id[+Z](value: Z)
implicit object idSeq extends Seq[Id] {
override def res[Z](z: Z): Id[Z] =
Id(z)
// implementation
// does nothing in parallel
// but
// an implementation is possible (e.g. using actors) that
// does things in parallel
override def par[Z, Y](iz: Id[Z])(iy: Id[Y]): Id[(Z, Y)] =
Id((iz.value, iy.value))
override def seq[Z, Y](iz: Id[Z])(z2iy: Z => Id[Y]): Id[Y] =
z2iy(iz.value)
}
import idSeq._
import ops._
//
// examples 2, 3, 4 and 5 revisited
//
{
val res2: Id[Int] =
res(1) par res(2) seq { case (z, y) => // val (z, y) = (1, 2)
res(z + y + 1) seq { x => // val x = z + y + 1
res(x) // x
}
}
println(s"res2 == $res2")
}
{
val res3: Id[Int] =
res(2) par res(1) seq { case (y, z) => // val (y, z) = (2, 1)
res(z + y + 1) seq { x => // val x = z + y + 1
res(x) // x
}
}
println(s"res3 == $res3")
}
{
val res4: Id[Int] =
res(1) seq { z => // val z = 1
res(z + 1) seq { y => // val y = z + 1
res(z + y + 1) seq { x => // val x = z + y + 1
res(x) // x
}
}
}
println(s"res4 == $res4")
}
// does not compile
// {
// val res5: Id[Int] =
// res(z + 1) seq { y => // val y = z + 1
// res(1) seq { z => // val z = 1
// res(z + y + 1) seq { x => // val x = z + y + 1
// res(x) // x
// }
// }
// }
// println(s"res5 == $res5")
// }
}
1 Like
xs.filter(...) is serial, xs.par.filter(...) is parallel, done.
whereas in Java < 1.8, before we had streams and operations like filter, we wrote (pseudocode):
List result = new List;
for(x : xs) {
if(!f(x)) result.add(x);
}
return result;
there’s no simple way to parallelize this. for in Java is always a serial loop (unlike for in Scala which desugars into method calls, and we’re free to make those method calls do what we want).
2 Likes