CS 135: Designing Functional Programs


CS 135 covers only part of the features that Racket provides, and only part of the techniques, concepts, and applications of functional programming. At the end of each assignment we have placed at least one extra credit question, followed by a number of optional challenges. These explore areas we don't have time for in class, ranging from relatively short or simple questions to topics that are conceptually difficult and suggestions for extended projects. We would be happy to discuss any of this material with you, or examine and give you feedback on your solutions. You can't earn extra credit for the optional challenges, but you can earn something more valuable: additional understanding and insight.

Here are some enhancements that have been used in past terms and will likely be used in the future.

  • I/O (not covered until CS 136)
  • animation
  • generating Web pages
  • arithmetic on unbounded integers
  • proving program fragments correct by induction
  • image manipulation through conversion to lists of pixels
  • dynamic Web page generation facilitated by quasiquote, unquote, unquote-splicing
  • Wolfram's cellular automata
  • evaluating Racket expressions (Racket interpreter)
  • The halting problem (easier to talk about with Racket knowledge than in CS 360!)
  • beginning of lambda calculus, Church numerals (CS 442 material)
  • drawing program using GUI primitives
  • chat program using networking primitives (both use callbacks)
  • Eliza (primitive AI simulation of psychotherapist)

Here are enhancement topics that in past terms were delivered in supplementary lectures in CS 136, continuing with advanced features of the Racket language:

  • memoization and the Y combinator
  • issues in domain-specific languages (DSLs) via example of slideshow program
  • macros as means to define DSLs (hide syntax, delay argument evaluation)
  • a second example (defining and running finite state machines) with "interpretation" versus "compilation" approaches to this problem
  • transforming Racket programs so that they will work on the Web
  • using capturing of continuations in Racket to avoid the need to transform, with specific application to "natural" Web scripts
  • uses of continuations (e.g. breakpoint debugging facility, exception-handling, threads and message-passing)
  • lazy evaluation and "infinite" data structures

Last modified on Friday, 27 April 2018, at 19:04 hours.