Recursive Programming

Our universe of objects consists of atom and list. There are two kinds of atom: integer, string.  With few simple functions to manipulate them.

functions

head(L)
tail(L)

L == cons(head(L),tail(L))

cons always creates a new cell.

examples of list

simple list  (1 2 3)     can be created by    

cons( number(1), cons( number(2), cons( number(3), nil)))

a list can contain another list.  This is called complex list.  ( (1 2) 3) can be created by

cons(  cons( cons( number(1), cons(number(2), nil)), cons(number(3), nil))

Now we will do programming based on two goals:

list -> number
number -> list

list -> number

count: simple, complex list

count_simple(L)
  if L == nil ret 0
  ret 1 + count_simple(tail(L))

count_complex(L)
  if L == nil ret 0
  if isatom(head(L)) ret 1 + count_complex(tail(L))
  ret count_complex(head(L)) + count_complex(tail(L))

number -> list    using cons()

Let us creates a number with a list, using unary system. 

We will create this kind of number and function to add them.

unary(n)
  if n == 0 ret nil
  ret cons( number(1), unary(n-1))

uadd(a,b)            // where a, b are unary number
  if a == nil ret b
  ret uadd( tail(a), cons( head(a), b))

Homework

1) write a recursive  reverse(L)
2) write a copy_list(L)  return a new list (L can be complex)

data == program

I will show how to represent a program with List. Use count_simple(L) as a case study.

We will represent a statement by a list with the first element as "operator" and the rest of the list are the arguments to that operation.

( op arg1 arg2 ... )

to define a function we will use the operator "def". So, to define count_simple(L):

program -> ( "def" "count_simple" arglist body )
 
arglist -> ( "L" )

the body of this function consists of two lines.

line1 -> ("if" ( "==" "L" nil) ("ret" 0))
line2 -> ("ret" ("+" 1 ("count_simple" ("tail" "L")))

nil is a special atom is our universe of objects. To represent a "block" of statement we use the operator "do".

body -> ("do" line1 line2)

with this representation of a program as a list (data), we can write an interpreter to evaluate (run) this program.

This is a complete picture of a list representing the count_simple function:

("def" "count_simple" ("L")
  ("do"
    ("if" ("==" "L" nil) ( "ret" 0))
    ("ret" ("+" 1 ("count_simple" ("tail" "L")))))

end

last update 9 Nov 2017