CSC 4980/6980, Functional Programming (Fall 2026)

Homework 2 (Due: 27 September - Sunday)

sudo handin4980 2 file1 ...

1. Using the Lambda Calculus implementation in Python, write a lambda expression, {\tt mlist}, for merging two sorted lists of Church encoded numbers. Then, write a lambda expression, {\tt mergelists}, that will use the {\tt ycomb} operator to merge two sorted lists. Examples of two sorted lists are given below:

   	listA = ((cons one) ((cons three) ((cons five) nil)))
   	listB = ((cons two) ((cons four) nil))
   

   Since the result of merging two sorted lists will be a sorted list of Church encoded numbers, write a lambda expression, {\tt displayListOfNumbers}, that would convert a list of Church encoded numbers to a Python String representing the corresponding list of ordinary numbers. This way, we can easily verify if the merging of two sorted lists is coded properly! Submit a new version of {\tt startupLambda.py} in which these new lambda expressions are included at the end of the file.

2. Solve the challenging programming problem in Section ``IV. A CHALLENGING PROGRAMMING ASSIGNMENT'' of the ``Pure Functional Programming in Python'' paper.

   Here is a template of the code you should use. Complete the implementation of the functions convert2ra and parseF.

   $ more DLOG.py
   # takes in as input a pair rname_args = (rname,args):
   #   rname is the relation name and
   #   args is a list of arguments of the form ("str",val) or ("num",val) or ("var",val)
   #     where val is one of it's arguments
   # and returns the relational algebra string corresponding to rname and args.
   def convert2ra(rname_args):
     pass
     return result
   
   # takes as input the input string, parses for it's different components and returns
   # relation name and a list of arguments as describe above.
   def parseF(data):
     pass
     return rname, arguments
   
   # main function
   def main():
     while True:
       data = input('\nDLGAtom: ').strip()
       if data == 'exit':
         break
       print(convert2ra(parseF(data)))
   
   main()
   

   What to submit?

   DLOG.py