Hello,
I'm sorry for the bad subject, but I could not find anything better.
Some times ago I was talking with a friend of mine, and we compared newLisp vs other imperative languages (object pascal, generic basic, and java).
We tried to make small programs to get an input and produce same output, but using the best of each sector ("imperative" concepts and "functional" ones).
Well, I'm working in newLisp but I come from many years programming with imperative languages. So sometimes is difficult for me using advance functional algorithms since I tend to use "imperative" concepts to solve problems in newLisp.
(sorry for this long introduction!)
This is the "trivial" problem:
I have a list of strings, and I want to convert only some strings to upper-case. The strings are: first string, third string, 5th string, etc...
So... I have:
("string 1" "string 2" "string 3" "string 4" "string 5" "string 6")
I want to obtain:
("STRING 1" "string 2" "STRING 3" "string 4" "STRING 5" "string 6")
In an "imperative algorithm" I could use a loop and a "step". For example:
dim myList$(6)
myList$(1) = "string 1"
myList$(2) = "string 2"
myList$(3) = "string 3"
myList$(4) = "string 4"
myList$(5) = "string 5"
myList$(6) = "string 6"
for i=1 to 6 step 2
myList$(i) = uppercase(myList$(i))
next
How can I do in newLisp without using loops, but using "functional" concepts (e.g. using "map")?
How many possibilities/alternatives do I have to accomplish it?
(I wish to insert the results of this topic even in my blog, since I think this discussion could be interesting even for many other guys).
Thank you!
(MAIN)-> (setq L '("string 1" "string 2" "string 3" "string 4" "string 5" "string 6"))
("string 1" "string 2" "string 3" "string 4" "string 5" "string 6")
(MAIN)-> (map (fn(x) (setf (L x) (upper-case (L x)))) '(1 3 5))
("STRING 2" "STRING 4" "STRING 6")
(MAIN)-> L
("string 1" "STRING 2" "string 3" "STRING 4" "string 5" "STRING 6")
Here's an example from documentation which looks like a helpful hint to me:
--> '(1 7 3 9 5)
From alphabetical section on functions in User Manual
@newdep immediately uses newLisp 10 features! ;-)
I like that solution!
@unixtechie I found that hint, but I cannot grab final solution using it. I don't know if that one is a good way.
I think the "problem" is
I don't know if there is a function tomake something like this (meta-code):
In this way I could get two values per step. So I could obtain:
("S1" "s2" "S3" "s4" ... )
Maybe there is a better way than using MAP (but... how?)
Or better (more flexible):
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(map (fn (x y) (if (= (/ x 2) (div x 2) ) y (upper-case y) )) (sequence 1 (length f) ) f )
(define (odd? num)((bits num true) 0))
(define (even? num)(not ((bits num true) 0)))
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (odd? $idx) (setf (f $idx) (upper-case (f $idx)))))
(println f)
; ("a" "B" "c" "D" "e" "F" "g")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case (f $idx)))))
(println f)
; ("A" "b" "C" "d" "E" "f" "G")
(exit)
Q.E.D. ;)
-- xytroxon
P.S. And six months later, at a glance, I can tell what this code does!
In self-referential 'setf' statements you can also use the system variable '$it':
ps: congratulations for using new 'bits' with extra flag ;-)
Quote from: "Lutz"
ps: congratulations for using new 'bits' with extra flag ;-)
I think you mean:
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it)))
(define (odd? num)((bits num true) 0))
(define (even? num)(not ((bits num true) 0)))
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (odd? $idx) (setf (f $idx) (upper-case $it))))
(println f)
; ("a" "B" "c" "D" "e" "F" "g")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it))))
(println f)
; ("A" "b" "C" "d" "E" "f" "G")
(exit)
Yes, much better now!
-- xytroxon
How about:
; or
(apply append (map (fn (l) (list (upper-case (first l)) (last l))) (explode f 2 true)))
I suppose this is also 'functional' in that the initial list is unchanged...
Nice solution because without the need for 'odd?' and 'even?' functions!
But here another one using 'map' and also using the system variable '$idx', which also gets updated during 'map':
You guys get carried away, but it's interesting to see so many ways to arrive at usable solutions.
I had done basically what xytroxon did but created a new list. Easier for a casual programmer such as myself to understand at some later date.
(dolist (this-string myList) (if (even? $idx)
(push (upper-case this-string) newList -1)
(push this-string newList -1)
)
)
--> "STRING 5"
newList
--> "STRING 1" "string 2" "STRING 3" "string 4" "STRING 5"
myList
--> ("string 1" "string 2" "string 3" "string 4" "string 5")
After lunch, I simplified
; test bit position in number for 1 or 0
(define (bit? pos num) (bits num true) pos)
(define (odd? num) (bit? 0 num))
(define (even? num) (not (bit? 0 num)))
Bit operations on integers can be useful on packed data and working on data sent to and from hardware registers via dll, etc.
Other proposed bit functions to be developed:
(bit0 pos num) ; set bit position in number to 0 "clear bit"
(bit1 pos num) ; set bit position in number to 1 "set bit"
(bit~ pos num) ; toggle bit position in number 0 -> 1 , 1 -> 0
Any others?
And I propose adding at least
This code sprint was fun, I learned a few things and it helped to clean up some of my code too.
(Now I can make checkerboard colored html tables! Woo Hoo!)
-- xytroxon
I was delighted from these solutions!
I learnt so many things!
@cormullion you killed me with that solution! I'm still studying it to better understand your solution!
Thank you even for odd and even optimizations! I think in future newLisp versions they should be really included ;-)
I started this topic saying I wanted to prepare an article, but now... I think I will prepare more than one!!!
There's an interesting aspect of this thread that hasn't so far been mentioned: performance. Although I generally agree with DrDave's signature ("make programs efficient only if really needed"), I'm always fascinated by the interplay between simplicity, elegance, performance, and readability that newLISP allows us to explore.
Which of these algorithms are faster? Is the full-speed ahead iteration of
I put the different algorithms head to head on a 60000 word list. Some are an order of magnitude slower than another. It might matter some day... :)
Good point of view @cormullion.
I found another interesting solution for this problem just studying Erlang language.
In fact, I think sometimes we forget that newLisp is a functional language, and some items should be solved in a functional way.
If you start to use languages like Erlang, where some functional aspects are very strong (e.g. variables are immutable, recursive algorithms are a great resource to solve problems, etc...) you will see our problem in a different point-of-view.
Now I'm at work, but at home I want to write another possibility only using function call. Example (pseudo-code):
get_first_string:
is it odd?
YES->convert to uppercase and add it to final list.
NO -> add it to final list as is.
call MY_FUNC(remaining_strings, final_list)
I hope my concept is clear.
This is a clear example about functional programming:
@cormullion I add another important point to your list: code must be safe and error-free. So... in the previous code...
1) variables are immutable.
2) usage of real functional-programming aspects.
Quote from: "cormullion"
And you're just leaving us hanging??
Quote from: "cormullion"
Yes.
Try these changes to
;corrected 12/12/2008
(define (odd? num) (= (& num 1) 1))
(define (even? num) (= (& num 1) 0))
(dolist (x f) (if (odd? $idx) (setf (f $idx) (upper-case $it))))
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it))))
And then try putting them "inline":
(dolist (x f) (if (= (& $idx 1) 1) (setf (f $idx) (upper-case $it)))) ; odd
(dolist (x f) (if (= (& $idx 1) 0) (setf (f $idx) (upper-case $it)))) ; even
-- xytroxon
Quote from: "ale870"
I want to write another possibility only using function call. Example (pseudo-code):
get_first_string:
is it odd?
YES->convert to uppercase and add it to final list.
NO -> add it to final list as is.
call MY_FUNC(remaining_strings, final_list)
I hope my concept is clear.
I see you want to recursively call your function and have it walk the list until out of strings. But how does 'dolist' handle it? Does it make recursive calls to itself or just traverses the list? (Personally, I think recursion is over rated. It certainly has some very good places where it gives simple, readable code compared to a non-recursive solution. But I don't see that it is a major tool in my toolbox.)
Quote from: "xytroxon"
Quote from: "cormullion"
-- xytroxon
Rather than go through all that code, I made a similar comparison of the time it takes to evaluate the predicate form versus the inline form for determining if a number is odd. I get a ratio of about 53:30 (inline faster).
And while we're talking optimization now, in my version I built the second list on-the-fly by pushing each string to the end of a second list. Would it be faster to start off by copying the entire first list and then pushing only the changed string to its proper location (according to $idx) because it makes only half as many pushes?
Does pushing to an index location require traversing the list from the start? And if pushed to either the first or last position, would those always be "instantly" located?
I made some tests for recursive functions. But it seems some "instruments" are missing to "emulate" Erlang functioning.
So I think recursive way is better for newLisp.
@Curmullion can you give us the results you obtained about performance?
Quote from: "DrDave"
Yes, the first location is accessed instantly and access to the last location is optimized with no need to traverse the list. This is true not only for 'push' and 'pop' but also other indexed access with 0 or -1 and via the functions 'first' and 'last'.
Lists in newLISP are forward-single-linked lists, but a pointer to the last element is stored in the header/envelope of the list and updated whenever possible.
Correction, swap the 1 and 0 for odd and even like this. (Lunchtime programmer error. ;)
(define (odd? num) (= (& num 1) 1))
(define (even? num) (= (& num 1) 0))
Another "case" to consider is to use
(println "case 1 odd")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (case (& $idx 1)(1 (setf (f $idx) (upper-case $it)))))
(println f)
(println "case 0 even")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (case (& $idx 1)(0 (setf (f $idx) (upper-case $it)))))
(println f)
(exit)
Much faster!
-- xytroxon, now going to dinner. Without a computer...
One "functional" contribution to the discussion.
(cond ((= x y) z)
((= x z) y))))
(set 'alt-case-starting-with
(lambda(L first-case)
(if (empty? L) (list)
(cons (first-case (first L))
(alt-case-starting-with (rest L)
(other-one first-case
lower-case
upper-case))))))
(println (alt-case-starting-with '("str1" "str2" "str3" "str4") upper-case))
(exit)
Good exercise @Kazimir!
Your approach hightlight a potential "problem" in newLisp (maybe it could be completed with a specific function): newLisp does not apply "tail recursive" method. This is one of the biggest problems of imperative languages, and this is one of the reasons because recursive functions are not so much used.
I think, if newLisp could contain a function like
Now recursive algorithms are not used since they could cause serious problems to the stack area.
@Lutz, I think you need to evaluate this function implementation (tail-recursive). In fact I don't think you could implement at compile-level (but I'm still a newbie in functional programming so I do not know all the concepts in detail).
Well, I wasn't originally going to post this, but I'm off sick today ... if you forgive me mangling your code, guys, just to make it fit my approach, and don't for a moment think that this is rigourous or scrupulously fair...
(set 'source-list .... your list of strings goes here...
(define (method1 lst)
(map (fn (x) (setf (lst x) (upper-case (lst x))))
(sequence 0 (- (length lst) 1) 2))
lst)
(define (method2 lst)
(map (fn (x y) (if (= (/ x 2) (div x 2)) y (upper-case y)))
(sequence 0 (- (length lst) 1))
lst))
(define (odd? num) (= "1" (last (bits num))))
(define (odd? num) (= (& num 1) 1))
(define (method3 lst)
(map (fn (x) (if (odd? $idx) (upper-case x) x)) lst))
(define (method4 lst)
(dolist (x lst) (if (odd? $idx) (setf (lst $idx) (upper-case $it))))
lst)
(define (method5 lst)
(flat (replace '(+) (explode lst 2 true) (list (upper-case (first $it)) (last $it)) match)))
(define (method6 lst)
(apply append (map (fn (l) (list (upper-case (first l)) (last l))) (explode lst 2 true))))
(set 'other-one (lambda (x y z)
(cond ((= x y) z)
((= x z) y))))
(define (method7 lst (first-case upper-case))
(if (empty? lst) (list)
(cons (first-case (first lst))
(method7 (rest lst)
(other-one first-case
lower-case
upper-case)))))
(define (method8 lst)
(dolist (x lst) (case (& $idx 1) (0 (setf (lst $idx) (upper-case $it)))))
lst)
(define (method9 lst)
(dolist (this-string lst)
(if (odd? $idx)
(push (upper-case this-string) newList -1)
(push this-string newList -1)))
newList)
(push (list (time (method1 source-list)) "method1") results)
(push (list (time (method2 source-list)) "method2") results)
(push (list (time (method3 source-list)) "method3") results)
(push (list (time (method4 source-list)) "method4") results)
(push (list (time (method5 source-list)) "method5") results)
(push (list (time (method6 source-list)) "method6") results)
(push (list (time (method7 source-list)) "method7") results)
(push (list (time (method8 source-list)) "method8") results)
(push (list (time (method9 source-list)) "method9") results)
(map println (sort results))
These don't give exactly the same answer (odd/even) but I was only looking to make a quick comparison - not proper testing methodology... :)
Note that method7 requires a larger stack for longer lists.
The topic of
As somebody else said already in this thread: "recursion is overrated"
It may be interesting from a theoretical point of view to reduce iteration to tail-recursive function calls, but from a practical point of view I don't see much sense in it. First of all, its inefficient, it took the Scheme designers a long time to implement continuations with more or less acceptable but not stellar performance.
Don't get me wrong I am all for recursion where an algorithm is elegantly expressed this way, and newLISP supports recursion. But often I see that people in traditional Lisp texts try to force recursion on naturally linear, iterative problems. Remember that only the tail-recursive part in an recursive algorithm can be optimized. But why optimize something into iteration if it was expressed more naturally iterative in the first place?
Generations of programmers have been taught by their CS professors that recursion is the holy grail of algorithm design. I think its just not true, its an important part among other important techniques, nothing else. I agree, that it has a special place in functional programming theory, but it is not special in a practical, applications oriented, multi-paradigm scripting Lisp.
Use recursion where appropriate, i.e. processing and generating tree like structures, but where the problem is linear don't force it into a recursive perspective to satisfy some theoretical purity of solving all control patterns in computer programming with recursive function calls.
newLISP has a wide selection of iterator functions to make iteration comfortable: 'dotimes, dolist, for, while, until, do-while, do-until'; more than most other scripting languages.
Most recursive algorithm will suffice with the default stack depth of 2028 in newLISP. You can bump it up to whatever number you need using the -s command line switch. Most recursive programs running into stack problems are better solved using an iterative algorithm. Again remember: only the tail-recursive part can be optimized (translated into iteration) anyway.
To make a long story short: there will never be tail-recursion optimization in newLISP ;-)
Ok Lutz, I didn't want to oblige you to implement tail-recursion!
As you said, recursion is a way to apply an algorithm (so it has advantages and weakness as any other algorithm).
I proposed to insert a such function so the users will have another important instrument in their toolbox.
In other languages recursion is a must (for example to by-pass the problem related to immutable variables), but newLisp, as many other languages, offer "rewritable" variables, so recursion becomes simply another tool.
Finally, I simply think that...
If I have a tool I can decide if use it or not (flexibility); if I haven't a tool I cannot decide anything...
Thank you.
Quote
If I have a tool I can decide if use it or not (flexibility); if I haven't a tool I cannot decide anything...
I totally agree on that point and newLISP prides itself to often offer different styles and solutions to the same problem, which is all the fun we are having in this thread. A big part of the joy of programming is to express your own style.
Unfortunately there is no way to implement tail-recursion optimization or some helper function like 'recur' with little code and no impact on performance, the way newLISP's VM is architectured.
After some minor tweaking, I ran the code that Cormullion was nice enough to post. I used a source list of length 81920. Initally, I ran the versions one at a time and discoverd that method7 never completed, even after 40 minutes. So, when I ran the whole group, it was omitted.
I implemented only this version of odd?
newLISP 10.0.0 WIN32 (Windows XP pro)
Here are typical results, time in milliseconds
(468 "method9")
(515 "method3")
(546 "method2")
(609 "method5")
(781 "method6")
(25781 "method8")
(29234 "method4")
(103562 "method1")
( never completes "method7")
I was actually surprised to see that method9 turned in the best performance.
Also note that the results clearly fall into three groups: {9, 3, 2, 5, 6}; {8, 4}; {1}. And I suppose we could add a fourth gorup {7} also out there by itself.
The fast methods 9,3,2,5,6 all work the list sequentially and assemble the new list sequentially.
The destructive methods 8,4,1 all do indexed access in the list using indexing, which gets slower the more they have to count into the list in the (lst $idx) expressions.
I could imagine the only way to do it destructively fast is using some form of 'replace', which works the list sequentially and changes the found element directly in place as it goes.
The difference will be smaller or can be neglected when dealing only with a few dozen elements, or when using arrays in 8,4,1.
Quote from: "ale870"
Only relatively small set of recursive functions can be tail-call optimized. Typically, recursive call can be eliminated only by introduction of a new data - some kind of stack. So, efficiency is about the same, just it is much harder to write non-recursive version. Fibonacci
can be rewritten on non-recursive way easily. But with only slight change, for example,
[/list]
recursive version is still easy, but non-recursive version is much more complicated, and probably only for a constant factor more efficient.
just to fillup the solutions...
This topic got me thinking the whole week actualy because i also had the
same though once, doing it all functional,... The result is not always a
charming clean code line...The results from this topic are very nice and
creactive.. (the use of 'bits and the use of replace..nice ;-)
The original statement of doing this without a loop but only functional is
not matching the procedure ;-) This can only be solved with at least 1
loop...(as map dolist etc are macro loops)
The old fasioned 'for..not listed here but yet actualy the fastest..irrc..
(setq L '("string 1" "string 2" "string 3" "string 4" "string 5" "string 6"))
(for (l 0 (dec (length L)) 2) (setf (L l) (upper-case (L l))))
("STRING 1" "string 2" "STRING 3" "string 4" "STRING 5" "string 6")
Replacing the 0 with 1 or 2 indicates the start position.. with a step 2..
I tried playing with 'index 'filter 'clean and ref-all but they all get very
bigish in code.. Yes I must admit..'for is not the nicest loop on the block
but its an effective one..we should not neglect it ;-)
@newdep your observation is a good point, since in every other algorithm we are obliged to check every value,m then we need to take/eliminate a condition.
In the FOR...STEP statement, we really by-pass the conditions, and we made only the half of the checks.
It seems very strange that a procedural algorithm can manage this in a way not that cannot be implemented in a functional way.
I think we could avoid to use FOR..NEXT only if we could implement a kind of index, example:
(inc i 2)
This could be a good way without using real for/loops statements.
here it is ->
(map (fn(x) (setf (Q x) (upper-case (Q x)))) (index = (map (fn(x) (% x 2)) (index != Q))))
assuming Q is a string based list...
("a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o" "p" "q" "r" "s" "t"
"u" "v" "w" "x" "y" "z")
would result in ->
("A" "b" "C" "d" "E" "f" "G" "h" "I" "j" "K" "l" "M" "n" "O" "p" "Q" "r" "S" "t"
"U" "v" "W" "x" "Y" "z")
Good solution newDep!
I love this topic, since I found how flexible is newLisp!
how about this one:
Aaaa smooth one Lutz!
Even 1 lambda less ;-)
Last not least the classic full functional, recursive solution to this problem. Slow as hell, but no side effects when flipping the flag!
(if (empty? lst) lst
(cons (if flag (upper-case (first lst)) (first lst))
(foo (rest lst) (not flag)))))
you call it with either (foo Q) for starting with ods or (foo Q true) for stating with evens.
Lutz, you cracked my mind!!!
The main reason it is slow is not in recursion itself, but in its combination with
Quote from: "Kazimir Majorinc"
Is there a way to work like Rebol? It can return a "pointer" of a list, but it is referenced to the original list. In fact if you "navigate" in the list using that "pointer", you can find all list values.
I say this because new newLisp version 10 was optimized to work/return many pointers, instead the copy.
So REST function could return a reference to the second element of the list, not its copy.
No newlisp does not use indexes like rebol does, which I sometimes like and sometimes dislike..
..So you have to create you own indexing regarding counting..
But newLisp could get a function, similar to
(define (rest-ref argList)
(1 argList) )
But in this way it works
> (push 'Z (rest-ref a))
(Z 8 7 6 5)
> a
(9 8 7 6 5)
I think we need a way (using setf?) to return a reference.
Currently things works like this:
(push 'Z (rest a)) => (Z 8 7 6 5)
With 'a' unchanged. If we could push on (rest a) as a reference the result would be:
Which is not (Z 8 7 6 5). if this is what you want, do this:
and have 'a' changed.
Lutz, is there any way (generally speaking) to make a function that return a reference to an element of a list (like in the example before) instead returning a copy? Can I do that using contexts?
Not for user-defined functions
(push 'Z (L 2)) => (Z c d e)
L => (a b (Z c d e) f g)
You
(define (my-push lst offset)
(push 'Z (lst offset)))
(my-push L 2) => (Z c d e)
L:L => (a b (Z c d e) f g)
Your explanation is very clear, thank you Lutz!
just for information: in my blog I just started to write some workshops to "put all together" about my experience acquired in this topic (I want even to highlight the new things I learnt). Even if they are in italian language there is an "automatic" translator using google. I'm very happy if you read and correct/comment/etc... my workshops.
First workshop is at:
ORIGINAL (ITALIAN):
http://newlisp.wordpress.com/2008/12/15/convertitevi-workshop-1/
TRANSLATION:
http://translate.google.com/translate?hl=it&ie=UTF8&sl=it&tl=en&u=http://newlisp.wordpress.com/2008/12/15/convertitevi-workshop-1/
Thank you!
I thought it'd be fun to implement this using streams...
Results:
A b C d E f G "done"
The upper-other-case function which does this:
(join-streams
(every-other-stream (map-stream upper-case s))
(every-other-stream (tail s))
)
)
Other functions used by upper-other-case:
(if (empty-stream? s1)
s2
(empty-stream? s2)
s1
(letex (a (head s1)
b (tail s1)
c s2)
(cons-stream a (join-streams 'c 'b)))
)
)
(define (stream-from-list l)
(if (empty? l)
the-empty-stream
; underscore hack, newlisp namespace problem with:
; (stream-from-list '(a b c)) b/c of usage of vars a & b
(letex (_a (first l) _b (rest l))
(cons-stream '_a (stream-from-list '_b)))
)
)
(define (every-other-stream s)
(if (empty-stream? s)
the-empty-stream
(empty-stream? (tail s))
(letex (a (head s))
(cons-stream a (every-other-stream '())))
(letex (a (head s) b (tail (tail s)))
(cons-stream a (every-other-stream 'b)))
)
)
For the rest of the functions you can read:
To pass the time while awaiting my turn at the medical center, I thought about how to take some of the information from this thread to produce a very fast method. Method9 was previously the fastest, so I included only method9 and my latest endeavor, method11; it smokes method9. I wanted to have a list large enough to give a run time of at least half a second. This required 16 iterations to construct source-list, resulting in length of 327680.
I think method11 still has code that is clear, easy to maintain, and efficient, assuming ending with an output list the same size as the source list is acceptable.
;; To try out the really slow methods, reduce iterations to 2 or 3 and work your way up
(set 'source-list "a") ;after generating source-list the first time, can comment out this line
(set 'iterations 16) ; for new methods, use a small value like 3 to start
(if (< (length source-list) 4)
(silent ;;silent to supresses output of list generation. Use begin to see output
(set 'source-list '("a" "b" "c" "d" "e"))
(for (zz 1 iterations) (push source-list source-list -1))
(set 'source-list (flat source-list))
)
)
(println (length source-list))
;; Need to reset these in case running the code several times in succession
(set 'newList nil 'results nil 'myeven? nil)
(define (method9 lst)
(dolist (this-string lst)
(if (odd? $idx)
(push (upper-case this-string) newList -1)
(push this-string newList -1)))
newList)
(define (method11 lst)
(while lst
(set 'myeven? (not myeven?))
(if (= myeven? true)
(push (upper-case (first lst)) newList -1)
(push (first lst) newList -1)
)
(pop lst)
)
)
(push (list (time (method9 source-list)) "method9") results)
(push (list (time (method11 source-list)) "method11") results)
(println "======")
(map println (sort results))
Here are typical results on my system: newLISP 10.0.0. WIN32, Windows XP pro
(531 "method11")
(3343 "method9")
EDIT-- and here is the version of odd? I used
Also, I actually prefer to use some intermediate functions rather than inlinng the code, like below. But there is quite a speed penalty to call the functions, if speed is the goal.
(push (upper-case (first lst)) newList -1)
)
(define (process-odd-members)
(push (first lst) newList -1)
)
(define (method11 lst)
(while lst
(set 'myeven? (not myeven?))
(if (= myeven? true)
(process-even-members)
(process-odd-members)
)
(pop lst)
)
)
Quote from: "DrDave"
O_O
No comment... :-)
(I have my best idea into the bathroom! Everyone has its own place to think, to ponder :-)
Great!
you could make it even shorter putting the 'pop' inside the 'if'
(if (setq myeven? (not myeven?))
(push (upper-case (pop lst)) newList -1)
(push (pop lst) newList -1)
)
Quote from: "Lutz"
(if (setq myeven? (not myeven?))
(push (upper-case (pop lst)) newList -1)
(push (pop lst) newList -1)
)
Right, I considered that. But because no matter what happens in the 'if' block, there will be a 'pop', I decided to factor it out and write it just once.
Do you think it will make a speed difference?
Nevermind... I tested it. It DOES make it a bit faster to in-line the 'pop'. From a bit over half a second runtime to a bit under.
Quote from: "ale870"
Symbols can be used as references.
(set 'return-by-reference (lambda(lst i)(nth i lst)))
(set (return-by-reference L 0) "i!")
(set (return-by-reference L 1) "o!")
(set (return-by-reference L 2) "let's go!")
(set 'dereference-list (lambda(lst)(map eval lst)))
(println (dereference-list L)) ;("i!" "o!" "let's go!")
It has its price, but I think it is The Way.
@Kazimir can you help me to understand what's happening here?!
What's happening in newLisp with that syntax?
And, generally, speaking, can you help me to understand your example? It seems really interesting and using advanced tricks, but I'm lost after the first row!!
What's happening there?
Thank you!
@Alesandro, you've been too long without alcohol in your system resulting in cloudy thinking LOL
It's all straight-forward, if you take it bit-by-bit.
This creates the list (L.0 L.1 L.2) and binds it to L.
This just defines a function. It is identical to writing this:
This function has two paramters, a list and an integer used as an index. The function body finds the ith member in the list and returns it.
(set (return-by-reference L 1) "o!")
(set (return-by-reference L 2) "let's go!")
These three lines work the same. They simply set values to each member of the list L. It's a generic way to do this on a list
This is the same as
You can see that it take s a list as a paramter, then evaluates each member of the list.
This is doing
(eval L.1)
(eval L.2)
Thank you, functional languages are still "a new thing" for me, even after many months and several bottles of alchol :-) !
Quote from: "ale870"
It will make more sense the more you use it. I'm just a casual programmer, not a hard-core computer scientist like Kaz or Lutz or some of the others.
I'm not sure, but I think Kaz used 'return-by-reference' for his function name to emphasize that a pointer is being used rather than returning a copy of the actual value. Someone will verify or correct this, I'm sure.
There is an easier, straight forward and safe way to pass and return data by reference to and from user-defined functions, when using default functors:
(define (foo lst x)
(push x lst)
lst)
(foo data 99) => data
data:data => (99 a b c d e f)
; push one more than use the return value
(reverse (foo data 98)) => (f e d c b a 99 98)
data:data => (f e d c b a 99 98)
so basically when you call the function you pass the namespace handle only, which will pass it by reference and return it again. All list/array/string functions in newLISP now if they see a context they have to look for the list/array/string inside the default functor of the context which is <context>:<context>
Quote
Personaly i have this problem ->
.. If you start studying it, its getting even more difficult ..
not because of its complexity but because of it flexibility.. ;-)
@Lutz, I think functors are the best way to manage references. They are easy to be used, fast and readable.
@newdep, that is normal. In fact, while you are studying a programming language, you want to face more and more complex problems, and every problem open a door with many possible solutions inside. But in order to apply a solution, you need to acquire more knowledge. Furthermore, more a language is "flexible", more solutions you can find, and more things you need to learn to apply them. I love this!
I really like progrmaming languages, I study some of them only to get the "phylosofy" that is behind them. Instead I learnt other languages to use them for specific jobs or for every-day-usage. I know more than 15 languages but, of course, I know very well only some of them.
newLisp is one of those languages I started to study just for curiosity, and to learn some basics of functional languages. But in the time, I discovered that it's a powerful tool, and that Lutz made a great job with it.
So I decided to "promote" it to "everyday-language".
But in the time I even discovered that it was a good language not only for scripting, but even for something more complex. So... I'm here to discuss with you, in order to learn every day something more, and to help other guys (this is the reason I opened one italian blog site).
Hi all!
This past weekend I was trying to automate the word list, but had a problem on Windows 98se (48 megabytes of memory)...
This code slows down to a dead crawl, unless I add
; Create all 456976 English four letter words...
; ( Warning: May be offensive to some sensitive programmers ;)
(for (z 97 122)
(for (y 97 122)
(print (time ; begin timing debug
(for (x 97 122)
(for (w 97 122)
(push (string (char z) (char y) (char x) (char w)) word-list -1)
; (inc ctr) ;<<< uncommenting this statement makes time linear
)
)
) ",") ; end timing debug
)
)
(println ctr " - " (length word-list) " words.")
(setq source-list (copy word-list)) ; copy list before each pass
; trust newLISP, but verify... ;)
(println (slice source-list 0 32))
(println (slice source-list -32))
(exit)
Does this work for you on other systems? Or have I found a strange problem with newLISP? May need to add another
-- xytroxon
I think that must be a bug. It doesn't appear to matter what you insert - a number or string, just anything other than the push result. Older versions of newLISP don't show this behaviour...
Its the returning of the growing word-list getting longer and longer from the 'for' statement.
Instead of inserting (inc cnt) you can put any thing else i.e. true or nil, which changes the return to a smaller piece of data.
added later:
In older versions 'push' returned the pushed element, so the return value as last fucntion in a 'for' loop was always small.
I didn't try to figure out your code, but just ran it. As you said, incrementing your counter and it zips through. Comment it out and it crawls, getting slower as it progresses.
newLISP 10.0.0 WIN32 XP pro
But Lutz I thought it returned a reference rather than a copy?
- ah wait, it's the return of
There is a list of all of them here:
http://www.newlisp.org/downloads/newLISP-10.0-Release.html
Its basically everything except user-defined functions and macros and 'for' and all other iterators with a local looping variable, like 'dotimes', 'dolist', 'doargs' and 'dotree'.
... so the following is possible:
(1 2 3)
> (reverse (begin (push 99 l)))
(3 2 1 99)
> l
(3 2 1 99)
>
the reference passes through the 'begin' without a problem.
Note that 'push' in older versions always returned the pushed element, now it returns a reference to the list.
starting version 10.0.1 the 'for' loop will return the reference, so there will be no slowdown.
Yes, DrDave, that was everything right. Henx.
Using references is a big improvement even to speed up the code.
Lutz, it means now the functors can be substituted in some way in the program, isn't it? In fact, in the past, we used functors to pass values by reference, but now they could be useful only for user-defined functions.
Ones question: Is there any reason (e.g. performance) to still use functors instead native reference-passing?
If I find a situation where I can use either functors or function reference, is there any tip to decide what's the best way to follow?
All built-in functions automatically pass references in and out for lists, strings and arrays. Only with user-defined functions and macros you need default-functors for reference passing in and out.
If the majority of lists and strings in a program are small, then don't worry about the whole thing. When lists or strings get bigger than a hundred elements then you might consider reference passing, but only if some operation on them occurs frequently.
In older versions everything in newLISP was value passing by default and newLISP was still considered one of the fastest scripting languages (see http://www.newlisp.org/benchmarks/ )
But the reference passing issue is not just about speed. Reference passing also allows you to write destructive user-defined functions without recurring to macros or passing quoted symbols (1).
From a programming style point of view, I would say that value passing and non-destrcuctive user-defined functions are the cleaner, safer and more intuitive way to write bug-free functional programs. But from a practical point of view, you need reference passing to efficiently deal with large data objects, when you want to avoid frequent copying. Then default-functors are the most straight forward method in newLISP.
(1) Traditionally reference passing can also be achieved using either macros or passing quoted symbols to user-defined functions. This method is not recommended because it brings a whole basket of other problems, i.e. variable capture. There are ways around it, but they lead to complex code. Some of Kazimir's blog posts investigate these problems in greater detail.