Printing a string in Common Lisp after formatting a concatenation function with recursion

Question

I am trying to learn Common Lisp by reading Paul Graham's Ansi Common Lisp and using the EEC325 course critical functions and check functions and lectures. I created Emacs with Slime and SBCL

The problem in exercise 8 of chapter 8 is:

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

> (showdots ' ( abc)) (A . (B . (C . NIL))) NIL 

I made the following function so that the result is a string, and it works well for cases, but does not print, which is the main goal 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 creates a line that does not print the line but works

 CS325-USER> (SHOW-DOTS '(ABC)) "(A . (B . (C . NIL)))" CS325-USER> (SHOW-DOTS '(A (BC))) "(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 is awaiting printing, so it actually fails, but it is obvious that problems arise when printing the result

  (run-tests show-dots) SHOW-DOTS: (SHOW-DOTS '(ABC)) failed: Should have printed "(A . (B . (C . NIL)))" but saw "" SHOW-DOTS: (SHOW-DOTS '(A (BC))) 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 that the only thing I have to do is print this line after creation, but it doesn’t work, and I don’t 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 these results

 CS325-USER> (SHOW-DOTS '(ABC)) ABCNIL(NIL . NIL)(NIL . NIL)(NIL . NIL) NIL CS325-USER> (SHOW-DOTS '(A (BC))) 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 the crazy first line and its print

 (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 correct

 CS325-USER> (SHOW-DOTS '(ABC)) ABCNIL(NIL . NIL)(NIL . NIL)(NIL . NIL) NIL CS325-USER> (SHOW-DOTS '(A (BC))) 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 a line there 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 incorrect

 CS325-USER> (SHOW-DOTS '(ABC)) ABCNIL(NIL . NIL)(NIL . NIL)(NIL . NIL) NIL CS325-USER> (SHOW-DOTS '(A (BC))) 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 is happening here, maybe this is something stupid, but I do not understand.

thank you for your time

Answer 1

The original function that creates the string is actually very close. The problem is that the function that generates the line should also not print the line if it is called recursively, since you do not want intermediate lines to be printed as well. A very simple change you can make is to make the main object of your show points a function of an internal helper function, which creates a string and then prints the result of the helper function in the main 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 '(abc)) (A . (B . (C . NIL))) NIL 

Another way you can do this is to use an optional argument to indicate whether to print or return a string, and by default it can be printed, but in recursive cases you should return it. In fact, since the format takes t and nil as output arguments with semantics, you can make it 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 '(abc)) (A . (B . (C . NIL))) NIL 

However, both of these implementations end up creating a bunch of intermediate lines and then concatenating them together. This is not an efficient use of space. It is possible that it is better to write to the stream when moving the object that is being printed. Perhaps the most straightforward way to do this is to handle the formatting of the parentheses and tag yourself. This would lead to a more or less similar solution (it returns nil because this was the first example you gave):

 (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 '(abc)) (A . (B . (C . NIL))) ;=> NIL 

Now the format function has the ability to call other functions when they are named in format strings using the tilde slash . This means that you can do something like this, which I think is pretty elegant (I defined a new package, just to illustrate that the tilde format can look for characters in other packages, if you do 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/" '(abc)) (A . (B . (C . NIL))) ;=> NIL 

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 feature. Arguments are evaluated first. (princ 1) gets a rating. It prints 1 and returns 1 . Then evaluated (princ 2) . It prints 2 and returns 2 . The FORMAT function is called with evaluated arguments: t , "(~a ~a)" , 1 and 2 . It prints (1 2) and returns NIL .

Now look at this:

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

Just reusing the 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 : the original recursive show-dots row generation is not a good idea. What for? Since it recursively supports strings and potentially generates a 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 FORMAT calls highlight newlines ...

it is 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))" 

In general, think in terms of stream output, not string concatenation.

Answer 3

If the return string is indeed part of the specification of the problem, use CONCATENATE 'STRING . If not, don’t worry and just stick to FORMAT T and type on the console.