CS350A Assignment 2 & 3

This is the repository for assignment 2 & 3 of CS350A: Principles of Programming Languages, offered in the odd semester of 2019. The goal is to build an interpreter for the kernel language of the Oz programming language, given its AST. This supports the declarative concurrent model (lazy execution is not supported).

Group Members

• Harish Rajagopal (160552)
• Vishwas Lathi (160808)

Requirements

• Python 3.6+

Instructions

1. Change the current directory to the root of this repository.

2. Choose a test case from the "testcases" directory.

3. Run the interpreter as follows:

   ./run.py name_of_testcase

   For example, if you want to use the test case "testcases/conditionals_1.py":

   ./run.py conditionals_1

AST Specification

The AST for the kernel language is to be written in Python.

For variables and values, the translations from the Oz syntax into the Python AST spec is as follows:

• Variable X: Ident("X"). The name of the variable must be in quotes.
• Literal 10: Literal(10). The value of the literal is written as a Python value. eg. true is Literal(True)
• Record tree(key:10 left:nil right:nil):

  [
      "record",
      Literal("tree"),
      [
          (Literal("key"), Literal(10)),
          (Literal("left"), Literal(None)),
          (Literal("right"), Literal(None)),
      ],
  ]

• Procedure proc {$ X Y} skip end:

  [
      "proc",
      [Ident("X"), Ident("Y")],
      ["nop"],
  ]

The statements allowed in the kernel language, and the format of its AST, are as follows:

Statement	Oz	AST
No-op	skip	["nop"]
Compound statements	skip skip	[["nop"], ["nop"]]
Variable creation	local X in skip end	["var", Ident("X"), ["nop"]]
Binding	X = Y	["bind", Ident("X"), Ident("Y")]
	X = 5	["bind", Ident("X"), Literal(5)]
If-else	if X then skip else skip end	["conditional", Ident("X"), ["nop"], ["nop"]]
Pattern matching	case X of nil then skip else skip end	["match", Ident("X"), Literal(None), ["nop"], ["nop"]]
Procedure call	{F X Y}	["apply", Ident("F"), Ident("X"), Ident("Y")]
Thread	thread skip end	["thread", ["nop"]]

Test Cases

There are 14 test cases, with 12 positive ones and 2 negative ones. The description of these test cases is:

Test Case	Type	Description
arithmetic	Positive	Sum and product arithmetic operations
case_1	Positive	Pattern matching for `X = 1
case_2	Positive	Both positive and negative pattern matches
conditionals_1	Positive	Simple if-else
conditionals_2	Positive	Simple if-else
deadlock_1	Negative	Two variable definitions depending on each other's values
deadlock_2	Positive	Two consecutive suspended threads, waiting for a third (the main thread)
deadlock_3	Positive	Same as "deadlock_2", but the main thread is among the suspended
deadlock_4	Negative	Same as "deadlock_2", but the third thread doesn't solve the deadlock
nested_proc	Positive	Procedure defined inside another procedure
procedures_1	Positive	Procedure with two free variables
procedures_2	Positive	Procedure with one free variable
records	Positive	Unification of X, Y and Z, where `X = 1
threads	Positive	Main thread suspended and waiting for a child thread

For running all of these tests at once:

1. Change the current directory to the root of this repository.
2. Run the testing script as follows:

   ./test.sh