Append procedure in scheme

Question

I have been recently learning Scheme and in a tutorial i found a procedure called append

(define append
(lambda (ls1 ls2)
(if (null? ls1)
    ls2
    (cons (car ls1) (append (cdr ls1) ls2)))))

I didn't understand the logic behind this but understood that it attaches the members of the first list one by one to the second list.Can anyone explain me the last line of the procedure? And what does cons with the two arguments mean?

I ran

(trace (append '( a b c) '(d e f)))

and ended up with

[Entering #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]
[Entering #[compound-procedure 4 append]
Args: (b c)
      (d e f)]
[Entering #[compound-procedure 4 append]
Args: (c)
      (d e f)]
[Entering #[compound-procedure 4 append]
Args: ()
      (d e f)]
[(d e f)
  <== #[compound-procedure 4 append]
Args: ()
      (d e f)]
[(c d e f)
  <== #[compound-procedure 4 append]
Args: (c)
      (d e f)]
[(b c d e f)
  <== #[compound-procedure 4 append]
Args: (b c)
      (d e f)]
[(a b c d e f)
  <== #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]
;The object (a b c d e f), passed as an argument to procedure-lambda, is not a procedure.

It'd be gud if you explain how to read this trace results!

Answer 1

First off you use trace wrong. You need to call it on the procedure you are going to trace, not an expression. Like this:

(trace append)

The last line is trace complaining about it not being able to trance the list (a b c d e f). The trace output you see is from a previous call to trace done right!

Now for how to read.. Every entry looks like:

[Entering #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]

That means the same as (append '(a b c) '(d e f)). Here is the exit trace from the same instance:

[(a b c d e f)
  <== #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]

This says it returns (a b c d e f) and the call was (append '(a b c) '(d e f)).

Notice that these two doesn't come after each other. The reason is that the cons step needs to wait for the recursive step to do (b c d e f) first. All lists are made from end to beginning.

If we call (append '(a b c) '(d e f)) this is what happens:

(append '(a b c) '(d e f))                          ; ==>
(cons 'a (append '(b c) '(d e f)))                  ; ==>
(cons 'a (cons 'b (append '(c) '(d e f))))          ; ==>
(cons 'a (cons 'b (cons 'c (append '() '(d e f))))) ; <==
(cons 'a (cons 'b (cons 'c '(d e f))))              ; <==
(cons 'a (cons 'b '(c d e f)))                      ; <==
(cons 'a '(b c d e f))                              ; <==
'(a b c d e f)                                      ; result

In reality the parameters expressions evaluates to values, but I quote them here so that you can paste these in the REPL and get the same result on all lines.

the evaluation order here is the same as in your trace.