A Crash into FP through ATS:
PrevNext

Chapter 4. Example: Sierpinski Triangle

A Sierpinski triangle is a fractal that can be constructed by first removing the medial triangle or midpoint triangle of a given triangle and then doing so recursively to the three triangles formed due to this removal. I would like to present in this chapter a program for drawing a Sierpinksi triangle (of which a demo can be seen by clicking here). This is also a place for me to advocate the so-called refinement-based programming.

A triangle can be represented as a tuple of three points. Let us introduce an abstract type for points: 

//
abstype point // abstract type for points 
//

Given two points A and B, the following function midpoint returns the middle point lying on the line segment connecting A and B: 

//
extern
fun
midpoint(A: point, B: point): point = "mac#"
//

The use of "mac#" is to indicate to patsopt that the function midpoint should be compiled into a function in C of the same name.

Given three points A, B, and C, the following function SierpinskiDraw draws (in some manner) the Sierpinkski triangle inside the triangle ABC: 

//
extern
fun
SierpinskiDraw
( n: int
, A: point, B: point, C: point): void = "mac#"
//

Note that the first parameter of SierpinskiDraw sets the limit for the recursion depth. An implementation of SierpinskiDraw is given as follows: 

//
implement
SierpinskiDraw
(n, A, B, C) = (
//
if
(n > 0)
then let
//
val AB = midpoint(A, B)
val BC = midpoint(B, C)
val CA = midpoint(C, A)
//
val () = TriangleRemove(AB, BC, CA)
//
val () = SierpinskiDraw(n-1, A, AB, CA)
val () = SierpinskiDraw(n-1, B, BC, AB)
val () = SierpinskiDraw(n-1, C, CA, BC)
//
in
  // nothing
end // end of [then]
else () // end of [else]
//
) (* end of [SierpinskiDraw] *)
//

where the function TriangleRemove inside the body of SierpinskiDraw is given the following interface: 

//
extern
fun
TriangleRemove
  (A: point, B: point, C: point): void = "mac#"
//

ATS source can be compiled into many programming languages, including C, Javascript (JS), PHP, etc. For instance, we may choose JS as the target language for compiling ATS. With this choice, we can implement TriangleRemove in JS directly: 

%{
//
function
TriangleRemove
 (A, B, C)
{
  theCtx.save();
//
  theCtx.beginPath();
  theCtx.moveTo(A.x, A.y);
  theCtx.lineTo(B.x, B.y);
  theCtx.lineTo(C.x, C.y);
  theCtx.closePath();
//
  theCtx.fill();
//
  theCtx.restore();
} // end of [TriangleRemove]
//
%}

The code between %{ and %} is considered to be external by patsopt, and it is pasted into the compilation output verbatim. The variable theCtx refers to the 2-dimensional context associated with certain canvas (in the DOM tree); what the function TriangleRemove does is drawing a closed path that forms the boundary of the triangle positioned at three given points and then filling the closed path with some color.

The function midpoint can also be conveniently implemented in JS: 

%{
//
function
midpoint
(p1, p2)
{
//
  var
  xmid = (p1.x + p2.x)/2;
  var
  ymid = (p1.y + p2.y)/2;
//
  return { x: xmid, y: ymid };
//
}
//
%}

Various coding details that are omitted for brevity can be found in the file Sierpinski.dats. I will talk more about co-programming with ATS and JS in a chapter presented later in this book.

Please find on-line the entirety of the code used in this chapter. The mentioned URL link(s) can be found as follows:

PrevHomeNext
Recursive Functions (2) Higher-Order Functions