Using Car and Cdr
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...
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.
1 Answer
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.
Maya is a hardware enthusiast who tests and reviews smart home devices, smartphones, wearables, and audio gear. She focuses on practical consumer value and build quality.
