COS 371: Programming Languages
Spring 2022
hw4: First-class functions
Due: Monday, 02/21 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 functionf
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
usingcurry2
. (compose f g)
Takes two 1-parameter functionsf
andg
and returns a function that isf
composed withg
. Thus,((compose f g) x)
returns the result of(f (g x))
.(negate predicate)
Takes a 1-parameter predicatepredicate
and returns a predicate that is the negation ofpredicate
. Thus, exactly one of(predicate x)
and((negate predicate) x)
is true.
4. Optional Challenges
(curry n)
Takes a positive integern
and returns a function that curriesn
-parameter functions. In other words,(curry 2)
iscurry2
. One could say thatcurry
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) +))
definesadd5
as a curried version of+
that can be used like this(((add5 1 2) 3) 4 5)
- Extend
compose
andnegate
to the case whereg
andpredicate
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.