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.

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.