sorta-OT: my first Lisp program!
|
| 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))))))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.