COS 371: Programming Languages

Spring 2020

hw4: First-class functions

Due: Monday, 02/24 at 22:00

This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should code your own assignment.

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.

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