Course Description

CS 3360 is a required course for a BS in computer science at University of Texas at El Paso. The primary goal of CS 3360 is to study the design and implementation that underlay the programming languages. In previous courses, students have examined how to write programs in individual languages such as C, Java, and Python. In this class, we will take a broader view of programming languages, and study the key concepts and techniques that allow developers to implement languages such as Python.

Certainly, there are social and personal preferences to choose programming languages. But there is also a body of principles that allow us to discuss and think about languages in a rigorous manner. We study these principals because a language affects the way one approaches problems working in that language and affects the way one implements that language.

We will deep dive into programming languages by constructing increasingly complex syntax and semantic features. Our goal is to build an interpreter for a toy language taken from the subset of ML languages. We will see that interpreters are the basis for realizing computation, and we will study the programming language theory that enables us to reason carefully about a language's design and implementation.

The course covers many aspects of using, understanding, and reasoning about programming languages (e.g., syntax/grammar, semantics, environment, scoping, inductive data types, type inferences, functional computations, logic, and probabilistic programming).

Course Objectives

Upon completion of this course, students will be able to:

• Students will be able to learn new languages quickly and select a suitable one for your task.
• Students will gain new ways of viewing computation and approaching algorithmic problems.
• Students will gain new ways of viewing programs.
• Students will gain insight into avoiding mistakes for when you design languages.

Course Topics

• Basic Introduction to Scala and Functional Programming
• Recursion and Tail Recursive Programming
• Pattern Matching and Inductive Definition
• High-Order Functions: Map, Reduce (Fold), Filter
• Introduction to Context-Free Grammar, BNF, and Abstract Syntax Tree
• Parser and EBNF Form
• Syntax for Arithmetic Expressions
• Big Step Semantics for Arithmetic Expression
• Intro to Lettuce, a functional language with Let bindings and Scoping.
• Describe and Implement the Syntax of Lettuce: Arithmetic Expression, Let binding, and Conditions.
• Define and Implement Semantics Rules for Basic Lettuce.
• Lettuce with Functions and Function Calls (Closure).
• Lettuce with Recursive Functions (Inductive Environment).
• Calling Conventions, Currying, and Continuation Passing Style (CPS).
• Lettuce with Side Effects (Imperative Programming Paradigm).
• Lettuce with Explicitand Implicit References (store and reference variables).
• Lettuce with Type: Mechanisms for Type Checking in Lettuce.
• Lettuce with Type Inferences.
• Introduction to Logic Programming.
• Case Study: Programming Tax Law with Prolog.
• A short Introduction to Probabilistic Programming Languages.

Acknowledgment: This course is adapted from the fantastic programming languages courses at CU Boulder by Dr. Sriram Sankaranarayanan and Dr. Bor-Yuh Evan Chang. Special thanks to Sriram and Evan for their assistances and help in preparation of materials.