Finally, it's done. That program for
finding the next palindrome given a number. I had to jump through several hoops and get help from the www and IRC to get it done (thanks to the helpful guys at #lisp - the newbie bashing notwithstanding).
Lisp is supposed to be a functional language. To be honest, I myself don't clearly understand what that means; I'm trying to learn little by little. As of now, it seems to me to be a conglomorate of various concepts and language facilities, some of which are present in some languages, and almost no real language seems have all of them.
Anyway, because of that, I tried not to make the program entirely C-like, and tried to do it the 'functional' way. Practically to me, it involved using recursion where I would have used iteration in C, and using variables as if they were constants - trying not to modify anything. In functional programming (FP) circles, this is called treating symbols as immutable (I think), and is glorified as a Good Thing. I haven't adhered to it fully (one place that comes to mind is the changing the value of ndigits in increm-left-from-here function), but I feel this is good enough for a C/C++/Perl programmer who understands very little of FP. :)
Some descriptions that
might help understand the program are here. You can try out things with the
Lisp in a Box IDE for Windows (you'll need to install the
base installer and the
CLISP module). Some clarifications: I'm not an expert in Lisp and don't claim to be one, I've described things as I understand them. Also, when making analogies to C, I've tried to take the thing that comes closest to it, but don't take the analogies literally. Concepts in Lisp are quite different from those in C, these are here only to give you a rough idea about them.
() syntax:
The parenthesis syntax here is something that might be very new to you. But it's quite simple, and very consistent.
When you see (A B C) in Lisp, what it means is call the function A with arguments B and C (A can also be a
macro, which I've
explained under
incf). In C syntax, that might be A(B, C). One good thing about Lisp is, this notation is followed very consistently throughout the language. Even operations like addition are done with this syntax: 1+2 in C will be (+ 1 2) in Lisp. Whenever you see a list (x y z a b c), you can say it's a function call calling function x with arguments y, z, a, b, and c. The only exception to this are literal lists - you know, the lists you use to store data, like C arrays. When you want a list of number 1 to 5, you might try (1 2 3 4 5). But... Lisp sees such lists as function calls, and so tries to 'call' the function 1 with arguments 2, 3, 4, and 5. Surely not what we wanted. So, to tell Lisp that we want a literal list, and not a function call, we have to put a single quote ' before the list. So, '(1 2 3 4 5) will achieve what we wanted. This actually works by changing itself it (quote (1 2 3 4 5)) where quote is a
macro. But you don't need to understand that to use the single quote. :)
defun:
This defines a function, like the sub keyword in Perl. For the C-ers among us,
(defun funName (arg1 arg2)
(body ...
....))
is very much like
void funName(type1 arg1, type2 arg2)
{ body ...
...}
Immediately, we can notice a few things: In Lisp, we don't specify the type of the arguments that the function takes - it can take whatever it wants. arg1 itself can be an entire list itself, or a number, or a string, or an object, or any type you can imagine (and Lisp can handle :) ). Also, there's no declaration of what the function is going to return - this too can be anything.
incf:
This is a simple macro that increments whatever you give to it as argument. If you're asking 'hello, what is a macro?', congratulations for the careful reading.
A macro is a thing that modifies the code at the place where you put it. They are somewhat like the preprocessor macros in C - and before the Lisp fans start grumbling, I'll add - but they're supposed to be much much more powerful. There's an entire book that is almost fully dedicated to doing magic with Lisp macros:
On Lisp.
In case you didn't get any clear idea about what macros are from the previous paragraph (yes, I guessed it), I'll explain with this example itself. In my code, in one place, I had
(incf i)
While debugging the code, I saw how the incf was expanded: the macro just replaced itself with
(setq i (+ i 1))
I myself wrote a macro in this code using the
defmacro command.
defmacro:
I described what a
macro is above. In Lisp, the syntax for macros is very much like the one for functions, with defun replaced by the keyword defmacro. For example, I have defined a macro in this code as:
(defmacro get-mid-index (list)
`(ceiling (1- (/ (length ,list) 2))))
A macro too gets arguments like a function (the argument is 'list' here). What follows after the argument is the
expansion of the macro, which means the macro is replaced with this thing wherever we call the macro.
There are some curious things to note here. First off, the expansion of the macro is not in an ordinary
(some code here ...
...)
format here. There is a ` and a , in that code, which makes it special. In
() syntax, we said that '() makes a literal list - that is, a list that is not evaluated, but is treated as data. The ` (that is the backtick - the thing which is to the left of 1 in the keyboard) is similar to ' but with a difference: while
nothing within the '() is evaluated, in a `() you can ask Lisp to evaluate certain things alone by putting a comma (,) before it. For example, in this expansion, the 'list' has a comma before it, so it will be evaluated. Since here 'list' is the argument we pass to the macro, it gets evaluated to the actual list which we pass. For example,
(get-mid-index digits-of-n)
becomes
(ceiling (1- (/ (length digits-of-n) 2)))
That's nifty, right? :)
nth:
nth is a function that returns the n'th element of a list. For example, (nth 2 '(a b c d e)) will return c. Here, it's important to note that Lisp lists are 0-based - the counting starts from 0. So a is the 0th element, b is the 1st, etc.
cond:
cond is a 'special form' (which is something like a function or a macro, but they say it's not either of those. I'm yet to understand special forms) which is somewhat like the if() construct of C. Lisp too has an (if ...) syntax, but it is limited to single statements. You can say (if (condition) (do-this) (else-do-that)), but (if (condition) ((do-this) (and-this)) (else-do-that)) is not allowed. In C syntax, it's as if
if(condition)
do-this;
else
do-that;
is allowed, but
if(condition) {
do-this;
and-do-this;
}
else
do-that;
is not allowed. In most practical cases, I find that I need to put multiple statements in the if's body, so I rarely use if in Lisp.
The cond function is similar to if, but much more flexible. It's syntax is,
(cond ((condition1) (do-this) (and-this) (also-this) (and-much-more) ...)
((condition2) (do-that) (and-that) (also-that) (and-much-more) ...)
...
(t (do-something) (do-something-else) (and-much-more) ...))
In this syntax, cond is followed by many lists. Each list contains one condition and a set of statements. Lisp will look through each of those conditions, and when any of the conditions succeeds (that is, returns true), it will execute the set of statements that are with that conditions. One weird thing about cond is that it requires that at least one of the conditions be true. If not, Lisp will go mad and bite you (or so they say). So, just for safety, it is good practice to put a (t ..) as the last condition, which stands for 'true', so it is a condition that will always be true. If any of the conditions succeeds, Lisp will execute its statements and exit the cond. If none of them succeed, the statements that are with the (t ...) will run.
If you want, you can think of the above cond as equivalent to:
if(condition1) {
do-this;
and-this;
also-this;
and-much-more; ...
}
else if(condition2) {
do-that;
and-that;
also-that;
and-much-more; ...
}
...
else {
do-something;
do-something-else;
and-much-more; ...
}
Note that the final (t ...) in Lisp is like the final else clause of C.
setq:
setq is like the = assignment of C. i = 1; in C would be (setq i 1) in Lisp. Only today (two days after I finished this code), I read
here that it is better to use setf for this purpose in Lisp, but so far everyone has told me to use setq, so I'm not sure which one is really better. The author of this FAQ that I linked to seems to know things, so I'm gonna trust him and use setf hereafter. It's really a trivial change, here it would be (setf i 1) instead of (setq i 1).
car and
cdr:
These strange names stand for simple concepts - they give you the first element of the list and the rest of the elements of the list, respectively. (car '(1 2 3)) would be 1. (cdr '(1 2 3)) would be (2 3). As you can see, car returns a single value (which the Lispers call an atom), but cdr returns a list.
format:
The format command is the printf of Lisp. It has many fancy options - it can even iterate through a list and print the elements one by one. Peter Seibel gives a very good explanation of the format function
here. One simple example is:
(format t "~D~%" n)
is similar to
printf("%d\n", n);
The 't' argument to format tells it to print the output to the screen (and not to a file or something like that).
With this intro, and some help from the Net, I think you'd be able to get a grasp of this program and learn a lot of Lisp in the meantime. Learning Lisp is said to be an
enlightening experience, so I hereby invite you to the path to
Nirvana, with this piece of code (many thanks to this
online syntax highlighter for producing this HTML):
(defun inc-nth (n list)
(incf (nth n list))
list)
(defun get-mid-elem (list)
(nth (get-mid-index list) list))
(defun mid-inc (list)
(inc-nth (get-mid-index list) list)
list)
(defun get-digits (n)
(cond ((and (< n 10) (>= n 0))
(list n))
((< n 0)
(get-digits (- n)))
(t
(append (get-digits (floor (/ n 10))) (list (mod n 10))))))
(defun num-from-digits (digits)
(cond ((= 1 (length digits))
(car digits))
(t
(+ (car (last digits)) (* 10 (num-from-digits (butlast digits)))))))
(defmacro get-mid-index (list)
`(ceiling (1- (/ (length ,list) 2))))
(defun get-mirrored-num (ndigits)
(num-from-digits
(let ((firsthalf (butlast ndigits (floor (/ (length ndigits) 2)))))
(append firsthalf
(if (evenp (length ndigits))
(reverse firsthalf)
(cdr (reverse firsthalf)))))))
(defun increm-left-from-here (index ndigits)
(cond ((= (nth index ndigits) 9)
(progn
(setf (nth index ndigits) 0)
(if (zerop index)
(setq ndigits (cons 1 ndigits))
(setq ndigits (increm-left-from-here (1- index) ndigits)))))
(t
(inc-nth index ndigits))))
(defun get-next-palin (n)
(let ((ndigits (get-digits n)))
(cond ((> (get-mirrored-num ndigits) n)
(get-mirrored-num ndigits))
(t (get-mirrored-num (increm-left-from-here (get-mid-index ndigits) ndigits))))))
(let ((num-cases (parse-integer (read-line))))
(format t "~{~D~%~}"
(loop
for i from 1 to num-cases
collect (get-next-palin (parse-integer (read-line))))))
for some time now. It’s a great book, the kind of book that makes you realize what programming really is about.
