Question

What is an S-expression? 

What is a cons cell? 

What is an atom? A pair? A list? 

What do car and cdr do? 

What do the map and reduce functions do? 

Write a recursive function to compute the length of a list. 

Write a function to compute the length of a list using reduce.

Answer 1

what is an S-expression?

S-expression, also known as sexpr or sexp. It is a way to represent a nested list of data. It stands for symbolic expression and it is used in Lisp programming language. The  variants of Lisp such as Scheme, Racket, and Clojure. These programming languages use s-expressions to represent the computer program, as well as the program's data.

Example: The simple mathematical expression "six times the sum of four and two" can be written as a s-expression with prefix notation. In Lisp, the s-expression might look like the example below.

(* 6 (+ 4 2))

what is a cons cell?

Lists in the Lisp language are not primitive data type, they are built from cons cell. Cons cell are data objects represents the ordered pair, it has two slots and each slot holds or refer to some Lisp object. One slot is car and the other one is cdr. (These names are traditional) cdr is "could-er".

"the car of this cons cell is" whatever object its car slot currently holds, and like wise for the cdr.

List is a series of cons cells chained together, so the each cell refers to the next one. There are one cons cell for each element of the list. In convention, cars of the cons cell hold the elements of the list and cdrs are used to chain the list(this asymmetry between car and cdr is entirely matter of convention. the level of cons cells, the car and cdr slots have similar properties). Thus the cdr slot of each cons cell in list refers to the following cons cell.

what is a atom?A pair? A list?

The definition of an atom varies per context, it is assumed that there exists, An infinite set of distinguishable atomic symbols can be represented as strings of capital Latin letters and digits with single embedded blanks.(character string and numeric literals). Most modern sexpr notation in addition use an abbreviated notation to represent lists in s-expression, so that

(a b c)

stands for

(a. (b. (c .NIL)))

where NIL is the special end-of-list object.

Pair joins two arbitrary values. Cons procedure constructs pairs, car and cdr procedures extract the first and second elements of the pair.

List is combination of pairs that creates a linked list. List is either the empty list null, or it is pair whose first element is a list element and second element is a list.

what do car and cdr do?

Cons cell are data objects represents the ordered pair, it has two slots and each slot holds or refer to some Lisp object. One slot is car and the other one is cdr. (These names are traditional) cdr is "could-er".

"the car of this cons cell is" whatever object its car slot currently holds, and like wise for the cdr.

List is a series of cons cells chained together, so the each cell refers to the next one. There are one cons cell for each element of the list. In convention, cars of the cons cell hold the elements of the list and cdrs are used to chain the list(this asymmetry between car and cdr is entirely matter of convention. the level of cons cells, the car and cdr slots have similar properties). Thus the cdr slot of each cons cell in list refers to the following cons cell.

what do the map and reduce functions do?

Map function takes set of data and converts into another set of data, where individual elements are broken down into tuples(key/value pairs)

Reduce function task, takes the output from the map as an input and combines those data tuples into smaller set of tuples.

write a recursive function to compute the length of a list?

def lislength(l):
     if l:
         return 1 + lislength(l[1:])
     return 0

write a function to compute the length of a list using reduce?

import reduce # reduce() is built-in in Python 2.

def list_length(L):
    return reduce(lambda x,y: x+1, L, 0)