CSCE 330: Programming Language Structures (Fall 2015)

Prerequisites: CSCE 240 and either MATH 374 or MATH 174

Section 1: TTh 1315--1430 SWGN 2A31

Section 2: MW 1640--1755 Horizon Parking Garage 210

Instructor (Section 1): Marco Valtorta
Office: Swearingen 3A55, 777-4641
E-mail: mgv@cse.sc.edu
Office Hours: MWF 1100-1200 and by appointment

Instructor (Section 2): James O'Reilly
E-mail: oreillyj@email.sc.edu
Office Hours: MW 1500-1630

Any student with a documented disability should contact the Office of Student Disability Services at (803)777-6142 to make arrangements for proper accommodations.

Syllabus

Grading Policy

Reference materials:

Hector J. Levesque. Thinking as Computation. The MIT Press, 2012 (required text, referred to as [L]). Supplementary materials from the author are available.

Graham Hutton. Programming in Haskell. Cambridge University Press, 2007 (required text, referred to as [U]). Supplementary materials from the author, including an errata list, are available. Here is the direct link for Chapter 11 ("The Countdown Problem") lecture. Here is the direct link for the countdown program code, in literate Haskell format.

The current departmental syllabus lists the following outcomes of instruction for this course:

Categorize a language as imperative (procedural), functional (applicative), or declarative (logic).
Generate and use syntax descriptions in EBNF.
Write code in a functional language (e.g, Haskell)
Write code in a logic language (e.g., Prolog)

Specific objectives of this course are:

Provide a historical overview of programming languages and their features
Introduce a logic programming language (Prolog)
Introduce a functional programming language (Haskell)
Describe (semi-)formally syntax and semantics of programming language constructs

If time allows, we will also study the run-time behavior of block-oriented, statically-typed imperative languages.

Lecture Log

Lecture Notes

Homework, Tests, and Programs
Final exam from 2013

Some notes and examples for the fall 2015 midterm, courtesy of James O'Reilly
Programs and related notes follow.

Predicates describing a solar system; similar in difficulty to predicates for HW3 (family predicates from ch.4[L])
Description of the brainbasher puzzle
Prolog code for the brainbasher puzzle, solved using the generate and test approach described in ch.5[L] and applied in HW4 from ch.5[L].
Some examples of list predicates (cf. ch.7[L])
A program that applies list predicates
List reversal using an accumulator
Description of the list reversal program using an accumulator

See the lecture log for assignments not listed below.

Grading policy per assignment
Please include examples of use for Prolog assignments. The examples of use should address all types of queries or predicates that you are asked to write. You may create a log of an SWI-Prolog session using protocol/1 and noprotocol/0. See www.swi-prolog.org/FAQ/MakeLog.html.
Please include examples of use for Haskell assignments.
Solutions for the exercises from Hutton's book are easily available. Please, on your honor, do not consult them.

Midterm from 2012 edition of the course (with some changes) (MS-Word format).

Prolog Information

Haskell Information

Student Presentation

Quizzes (In-Class Exercises)
Quiz 1 of 15-08-27 (in pdf format, with answer)
Quiz 2 of 15-09-01 (in pdf format, with answer)
Quiz 3 of 15-09-08 (in pdf format, with answer)
Quiz 4 of 15-09-22 (in pdf format, with answer)
Quiz 5 of 15-10-29 (in pdf format, with answer) (This quiz was erroneously called Quiz 6 in the version handed in class.)
Quiz 6 of 15-11-19 (in pdf format, with answer)

Some useful links:
In this class, we write dates according to ISO Standard 8601.
Brian Hayes. "The Semicolon Wars." _American Scientist_, July-August 2006, pp.299-303. Local copy, pdf.
Philip Wadler, "Monads for Functional Programming" (pdf, local copy; bibliographical details at the bottom of the first page). Chapter 5 (especially starting with section 5.2) mirrors the presentation in Chapter 8 [H]. The beginning of Section 5.4 specifies the unit and * operations needed to define a monad. The discussion at the beginning of Section 5.12 explains that these operations have the monad properties, and therefore the parsers of Chapter 8 [H] are monads: "The empty parser and sequencing correspond directly to unit and *, and the monads laws reflect that sequencing is associative and has the empty parser as a unit. The failing parser and alternation correspond to zero and (XOR), which satisfy laws reflecting that alternation is associative and has the failing parser as a unit, and that sequencing distributes through alternation."
Repository of Code for: Cristina Videira Lopez. Exercises in Programmign Style. CRC Press, 2014.
Parnas D.L. (December 1972). "On the Criteria To Be Used in Decomposing Systems into Modules" (PDF). Comm ACM 15 (12): 1053-1058 (local copy).
Derek Partridge and Yorick Wilks. "Does AI Have a Methodology Different from Software Engineering?" Technical Report MCCS-86-53 (1986), Computing Research Laboratory, University of New Mexico (local copy).
Computer Language History web site by Eric Levenez
The Ariane 5 launch disaster.
Local copy of: Adrion, W.A., M.A. Branstad, and J.C. Cherniavsky. "Validation, Verification and Testing of Computer Software." ACM Computing Surveys, 14, 2 (June 1982), pp.159--192.
Local copy of: Rajlich, V., N. Wilde, M. Buckellew. and H. Page. ``Software Cultures and Evolution.'' _Computer_, 34, 9 (September 2001), pp.24--28.
C.A.R. Hoare. "Retrospective: An Axiomatic Basis for Computer Programming." _Communications of the ACM_, 52, 10 (October 2009), pp.30-32.
C.A.R. Hoare. "An Axiomatic Basis for Computer Programming. _Communications of the ACM_, 12, 10 (October 1969), 576-580.
John McCarthy. "A Micromanual for LISP---Not The Whole Truth." ACM SIGPLAN Notices, Vol. 13, Issue 8 (August 1978), Pages 215-216 (local copy)
The Simplesem interpreter: unzip, and follow the instructions in readme.txt. This is a Java implementation that seems robust and will run in Windows.
Carter Bays's FP interpreter
John Backus. "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs." Communications of the ACM, 21, 8 (August 1978), 613-641
John Backus: Function Level Programming and the FL Language: a 1987 lecture on FP by John Backus.
Boyko Bantchev's List of Interviews with Programming Language Creators from Computerworld's series "The A-Z of Programming Languages (pdf)
A to Z of Programming Languages Index
J.W. Backus. "The 701 Speedcoding System." Journal of the ACM, 1, 1, pp.4-6, 1954 (local copy).
A site with a short program written in many languages, not including FP.
A site with another short program written in several languages..
Examples of APL code
John McCarthy, developer of LISP, wins the Franklin Medal
John McCarthy's Obituary from the _New York Times_, 2011-10-25 (local copy).
Dennis Ritchie's Obituary from the _New York Times_, 2011-10-13 (local copy).
Joe Armstrong. "Erlang." Communications of the ACM, Vol. 53 No. 9 (September 2010), Pages 68-75.. This article describes the notion of dynamic code upgrade.
Pascal Rigaux's Diagrams of Programming Language History.
Eric Levenez's Genealogy of Programming Languages.