lisp代写: COMPT 306 assignment1

•   To become familiar with the basic features of Lisp syntax and semantics.
•   To become acquainted with the techniques of pure functional programming.
•   To learn to think recursively.

  NOTE:Properly acknowledge (add a note and/or hyperlink and/or comment) any help or resource you used.

  1) Write a set of LISP functions to implement the following operations on polynomials:

•   Poly-add – to add two polynomials
•   Poly-sub – to subtract two polynomials
•   Poly-mul – to multiply two polynomials
•   Poly-der – to compute the derivative of a polynomial
•   Poly-val – to compute the value of a polynomial for a given argument
•   Poly-prim – to compute the primitive(antiderivative) of a polynomial

  A polynomial will be represented as an association list. There will be one sublist for each term of the polynomial. Each sublist will have the exponent of the term as the first component and the coefficient as the second component. Ex: 3X5+3X3+7 is represented as ((5 3) (3 3) (0 7)).

  2)Write the LISP function:
  (deep-subst x y L)
  that returns a list L1 formed by replacing, within the recursive-list L, each occurrence of the atom x (at any level) with the atom y. (You may assume that L is a recursive list, and that x and y are each atoms.)

  (deep-subst 4 t '(truth is 4)) → (TRUTH IS T)
  (deep-subst 4 nil '(4 is not (4))) → (NIL IS not (NIL))
  (deep-subst 4 nil '(5 is not (22))) → (5 is not (22))
  

  3) Write the LISP function
  (count-sub-list-occ L1 L2)
  That returns the number of occurrences of the list L1 as a sublist of L2. L1 is a sublist of L2 if all the elements of L2 can be found in sequence in L1.
  For example: (1 2) is a sublistof (3 1 2)

  (1 3) is not a sublist of (1 2 3)
  (1 3) is not a sublist of (3 2 1)
  (1 1) is a sublist of (2 3 2 3 1 1 3 2)

  (count-sub-list-occ '(1 2) '(1 2 3))→1
  (count-sub-list-occ '(1 2) '(3 2 3))→0
  (count-sub-list-occ '(1 2) '(1 2 1 2 3))→2
  (count-sub-list-occ '(1 1) '(1 1 1 1))→3
  

4) The following procedure illustrates a possible way of generating password for different servers:
1. Start with an easy to remember sentence. Get a letter code by taking the first letter of each word in the

sentence. If the sentence contains numbers, then the entire number is selected in the code. o For example:

•   The sentence “How I wish how I wish you were here” generates the code HIWHIWYWH
•   The sentence “There were 12 of us this morning I am the only one this evening”, generates

  the code TW12OUTMIATOOTE.

2. Add the first letter of the server name in front of the code and the last letter of the server name after the

code to generate an intermediate password o For example:

•   If the server name is “My new cool business” and the code is HIWHIWYWH, the intermediate password is MHIWHIWYWHS
•   If the server name is “MacEwan” and the code is TW12OUTMIATOOTE the intermediate password is MTW12OUTMIATOOTEN

3. Consider a replacement list which specifies pairs of symbols, where each occurrence of the first symbolis to be replaced by the second symbol. Get the final password by replacing the symbols of the intermediate password according to the replacement list.

o For example:
 If the intermediate password is MHIWHIWYWHS and the replacement list is ( (S 5) (I 1))

the final password is: MH1WH1WYWH5
 If the intermediate password is TW12OUTMIATOOTE and the replacement list is ((T 7) (M

Q) (O 0)) the final password is: 7W120U7QIA7007E

Write the LISP function:

(gen-passsn-list st-list subst-list)
That returns a password formed as explained above for the server name list sn-list, sentence list st-list and replacement list subst-list. The sn-list and the st-list are lists which contains the letters of each word as lists.
For example:
The site-name “My new cool business” is represented as
‘((m y) (n e w) (c o o l) (b u s i n e s s)) .
The sentence “How I wish how I wish you were here” is represented as
‘((h o w) (i) (w i s h) (h o w) (i) (w i s h) (y o u) (w e r e) (h e r e)).The replacement list is a list of pairs – where the first element specifies the symbol to be replaced and the second one specifies the symbol to replace it by.

(gen-pass
 ‘((m y)  (n e w) (c o o l) (b u s i n e s s))
 ‘((h o w) (i) (w i s h)  (h o w)  (i) (w i s h) (y o u) (w e r e) (h e r e))
 ‘( (O 0) (I 1))) → '(M  H 1 W H 1 W Y W H S)

(gen-pass
 ‘((m a c e w a n))

‘((
There)(were)(12)(of)(us)(this)(morning)(i)(am)(the)(only)(one)(this)(evening)
),

 ‘( (W 3) (T7))) → '(M 7 3 1 2 O U 7 M I A 7 O O 7 E N)

Implementation is subject to the constraint that it should illustrate pure functional programming; that is, it should not use set, setf, setq, or any other binding primitive. You may use set, etc., for the purposes of testing your functions, but not in any of the functions that form part of your solution to the problem. You may, of course, define any other subsidiary functions that you might find useful. The list of LISP built-in functions and forms that you can use is attached to this assignment..

Correctness – The programs should conform to the specifications for which it was written. It should include correct handling of special cases, error conditions, etc., except that you may assume that input will be provided in the specified format. Your file must load without error in the clisp evaluator installed on ugrad.cs.macewan.ca. There is a 50% penalty if errors are detected at loading time.

Design and Efficiency – The program should be constructed from small, coherent, independent and loosely coupled functions. Each function should access only its own parameters. The control constructs and data structures used should be those appropriate to the problem at hand. The program should not perform unnecessary steps, use extraneous variables, nor implement the algorithm in a contorted or inefficient way. Your functions must be documented – through comments and properly indented.

Marking scheme: