Grades and deadlines

• Initial deadline: 23:59 on Tuesday 26 August

• How to submit: Turn in your completed spec.yml file on the CS department submit system under SI413 / lab1.1

  If you used an AI tool to help with this lab (you should use Gemini), turn in a file aichat.md as well. Remember the course guidelines for the use of generative AI on labs.

• Grading:

  In this lab you will complete the following tasks:

  1. Design a new language to meet the capabilities specified below
  2. Write an example program to demonstrate how your language works
  3. Write a clear and complete specification of your language’s syntax and semantics
  4. Carefully review one of your peer’s language spec for any unsupported capabilities or underspecified behavior
  5. Have a peer review your language spec for the same

  If your submission meets the requirements for each task, you will receive 7 points towards your total lab grade.

  Remember the somewhat unusual way we are assigning points for lab assignments this semester: If your submission meets the requirements, you get all 7 points. If it does not meet the requirements, you get 0 points (and a chance to resubmit for full credit next week).

• Resubmissions:

  We will follow the same resubmission policy for all labs this semester. Here is how it will work:

  1. Every lab has an initial deadline.
  2. If your work is submitted by the deadline and meets the requirements, you get full credit and are done.
  3. If your work is submitted by the deadline, demonstrates significant progress (at the discretion of your instructor), but does not yet meet the requirements, then your deadline is extended by exactly 1 week from the previous deadline (or the end of classes, whichever is sooner). Go back to step 2.
  4. Otherwise, if you do not submit work which demonstrates significant progress (from the prior submission) by the deadline, you will earn no points and lose the possiblity for further resubmission.

  In other words,

  def points_earned(deadline, max_points, previous_submission=None):
      while current_time() < deadline:
          wait()
      submission = get_from_submit_system()
      if meets_all_requirements(submission):
          return max_points
      elif significant_progress(previous_submission, submission):
          return points_earned(deadline + one_week, max_points, submission)
      else:
          return 0

Unit 1 Labs Overview (next three weeks)

You will design and write careful specifications for a new programming language. As of now, and for the next three weeks, your language will only support string literals, string input/output, and a few string operations.

For this week’s lab, you will work creatively to design a new language that provides the features (details below). You will turn in a careful spec of your language, and an example program written in that language which demonstrates all of the features.

You will form groups of two and three to peer review each others’ work. Everyone is responsible to be the primary reviewer for exactly one classmate. In order to receive credit, your primary reviewer needs to sign off on your work. (Remember to still turn in your work in progress, even if it has not yet been reviewed or you know it doesn’t yet meet the requirements, in order to earn the right to resubmit in another week!)

Looking ahead, for next week’s lab your instructors will select a few of the clearest language specifications from this week. You will all choose one of those select-few languages, write an example program in that language, and then write code for an interpreter for that language. A complete, working, and well tested interpreter will be earn 10 points.

In two weeks, you will continue and write a compiler for that same language to LLVM IR code. A complete, working compiler will earn 3 points.

In total, up to 20 points of your total lab grade are available over the next three weeks.

YAML file to complete

Download the file spec.yml

As you complete your work for this part, you will fill in and eventually submit this file.

The parts you need to fill in are written in all caps like BLAH BLAH. Replace any of that with your actual responses.

The file format should be mostly self-explanatory. Just be careful about the indentation. Generally, when your response goes over multiple lines, you have to maintain the same level of indentation (or greater) to keep that response together.

You can read the full YAML language specification here: https://yaml.org/spec/1.2.2/

Task 1: Language Design

Ground rules

Source code for your language should be plain-text, using the characters on your keyboard. Specifically, the 95 ASCII printable characters, space, and newline. (So no weird control characters, tabs, emojis, accents, etc.)

Required capabilities

Your language needs to support:

• String literals: a literal sequence of zero or more of the 97 ASCII characters that your program source code may contain.

• Concatenation: combining two (or more) string expressions into a single string, one after the other

• Reversal: taking any string expression and producing a new string with the same characters in the reversed order

• Input: reading a single line of text from the console as a string in your program

• Print: displaying any string expression to the screen

• Comments: a way to write notes in English which appear in your source code but do not affect the program meaning in any way

REQUIREMENTS

Fill in the language_name field in spec.yml with a name you choose for your programming language.

There is nothing else really to turn in for this part. But you should be sketching out ideas, writing small programs, starting to figure out what works and what doesn’t, as you narrow in on how your language will look and work.

To receive credit for this lab, your language needs to:

• Be original. The syntax and semantics should not be very similar to any single existing language, or to any of your classmates’ languages.

• Support the required capabilities

• Not have unnecessary extra features, like variables, functions, or while loops. We have a whole semester to add more cool capabilities, don’t worry!

Tips

If you are feeling stuck for ideas, feel free to peruse some of these sources of inspiration.

(Note, I was starting to make links for all of these so you can read more, but often the official documentation is too technical for a casual browse, and the many unofficial tutorials are on random websites that aren’t of high quality. You are genuinely better off asking an AI chatbot to explain these to you and give you some examples.)

• Python’s raw literals and multi-line literals

• Haskell’s comment syntax, which allows for nested comments

• Quote-like operators in Perl, which is essentially another way to write string literals. (Ruby also has something similar.)

• Heredocs and nowdocs in languages such as Bash or PHP

• Reverse Polish Notation (RPN), while not really a complete programming language, is an alternate way of writing math expressions which amazingly can be unambiguous without requiring any parentheses

• The Brainfuck language, which is extremely minimal with only 8 single-character commands, and yet powerful enough to perform any computation. How can you write code comments in such a language?

• Befunge, a two-dimensional kind of ASCII art programming language. Each individual character acts like a command, and execution follows straight-line paths through the code itself, turning according to certain commands.

Task 2: Example program

Once you have a good “feel” for how you want your language to work, test it out by writing an example program in your language.

I am not going to tell you exactly what your program should do. It should exercise all of the features of your language, and sort of “stretch” the limits a bit to demonstrate what your language can do.

Your program doesn’t necessarily need to be super long, but it should be long enough to hit most of the conceivable ways of combining the different constructs in your language.

Think of it this way: if someone wrote an interpreter for your language, and then they ran your code and it worked as intended, you would be pretty convinced that their interpreter is correct.

And remember that someone will look at this code without knowing anything about how your language works. It needs to be very well commented, using the comment syntax that you come up with!

REQUIREMENTS

Fill in the complete source code (along with comments) under the example_program field in spec.yml

Come up with at least two input/output test cases, representing sample input that could be entered at the console when your program is run, and the expected output that would be printed by your program as a result.

Fill these in under example_input_1, example_output_1, etc.

Your example program must:

• Demonstrate all of the capabilities that your language has in simple form, clearly demonstrating how your language is supposed to look and work.

• Demonstrate more complex parts to show how your language’s capabilities can be nested and combined.

• Make good use of code comments to explain clearly what your code means and what would happen if it were executed.

Task 3: Language specification

Syntax specification

Start by clearly and unambiguously defining the syntax of allowable programs in your language. You are not yet saying what anything means or how it should be executed, just what any possible program could look like.

For example, to describe simple string literals in C++, we might write something like

An ordinary character is any single character other than newline,
double quote ", or backslash \.

An escape sequence is a backslash \ followed by any single
character.

A string literal is a double-quote character ", followed by
a sequence of ordinary characters and escape sequences, followed by
another double quote character.

Notice how carefully this is written to try and cover every possible case! Of course your language will work differently than this, but this is the kind of precision we want.

You might want to think about organizing things into statements and expressions, and be clear when an expression can be nested inside another expression, or inside a statement.

Semantics specification

Now describe the precise meaning of the syntax you just laid out.

For each kind of expression, you should explain what value that expression produces. (Remember, every value in this language has the same type, strings.)

And for each kind of statement, you should explain exactly what that statement is supposed to do when executed.

REQUIREMENTS

Fill in the language syntax and semantics under language_syntax and language_semantics in the spec.yml file.

Your spec must:

• Clearly and unambigiously define the syntax of allowable programs in your language

• Be written with technical precision and clarity, at an abstract level without the use of examples

• Support all of the required capabilities in the language from Task 1

• Contain no UB (underspecified behavior).

  On a technical level, this means that every syntactically valid program in your language must have a single, clear, and unambiguous meaning. (Even if that meaning is sometimes “this program causes a runtime error” or something like that.)

Tasks 4 and 5: Peer Review

Make a group (circle) with two or three classmates, where you will each act as the official “final reviewer” of one other person’s spec.

Reviewer guidelines

• Be kind, but remember your job is to help you peer by identifying issues that they need to fix to meet the requirements.

• Focus mostly on the objective aspects of the requirements, like whether the language supports all the required capabilities, and whether the spec is unambiguous and free of any UB.

• Examples are not definitions. If you needed to look at the example to understand a part of the spec, that means the spec was not clear or complete on that aspect.

• Be pedantic. Think about edge cases and weird ways of putting things together which are technically allowed by the spec, but may not be what the author intended.

• Feel free to discuss further and offer suggestions if you want, but you are not required to fix any problems, just to help identify them.

• When you say Y and agree that the spec meets all the requirements, you are putting your integrity on the line. If you sign off on a spec which has particularly glaring flaws or omissions, you may be deducted 1 point from your own grade.

Reviewee guidelines

• Be respectful of your reviewer’s time. You should feel confident that your work satisfies all of the requirements before you ask someone else to (officially) review it.

• Be happy when your reviewer finds errors in what you did. They are not attacking you, they are helping you improve your work and get it up to the required standard.

• Try to avoid explaining things about your language. Your spec is supposed to stand alone without added commentary.

• If your reviewer doesn’t have time to complete a careful review before the deadline, remember you can submit your (incomplete) work and add in the review for a resubmission the following week.

REQUIREMENTS

Fill in the following fields in your spec.yml:

• reviewer_for: For which classmate are you serving as the final reviewer? (Just put their name.)

• reviewed_by: Which classmate is performing the final review on your submission? (Can be the same as the previous answer.)

• review_passed: Change this to Y when your reviewer agrees that your submission meets all of the requirements.

• reviewer_comments: Get your reviewer to write a sentence or two summarizing what they thought of your language design and spec.