Scripting Language Design and Implementation

Instructor    Matt Might
TA    Leif Andersen
Office hours: Tues/Thurs, 11:00am - 12:30pm
Online Queue
Course num    16715
Time Mon and Wed, 11:50am - 1:10pm
Location WEB 1230
Appts. Office hours after each lecture, or when my door is open.
Group utah-sldi-spring-2014
Blog (I'll post lecture notes here.)
Class server
Live code live code
Slides slides
Final exam Official schedule



This course has two major co-themes:

The design theme will include a hands-on survey of scripting languages.

New languages will be introduced at a rate of one to two weeks, and assignments will allow students to experience their strengths and weaknesses by programming in them.

For the implementation theme, students will be required to implement an interpreter for a scripting language from scratch.

An understanding of models of computation is a critical prerequisite.

This course is much more difficult than the average computer science course, and may require double or triple the effort.

The time invested will be well worth it: the course will impart a deep, unified understanding of programming languages, and a fundamental appreciation for the nature of computation.

Students will learn how to quickly teach themselves and exploit new programming lanuages.

Languages covered

We aim to discuss most of the following languages in this course:




Your final grade is the maximum of your projects grade and your grade on the exams.

You do not have to take the final if you are satisfied with your grade on the projects.


The first three projects count for 16.7% each and the final project counts for 50%.

Midterm exam

There will be a midterm exam covering concepts thus far in the course.

Everyone is required to take it.

It counts for 50% of the exam grade.

Final exam

The final exam will be impossible to finish in the alloted time.

It will be divided into two portions, each scored separately.

The first portion will cover the same material as the midterm. If you were satisfied with your midterm grade, skip this portion. If you score higher on this portion than on your midterm, it replaces your midterm grade.

The second portion will be on post-midterm material, and it will account for 50% of your final grade.

You should answer those questions which you know best.

The weight of each question is related to the percentage of students that failed to answer it or answered it incorrectly.

The result will be curved.


I'm morally opposed to the way textbooks are priced.

There is no required textbook for the class.

A textbook also cuts against the spirit of this class, which is ultimately about teaching you how to teach yourself a new programming language.

When it comes to learning a programming language, there is a wealth of material available through Google. I will teach you how to find it!

If you'd like recommended (but not required) textbooks, try the following:

I'll link to applicable online material from here, as well as my notes, the slides and any code we use in class.

Preliminaries and prerequisites



Lambda calculus



Lexical analysis



Collaboration policy

I encourage the formation of study groups to discuss the theory and algorithms behind the projects.

You may not share code.

If you want to learn it, you have to implement it.

Violators of this rule will automatically fail the course and be dealt with under the School and University academic misconduct policy.


These projects will be fleshed out in more detail before they're formally assigned. Take them as draft "project ideas" for now.

Depending on how the course evolves and student interest, I may change a later project to a different one entirely.

Project 1: Unix scripting

Released: Jan 15 2014

Due: Jan 29 2014, 5:00 PM Utah time

The description for this project is available on github, along with the stub code.

You will test and turn in this assignment on the class server.

Click here request an account.

Contact Matt if you cannot log in to

Once logged in, run get-p1 to git clone the stub project into $HOME/p1.

Complete the scripts provided in the scripts directory.

To turn in your project, have the most recent version of your project in $HOME/p1 when the due date hits.

My turn-in script will pull all repositories at that time.

Project 2: Implementing regex

Due: March 5 2014, 5:00 PM Utah time

In this project, you will parse and evaluate regular expressions.

A project description, as well as stub code, is available on github.

On the class server, you can run get-p2 to clone the project into your public_html folder. It includes a basic testing framework as well.

It will provide you with a secret URL for viewing your project on the web.


Your code will be in ~/p2/.

Be sure to make back-ups of your project code!


To turn in this project, leave your code in ~/p2/ by the submission deadline.

Project 3: Web script hacking

Due: Wedensday, April 2

In this class, you will get practice compromising simple web applications.

You will compromise an image sharing service, and use that to obtain (and crack) the password for a task-management service.

You can access the web services at:

The auto-grader is available at:

You can measure your progress on the objectives in real time.

For more detailed instructions, read

Bonus Project : Computer algebra

Due: Wednesday, April 2

In this project, you will implement basic computer algebra operations in Racket over the following expression language:

 <exp> ::= <num>
        |  <var>
        |  (+ <exp> ...)             [addition]
        |  (* <exp> ...)             [multiplication]
        |  (- <exp> <exp>)           [subtraction]
        |  (- <exp>)                 [negation]
        |  (/ <exp> <exp>)           [division]
        |  (^ <exp> <exp>)           [exponentiation]

Your task is to complete the stubbed out file alg-stub.rkt so that it meets its specification in the comments.

A reference implementation is also available on hoth as the command alg.

To run it, use:

    $ alg command [args]

And then enter your expression on stdin.

The available commands are:

    derive var

To turn in the assignment, leave it in $HOME/project3/alg-turnin.rkt on hoth.

Running the stub file without any arguments will run 20 test cases.

(Set permissions appropriately to prevent classmates from seeing the file.)

You may want to reference lambda.rkt, a reduction-based interpreter for three languages. In particular, the way it desugars let using three separate functions is a good design pattern for this project.

Pay attention to the provided code. In particular, the function map-exp-bu can spare you having to write recursive tree walks. You can supply it a function that applies local rewrites, and it will apply them to the entire tree!

Also, you can phrase many operations much more simply in terms of repeatedly applying an operation to the whole tree until it reaches a stable value.

Final Project: Implementing an interpreter

Due: April 21, 5:00 PM Utah time

On hoth, implement an interpreter for MicroScheme.

A complete project description with stub code is available.

On hoth, running /home/username/final/bin/microscheme should execute your interpreter.

Your source code should be in /home/username/final/src/