CSC 533: Programming Languages
Spring 2025

HW2: Implementing a Simple Interpreter

For this assignment, you are to complete an interpreter for a subset of the SILLY (Simple, Interpreted, Limited Language for You) programming language. Recall that the syntax rules for SILLY v. 24 were provided in HW1. There can be no spaces between the characters in an identifier, integer, character or string. Delimiters, i.e. '(', ')', '{', '}', '[', and ']', do not require spaces to separate them from other tokens, but all others do. The SILLY language is case-sensitive, so variables a and A are considered unique.

There are five data types in SILLY: number, Boolean, character, string, and list. The language is dynamically typed, meaning that a variable does not have a set type but is defined by the value assigned to it. Variables are not explicitly declared - the first time an assignment is made to a variable, that variable is implicitly declared and initialized. If a variable is used in an expression before having a value assigned to it, a run-time error should occur. Compound statements represent new, nested scopes. If a variable is initialized (i.e., used for the first time) inside a compound statement, it is local and will not exist outside of that scope.

There are a number of predefined operators in SILLY for building expressions, as listed below. Note that expressions are enclosed in parentheses and use a prefix ordering, where the operator comes first. 

 DESCRIPTION    OP(S)              OPERAND(S)                EXAMPLE
 -------------  -------            ----------------------    ----------------------------
 math ops       + * /              applied to 2+ numbers     (+ 1 2) → 3
                                                             (* 2 3 4) → 24
 Boolean ops    == != > >= < <=    applied to 2+ values      (== 1 2) → false
                                     of same type            (> 5 3 1) → true
                not                applied to 1 Boolean      (not true) → false
                and or             applied to 2+ Booleans    (and true (not true)) → false                               
                                                             (or false (not true) true) → true
sequence ops    len                applied to string/list    (len "foo") → 3
                                                             (len [10 20]) → 2
                get                applied to string/list    (get "foo" 0) → 'f'
                                     & integer value         (get [10 20] 1) → 20
                cat                applied to 2+ string/list (cat "foo" "bar") → "foobar"
                                     of same type            (cat [1 2] [3 4]) → [1 2 3 4]
                str                applied to 1 value        (str 99) → "99"
                                                             (str true) → "true"
                                                             (str 'M') → "M"
                                                             (str "foo") → "foo"
                                                             (str [1 2]) → "[1 2]"

Note that all data types in SILLY are comparable within their own type. Numbers are ordered numerically (e.g., 2 < 3); characters and strings are ordered alphabetically (e.g., 'a' < 'b' and "bar" < "foo"); Booleans are ordered truthfully (e.g., false < true) and lists are ordered by their string values (e.g., ["a", "b"] < ["x", "y"]). When an operator is applied to more than one input, it is applied left-to-right, e.g., (/ 8 4 2) → 1. This leads to a counter-intuitive evaluation of != when applied to multiple values, e.g., (!= 1 2 1) → true. You may note that there is no subtraction operator in SILLY. Instead, subtraction can be accomplished by adding a negative number, e.g., (+ 5 -1) → 4. Any type mismatch within an expression (e.g., applying the * operator to two non-numeric values or comparing values of different types) should result in a run-time error with a descriptive message.

SILLY provides a number of different statement types, including assignment, compound, print, if and while. Sample interpretations of SILLY code are provided below, with user input prefaced by ">>>" and the interpreter's output highlighted in red:

SAMPLE CODE (output in red)
>>> print -4.8
-4.8
>>> print [1 3 5]
[1 3 5]
>>> x = (+ 1 (* 2 3) 4)
>>> print x
11
>>> y = (+ x -1)
>>> print y
10
>>> print (>= 5 4 4 2)
true
>>> test = (== 9 (+ 7 3))
>>> print test
false
>>> list = [1 3 5 7]
>>> print (len list)
4
>>> print (get list (+ (len list) -1))
7
>>> print (cat [0] list [8 9])
[0 1 3 5 7 8 9]
>>> x = 12
>>> if (> x 5) {
      if (< x 10) {
        print 1
      }
      else {
        print 2
      }
    }
    else {
      print 3
    }
2
>>> numFolds = 0
>>> thick = 0.02
>>> while (< thick (* 93.3e6 5280 12)) {
      thick = (* 2 thick)
      numFolds = (+ numFolds 1)
    }
>>> print numFolds
49

>>> flag = true
>>> print (not flag)
false
>>> print (or flag (not flag))
true
>>> print (and flag (> 3 2) (!= 'a' 'b'))
true
>>> ch = 'a'
>>> print ch
a
>>> chars = ['a' 'b' 'c']
>>> print (get chars 0)
a
>>> print (== ch (get chars 0))
true
>>> i = 0
>>> while (< i (len chars)) {
      print (get chars i)
      i = (+ 1 i)
    }
a
b
c
>>> repeat 3 {
      print true
    }
true
true
true 
>>> empty = [ ]
>>> repeat 5 {
      empty = (cat empty [0])
    }
>>> print empty
[0 0 0 0 0]
>>> i = 0
>>> repeat (len chars) {
      print (get chars i)
      i = (+ 1 i)
    }
a
b
c

An incomplete version of the SILLY interpreter is provided for you via the following classes/files (which are also downloadable as SILLY.zip):

As provided, the interpreter runs a subset of the SILLY language. Numeric, comparison and list operators are implemented, but the Boolean operators (not, and and or) are not. The data types for number, Boolean and list are implemented, but character and string are not. Assignments, print statements, if statements, while loops and compound statements are implemented, but repeat, function declarations and return statements are not. Note that statements in the left column above will execute given the existing code; statements in the right column depend on language features that you will be implementing in this assignment:

  1. Modify the evaluate method within the Expression class so that the operators are Boolean operators (not, and and or) are evaluated as specified. If the structure or data types in an expression are invalid, your code should throw an exception with a meaningful error message.
  2. Define a new class named CharValue that implements the DataValue interface and provides the required methods for the character data type. You will also need to add a corresponding value to the Type enumeration in DataValue for this new type. Finally, make the needed modifications to the Expression class so that expressions involving characters can be handled.
  3. Define a new class named Repeat that inherits from Statement and provides the required methods for a repeat statement. A repeat statement is similar to a while statement, except its expression should evaluate to a whole number (i.e., an integer). The repeat statement executes the code in its compound statement as many times as the expression specifies. Note: if the expression in a repeat statement does not evaluate to a whole number (i.e., an integer), an exception should be thrown with a meaningful error message. Don't forget to update the Statement class so that repeat statements can be created from the token stream.