Lab 5

For these programs, you may use only "lambda" to define your functions, and the solution to each problem must be a single racket term, defined using a ’define’.

As in Lab 4, I recommend the use of the racket language, rather than typed/racket.

In addition, the solution to each problem must consist *only* of lambda terms with exactly one argument, applications, and variable references. No if, no cond, no numbers, no primitive functions, etc.

Please note that it’s fine to use these things in your test cases, which are otherwise very hard to read.

So, for instance: define a function p1 that takes a value ’v’ and a function ’f’ and just returns ’v’:

;; solution

(define p1 (lambda (v) (lambda (f) v)))

;; test case:

(check-equal? ((p1 8) (lambda (x) 1234)) 8)

Note that the solution doesn’t use numbers, just the test case.

Also note that in order to define a function that "takes two arguments" with the restriction that every function take exactly one argument, you must use currying (as in this example) so that functions accept their arguments "one at a time."

1 Warmup

• Define a function called one that accepts a function and an argument and applies the function to the argument. SPECIAL NOTE: the order of arguments should be as specified: function first, then argument.

2 Continuing on:

1. Define a function called two that accepts a function and an argument and applies the function to the result of applying the function to the argument.

2. Define a function called zero that accepts a function and an argument and returns the argument.

3. Let’s use the term “number-like functions” for functions like zero, one, and two. Define a function called add1 that accepts a number-like function and returns a new number-like function that does the function "one more time". So, for instance, calling add1 with two should produce the function that applies its first argument to its second argument three times. This function should not use racket’s numbers at all, just the number-like functions described above.

4. Define a function called ’add’ that accepts two functions like zero and one and returns a function that applies its first argument to its second argument a number of times that corresponds to the sum of the two ’numbers’ it was given. So, if called with the ’three’ function and the two function, it should produce a function that applies its first argument to its second argument five times.

5. Define a function called tru that accepts two arguments and returns the first one.

6. Define a function called fals that accepts two arguments and returns the second one.

7. Define a function called ’if’ that accepts three arguments. If the first one turns out to be the function tru (as above), it returns the result of the second argument. If the first one turns out to be the function fals (as above), it returns the result of the third argument.

   This function should not use any of racket’s conditional operators (if, cond, etc.)

8. Write a program in PAIG5 that includes the definitions of ‘add‘ and ‘one‘ and ‘two‘ (as defined above), then uses ‘add‘ and ‘two‘ and ‘one‘ to produce ‘three‘, then applies it to a function that doubles a number, and checks that the result is correct.

   In order to write a program in the PAIG5 language before you’ve implemented it, use the "sim" language defined by this module:

   (module sim-PAIG5 racket

   (provide

   [rename-out (#%lam-app #%app)

   (my-with with)]

   #%module-begin

   #%datum

   + - * / = equal? <= =>

   true false)

   (define-syntax (#%lam-app stx)

   (syntax-case stx (? else: blam)

   [(_ blam (args ...) body)

   #'(lambda (args ...) body)]

   [(_ e1 ? e2 else: e3)

   #'(if e1 e2 e3)]

   [(_ e ...)

   #'(#%app e ...)]))

   (define-syntax my-with

   (syntax-rules (as)

   [(with [e as x] ... : eb)

   ((lambda (x ...) eb) e ...)])))

   Don’t change this module definition; instead, write a separate module that’s written in this language, and then require it. For instance, you might write this module in the smae file as the earlier module definition:

   (module my-module (submod ".." sim-PAIG5)

   {+ 4 5})

   ... and then require it (that is, run the code in the module) with this code:

   (require 'my-module)

   When you’re done, make a note of this program; it will make a wonderful late test case for your Assignment 3!

3 Very Hard (Optional)

• Define a function called ’sub1’ that ... well, subtracts one from a ’number’. Yes, it can be done. Yes, it’s quite tricky.

• Can you define a recursive function?