20 Homework 12B

Due:

Thursday, 4/4 at 9PM

This assignment is SOLO, and entirely AUTOGRADED.

What to Download:

hw12b.rkt

Please start with this file, filling in where appropriate, and submit your homework to the HW12B assignment on Gradescope. This page has additional information, and allows us to format things nicely.

20.1 Resources in Programs

Many data that exist in programs can be logically thought of as resources, which usually means there are specific rules of how they are created and disposed of. In particular, there is often an idea that they may only be able to be duplicated under specific circumstances (if at all). This is in contrast to most program values which can be freely copied, irregardless of what they stand for.

The example that we’ll use in this assignment are items in a video game inventory. While an item could be represented as a struct, like:

If an inventory were defined as:

(define-contract Inventory (List Item~))

There is nothing that prevents a bug in the code from accidentally duplicating items. Instead, we’ll represent items with an affine contract, as follows:

What this means is that each item in the list is wrapped behind a check that only allows the value inside to be accessed once.

Of course, once the item has been extracted from the inventory, it can be copied, so this should not be seen as a security mechanism. Rather, systems like this (of which one of the most successful is the memory ownership system in the programming language Rust) are intended to make it easier to write correct code so that intentions can be encoded directly into patterns that get enforced, rather than merely relying on conventions.

20.2 Problem 1

One of the key ideas in resource programming is to provide restricted access to necessary operations. One that you might want to do is transform all items in the inventory; effectively, performing a map, but this has to deal with the Single abstraction, accessing & creating new affine values. Implement the following function:

20.3 Problem 2

Transforming every item is sometimes useful, but often, what you want to do is select some items and remove them from the inventory. This seems like it should be like filter, but if you implemented it with a normal signature:

(: inventory-filter (-> Inventory (-> Item~ Boolean) Inventory))

There would be a problem: accessing the items to check the predicate consumes them, so while you could reconstruct the items in the output Inventory, if you tried to copy the Inventory and filter it multiple ways, it would not work, since all the items in the original Inventory would have been consumed by the original traversal. As a result, any item not returned by inventory-filter would be lost, which is most likely not what you want!

Instead, a better abstraction in an affine setting would be to partition: to return two lists: one for which the predicate returned #t, and the other for which it returned #f.

Implement that function:

Hint: you probably want to define a helper function with one (or two!) accumulators.

20.4 Problem 3

Just like partitioning is a better abstraction than filtering in the context of resources that cannot be freely copied, if you want to get an element out of a list, rather than just writing a function like:

(: inventory-get (-> Inventory (-> Item~ Boolean) (Maybe Item~)))

Which will have the same problem as filter: the rest of the Inventory will be consumed and thus be unusable, you should write a function:

Hint: you should be able to use inventory-partition to accomplish this.

20.5 Problem 4

Now, with a few helpers for working with Inventorys, let’s implement a function that could actually show up in the game logic. Let’s imagine the game allows some mechanism of "crafting" – i.e., using certain items to create other items. Clearly, this should involve consuming the input items and producing the new output items, so the resource abstraction is a good one.

In this case, we’d like you to write a function that looks for two Item~ with name "wood" and one Item~ with name "stone" and produces a new Item~ with name "hammer". If there are not two "wood"s and one "stone", it should return the Inventory "unchanged" (note: that means it should have the same elements, all accessible).