CSci 658: Software Language Engineering
Fall 2013
Syllabus (Modified 10 October)

Locations

The fall semester 2013 class meets in 235 Weir Hall at 4:00 p.m. to 5:15 p.m. on Tuesdays and Thursdays.

The class is taught by Prof. Conrad Cunningham, whose office is in 203 Weir Hall. The official office hours for this class are 1:00 to 2:30 p.m. on Mondays and Wednesdays and by appointment at other times.

Prof. Cunningham's voice telephone number is (662) 915-5358 and fax number is (662) 915-5623. His WWW home page is http://www.cs.olemiss.edu/~hcc/ and his email address is cunningham ATSIGN cs DOT olemiss DOT edu.

The WWW home page for this class is http://www.cs.olemiss.edu/~hcc/csci658/.

The final examination for this class is scheduled for Wednesday, 11 December at 4:00 p.m..

Student Disabilities Services Statement

"It is the responsibility of any student with a disability who requests a reasonable accommodation to contact the Office of Disability Services (915-7128). Contact will then be made by that office through the student to the instructor of this class. The instructor will then be happy to work with the student so that a reasonable accommodation of any disability can be made."

Course Description from Catalog

Study of topics on the design, implementation, use, and evolution of artificial languages for the engineering of software. Languages of interest include general-purpose programming languages, domain-specific languages, and modeling languages as well as application programming interfaces and collections of design patterns that implicitly define languages.

Prerequisites

Graduate standing in computer science

Course Outcomes/Objectives

Upon successful completion of this course, students:

1. know and understand the fundamental concepts and techniques of the Lua programming language
2. can analyze a problem and synthesize a solution using functional programming techniques in Lua
3. (added) know and understand the concepts and techniques of data abstraction and can incorporate them into Lua programs
4. know and understand the concepts of tables and metatables and can implement modules and object-oriented programming facilities in Lua
5. (added) know and understand the concepts of domain-specific languages (DSLs) and can apply basic techniques for implementing internal DSLs in Lua
6. know and understand the basic concepts of parsing expression grammars and the LPEG library and can use the library to implement simple languages
7. know and understand the structure of interpreters and can modify or implement interpreters for simple languages
8. (removed, not enough time) know and understand the concepts of coroutines and can implement "concurrent" programs in Lua

Motivation

Linguistic abstraction is at the core of computing science. As computing scientists, we should be able to solve problems and express the solutions in a variety of programming paradigms. We should understand how programming languages work. We should be able to design and implement simple languages to assist us in our work.

This course seeks to deepen our understanding of the concepts and techniques for the design, implementation, and use of programming languages. It uses the dynamic application programming language Lua as both an object of study and a tool for implementing languages.

Lua is appropriate for this purpose. Its developers want to keep the core language simple but enable users to extend it by adding new features via host language (e.g., C) libraries. They also want to enable users to embed Lua functions and programs within host language applications. They want Lua to have an implementation that is small, efficient, and portable.

To help achieve these goals, the Lua developers adopted the principle of separating mechanism from policy. That is, Lua provides "meta-mechanisms for implementing features, instead of providing a host of features directly in the language" [http://www.lua.org/about]. For example, Lua is not natively an object-oriented language, but its first-class functions, tables, and metatables enable several different implementations of classes and inheritance. We can study these different techniques--and perhaps design our own--to get a concrete understanding of how object-oriented languages work.

Although Lua is primarily a procedural language, it supports programming in multiple paradigms. Its lexically scoped, first-class functions (closures) and tail recursion (tail call) elimination enable functional programming. Its closures, tables, and metatables enable both modular programming and object-oriented programming implementations. Its closures, first-class coroutines, and generic-for construct enable goal-directed programming. Its coroutines enable cooperative (nonpreemptive) multitasking natively. In combination with host language thread libraries, its coroutine and state maintenance facilities enable a variety of "shared-nothing" concurrent programming approaches to be implemented.

Lua also supports language-oriented programming by means of its add-on LPEG text-processing/parsing library. LPEG provides a set of composable operators to parse languages defined by parsing expression grammars. This library is efficient and subsumes the functionality of regular expression processors. But it supports parsers for a class of languages similar to those definable by context-free grammars. Thus LPEG should enable the processing of small languages such as external domain-specific languages (DSLs).

Lua should thus be effective for processing the simplified languages used in interpreter-based approaches to programming language organization courses. These languages are often Lisp-like languages using parentheses to specify the structure of the program expressions. We can use the implementation of such languages to help us explore programming language design and implementation concepts.

Samuel Kamin's textbook Programming Languages: An Interpreter-Based Approach (Addison Wesley, 1990) examines a variety of programming languages by first building an interpreter for a core Lisp-like language and then modifying it to process languages with a similar syntax but differing semantics (meaning). Although Kamin's languages were implemented in Pascal and C (and later in C++ by Timothy Budd), the instructor recently developed a prototype of Kamin's core, Lisp, and Scheme language interpreters in Lua using LPEG to build the parser. We can use this implementation (and others we may build) to study key concepts of programming language design and implementation.

Source Materials

Selected Course Textbook:

Roberto Ierusalimshcy. Programming in Lua, Third Edition, Lua.org, Rio de Janiero, 2013.

(The bookstore may not be stocking this course. You can buy from Amazon for less than $30.)

Course Topics

The course is expected to cover most of the following topics. Of course, this list is subject to refinement as the semester progresses.

1. Fundamental Lua concepts
2. Functions and closures
3. Functional programming
4. Tables and metatables
5. Implementing data abstraction and modules
6. Implementing object-orientation (classes, single/multiple inheritance)
7. (Added) Internal domain-specific languages
8. LPEG library and parsing
9. Implementing simple languages
10. (Not covered) Coroutines and iterators
11. (Not covered) Concurrency

Professional Conduct

As a student in CSci 658, you are expected to conduct yourself in a professional manner according to the Honor Code of the School of Engineering, the Information Technology (IT) Appropriate Use Policy, the M Book, and any other relevant policies.

Limited Collaboration Policy. Unless otherwise indicated, any homework assignment or programming exercise given in this class will be an individual assignment. The work you submit is to reflect the knowledge, understanding, and skill that you have attained as an individual. However, the instructor does want to encourage the development of a community of scholars who are actively engaged in discussion of the ideas related to this course. With this in mind, you are allowed to discuss solutions of the homework and programming problems with other students if done so according to the following guidelines:

• You may discuss ideas for homework and programming assignments with your classmates. However, you cannot collaborate on writing the solution or the program code. That is, you can talk about the problems and ideas for solving them, but you cannot write things down with anyone else. You are, of course, prohibited from copying or seeing another student's written solution, and you are not allowed to show your work to anyone else. Similarly, you are not allowed to copy text or program code from a book or a page on the Web unless explicitly authorized to do so by the instructor.

• You should accept help with care. If you work too closely with another student, you might mislead yourself into believing that you understand the concepts and techniques better than you actually do. Don't forget that the instructor has office hours and can probably give you hints or suggestions to get you started.

• You should give help with care. Do not help anyone too much. When you have solved a problem, it is tempting to just tell other students how you solved it. Instead, try to allow them to come to the solution on their own. Maybe give them a hint to help them get "over a hump." Remember that helping someone too much will hurt them in the long term if they can't work through problems on the exams by themselves. So avoid the temptation to do so. If you can't help other students without giving away the whole solution, direct them to see the instructor (who may or may not have a way to "edge" them toward the solution).

• You are not obligated to help anyone. If you feel uncomfortable helping another student for any reason, please direct them to see the instructor.

• Except as described above, all work in this class is covered by the School of Engineering's Honor Code statement on plagiarism. It is plagiarism "to knowingly deceive, copy, paraphrase, or otherwise misrepresent your work in a manner inconsistent with professional conduct".

Grading

The grading scale for this class is A [90..100], B [80..90), C [70..80), D [60..70), and F [0..60). However, the instructor will be using the +/- grading scale, as appropriate, to provide more fine-grained grading within these ranges.

Modified 10 October. Thirty percent of the semester grade will come from the exam grade and seventy percent from the homework assignment/project average.

Assignments and Projects

• All students are expected to study the relevant portions of the textbook and handouts in conjunction with our class discussions (i.e., before coming to class). Explicit reading assignments will not always be given. If in doubt on what you need to read, please ask the instructor.
• Approximately four homework assignments are planned for the semester. Some of the assignments may be called "projects" and have more credit than the "regular" assignments.
• Unless otherwise stated in the assignment description, an assignment is to be carried out by each individual student without inappropriate collaboration with others. See the section on Professional Conduct.

• In preparing and submitting homework assignments make sure that:
  • your name, the course number or name, the assignment identifier, and individual exercises are clearly indicated in the content of the file or on the paper. (If it is a group assignment, give the group identifier and the names of all members.)
  • for any handwritten portions, you write legibly on only one side of the paper in a black or blue pen or dark pencil. Do NOT use red or green ink! Some of the assignments may require that materials be generated with a word processor and/or other tools.
  • your pages are stapled together in the upper left corner when viewed from the front.

• Several programs will be assigned during the semester. We will use the multiparadigm programming language Lua, unless otherwise directed.

For these exercises, you will need to submit appropriate design documentation, a listing of your program code, and appropriate printed output from your program testing. Make sure that you clearly label the assignment as described above. You will also be asked to submit your program source code in electronic form using Blackboard.

• As appropriate, there may be a few in-class assignments or quizzes that count toward the assignment/project portion of the grade.
• The programs and other assignments given to students enrolled in the course for graduate credit will often differ from the ones given to undergraduates. In particular, the assignments will often include components that are required for graduate students but optional for undergraduates.
• All students are expected to complete their homework assignments by their due dates. If an assignment is submitted late, a penalty of 10 percent of that assignment's grade will be assessed for each day it is late. A homework paper will not be accepted after graded papers have been returned, after a solution has been distributed, or after the final examination.

Examinations

• Modified 10 October. There will be only one examination. The exam will be scheduled sometime in the period from mid-November until the final exam period.
• The exam will cover all topics studied to that point.
• The exam may consist of a combination of in-class and take-home components.
• If you cannot take an examination at the scheduled time because of an illness or other special circumstances, please notify Prof. Cunningham in advance. Without advance notification, it may not be possible to give a make-up examination.

UP to CSci 658 root document?