CS 251: Programming Languages

Fall 2017

hw4: First-class functions

Due: Monday, 09/25 at 22:00

This is a pair programming assignment. If you are on a team, this means that you and your partner should be doing the entirety of this assignment side-by-side, on a single computer, where one person is "driving" and the other is "navigating." Set a timer to swap every 15 minutes, say. You can choose your favourite from this online timer page. Make sure your sound volume is audible, but not so loud to disturb the people around you.

1. Goals

To not discriminate against functions and treat them as first-class citizens.

2. Introduction

In some languages, functions are a special thing. They can be invoked with values and return values. However, they themselves are not values, so functions cannot be created by other functions, passed as arguments into other functions, or returned by other functions. In Scheme, lambda expressions create values just like any other expression, so functions are first-class citizens. It is therefore our moral obligation to avoid treating them differently.

A function that takes multiple arguments can be curried into one that takes the arguments one at a time. For example, a curried function to handle multiplication of two numbers can be defined as

(define mult
  (lambda (a)
    (lambda (b)
      (* a b))))

Note that mult is a 1-parameter function that takes an input a and returns a function, which takes an input b and multiply a and b together. In other words, (mult 23) is just the function

(lambda (b)
  (* 23 b))

A higher-order function is a function that takes one or more functions as arguments or returns a function. So mult is a higher-order function since it returns a function.

You are to implement a pair of higher-order functions that perform (un)currying.

3. Specification

• (curry2 f)
  Takes a 2-parameter function f and returns a curried version of that function. Thus, (((curry2 f) x) y) returns the result of (f x y).
• (uncurry2 f)
  Takes a curried 2-parameter function and returns a normal Scheme uncurried version of that function. Thus, ((uncurry2 f) x y) returns the result of ((f x) y).
• Define mult using curry2.
• (compose f g)
  Takes two 1-parameter functions f and g and returns a function that is f composed with g. Thus, ((compose f g) x) returns the result of (f (g x)).
• (negate predicate)
  Takes a 1-parameter predicate predicate and returns a predicate that is the negation of predicate. Thus, exactly one of (predicate x) and ((negate predicate) x) is true.

4. Optional Challenges

• (curry n) Takes a positive integer n and returns a function that curries n-parameter functions. In other words, (curry 2) is curry2. One could say that curry is a higher-order higher-order function, since it returns a higher-order function.
• Extend curry so the curried functions can partially apply one or more arguments, instead of just one argument. For example,

  (define add5 ((curry 5) +))
  

  defines add5 as a curried version of + that can be used like this

  (((add5 1 2) 3) 4 5)
  

• Extend compose and negate to the case where g and predicate are not necessarily 1-parameter functions. Of course, f must still be a 1-parameter function.

5. Submission

Submit your code in a file called first-class.scm. We will be grading this using Moodle's anonymous grading capabilities, so make sure that your names are not included in your file.

Start early, have fun, and discuss questions on Moodle.