Send
Close Add comments:
(status displays here)
Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.
Lists: Prolog, Lisp, etc.
1. Lists: Prolog, Lisp, etc.
2. Lists
Lists are very general structures that can be used to represent lists, trees, etc.
3. Low level representation
It can be helpful to understand some of the low-level details of how lists are represented in memory.
4. Views
There is a logical and a physical view of lists and tree structures.
The logical view (e.g., in program code) is how one can think about the structure.
The physical view is how the structure is represented in memory and more closely relates to what is studied in a data structures or algorithms course.
5. Example tree structure as a list
Here is the example expression.
X & Y
Here is the example tree structure as a list that represents the logical view.
["op2", "and"
["var", "X"],
["var", "Y"]
]
6. Logical view
Here is a logical view of the expression.
["op2", "and"
["var", "X"],
["var", "Y"]
]
7. Physical view
Here is the example tree structure as a physical view using
cons as the list constructor and
nil as the empty list.
["op2", "and"
["var", "X"],
["var", "Y"]
]
8. Abstraction
In abstraction terms, it is easier to think about the tree structure in the logical view rather than the physical view.
9. Lists
A list has the following inductive definition.
Lisp: nil is a list, the empty list.
Prolog: [] is the empty list.
If
X is an item, such as an integer, string, or list, then the list consisting of just
X is as follows.
Lisp: '( X . nil )
Lisp: '( X )
Prolog: [ X | []]
Prolog: [ X ]
10. Lisp quoted notation
In Lisp, if a singe quote is not used, the list expression will be evaluated. Lisp expressions are in prefix form so the first element should be a function that takes as arguments the rest of the list.
So the Lisp expression
(add 2 3)
evaluates to
5. The quote avoids the evaluation.
11. Constructing a list
If X and Y are items then the following is the list with head X and tail Y.
Lisp: '( X . ( Y . nil ))
Lisp: '( X Y )
Lisp: (cons X (cons Y nil ))
Lisp: (list X Y)
Prolog: [ X | [ Y | []]]
Prolog: [ X , Y ]
Lisp: The cons operator is the dot ".".
Prolog: The cons operator is the vertical bar "|".
The Lisp notation is called a dotted S-expression.
12. General concept
Lisp: S expression
Prolog: term structure
13. Head and tail of a list
The head of a list is the first item in the list.
Lisp: ( X . Y ) has head X and tail Y
Lisp: ( X Y ) has head X and tail Y
Prolog: [ X | Y] has head X and tail Y
Prolog: [ X , Y ] has head X and tail Y
14. Prolog cons operator for lists
The following Prolog lists and terms unify (i.e., are true).
[a] = '.'(a,[])
[a,b] = '.'(a,'.'(b,[]))
[a,b|c] = '.'(a,'.'(b,c))
15. Tail of a list
The tail or rest of a list is the list without the head of the list. Lisp calls this the cdr (coulder).
16. End of page
