I saw something on SlashDot that raised the question: should all school children learn to code?
Yes.
For the same reason all school children should spend some time learning to sing, learning to do long division, learning to paint, learning some physics, learning some literature, learning to use a wrench and screwdriver, learning some history, learning some chemistry, etc, etc, etc. I believe that children who get a reasonably well-rounded, reasonable quality education grow up to be happier than those who don't, all else being equal. I don't have thousands of pages of peer-reviewed scientific research to support my belief, but I still believe it.
This does not mean that we should try to teach all children to be *good* programmers, any more than we should try to teach all children to be professional-level singers. We just need to introduce a wide-range of subjects so that they have a basic understanding of what the subject is about. After that, let their natural talents and interest drive where they go in-depth.
I never knew that software was my calling until I had my first opportunity to try coding in ... was it 1975? This introduction was *not* taught in school. It was a group called "explorer scouts", which may or may not have been associated with Boy Scouts of America, I don't remember. All I can tell you is that there were no uniforms, no camping, none of the trappings of Boy Scouts. The only activity I can remember was the programming. It was Fortran on a time-sharing system with a teletype. The fire it ignited in my brain overwhelms any other memories of the Explorer Scouts. THIS is what I wanted to do; my path in life was obvious.
HOW TO TEACH IT?
So, how should programming be taught? I don't know. I know there has been a lot of research and development in the area of programming systems for young people. Drag-and-drop icons representing programming constructs. I've glanced at them, and even used one briefly (it was a google doodle). It's OK, I guess. I think an important goal is to give a child early success and a feeling of accomplishment. I don't think those systems actually teach *programming*, but I think they probably do teach some fundamental concepts that are needed for programming.
My concern is that those systems don't really give a flavor of what programing is like. If you sing in music class, you get a sense of what singing is. If you play touch football, you get a sense of what that is. I actually consider myself fortunate that I wasn't introduced to programming that way. I suspect I would have thought that it was kind of neat, but I'm not sure it would have lit the fire. Part of what inspired me with my exposure was just the limitless possibilities. I'm not sure you get that with drag-and-drop programming.
The problem with most languages is the sheer amount of infrastructure you need to master before you can do things. To write a simple Java program, you need to define a namespace and a class. To print something, you need to enter System.out.println("something");. To read a line from the user will require several lines of junk that would require hours of explanation if you want the person to understand what the lines mean. Granted, you could just boilerplate it and tell the student to ignore all that stuff till later, but I think that reduces engagement. As does the edit/compile/run cycle. I don't think Java is a good first language, at least not for young children (and maybe nobody).
I have taught a few people to program. Want to know what worked for me?
"NO! DON'T SAY IT! PLEASE FOR THE LOVE OF ALL THAT IS DECENT, NO!"
Basic.
"GAAAAAAAAAAAAAAH %@!&*$!!!"
BASIC???
Yep. And I mean BASIC Basic. Line numbers. One or two character variable names. No "else".
10 print "hello"
20 goto 10
run
I find that humor is a good teaching tool. If your first program is an infinite print loop, it's kind of funny. Not very funny, but a little. Also, you definitely need a REPL (Read-Eval-Print Loop), which Basic is. No edit/compile/run cycle please.
It takes me an afternoon to teach somebody to program. We don't get sophisticated, but by the end of the afternoon we do end up writing a simple "text adventure" style game.
You are facing two doors. Do you want the right one or the left one?
? right
A lion has just eaten you!!!
Try again?
? yes
You are facing two doors. Do you want the right one or the left one?
? left
You found a gold coin!
Do you want to keep going? Or turn around? (answer "going" or "turn")
? turn
You are facing two doors. Do you want the right one or the left one?
etc. See? More humor. How many ways can you kill the player? :-)
I feel that the Basic language didn't get in the way of seeing the simple algorithm. Any other language would have obscured the simple beauty of what we were doing.
[Update] Now mind you, this is a one-day exercise! For somebody with more interest, I would have a second lesson with subroutines and gross Basic-style input parameters (globals, actually), and for the third lesson, we would switch to a modern language. Maybe Python? Maybe Java? Maybe Lisp? It would depend on who it is and what they might do with it.
Anyway, I did this 1-day lesson with my daughter (she was ... I don't remember ... maybe 10?) and she did well. Afterwards, she did ask me some questions and got a little help. Later that year she gave me a birthday present. It was a CD ROM with her updated adventure program. It has maybe a dozen "rooms" and lots of jokes and little surprises in it. She was VERY proud of herself. (And me of her; I still have the disk.)
But she pretty much lost interest. I am confident it was *not* because of the primitive language. It was just because it didn't light a fire in her. Which is fine.
Anyway, I really think an afternoon of Basic is a good way to introduce programming to a newbie of any age. I *know* it works.
Showing posts with label non-C coding. Show all posts
Showing posts with label non-C coding. Show all posts
Sunday, June 16, 2019
Tuesday, September 23, 2014
Tail Call Recursion in Clojure
In this article, I explain tail call recursion, show an example in both Clojure and common lisp, opine that Clojure's approach to tail call recursion optimization is better than lisp's, and finally look at Clojure's "lazy-seq" which seems to mysteriously provide the benefits of tail call recursion optimization for algorithms which are *not* tail call recursive.
Note: in this article, I refer to "tail call recursion", but I am actually dealing with a subset of that domain: tail *self* call (a.k.a. "direct") recursion. The theories presented also apply to the general case, including mutual (a.k.a. "indirect") recursion. However, optimization of tail *mutual* call recursion is much more rare in compilers than optimization of tail *self* call recursion. So I'm only considering self call.
What Is Tail Call Recursion?
Tail call recursion is a special case of recursion. With recursion, a function calls itself. *Tail* call recursion is where the function calls itself, and then immediately returns, either returning nothing, or returning the value of the recursive call. I.e. it doesn't call itself, and then do something with the results recursive call's value before returning. The reason tail call recursion is an interesting special case is that it can be optimized in a way that doesn't require a stack frame for each recursive invocation (i.e. it converts it into a simple loop). This makes it faster and conserves stack space.
Take the most-obvious way to program factorial recursively in clojure:
(defn fact1 [x]
(if (<= x 1)
1N
(* x (fact1 (dec x)))))
(fact1 5) ;= 120N
(fact1 9000) ;= StackOverflowError
(if (<= x 1)
1N
(* x (fact1 (dec x)))))
(fact1 5) ;= 120N
(fact1 9000) ;= StackOverflowError
This is not tail call recursive. If you call (fact 5), that initial invocation needs to wait for the recursive invocation to return the value of 4! so that it can multiply it by 5 and return the result. It needs to maintain the state of x across the recursive invocation, and it uses the stack for that. Clojure's stack seems awfully small to me; less than 9000 levels deep.
It's easy to modify fact1 to be tail recursive. It requires a modified version in which you pass a "result so far" as an additional input parameter:
(defn fact2-tail [x result-so-far]
(if (<= x 1)
result-so-far
(fact2-tail (dec x) (* x result-so-far))))
(fact2-tail 5 1N) ;= 120N
(fact2-tail 9000 1N) ;= StackOverflowError
(if (<= x 1)
result-so-far
(fact2-tail (dec x) (* x result-so-far))))
(fact2-tail 5 1N) ;= 120N
(fact2-tail 9000 1N) ;= StackOverflowError
(If you don't like having to pass the "1N", you can simply define a wrapper function.) This is tail call recursive because all the work, including the multiplication, is done before the recursive call. So theoretically no state needs to be stacked up as the recursion goes deeper. But as you can see by the stack overflow, Clojure doesn't realize this.
Be aware that some lisps will do automatic tail call optimization (or at least tail self-call optimization). I tried the equiv thing with clisp and it worked fine with big values:
Be aware that some lisps will do automatic tail call optimization (or at least tail self-call optimization). I tried the equiv thing with clisp and it worked fine with big values:
(compile
(defun fact2-tail-lisp (x result-so-far)
(if (<= x 1)
result-so-far
(fact2-tail-lisp (1- x) (* x result-so-far)))))
(fact2-tail-lisp 59999 1) ;= 260,630-digit number starting with 2606
(defun fact2-tail-lisp (x result-so-far)
(if (<= x 1)
result-so-far
(fact2-tail-lisp (1- x) (* x result-so-far)))))
(fact2-tail-lisp 59999 1) ;= 260,630-digit number starting with 2606
So what's a Clojure programmer to do? Use the loop/recur construct. Let's convert fact1, which is NOT tail call recursive, to loop/recur:
(defn fact1-loop [x]
(loop [i x]
(if (<= i 1)
1N
(* i (recur (dec i))))))
CompilerException java.lang.UnsupportedOperationException: Can only recur from tail position
(loop [i x]
(if (<= i 1)
1N
(* i (recur (dec i))))))
CompilerException java.lang.UnsupportedOperationException: Can only recur from tail position
Interesting. Clojure is NOT smart enough to recognize tail call recursion in fact2-tail, but it is smart enough to recognize NON-tail call recursion in fact1_loop. So the Clojure programmer must both recode the algorithm to be tail call recursive and code it to use loop/recur:
(defn fact2-loop [x]
(loop [i x, result-so-far 1N]
(if (<= i 1)
result-so-far
(recur (dec i) (* i result-so-far)))))
(fact2-loop 5) ;= 120N
(fact2-loop 59999) ;= 260,630-digit number starting with 2606
(loop [i x, result-so-far 1N]
(if (<= i 1)
result-so-far
(recur (dec i) (* i result-so-far)))))
(fact2-loop 5) ;= 120N
(fact2-loop 59999) ;= 260,630-digit number starting with 2606
There! One advantage to using loop/recur is you don't need a separate function which takes the extra result-so-far parameter. It's kind of built in to the loop construct.
Which Is Better?
So, which is better: Clisp, which automatically did the optimization, or Clojure, where the programmer basically has to *tell* the compiler to optimize it with loop/recur?
I have to side with Clojure, and I'll tell you why. I started my experimentations knowing that lisp did the optimization automatically. I coded it up, and it overflowed the stack. Huh? I had to do a bunch of googling to discover this page which mentions in footnote 1 that you have to compile the code to get it to do the optimization. Had I not tried it with a large number, or if I had mis-coded the algorithm to not really be tail call recursive, then I would have put in some effort to achieve an intended benefit, would not have received that benefit, and I might not have known it.
Most of the time, you need to carefully code your algorithm to be tail call recursive. I prefer Clojure's approach where you tell the compiler that you intend it to perform the optimization, and it gives you an error if it can't, as opposed to lisp which silently leaves it un-optimized if you make a mistake. It also gives a hint to a future maintainer that your potentially awkward algorithm is coded that way for a reason (admit it: fact2-tail and fact2-loop are more awkward algorithms than fact1).
What About lazy-seq?
Now I'm experimenting with lazy-seq, which can also be used to avoid stack consumption. It's a different animal -- the factorial function only returns a single value, whereas lazy-seq is intended to assemble a list (or more-accurately, a lazy sequence).
Let's start with re-writing fact1 to return a list of all factorials, from 1 to the requested value:
This function is recursive but doesn't use loop/recur. No wonder it blew up the stack. To convert this to loop/recur requires a change in the output. The final return value has to be the entire list, so the "cons"ing needs to be done on-the-fly each time through the loop. Thus, larger factorial values are "cons"ed onto a list-so-far of smaller factorial values, resulting in a reversed list:
Now I'm experimenting with lazy-seq, which can also be used to avoid stack consumption. It's a different animal -- the factorial function only returns a single value, whereas lazy-seq is intended to assemble a list (or more-accurately, a lazy sequence).
Let's start with re-writing fact1 to return a list of all factorials, from 1 to the requested value:
(defn fact3 [x i result-so-far]
(if (> i x)
'()
(cons
(* i result-so-far)
(fact3 x (inc i) (* i result-so-far)))))
(fact3 5 1N 1N) ;= (1N 2N 6N 120N)
(last (fact3 5 1N 1N)) ;= 120N
(last (fact3 9000 1N 1N)) ;= StackOverflowError
This function is recursive but doesn't use loop/recur. No wonder it blew up the stack. To convert this to loop/recur requires a change in the output. The final return value has to be the entire list, so the "cons"ing needs to be done on-the-fly each time through the loop. Thus, larger factorial values are "cons"ed onto a list-so-far of smaller factorial values, resulting in a reversed list:
(defn fact3-loop [x]
(loop [i 2N, result-so-far '(1N)]
(if (> i x)
result-so-far
(recur (inc i) (cons (* i (first result-so-far)) result-so-far)))))
(fact3-loop 5) ;= (120N 24N 6N 2N 1N)
(first (fact3-loop 5) ;= 120N
(first (fact3-loop 9000)) ;= 31,682-digit number starting with 8099
(first (fact3-loop 59999)) ;= OutOfMemoryError Java heap space
We solved the stack problem, but ran out of heap assembling the massive list (note that most of the elements of the list hold VERY large numbers, which consumes significant space for each list element).
lazy-seq to the rescue! Here's it is in action:
lazy-seq to the rescue! Here's it is in action:
(defn fact3-lazy [x i result-so-far]
(if (> i x)
'()
(cons
(* i result-so-far)
(lazy-seq (fact3-lazy x (inc i) (* i result-so-far))))))
(fact3-lazy 5 1N 1N) ;= (1N 2N 6N 24N 120N)
(last (fact3-lazy 5 1N 1N) ;= 120N
(last (fact3-lazy 9000 1N 1N) ;= 31,682-digit number starting with 8099
(last (fact3-lazy 59999 1N 1N) ;= 260,630-digit number starting with 2606
Look at the algorithm; it's almost identical to fact3. I.e. it is *not* tail call recursive! Each recursive call must return its list, which is then "cons"ed onto (* i result-so-far).
The lazy-seq function allows Clojure to conserve stack, even though the algorithm is not tail call recursive. It is also able to reclaim unneeded early list items (I'm only interested in the last one), so it conserves heap.
The lazy-seq function allows Clojure to conserve stack, even though the algorithm is not tail call recursive. It is also able to reclaim unneeded early list items (I'm only interested in the last one), so it conserves heap.
Did Clojure figure out a way to not have to maintain state across all 59999 invocations? Or is it just doing it with fact3-lazy in a more-space-efficient way than fact3? I'm guessing that it is maintaining state on the heap instead of the stack, but I'll be honest, I'm not exactly sure what's going on.
Friday, September 12, 2014
Clisp Performance
In my previous post, I did some speed measurements of Clojure. John commented with a test in common lisp, which performed MUCH better than Clojure.
So I did some more experimentation. Based on John's "fact2" results, his laptop appears to be about 3x faster than mine; not surprising since I have a 2nd gen Mac Air, and he probably has a real computer :-). But when I ran John's fact4 with clisp, I got:
(time (fact4 1000))
Real time: 0.003765 sec.
Run time: 0.003765 sec.
Whoa! That's over 200 times slower! I tried it again. And again. And again. Same results.
Then I tried (fact4 10000) and got "APPLY: too many arguments given to +". Oh yeah, now I remember that about clisp. :-)
Then I tried John's trick of timing a loop of them:
(time (dotimes (i 1000 (fact4 1000))))
Real time: 0.005146 sec.
Run time: 0.005117 sec.
Each run of (fact4 1000) now took 5 microseconds. I could imagine some overhead which needs to be amortized across multiple loopings, but that seems extreme.
Look at this:
(progn
(time (dotimes (i 1 (fact4 1000))))
(time (dotimes (i 10 (fact4 1000))))
(time (dotimes (i 100 (fact4 1000))))
(time (dotimes (i 1000 (fact4 1000)))))
Real time: 0.003783 sec.
Run time: 0.003783 sec.
Space: 8760 Bytes
Real time: 0.002432 sec.
Run time: 0.002394 sec.
Space: 8760 Bytes
Real time: 0.002528 sec.
Run time: 0.002528 sec.
Space: 8760 Bytes
Real time: 0.003901 sec.
Run time: 0.003832 sec.
Space: 8760 Bytes
They ALL took approximately the same time! Is clisp somehow not doing the loop? Maybe it sees that there are no side-effects, and just optimizes out all but one run? Maybe it implicitly does Clojure's "memoize" function of caching results? I kept going:
(progn
(time (dotimes (i 1000 (fact4 1000))))
(time (dotimes (i 10000 (fact4 1000))))
(time (dotimes (i 100000 (fact4 1000))))
(time (dotimes (i 1000000 (fact4 1000)))))
Real time: 0.004611 sec.
Run time: 0.00461 sec.
Space: 8760 Bytes
Real time: 0.017613 sec.
Run time: 0.01703 sec.
Space: 8760 Bytes
Real time: 0.126134 sec.
Run time: 0.125795 sec.
Space: 8760 Bytes
Real time: 1.231531 sec.
Run time: 1.230281 sec.
Space: 8760 Bytes
FINALLY! The times start increasing by factors of 10 after about 10,000 runs, settling down to about 1.2 microseconds per "(fact4 1000)". John - I suspect that you would see even better performance if you did more loops.
Anyway, I went back to the Clojure programs and did the same thing with timing multiple loopings.
(do
(time (dotimes [i 1] (fact1 1000)))
(time (dotimes [i 10] (fact1 1000)))
(time (dotimes [i 100] (fact1 1000)))
(time (dotimes [i 1000] (fact1 1000))))
"Elapsed time: 0.396 msecs"
"Elapsed time: 2.413 msecs"
"Elapsed time: 39.325 msecs"
"Elapsed time: 250.707 msecs"
The timings are basically consistent with a 10-fold increase in time with each 10-fold increase in loops. Yes, there is variability (presumably due to GC), but multiple runs have tended to prove the rule.
I get the same trends with fact2 and fact3. So my originally-posted timings were about right.
Conclusion? I've spent WAY too much time on this issue this morning and I'm going to be late to work. I think I'll just skip my morning exercise and only be a little late. :-)
(Update: my original C-language timings were wrong. I've corrected this post based on correct C timings. I no longer mistrust the "clisp" results, and have removed claims to that effect.)
Update 2: now that I trust the timing, I did a bit more number crunching. I'll assume that clisp can run a single call to (fact4 1000) in 1.2 microseconds. There is obviously some kind of overhead associated with the first call. (Maybe clisp is compiling "fact4" just in time? I.e. after "time" took the start timestamp?) Let's say that it takes 3500 microseconds for that overhead. So, with varying number of loops, I would expect to see the following:
3500 + 1.2 * 1 = 3501.2
3500 + 1.2 * 10 = 3512
3500 + 1.2 * 100 = 3620
So I did some more experimentation. Based on John's "fact2" results, his laptop appears to be about 3x faster than mine; not surprising since I have a 2nd gen Mac Air, and he probably has a real computer :-). But when I ran John's fact4 with clisp, I got:
(time (fact4 1000))
Real time: 0.003765 sec.
Run time: 0.003765 sec.
Whoa! That's over 200 times slower! I tried it again. And again. And again. Same results.
Then I tried (fact4 10000) and got "APPLY: too many arguments given to +". Oh yeah, now I remember that about clisp. :-)
Then I tried John's trick of timing a loop of them:
(time (dotimes (i 1000 (fact4 1000))))
Real time: 0.005146 sec.
Run time: 0.005117 sec.
Each run of (fact4 1000) now took 5 microseconds. I could imagine some overhead which needs to be amortized across multiple loopings, but that seems extreme.
Look at this:
(progn
(time (dotimes (i 1 (fact4 1000))))
(time (dotimes (i 10 (fact4 1000))))
(time (dotimes (i 100 (fact4 1000))))
(time (dotimes (i 1000 (fact4 1000)))))
Real time: 0.003783 sec.
Run time: 0.003783 sec.
Space: 8760 Bytes
Real time: 0.002432 sec.
Run time: 0.002394 sec.
Space: 8760 Bytes
Real time: 0.002528 sec.
Run time: 0.002528 sec.
Space: 8760 Bytes
Real time: 0.003901 sec.
Run time: 0.003832 sec.
Space: 8760 Bytes
They ALL took approximately the same time! Is clisp somehow not doing the loop? Maybe it sees that there are no side-effects, and just optimizes out all but one run? Maybe it implicitly does Clojure's "memoize" function of caching results? I kept going:
(progn
(time (dotimes (i 1000 (fact4 1000))))
(time (dotimes (i 10000 (fact4 1000))))
(time (dotimes (i 100000 (fact4 1000))))
(time (dotimes (i 1000000 (fact4 1000)))))
Real time: 0.004611 sec.
Run time: 0.00461 sec.
Space: 8760 Bytes
Real time: 0.017613 sec.
Run time: 0.01703 sec.
Space: 8760 Bytes
Real time: 0.126134 sec.
Run time: 0.125795 sec.
Space: 8760 Bytes
Real time: 1.231531 sec.
Run time: 1.230281 sec.
Space: 8760 Bytes
FINALLY! The times start increasing by factors of 10 after about 10,000 runs, settling down to about 1.2 microseconds per "(fact4 1000)". John - I suspect that you would see even better performance if you did more loops.
Anyway, I went back to the Clojure programs and did the same thing with timing multiple loopings.
(do
(time (dotimes [i 1] (fact1 1000)))
(time (dotimes [i 10] (fact1 1000)))
(time (dotimes [i 100] (fact1 1000)))
(time (dotimes [i 1000] (fact1 1000))))
"Elapsed time: 0.396 msecs"
"Elapsed time: 2.413 msecs"
"Elapsed time: 39.325 msecs"
"Elapsed time: 250.707 msecs"
The timings are basically consistent with a 10-fold increase in time with each 10-fold increase in loops. Yes, there is variability (presumably due to GC), but multiple runs have tended to prove the rule.
I get the same trends with fact2 and fact3. So my originally-posted timings were about right.
Conclusion? I've spent WAY too much time on this issue this morning and I'm going to be late to work. I think I'll just skip my morning exercise and only be a little late. :-)
(Update: my original C-language timings were wrong. I've corrected this post based on correct C timings. I no longer mistrust the "clisp" results, and have removed claims to that effect.)
Update 2: now that I trust the timing, I did a bit more number crunching. I'll assume that clisp can run a single call to (fact4 1000) in 1.2 microseconds. There is obviously some kind of overhead associated with the first call. (Maybe clisp is compiling "fact4" just in time? I.e. after "time" took the start timestamp?) Let's say that it takes 3500 microseconds for that overhead. So, with varying number of loops, I would expect to see the following:
3500 + 1.2 * 1 = 3501.2
3500 + 1.2 * 10 = 3512
3500 + 1.2 * 100 = 3620
3500 + 1.2 * 1000 = 4700
3500 + 1.2 * 10000 = 15500
3500 + 1.2 * 100000 = 123500
3500 + 1.2 * 1000000 = 1203500
Given the wide variability of individual timings, this matches reasonably well the results above. I don't think clisp is doing anything too fishy.
Given the wide variability of individual timings, this matches reasonably well the results above. I don't think clisp is doing anything too fishy.
Thursday, September 11, 2014
Clojure performance
There is a cute site www.4clojure.com which poses coding challenges to Clojure programmers. I don't have lot of time each day, so I'm only up to #42, but I'm having fun. The actual problems have been trivial so far, targeted to giving a beginner practice with Clojure features. One nice thing about it is that you can "follow" somebody else to see what their solutions are (but you can only see them *after* you've solved it yourself). I've found a pretty experienced Clojure programmer to follow, so it's been very educational to compare my sometimes-brute force solutions with his more elegant solutions.
For example, problem #42 is to write a factorial function. For the purposes of this post, I'm changing the factorial algorithm to do addition rather than multiplication. This is because I wanted to test it with large numbers without arithmetic overflow to get timing information.
As a long-time C programmer, I would just write:
I timed that (on my 2nd gen Mac Air) for n=1,000 and it took 6 nanoseconds.
A beginning Clojure functional programmer might do it recursively like this:
For n=1,000, this takes about 330 microseconds - about 55,000 times longer than C. :-(
The more-experienced guy solved it this way:
This is very elegant and uses some of Clojure's interesting features. As soon as I saw it, I thought, "wow, that probably took him 10 seconds to write." It executes in almost exactly the same time as the recursive version - about 330 micros.
Here is how I wrote it:
Note that this is arguably the most-complex of all the solutions. Part of the reason I wanted to write it this way was that I wanted to practice a method called "tail recursion". In this method, the algorithm is technically recursive (hence the "recur" function), but the compiler can trivially convert it into a simple loop. I.e. this method does not actually create 1000 stack frames. The reason for doing this is to make it more efficient.
My version takes about 200 microseconds, only 33,000 times longer than C. :-)
What happens if we go with n=10,000? Surprise! The purely-recursive version gets a stack overflow. (That seems like an awfully small stack to me...) The other versions each take about 10 times longer, as you would expected.
The moral of the story? Use Clojure when you want short development cycles, not high performance. And by that measure, the *real* winner is that more-experienced Clojure programmer who wrote "(apply + (range 1 (inc n)))". No "if" statements to get wrong, no partial-sum to keep track of, no stacks to overflow. By a HUGE margin, the fastest to get to a working program.
(Update: my first posting used mistakenly used C timing without optimizing. I've corrected this article with timings using "-O3" optimization. The optimizer gave a 600x speed improvement, from 4 microseconds to 6 nanoseconds. Wow!)
For example, problem #42 is to write a factorial function. For the purposes of this post, I'm changing the factorial algorithm to do addition rather than multiplication. This is because I wanted to test it with large numbers without arithmetic overflow to get timing information.
As a long-time C programmer, I would just write:
long long fact (long long n)
{
long long r = 1;
long long i;
for (i = 2; i <= n; i++)
r += i; /* not really factorial */
return r;
}
I timed that (on my 2nd gen Mac Air) for n=1,000 and it took 6 nanoseconds.
A beginning Clojure functional programmer might do it recursively like this:
(defn fact1 [n]
(if (= n 1)
1
(+ n (fact1 (dec n)))))
For n=1,000, this takes about 330 microseconds - about 55,000 times longer than C. :-(
The more-experienced guy solved it this way:
(defn fact2 [n]
(apply + (range 1 (inc n))))
This is very elegant and uses some of Clojure's interesting features. As soon as I saw it, I thought, "wow, that probably took him 10 seconds to write." It executes in almost exactly the same time as the recursive version - about 330 micros.
Here is how I wrote it:
(defn fact3 [n]
(loop [sum-so-far 1, i n]
(if (<= i 1)
sum-so-far
(recur (+ sum-so-far i) (dec i)))))
Note that this is arguably the most-complex of all the solutions. Part of the reason I wanted to write it this way was that I wanted to practice a method called "tail recursion". In this method, the algorithm is technically recursive (hence the "recur" function), but the compiler can trivially convert it into a simple loop. I.e. this method does not actually create 1000 stack frames. The reason for doing this is to make it more efficient.
My version takes about 200 microseconds, only 33,000 times longer than C. :-)
What happens if we go with n=10,000? Surprise! The purely-recursive version gets a stack overflow. (That seems like an awfully small stack to me...) The other versions each take about 10 times longer, as you would expected.
The moral of the story? Use Clojure when you want short development cycles, not high performance. And by that measure, the *real* winner is that more-experienced Clojure programmer who wrote "(apply + (range 1 (inc n)))". No "if" statements to get wrong, no partial-sum to keep track of, no stacks to overflow. By a HUGE margin, the fastest to get to a working program.
(Update: my first posting used mistakenly used C timing without optimizing. I've corrected this article with timings using "-O3" optimization. The optimizer gave a 600x speed improvement, from 4 microseconds to 6 nanoseconds. Wow!)
Tuesday, July 22, 2014
Adventure! ... in BASIC???
Over the weekend, I was feeling sorry for myself for not having as much time to program as I would like, so I sneaked a few hours (about 6) to write an adventure game. I thought a bit about what language to use. Part of me wanted to do it in one of the functional languages, but I knew I wouldn't have enough time to both learn the language sufficiently AND write enough to be recognizably adventurous.
And then a wave of nostalgia swept over me.
BASIC.
And none of this new-fangled BASIC with block-structured coding constructs. Basic BASIC. With 1 or 2 character variable names, and lots of GOTOs.
I gotta say, I haven't had this much fun programming in years. I actually chuckled at times, remembering the old days of:
3165 if w <= 9 then 3170
3167 print "Too many words! Talk more simply."
3168 v$ = "" : n$ = "" : return
3170 rem
OK, the pedantic among you will say that putting multiple statements on a line is not basic BASIC. Oh well, I make the rules, I can break them. But I did restrict myself to variable names of one letter, or one letter and one digit, with all variables gloriously global. Man, kids today don't know how good they have it.
>load "a.txt"
>run
You are in a brightly-lit room. Birds are singing, puppies and kitties are playing in the sunlight streaming in through cheerily open windows. There is a hole in the north wall that looks just big enough to crawl through.
You see:
a grey bag of scratchy cloth
? north
You are in a dimly-lit room. Shadowey figures seem to slither towards you. A low moan can faintly be heard. What little light penetrates the ominous darkness comes from the south.
You see:
a fabulous 100-carat diamond!
? take diamond
got it.
You are in dim room
? n
Can't go that way
You are in dim room
? s
You are in a brightly-lit room. Birds are singing, puppies and kitties are playing in the sunlight streaming in through cheerily open windows. There is a hole in the north wall that looks just big enough to crawl through.
You see:
a grey bag of scratchy cloth
? look at the grey bag
a grey bag of scratchy cloth
which contains:
an iron key, slightly rusted
You are in bright room
? take bag
NEXT without FOR in line 9075
>
Whoopsie! Looks like I need a bit more debugging. :-)
Or not. The exercise accomplished its purpose, which honestly was more to feel young again than hone my coding skills. I.e. I don't think I'll be putting this on my resume any time soon. ;-)
Update: I thought I might put it up on github, not because it is a useful or notable piece of work, but because I wanted to be the first person to put BASIC on github. No such luck. There is a ton of BASIC already on github. Oh well...
And then a wave of nostalgia swept over me.
BASIC.
And none of this new-fangled BASIC with block-structured coding constructs. Basic BASIC. With 1 or 2 character variable names, and lots of GOTOs.
I gotta say, I haven't had this much fun programming in years. I actually chuckled at times, remembering the old days of:
3165 if w <= 9 then 3170
3167 print "Too many words! Talk more simply."
3168 v$ = "" : n$ = "" : return
3170 rem
OK, the pedantic among you will say that putting multiple statements on a line is not basic BASIC. Oh well, I make the rules, I can break them. But I did restrict myself to variable names of one letter, or one letter and one digit, with all variables gloriously global. Man, kids today don't know how good they have it.
>load "a.txt"
>run
You are in a brightly-lit room. Birds are singing, puppies and kitties are playing in the sunlight streaming in through cheerily open windows. There is a hole in the north wall that looks just big enough to crawl through.
You see:
a grey bag of scratchy cloth
? north
You are in a dimly-lit room. Shadowey figures seem to slither towards you. A low moan can faintly be heard. What little light penetrates the ominous darkness comes from the south.
You see:
a fabulous 100-carat diamond!
? take diamond
got it.
You are in dim room
? n
Can't go that way
You are in dim room
? s
You are in a brightly-lit room. Birds are singing, puppies and kitties are playing in the sunlight streaming in through cheerily open windows. There is a hole in the north wall that looks just big enough to crawl through.
You see:
a grey bag of scratchy cloth
? look at the grey bag
a grey bag of scratchy cloth
which contains:
an iron key, slightly rusted
You are in bright room
? take bag
NEXT without FOR in line 9075
>
Whoopsie! Looks like I need a bit more debugging. :-)
Or not. The exercise accomplished its purpose, which honestly was more to feel young again than hone my coding skills. I.e. I don't think I'll be putting this on my resume any time soon. ;-)
Update: I thought I might put it up on github, not because it is a useful or notable piece of work, but because I wanted to be the first person to put BASIC on github. No such luck. There is a ton of BASIC already on github. Oh well...
Monday, April 28, 2014
Cute "sed" Trick: rotate file
I wanted a script that would invoke a process, passing in a port number from a circular pool of ports. When the process exits and restarts, I want the script to pass in the *next* port from the pool.
In the above "sed" command:
Thus, given that "port_file.txt" contains:
and "PORT" set to 12000.
PORT=`head -1 port_file.txt`
sed -i -e '1h;1d;$G' port_file.txt
In the above "sed" command:
- The "-i" causes the file "port_file.txt" to be edited in-place.
- The "1h" sed command yanks the first line into the "hold" space.
- The "1d" sed command deletes the first line (prevents it from being output).
- The "$G" command appends the hold space after the last line of the file.
Thus, given that "port_file.txt" contains:
12000
12001
12002
12003
the above two commands will leave the file with:
12001
12002
12003
12000
Friday, February 7, 2014
Configure a Cron Job with a Wiki
I have some periodic cron jobs that need extra configuration. For example, one of them generates a report on bug statistics on a code branch basis. So I need to tell it which code branches to process. I could just put the list of branch tags on the command line of the report generator, and just use "crontab -e" while logged in to modify it. However, I want anybody to be able to maintain the list, without having to know my password or the syntax for crontab.
It turns out that we installed Mediawiki locally for our own internal wiki. So I created a wiki page with a table listing the code branches that are active. Then I wrote a script which uses "curl" to fetch that wiki page and parse out the branches. This gives me a nice web-based GUI interface to the tool that everybody is already familiar with. Everybody here knows how to use Wikipedia, so anybody can go in and change the list of branches.
After doing some additional development, I wanted to be able to include additional configuration for the cron job which I didn't particularly want displayed on the wiki page. You can use <!--HTML-style comments--> with Mediawiki and it won't display it on the page. Unfortunately, it completely withholds the comment from the html of the page. I.e. you can't see it even if you display source of the page. You only see the comment when you edit the page.
So here's what I ended up with:
The "sed" commands use "-n" to suppress printing of lines to stdout. Adding a "p" suffix to the end of a sed command forces a print, if the command is successful. So, for example, the line:
OPTS=`echo "$ILINE" | sed -n 's/^.*--OPTS:\([^:]*\):.*$/\1/p'`
If the contents of $ILINE does not contain match the pattern (i.e. does not have an option string), the "s" command is not successful and therefore doesn't print, leaving OPTS empty.
One final interesting note: the use of "eval" to run the qa_report.sh script. Why couldn't you just use this?
./qa_report $OPTS "$TARGET_MILESTONE" 2>&1
Let's say that $TARGET_MILESTONE is "milestone" and the contents of $OPT is:
The "eval" form of the command works like this:
eval ./qa_report $OPTS \"$TARGET_MILESTONE\" 2>&1
First the shell looks at this command line and parses it with "eval" as the command and the rest as "eval"s parameters. It does the symbol substitution. Thus, the thing that gets passed to "eval" is:
./qa_report -a "b c" -d "e f" "milestone"
What does the eval command do with that? It passes it to the shell for parsing! In this pass, "./qa_report" is the command, and the rest are the parameters. Since the shell is parsing it from scratch, it will group "b c" as a single entity, letting the "-a" option pick it up as a single string.
It turns out that we installed Mediawiki locally for our own internal wiki. So I created a wiki page with a table listing the code branches that are active. Then I wrote a script which uses "curl" to fetch that wiki page and parse out the branches. This gives me a nice web-based GUI interface to the tool that everybody is already familiar with. Everybody here knows how to use Wikipedia, so anybody can go in and change the list of branches.
After doing some additional development, I wanted to be able to include additional configuration for the cron job which I didn't particularly want displayed on the wiki page. You can use <!--HTML-style comments--> with Mediawiki and it won't display it on the page. Unfortunately, it completely withholds the comment from the html of the page. I.e. you can't see it even if you display source of the page. You only see the comment when you edit the page.
So here's what I ended up with:
#!/bin/sh
# all.sh
# Generate QA report for all active releases. Runs via cron nightly.
date
# Read wiki page and select rows in the release table ("|" in col 1).
# Uses "action=edit" so that are included (for option processing).
curl 'http://localwiki/index.php?title=page_title&action=edit' | egrep "^\|" >all.list
# read the contents of all.list, line at a time. Each line is an entry in the table of active releases.
while read ILINE; do :
# Extract target milestone (link text of web-based report page).
TARGET_MILESTONE=`echo "$ILINE" | sed -n 's/^.*_report.html \(.*\)\].*$/\1/p'`
# Extract the (optional) set of command-line options.
OPTS=`echo "$ILINE" | sed -n 's/^.*--OPTS:\([^:]*\):.*$/\1/p'`
eval ./qa_report $OPTS \"$TARGET_MILESTONE\" 2>&1
done <all.list
The "sed" commands use "-n" to suppress printing of lines to stdout. Adding a "p" suffix to the end of a sed command forces a print, if the command is successful. So, for example, the line:
OPTS=`echo "$ILINE" | sed -n 's/^.*--OPTS:\([^:]*\):.*$/\1/p'`
If the contents of $ILINE does not contain match the pattern (i.e. does not have an option string), the "s" command is not successful and therefore doesn't print, leaving OPTS empty.
One final interesting note: the use of "eval" to run the qa_report.sh script. Why couldn't you just use this?
./qa_report $OPTS "$TARGET_MILESTONE" 2>&1
Let's say that $TARGET_MILESTONE is "milestone" and the contents of $OPT is:
-a "b c" -d "e f"
If you omit the "eval", you would expect the resulting command line to be:
./qa_report -a "b c" -d "e f" "milestone" 2>&1
I.e. the qa_report tool will see "b c" as the value for the "-a" option, and "e f" as the value for the "-d" option. But the shell doesn't work this way. The line:
./qa_report $OPTS \"$TARGET_MILESTONE\" 2>&1
will expand $OPTS, but it won't group "b c" as a single entity for -a. Without "eval", the "-a" option will only see the two-character value "b (with the quote mark). I found a good explanation for this; the short version is that the shell does quote processing before it does symbol expansion. So essentially, the thing you need to do is have the shell parse the command line twice.
eval ./qa_report $OPTS \"$TARGET_MILESTONE\" 2>&1
First the shell looks at this command line and parses it with "eval" as the command and the rest as "eval"s parameters. It does the symbol substitution. Thus, the thing that gets passed to "eval" is:
./qa_report -a "b c" -d "e f" "milestone"
What does the eval command do with that? It passes it to the shell for parsing! In this pass, "./qa_report" is the command, and the rest are the parameters. Since the shell is parsing it from scratch, it will group "b c" as a single entity, letting the "-a" option pick it up as a single string.
Subscribe to:
Posts (Atom)
