Decaf

P0: Decaf Program

Objective

The goal of this project is to become familiar with the Decaf programming language.

Introduction

The semester-long project for this course is to build a compiler for the Decaf language. In this project, you will implement various functions in Decaf to become familiar with the language.

You should use the reference copy of the compiler and simulator to test your submission for this project:

/cs/students/cs432/f23/decaf <decaf-file>

You may wish to download the starter file with function stubs: p0.decaf (use wget or curl to download a file from the internet on stu)

You may edit Decaf code using the editor of your choice. See the Resources page for some syntax highlighting plugins written by former students. There is no testing framework for Decaf so you will need to devise your own testing regimen given the requirements below.

Assignment

Implement the following functions in Decaf:

  • int fact(int n)
    Returns the factorial of n (i.e., "n!"). For example, "fact(3)" should return 6. You may assume 1 ≤ n ≤ 10.
  • int fib(int n)
    Returns the nth Fibonacci number (0, 1, 1, 2, 3, 5, etc.). Thus, "fib(1)" should return 1 and "fib(4)" should return 3. You may assume 0 ≤ n ≤ 25.
  • bool is_prime(int n)
    Returns true if n is prime, and false otherwise. Performance is not a concern, so you may use a naive algorithm. You may assume 0 ≤ n ≤ 600.
  • int sum_nums(int len)
    Returns the sum of len numbers from an array called nums. For example, "sum_nums(0)" should return 0 regardless of the contents of nums, and "sum_nums(2)" should return the sum of the first two numbers. You may assume the array size does not exceed 100.
  • void sort_nums(int len)
    Sorts len numbers from an array called nums in ascending numerical order. Sorting should be done in-place and if the array is actually larger than len, none of the elements past the first len should be modified. Performance is not a concern, so you may use any sorting algorithm you wish. You may assume the array size does not exceed 100.
  • int gcd(int a, int b)
    Returns the greatest common divisor of a and b. For example, "gcd(8,12)" should return 4. Performance is not a concern, so you may use a naive algorithm. You may assume 1 ≤ a,b ≤ 200.
  • void draw_triangle(int base)
    Draw a simple text-based triangle using hash marks ('#'). The base of the triangle should be base characters long and the triangle should be oriented upwards from the base. Each level of the triangle should decrease in width by two characters per level (one on each side). Every line should end with a newline character ('\n'), but there should be no extra whitespace above or below the triangle or on its right side. You may assume 1 ≤ base ≤ 100. Examples:

    Example (base=3):
     #
    ###
    
    Example (base=4):
     ##
    ####
    
    Example (base=9):
        #
       ###
      #####
     #######
    #########
    

Note that draw_triangle is the ONLY function that should print any output. If you insert any debugging output as you work on the project, make sure you remember to remove it or comment it out before submitting!

For sum_nums and sort_nums, you should assume in those functions that a global nums array has been initialized. For testing purposes, you should do this in your main or in a helper function before calling sum_nums or sort_nums.

Submission

Please submit your p0.decaf file on stu AND to the appropriate assignment on Canvas by the due date indicated there.

To submit on stu, run the following command from your project folder:

/cs/students/cs432/f23/submit.sh p0

Code Reviews

One of the goals of this course is to encourage good software development practices, especially when building a large software system (such as a compiler). For this project, you will be assigned two other random students in the course. You must review their code and offer constructive feedback according to the given rubric.

Submit your review on Canvas by the Friday following this project's due date, as described in the appropriate Canvas assignment.

Grading

Here is the overall grading breakdown for this project:

Instructor grade90
Code review8
Review response2
TOTAL100

Here is the rubric for the "Instructor grade" part of the overall grade:

Grade Description Requirements
A Exceptional
  • Functional draw_triangle
  • All edge cases handled correctly
  • All of the below
B Good
  • Functional sum_nums
  • Functional sort_nums
  • All of the below
C Satisfactory
  • Functional is_prime
  • Functional gcd
  • All of the below
D Deficient
  • Functional fact
  • Functional fib
F Unacceptable
  • Some evidence of a good-faith attempt

The above rubric shows the base grade possible if your submission meets the criteria listed. Most of the items listed will be assessed via automated testing, consisting of test cases that are mostly NOT provided to you in advance (so write your own tests!).

I will also be examining your submission manually for acceptable style and documentation, as well as the use of any unsafe functions. If your submission is particularly egregious in any of these categories you will earn a half- or full-letter grade deduction depending on the severity of the issue. If you are unsure regarding my standards in this regard, I would suggest consulting my CS style guide and list of unsafe functions from CS 261.