Challenge 23: Small Racket

In Programming Paradigms, students explore all sorts of different languages such as Scheme, Python, Java, and JavaScript in order to familiarize themselves with various programming paradigms such as functional programming, object-oriented programming, and event-driven programming. For instance, at the beginning of the semester, the students had to implement a Tic-tac-toe evaluator in Scheme. Unfortunately, they had to use a janky Scheme implementation called Guile which produces lovely error messages such as:

ERROR: In procedure car: Wrong type (expecting pair): ()

Not satisfied with this inferior Scheme1, you decide to make your own arithmetic Scheme interpreter that supports the following EBNF grammar:

<digit>         = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<number>        = {<digit>}
<op>            = - | + | * | /
<expression>    = (<op> <expression> ...) | <number>

Given the above definition, note the following:

  1. You only have to support natural numbers (i.e. 0, 1, 10, 100, ...)

  2. You only have to support basic arithmetic operators: addition, subtraction, multiplication, and division.

  3. You have to support variable length expressions (that is operations that take two or more arguments) or numeric literals.

  4. You do not have to worry about syntax errors or invalid input. You can safely assume that any given test input will follow these rules.

Blast From the Past

If you need more guidance on how to solve this project, you can check out the Project 01: Arithmetic Scheme Interpreter write-up from a previous instance of the Data Structures course (note that version only supports binary operations, you need to support variable length operations).

If you have already written a Scheme interpreter, challenge yourself by writing one in a different language.

Input

You interpreter will be given multiple lines of input where each line is a single Scheme expression as defined by the EBNF grammar above. You should process these expressions until you reach EOF.

Example Input

1
(1)
(+ 1 2 3 4)
(+ (- 1 2) (* 3 4))

Output

For each Scheme expression (that is for each line), output the final evaluation result.

Example Output

1
1
10
11

Simon's Stack Algorithm

If you want to avoid building a tree, you can use the following stack based approached developed by Simon Rodriguez in 2021:

ParseExpression(Line):
    Characters = Line.Characters()
    Stack      = []
    for Token in ParseToken(Characters):
        if Token is ')':
            Expression = [Stack.Pop() until we reach '(']
            Result     = EvaluateExpression(Expression)
            Stack.Push(Result)
        else:
            Stack.Push(Token)
    return int(Stack.top())

ParseToken(Characters):
    # Given ['(', '+', ' ', '1', '2', ')']
    # Return next non-whitespace character (while consuming Characters)

EvaluateExpression(Expression):
    # Given [Operand, Argument0, Argument1, ...] or [Integer]
    # Return evaluated expression```

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge23               # Create and checkout challenge23 branch

$ $EDITOR challenge23/program.cpp           # Edit your code

$ git add challenge23/program.cpp           # Stage your changes
$ git commit -m "challenge23: done"         # Commit your changes

$ git push -u origin challenge23            # Send changes to GitHub

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/check.py
Checking challenge23 code ...
  Result Success
    Time 0.26
   Score 6.00 / 6.00

$ curl -F source=@challenge23/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge23
{"result": "Success", "score": 6, "time": 0.2649972438812256}

Pull Request

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 11 TA List.

  1. Some better Scheme implementations: Racket, Chicken Scheme, and my former love Gauche Scheme. ↩