CSC 254 2014 Programming Language Design and Implementation

CSC 254 2014 Programming Language Design and Implementation


Teaching staff and office hours

  • Instructor: Prof. Chen Ding, CSB 720, ext. 51373
  • Grad TA: Jake Brock, jbrock@cs. [city we live in] .edu
  • Grad TA: Kevin Hu, hxy9243@ [the letter after f]
  • Lectures: Mondays and Wednesdays 2-3pm @ Georgen 108
  • Office hours
    • Ding: Fridays 11-12pm and by appointment @ CSB 720

Textbook (required)


  • Programming Projects:  70%
    • Meaning of Life: 2%‚Äč
    • Compiler:  75%
      • Tokenizer:  10%
      • Calculator:  20%
      • Parser:  20%
      • Intra-Function Generator:  20%
      • Inter-Function Generator:  30%
    • Singularity: 13%
    • Language Extension:  10%
  • Midterm Exam:  15%
  • Final Exam:  15%

Course description

Today's programmers face a wide range of programming language features. For efficiency in embedded systems, one may use static data structures and macros. For extensibility in prototyping, one may favor polymorphic operations and encapsulated modules. For resource sharing and aggregation, one may design a parallel and distributed system. Quite often, the program demand at hand is a mixture of many requirements, and the appropriate solution is probably a combination of several languages/systems.  To made such decision, you need to understand how programming languages work.

This course will focus on the design, implementation, and composition of core constructs in procedural, object-oriented, and functional languages while at the same time covering basic material on syntax analysis, semantic analysis, and code generation. The teaching is styled as a process of problem solving and learning by doing. Students will build a compiler for a C-like language, and an interpreter for Lambda calculus, and (release) new modules for real languages such as Ruby, Python, and R.

The material of this course is covered by its textbook, supplemented by lecture slides and other reading material. I will emphasize concepts and tools that are most relevant to building composable and reusable software. For this reason, I will focus on high-level language implementation and leave out most assembly-level issues. Drawing from my research, I will include in lectures recent advances in safe parallel programming.

Course schedule

  • schedule added 9/15/2014 (future updates in file 254F14schedule.pdf in the class repository.)

Course Repository - Mercurial Version Control Software

Course Repo

For this class, we will be managing all code in version control software (Mercurial).  All provided assignment code will be distributed using this software, and all projects will be turned in using it  (so please make sure you understand how to use the software!)

What is version control?

Version control software allows several people to work on and share a project, while also providing a method of recovering previous version in the case of problems.  In this class, we will be using Mercurial (also known as hg). 

On the undergrad network, we will host a shared repository, which holds all class code.  On your personal machine, you can check out a copy of this code into a local folder, modify it, and then check it in.  To save changes to the code, you commit, taking a snapshot of your progress and creating a save point you can go back to.  To copy the code to your local machine is called a pull, whereas to send in your changes is a push

In Mercurial, we can keep track of changes to the project in branches.  Branches allow different versions of a project to exist independently - for instance, two developers might try two vastly different (and incompatible) methods of implementing a new feature.  While they are stilll developing, their changes should be isolated from the main project - after all, we shouldn't add features until they work.  Eventually one might be accepted into the main project, at which point we will merge their changes with the main (default) project.

In our class, we will release assignments on the default branch in the class repo.  Each student will have their own branch.  When we release assignments, you will merge the assignment into your branch.  When you complete the assignment, you will commit your changes and push the code back to the shared repository.

Some more resources on Mercurial:

  •     Mercurial's "Beginners Guides", where you can go for instructions on downloading and tutorials.
  •     Mercurial's "Quick Start Guide", for when you have it installed and are ready to "clone" the repository.


Setting up your local repository:

Before you start, make sure that you have an account on If you need an account, please see MartyGuenther.

First, we need to configure hg to use associate your name when tracking code changes, and to trust files belonging to the teaching staff.  To do this, create a file in your home directory ~/.hgrc and add the following:
username = First, Last <>

users = cs254, jbrock, cding, xhu9

Second, create a directory to keep your local repository.  For instance, on Linux:
mkdir cs254

Third, navigate to this directory:
cd cs254

Fourth, clone the shared repository onto your local machine:
hg clone ssh://

Go into that directory

cd cs254hg

Next, create a new branch with your name:
hg branch myusername

Commit that change, and push it:
hg commit -m 'made [myusername] branch'
hg push --new-branch

Getting Course Material:

Since assignments are released on the default branch, you need to merge the assignment code into your branch.  To do this, first make sure you are on your branch:
hg checkout myusername

Next, pull the changes to the repository, including the new assignment:
hg pull

Finally, merge the changes from the default branch into your branch.
hg merge default

If you take a look in your repository now, you'll see the new assignment.

Submitting assignments:

To submit an assignment to the repository (remember, the one submitted via TURN_IN is the one that is turned in), first make sure you have added all your files to the repo:
hg add somefile.txt
hg add someotherfile.txt
hg add makesureyouaddallyourfiles.txt

And saved your changes in a commit, and provide a comment to make sure you (and the TA) know what it is your are committing:
hg commit -m "A commit message, e.g. Finished hwk01"

Next push your changes to the remote repository so the TA can grade it:
hg push

Additional reading


Homework 1: Calculate the Meaning of Life (Due Tuesday, Sept. 9, 11:59pm)

Consider the following short program, "Meaning of Life".

#include <stdio.h>
int const N = 1000000;

double Calculate(double meaning) {
  for (int i=0; i<N; i++) 
      meaning += 0.000042;
  return meaning;

main () {
  printf("The meaning of Life is ");
  printf("%.0f.\n", Calculate(0.0));
Rewrite "Meaning of Life" such that the new program computes the "meaning of life", while never overwriting a variable (though you may initialize variables).  Also, you may not declare extra variables beyond what is in the example program.  You can use Ruby, C, C++, or Java (if you use C/C++, test the program both with and without compiler optimization).  I recommend that you change the constant N to be a smaller number as an intermediate step, then use the large N and see what happens (whether you get the same results).
Write a brief report in no more than two pages (plain text is preferred).  I do not want you to explain why the two programs behave differently.  You will understand the underlying cause later in this class.  For this assignment, I want you to think about and articulate what you see are some of the basic issues in language design as evidenced by this experiment.  It should have two sections:
  1. Describe your new program (source code is fine) and the result you observed.
  2. Based on your observations, discuss what you see are the basic problems in language design and what is the role of language implementation.
Update: Submit with TURN_IN script as follows!


Submit by putting your work in a folder and using the following command from a lab computer (it is fine if you are ssh'd into the lab computer too - but some people have had trouble with ssh, so don't wait until the last minute to try):

"/u/cs254/bin/TURN_IN [my_folder_name]".

In class this looked like "/u/cs254/bin/TURN_IN ." because "[dot]" refers to the current directory.

FYI, the TURN_IN script compresses the entire specified directory and then sends it to me, labeled with its date and time.  If you submit and then wish to change your work, you may resubmit as much as you like up until the deadline (your friendly TA will grade the last submission prior to the deadline).

End of Update.

When you are finished, be sure you are in your branch of the repository, and place your homework in the folder "cs254hg/assignments/hwk01" with the file name.  It is very important that you get this right, so that your friendly TA can get your homework out with a script instead of fishing around for it.  Once your homework is in the correct location of your branch, submit it like so:
  1. "hg add [each file you want to submit]" or "hg add hwk01" to add everything in that folder.
    1. "hg status" will give you information on which files are M: modified, A: added, ?: untracked, and !: missing.
  2. "hg pull" to pull any recent changes to the repository.
  3. "hg merge default" to merge your branch with the default directory.
  4. "hg commit -m 'Homework 1: [username]'"
  5. "hg push"
Now sit back, relax, and feel a sense of accomplishment wash over you!

Homework 2: Compiler Project - Part 1: Tokenizer

Due by 10:00pm, Tuesday, Sept. 16.


This assignment is lexical scanning---the first step in compilation. Scanning identifies tokens from literals. You are required to build your own tokenizer and use it to process programs in a subset of the C language. (Note: do NOT use lex to generate your tokenizer automatically.) In particular, it should rename all user defined identifiers, i.e. variables and function names, to end with our course number (_cs254). The tokenizer should report an error if a token does not conform to the token-language definition (below). If the input program is correct, the output should also be a correct program with the same behavior. (E.g., if the input to your tokenizer is a program that can be compiled by gcc, then the output better be too!)  See the following examples:

  • A good example
    • Input file: int main() { int i; i=0; printf("%d\n", i);}
    • Output file: int main() { int i_cs254; i_cs254=0; printf("%d\n", i_cs254);}
  • An error example
    • Input file: int main() { int 2010i; printf("%d\n", 2010i);}
    • Abort scanning and report an error of the illegal token "2010i"

The Token Language

For this and later projects on compilation, we use a subset of the C language. There are only integer variables and arrays and no external library calls except for I/O. There are no pointers except for reading the input. In this project, we are concerned with the token definition of the language. See the token specifications below.  Note that tokens are separated either by white spaces (including tabs and line returns) or by symbols such as operators and semcolons. 

Token Language Specification

The tokens include <identifier><number><reserved word><symbol><string>, and <meta statement>. They are defined as regular expressions as follows:
  • <letter> --> a | b | ... | y | z | A | B | ... | Z | underscore
  • <identifier> --> <letter> (<letter> | <digit>)*
  • <digit> --> 0 | 1 | ... | 9
  • <number> --> <digit>+
  • <reserved word> --> int | void | if | while | return | continue | break | scanf | printf | main
  • <symbol> --> left_parenthesis | right_parenthesis | left_brace | right_brace | left_bracket | right_bracket | comma | semicolon | plus_sign | minus_sign | star_sign | forward_slash | == | != | > | >= | < | <= | equal_sign | double_and_sign | double_or_sign | and_sign | or_sign (The symbols are: ( ) { } [ ] , ; + - * / == != > >= < <= = && || & |)
  • <string> --> any string between (and including) the closest pair of quotation marks.
  • <meta statement> --> any string begins with '#' or '//' and ends with the end of line ('\n').

Note: letters and digits should be part of the same token unless they are separated by a while space character or a symbol.

Tokenizer Design

You may use any programming language to write your tokenizer (we recommend Ruby, Python or possibly Java - but for you probably don't want to use C).  Note that your grade will be based on correct performance.  Although you may organize your code however you like, your tokenizer should be executable on cycle1 as such: "./tokenizer.extension input_file.c".  Also, note that the tokenizer is the first step in a series of projects through which you will develop a calculator and a compiler. In later projects, you will reuse your tokenizer (if your tokenizer is not working well when the next assignment is given, please, please, please ask Jake or Kevin for help).

A modular implementation can use two classes---the token and the scanner classes. A token in the token class has information such as type and name (for identifiers) or value (for numbers). The constructor of the scanner class takes the input file name as an argument. It provides an enumerator method that yields the next token when called. The following shows such an interface for the scanner class in Ruby syntax:

class Scanner
    def init( file_name )
       ... ...

   # return the next token (as a Token object) or EOF
   def next_token
     ... ...

Readme File

You are also required to submit a concise (brief but comprehensive) plain text Readme file explaining the usage and functionality of your code.  If it doesn't work, describe what you think might be wrong and what needs to be done in order to get it working.

Answers to Questions

  1. Can we use regular expressions?
  • No. 


You are required to submit a folder containing an executable program and a plain text Readme file as specified above.  It must run on cycle1, and it is due by 10:00pm, Tuesday, Sept. 16.  Submit your folder with the following command from a lab computer (it is fine if you are ssh'd into the lab computer too - but some people have had trouble with ssh, so don't wait until the last minute to try):

"/u/cs254/bin/TURN_IN [my_folder_name]".

In class this looked like "/u/cs254/bin/TURN_IN ." because "[dot]" refers to the current directory.

FYI, the TURN_IN script compresses the entire specified directory and then sends it to me, labeled with its date and time.  If you submit and then wish to change your work, you may resubmit as much as you like up until the deadline (your friendly TA will grade the last submission prior to the deadline).


Homework 3: Compiler Project - Part 2: Calculator

Due by 10:00pm, Wednesday, Sept. 24 (Shorter time since you have all done this in 173).


In this assignment, you are required to write a calculator that takes a single-line expression of integer constants and outputs the result of the expression. Following is an example of how your program should behave (each line is input/out in a shell):
       % cat input_file
       % ./caculator input_file

The semantics of arithmetic operations is the same as integer operations in C (so 5/3 = 1). Your calculator needs to evaluate the expression in the left-associative order. For example, the steps to evaluate 3+4+5 are 3+4+5 => 7+5 => 12.

To complete this assignment you need to write:

  1. A parser for an expression grammar.  The parser requires grammar design and parsing, especially LL(1) parsing.
  2. An evaluator, which will take the output of the parser and evaluate the result of the expression.  The evaluator uses a technique called attribute grammar or syntax-directed translation, which we will discuss in detail starting in the lecture on September 22.

You may use any of the language you want, but we recommend Ruby, Python, or possibly Java (C is allowed, but be aware it will take you much longer!).

Note: do NOT use lex or yacc to generate code automatically.

Syntax of an input expression

<expression> --> <term> | <expression> <addop> <term> 
<addop> --> plus_sign | minus_sign 
<term> --> <factor> | <term> <mulop> <factor>
<mulop> --> star_sign | forward_slash 
<factor> --> NUMBER | minus_sign NUMBER | left_parenthesis <expression> right_parenthesis

We recommend you to implement a top-down parser.  You should use the grammar above (also, given by the slides in reading/04-LL1-parsing.pdf).  Edit: The grammar above is not LL(1), but it is equivalent to an LL(1) grammar.  It is your job to determine an equivalent LL(1) grammar to use.  Tip: see Figure 2.15 in PLP (Prog. Lang. Prag.) for a similar LL(1) grammar.   For a very good walk-through of how to implement a parser for a similar grammar, we strongly encourage you to read Chapter 2.3 in "Programming Language Pragmatics" prior to starting your work.

Readme File

You are also required to submit a concise (brief but comprehensive) plain text Readme file explaining the usage and functionality of your code.  If it doesn't work, describe what you think might be wrong and what needs to be done in order to get it working.


Use the TURN_IN script, as described above.  Remember, this assignment is due at 10:00pm, Wednesday, Sept. 24.

Condition for Extension

You can have two more days if you solve a slightly more complex version of the problem.  Instead of caculating on an expression during parsing, translating it into a C program.  For example, 

% cat input_file
% ./exprgen input_file
#include <stdio.h>

int main(int argc, char**argv) {
  int t1;
  t1 = 2 + 5;
  int t2;
  t2 = t1 + 4;
  printf("%d\n", t2);

The output code should have the include macro and define a main function and should output the result in a printf, as shown in the example output.  The spacing and variable names can be different depending on what you like.  In the output code, each assignment statement can have at most two operands on the right-hand side.  The output code must be compilable by a C compiler and can execute to produce the correct result of the expression.

If you choose this extension, the due time is 
10:00pm, Friday, Sept. 26.



Homework 4: Compiler Project - Part 3: Parser

Due by 10:00pm Oct. 3


Extend the parser of your calculator to support the full input language (specified below). The parser should check whether the program is grammatically correct. The specific requirements are:

  • As in the scanner project, your parser should ignore (but copy) "meta-statements".
  • See the detailed syntax specification below. Regardless of the choice of your implementation, you must convert the grammar into an LL(1) grammar and submit the modified grammar in writing.
  • For each input program, your parser should report "pass" or "error" as the result of grammar analysis.
  • Count the number of global and local variables (<data decls>), functions (<func list> but not function declarations), and statements (<statements>) in correct programs (Note: “int a,b;" increases the counter of variables by 2, not 1.).  Output the result in the following format: variable _num_variables  function _num_functions statement _num_statements.  For example, for a correct program with 4 variables, 2 functions and 6 statements, your compiler should output at least the following:
    • Pass
    •   Variables: 4
    •   Functions: 2
    •   Statements: 6


Syntax specification of the input language

<program> --> <data decls> <func list>
<func list> --> empty | <func> <func list>
<func> --> <func decl> semicolon | <func decl> left_brace <data decls> <statements> right_brace
<func decl> --> <type name> ID left_parenthesis <parameter list> right_parenthesis
<type name> --> int | void
<parameter list> --> empty | void | <non-empty list>
<non-empty list> --> <type name> ID | <non-empty list> comma <type name> ID
<data decls> --> empty | <type name> <id list> semicolon <data decls>
<id list> --> <id> | <id list> comma <id>
<id> --> ID | ID left_bracket <expression> right_bracket

<block statements> --> left_brace <statements> right_brace
<statements> --> empty | <statement> <statements>

<statement> --> <assignment> | <general func call> | <printf func call> | <scanf func call> | <if statement> | <while statement> | <return statement> | <break statement> | <continue statement>
<assignment> --> <id> equal_sign <expression> semicolon
<general func call> --> ID left_parenthesis <expr list> right_parenthesis semicolon     (ID is not "printf" or "scanf".)
<printf func call> --> ID left_parenthesis STRING right_parenthesis semicolon | ID left_parenthesis STRING comma <expression> right_parenthesis semicolon    (ID is "printf".)
<scanf func call> --> ID left_parenthesis string comma and_sign <expression> right_parenthesis semicolon    (ID is "scanf".)
<expr list> --> empty | <non-empty expr list>
<non-empty expr list> --> <expression> | <non-empty expr list> comma <expression>

<if statement> --> if left_parenthesis <condition expression> right_parenthesis <block statements> | if left_parenthesis <condition expression> right_parenthesis <block statements> else <block statements>
<condition expression> -->  <condition> | <condition> <condition op> <condition>
<condition op> --> double_and_sign | double_or_sign
<condition> --> <expression> <comparison op> <expression>
<comparison op> --> == | != | > | >= | < | <=

<while statement> --> while left_parenthesis <condition expression> right_parenthesis <block statements>
<return statement> --> return <expression> semicolon | return semicolon
<break statement> ---> break semicolon
<continue statement> ---> continue semicolon

<expression> --> <term> | <expression> <addop> <term>
<addop> --> plus_sign | minus_sign
<term> --> <factor> | <term> <mulop> <factor>
<mulop> --> star_sign | forward_slash
<factor> --> ID | ID left_bracket <expression> right_bracket | ID left_parenthesis <expr list> right_parenthesis | NUMBER | minus_sign NUMBER | left_parenthesis <expression> right_parenthesis


Test Cases

Write (at least) 5 test cases to test the correctness of your program.  

Update: We have prepared test cases for you to use - you can download them at  You are encouraged to use the given test cases and report the compiler test results on them.  If you use these standard tests, you don't need to create and submit your own tests.

You no longer need to write your own test cases.

What/When to Submit

Due by 10:00pm Oct. 3
Turn in your code using TURN_IN with a report of your design including the LL(1) grammar you used, with instructions to run your compiler. Include the results for all passed test cases and the problems for other test cases. In the report, write down the name of passed test cases with the results, and the reasons for failure in other test cases.




Homework 5: Compiler Project - Part 4: Intra-Function Code Generation

Part 1 Due by 10:00pm Oct. 10 

Part 2 Due by 10:00pm Oct. 17
Part 2 Due by 10:00pm Oct. 19

In this assignment, you are required to modify your parser to generate assembly-like code for each function in an input program.  The specific requirements are as follows.

  • (Part 1) Copy all meta statements (the lines that begin with # or //) to the output file.
  • The output program uses the same grammar as the input program with the following modifications:
    • (Part 1) An assignment statement can have at most 2 operands on the right-hand side.
      • <assignment> --> <id> equal_sign <operand> <operation> <operand> semicolon | <id> equal_sign <operand> semicolon
      • <operand> --> NUMBER | <id>
      • Change all mentionings of <expression> with <operand>, as in <id>, <func call>, <return>, and <condition>.
      • Redefine the grammar rules so that there are no <expression>s, only <operand>s.  This will require generating code to evaluate expressions.  Replace each <expression> with <operand>, (e.g. <id>, <func call>, <return>, and <condition> should not have <expression> on the right hand side of their productions).
      • However, if there is an expression specifying the size of an array, it has to be compile-time evaluable. You should raise an error for something like "int x[n];".  For this project, being "compile-time evaluable" means that it can only be a constant or a constant expression.  Raise an error if a variable is used to specify the array length.
      • You do not need to generate code for arithmetic expressions used inside a condition of IF or WHILE statements.  If you do, you don't have to implement short-circuit evaluation.  The code generation of conditions and their short-circuit evaluation are required in Part 2.
    • (Part 2) Grammar modification for control flow: (i.e. all intra-function control flow is changed to gotos and if-gotos.)
      • <if-statement> --> if left_parenthesis <operand> <comparison op> <operand> right_parenthesis goto LABEL semicolon
      • <goto-statement> --> goto LABEL semicolon
      • <label-statement> --> LABEL colon
      • LABEL is just another name for ID token
    • (Part 2) Remove the use of variables both local and global.  Allocate them in a global array called gvar and a local array in each function called lvar.  The names gvar and lvar are suggestions.  You may name them any way you want.  Parameters are not changed.  They will still be specified in a function declaration and referenced inside a function body. 
    • (Part 2 optional) Simplify so the index of an array access can be only a constant, another array access, or the addition/subtraction between an array access and a constant, with no complex computations.  An array access can be nested but for at most two levels.  For example, m[m[m[1]]] = 2 is converted to m[t] = m[[m[1]]; m[m[t]] = 2, where a[t] acts as a temporary variable.  This restriction adheres to the assembly-like nature of the output language.  In assembly, a memory instruction can use constant offsets but cannot make an arbitrary number of memory accesses.
    • (Part 2) Grammar modification for functions: (i.e. no expression is in arguments passing and value return.)
      • Function declaration and definition remain unchanged.
      • In <func call>, each parameter must be <id> instead of <experssion>.
      • In <return>, use <id> instead of <expression>.
  • The output program should be compilable by a C compiler (i.e. can be compiled by gcc successfully) and have the same behavior as the input program.  In addition, your compiler should still be able to parse and compile the code generated by your compiler for the expression generation step of the project (the first grammar modification).
  • Do not use a scanner generator or a parser generator for writing your compiler.


Test Cases

Use the given test cases to test the correctness of your program.  Report pass/failure in the readme.  

Update: We have prepared test cases for you to use - you can download them at

You no longer need to write your own test cases.


What/When/Where to Submit

Part 1 Due by 10:00pm Oct. 10 

Part 2 Due by 10:00pm Oct. 17
Part 2 Due by 10:00pm Oct. 19
Turn in your code using TURN_IN with a report of your design including instructions to run your compiler. In the report, write down the name of passed test cases and the reasons for failure in other test cases.

Homework 6: Compiler Project - The 5th and Final Part: Function Code Generation

Due by 10:00pm Sunday 11/02/2010

In this assignment, you are required to modify your compiler to generate assembly-like code for entire programs. Following are the requirements:
  • Copy any lines that begin with #include to the output program.
  • Put all variables including local and global arrays and all parameters into a single global array, e.g. M[ ] or Mem[ ], at a sufficient size of your choice (sufficient to run all test programs).
  • The generated program cannot have any function other than main()/printf()/scanf()/read()/write(), and it cannot have any variables other than the one global array. However, you can define and use macros such as #define stackTop mem[0].
  • Remember that in the input language, all function parameters are passed by value.
  • You may use a jump table to implement parameterized gotos. See an example at [repos]/reading/12-func-code-gen.pdf .  Alternatively, you may use the GNU extension for labels to be values (see the link on Slide 26). 
  • (455 Required, 255 Extra Credit, Finish above requirements before implementing this one). Use your compiler to insert checking code into a program to report the overflow of maximal stack size when it happens and terminate the execution.  Modify the test program MeaningOfLife.c to test your compiler and compare it with the default GCC.
  • As with the previous assignment, the output program should be compilable by a C compiler and have the same behavior as the input program. The only difference is the checking of stack overflow.

What/When/Where to Submit

Submit the execution results for the standard test programs after they are compiled by your compiler. A testing script is provided at [repos]/assignments/test.rb and the correct outputs are in [repos]/assignments/test_correct_results.txt. Use test.rb to generate the report on the execution result of standard tests, compare the output with the correct output (in test_correct_results.txt), and submit the report along with a README to list the programs passed/failed in the tests (compared with the correct report).

Turn in your code with a design description and the testing report in the README file by the due time. For the maximal stack depth check, report your design and the result in README.

Re-grading of earlier projects. If you finish this last part within the deadline and show that the compiler is correct and consists of entirely your own work (you wrote all the code), you can ask for your previous projects to be regraded based on what you have in the finished compiler.

Showcase Submission for Finished Projects

Submit as soon as you finish the project (before the deadline).

Submit the compiled code for all test programs into the default branch under the directory [repos]/showcase/Mmm-DD-project-name/. The first part of the directory name is the date when you finish. Use the 3-letter abbrevation Oct or Nov. The last part is a project name of your choice. You can use your user id or something fancier, e.g. no-stackoverflow. The first directory is [repos]/showcase/Oct-20-input-programs. It is a showcase, so include only the generated C files and do not include your compiler code or any other auxiliary files. The entire showcase directory will be made public, e.g. github or bitbucket, as a permanent record of the finished projects in this class.


Homework 7: Singularity

Singularity Assignment
You are asked to implement higher order functions using higher order functions.  As part of the assignment, you will form 2-people groups to practice working with other people's code.
1) Lambda Calculus
As an individual part, implement an interpreter for a function-only language.  This language must have the following features:
 * Create a single-parameter function, i.e. lambda
 * Apply (call) a function
This is the LC language describe in class.  Implement the language by writing an evaluator, using closures as taught in class.  For testing and demonstration, you may choose to extend the basic language and the evaluator to support numbers and/or strings.
You do not have to implement a parser yourself (see below on group work).  You are allowed to create the data structures directly, e.g., eval('x','x'),1), empty_env) is the call to evaluate the program that applies the identity function on number 1, if you implement Lambda and Apply as classes.
2) Group Work
You should work with another student to make it a group effort.  The basic requirement is that you each should produce code which can be independently tested but work together in a single program. 
You may collaborate in two ways.  The first way is peer testing.  Each student writes an evaluator by self but the test cases for the peer.  Each student writes an API document on how to use his or her evaluator, and the other student writes test cases purely based on the written document.  The testing should be extensive enough to ensure that the partner's code is correct.  The two students are encouraged to each program in a different programming language.
The second way is collaborative development of both syntax and semantics.   Choose a target language that supports lambda functions.  Extract just this part (not the full language).  One student writes the parser, and the other writes the evaluator.   Then the first student writes the test cases for the evaluator (without the parser), and the second student writes the test cases for the parser (and eventually the interpreter).  In this way, you can design the syntax for your language the way you like it.  To work together effectively, be sure that each person's code can be *individually* tested.
Languages that support higher order functions include Scheme, Ruby, Python, Haskell, ML, Javascript, Scala and Lisp.  You may implement the target language using itself or a different language, e.g. Ruby Proc implemented in Java.  
3) Extra Credit
10\% extra credit is given to the student whose evaluator (individual work as mentioned before) implements the environment in a purely functional way, i.e. no variables other parameters and no re-assignment of parameters inside their function.  For example, to be purely functional, you cannot use a hashtable or an array.  If your part is the parser, you can write the purely functional implementation of environment and show that it works correctly in your partner's evaluator.
4) Project Schedule and Submission
By Wednesday Nov 12.  Email the TAs the group members, the way of collaboration (peer testing vs full lambda language) and the programming language(s) to be used/targeted.  One email per group.
By Saturday Nov 15.  Finish and submit the individual parts.  Individual submission.
By Sunday Nov 23.  Finish and submit group project and report.  Group submission.
In the final step, each group submits the finished project with a report detailing all the code, documents and test cases.  Each should be authored by just one student.  Submit a summary report named summary.txt listing all project work and authorship.
5) Suggestions (Optional, Not Required)
5a) Brennan parser
If you program in Ruby and want a pre-implemented parser, you can use the provided `brennan_parser.rb`, created by Sean Brennan when he was a student in 2012.  The code has substantial in-line documentation on usage and syntax.
5b) Coverage testing
A common tool for coverage testing.  In Ruby, a package called SimpleCov can check what lines are run by a set of test cases and show the coverage in HTML format.  You are encouraged but not required to use a coverage testing tool like SimpleCov.  
To run SimpleCov, you would edit a test file to include the following before it includes any other code.
  require 'simplecov'
You will need to use the `gem install simplecov` command to install the library on the machine you're testing on.  After adding that small snippet of code, run with `ruby -I. test.rb`.  In addition to running the script, SimpleCov will create a directory called `coverage` with an HTML report on the code coverage.  
5c) Church numerals and recursion
Church, who invented lambda calculus, showed how to represent numbers and arithmetics using lambda functions.  See the Wiki page on Church numerals.  You are encouraged to design test cases to use such numbers.  If you look for more challenging problems, you can try defining subtraction (which Church couldn't do) and enabling recursion in lambda calculus with the Y operator (which Sean Brennan did in his class project).  

Homework 8: Language Extension

In this project, you are asked to extend a host language with a non-trivial data structure implemented in a guest language. The extension allows the data structure to be accessed directly in both languages.

The pedagogical purpose is to study the interoperability between two languages. In the most common case, the host language is interpreted, and the guest language is compiled. The extension is an exercise for you to compare and synthesize the design of both types of languages. The previous projects, the compiler and the lambda calculus evaluator, focused on just a single type.

The practical purpose is code reuse across languages. The host language should be higher level and easier to program than the guest language is. The guest language should be more efficient than the host language is. The extension is a useful skill and a common practice to combine their strengths.

Extending Ruby with an Interval Tree Class Implemented in C

An interval is a series of continuous integers between two end values. For example, [1...3] represents 1, 2, 3. An interval tree stores a collection of non-overlapping, non-adjacent intervals in a sorted, search tree. As a Ruby class, it has at least four methods: adding an interval, removing an interval, finding the interval that contains an integer, and inspecting all intervals. The inspection returns all intervals in a string or an array. These methods and their data structures should be implemented in C.  We call them interoperable methods to distinguish them from methods existed purely in Ruby or purely in C.

Other Languages and Data Structures

You can choose any language as the host language. The choices include other scripting languages such as Python, Matlab, R, and Scheme. Instead of C/C++, the guest language can be another compiled language such as Fortran and Java.

Instead of the interval tree, you may choose another data structure that has a comparable complexity. It should be a dynamic data structure, which requires dynamic memory allocation in the guest language, has potentially unbounded size, and a search and inspection operation that examines more one piece or the entire data structure entirely in the guest language.

Code Reuse

The purpose of the project is *not* the implementation of a data structure in the guest language. You are not just allowed but encouraged to find existing code and reuse it. For example, a partial C implementation of the interval tree can be found at

Document clearly the source of any code not written by you.


You must evaluate the language extension by comparing the performance of two implementations. The foreign implementation is the extension implemented in the guest language. The native implementation is another one implemented entirely using the host language.

You are required to compare the performance of all methods in data structures of three different sizes: small, medium, and large. The difference between two consecutive sizes should be at least two orders of magnitude.

In the case of C extension of Ruby, a small size interval tree can have 10 intervals, while the medium and large trees have 1000 and 1 million intervals. You must evaluate the cost of calling each of the class methods: add, remove, search and inspect.

You may use existing code for the native implementation. A Ruby implementation of the interval tree can be found at You are also encouraged to reuse the existing test cases, for example, those of the Ruby interval tree.

Group Work

You may form any size groups as long as each person in the group has a clearly defined role that includes the implementation of at least one interoperable function, i.e. the Ruby method to add an interval that is implemented in C. The group as a whole is responsible for the complete implementation and evaluation.

You are encouraged to share problems and solutions with others.  If your work is helped significantly by a classmate, let the teaching staff know who and what help, so we may award the person bonus points.


Each group must submit a report in one *PDF* document with the following content:
  • The group members and the role of each person
  • The interface in the host language
  • The data structure and interface in the guest language
  • The design for interoperability first in general and then each interoperable method in particular, clear enough that a reader can reproduce the implementation based on the description
  • The source of any external code
  • The performance evaluation of each interoperable method for each of the three data sizes
The report will be the primary basis for grading.  Submit one report in PDF format with all the required content; otherwise, you may be asked to revise and augment the report, if the teaching staff finds it not clear or not complete.  


  • Group formed and the roles enunciated in an email to the teaching staff, due 11:59pm Tuesday December 2.
  • Implementation and report, due 11:59pm Friday December 12.