Course Outline

Description

What is computation? This is the question that birthed Computer Science as a discipline, and serves as the focal point of this course. Our plan for answering it is twofold. First, we will introduce functional programming through Scheme (a dialect of Lisp). Unlike imperative languages, functional programming tends to emphasize techniques such as lambda functions, higher-order functions, recursion, and the use of immutable data. We will explore each of these techniques, and discover their significance in diverse contexts.

Second, we will use our understanding of functional programming to explore the nature of computation itself. This will involve reading parts of Alonzo Church’s revolutionary article, “An Unsolvable Problem of Elementary Number Theory.” We will see how the notion of computation emerges from his understanding of functions, and engage with the fundamental conjecture of Computer Science: the Church-Turing Thesis.

This course is interdisciplinary in nature: we shall be learning skills in Computer Science (functional programming); but we will also be using these skills to explore serious questions at the nexus of Computer Science, Mathematics, and Logic. By the course’s end, you will understand the principles of functional programming, and their connection to computation. Additionally, you will gain insight into the Church-Turing Thesis and its foundational role in the discipline of Computer Science.

No previous experience in Computer Science, Mathematics, or Logic is necessary to take this course. However, you will be programming in Scheme and reading challenging texts in theory of computation; so your learning will be well-supported by having already taken a course that emphasizes symbolic thinking. For this reason, at least one course in Computer Science or Mathematics is a prerequisite.

Topics include: function composition, higher-order functions, lambda functions, recursion, primitive recursive functions, mu-recursive functions, combinatorial logic, fixed-point combinators, the Church-Turing Thesis, computation.

Learning Outcomes

1. Grasp the Principles of Functional Programming: By the end of the course, you will be proficient in writing, debugging, and analyzing functional programs in Scheme, utilizing constructs like lambda functions, higher-order functions, and recursion.
2. Understand Church’s Account of Computation: You will work through Church’s paper on lambda functions, and be able to articulate the relationship between functions and computation, highlighting its significance for computational problems.
3. Grapple with the Church-Turing Thesis: You will consider, critique, and form perspectives on the Church-Turing Thesis, appreciating its pivotal role in bridging the realms of Computer Science, Mathematics, and Logic.
4. Connect Functional Programming to Computation: You will draw connections between specific programming constructs (such as fixed-point combinators) and overarching theories of computation, emphasizing the relationship between theory and practice.

An overarching objective of this course is to help you develop as a student of the liberal arts. True students of the liberal arts are able to reflect on the context in which they live, and reason about what it means to live a meaningful and happy life. Thus, they are able to be more than just children of their own time. But this means we must be willing to put our ideas to the test, see our own errors, and develop intellectual courage and humility. It also helps not to take ourselves too seriously.

Readings

1. Church, Alonzo. “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics, Vol. 58 No. 2 (April 1936), 345–363. Online.
2. Eberbach, E.; Wegner, P. “Beyond Turing Machines,” Bulletin of the European Association for Theoretical Computer Science, No. 81 (October 2003), 279–304. Online.
3. Harvey, Brian, and Matthew Wright. Simply Scheme: Introducing Computer Science, 2nd ed. Cambridge: MIT Press, 1999. Online. Available in the Dickinson reading room.
4. Nonaka, Ayaka. “The Y-Combinator (no, not that one): A crash course on lambda calculus,” Medium, September 10, 2014. Online.
5. Rojas, Raul. “A Tutorial Introduction to Lambda Calculus,” arXiv, 1503.09060 (March 2015).
6. Shapiro, Stewart. “The Open Texture of Computability,” in Copeland, Jack B., Carl J. Posy, and Oron Shagrir, Computability: Turing, Gödel, Church, and Beyond. Cambridge: MIT Press, 2013. Online through the library. On reserve at the library. Available in the Dickinson reading room.
7. Smith, Peter. An Introduction to Gödel’s Theorems, 2nd ed. Cambridge: Cambridge University Press, 2013. Online. Available in the Dickinson reading room.

Evaluation

• Exercises and Writing: Short exercises and writing assignments will be given in coördination with the current topic, and comprise your portfolio. All written submissions should be submitted as PDF, with program code attached as appropriate. Please put your last name and assignment number in the filenames, as well as in the text of the file.

• Final Project: You will propose and complete a group project in coördination with the professor. A proposal must be approved in order to submit your final project. See below for details about possible projects.

• Oral Examination: The examination is comprehensive and will be a series of oral questions, related to the topics covered in the course.

Portfolio Assignment #1

Portfolio Assignment #1 is due on Thursday, March 28. In preparation to submit your portfolio, please submit (in groups of two) the following exercises:

• Concepts
  1. For the following, define the concept, provide an example, and explain how the example is an instance of the concept (written; about 1/2 page typing minimum of each): Compound expression; “=” versus “equal?”; semipredicate; Higher-order function; Lambda as a special form.
• Exercises: 8.8, 8.11, 8.12, 8.14
• Exercises: 9.11, 9.14, 9.15, 9.16
• Extend Tic-Tac-Toe game (from Chapter 10) to a 4x4 game

Fill out the Portfolio Cover Sheet for Assignment #1, and follow the submission instructions on that sheet.

Portfolio Assignment #2

Portfolio Assignment #2 is due on Thursday, May 16. In preparation to submit your portfolio, please submit (in groups of two or three) the following exercises:

• Concepts
  1. For the following, define the concept, provide an example, and explain how the example is an instance of the concept (written; about 1/2 page typing minimum of each): Beta reduction (in lambda calculus), conditional test (in lambda calculus), standard definition (of primitive recursive functions), extensionality (of functions).
• Exercises (from Simply Scheme): 14.11, 14.12, 14.14, 14.15, Project: Spelling Names of Huge Numbers
• Lambda Calculus
  1. State the lambda expression equivalent to NAND.
  2. Consider the following formulae in lambda calculus. Do they have a normal form? Why or why not?
     • ((((λabx.((ax)(bx)))(λmn.(n m)))(λn.z))p)
     • (λb.((λa.((λx.(a(xx)))(λx.(a(xx)))))b))
• In one to two pages (double-spaced, regular margins) articulate and explain the diagonalization argument (from section 14.5 of Smith) as if you were explaining it to a first-year student. Are there any reasons to think that it does not hold?

Final Project

Your final project is an exploration of a particular topic in computer science that is connected to our course in some way. You will complete your final project in a group of two or more. The project should be a substantive piece of work that correlates with the weight given in the course. Beyond this, there are no preëstablished guidelines: you submit make a proposal for your final project before the midterm break.

Project proposals should be no more than one page in length (single spaced), and should consist of the following: (i) a list of who is going to be involved in the final project; (ii) a brief description of the final product (be it an analysis, a commentary, a program, or some other work), including the steps you will take to complete the project; (iii) a bibliography of works that you intend to consult as part of the project. Note that the bibliography need not be long, and it also does not bind you: you may go beyond these works if you choose.

Here are some examples of final projects:

1. A detailed commentary on Church’s paper where he introduces lambda calculus.
2. An implementation of Shor’s Algorithm (quantum factoring) in Scheme.
3. An analysis of Gandy’s generalisation of the Turing Machine.
4. An analysis of Ada Countess of Lovelace’s Note E.
5. A set of exercises from the initial chapters of SICP.
6. A commentary on linear recursion and tail recursion in Scheme.
7. A set of exercises from the Simply Scheme chapters we do not cover.
8. A commentary and exercises for the initial chapters of Neural Networks and Deep Learning (caution: some partial differential equations).

Tentative Schedule

Resources

Reading Questions

• For Harvey’s Simply Scheme
• For Church’s “An Unsolvable Problem of Elementary Number Theory”

Install Racket and the Simply Scheme Package

We will be using the Racket language as an integral part of this class. You will need a fully-fledged computer (not just a mobile device) to fully participate. Dickinson 235 has computers with Racket installed if you do not have your own.

1. Download Racket from here: http://download.racket-lang.org. There are versions for all modern Macs, Linux machines, and Windows. Open the downloaded file (probably called: racket-8.x-aarch64-macosx-cs.dmg on an Apple Silicon Mac, racket-8.x-x86_64-macosx-cs.dmg on an Intel Mac, or racket-8.x-x86_64-win32-cs.exe on a PC).
   • On a Mac, open and drag the folder to Applications.
   • On a PC, run the installer.
2. Start DrRacket.
   • On a Mac, this is in the Racket folder of your Applications list. If your computer complains that DrRacket is not from a “trusted developer,” you may have to go into the Finder, then Applications, then right-click DrRacket, and click “Open” to bypass this. You only need to open it this way once.
   • On a PC, this is in the Racket folder of your Applications list.
3. Install the simply-scheme package by opening the “File” menu and selecting “Install Package…”. In the field labelled “Package Source” enter “simply-scheme” and click Install.
4. When the package has installed, click Close. You will now be able to write in the language by starting your code with “#lang simply-scheme”.
5. You can find documentation for package by opening the “Help” menu and selecting “Racket Documentation”. Then in the “… search manuals …” box, enter “simply-scheme” and select “simply-scheme”. Or, you can find the documentation online.

Downloading and Using Functions.scm

1. Here is Functions.scm, which you will need to complete Chapter 2 of Simply Scheme.
2. Follow the link, and copy the contents of the text file into the definitions window. Click “Run” in DrRacket.
3. In the interaction window, type (functions) to start the program.

External Links

1. Electronic Whiteboard: For information sharing during class
2. Code from Class: A listing of code we worked on during class
3. Lectures on Simply Scheme: by Brian Harvey, coäuthor of our textbook
4. SICP Website: Text and exercises
5. Land of Lisp: Music Video
6. Land of Lisp Comic: Scroll to the (very) bottom to see the “Secrets of the Seven Guilds”
7. Xkcd: Lisp Cycles: Elegant weapons for a more civilized age
8. Scheme Style Guide: Suggested style for Racket programs
9. History of Lisp: by John McCarthy, creator of Lisp
10. How Lisp became God’s Own Programming Language: by Sinclair Target
11. Beating the Averages (Lisp as a secret weapon): by Paul Graham
12. Ada Lovelace Obituary: New York Times, 2018
13. Computing Machinery and Intelligence: by Alan Turing
14. Consciousness in Human Robots and Minds: by Daniel Dennett
15. They’re Made out of Meat: A short story by Terry Bisson

Additional Information

1. This course outline is subject to arbitrary change. I shall announce any changes in class; if you are not present, you are still responsible for finding out what I announce.
2. Late assignments will not be accepted without an acceptable medical or compassionate reason. Assignments are due according to deadlines on this course outline.
3. You must attend classes regularly and on-time. Penalties for unexcused absences and for lateness will factor into the class grade. Two unexcused absences are grounds for a marginal pass, and three are grounds for failure, even if all you other work is good.
4. Office hours are first-come-first-serve, unless you have an appointment. If you request an appointment by email, please send me a selection of several times you are available.
5. Please be aware of the college policies on class attendance, as well as academic and artistic ethics. You must declare any work you submit that is generated in part or whole by AI.
6. If you are being graded, your mark in the course will be translated into a letter-grade, according to the following scale: A (85–100), A– (80–84), B+ (77–79), B (73–76), B– (70–72), C+ (67–69), C (63–66), C– (60–62), D (50–59), F (0–49). Your grade will not be otherwise curved or adjusted.