# CS 32: Programing in Racket

Programing exercises in this course are developed using DrRacket (formerly known as DrScheme). DrRacket supports a language called racket, a descendant of a language called scheme, which in turn was derived from the classic language for artificial intelligence called LISP. Think of LISP as the grandmother, scheme as the mother, and racket as the daughter. DrRacket can also be used to develop languages in a variety of dialects of scheme (e.g., R5RS).

To get started, download and install Racket from www.racket-lang.org. Automatic installers exist for Linux, Microsoft Windows, and Mac OS X. (If you have trouble installing the software, please consult with the professor or teaching assistant.) When you first run DrRacket it is advisable to select a language dialect from the Language menu that appears along the top of your display. For our applications to run optimally, select Choose Language …, and then select “PrettyBig” under “Legacy Languages” from the drop-down menu. Since the distinction between racket and scheme is minimal,

Almost all of the information that you need to use DrRacket will be given in your lecture and laboratory sessions. We actually will need only to understand a small fraction of racket and scheme in this course. More information for the curious student is available at the bottom of this page.

## Some Example Programs

• factorial.rkt The factorial function, defined recursively by $n! = 1$, if $n=0$ and $n\cdot (n-1)!$, otherwise. So, for example, $7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5040$ enumerates the number of ways that $n$ distinct objects can be permuted, e.g., the number of anagrams that can be created using $n$ distinct letters of the alphabet. We will use this formula and function pattern often.

• doomsday.rkt implements John Conway’s Doomsday algorithm for finding the day of the week of any date in the Gregorian calendar. A random-date function, also generates random dates for students to test their ability of applying the algorithm using mental arithmetic.

• binomial.rkt computes binomial coefficients, which are the numerical values that appear in Pascal’s triangle.

• unscramble.rkt solves simple jumble, or word scramble, puzzles: e.g., find a word in the dictionary that is an anagram of naanba. This program requires a dictionary (web2) of English words.

• factorial_variations.rkt displays over a dozen variations of the factorial function, including count, count-up, count-down, gcd (the greatest-common divisor function), lcm (the least-common multiple function) reversi, delete, drop, take, swap, and iterate.

• clone.rkt creates an exact copy of a list. This task is not particularly useful. However it is helpful to learn the pattern of taking something completely apart, and then putting it back together again, as variations of this pattern can lead to impressive and useful applications.

• anteater.rkt is a simple variation of clone that swallows every ant that is visible in the argument list, leaving everything else alone.

• alchemy.rkt is a simple variation of clone that turns every piece of lead in the input list into gold, leaving everything else intact.

• randomsearch.rkt simulates the behavior of a drunken mouse in a maze.

• shuffle.rkt simulates a perfect shuffle of a deck of playing cards.

• tremaux.rkt simulates the behavior of a CS 32 student in the Great Vermont Corn Maze.

• harry_potter_game.rkt implements a graph-based game of adventure with a Harry Potter theme. The topology of the graph, the room titles, and room descriptions can be modified, allowing students to create similar games with other themes. To invoke the game evaluate (play) in the interaction window. A separate function, theseus implements a depth-first search algorithm in a given graph.

• dfs_pegsolitaire.rkt uses a depth-first search algorithm (a more efficient version of Tremaux) to solve our one-dimensional pegsolitaire puzzle, with an arbitrary number of pegs.

• hanoi.rkt solves the Tower of Hanoi puzzle.

• graphsearch.rkt demonstrates how a single function graph-search can be used to solve four different problems: threading a maze, solving a one-dimensional peg solitaire puzzle, solving the Tower of Hanoi puzzle (although not so efficiently), and solving the missionaries and cannibals puzzle. A common algorithm is facilitated by reducing each puzzle to its state-transition graph.

## Online Documentation about Racket and Scheme

• http://docs.racket-lang.org/ contains information about DrRacket and the racket programming language.
• The Schematics Scheme Cookbook provides numerous recipes for PLT Scheme (the immediate ancestor of racket).
• How to Design Programs is an introduction to computer programming, written by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi, the developers of Racket (formerly, DrScheme). The full text is available online. Highly recommended!
• The syntax of the scheme programming language is concisely described in R. Kent Dybvig’s The Scheme Programming Language, second edition, Prentice-Hall, Upper Saddle River, NJ, 1996. (The link should direct you to an on-line copy of the textbook.)
• The textbook Structure and Interpretation of Computer Programs by Harold Abelson and Jay and Julie Sussman, is available on line. It is used as an “introductory” textbook at MIT, and is based on scheme.