SICP series - Procedural and Data Abstraction

14 November 2019
Tags: fundamentals SICP functional programming

The purpose of this post is to provide an example on how procedural and data abstractions can be exploited and combined together to build modular systems. At the end of this article you should be convinced that there is actually not a clear distinction between the two types of abstractions, rather they are two sides of the same coin. I am going to outline only the most important points on the picture language defined in the book [1].

It is possible to build domain specific languages in Scheme for describing and solving the domain problem. Since the language is embedded within Scheme, it inherits the power of Scheme. The topic of the current post is to build a language to draw pictures in the style of Escher [2]. What we want to do is drawing into frames intricated recursive patterns out of a figure we will name George. We can proceed to define George straight away in the following manner

(define (george rect)
  (draw-line rect .25 0 .35 .5)
  (draw-line rect .35 .5 .3 .6)
  (draw-line rect .3 .6 .15 .4)
  ; ...
)

The problem with this implementation is that both the action of drawing George and the data representing George are intertwined. Besides, the representation of the elements of George are very low-level. With some data abstraction it is possible to define vectors as poitns in space and segments as lines connecting two vectors. So a better representation of George could be

(define (george-lines)
  (list
    (make-segment p1 p2)
    (make-segment p2 p3)
    (make-segment p3 p4)
    ; ...
  )
)

Here we have defined George in terms of segments, which is a higher level of abstraction. Besides, these lines are defined with respect to some coordinate frame, but they are not being drawn yet. So the act of drawing has been separated from the representation of the data.

Now comes the key problem: drawing a picture within a frame. The first idea that comes to mind could be to create a procedure to draw collections of segments. However, we would like to have the flexibility of using any frame to draw in. So, a picture could be made a procedure. This may sound weird at first, since one would normally assume it should be a data structure, but it is actually a good idea because it captures the procedural abstraction of drawing data within a frame. The procedure is going to contain the geometric entities of George, but is also going to take as input a frame, the nscale the elements to fit within the frame and finally display the results. This abstraction results in an increased flexibility in manipulating the picture structure. We are now going to define the function which implements this job.

(define (make-picture seglist)
  (lambda (frame)
    (for-each
      (lambda (segment)
        (let ((b (start-segment segment))
              (e (end-segment segment)))
          (draw-line frame
                     (xcoord b)
                     (ycoord b)
                     (xcoord e)
                     (ycoord e))))
    seglist)))

First of all note that make-picture is a higher-order procedure, since it returns another procedure. It takes as input a list of segments to be drawn, George in our case. The inner procedure takes the frame on which to draw the figure as input, making the drawing process of the figure independent of the frame in which to draw in. The body of the inner function cycles through each segment of the list of segments (George), assigns the the start vector and end vector of the segment to two local variables, then proceeds to draw inside the segment inside the frame (note the draw-line we had previously employed to define George). Finally, George can be defined with the following instruction:

(define g (make-picture george-lines))

To wrap up, George is now both a data abstraction (george-lines, a list of segments) and a procedure (g, a procedure for drawing those lines within a frame). Also note that g contains the information about the segments within it as part of the procedural abstraction. This makes it easy to use George as the building block to draw other pictures and define other operations such as scaling, rotation, combinations.