Assignments for CIS 624 (Programming Languages)

/cs/classes/cis624/submit files

This will copy all of the files you specify to a directory where I can get them. You can "unsubmit" any of the files:

/cs/classes/cis624/usubmit files

You can keep doing this as many times as you want as long as your final work has been submitted by the deadline.

Regular Assignments

• Assignment 7 (Types)
• Assignment 6 (Objects)
• Assignment 5 (Exceptions)
• Assignment 4 (CPS)
• Assignment 3 (Scheme in Java II)
• Assignment 2 (Scheme in Java)
• Assignment 1 (Simple Java Programming)

Solved Extra Credit Problems

1. The C preprocessor expands macros using a process superficially similar to beta reduction but that does not rename bound variables. Write a C macro which illustrates the problem of name capture. Try the same macro in Scheme and compare the results.
   • Solution by Jim Suruda

Open Extra Credit Problems (accepted any time)

1. Research how continuations can be used to implement backtracking; provide an implementation and an example.
2. Research how continuations can be used to implement coroutines; provide an implementation and an example.
3. Research other applications of continuations in non-standard domains: GUIs, operating systems, etc.
4. Write the Y combinator in Java and use it to write a non-recursive factorial function.

5. The Y combinator can be used to express recursion in the lambda-calculus. There are many other combinators that perform various useful functions. Research the S, K, and I combinators, find out their significance, and prove that SKK=I. Research other combinators that are used to express recursion in the lambda-calculus and prove that they satisfy the same equation as Y, namely YM=M(YM).

6. Provide solutions to some of the "interesting" problems in previous midterm exams. You might have to explain your solutions to me or to the class.

7. Provide solutions to some of the "interesting" problems in the book or in the continuations paper. You might have to explain your solutions to me or to the class.

8. Take your favorite recursive function, convert it to CPS using functions to represent continuations, choose another representation for continuations, and show your new representation is correct.

9. Look at the Church-encoding of numerals in the lambda-calculus. Explain how the predecessor function works. Try writing an interesting function like the square root function.

10. Write a function that automatically converts a subset of Scheme programs to continuation-passing style.

11. Write a recursive version of Quicksort that sorts a list of ints. Convert your solution to CPS, and then to an iterative algorithm.
    You should get code that looks like the COBOL program from Augusta's article (handed out in class 04-23).

12. The original "Devils and Angels" problem is due to Dan Friedman. He formulated the problem as an extension to the interpreter. Do this original problem: Number 10 in Friedman's Applications of Continuations paper (handed out in class 04-23).