Printing a string in Common Lisp, after concatening function format with recursion

Question

I'm trying to learning Common Lisp reading Ansi Common Lisp from Paul Graham and Using EEC325 course critique and run-tests functions and the lectures. I set up Emacs with slime and SBCL

The problem is on chapter 3 exercise 8 says:

Define a function that takes a list and prints it in dot notation:

> (showdots ' ( a b c))
(A . (B . (C . NIL)))
NIL

I made the following function that the result is a string and it works well for the cases but doesn't print which is the main objective of the exercise

(defun show-dots (lst)
  (cond
    ((atom lst) (format nil  "~A" lst ))
    ((consp lst) (format nil "(~A . ~A)"
             (show-dots (car lst))
             (show-dots (cdr lst))))))

The problem is that it produces the string not prints the String but it works

CS325-USER> (SHOW-DOTS '(A B C))
"(A . (B . (C . NIL)))"
CS325-USER>  (SHOW-DOTS '(A (B C)))
"(A . ((B . (C . NIL)) . NIL))"
CS325-USER>  (SHOW-DOTS '(A . B))
"(A . B)"
CS325-USER>  (SHOW-DOTS NIL)
"NIL"
CS325-USER>  (SHOW-DOTS '(NIL))
"(NIL . NIL)"

The test expects for printing so really it fails but it is obvious the problems comes when printing the result

 (run-tests show-dots)
SHOW-DOTS: (SHOW-DOTS '(A B C)) failed: 
Should have printed "(A . (B . (C . NIL)))" but saw ""
SHOW-DOTS: (SHOW-DOTS '(A (B C))) failed: 
Should have printed "(A . ((B . (C . NIL)) . NIL))" but saw ""
SHOW-DOTS: (SHOW-DOTS '(A . B)) failed: 
Should have printed "(A . B)" but saw ""
SHOW-DOTS: (SHOW-DOTS NIL) failed: 
Should have printed "NIL" but saw ""
SHOW-DOTS: (SHOW-DOTS '(NIL)) failed: 
Should have printed "(NIL . NIL)" but saw ""
SHOW-DOTS: 0 assertions passed, 5 failed. 

so i thought the only thing that I must do is print this string, after creating but this things doesnt' working and I do not understand why

1) attemp

(defun show-dots (lst)
  (cond
    ((atom lst) (format t  "~A" lst ))
    ((consp lst) (format t "(~A . ~A)"
             (show-dots (car lst))
             (show-dots (cdr lst))))))

with this results

CS325-USER> (SHOW-DOTS '(A B C))
ABCNIL(NIL . NIL)(NIL . NIL)(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS '(A (B C)))
ABCNIL(NIL . NIL)(NIL . NIL)NIL(NIL . NIL)(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS '(A . B))
AB(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS NIL)
NIL
NIL
CS325-USER>  (SHOW-DOTS '(NIL))
NILNIL(NIL . NIL)
NIL

so I said Ok, this is crazy first string and the print it

(defun show-dots (lst)
 (format t (cond
    ((atom lst) (format nil  "~A" lst ))
    ((consp lst) (format nil "(~A . ~A)"
             (show-dots (car lst))
             (show-dots (cdr lst)))))))

but the result is not the correct

CS325-USER> (SHOW-DOTS '(A B C))
ABCNIL(NIL . NIL)(NIL . NIL)(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS '(A (B C)))
ABCNIL(NIL . NIL)(NIL . NIL)NIL(NIL . NIL)(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS '(A . B))
AB(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS NIL)
NIL
NIL
CS325-USER>  (SHOW-DOTS '(NIL))
NILNIL(NIL . NIL)
NIL

So I said ok let's create a local variable put there the string and print it, but it doesn't work again

(defun show-dots (lst)
  (let ((str (cond
         ((atom lst) (format nil  "~A" lst ))
         ((consp lst) (format nil "(~A . ~A)"
                  (show-dots (car lst))
                  (show-dots (cdr lst)))))))
    (format t str)))

and the result is not correct

CS325-USER> (SHOW-DOTS '(A B C))
ABCNIL(NIL . NIL)(NIL . NIL)(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS '(A (B C)))
ABCNIL(NIL . NIL)(NIL . NIL)NIL(NIL . NIL)(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS '(A . B))
AB(NIL . NIL)
NIL
CS325-USER>  (SHOW-DOTS NIL)
NIL
NIL
CS325-USER>  (SHOW-DOTS '(NIL))
NILNIL(NIL . NIL)
NIL

So I really want to understand what happens here, maybe is something silly but I do not get the point.

Thanks for yout time

Ulotrichous

Answer 1

You original function that produces the string is actually very close. The problem is that the function that generates the string shouldn't also print the string if it's going to be called recursively, since you don't want the intermediate strings to be printed as well. A very simple change you can make is to the make the main body of your show-dots function an internal helper function that creates the string, and then in the main function, print the result of the helper function:

(defun show-dots (lst)
  (labels ((%show-dots (lst)
             (cond
               ((atom lst) (format nil  "~A" lst ))
               ((consp lst) (format nil "(~A . ~A)"
                                    (%show-dots (car lst))
                                    (%show-dots (cdr lst)))))))
    (write-string (%show-dots lst))
    nil))

CL-USER> (show-dots '(a b c))
(A . (B . (C . NIL)))
NIL

Another way you could do this is by using an optional argument to indicate whether the string should be printed or returned, and it could default to printing, but in the recursive cases, you'd return it instead. Actually, since format takes t and nil as output arguments with those semantics, you can make this very sneaky:

(defun show-dots (lst &optional (output t))
  ;; If OUTPUT is T (the default) then stuff will actually be printed,
  ;; and FORMAT returns NIL.  If OUTPUT is NIL (as it is in the
  ;; recursive calls), then FORMAT creates the string and returns it,
  (cond
    ((atom lst) (format output "~A" lst))
    ((consp lst) (format output "(~A . ~A)"
                         (show-dots (car lst) nil)
                         (show-dots (cdr lst) nil)))))

CL-USER> (show-dots '(a b c))
(A . (B . (C . NIL)))
NIL

That said, both of these implementations end up creating a bunch of intermediate strings and then concatenating them together. That's not an efficient use of space. It may well be better to write to the stream as you traverse the object that is being printed. Perhaps the most direct way to do this is to handle the formatting of the parentheses and dot yourself. That would lead to a solution more or less like this (it returns nil because that was what the first example you gave did):

(defun print-dotted (object &optional (stream *standard-output*))
  "Print the object as usual, unless it is a cons, in which case
always print it in dotted notation. Return NIL."
  (prog1 nil
    (cond
      ;; write non-conses with WRITE
      ((not (consp object))
       (write object :stream stream))
      ;; write the "(" " . " and ")" by hand,
      ;; and call print-dotted recursively for
      ;; the car and the cdr.
      (t (write-char #\( stream)
         (print-dotted (car object) stream)
         (write-string " . " stream)
         (print-dotted (cdr object) stream)
         (write-char #\) stream)))))

CL-USER> (print-dotted '(a b c))
(A . (B . (C . NIL)))
;=> NIL

Now, the format function actually has the ability to call other functions when they're named in format strings, using tilde slash directive. That means that you could do something like this, which I think is kind of elegant (I defined a new package, just to illustrate that the tilde format can look up symbols in other packages; if you're doing eventhing in CL-USER, you can ignore it):

(defpackage ex
  (:use "COMMON-LISP"))

(in-package #:ex)

(defun dot-cons (stream object &rest args)
  (declare (ignore args))
  (if (consp object)
      (format stream "(~/ex:dot-cons/ . ~/ex:dot-cons/)" (car object) (cdr object))
      (write object :stream stream)))

CL-USER> (format t "~/ex:dot-cons/" '(a b c))
(A . (B . (C . NIL)))
;=> NIL

Fetching

I just updated too, to talk a bit more about your original code, which is actually very close to a solution. The second code I posted is almost identical to yours. – Fetching

Answer 2

Try to understand what this does:

CL-USER 9 > (format t "(~a ~a)" (princ 1) (princ 2))
12(1 2)
NIL

FORMAT is a function. The arguments are evaluated first. (princ 1) gets evaluated. It prints 1 and returns 1. Then (princ 2) is evaluated. It prints 2 and returns 2. The function FORMAT gets called with the evaluated arguments: t, "(~a ~a)", 1 and 2. It prints (1 2) and returns NIL.

Now look at this one:

CL-USER 8 > (progn (princ "(")
                   (princ 1)
                   (princ " . ")
                   (princ 2)
                   (princ ")"))
(1 . 2)
")"

Just reuse above when printing a cons cell:

CL-USER 10 > (defun princme (c)
               (if (consp c)
                   (progn
                     (princ "(")
                     (princme (car c))
                     (princ " . ")
                     (princme (cdr c))
                     (princ ")"))
                 (princ c)))
PRINCME

CL-USER 11 > (princme '(1 2 3))
(1 . (2 . (3 . NIL)))

Note: your original recursive show-dots generating a string is not a good idea. Why? Because it recursively conses strings and potentially generates huge amount of garbage...

CL-USER 14 > (trace show-dots)
(SHOW-DOTS)

CL-USER 15 > (show-dots '((1 2) (3 (4 (5 6) ))))
0 SHOW-DOTS > ...
  >> LST : ((1 2) (3 (4 (5 6))))
  1 SHOW-DOTS > ...
    >> LST : (1 2)
    2 SHOW-DOTS > ...
      >> LST : 1
    2 SHOW-DOTS < ...
      << VALUE-0 : "1"
    2 SHOW-DOTS > ...
      >> LST : (2)
      3 SHOW-DOTS > ...
        >> LST : 2
      3 SHOW-DOTS < ...
        << VALUE-0 : "2"
      3 SHOW-DOTS > ...
        >> LST : NIL
      3 SHOW-DOTS < ...
        << VALUE-0 : "NIL"
    2 SHOW-DOTS < ...
      << VALUE-0 : "(2 . NIL)"
  1 SHOW-DOTS < ...
    << VALUE-0 : "(1 . (2 . NIL))"
  1 SHOW-DOTS > ...
    >> LST : ((3 (4 (5 6))))
    2 SHOW-DOTS > ...
      >> LST : (3 (4 (5 6)))
      3 SHOW-DOTS > ...
        >> LST : 3
      3 SHOW-DOTS < ...
        << VALUE-0 : "3"
      3 SHOW-DOTS > ...
        >> LST : ((4 (5 6)))
        4 SHOW-DOTS > ...
          >> LST : (4 (5 6))
          5 SHOW-DOTS > ...
            >> LST : 4
          5 SHOW-DOTS < ...
            << VALUE-0 : "4"
          5 SHOW-DOTS > ...
            >> LST : ((5 6))
            6 SHOW-DOTS > ...
              >> LST : (5 6)
              7 SHOW-DOTS > ...
                >> LST : 5
              7 SHOW-DOTS < ...
                << VALUE-0 : "5"
              7 SHOW-DOTS > ...
                >> LST : (6)
                8 SHOW-DOTS > ...
                  >> LST : 6
                8 SHOW-DOTS < ...
                  << VALUE-0 : "6"
                8 SHOW-DOTS > ...
                  >> LST : NIL
                8 SHOW-DOTS < ...
                  << VALUE-0 : "NIL"
              7 SHOW-DOTS < ...
                << VALUE-0 : "(6 . NIL)"
            6 SHOW-DOTS < ...
              << VALUE-0 : "(5 . (6 . NIL))"
            6 SHOW-DOTS > ...
              >> LST : NIL
            6 SHOW-DOTS < ...
              << VALUE-0 : "NIL"
          5 SHOW-DOTS < ...
            << VALUE-0 : "((5 . (6 . NIL)) . NIL)"
        4 SHOW-DOTS < ...
          << VALUE-0 : "(4 . ((5 . (6 . NIL)) . NIL))"
        4 SHOW-DOTS > ...
          >> LST : NIL
        4 SHOW-DOTS < ...
          << VALUE-0 : "NIL"
      3 SHOW-DOTS < ...
        << VALUE-0 : "((4 . ((5 . (6 . NIL)) . NIL)) . NIL)"
    2 SHOW-DOTS < ...
      << VALUE-0 : "(3 . ((4 . ((5 . (6 . NIL)) . NIL)) . NIL))"
    2 SHOW-DOTS > ...
      >> LST : NIL
    2 SHOW-DOTS < ...
      << VALUE-0 : "NIL"
  1 SHOW-DOTS < ...
    << VALUE-0 : "((3 . ((4 . ((5 . (6 . NIL)) . NIL)) . NIL)) . NIL)"
0 SHOW-DOTS < ...
  << VALUE-0 : "((1 . (2 . NIL)) . ((3 . ((4 . ((5 . (6 . NIL)) . NIL)) . NIL)) . NIL))"
"((1 . (2 . NIL)) . ((3 . ((4 . ((5 . (6 . NIL)) . NIL)) . NIL)) . NIL))"

All those calls to FORMAT are allocating new strings...

Better:

CL-USER 16 > (with-output-to-string (*standard-output*)
               (princme '((1 2) (3 (4 (5 6) )))))
"((1 . (2 . NIL)) . ((3 . ((4 . ((5 . (6 . NIL)) . NIL)) . NIL)) . NIL))"

Generally think in terms of stream output, not string concatenation.

Milliken

Thank you, for this explanation this really, get me the point with format, stream output and concatenation – Ulotrichous

Answer 3

If returning a string is really part of the problem specification, then use CONCATENATE 'STRING. If not, don't even bother with it, and just stick with FORMAT T and print to the console.

Bespatter

The problem is only printing, but format t doesn't work, or I do not know how to do it properly – Ulotrichous