CS 378: Symbolic Programming
Spring 2019: TTh 2:00 - 3:30 in GDC 5.302, Unique No. 51135.
Gordon S. Novak Jr., GDC 3.824; Office Hours: TTh 3:30 - 5:00 PM,
or any time my door is open.
TA: Ankur Garg
Office Hours: Monday 11-12 at TA Desk 1 and Thursday 10-12
at TA Desk 2 in GDC basement.
Daniel Higginbotham, Clojure for the Brave and True
Each student is required to buy/rent an iClicker (any version of iClicker
device; not iClicker GO app). This will be used for attendance
and to reinforce and practice with the class material. Two iClicker
points are given just for voting, and an additional point is given
for a correct answer. Most iClicker questions and answers are online at
Clicker Questions, and it is
okay to review them in advance. The clicker scores will be converted
to a grade by making the highest student score at least 108 and
linearly scaling other scores; this gives some extra points to account
for minor illness, forgotten or malfunctioning clicker, etc.
Do not bring another student's clicker to class.
Grades on Canvas
Register your iClicker on Canvas.
Follow CS 378 Discussions on Piazza
Signup Link for Piazza
Lecture Notes: Available in printed form in GSB 3.136.
Online by Contents or
Symbolic Programming involves the manipulation of symbolic data
such as programs, equations, rules, and natural language (human
languages such as English). Symbolic programming is increasingly
being used in real applications by large companies such as
Bloomberg and Walmart.
Symbolic programming provides several advantages:
Students will write a number of interesting programs that will provide
practice and expertise in symbolic programming.
- Flexibility. Bloomberg uses symbolic representations of
derivative securities to allow users to answer what if?
- Rapid programming. Understanding how to manipulate symbolic
structures can allow interesting programs to be constructed
easily and quickly.
- Modularity. Symbolic programs can be plugged together with
- Parallelism. Symbolic programs work well with modern
web-based and cloud-based systems.
- Explanation. Symbolic programs can explain and justify their
- Automatic Programming. Programs can write programs.
Topics to be Covered:
- Tree Representation and Tree Recursion
Most of the languages we use (programming languages, math, English)
are structured as trees; the printed representation is easily generated
from the trees. To manipulate languages, we need to manipulate the
trees rather than the surface structure.
Given an expression, and values of variables, find its value. Bloomberg
represents derivative securities as expressions and uses evaluation
to answer what if questions.
- Pattern Matching
Pattern matching allows declarative programming in terms of transformations
or rewrite rules. Rather than specifying steps of how to do something
as in ordinary programming, we specify that a certain pattern should be
replaced by another pattern, with variable substitutions. This allows
tasks such as symbolic math and program transformation to be done easily.
- Symbolic Math
Symbolic math is manipulation of expressions, such as equations, to form
new expressions. Whereas a numeric program calculates the answer to one
problem, symbolic math provides an answer to a class of problems.
- Code as Data: Programs that Write Programs
Program components can be composed to form programs that accomplish
a desired task.
- Program Translation
Given a program expressed in the form of a tree, it is fairly easy
to translate it into code in various programming languages.
- Functional Programming
Functional programs return values but do not have side effects
such as changing global variables or printing. This makes it easy
for a functional program to be replicated on parallel computers and
used as a plug-in to other programs.
- Backchaining and Prolog
Backchaining takes rules of the form A ∧ B ⇒ C .
Given such a rule, one way to prove C is to prove both A and B,
recursively. If A, B, and C are programs, this can find a way to solve
a desired problem by combining existing programs.
- Rule-Based Expert Systems
Expert systems perform a diagnostic task (e.g. deciding whether to
approve a loan application) based on symbolic rules. The rules can
be inspected by humans and can be used to generate explanations
of the conclusions that are reached.
- Semantic Grammar and Natural Language Interfaces
While English is highly ambiguous, the phrases used in an application
area usually have a clear meaning. By writing a grammar specialized
to an application such as database access or physics problems,
it is fairly easy to produce a natural language interface to a program.
- MapReduce and Hadoop
MapReduce (Google proprietary) and Hadoop (an open-source version based
on Java and available through Amazon web services) allow functional
program plug-ins to operate in parallel on massive amounts of data.
MapReduce handles all the hard stuff, and the functional plug-ins are easy.
Turn in via Canvas
- Lists and Trees in Clojure
- Symbolic Algebra
- Physics and Code
- Program Synthesis by Deduction
- Expert Systems
- Natural Language Interfaces
All programming assignments must be your own individual work.
Program files are provided,
FTP directory for Program Files,
for use with the assignments. The files are described by
Program File Descriptions.
It is legal to use any of these files as part of your programs.
Lisp / Clojure Functions
Using Emacs with Clojure
Emacs Command Summary
Tracing in Clojure
Testing and Debugging
Study Guide for Midterm Exam
Examples of Function Calls
Study Guide for Final Exam
Grades are kept on
It is your responsibility to check your grades often to
make sure that your assignments have been received and graded.
Course grades are assigned on the scale A = 93-100, A- = 90-93,
B+ = 87-90, B = 83-87, B- = 80-83, etc.
provided that the Final Exam grade is at least 65; if the Final Exam
grade is below 65, a lower course grade may be assigned at the
instructor's discretion. Grades are averaged using the following weights:
|Midterm Exam || 15% ||
|| Thursday, March 14, in class|
|Final Exam || 25% ||
||Friday, May 17, 2-5 PM|
|Clicker Participation|| 10% |
|Programming Assignments: || 50% ||
Quotes from Alan Perlis
Tech at Bloomberg: Mr. Varun Kohli, Software Engineer, Derivatives Pricing
Simon Peyton Jones, Jean-Marc Eber, Julian Seward, Composing Contracts:
an Adventure in Financial Engineering, ACM SIGPLAN Int. Conf.
on Functional Programming (ICFP'00) pp. 280-292, 2000.
- PowerPoint slides for above
- How to write a financial contract, in The
Fun of Programming, ed Gibbons and de Moor, Palgrave Macmillan 2003
Is There a Smarter Path to Artificial Intelligence? Some Experts Hope So
- The Great A.I. Awakening
Stickel, M., Waldinger, R., Lowry, M., Pressburger
T., and Underwood, I., "Deductive Composition of
Astronomical Software from Subroutine
Libraries", in 12th Conference on Automated
Deduction, Nancy, France, June 28-July 1, 1994. In
Automated Deduction, A. Bundy, ed.,
Springer-Verlag Lecture Notes in Computer
Science, Vol. 814.
local copy PS (447 KB),
Fig. 1: Where is the shadow of Io on Jupiter?
- G.S. Novak,
Conversion of units of measurement
- New York Times Article on Hadoop
- Lecture slides on PageRank
Simple MapReduce in Java
Lisp Functions in Java