On this page:
1 Libraries and Constants
2 Data Definitions
3 run
4 draw
5 next-ball
5.1 An Ambiguity
5.2 next-x
5.3 next-x Review
6 next-ball, Revisited
7 Ball-processing Functions
7.1 ball-off-canvas?
7.2 ball-forward
7.3 ball-reverse-direction
7.4 ball-to-edge
8 Summary

How to Implement Functions

Last updated: Fri, 16 Jan 2015 15:10:18 -0500

The Function Specification step of The Program Design Recipe thoroughly describes how to explain the behavior of a function at a high level via data definitions, English prose, and examples. The recipe provides less guidance, however, on how to write the function’s code.

The data decomposition strategy dictates a starting template, such that the shape of the function’s code mirrors the shape of its input data. But how does one choose a strategy in the first place?

Thus far, we’ve introduced two design strategies:

Which strategy is better for a given situation? This page provides guidelines for choosing a strategy, as well as other guidelines to keep in mind while designing the code for a function.

The guidelines are further categorized as:
  • process guidelines, which should be followed when coding a function for the first time,

  • and review guidelines, which you should apply during the review step after you’ve written a first draft of a function.

We will use a running example to introduce and illustrate the guidelines:

Write a big-bang program that simulates a red ball moving horizontally at a constant speed of 9 pixels/tick. The canvas dimensions are 400 x 400 pixels and the ball has a radius of 40 pixels and starts in the middle of the canvas.

On a tick, if any part of the ball would move off the canvas, the ball is instead positioned flush against the edge it just passed, moving in the opposite direction. Thus, the ball should bounce back and forth between the left and right edges of the canvas, as shown.

Some things to keep in mind while reading the tutorial:
  • This tutorial is just one example of how you might devise a solution to the problem, but it is not the only path. The intention is to introduce some important general guidelines that you should follow for when you do your own programming.

  • Points may not necessarily be deducted for violating these guidelines, as there may not be an "optimal" solution to any given problem. But any deviation from the guidelines should be supported with pros and cons of your design decision as well as possible alternatives. Be prepared to discuss these tradeoffs during your code walk.

  • This tutorial focuses on the Function Implementation step of the design recipe. Thus, the guidelines complement the guidelines you’ve already learned for the other recipe steps.

1 Libraries and Constants

We use the Beginning Student Language and the following libraries to implement our program:

(require 2htdp/universe)
(require 2htdp/image)
(require rackunit)
(require "extras.rkt")

We also define some constants based on information from the problem description.

; canvas constants
(define CENTER-X 200) ; pixels
(define CENTER-Y 200) ; pixels
(define WIDTH (* 2 CENTER-X)) ; pixels
(define HEIGHT (* 2 CENTER-Y)) ; pixels
(define EMPTY-SCENE (empty-scene WIDTH HEIGHT)) ; Image
 
; Ball constants
(define BALL-RADIUS 40) ; pixels
(define BALL-IMG (circle BALL-RADIUS "solid" "red")) ; Image
(define VELOCITY 9) ; pixels/tick
2 Data Definitions

Following The Program Design Recipe, we first define data definitions. Since we wish to call big-bang, we need a World data definition. Thinking about what objects we need to represent and what values are changing on each tick, we come up with the following data definitions and accompanying Data Design requirements.

; A Direction is one of:
; - "right"
; - "left"
; INTERP: represents a canvas direction where "right" is x-increasing.
(define RIGHT "right")
(define LEFT "left")
 
; <direction predicates> : Direction -> Boolean
; Returns true if d is the Direction indicated by the function name.
; STRATEGY: function composition
(define (right? d) (string=? d RIGHT))
(define (left? d) (string=? d LEFT))
 
; TEMPLATE
; direction-fn : Direction -> ???
(define (direction-fn dir)
  (cond
    [(right? dir) ...]
    [(left? dir) ...]))
 
; A Ball is a (make-ball Coordinate Direction)
; INTERP: The Coordinate is the ball's x position.
(define-struct ball (x dir))
 
(define INIT-BALL (make-ball CENTER-X RIGHT))
(define INIT-BALL-LEFT (make-ball CENTER-X LEFT))
(define BALL-X-RIGHT-EDGE (- WIDTH BALL-RADIUS)) ; x Coordinate
(define BALL-X-LEFT-EDGE BALL-RADIUS) ; x Coordinate
(define BALL-AT-RIGHT-EDGE (make-ball BALL-X-RIGHT-EDGE LEFT))
(define BALL-AT-LEFT-EDGE (make-ball BALL-X-LEFT-EDGE RIGHT))
 
; TEMPLATE:
; ball-fn : Ball -> ???
(define (ball-fn b)
  (... (ball-x b) ... (direction-fn (ball-dir b)) ...))
 
; A World is a Ball
(define INIT-WORLD INIT-BALL)

Note the call to direction-fn in Ball’s template. Restricting functions to decomposing only one kind of data helps ensure that each function adheres to performing only one distinct task.

Process Guideline 1: Decompose one kind of data per function.

3 run

To start, we define run, which calls big-bang.

; run : World -> World
; Starts the simulation.
; STRATEGY: function composition
(define (run init-world)
  (big-bang
   init-world
   (on-tick next-world)
   (to-draw draw)))

We utilize a wish list to remember what other functions we need to implement.

Wish List:
  • ; next-world : World -> World
    ; Computes the next World state.
  • ; draw : World -> Image
    ; Renders the current World state into an Image.

Process Guideline 2: Use a wish list to organize and document your progress as you write a program.

It’s a good idea to record your wish list somewhere where you can refer back to it, since you may be asked about it during your code walk.

4 draw

Our wish list contains next-world and draw. The draw function seems straighforward so we implement it first.

Following the design recipe:

Here is the result:

; draw : World -> Image
; Renders the current World state.
; STRATEGY: function composition
(define (draw w)
  (draw-ball-on w EMPTY-SCENE))
 
; draw-ball-on : Ball Image -> Image
; Draws Ball b onto Image img.
; WHERE: BALL-RADIUS <= (ball-x b) <= ((image-width img) - BALL-RADIUS)
;        (Ball b is completely within img.)
; STRATEGY: data decomposition on b : Ball
(define (draw-ball-on b img)
  (place-image BALL-IMG (ball-x b) CENTER-Y img))
 
(begin-for-test
  (check-equal? (draw INIT-BALL)
                (place-image BALL-IMG CENTER-X CENTER-Y EMPTY-SCENE))
  (check-equal? (draw BALL-AT-LEFT-EDGE)
                (place-image BALL-IMG BALL-X-LEFT-EDGE CENTER-Y EMPTY-SCENE)))

Commentary:
  • Function examples are less important here since draw produces an Image, so we leave them out (but we still must have sufficient tests).

  • In this example, a World is just a Ball so draw just calls draw-ball-on. Two separate functions are not strictly needed here, but this way, we keep the concept of World and Ball separate, which makes it easier to change the World definition later if necessary.

  • draw-ball-on’s signature allows any Ball and Image input. Since we know the given Ball is always on the canvas, however, we add an argument invariant to capture this additional information. This restricts what Ball values draw-ball-on accepts, making the function specification more precise. This also means that while writing the function, we don’t need to worry about cases where the Ball is off the canvas and we can omit tests for these cases as well.

5 next-ball

Finally, we implement next-ball. Again following The Program Design Recipe, we come up with the Function Specification. For this function, examples are crucial in explaining its behavior, particularly for the edge cases. Since we are again processing compound data, we initially choose the data decomposition strategy and start with Ball’s template.

So far, our next-ball looks like:

(define BALL-NEAR-RIGHT-EDGE (make-ball (sub1 BALL-X-RIGHT-EDGE) RIGHT))
(define BALL-1TICK-FROM-RIGHT-EDGE (make-ball (- BALL-X-RIGHT-EDGE VELOCITY) RIGHT))
(define BALL-AT-RIGHT-EDGE-MOVING-RIGHT (make-ball BALL-X-RIGHT-EDGE RIGHT))
 
; next-ball : Ball -> Ball
; Computes the next ball state.
; WHERE: Ball b is completely on the canvas.
; EXAMPLES:
(begin-for-test
  (check-equal? (next-ball INIT-BALL)
                (make-ball (+ CENTER-X VELOCITY) RIGHT))
  (check-equal? (next-ball BALL-NEAR-RIGHT-EDGE) BALL-AT-RIGHT-EDGE)
  (check-equal? (next-ball BALL-1TICK-FROM-RIGHT-EDGE) BALL-AT-RIGHT-EDGE)
  (check-equal? (next-ball BALL-AT-RIGHT-EDGE-MOVING-RIGHT) ???))
; STRATEGY: data decomposition on b : Ball
(define (next-ball b)
  (... (ball-x b) ... (direction-fn (ball-dir b)) ...))
5.1 An Ambiguity

While writing Function Examples for next-ball, we came up with an example (indicated by the ???) where we are unsure what the expected result should be. What should be the next state for a ball at the right edge, moving RIGHT? Apparently, the specification says that it should again be touching the right edge, but moving LEFT. But this feels counter-intuitive; shouldn’t the ball still change position in that situation? Did we interpret the specification correctly? Do we understand what the problem meant by "off the canvas" and such terms?

Oftentimes a problem statement is ambiguous about how exactly the program should behave, or our intuition leads us to doubt the literal statement of the problem itself.

Indeed, ambiguities and confusions are certain to occur when writing any program, whether in an academic or a professional setting. In this class, when you think the problem description is ambiguous or unclear, you should carefully re-read it to see if it explains the expected behavior. In this case, it does not. Specifically, the words "off the canvas" are ambiguous, since we don’t know exactly which pixel constitutes "off the canvas."

When this occurs in practice, you should consult your client or colleagues about the appropriate behavior. In this class, you should ask the course staff to clarify. We may not always provide an exact answer, just like your clients may not always know what they want, in which case you need to choose a reasonable behavior. Be prepared to explain the reasoning supporting your choices in your code walk.

How shall we resolve our example? In this case, there is a clever trick we can use. To avoid having the Ball remain idle during a tick, we can consider (make-ball BALL-X-RIGHT-EDGE LEFT) "on" canvas while (make-ball BALL-X-RIGHT-EDGE RIGHT) is "off" canvas. Stop for a moment to think about how this changes our dilemma. Think about how we arrive at each state, as well as what happens after that state.

Have you thought it through? OK, here’s how it’s different: by defining (make-ball BALL-X-RIGHT-EDGE RIGHT) to be "off canvas," we ensured that our problematic situation should not have occurred in the first place. As the ball approaches the right edge, if it hits BALL-X-RIGHT-EDGE exactly, then it is already off-canvas, and its next state has heading LEFT. In particular, by ruling out this boundary case (and declaring that we did so) we’ve avoided the need to test it. Note that you must declare an invariant if you do so; and you have to be sure that your own code won’t violate the invariant! (That’s the meaning of an invariant: something whose truth does not vary.)

You should be prepared to give an explanation like this during a code walk if asked about how you resolved an ambiguous situation.

Ruling out certain inputs doesn’t always get you out of a jam, but when it’s a close matter of one pixel plus or minus, it may be just what you need.

Thus we update the argument invariant to state that the input ball must be on-canvas in this precise sense, and then leave off the last example.

Process Guideline 4: When encountering ambiguous behavior, ask for clarification, and then make a reasonable decision if necessary. Be prepared to explain your decision during a code walk.

5.2 next-x

Now we wish to complete our implementation of next-ball. To do so, we need to compute the next x position and the next Direction.

To compute the next x, we need to either add or subtract VELOCITY, depending on the ball’s direction. Since we don’t want to decompose more than one kind of data in one function, we define a new function that decomposes a Direction. Let’s try writing it like this:

; next-ball : Ball -> Ball
; Computes the next ball state.
; WHERE: Ball b is completely on the canvas.
; STRATEGY: data decomposition on b : Ball
(define (next-ball b)
  (... (next-x (ball-x b) (ball-dir b))
       ...
       (direction-fn (ball-dir b)) ...))
 
; next-x : Coordinate Direction -> Coordinate
; Computes the next x position in Direction dir.
; STRATEGY: data decomposition on dir : Direction
(define (next-x.v1 x dir)
  (cond
    [(left? dir) (- x VELOCITY)]
    [(right? dir) (+ x VELOCITY)]))

(We add the .v1 suffix to better track our progress, but assume the function name is always next-x.)

We leave out function examples since we already considered the possible behaviors in the next-ball examples.

Of course, next-x may move the ball off the canvas. To handle this, we might update next-x to something like:

; next-x : Coordinate Direction -> Coordinate
; Computes the next x position in Direction dir.
; If any part of a Ball with the computed x position would be off the canvas
; then instead return an x position such that the Ball is flush with the
; nearest canvas edge.
; STRATEGY: data decomposition on dir : Direction
(define (next-x.v2 x dir)
  (cond
    [(left? dir) (if (<= (- x VELOCITY) BALL-X-LEFT-EDGE)
                     BALL-X-LEFT-EDGE
                     (- x VELOCITY))]
    [(right? dir) (if (>= (+ x VELOCITY) BALL-X-RIGHT-EDGE)
                      BALl-X-RIGHT-EDGE
                      (+ x VELOCITY))]))

Adding tests, one partition per combination of inputs, confirms that our function behaves as expected.

(begin-for-test
  (check-equal? (next-x CENTER-X RIGHT) (+ CENTER-X VELOCITY))
  (check-equal? (next-x CENTER-X LEFT) (- CENTER-X VELOCITY))
  (check-equal? (next-x (sub1 BALL-X-RIGHT-EDGE) RIGHT) BALL-X-RIGHT-EDGE)
  (check-equal? (next-x (add1 BALL-X-LEFT-EDGE) LEFT) BALL-X-LEFT-EDGE))
5.3 next-x Review

After completing the implementation of next-x, the next design recipe step is the review step. Don’t skip this step. You may be asked about your review steps during your code walk.

The above next-x is stylistically valid since:

However, we should not be satisfied with our current next-x implementation. Here are some potential problems (some programmers might refer to these as code smells):
  • The function consumes and produces Coordinates and thus should represent a "Coordinate task". However the function requires a Ball property (BALL-RADIUS) to do its computation and the output is only meaningful when it’s part of a Ball. Thus the function doesn’t make sense when viewed independently so we need to rewrite it.

    Review Guideline 1: Check that a function’s "task" makes sense for the kind of data it consumes and produces, and that its output is not dependent on a specific context.

  • The function is somewhat long and complicated, such that someone looking at it can’t tell what it does right away. A good indicator of a too-complicated function is when we can’t write a clear, concise purpose statement. The purpose statement we wrote is way too long.

    While editing your prose for clarity and conciseness is always a good idea during the review step, this tutorial’s focus is a function’s implementation so we don’t introduce a formal guideline for editing the purpose statement.

  • The expressions (+ x VELOCITY) and (- x VELOCITY) are repeated.

  • The cond right-hand sides have similar shape so there may be opportunities for abstraction.

    Review Guideline 2: Look for abstraction opportunities in repeated code.

Regarding the first bullet, it’s clear that the "off canvas" computation should be a performed by a Ball-processing function. However, it’s redundant to re-create a Ball (and then decompose it again) after we’ve already decomposed it:

dont decompose and then reconstruct a piece of data

(define (next-x.bad x dir)
  (if (ball-off-canvas? (make-ball x dir))
      ...
      ...))
(define (ball-off-canvas?.bad b)
  (... (ball-x b) ... (ball-dir b) ...))

Review Guideline 3: Check that a chain of function calls only decomposes compound or itemization data once.

Thus, perhaps we should revisit next-ball’s implementation to delay decomposition of the Ball. Another indication that next-ball should perhaps not decompose Ball is that next-x needed both parts of the compound Ball value. When this is the case, it’s often better to just pass the compound data directly, since the multiple arguments clutter the program.

Review Guideline 4: Avoid overeager decomposition. If a data decomposition function passes multiple subpieces of data to other functions, then consider refactoring the function to use function composition and instead pass the whole argument. Or you may need to refactor your data definitions.

A variant of overeager decomposition may require some parts of a compound data, but other parts get strung through multiple function calls and are not used until later, again cluttering the code. In this situation, data definition refactoring is recommended.

Keep in mind that a function composition function does not decompose any compound or itemization data. As another corollary of the above guideline, avoid partial function composition functions that pass both the whole data and its pieces. For example, the following uses neither a function composition nor a data decomposition strategy:

dont pass on both pieces and the whole compound data

(define (next-ball.bad b)
  (if (off-canvas? (ball-x b) (ball-dir b))
      (next-x b (ball-x b) (ball-dir b))
      ...))
6 next-ball, Revisited

Let’s refactor next-ball to be a composition of Ball-processing functions. To determine what functions we need, let’s see if we can think of discrete Ball "tasks":
  • moving a Ball forward, independent of any canvas edges,

  • checking if a Ball is off the canvas,

  • moving a Ball to the edge of a canvas,

  • changing a Ball’s direction.

These tasks make sense when viewed independently, and thus are consistent with the previous guideline. In other words, the output of the tasks are not dependent on a specific context. As the textbook advises, being able to identify discrete tasks is another sign that function composition may be appropriate.

Review Guideline 5: If you can identify multiple, discrete tasks performed by a data decomposition function, consider refactoring the function to use function composition.

Now let’s turn these tasks into functions for our wish list.

We can keep most of the other design recipe steps unchanged, so we only present the changed components.

; next-ball : Ball -> Ball
; Computes the next ball state.
; STRATEGY: function composition
(define (next-ball b)
  (if (ball-off-canvas? (ball-forward b))
      (ball-reverse-direction (ball-to-edge b))
      (ball-forward b)))

Our wish list looks like:

Wish List:
  • ; ball-off-canvas? : Ball -> Boolean
    ; Returns true if any part of the given Ball is off the canvas.
  • ; ball-forward : Ball -> Ball
    ; Moves the Ball forward in its Direction by VELOCITY pixels.
  • ; ball-reverse-direction : Ball -> Ball
    ; Reverses the Direction of the given Ball.
  • ; ball-to-edge : Ball -> Ball
    ; Moves the given Ball as far as possible in its Direction.

7 Ball-processing Functions

Let’s tackle the wish list in order. For brevity, we highlight only the the interesting design recipe steps. We leave it as an exercise to fill in the missing requirements.

7.1 ball-off-canvas?
; ball-off-canvas? : Ball -> Boolean
; Returns true if any part of b is at or past the left or right canvas edge.
(begin-for-test
  (check-true (ball-off-canvas? (make-ball BALL-X-RIGHT-EDGE RIGHT)))
  (check-true (ball-off-canvas? (make-ball BALL-X-LEFT-EDGE LEFT))))
; STRATEGY: function composition
(define (ball-off-canvas? b)
  (or (ball-at/past-left-edge? b)
      (ball-at/past-right-edge? b)))
 
; <Ball edge predicates> : Ball -> Boolean
; Returns true if any part of b is at or past the named edge.
; STRATEGY: data decomposition on b : Ball
(define (ball-at/past-left-edge? b)
  (<= (ball-x b) BALL-X-LEFT-EDGE))
(define (ball-at/past-right-edge? b)
  (>= (ball-x b) BALL-X-RIGHT-EDGE))

Commentary:
  • Function examples are important here to precisely illustrate the edge cases.

  • We could have written just one function, but separating the tasks improves code readability.

7.2 ball-forward
; ball-forward : Ball -> Ball
; Move ball b by VELOCITY pixels in its current Direction.
; STRATEGY: data decomposition on b : Ball
(define (ball-forward b)
  (make-ball
   (x-forward (ball-x b) (ball-dir b))
   (ball-dir b)))
 
; x-forward : Coordinate Direction -> Ball
; Move coordinate x by VELOCITY pixels in direction dir.
; STRATEGY: data decomposition on dir : Direction
(define (x-forward x dir)
  (cond
    [(left? dir) (- x VELOCITY)]
    [(right? dir) (+ x VELOCITY)]))

Commentary:

In the review step, we note that we could define ball-forward in terms of a Ball x-updater function, but since this would be the only current use for the updater, we leave the code as-is and just keep the option in mind for later.

7.3 ball-reverse-direction
; ball-reverse-direction : Ball -> Ball
; Reverses the direction of the given ball.
; STRATEGY: data decomposition on b : Ball
(define (ball-reverse-direction b)
  (make-ball
   (ball-x b)
   (reverse-direction (ball-dir b))))
 
; reverse-direction : Direction -> Direction
; Flips the given direction d.
; STRATEGY: data decomposition on d : Direction
(define (reverse-direction d)
  (cond
    [(right? d) LEFT]
    [(left? d) RIGHT]))

ball-reverse-direction follows essentially the same design as ball-forward. We also note that it could use a Ball-direction updater function.

7.4 ball-to-edge

If we follow the design of ball-forward and ball-reverse-direction, we get the following implementation of ball-to-edge.

; ball-to-edge : Ball -> Ball
; Moves b to the furthest edge in the direction it's facing.
; STRATEGY: data decomposition on b : Ball
(define (ball-to-edge.v1 b)
(make-ball
 (ball-x-at-edge (ball-dir b))
 (ball-dir b)))
 
; ball-x-at-edge : Direction -> Coordinate
; Returns the extreme x coordinate of a ball center,
; at the edge indicated direction by the direction dir
; STRATEGY: data decomposition on dir : Direction
(define (ball-x-at-edge dir)
  (cond
    [(left? dir) BALL-X-LEFT-EDGE]
    [(right? dir) BALL-X-RIGHT-EDGE]))

However, ball-x-at-edge again doesn’t satisfy the task-data-consistency guideline (although the name is better this time, since it indicates that we’re only concerned with Ball x’s), because its output is only meaningful when used as a Ball field.

In the review step, we note that as another alternative, perhaps defining a subset of Coordinate called BallXCoordinate would help us in defining a ball-x-at-edge function that make sense. Again, this tutorial’s focus is on implementation, so we don’t introduce a formal guideline, but think about what this alternate data definition would look like.

Instead, we refactor ball-to-edge to call an alternate constructor, make-edge-ball, which consumes a Direction and returns a Ball at the indicated edge of the canvas.

; ball-to-edge : Ball -> Ball
; Moves b to the furthest edge in the direction it's facing.
; STRATEGY: data decomposition on b : Ball
(define (ball-to-edge b)
  (make-edge-ball (ball-dir b)))
 
; make-edge-ball : Direction -> Ball
; Constructs a new ball positioned as far as possible in the given Direction,
; and moving in the opposite direction.
(define (make-edge-ball dir)
  (cond
    [(left? dir) (make-ball BALL-X-LEFT-EDGE RIGHT)]
    [(right? dir) (make-ball BALL-X-RIGHT-EDGE LEFT)]))

An alternate constructor’s name should begin with make- and the function should consume (some) component data and produce a compound data.

Process Guideline 5: Write alternate constructor functions when appropriate.

With this definition of ball-to-edge, we no longer need ball-reverse-direction so the final version of next-ball looks like:

; next-ball : Ball -> Ball
; Computes the next ball state.
; STRATEGY: function composition
(define (next-ball b)
  (if (ball-off-canvas? (ball-forward b))
      (ball-to-edge b)
      (ball-forward b)))
8 Summary

Note we can still find some problems with our solution. For example, (ball-forward b) is repeated. There will rarely be an optimal solution however. Designing programs is all about identifying, weighing, and making tradeoffs.

For the repeated code, given that the Beginner Language does not allow local definitions, to eliminate the repetition, we would have to define a new function. However, it’s not clear what discrete task that function would accomplish (as an exercise, try to name the function), so given this tradeoff, since the repetition is minor, we leave it as is. (Note that this is the kind of reasoning we expect to hear during code walks.)

Our final solution is not the only acceptable solution. In particular, we have not even considered alternate data definitions. However, this guide’s purpose is not to explore all possible design decisions, but merely to illustrate some guidelines you should follow when implementing your programs.

In summary, here are all the process guidelines:

And here are the review guidelines: