Lab 8h Higher-Order Functions and Live XML

Purpose The purpose of this lab is to provide you some more practice with higher-order functions and with processing intertwined data, as well as to show you how to write small app-like programs with ISL+.

Functions on Functions

Exercise 1 Design the function two that takes a function f : [X -> X] as input and returns another function that applies f twice in a row. That is, two returns a function which first applies f to its input, then applies f again to the output of the first application.

Exercise 2 Design the function three, similarly, that applies f three times in a row.

Exercise 3 Design the functions one and zero. Writing one is easy, but what about zero? What does it mean to apply a function to its argument zero times?

Exercise 4 Design a function rep->nat which consumes a Repeater as input and produces the number of times it repeats its argument. So:

(check-expect (rep->nat zero) 0)

(check-expect (rep->nat one) 1)

(check-expect (rep->nat two) 2)

(check-expect (rep->nat three) 3)

(check-expect (rep->nat (λ (f) (λ (x) ((three f) ((two f) x))))) 5)

Hint If you have a Repeater, all you can do is give it some inputs and see what it gives you back. So your task here is simply to devise some inputs that will force it to tell you which number it represents:

; rep->nat : Repeater -> Nat

; Discover how many times the given Repeater repeats its input

(define (rep->nat rep)

((rep ?) ?))

Exercise 5 Design the function rep-add1 that increments a Repeater by 1.

Exercise 6 Design the function nat->rep that converts a natural number n to the Repeater that repeats its input n times. Use the following data definition to process natural numbers recursively.

; A Nat (natural number) is one of:

;  - 0

;  - (add1 Nat)

Repeaters give us an alternative representation of natural numbers, and the cool part is that we can build them using nothing more than λ. Can we also do arithmetic with them using nothing more than λ?

Exercise 7 Design the function rep+ that takes two Repeaters and returns the Repeater that represents their sum. Don’t use rep->nat, nat->rep, or built-in arithmetic.

Exercise 8 Design the function rep* that takes two Repeaters and returns the Repeater that represents their product. (Again, no rep->nat, nat->rep, or built-in arithmetic.)

Hint It’s shorter than rep+.

Exercise 9 Design the function rep-expt that takes two Repeaters and returns the Repeater that represents their exponentiation: (rep-expt n m) = nm. (No rep->nat, nat->rep, or built-in arithmetic.)

Hint It’s shorter than rep*.

XML

TAs: work through this part with your students.

Sample Problem Design the function x-expression-has-content-attribute, which determines whether some given XExpr has an attribute or contains a (possibly deeply nested) XExpr that has an attribute labeled 'content.

XML Live!

One really cool thing we can do with XExprs is to retrieve data about various interesting things from the internet. For this lab we’re going to try to create a program that checks how much a certain stock is currently worth and displays that information in a big-bang window.

In order to do this we’re going to need to find a way to parse the information in an XExpr so that when we get the XML from the internet we can figure out what it means.

The best way to achieve this is to deal with XExprs similarly to how we deal with structures. That is, we define functions that help us pull out data from XExpr using selector-like functions:

; A [Maybe X] is one of:

; - false

; - X

; XExpr -> [Maybe Symbol]

; Extracts the name of the XExpr if there is one

(define (xexpr-name xe)

(cond [(or (symbol? xe) (string? xe) (number? xe)) false]

[else (first xe)]))

; XExpr -> [List-of Attribute]

; Extracts the attributes from the XExpr if there are any

(define (xexpr-attributes xe)

(cond [(or (symbol? xe) (string? xe) (number? xe)) '()]

[(empty? (rest xe)) '()]

[(loa? (second xe)) (second xe)]

[else '()]))

; XExpr -> [List-of XExpr]

; Extracts the content from the XExpr if there is any

(define (xexpr-content xe)

(cond [(or (symbol? xe) (string? xe) (number? xe)) '()]

[(empty? (rest xe)) '()]

[(loa? (second xe)) (rest (rest xe))]

[else (rest xe)]))

; Any -> Boolean

; is x a list of attributes?

; NOTE: this function cannot be designed with the design recipe for

; structurally recurisve functions from parts I, II, and IV (2e)

(check-expect (loa? 1) false)

(check-expect (loa? 'hello) false)

(check-expect (loa? "world") false)

(check-expect (loa? '()) true)

(check-expect (loa? '((a "1") (b "2"))) true)

(check-expect (loa? '((a "1") 42)) false)

(define (loa? x)

(and (list? x) ; knowledge: x is either '() or (cons ... ...)

(andmap (lambda (candidate-attribute) ; is each item an attribute?

(and (cons? candidate-attribute)

(cons? (rest candidate-attribute))

(empty? (rest (rest candidate-attribute)))

; knowledge: candidate-attribute = (list Any_1 Any_2)

(symbol? (first candidate-attribute))

(string? (second candidate-attribute))))

x)))

Exercise 10 Use the above functions to design the function attribute-value, which consumes a [List-of Attribute] and a Symbol and produces the value of the Attribute with that name if it exists in the list. For example, given the list of attributes '((a "b") (c "d") (e "f")) and the attribute name 'c the function should produce the string "d". If the given attribute is not in the list the function should produce false.

Recall that we are trying to create a program that finds the stock price of a certain stock. The XML information we get back from a site like google.com/finance is going to be large and complex because there is a lot of information stored on that site. Therefore, we need to find out where the "important" information (in this case the price of a stock or the change in price of a stock) is stored within the large XExpr that we read off the web.

Exercise 11 Suppose we want to know the stock price of IBM. We can go to the Google Finance site and enter IBM to obtain a quote. We did so on 15 October 2013 at 13:43:22 and converted the XML into a this XExpr. The price was $184.77. How did we figure it out? What is the symbolic name of the XExpr that holds this data? What attributes does it have?

Now that we know where the price and price change are stored within the XExpr we can extract them by building functions to search for the meta expressions with the itemprop attributes "price" or "priceChange".

Exercise 12 Design the function get-meta-content-pricechange, which extracts the value of the 'content attribute of the meta expression with the 'itemprop attribute "priceChange". Given an XExpr that does not have either of these two properties (the name of the XExpr is 'meta and the 'itemprop attribute has the value "priceChange"), the function returns false.

Hint Do not use the XExpr provided in Exercise 2 as an example. Instead create a small Xexpr with the desired properties.

Exercise 13 Design the function get-meta-content-price which extracts the value of the content attribute of the meta expression with the itemprop attribute "price". Given any XExpr that does not have these two properties (the name of the XExpr is 'meta and the 'itemprop attribute has the value "price") the function should return false.

Hint Do not use the provided XExpr as an example. Instead create a small Xexpr with the desired properties.

Exercise 14 Design the function get-xexpr, which consumes an XExpr and a String and produces a [Maybe String]. The function should extract the value of the 'content attribute of the 'meta XExpr with the 'itemprop attribute value given by calling get-meta-content. Remember to use the selector functions for XExpr.

Hint Design the function get-xexpr-from-list which consumes a [List-of XExpr] and a String and produces a [Maybe String]. The function should search the list for a 'meta expression and if it finds one it should extract the value of the content attribute of that expression. If it does not find one it should return false.

Why is this a hint and not a separate exercise?

We are almost done finding the price and the price change of the stock based on the XExpr we were given by google.com/finance. Now we just need to combine all our functions and alert the user if the XExpr we are looking for does not exist!

Exercise 15 Design the function get which consumes an XExpr and a String and produces a String. The function should extract the value of any 'meta expression it finds with the 'itemprop attribute value given. If it does not find that expression it should return an error that says "No such itemprop attribute : s" for the input string s.

Hint Do not use the provided XExpr as an example.

When you think your functions are ready, copy and paste XExpr and try calling your get function on that with the String value "price" or "priceChange". See if your function works on real data. If not, debug (write more tests and try to find out where your function works and where it doesn’t). It helps to try larger and larger test cases. Start with something simple such as the 'stockinfo expression above and work your way up to the big XExpr given by the site.

When your function works on that you can try it on the live site!

After lab, read the program to understand how it works and to study its style.