functional programming - Using car and cdr

Question

I am new to scheme and having a hard time with using car and cdr. I have an AST string literal in ast.

(define ast '(program
  ((assign (var i int) (call (func getint void int) ()))
   (assign (var j int) (call (func getint void int) ()))
   (while (neq (var i int) (var j int))
    ((if (gt (var i int) (var j int))
         ((assign (var i int) (minus (var i int) (var j int))))
         ((assign (var j int) (minus (var j int) (var i int)))))))
   (call (func putint int void) ((var i int)))))
)

I know car returns the head of ast. So

(car ast)

returns 'program.

I am confused how to use car and cdr to get strings from ast such as 'assign, 'while, 'if, and 'call.

Answer 1

You need to understand how pairs and lists are built, from The Racket Reference:

A pair combines exactly two values. The first value is accessed with the car procedure, and the second value is accessed with the cdr procedure. Pairs are not mutable (but see Mutable Pairs and Lists).

A list is recursively defined: it is either the constant null, or it is a pair whose second value is a list.

Basically every Pair (x . y) is made of two elements - car gets us x cdr gets us y.

Notice that x and y can both be pairs or lists themselves, just like your AST, ie(out of same reference):

> (define lst1 (list 1 2 3 4))

>lst1 

'(1 2 3 4)

notice that '(1 2 3 4) is actually: (1 . ( 2 . ( 3 . ( 4 . ()))) <-- Very important to know the implementation in scheme.

> (car lst1)

1

> (cdr lst1)

'(2 3 4)

> (car (cdr lst1))

2

Another way to chain car and cdr calls(read from the right): cadr means (cdr lst) and then apply car on the answer => (car (cdr lst)) == (cadr lst)

> (cdddr lst1)

'(4)

> (cadddr lst1)

4

> (define lst2 (list (list 1 2) (list 3 4)))

>lst2 

'((1 2) (3 4)) 

== ( ( 1 . ( 2 . ()) ) . ( 3 . ( 4 . () )))

> (car lst2) 

'(1 2)

>(cdr lst2)

'((3 4))

which is actually ((3 . (4 . () ) ) . () ) == ((3 4) . ()) == ((3 4))

You did not ask but I'm assuming you are going to traverse through the tree/list. Ultimately you will have to traverse with a recursion (unless using advanced method not suitable at this stage, ie check CPS when ready ) like so:

(define runner 
  (lambda (tree)
    (if (null? tree)
        null
        (let ((first_element (car tree))
              (rest_of_tree  (cdr tree)))
          ;body:
          ;do some logic like:
              ;if first is list call runner on it:
              ;(runner rest_of_tree)
              ;possibly chain answer of logic and call together
              ;else check/return string is there (recognize tree root)
          ))))

Hope this helps questions welcome.