8 Program Design via Iterative Refinement

Purpose The purpose of this lab is to practice iterative refinement on a data-complex problem.

Textbook references Part IV: Iterative and Incremental Refinement

Language You may use ISL+ if you are comfortable with lambda, but it is also perfectly okay to use ISL.

Introduction

5 minutes

Iterative refinement is the process of developing a program or product by starting with a simplified version of a problem or scenario and adding detail and functionality to it bit by bit. It is used in any setting (besides and including software development) where the requirements of a product or problem may not be well-defined at first, necessitating the development of a functional but incomplete prototype and its gradual re-development over time as additional requirements become known.

As a method, it originated in scientific research. For example, when "Programmers are computer scientists" anyone? scientists develop a model based on experimental data and later refine it over time as new observation data reveal inaccuracies in the predictive powers of the model.

In Fundamentals 1, we have used iterative refinement to design a more and more complete evaluator for ISL+ and expand our Gobbler game. In this (still simple) setting iterative refinement takes the form of either revising a set of data definitions or creating additional functionality for existing data definitions. What these refinements usually boil down to is the design of new functions or the enhancement of existing ones.

You should know by now that in order to succeed with iterative refinement, it is of highest importance to follow the design recipe in your data and functions. Otherwise you have no chance of recognizing when what and how to change your code base.

Social Networks

20 minutes

Social networks are a good real-world example of complex, mutually recursive data. In today’s lab, we will work with a simplistic representation of a social network, Matthias does not belong to any social network. If it’s free, you are the product. vaguely modeled after Google Plus. If you have never heard of Google Plus, that’s okay, it’s like Facebook, a hangout for old people.

In this model, users may connect with other users in the network by classifying them as either friends or enemies. These connections are more like Instagram followers than Snapchat friends, meaning that they are unidirectional and not necessarily reciprocal: When a user A adds another user B as a friend or enemy, B does not have to have A as a connection. See the examples of User below for clarification.

(define-struct user [name friends enemies])

; A SocialNetwork (SN) is a [Listof User].

; A User is a

;    (make-user String [Listof String] [Listof String])

; interpretation name is the user's nick name,

; friends is a list of (the names of) their friends, and

; enemies is a list of (the names of) their enemies.

(define amanda

(make-user "Amanda" '("Carlo" "Diya" "Fran") '()))

(define bruce

(make-user "Bruce"

'("Carlo" "Diya" "Emmi" "Fran" "Han")

'("Fran" "Diya" "Carlo")))

(define carlo

(make-user "Carlo" '("Diya" "Han") '("Amanda")))

(define diya

(make-user "Diya" '("Emmi" "Fran" "Han") '("Fran" "Carlo")))

(define emmi

(make-user "Emmi"

'("Fran" "Han")

'("Carlo" "Diya" "Bruce" "Fran" "Han")))

(define fran

(make-user "Fran" '("Gregg" "Han") '("Amanda" "Carlo")))

(define gregg

(make-user "Gregg" '() '("Han" "Bruce" "Fran")))

(define han

(make-user "Han" '("Gregg") '("Bruce" "Carlo")))

(define SN1 (list amanda bruce carlo diya emmi fran gregg han))

The above data definitions and examples, as well as a few "library functions" for string list manipulation, are provided here, so don’t start from scratch.

Exercise 1 Design a function, remove-user, that removes a given User from a SocialNetwork.

Exercise 2 Design a function, count-friendships, that counts the number of other users in a SocialNetwork who consider a given user to be their friend.

Code Review

10 minutes

The Teaching Assistants will pick a pair who will explain a solution to their lab mates following the design recipe steps.