ECS140A-Project 3 Solved

For this programming assignment you will be programming in LISP.  This entire project must be purely functional; you are not allowed to use setq, loop or similar constructs. Points may be docked for use of such constructs.

Fibonacci Sequence Less Than N
Write a function fibo-lt to return a list as the Fibonacci sequence such that all numbers in the sequence are less than n (NOT the first n numbers of the sequence). For example:

(fibo-lt '50) 

(0 1 1 2 3 5 8 13 21 34) 

Your function must run in sublinear time and may not hardcode results except for those of the beginning of the sequence such as '(), '(0) and '(0 1).

Pattern Matching Program 
Before we start building the pattern matching function, let us first build a set of routines that will allow us to represent facts, called assertions. For instance, we can define the following assertions:

(this is an assertion) 

(color apple red) 

(supports table block1) 

Patterns are like assertions, except that they may contain certain special atoms not allowed in assertions, the single ! character, for instance, or may have strings containing the * character.

(color ! red) 

(su*ts table block1) 

Write a function match, which compares a pattern and an assertion. When a pattern containing no special atoms is compared to an assertion, the two match only if they are exactly the same, with each corresponding position occupied by the same atom.

(match '(color apple red) '(color apple red)) 

T 

(match '(color apple red) '(color apple green)) NIL 

The special symbol '!' expands the capability of match by matching zero or more atoms.

(match '(! table !) '(this table supports a block)) T 

Here, the first symbol '!' matches this, table matches table, and second symbol '!' matches supports a block.

(match '(this table !) '(this table supports a block)) 

T 

(match '(! brown) '(green red brown yellow)) NIL 

In the last example, the special symbol '!' matches 'green red'. However, the match fails because yellow occurs in the assertion after brown, whereas it does not occur in the assertion. However, the following example succeeds:

(match '(! brown) '(green red brown brown)) T 

In this example, '!' matches list (green red brown), whereas the brown matches the last element.   

(match '(red green ! blue) '(red green blue)) T 

In this example, the '!' matches the empty list.  The * character matches zero or more characters inside a string.

(match '(red gr*n blue) '(red green blue)) 

T 

(match '(t* table is *n) '(this table is blue)) NIL 

In the first example the *, matches ee.  In the second example the first * matches his, but the second one fails to match because of the n.  The lone * will match any single atom.

(match '(color apple *) '(color apple red)) 

T 

(match '(color * red) '(color apple red)) 

T 

(match '(color * red) '(color apple green)) 

NIL 

In the last example, color * red and (color apple green) do not match because red and green do not match.

Erasure Code Reconstruction
Erasure codes are used when a value can be detected as incorrect (or erased). They are commonly used in storage (like in RAID-5) as well as in communication. Write a function to return a reconstructed message. Each message will be a set of words each with a parity bit followed by a parity word. Each word is represented as a list of 0, 1 or NIL values. The parity bit will be the final value in each word, the parity word will be the final word in the list of words. An example output should be something like:

(parity-correction '((0 1 1 NIL 0) (0 0 0 NIL 1) (NIL 1 1 1 0) (1 0 1 

NIL 0) (0 NIL 1 0 1))) 

(T ((0 1 1 0 0) (0 0 0 1 1) (1 1 1 1 0) (1 0 1 0 0) (0 0 1 0 1))) This would be equivalent to the following message.

 
D0 
D1 
D2 
D3 
P 
W0 
0 
1 
1 
0
0 
W1 
0 
0 
0 
1
1 
W2 
1
1 
1 
1 
0 
W3 
1 
0 
1 
0
0 
WP 
0 
0
1 
0 
1 
If the message is incorrect or can’t be solved NIL should be returned with the original message. For example:

(parity-correction '((0 1 1 NIL 0) (0 0 0 NIL 1) (NIL 1 1 1 0) (1 0 1 

NIL 0) (0 NIL 1 0 0))) 

(NIL ((0 1 1 NIL 0) (0 0 0 NIL 1) (NIL 1 1 1 0) (1 0 1 NIL 0) (0 NIL 1 

0 0)))