/* CSC 123/252 Assignment: Functional Programming With GCC
In this assignment, unless otherwise noted for a specific program,
your MAY NOT USE ANY OF THE FOLLOWING:

whileloops, forloops, dowhile loops, goto, or any other kind of loop:
YOU CAN ONLY USE TAIL RECURSION. 
The assignment statement that changes the value of a declared variable:
int x = 1; // this is fine and corresponds to (define x 1), (let ((x 1))…
x = x+2; // THIS IS NOT ALLOWED (neither is x=y, x++, ++x, etc.)You can assign to a variable only once.

Pointer notation including *, & and > (as well as pointer arithmetic), except
when otherwise indicated. (You can, however, call cons, car, cdr defined below). 
Any imported data structure/functions. Use only the functions such
as cons, car, cdr as defined in this program.
The idea is to stay as close as possible to pure lambda calculus in C.
However, for this assignment you will use gcc (Gnu C) instead of ANSI C
(clang). Gnu C enables a few more features, including the ability to define
a function inside a function: the inner function is not visible outside
the function in which it’s defined. The inner function also has access
to the local variables of the outer function (variables that are free
in the inner function but bound in the outer function).
The only functions that you can call which are not admissible in pure
lambda calculus are printf and the freelist
function defined below for
deallocating heap memory. Furthermore, these functions should only be
called in main to test your program.
You can declare a variable and give it a value, but you may not CHANGE it.
The assignment statement is a MEMORY OPERATION and is not definable in pure
lambda calculus. All programs that run on real computers, however, must
read from and write to memory. But at the programming language level,
such operations can be hidden. Think about where in a program you will
typically see “x=x+1”: probably inside a while loop. But while loops can
be replaced by tailrecursive calls. The linked list datatype has already
been defined, but you can’t access its internal representation. You can
only use the highlevel functions cons, car and cdr.
The purpose of this assignment is to understand the most important
differences between a highly abstract language and a relatively “low level”
language. You will see that (gnu) C is still capapble of creating powerful
abstractions, much more so than you might think. Ultimately, however,
there will be fundamental limitations to C.
Because C is a statically typed language, but it’s not capable of type
inference, BY DEFAULT, WE WILL ASSUME THAT THE PRIMITIVE TYPE OF ALL
VALUES IS int (sometimes unsigned int). However, we will
distinguish between ints and lists/vectors of ints, as well as
functions that operate on ints (functions are also values that have
a type in C).
Be sure to use gcc (Gnu C). Beaware that the default gcc on Macs is
NOT Gnu C. If you have a Mac, follow instructions on Canvas to
install homebrew and use that to install gcc14.
*/
#include<stdio.h>
#include<stdlib.h>
#define NIL 0
#define BOOL int
typedef unsigned int uint; // convenient name for unsigned int
// The following defines the TYPES OF FUNCTIONS
typedef int (fun)(int); / fun is the type of functions int>int /
typedef int (binop)(int,int); / binary operation on ints, intint > int */
typedef BOOL (predicate)(int); / predicates on integers */
typedef void (action)(); / simple action, no return value */
typedef void (actionon)(int); / act on an integer */
/* refer to programs written in class for more code and examples */
// Basic linkedlist encapsulation
typedef struct cell* list; // linked list pointer
struct cell
{
int item;
list next;
};
list cons(int x, list n) // creates struct on heap
{
list newcell = (list)malloc(sizeof(struct cell));
newcell>item = x;
(*newcell).next = n;
return newcell;
}
struct cell CONS(int x, list n) { // creates actual struct, return on stack
struct cell newcell; // stack allocated struct
newcell.item = x;
newcell.next = n;
return newcell;
}
// list m = cons(2,cons(3,cons(5,cons(7,NIL))));
int car(list m) { return m>item; }
list cdr(list m) { return m>next; }
int cadr(list m) { return m>next>item; } // second item
list cddr(list m) { return m>next>next; }
BOOL isnil(list m) { return m==NIL; } //tests for empty list
void freelist(list m) {
if (!isnil(m)) {
list tmp = cdr(m);
free(m);
freelist(tmp);
}
}//freelist
IN YOUR CODE THESE ARE THE ONLY OPERATIONS YOU CAN CALL ON LISTS:
// cons, car, cdr, isnil and functions defined from them: you may NOT access
// the struct cell encapsulated by these functions (and you won’t have to).
// You may not call malloc/calloc and you can’t use any pointer notation.
// sample functions on lists (similar to lecture examples).
list reverse(list m)
{
// need a stack, initially null
list irev(list m, list stack)
{
if (isnil(m)) return stack; else return irev(cdr(m), cons(car(m),stack));
}
return irev(m,NIL);
}
list map(fun f, list m)
{
list imap(list m, list stack)
{
if (isnil(m)) return stack;
else return imap(cdr(m), cons(f(car(m)),stack));
}
return reverse(imap(m,NIL));
}
// the id is the “leftidentity” of the binary operator, e.g 1 for *
int reduce(binop bop, int id, list m)
{
int inner(list m, int ax) {
if (isnil(m)) return ax; else return inner(cdr(m),bop(ax,car(m)));
}
if (isnil(m)) return id; else return inner(cdr(m),car(m));
}// repeated apply bop to all values of list, returning id for empty list
// thereexists:
BOOL exists(predicate p, list m)
{
return m!=NIL && (p(car(m))  exists(p,cdr(m)));
}// is this tail recursive? TRICK QUESTION
BOOL forall(predicate p, list m)
{
BOOL notp(int x) { return !p(x); }
return !exists(notp,m); //forall x.P(x) == !exists x.!P(x)
}
/* *************** ASSIGNMENT PROBLEMS: *****************
For each problem, write out the program in C and demonstrate how it’s called
in main. I will give you some code in scheme. Linked lists in Elm
works a bit differently because of how error handling is done.
 write the equivalent of the following scheme function, which “doubles up”
each value of a list.
(define (doubleup m)
(if (null? m) m (cons (car m) (cons (car m) (doubleup (cdr m))))))
for example, (doubleup '(1 2 3)) returns '(1 1 2 2 3 3)). This function
is recursive but not tailrecursive. ALL FUNCTIONS AFTER #1 must be tailrecursive.
RECREATE THIS FUNCTION IN C, RESPECTING THE STRUCTURE OF THIS PROGRAM.
1b. Write a tailrecursive version of the doubleup function: wrap the tail
recursive function inside an outer function. You may also want to copy
over the reverse function from above.

define a new type:
typedef void (*actionon)(int);Then define a “foreach” loop construct that works as follows:
void output(int x) { printf("%d ",x); }
foreach(m,output); // would print every value in mIt is possible to use map for printing, but that would be a bit
wasteful because, unlike map, foreach doesn’t need to return anything.
As hint, in Scheme you can define it tailrecursively with(define (foreach m f) ; arguments are list m and function f
(if (not (null? m)) (begin (f (car m)) (foreach (cdr m) f))))The signature (header) of your foreach function should be
void foreach(list m, actionon f);
or
void foreach(list m, void (*f)(int)); // without typedef 
Write a function to print every value in a list using the foreach loop
you created above for problem 2. If you’re not sure of the above, write a
tail recursive function to print from scratch first. 
write a higherorder function ‘howmany’ that takes a predicate
as an argument and returns how many values in a list satisfy the
given property. In scheme, the function should behave as follows:(howmany (lambda (x) (< x 0)) (cons 2 (cons 3 (cons 4 (cons 1 ())))))
should return 2 because there are two negative numbers in the list.Here’s how you’d write the function nontail recursively in scheme:
(define (homany p m)
(if (null? m) 0 (+ (if (p (car m)) 1 0) (homany p (cdr m)))))
;(if (p (car m)) 1 0) evaluates to 1 or 0, which is added to (howmany…)YOUR SOLUTION IN C MUST BE TAIL RECURSIVE and work as in the following
list n = cons(2,cons(5,cons(6,cons(8,NIL))));
BOOL even(int x) { return x%2==0; }
int even = howmany(even,n); // should return 3 (3 even numbers in n)hint: for the (inner) tailrecursive function, the counter should be
passed in as an extra argument. 
write a higher order function ‘filter’ that takes a predicate p and list
m as an arguments and returns a list with just those values in m that
satisfies the predicate. For example, using above definitions,filter(even,n) should return a list consisting of 2,6,8
The order of values in the filtered list is NOT important.

write a function that takes two lists as arguments and returns their
intersection: a list that contains all values found in both lists
(ordering and duplicates do not matter). For example, givenlist m = cons(2,cons(4,cons(6,NIL)));
list n = cons(2,cons(5,cons(6,cons(8,NIL))));
list mn = intersection(m,n); // should return list cons(2,cons(6,NIL))hint: for the tailrecursive function the intersection to be built (mn)
should be an extra argument. 
write a function ‘sublist’ so that sublist(m,n) returns true if every
value in m is also found in n (ordering and duplicates don’t matter),
and returns false othewise.
7b (challenge). Write the sublist function using only the forall and exists
functions. That is, do not write your own recursive function: use only calls
to forall and/or exists.
hint: M is a sublist of N if forall x in M there exists a y in N such that x==y
 The following function applies a ‘binop’ to the values of a list:
int left_reduce(list m, binop op) // assumes m is not empty
{
int iter(list m, int ax)
{
if (isnil(m)) return ax; else return iter(cdr(m),op(ax,car(m)));
}
return iter(cdr(m),car(m)); // will crash if there’s no car
}
For example, given
int subtract(int x, int y) { return xy; }
list m = cons(5,cons(3,cons(2,NIL)));
left_reduce(m,subtract) will return (53)2 = 0.
This function will always assume that binop is leftassociative and only works for
nonempty lists.
Write a tailrecursive version of this function that assumes that binop is rightassociative.
Hint: here’s one that works, but is not tailrecursive
int fold(list m, binop op) {
if (isnil(cdr(m)) return car(m); else return op(car(m),fold(cdr(m),op));
}
fold(m,subtract) will return 5(32) = 4.
Submit all problems with main in one .c file.
*/
int main()
{
list m = cons(2,cons(3,cons(5,cons(7,cons(11,NIL)))));
// why can’t we create a list directly on the stack? We can, but it
// will be painful. We can place the & only before LVALUES. This
// is not feasible except for very short lists:
struct cell D = CONS(8,NIL);
struct cell C = CONS(6,&D); // can’t do CONS(6,&CONS(4,&D))
struct cell B = CONS(14,&C);
struct cell A = CONS(2,&B);
list M = &A; // stack allocated list, painfully created.
int print(int x) {printf(“%d “,x); return 0;}
map(print,reverse(m)); printf(”\n”);
int max(int x, int y) {if (x>y) return x; else return y;}
printf(“largest value in M is %d\n”, reduce(max,0,M));
// don’t call reverse on M as it uses cons to construct list on heap.
// … demonstrate all your functions …
freelist(m);
return 0;
}//main