Programming Languages

Problem Set #4

Objectives

During this activity, students should be able to:

This activity helps the student develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.


Activity Description

Individually or in pairs, modify the Lisp metacircular evaluator built in class in order to solve the following problems. All your code must be placed in a file called lisp.clj.

  1. Add to the Lisp interpreter the do special form, which has the following syntax:

    $$ \texttt{(do } \mathit{exp}_1 \; \mathit{exp}_2 \; \cdots \; \mathit{exp}_n \texttt{)} $$

    where every \(\mathit{exp}_i \) is an expression. This construct behaves like its Clojure counterpart of the same name: it evaluates each expression in order from left to right (most likely for their side effects, such as printing), and returns the result of \(\mathit{exp}_n\) (the last expression).

    Example:

    ($eval '(do (prn (+ -2 (+ 1 2)))
                (prn (+ 1 1))
                (prn 3)
                (+ 2 2))
           {'+ +
            'prn prn})
    => 4
    

    Output:

    1
    2
    3
    
  2. Add to the Lisp interpreter the dotimes special form, which has the following syntax:

    $$ \texttt{(dotimes}\texttt{ (}\mathit{var}\texttt{ }\mathit{count}\texttt{) } \mathit{body}\texttt{)} $$

    where \(\mathit{var}\) is a symbol, while \(\mathit{count}\) and \(\mathit{body}\) are expressions. This construct executes \(\mathit{body}\) (which must perform some side effect operation, typically printing) once for each integer from 0 (inclusive) to \(\mathit{count}\) (exclusive), binding the variable \(\mathit{var}\) to the integer for the current iteration. This special form always returns nil.

    Examples:

    ($eval '(dotimes (i (+ 2 2))
              (println "Line" i))
           {'println println, '+ +})
    
    ($eval '(dotimes (x 10)
              (pr x))
           {'pr pr})
    

    Output:

    Line 0
    Line 1
    Line 2
    Line 3
    
    0123456789
    
  3. Add to the Lisp interpreter the let special form, which has the following syntax:

    $$ \texttt{(let}\texttt{ (}\mathit{var}\texttt{ }\mathit{expr}\texttt{) } \mathit{body}\texttt{)} $$

    where \(\mathit{var}\) is a symbol, while \(\mathit{expr}\) and \(\mathit{body}\) are expressions. This construct evaluates and returns the result of \(\mathit{body}\) using an extended environment where \(\mathit{var}\) is bound with the result of evaluating \(\mathit{expr}\). In other words, it's equivalent to:

    $$ \texttt{((lambda}\texttt{ (}\mathit{var}\texttt{) }\mathit{body}\texttt{) } \mathit{expr}\texttt{)} $$

    Examples:

    ($eval '(let (x 6)
              (* 7 x))
           {'* *})
    => 42
    
    ($eval '(let (x (* 2 5))
              (let (y (+ 1 x))
                (+ 1 (* y x))))
           {'+ +
            '* *})
    => 111
    
  4. Add to the Lisp interpreter the cond special form, which has the following syntax:

    $$ \texttt{(cond } \mathit{test}_1 \; \mathit{exp}_1 \; \mathit{test}_2 \; \mathit{exp}_2 \; \cdots \; \mathit{test}_n \; \mathit{exp}_n \texttt{)} $$

    where every \(\mathit{test}_i\) and \(\mathit{exp}_i\) is an expression. This construct, like its Clojure counterpart of the same name, takes a set of \(\mathit{test}/\textit{exp}\) pairs. It evaluates each \(\mathit{test}\) one at a time. If a \(\mathit{test}\) returns logical true (any value not equal to nil nor false), cond evaluates and returns the value of the corresponding \(\textit{exp}\) and doesn't evaluate any of the other \(\mathit{test}\)s or \(\mathit{exp}\)s. If there are no \(\mathit{test}\)s that evaluate to true, cond returns nil.

    You can alternatively think of cond as being equivalent to:

    $$ \texttt{(if } \mathit{test}_1 \; \mathit{exp}_1 \; \texttt{(if } \mathit{test}_2 \; \mathit{exp}_2 \; \cdots \; \texttt{(if } \mathit{text}_n \; \mathit{exp}_n \; \texttt{nil)} \cdots \texttt{))} $$

    Example:

    ($eval '(cond
              (= x 1) (quote one)
              (= x 2) (quote two)
              (= x 3) (quote three)
              (= x 4) (quote four)
              true    (quote other))
           {'x 3
            '= =})
    => three
    

Deliverables

The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:

;----------------------------------------------------------
; Problem Set #4
; Date: October 18, 2019.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Upload Instructions

To deliver the lisp.clj file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Friday, October 18.

Evaluation

This activity will be evaluated using the following criteria:

-10 The program doesn't contain within comments the author's personal information.
-30 A docstring is missing in one or more functions.
10 The program contains syntax errors.
1 The program was plagiarized in whole or in part.
10-100 Depending on the amount of exercises that were solved correctly.