Lab 7: Call the Plumber,
or, A Tree by Any Other Name

28 October 2022

Learning objectives

The purpose of this lab is to give you practice:

  • modeling parts of the world using trees,
  • working with structurally recursive data definitions, and
  • writing functions using a template for structurally recursive data definitions.

This lab can be completed in pairs!

If you choose to work in a pair, you’ll make a single code file which you’ll upload to Gradescope with both your names.

Introduction

We would like to write a program that represents pipelines, as you might do if you were building a computer model of real-world infrastructure – or if you were making a game like SimCity!

A pipeline has

  • faucets, which can be opened or closed,
faucet open faucet closed
image of an open faucet image of a closed faucet
  • straight pipes, which can be copper or lead,
one straight pipe leading to a faucet two straight pipes leading to a faucet
  • and branches, where a pipe splits in two.
pipeline with one branch pipeline with several branches

Data definition

We can represent pipelines as described above with the appropriate data definition. Since our pipelines consist of multiple instances of faucets, straight pipes, and branches, our data definition includes these three varieties.

Task: Copy the following data definitions and examples into your lab07.arr file.

data Pipeline:
  | faucet(is-open :: Boolean)
  | straight(kind :: Metal, pl :: Pipeline)
  | branch(pl1 :: Pipeline, pl2 :: Pipeline)
end

data Metal:
  | lead
  | copper
end


#
# Example pipelines
#

f-closed = faucet(false)
f-open = faucet(true)

straight-c = straight(copper, f-closed)

straight-c-l =
  straight(copper,
    straight(lead, f-closed))

branching-pipeline =
  branch(
    branch(
      straight(copper, f-open),
      f-closed),
    branch(
      f-closed,
      f-closed))

Template

Since we defined a new type of data (Pipeline), it’s a good idea to write a template we can use for functions that take that data as input.

Task: Copy this template into your lab07.arr file:

#|
fun pipeline-fun(pl :: Pipeline) -> ...:
  doc: "Template for a function that takes a pipeline"

  cases (Pipeline) pl:
    | faucet(is-open) =>
      ... is-open ...
    | straight(kind, pl1) =>
      ... kind ...
      ... pipeline-fun(pl1) ...
    | branch(pl1, pl2) =>
      ... pipeline-fun(pl1) ...
      ... pipeline-fun(pl2) ...
  end
where:
  pipeline-fun(...) is ...
end
|#


#
# Exercise 1
#


#
# Exercise 2
#


#
# Exercise 3
#


#
# Exercise 4
#


#
# Exercise 5
#

Exercise 1

Task: Implement the function is-water-running, which takes a Pipeline and determines whether any faucets are open.

To help you get started with the lab, we’ve done this one for you!


#
# Exercise 1
#

fun is-water-running(pl :: Pipeline) -> Boolean:
  doc: "Determine whether any faucets are open in pl"

  cases (Pipeline) pl:
    | faucet(is-open) =>
      is-open
    | straight(kind, pl1) =>
      is-water-running(pl1)
    | branch(pl1, pl2) =>
      is-water-running(pl1) or is-water-running(pl2)
  end
where:
  is-water-running(f-open) is true
  is-water-running(f-closed) is false
  is-water-running(straight-c) is false
  is-water-running(straight-c-l) is false
  is-water-running(branching-pipeline) is true
end

Copy and paste it into your lab07.arr file. Make sure you understand how this function works – how did we write this based on the template above?

Task: Why do we have so many examples for this function? Since it’s a predicate (a function returning a Boolean), why isn’t it enough to have one true example and one false example? Put your answer in a comment.

Exercise 2

Task: Implement the function count-faucets, which takes a Pipeline and counts the number of faucets it contains.

To do this,

  • Copy and paste the template.
  • Fill in
    • the desired function name (everywhere it occurs),
    • the docstring, and then
    • the examples.
  • Using the examples, replace the placeholders (...) in the template with appropriate code.

Exercise 3

Task: Implement the function count-open, which takes a Pipeline and counts the number of open (that is, running) faucets.

Follow the same steps!

Exercise 4

Task: Implement the function modernize, which takes a Pipeline and converts all the (straight) lead pipes to copper ones.

Hint: You don’t need an if to do this!

Exercise 5

Task: Implement the function off, which takes a Pipeline and turns off all the faucets.

Submitting the lab

  • When you’ve completed the exercises, show your code to your instructor or one of the coaches.

  • Then upload your lab07.arr file to the Lab 7 assignment on Gradescope.

Acknowledgments

This lab includes material adapted from Marc Smith, Vassar College.