Solutions to the quiz 1 (language theory)

1.1  3)  Write a recursive program to do the following. Having a complex list input such as :  (1 (2 3) (4)), replace every "4" in the list with "8", the above list will become:  (1 (2 3) (8))

Solution

We show how to do the simple list first.  Here is the pseudo code:

repl(a)
1:  if a == nil then ret nil
2:  if head(a) == 4 then ret cons(8, repl(tail(a))
3:  ret cons(head(a), repl(tail(a))

line 1:  terminate when input is exhausted
line 2:  check element, if it is 4 then substitute with 8, recurse on tail(a)
line 3:  otherwise, go into tail(a) to replace recursively

Now we will tackle the complex list, must handle the case head(a) is a list.

repl2(a)
1:  if a == nil then ret nil
2:  if isatom(head(a))
3:     if head(a) == 4 then ret cons(8, repl2(tail(a))
4:     else ret cons(head(a), repl2(tail(a))
5:  ret cons(repl2(a), repl2(tail(a))

line 1: terminate case
line 2: check the case that element is an atom then
line 3-4:  do similar to replace simple list
line 5: otherwise, replace into head(a), replace into tail(a), then cons()


Here is the C source (used with ailib)// test atom equality
int eqatom(int a,int b){
  return (head(a) == head(b)) && (tail(a) == tail(b));
}

// replace with complex list
int repl2(int a){
  if( a == NIL ) return NIL;
  if( isatom(head(a)) ){
    if( eqatom(head(a),number(4)) ) return cons(number(8),repl2(tail(a)));
    else return cons(head(a), repl2(tail(a)));
  }else
    return cons(repl2(head(a)), repl2(tail(a)));
}

1-2  3)  Write a recursive program to do the following. Having a complex list input such as :  (1 (2 3) (4)), reverse the list, the above list will be :   ((4) (3 2) 1)

Do the simple list first.  Use a second function to hold "accumulating parameter" ( revs(a,b) ).  Here is the pseudo code:

rev(a)
  revs(a,NIL)

revs(a,b)
  if a == NIL then ret b
  ret cons(head(a), revs(tail(a),b))

With it, now we can do the complex list, must handle the case head(a) is a list.

rev2(a)
  revs2(a,NIL)
 
revs2(a,b)
  if a == NIL then ret b
  if isatom(head(a)) then ret cons(head(a), revs2(tail(a),b))
  ret cons(revs2(head(a),NIL), revs2(tail(a),b))

here is the C source (used with ailib)

// reverse complex list
int revs2(int a, int b){
  if( a == NIL ) return b;
  if( isatom(head(a)) ) return revs2(tail(a), cons(head(a),b));
    return revs2(tail(a), cons(revs2(head(a),NIL), b));
}

int rev2(int a){
  return revs2(a, NIL);
}

last update 19 Sept 2018