Our universe of objects consists of atom and list. There are two kinds of atom: integer, string. With few simple functions to manipulate them.
head(L)
tail(L)
L == cons(head(L),tail(L))
cons always creates a new cell.
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
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))
Let us creates a number with a list, using unary system.
(1 1 1 ) -> 3
(1 1) -> 2
(1) -> 1
() -> 0
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))
1) write a recursive reverse(L)
2) write a copy_list(L) return a new list (L can be complex)
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