Problem Set 1

home work!

Topic Basic Programming

Due 1pm on Friday, January 23, 2015

Purpose The goal of this problem set is to demonstrate basic competence in the prerequisites of this course and the PhD program in general, namely, solid programming skills in any programming language.

The problem also sets up a problem domain with a domain-specific language (DSL). This time around you write an "interpreter" for a program in the language. Later you will learn how to check basic properties and how to model this DSL in the tools that the course provides.


Problem 1 Write a one-page description of your chosen programming language X and why it is your favorite. Consider one or all of the following topics:
  • programming language X has a [your adjective here] syntax,

  • programming language X has a [your adjective here] type system,

  • programming language X has a [your adjective here] pragmatics,

  • programming language X has a [your adjective here] tool suite,

  • programming language X is well-suited for Y applications.

Do not feel restricted to these attributes. If you consider another one the prime reason, use it to illustrate X’s power.

Imagine writing this memo for a manager in a development lab.

Be concise. Use active voice and descriptive verbs. Avoid subjective adjectives; instead bring across your preference through the technical description. Keep in mind that the addressee may check up on the facts that you present to support your claim.

To format the memo, use (1) an 11-point font, (2) 1.5in margins all around, (3) a header that specifies the paper title and the author(s) of the memo.

Deliverable Print your memo and take it to Andy Fong (202 WVH, a.fong at He will mark it up for basic English problems. Schedule a meeting with him before January 30th to get one-on-one feedback. Then include a PDF version of the memo in the submission of problem set 3.

Problem 2 Your task is to implement a small fragment for an automatic driver for a dungeons-and-dragon-style game. The program reads a game configuration from the (Unix) standard input, and it writes its solution to the standard output. It computes the longest possible path for the player through an arrangement of rooms, subject to a simple rule (explained below).

A game configuration specifies two pieces: an arrangement of rooms and a player’s name and location in the arrangement. A room comes with a name, a description, and a series of exits. Each exit specifies a cardinal direction (north, east, south, west) and the name of the room to which this direction leads.

The program walks the player through this arrangement of rooms by always taking the first exit from the current room. Its result is the list of names of the rooms the player visits before getting back to an already visited room.

The designer of the game specifies an XML-based domain-specific language, dubbed DADL, for specifying a game configuration. Here is the grammar of DADL:

  Conf = <configuration name=String at=String>

          Room ...


  Room = <room name=String description=String>

          Exit ...


  Exit = <exit direction=DString to=String />

  DString is one of:

        - "north"

        - "east"

        - "south"

        - "west"

The name attribute of a configuration specifies the player’s name while at specifies his current location as the name of the current room. A room element names the room, describes it; its content lists any exits to other rooms. Finally, an exit element explains which direction leads to which room.

In this grammar, the dots (...) denote a possibly empty sequence of XML elements. Hence, a Config may not specify any rooms, and a Room may not include any exits.

Here is an example of a configuration and what the program is expected to produce:



expected output

<configuration name="amal" at="living">

  <room name="living" description="piano">

    <exit direction="east" to="sitting" />


  <room name="sitting" description="piano">

    <exit direction="east" to="dining" />

    <exit direction="west" to="living" />


  <room name="dining" description="piano">

    <exit direction="west" to="sitting" />







The output means that the player is in the living room and that by following the above rule, the player is going to walk from there to the sitting room and the dining room before she gets back to a room she has already seen.

Deliverable Email a tar.gz bundle to my CCS email address whose name combines the last names of the pair in alphabetical order. The tar bundle must contain a single directory—with the same name as the tar ball—with a README.txt file and an executable file (for your choice of extension).

The README.txt file must start with the following lines:

  ;; NameOfPartner1, NameOfPartner2


When I unpack the bundle on the standard departmental LINUX boxes (login-linux is a good example), I expect to cd into this directory and run the solution as

  $ ./ < 1-example1.xml | diff - 1-output1.txt

where 1-example1.xml and 1-output1.txt are files I will supply.