代写 lisp scala software COMP3109 Assignment 1 Programming in Functional Languages (10 marks)

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., .zip.
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 )thatcheckswhetherthematrixiswell-formed. If the matrix is well-formed, return T; otherwise nil. You may want to break up this task into two functions. The first function checks whether the shape of the matrix is correct, i.e., all rows have the same length. The second function checks whether the elements of the matrix are symbolic expressions.
Task 2 Shape of a Matrix (1 marks)
Writeafunction(m-shape )thatreturnstheshapeofthematrix.Forexample,
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 is well-formed. For example,
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 ) that returns the symbolic expression of the n-th row and m-th column. If the matrix is ill-formed, return nil. For example,
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 )
(+ 0)
(+ )
(* 1 )
(* 1)
(* )
(* (+ ) )
(* (+ ))
(+ )
(+ (* ) (* ))


+
⇒ c

*
⇒ (+ (* ) (* )) ⇒ (+ (* ) (* )) ⇒ (* 2 )
⇒ (* + )
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 ) that adds two matrices symbolically. If the shape of both matrices don’t comply or are ill-formed, return NIL. For example,
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 )thatmultipliestwomatrices,i.e.,giventwo matricesA,BtheelementsoftheresultmatrixC=A·Baregivenbycik =􏰀jaijbjk.Ifthematrices have the wrong shapes or are ill-formed, return NIL. Please don’t perform any simplifications on the result.
Task 6 Scalar-Multiplication (1 marks)
Write a function (m-scalar-mul ) that multiplies the scalar (as a symbolic expression) with the matrix . Please don’t perform any simplifications and return nil if scalar or matrix are not well-formed.
Task 7 Simplification (4 marks)
Writeafunction(m-simplify )thatsimplifiestheelementsofthematrix.Useahelper function that simplifies a symbolic expression. Given are a set of rewrite rules. They are applied until no further applications lead to further simplications. The rules are given below:

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