Decaf

PA1: 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 download the reference compiler from the "Files" tab in Canvas to test your submission for this project.

You may wish to download the starter file with function stubs: 01-stubs.decaf

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.
  • int fib(int n)
    Returns the nth Fibonacci number. For example, "fib(1)" should return 1 and "fib(4)" should return 3.
  • 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.
  • 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.
  • void sort_nums(int len)
    Sorts len numbers from an array called nums in ascending numerical order. Sorting should be done in-place. Performance is not a concern, so you may use any sorting algorithm you wish.
  • 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.
  • 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. Examples:
    
    base=3:
    
     #
    ###
    
    base=4:
    
     ##
    ####
    
    base=9:
    
        #
       ###
      #####
     #######
    #########
    
        

For this assignment, you may assume that all function inputs are valid by the function's mathematical definition. For example, the factorial operator is not defined for negative integers, so your fact does not need to handle negative inputs; the same holds for fib, gcd or draw_triangle.

Submission

DUE DATE: Friday, January 15, 23:59 EDT (11:59PM)

Please submit your .decaf file and your reflection paper to the appropriate assignments on Canvas.

Your decaf program should be self-contained in a single file and should implement all of the project specs described above. It MUST contain at least function stubs for all functions mentioned in the spec, even if you did not have time to implement all of the functions.