Saturday, August 6, 2011

Scala tribute to SICP, Paul Henderson and... George.

Houdy, strange title. Took me time to produce something acceptable. Although not satisified of the code I decided to write something about some illustrative micro DSL I have been produced while watching some SICP lecture .As usual let us start with something completly different. Thanks to Mario Fusco and Jonas Boner for referencing my Hanoï tower article. This provided me with my fifteen minutes of fame, attracting a number of visitors very close to 5k last month.

I was quite shocked when I learnt that SICP was under attack,as I started watching the online videos a few months ago. I had the feeling of discovering again my job. Progressing step by step in the exploration of functional programming, I try to reproduce each difficult example when possible in Scala and Clojure. The Hanoi tower article came from there. Now I will take again the book and read it from start to end. The best way of protesting. I know I promised Debasish Ghosh to read the Haskell manual he suggested. I will,  it will only double my load of work, that's all. But SICP matters !!

The best medecine to cure this shock state was to provide another example that I wanted to implement for long. In lecture 3A, Hal Abelson presents some implementation of Peter Henderson's article presenting a functional geometry language allowing him to denote the structure of an Escher woodcut. Nice article, I did not understand everything. But at least I am progressing. I may not go as far as Hal Abelson, but I wanted to make a try in Scala.

The idea is to conceive some easy algebric language allowing us to express the shape of a graphic representation rather than detailing how it is built. This expression adopts the shape of an embedded language into Scala (or Clojure/Lisp etc...)
Functional programming comes to help. This is easily done if your elementary bricks are not modeled as objects but as procedures (runtime constructions of lambdas).

Imagine one moment that the most basic element of your construction would be a picture. Not an object per se as perceived in the OOP world, but the ability to proceed a rectangle zone in some graphic area (Java2D developers may see where I am going to).
The lambda definition hides the craft of drawing a category of drawings. At some point in time, a procedure will be created from the lambda, closing onto some basic draw description. Now your application knows how to draw a specific picture, whatever is your target rectangle area. This knowledge is applicable as many times as you want.

Creating well named combining functions (combinators)- in essence higher order functions manipulating other functions- one can setup an embedded language allowing for a clear expression of its intents as a combination  of higher order functions.

This is where George comes to play. Well, Georges is the graphical example provided by Harold Abelson:


In the algebraic language the following expression

beside(picture, above(empty(), picture, byHalf), byHalf)

would draw some provided pictures,  side by side in an input rectangle area, allocating half of the rectangle width to each of the picture version. The right picture is reduce by half in size, because half of the above area rectangle is empty.

The expected result would be George and and some "kid" George:



Yes I know, the syntax of the language can be improved but at least, everyone understands it. The most amusing in the above expression is that I could provide any picture to this higher order expression, and apply it to any rectangle, the behavior would be the same, the graphical result varying graphically speaking.

The only basic physical brick to my construction is the target rectangle. The following represents my rectangle abstraction:


A rectangle is made of three vectors. One representing the origin, the two others representing the horizontal and vertical directions.

Trust me when I tell you I tested the abstractions. You are going to see more tests. By the way in order not to clutter the article with too many pictures, I invite you to take some paper and reproduce the examples by hand, while reading the upcoming tests.

The abstractions involved into the rectangle reification process are

case class Rectangle (origin: Vector2D, horizontal: Vector2D, vertical: Vector2D)

case class Vector2D(x: Double, y: Double) {
  def +(other: Vector2D) = {
    Vector2D(x + other.x, y + other.y )
  }

  def * (scale: Double) = {
    Vector2D(scale * x, scale * y)
  }
}

I have extended my vector in order to add two vectors together and scale a vector when necessary. The tests are:

import org.specs2.mutable.Specification

final class TestVector2D  extends Specification{

  "A given vector " should {
    "bind its xcoordinate" in {
      Vector2D(3.0, 5.0).x must be equalTo (3.0)
    }

    "bind its ycoordinate" in {
      Vector2D(3.0, 5.0).x must be equalTo (3.0)
    }

  }

  "The addition of two vectors" should {
    " add the vectors coordinates " in {
      (Vector2D(3.0, 5.0) + Vector2D(7.0, 11.0)) must be equalTo(Vector2D(10.0, 16.0))
    }
  }

  "The scaling of a vector" should {
    " scale the  vector coordinates " in {
      (Vector2D(3.0, 5.0) * 2) must be equalTo(Vector2D(6.0, 10.0))
    }
  }
}

As I have planned to work with lines exclusively, I introduce a segment notion. A segment is defined by two vectors, one pointing to the start, the other pointing to the end:

case class Segment(start: Vector2D, end: Vector2D)

That's all. My incoming bricks are going to be functions and higher order functions. Recovering from many years of Java, I felt the need to introduce a "reference point" for the input picture to my chain of combinators. But what is a picture, if not a simple function aiming to take a rectangle as an input and draw something in it:

trait Picture extends Function1[Rectangle, Unit]

Dealing with lines, I defined a function LinearPicture, aiming to map a list of segments (a definition) into a target rectangle. Here comes the test:


import org.specs2.mutable.Specification

final class LinearPictureSpecification extends Specification{
    "Linear picture " should {
    "reproduce segment into unitary rectangle " in {
      implicit val drawer = new FakeDrawer
      val picture = LinearPicture(segments)(drawer)
      picture(inCell)
      drawer.segment must be equalTo (Segment(Vector2D(1, 1), Vector2D(2, 2)))
    }
  }

  def segments = List(Segment(Vector2D(0, 0), Vector2D(1, 1)))

  def inCell = Rectangle(Vector2D(1, 1), Vector2D(1, 0), Vector2D(0, 1))
}

The picture, will need on behalf the help of a drawer which knows how to draw physically lines, and a list of segments is provided as a definition for the graphic. Take five minutes with a paper and a pencil to reproduce the stuff. I will need a LineDrawer trait definition:

trait LineDrawer {
     def draw(segment: Segment)
}

and a little fake line drawer to trace what hes been drawn:

final class FakeDrawer extends LineDrawer{
  var segment: Segment = _

  def draw(aSegment: Segment) = segment = aSegment
}

Still with me? This is my implementation:

import com.promindis.geometry.FunctionalGeometry._

class LinearPicture(defintion: List[Segment], drawer: LineDrawer) extends Picture{

  def apply(rectangle: Rectangle) {
    val mapping = coordinateMappingIn(rectangle)
    defintion.foreach(segment =>
        drawer.draw(
          Segment(mapping(segment.start), mapping(segment.end))))
  }
}

object LinearPicture {
  def apply(defintion: List[Segment])(implicit drawer: LineDrawer): (Rectangle => Unit) = {
    new LinearPicture(defintion, drawer)
  }
}

The LinearPicture companion object can work with some implicit line drawer more suited to the context of execution. The most important job is achieved into the function apply method: iterating through each segment and applying the draw operation onto the rectangle. The apply method of the companion object, captures the definition of the graphic to be applied to whatever rectangle area we want

The mapping utility comes from the object FunctionalGeometry:

object FunctionalGeometry {

//..............

  def coordinateMappingIn(rectangle: Rectangle): (Vector2D => Vector2D) = {
    point: Vector2D =>
      rectangle.origin +
        rectangle.horizontal * point.x +
        rectangle.vertical * point.y
  }
//..............

We implicitly admitted that the genuine provided segment definitions will always be described by vectors scoped into the boundaries of a unitary rectangle.

From that point we have all we need. We can construct on our picture functionality. Take back your paper and pencil :)

You want to flip some picture function ? Then test the following:

import com.promindis.geometry.FunctionalGeometry._
import org.specs2.mutable.Specification

final class FlipSpecification extends Specification {

  "Flip a linear slope " should {
    "in a test rectangle mirror x coordinate versus vertical center axis" in {
      val drawer = new FakeDrawer
      val picture = LinearPicture(List(segment))(drawer)
      flip(picture)(inCell)
      drawer.segment must be equalTo (Segment(Vector2D(1.75, 1.25), Vector2D(1.25, 1.75) ))
    }
  }

  def segment = Segment(Vector2D(0.25, 0.25), Vector2D(0.75, 0.75))

  def inCell = Rectangle(Vector2D(1, 1), Vector2D(1, 0), Vector2D(0, 1))
}

and you get with:

object FunctionalGeometry {

  type G = Rectangle => Unit
//...........
  def flip(picture: G): G = {
    rectangle: Rectangle => {
      picture(Rectangle(
        rectangle.origin + rectangle.horizontal,
        rectangle.horizontal * -1,
        rectangle.vertical)
      )
    }
  }

//...........
}

Quite self explanatory. You want to set two pictures side by side with some ratio ?


Let's go for a test:

import com.promindis.geometry.FunctionalGeometry._
import org.specs2.mutable.Specification

final class BesideSpecification extends Specification {

  "Beside with two segments " should {
    "draw the two segemts in the box " in {
      implicit val drawer: DrawingAccumulator = new DrawingAccumulator()
      val p1 = LinearPicture(firstSegment)(drawer)
      val p2 = LinearPicture(secondSegment)(drawer)

      val sideBySide = beside(p1, p2, 0.5)
      sideBySide(inCell)
      println(drawer.segments)
      drawer.segments.contains(Segment(Vector2D(1, 1), Vector2D(1.5, 2))) must be equalTo (true)
      drawer.segments.contains(Segment(Vector2D(1.5, 2), Vector2D(2, 1))) must be equalTo (true)

    }
  }

  def firstSegment = List(Segment(Vector2D(0, 0), Vector2D(1, 1)))

  def secondSegment = List(Segment(Vector2D(0, 1), Vector2D(1, 0)))

  def inCell = Rectangle(Vector2D(1, 1), Vector2D(1, 0), Vector2D(0, 1))

}

Implementation follows immediately:

object FunctionalGeometry {

  type G = Rectangle => Unit
//...........

  def beside(pictureOne: G, pictureTwo: G, withRatio: Double): G = {
    rectangle: Rectangle => {
      pictureOne(inLeft(rectangle, withRatio))
      pictureTwo(inRight(rectangle, withRatio))
    }
  }

  private def inLeft(rectangle: Rectangle, ratio: Double): Rectangle = {
    Rectangle(rectangle.origin, rectangle.horizontal * ratio, rectangle.vertical)
  }

  private def inRight(rectangle: Rectangle, ratio: Double): Rectangle = {
    Rectangle(rectangle.origin + rectangle.horizontal * ratio, rectangle.horizontal * (1 - ratio), rectangle.vertical)
  }

}

And so on, we come with the small following language:

object FunctionalGeometry {

  type G = Rectangle => Unit


  def coordinateMappingIn(rectangle: Rectangle): (Vector2D => Vector2D) = {
    point: Vector2D =>
      rectangle.origin +
        rectangle.horizontal * point.x +
        rectangle.vertical * point.y
  }

  def flip(picture: G): G = {
    rectangle: Rectangle => {
      picture(Rectangle(
        rectangle.origin + rectangle.horizontal,
        rectangle.horizontal * -1,
        rectangle.vertical)
      )
    }
  }

  def empty(): G = {
    rectangle: Rectangle => ()
  }

  def mirror(picture: G): G = {
    rectangle: Rectangle => {
      picture(Rectangle(
        rectangle.origin + rectangle.vertical,
        rectangle.horizontal,
        rectangle.vertical * -1)
      )
    }
  }

  def rotate(picture: G): G = {
    rectangle: Rectangle => {
      picture(Rectangle(
        rectangle.origin + rectangle.vertical,
        rectangle.vertical * (-1),
        rectangle.horizontal)
      )
    }
  }

  def above(pictureOne: G, pictureTwo: G, withRatio: Double): G = {
    rectangle: Rectangle => {
      pictureOne(inTop(rectangle, withRatio))
      pictureTwo(inBottom(rectangle, withRatio))
    }
  }

  private def inTop(rectangle: Rectangle, ratio: Double): Rectangle = {
    Rectangle(rectangle.origin + rectangle.vertical * (1 - ratio), rectangle.horizontal, rectangle.vertical * (1 - ratio))
  }

  private def inBottom(rectangle: Rectangle, ratio: Double): Rectangle = {
    Rectangle(rectangle.origin, rectangle.horizontal, rectangle.vertical * ratio)
  }


  def beside(pictureOne: G, pictureTwo: G, withRatio: Double): G = {
    rectangle: Rectangle => {
      pictureOne(inLeft(rectangle, withRatio))
      pictureTwo(inRight(rectangle, withRatio))
    }
  }

  private def inLeft(rectangle: Rectangle, ratio: Double): Rectangle = {
    Rectangle(rectangle.origin, rectangle.horizontal * ratio, rectangle.vertical)
  }

  private def inRight(rectangle: Rectangle, ratio: Double): Rectangle = {
    Rectangle(rectangle.origin + rectangle.horizontal * ratio, rectangle.horizontal * (1 - ratio), rectangle.vertical)
  }

}

So what ? You want to see it ? Tough guys you are :). Ok, I took my Programming in Scala (2nd ed), and started to program a small GUI to display my pictures.

I came with a fast solution inspired by the book examples:

import scala.swing._
import java.awt.Graphics2D
import com.promindis.geometry.FunctionalGeometry._
import com.promindis.geometry.Schemes._
import com.promindis.graphics.GraphicsLineDrawer._
import com.promindis.geometry._
import com.promindis.graphics.Definitions._


class Painter(width: Int, height: Int, draw: G => G, draft: List[Segment]) extends Panel {
  def boundaries = Rectangle(Vector2D(0, 0), Vector2D(width.toDouble, 0), Vector2D(0, height.toDouble))

  preferredSize = new Dimension(width, height)
  border = Swing.EtchedBorder

  override def paintComponent(onGraphic: Graphics2D) {
    draw(LinearPicture(draft)(onGraphic))(boundaries)
  }
}

object DemoApp extends SimpleSwingApplication {
  def top = new MainFrame {
    title = "George and al."
    contents = new BoxPanel(Orientation.Vertical) {
      contents += new FlowPanel {
        contents += new Painter(500, 500, genuine(), george)
        contents += new Painter(500, 500, dancing, george)
      }
      contents += new FlowPanel {
        contents += new Painter(500, 500, bigGeorgeAndSmallGeorge(), george)
        contents += new Painter(500, 500, mosaic(), george)
      }
    }
    pack()
  }


  def genuine(): Scheme = {
    graphic: G => mirror(graphic)
  }

  def dancing = quartet()


  def bigGeorgeAndSmallGeorge() = {
    picture: G => mirror(beside(picture, above(empty(), picture, byHalf), byHalf))
  }

}

The class DemoApp extends SimpleSwingApplication and not SimpleGUIApplication as it has been deprecated since the book edition. I basically split the frame in four, playing with patterns. As I am not very found of Gui conception, I hope most of you will forgive my clumsy conception. The drawing job is achieve into the Painter class:

class Painter(width: Int, height: Int, draw: G => G, draft: List[Segment]) extends Panel {
  def boundaries = Rectangle(Vector2D(0, 0), Vector2D(width.toDouble, 0), Vector2D(0, height.toDouble))

  preferredSize = new Dimension(width, height)
  border = Swing.EtchedBorder

  override def paintComponent(onGraphic: Graphics2D) {
    draw(LinearPicture(draft)(onGraphic))(boundaries)
  }
}


where the boundaries of the rectangle area where to draw are set by the dimensions of the painter component . But by what magic, can the LinearPicture directly draw onto the Java2D graphics object? The mystery is solved when having a look at the following partner class definition:

import java.awt.{Color, Graphics2D}
class GraphicsLineDrawer(g: Graphics2D) extends LineDrawer{

  implicit def doubleToInt(value: Double): Int = value.toInt

  def draw(segment: Segment)  {
    g.setColor(Color.BLACK)
    g.drawLine(segment.start.x, segment.start.y, segment.end.x, segment.end.y)
  }
}

object GraphicsLineDrawer {

  implicit def graphics2DToGraphicsLineDrawer(g: Graphics2D): GraphicsLineDrawer = apply(g)

  def apply(g: Graphics2D) = {
    new GraphicsLineDrawer(g)
  }
}



I used the implicit conversion

implicit def graphics2DToGraphicsLineDrawer(g: Graphics2D): GraphicsLineDrawer = apply(g)

so to provide the illusion of a direct processing of the Java2D graphic object. No magic. The GraphicsLineDrawer "seems" to draw directly onto the Java2D graphic object instance:

draw(LinearPicture(draft)(onGraphic))(boundaries)

In order to play a little bit, you need to have some segment definitions:

object Definitions {
  val bigF = List(
    Segment(Vector2D(0.1, 0.1), Vector2D(0.3, 0.1)),
    Segment(Vector2D(0.3, 0.1), Vector2D(0.3, 0.3)),
    Segment(Vector2D(0.3, 0.3), Vector2D(0.7, 0.3)),
    Segment(Vector2D(0.7, 0.3), Vector2D(0.7, 0.5)),
    Segment(Vector2D(0.7, 0.5), Vector2D(0.3, 0.5)),
    Segment(Vector2D(0.3, 0.5), Vector2D(0.3, 0.7)),
    Segment(Vector2D(0.3, 0.7), Vector2D(0.9, 0.7)),
    Segment(Vector2D(0.9, 0.7), Vector2D(0.9, 0.9)),
    Segment(Vector2D(0.9, 0.9), Vector2D(0.1, 0.9)),
    Segment(Vector2D(0.1, 0.9), Vector2D(0.1, 0.1))
  )

  val george = List(
    Segment(Vector2D(0.3, 0), Vector2D(0.5, 0.4)),
    Segment(Vector2D(0.5, 0.4), Vector2D(0.6, 0)),
    Segment(Vector2D(0.8, 0), Vector2D(0.7, 0.5)),
    Segment(Vector2D(0.7, 0.5), Vector2D(1, 0.2)),
    Segment(Vector2D(1, 0.3), Vector2D(0.7, 0.7)),
    Segment(Vector2D(0.7, 0.7), Vector2D(0.5, 0.7)),
    Segment(Vector2D(0.5, 0.7), Vector2D(0.6, 0.8)),
    Segment(Vector2D(0.6, 0.8), Vector2D(0.5, 1)),
    Segment(Vector2D(0.4, 1), Vector2D(0.3, 0.8)),
    Segment(Vector2D(0.3, 0.8), Vector2D(0.4, 0.7)),
    Segment(Vector2D(0.4, 0.7), Vector2D(0.3, 0.7)),
    Segment(Vector2D(0.3, 0.7), Vector2D(0.2, 0.6)),
    Segment(Vector2D(0.2, 0.6), Vector2D(0, 0.8)),
    Segment(Vector2D(0, 0.7), Vector2D(0.1, 0.4)),
    Segment(Vector2D(0.1, 0.4), Vector2D(0.3, 0.6)),
    Segment(Vector2D(0.3, 0.6), Vector2D(0.4, 0.5)),
    Segment(Vector2D(0.4, 0.5), Vector2D(0.1, 0))
  )
}


and a complementary class, where I awkwardly started to defines "schemes" of behavior, as kind of patterns of graphics. This is where I will need some help, because I am still very low on combination and typing in Scala. But I am willing, so forgivable ;):

import com.promindis.geometry.FunctionalGeometry._

object Schemes {
  type Scheme = G => G

  def byHalf: Double = {
    0.5
  }

  def quartet (): Scheme = {
    picture: G => {
      val draw = pattern()
      above(draw(picture), mirror(draw(picture)), byHalf)
    }
  }

  def mosaic (): Scheme = {
    picture: G => {
      val draw = quartet()
      above(beside(draw(picture), draw(picture), byHalf), mirror(beside(draw(picture), draw(picture), byHalf)), byHalf)
    }
  }

  def pattern(): Scheme = (picture: G) => beside(picture, flip(picture), byHalf)

}

The running program provides the following picture:



and at a very low cost in time.

What we have built at this point is, layer after layer,

  • some bottom primitives including the notion of rectangles, segments, then pictures as functions, but seen as "data"
  • Then a geometric language above that layer of primitives
  • At the end we started a clumsy -but understandable-  language of schemes of combinations using the geometric layers

I can imagine that with some skilled Scala developers we could go further, and stack layers onto layers providing a nice complete embedded language.

Critics will be welcomed as this is an experimental work.
Time for Torchwood episode.


Be seeing you !!:)

0 comments:

Post a Comment