To see revisions of this document or browse other course outlines, please Log In

Foundations of Sequential Programs Fall 2023
CS 241

Published Dec 18, 2023

Class Schedule

Please log in to view this content.

Instructor & TA (Teaching Assistant) Information

Please log in to view this content.

Course Description

CS 241:

The relationship between high-level languages and the computer architecture that underlies their implementation, including basic machine architecture, assemblers, specification and translation of programming languages, linkers and loaders, block-structured languages, parameter passing mechanisms, and comparison of programming languages. [Note: Enrolment is restricted; see Note 1 above. Lab is not scheduled and students are expected to find time in open hours to complete their work. CS 251 is a recommended corequisite. Offered: F,W,S]

Prereq: CS 138 or (CS 246/246E and CS 136L) or (CS 136L and a grade of 85% or higher in one of CS 136 or 146); Computer Science and BMath (Data Science) students only. Antireq: CS 230, ECE 351

Learning Outcomes

By the end of this course students should be able to:
Understand how high-level languages are implemented on modern computer architectures.
Write short machine code and assembly language programs
Formally specify regular languages
Use regular languages to scan and tokenize text
Write an assembler
Formally specify context-free languages with a context-free grammar
Generate the LR(0) parsing tables for a context-free grammar if one exists
Write a LR(1) parser for a context-free language given the LR(1) parsing table for a context-free grammar for that language
Reify the output of a LR(1) parser into a parse tree.
Perform semantic analysis and type checking on a parse tree corresponding to a parsed, high-level program written in some high-level language.
Generate assembly code from a parse tree corresponding to a parsed, high level program written in some high-level language.
Implement the runtime support necessary for high-level programs (such as dynamic memory management, linking and loading)

Tentative Course Schedule

 We will cover the course material in the following approximate order:

  1. Data representations
  2. Machine instructions and machine-code programs
  3. Scanning and regular languages
  4. Assemblers and assembly language basics
  5. Common higher-level constructs (such as conditionals and procedures) in assembly
  6. Assembly with labels and two-pass assemblers
  7. Runtime support for a high-level language (loaders and linkers)
  8. Specifying high-level languages (context-free languages and grammars)
  9. Parsing and parsing algorithms (top-down, bottom-up)
  10. Semantic analysis and type-checking
  11. Code generation
  12. Memory management 
  13. Compiler optimizations

Minor assignments (questions) will be released at a rate of roughly 1-2 per week, up until around halfway through the term. There will be 10 questions total. Questions will typically be due 1-2 weeks after release.

The following is a tentative schedule of the 5 major assignments (projects):

  1. MIPS and WLP4 Scanners
    Released week 3
    MIPS scanner due end of week 5
    WLP4 scanner due end of week 8
  2. MIPS Assembler
    Released week 4
    Due end of week 7
  3. WLP4 Parser
    Released week 9
    Due end of week 11
  4. WLP4 Semantic Analyzer
    Released week 10
    Due end of week 12
  5. WLP4-to-MIPS Code Generator
    Released week 11
    Due end of week 13

 

Texts / Materials

Title / Name Notes / Comments Required
CS 241 Course Notes Available online from website No
Modern Compiler Implementation in (C|ML|Java) No

Course notes are provided as a reference.  However, lectures may cover additional material not present in the course notes.  Students are responsible for learning all material covered in lecture, including material not in the course notes.

Student Assessment

Component Value
Assignments 30%
Midterm 30%
Final 40% (* See Final Exam Weight Adjustment below)
Lecture Feedback bonus Up to 3.5% bonus
Assignment bonus Up to 1.5% bonus

Assignments: Divided into roughly 10 questions (1% each) and 5 projects (4% each).

Examinations: There will be a midterm exam (on Wednesday, October 25, 7:00-8:50pm) and a final exam (details to be announced).

Final Exam Weight Adjustment: The weight of the final exam will be increased from the base weight of 40 by 1/3 of the value of the marks lost on the midterm. More precisely, if M is the mark you got on the midterm as a percentage out of 100, then:

  • The value of marks you lost on the midterm is L = 30 x (100 - M)/100
  • The weight of your final exam is (40 + L/3)

Bonus: There are 20 bonus points available, each worth +0.25% on the final grade, for a maximum bonus of +5%. 14 bonus points (3.5%) are award for completing lecture feedback surveys. 6 bonus points (1.5%) are awarded for completing bonus assignment questions, and for "linguistic diversity" on projects (implementing projects using a mix of C++ and Racket). See the course website for details.

Late policy: As assignments often build on each other, to encourage assignment completion, assignments may be submitted for partial credit up to 11:59PM EST on the last day of class. Specifically, the grade on an assignment will be an equally-weighted average of the grade earned on the best on-time submission and the grade earned on the best overall submission.  However, we strongly encourage students to complete assignments on time if possible.

Due to logistical constraints no late submissions will be accepted after the last day of class.

Assignment Screening

Assignments will be screened using MOSS, a software tool for measuring similarity of software.

Administrative Policy

Student support: We understand that students may experience difficulty dealing with academic stress, difficult life events, or feelings of isolation, anxiety, or depression. We encourage you to seek support, and if you need accommodation in this course to contact the instructors or the instructional support coordinator to arrange any necessary accommodations.

If you are on or near campus, the following services are provided to you by the University and by the Waterloo Undergraduate Student Association:

  1. Campus Wellness. https://uwaterloo.ca/campus-wellness/
  2. Counselling Services.  counselling.services@uwaterloo.ca. +1-519-888-4567 ext 32655. Needles Hall North 2nd floor, (NH 2401)
  3. MATES: one-to-one peer support program offered by WUSA and Counselling Services.  mates@uwaterloo.ca
  4. EmpowerME: a mental health and wellness service provided by WUSA. +1-833-628-5589 in North America, international numbers available at http://studentcare.ca/RTEContent/Document/EN/FAQ/Empower_Me_Optima_FAQ.pdf
  5. Health Services: located across Laurel Creek from the Student Life Centre. +1-519-888-4096.

In addition, the following off-campus services are provided by the local community:

  1. Good2Talk (24/7): Free confidential help line for post-secondary students. Phone: +1-866-925-5454.
  2. Here 24/7: Mental Health and Crisis Service Team. Phone: +1-844-437-3247.
  3. OK2BME: set of support services for lesbian, gay, bisexual, transgender or questioning teens in Waterloo. Phone: +1-519-884-0000 extension 213.

Collaboration: Assignment solutions must be written individually, in your own account, with your own code and your own tests. It is an academic offense to share Marmoset accounts, for the purpose of using extra release tokens for testing, or for any other purpose. While you are allowed to discuss the assignments verbally with each other, you are not allowed to share code with each other and you are not allowed take any written notes during such discussions. We understand that you will probably set up study groups on IM platforms such as Discord, Slack, Facebook, etc. We recommend that you only discuss assignments over video or audio call and refrain from substantive assignment discussion over text on these IM platforms. Please don’t screenshare your code either! Violations of the collaboration policy will incur the standard penalty under Policy 71 for all parties involved; that is, a 5% penalty on the final course grade and a 0% on the assignment in question.

Misconduct: We expect that students make a good faith attempt at solving assignment questions.  Students that attempt to deceive the grading system by submitting a program that simply prints or returns values in order to match expected test results rather than making an actual, reasonable attempt to solve the problem as required in the assignment question specification are guilty of an academic offense, and will incur the standard penalty under Policy 71; that is, a 5% penalty on the final course grade and a 0% on the assignment in question.

Intellectual Property: Students should be aware that this course contains the intellectual property of their course staff and the University of Waterloo. Intellectual property includes items such as:

  1. Lecture content, spoken and written (and any audio/video recording thereof);
  2. Lecture handouts, presentations, and other materials prepared for the course (e.g., PowerPoint slides, PDF documents);
  3. Questions or solution sets from various types of assessments (e.g., assignments, quizzes, tests, final exams); and
  4. Work protected by copyright (e.g., any work authored by the instructor or TA or used by the instructor or TA with permission of the copyright owner).

Course materials and the intellectual property contained therein, are used to enhance a student’s educational experience. However, sharing this intellectual property without the intellectual property owner’s permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).

Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).

Territorial Acknowledgement: The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within the Office of Indigenous Relations

Generative AI

This course includes the independent development and practice of specific skills; we're looking to see if you can write a compiler. Therefore, the use of Generative artificial intelligence (GenAI) trained using large language models (LLM) or other methods to produce text, images, music, or code, like Chat GPT, DALL-E, or GitHub CoPilot, is not permitted in this class. Unauthorized use in this course, such as running course materials through GenAI or using GenAI to complete a course assessment is considered a violation of Policy 71 (plagiarism or unauthorized aids or assistance). Work produced with the assistance of AI tools does not represent the author’s original work and is therefore in violation of the fundamental values of academic integrity including honesty, trust, respect, fairness, responsibility and courage (ICAI, n.d.). 

You should be prepared to show your work. To demonstrate your learning, you should keep your code in source control, for example on GitHub or the University's GitLab instance, and your rough notes, including research notes, brainstorming, and drafting notes. You may be asked to submit your notes along with earlier drafts of their work, either through saved drafts or saved versions of a document. If the use of GenAI is suspected where not permitted, you may be asked to meet with your instructor or TA to provide explanations to support the submitted material as being your original work. Through this process, if you have not sufficiently supported your work, academic misconduct allegations may be brought to the Associate Dean. 

In addition, you should be aware that the legal/copyright status of generative AI inputs and outputs is unclear. More information is available from the Copyright Advisory Committee: https://uwaterloo.ca/copyright-at-waterloo/teaching/generative-artificial-intelligence 

Students are encouraged to reach out to campus supports if they need help with their coursework including: 

 

University Policy

Academic integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check the Office of Academic Integrity for more information.]

Grievance: A student who believes that a decision affecting some aspect of their university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt, please be certain to contact the department’s administrative assistant who will provide further assistance.

Discipline: A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for their actions. [Check the Office of Academic Integrity for more information.] A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes they have a ground for an appeal should refer to Policy 72, Student Appeals.

Note for students with disabilities: AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.

Turnitin.com: Text matching software (Turnitin®) may be used to screen assignments in this course. Turnitin® is used to verify that all materials and sources in assignments are documented. Students' submissions are stored on a U.S. server, therefore students must be given an alternative (e.g., scaffolded assignment or annotated bibliography), if they are concerned about their privacy and/or security. Students will be given due notice, in the first week of the term and/or at the time assignment details are provided, about arrangements and alternatives for the use of Turnitin in this course.

It is the responsibility of the student to notify the instructor if they, in the first week of term or at the time assignment details are provided, wish to submit alternate assignment.