sorta-OT: my first Lisp program!

Forum: LinuxTotal Replies: 8
Author Content
gus3

Feb 06, 2010
5:12 PM EDT
I can't find the thread, in which someone (dinotrac?) posted a link to Practical Common Lisp. I would like to thank publicly whoever it was for that; it finally got me to write my first, from-scratch Lisp program:

(defun collatz(x)
  (cond
    ; 1 terminates
    ((eq x 1) 0)
    ; Odd recurses to collatz(3x+1)
    ((eq (mod x 2) 1) (+ 1 (collatz (+ (* 3 x) 1))))
    ; Otherwise, even recurses to collatz(x/2)
    (t (+ 1 (collatz (/ x 2))))))

(dotimes (i 1000000) (cond ((eq i 0) 0) (t (format t "~d ~d~%" i (collatz i)))))


The parsimony of the "collatz" defun could be matched only by abusing C's ternary operator. Yet here, it makes perfect sense.

It also gave me a good, non-trivial reason to try out that OS-within-an-editor...
Bob_Robertson

Feb 06, 2010
6:27 PM EDT
If you forget one of the parentheses, does it crash into Mars?

Oh, sorry, that was Carl Bussjaeger's _Net Assets_.
Bob_Robertson

Feb 06, 2010
6:30 PM EDT
Just as an aside, I used that particular function back in 1982 to test RadioShack interpreted BASIC, BASIC on the PC, compiled BASIC using QBasic, and as my first C program, too.

Glad to see it still being used to "try things out". Congrats, Gus.

(A friend who got a job at Apple ran it in C on their Cray, for kicks, and it came back with a simple 0 as the time. It ran immeasurably fast!)
gus3

Feb 06, 2010
7:15 PM EDT
Single-threaded, register-based C runs in 1.46 seconds. Hand-coding the collatz() in assembly trims .2s off the C.

The Lisp runs in 86 seconds. Optimizing the (cond) form, so the most likely condition appears first, didn't make a whit of difference.
jezuch

Feb 07, 2010
8:09 AM EDT
Quoting:abusing C's ternary operator. Yet here, it makes perfect sense.


In functional languages it is *the* way to do conditionals. And I find it hard to work with imperative ones too without it :)
gus3

Feb 07, 2010
12:50 PM EDT
Quoting:int collatz(int x) { return ((x % 2) == 0) ? collatz(x / 2) + 1 : (x - 1) ? collatz(x * 3 + 1) + 1 : 0;
Uh, no.

Just... no.

Besides, using an iterative approach makes a lot more sense, when the compiler can optimize the automatic variables into the register file. The stack approach pollutes cache beyond anything reasonable.

Can you imagine the above approach, running on a 64-bit SPARC? Since it isn't a leaf procedure, every function call allocates 128 bytes per register window spilled, to store one lousy value. Bye, bye performance, hello memory thrasing!
Bob_Robertson

Feb 07, 2010
2:20 PM EDT
> Besides, using an iterative approach makes a lot more sense, when the compiler can optimize the automatic variables into the register file. The stack approach pollutes cache beyond anything reasonable.

By Cromm, this is why I'm no programmer. I think that I might have identified that paragraph as "English", and the individual words are easy enough to understand, but the combination is just plain outside of my comprehension.

Dr. Who script, maybe?
azerthoth

Feb 07, 2010
11:35 PM EDT
Star Trek $TECH_BABBLE section of the script I think Bob.
Sander_Marechal

Feb 08, 2010
4:21 AM EDT
Quoting:Besides, using an iterative approach makes a lot more sense, when the compiler can optimize the automatic variables into the register file. The stack approach pollutes cache beyond anything reasonable.


Just don't use C. Use a language that supports closures and recurse ad infinitum!

You cannot post until you login.