COMP3109 Assignment 1 Programming in Functional Languages (10 marks)
This first assignment is an individual assignment, and is due on Friday, at 6pm, in Week 6. The aim of this assignment is to implement a symbolic rewrite system for matrix calculations.
For assessment, please pack the source code into a zip-file and submit it via Canvas. Please use your unikey for the name of your zip-file, i.e.,
The documentation of the program should be done in form of comments. Please be verbose with your comments, i.e., explain your ideas how you have implemented the program in plain English thoroughly. Not complying to documentation standards will give you less marks for your assignment (see rubric). Note that we will employ plagiarism detection software to detect plagiarism. Don’t plagiarize!
In this assignment you will implement a computer algebra system for matrix calculations. The as- signment is in LISP using the CLISP dialect. CLISP is available for a wide range of system including Linux and MacOS. We recommend to use the Linux sub-system for Windows user.
Have in the zip-file two files: the first file matrix.clisp contains the function declarations of your assignment; the second file contains your test-cases for the submission tests.clisp. Make sure that you follow the correct naming of the files.
Store your test-cases in the tests.clisp file. Note that for your submission you need to find and write at least 5 test-cases for each self-written function in CLISP. The naming of the functions (given in the assignment spec) must not change since we will use some (semi-)automatic marking.
A symbolic n × m matrix
is represented in lisp as
1 (setq A ‘( (a11 …
where A is a list containing n lists. Each of the lists has length m. We assume that the smallest
possible matrix is a 1 × 1 matrix in our system.
Amatrixelementaij foralli,1 ≤ i ≤ n,andallj,1 ≤ j ≤ m,isasymbolicexpressionE. A
symbolic expression E is defined as follows:
1. Ifxisanumber,thenxisinE.
2. Ifvisasymbol,thenvisinE.
3. Ife1 ∈Eande2 ∈E,then(+ e1 e2)isinE.
a11 … a1m .
A= . … an1 … anm
a1m) … (an1 … anm) ))
1
4. Ife1 ∈Eande2 ∈E,then(* e1 e2)isinE. 5. Nothing else is in E
An example of a well-formed symbolic matrix is
1 (setq A ‘((1 (+ x 2)) ((* 1 z) y))) An example of an ill-formed symbolic matrix is
1 (setq A ‘((1 x y) (1 (/ y 2))))
because the first row of the matrix has 3 columns but the second row has two columns, i.e., all rows
musthavethesamenumberofcolumns.Inaddition,thesub-expression(/ y 2)isnotinE.
Task 1 Correctness Check (1 marks)
Writeafunction(m-check
Task 2 Shape of a Matrix (1 marks)
Writeafunction(m-shape
1 (setq A ‘((1 x y) (1 x y)))
2 (m-shape A)
returns the list
1 (23)
since the matrix has two rows and three columns. Call function m-check in m-shape to check
whether the input matrix
1 (setq A ‘((1 y) (1 x y)))
2 (m-shape A)
should return NIL because A is not a well-formed matrix.
Task 3 Matrix Element (1 marks)
Write a function (m-elem
1 (setq A ‘((1 x) (1 y)))
2 (m-elem A 1 2)
would return x.
Programming Languages and Paradigms Page 2 of 4
COMP3109
(+ 0
(+
(+
(* 1
(*
(*
(* (+
(*
(+
(+ (*
⇒
⇒
⇒
⇒ c
⇒
⇒
⇒ (+ (*
⇒ (*
and are are applied to all levels of the symbolic expression.
Programming Languages and Paradigms Page 3 of 4
COMP3109
Task 4 Addition (1 marks)
Write a function (m-add
1 (setq A ‘((p q) (r s)))
2 (setq B ‘((1 2) (3 4)))
3 (m-element A B)
would result in
1 (((+ p 1) (+ q 2)) ((+ r 3) (+ s 4)))
Please don’t perform any simplifications. For example, (+ 1 1) stays (+ 1 1) and won’t be sim-
plified.
Task 5 Multiplication (1 marks)
Writeafunction(m-mul
Task 6 Scalar-Multiplication (1 marks)
Write a function (m-scalar-mul
Task 7 Simplification (4 marks)
Writeafunction(m-simplify
Come up with at least 5 more rewrite rules that further simplify a symbolic expression. However, make sure that the added rules make the system terminate for any given input.
For example,
1 (setq A ‘(((+ 1 2) (+ 0 q)) ((* 1 r) s)))
2 (m-simplify A)
should give
1 ((3 q) (r s))
COMP3109
Programming Languages and Paradigms
Page 4 of 4