Fundamentals of Computer Science I (CS151.02 2007S)

Homework 8: Evaluating Expressions

This homework assignment is also available in PDF.

Assigned: Friday, February 23, 2007
Due: Tuesday, February 27, 2007
No extensions!

Summary: In this assignment, you will further explore the evaluation of expressions in Scheme.

Purposes: To reinforce Scheme's evaluation strategy. To give you experience writing recursive procedures. To raise the question of how to implement a language.

Expected Time: One to two hours.

Collaboration: You may work in a group of any size between two and four, inclusive. You may consult others outside your group, provided you cite those others. You need only submit one assignment per group.

Submitting: Email me your work, using a subject of CSC151 Homework 8.

Warning: So that this exercise is a learning assignment for everyone, I may spend class time publicly critiquing your work.

Background: Evaluating Expressions

As you may recall from our discussion in class, Scheme uses a straightforward strategy for evaluating most expressions:

You may have also observed that procedure applications look remarkably like lists. For example,

(+ 2 3)

might represent apply the procedure + to the values 2 and 3 or it may be a list with elements +, 2, and 3. Similarly,

(* (+ 2 a) (+ 3 b))

might be the product of two sums, or it may be a list with two sublists.

The close ties between lists and general expressions is intentional. In fact, behind the scenes, Scheme represents expressions as lists and has an internal procedure that evaluates them using the algorithm above.

In this assignment, you will build a simple version of that algorithm.


Consider a Scheme-like language for building strings, which we'll call Streme. In Streme, the basic values are all strings (things surrounded by quotation marks). The valid operations on strings are

Your goal in this assignment is to write three related procedures, (streme-eval str-exp), (streme-apply-unary unary-function str), and (streme-apply-binary binary-function str1 str2), that we can use to evaluate Streme expressions.

The streme-eval procedure should evaluate its argument using a modified version of the technique discussed above. (That is, determine whether str-exp is a string or a procedure application. In the latter case, evaluate the arguments and then apply the procedure.)

In particular, streme-eval should look something like the following.

(define streme-eval
  (lambda (str-exp)
      ((string? str-exp) str-exp)
      ((procedure-call-with-one-parameter? str-exp)
       (streme-apply-unary (car str-exp) 
                           (streme-eval (cadr str-exp))))
      ((procedure-call-with-two-parameters? str-exp)
      (else #f))))

You will, of course, have to fill in the ellipses and the definitions of the new predicates. Note that the correspondence between lists and expressions suggests that a procedure call with one parameter is simply a list of two elements (the procedure and the expression to which to apply the procedure).

(define procedure-call-with-one-parameter?
  (lambda (str-exp)
    (and (list? str-exp)
         (= (length str-exp) 2))))

As the code above sugests, the streme-apply-unary and streme-apply-binary procedures should give the instructions necessary to apply the given procedure to one string or two strings, respectively.

The streme-apply-unary should look something like the following.

(define streme-apply-unary
  (lambda (proc str)
      ((eq? proc 'first) (substring str 0 1))
      (else #f))))


Here are some sample sessions with our Streme interpreter.

> (define sample1 (list 'first "Hello"))
> sample1
(first "Hello")
> (streme-eval sample1)
> (define sample2 (list 'remove-first (list 'remove-first "Hello")))
> sample2
(remove-first (remove-first "Hello"))
> (streme-eval sample2)
> (define sample3 (list 'remove-first (list 'remove-last "Hello")))
> sample3
(remove-first (remove-last "Hello"))
> (streme-eval sample3)
> (define sample4 (list 'join (list 'first "Joy") (list 'remove-first "Hello")))
> sample4
(join (first "Joy") (remove-first "Hello"))
> (streme-eval sample4)
> (define sample5 '(join (reverse "Hello") (remove-first "Hello")))
> sample5
(join (reverse "Hello") (remove-first "Hello"))
> (streme-eval sample5)

As the last example suggests, when testing it is okay if you build your expressions using quote. (In general, I prefer that you not build lists with quote, but here, it's clearly more natural.) Just be sure not to use quotes anywhere within the expressions.

Approaching the Problem

This problem is a bit bigger than the other work you've done so far, but it is managable if you break it up into pieces.

We'd recommend that you try implementing the procedures in the order given above (first, last, remove-first, remove-last, reverse, alphabetically-first, longer-string, and join).

Important Evaluation Criteria

As has been the case in all recent assignments, my primary evaluation criteria will be correctness, layout, and elegance.



Early September 2006 [Samuel A. Rebelsky]

Friday, 15 September 2006 [Samuel A. Rebelsky]

Monday, 18 September 2006 [Samuel A. Rebelsky]

Tuesday, 19 September 2006 [Samuel A. Rebelsky]

Wednesday, 20 September 2006 [Samuel A. Rebelsky]

Thursday, 21 September 2006 [Samuel A. Rebelsky]

Friday, 23 February 2007 [Samuel A. Rebelsky]


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Thu Sep 13 20:54:10 2007.
The source to the document was last modified on Fri Feb 23 11:36:56 2007.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Creative Commons License

Samuel A. Rebelsky,

Copyright © 2007 Samuel A. Rebelsky. This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.