Question

A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list): (define (make-mobile left right) (list left right)) A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile: (define (make-branch length structure) (list length structure)) a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch. b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile. c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced. d. Suppose we change the representation of mobiles so that the constructors are (define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure)) How much do you need to change your programs to convert to the new representation?

Short answer

Selectors extract components from compounds; total weight sums structures' weights; balance checks torque equality; new representation alters selectors minimally.

Step-by-step solution

Define Selectors

To solve part (a) of the problem, we need to define selectors for extracting the left and right branches of a mobile, as well as the length and structure of a branch. Using lists as the constructors: 1. Define the left-branch selector to get the first item of the list representing the mobile. 2. Define the right-branch selector to get the second item of the list representing the mobile. 3. The branch-length selector returns the first item of a list representing the branch. 4. The branch-structure selector returns the second item of the list representing the branch.

Calculate Total Weight

For part (b), define a procedure called `total-weight` that computes the weight of the mobile. Follow these steps: 1. Use the branch-structure selector to check if a structure is a number (simple weight). 2. If the structure is a mobile, recursively calculate the total weight of its left and right branches. 3. Continue recursing until you reach simple weights and sum all of them to get the total weight of the mobile.

Define Balanced Predicate

Part (c) requires us to define a predicate to check if a mobile is balanced:1. Calculate the torque for both the left and right branches using the formula: \( \text{torque} = \text{branch length} \times \text{total weight of the structure} \).2. Check if the torques are equal.3. Ensure that any submobiles are also balanced by applying the balanced predicate recursively to the branch structures.4. The mobile is balanced if both torques are equal and all submobiles are balanced.

Adapt to New Representation

For part (d), determine how to adjust the definitions for the new constructors using `cons`: 1. Since `cons` creates pairs, adjust the selectors to use `car` and `cdr`. 2. The left-branch and right-branch selectors will become `(car mobile)` and `(cdr mobile)`, respectively. 3. Similarly, for branches, use `(car branch)` for length and `(cdr branch)` for structure. 4. These changes translate to simple replacements, showing the selectors need minimal alterations for the new representation.

Key concepts

Compound Data

Compound data is an essential concept that allows us to group related data together into a single structure. In the case of a binary mobile, we use compound data to represent branches and the overall mobile structure. A branch combines two pieces of information: its length and its hanging structure. This could be another mobile or a simple weight.
To create a binary mobile with compound data, we rely on a constructor function like `make-mobile`, which takes two branches (left and right) and combines them into a single list. Similarly, each branch is constructed with `make-branch`, which pairs the length of the branch with the structure hanging from it. This encapsulation simplifies handling the mobile, enabling easy access and manipulation of its individual parts.

Selectors

Selectors are functions that allow us to extract specific pieces of data from compound data structures. In our exercise, we need selectors to access the left and right branches of a mobile, and the length and structure of each branch.
For example, `left-branch` and `right-branch` selectors can be created to access the first and second elements of the list representing the mobile. Similarly, `branch-length` extracts the length of the branch, while `branch-structure` retrieves the hanging structure.
These selectors are important because they provide a way to interact with complex data structures without needing to know their internal representation details, adhering to the principle of data abstraction.

Recursion

Recursion helps us to solve problems by breaking them down into smaller sub-problems of the same type. When it comes to calculating the total weight and checking the balance of a binary mobile, recursion greatly simplifies the process.
The `total-weight` function, for instance, uses recursion to calculate the weight. If the branch structure is another mobile, the function calls itself to compute the weight of this sub-mobile, summing up the weights until reaching simple weights.
Similarly, the predicate to check if a mobile is balanced uses recursion. It compares the torque of branches, which is the product of branch length and its structure's total weight. This balance check recursively applies to sub-mobiles, ensuring every part maintains balance.

Data Abstraction

Data abstraction hides the complexities of data structure, providing a simpler interface to interact with the data. In our binary mobile example, abstraction is achieved by using constructors and selectors.
Instead of dealing directly with lists or the specific implementation details, we use functions like `make-mobile` or `make-branch` to create structures and selectors to retrieve their components. This allows for changes in the underlying data representation without affecting how the data is used elsewhere.
For instance, switching from list-based representation to using `cons` for constructing mobile branches requires only minimal adjustments in our selectors to use `car` and `cdr` instead of list indexing, showing the flexibility provided by data abstraction.