Print Page - Streams in newLISP

Title: Streams in newLISP
Post by: itistoday on February 23, 2008, 03:51:06 PM

Note: This was originally a response to Pavel in his thread (//http), but I figure it deserves its own thread.

~~Quote from: "Elica"~~Now let me go back to newLisp. Does it support streams/sequences? (Not in the sense of I/O streams, but in the sense of infinite lists with delayed evaluation).

Thanks for asking this question. I was planning on investigating this question myself a while ago but never got around to it. Because of you I decided to spend the time finally. :-)

Short answer: Yes, but not elegantly like with Scheme. I think this is mainly due to the newLISP's dynamic scope. For example, trying to do memoization does not seem ... possible (actually it is, see several posts down). You might be able to do something with contexts but I think it would turn out ugly...

Long answer](set 'the-empty-stream '())

(define-macro (cons-stream)
   (letex (x (args 0) y (args 1))
      (cons x (list (delay y)))
   )
)

(define-macro (delay)
   (letex (x (args 0)) (fn () x))
   ;(letex (x (args 0)) (memo-proc (fn () x)))
)

(define (memo-proc)
   (letex (func (args 0))
      (fn ()
         (if (not already-run?)
            (begin
               (set 'result (func))
               (set 'already-run true)
            )
         )
         result
      )
   )
)

(define (head s)
   (first s)
)

(define (tail p)
   (force (last p))
)

(define (force func)
   (func)
)

(define (nth-stream n s)
   (if (= n 0)
      (head s)
      (nth-stream (- n 1) (tail s))
   )
)

(define (empty-stream? s)
   (empty? s)
)

(define (print-stream s)
   (if (empty-stream? s)
      "done"
      (begin
         (print (head s) " ")
         (print-stream (tail s))
      )
   )
)

(define (enum-interval low high)
   (if (> low high)
      the-empty-stream
      (expand (cons-stream low (enum-interval (+ low 1) high)) 'low 'high)
   )
)

(define (integers-from n)
   (expand (cons-stream n (integers-from (+ n 1))) 'n)
)

(set 'integers (integers-from 1))
(println "nth 20: " (nth-stream 20 integers))

(while true
   (print "> ")
   (read-line)
   (if (= (current-line) "")
      (exit)
      (println (eval-string (current-line)))
   )
)
[/code]

I tried:

Code Select Expand
> (print-stream integers)

And it printed up to 678 and then crashed:

Code Select Expand
call stack overflow in function list : delay
called from user defined function integers-from
called from user defined function func
called from user defined function force
called from user defined function tail
called from user defined function print-stream
called from user defined function print-stream
called from user defined function print-stream
...

This is simply because newLISP doesn't have tail-call recursion. You can change the stack size using the -s option when running newlisp. Update]

Code Select Expand
(define (print-stream s)
	(while (not (empty-stream? s))
		(print (head s) " ")
		(set 's (tail s))
	)
	"done"
)

You can have fun, here's an example using the above program's evaluator:

Code Select Expand
> (set 'ones (cons-stream 1 ones))
(1 (lambda () ones))
> (print-stream ones)
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .... (it goes on.. and then crashes)

Title:
Post by: itistoday on February 23, 2008, 06:48:00 PM

One of the annoying things here is that it seems you have to use the letex or expand functions in most of the situations where you call (cons-stream). I was trying to write map-stream but I'm encountering a weird problem:

Code Select Expand
(define (map-stream func s)
	(if (empty-stream? s)
		the-empty-stream
		(letex ((a (func (head s)))
				(b func)
				(c (tail s)))
			(cons-stream a (map-stream b c))
		)
	)
)

enum-interval works as demonstrated here:

Code Select Expand
> (set 'interval (enum-interval 10 100))
(10 (lambda () (enum-interval (+ 10 1) 100)))
> (print-stream interval)
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 done

But there's a problem when trying to use map-stream as demonstrated here:

Code Select Expand
> (set 'bigger (map-stream (fn (x) (* x 2)) interval))
(20 (lambda () (map-stream (lambda (x) (* x 2)) (11 (lambda () (enum-interval (+ 
       11 1) 100))))))
> (force (last bigger))
()

The problem occurs because of this letex expression from map-stream:

Code Select Expand
		(letex ((a (func (head s)))
				(b func)
				(c (tail s)))
			(cons-stream a (map-stream b c))
		)

For some reason the symbol 'c' is being set to the empty list. Help?

Title:
Post by: itistoday on February 24, 2008, 01:37:05 PM

nm - see below.

Title:
Post by: itistoday on February 24, 2008, 03:28:53 PM

Got it!

The problem is that this kind of list:

Code Select Expand
(11 (lambda () (enum-interval (+ 11 1) 100)))

Will get evaluated (duh!). newlisp then interprets that as the command for doing an implicit slice of the list (everything from the 12th position onwards), and this returns '() obviously! So I just quoted it and that fixed it:

Code Select Expand
(define (map-stream func s)
	(if (empty-stream? s)
		the-empty-stream
		(letex (a (func (head s))
				b func
				c (tail s))
			(cons-stream a (map-stream b 'c))
		)
	)
)

And now... ladies and gentlemen, map-stream in action!

Code Select Expand
> (set 'i (enum-interval 10 100))
(10 (lambda () (enum-interval (+ 10 1) 100)))
> (set 'b (map-stream (fn (x) (* x 2)) i))
(20 (lambda () (map-stream (lambda (x) (* x 2)) (quote (11 (lambda () (enum-interval 
       (+ 11 1) 100)))))))
> (print-stream b)
20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 178 180 182 184 186 188 190 192 194 196 198 200 done

Tada!

Title:
Post by: itistoday on February 24, 2008, 03:46:22 PM

Here are the new functions. With these you can do all sorts of powerful things. The only problem that exists with doing streams in newLISP is that so far I don't think you can do memoization, but I would be very happy if someone proved me wrong on that. Anyways, here are map-stream, filter-stream, and accumulate:

Code Select Expand
(define (map-stream func s)
	(if (empty-stream? s)
		the-empty-stream
		(letex (a (func (head s))
				b func
				c (tail s))
			(cons-stream a (map-stream b 'c))
		)
	)
)

(define (filter-stream pred s)
	(cond
		((empty-stream? s) the-empty-stream)
		((pred (head s))
			(letex (a (head s)
					b pred
					c (tail s))
				(cons-stream a (filter-stream b 'c))
			)
		)
		(true (filter-stream pred (tail s)))
	)
)

(define (accumulate combiner init-val s)
	(if (empty-stream? s)
		init-val
		(combiner (head s) (accumulate combiner init-val (tail s)))
	)
)

Here's an example straight out of SICP Lecture 6a that you can find here (//http):

Code Select Expand
(set 'odd (fn (x) (= (& x 1) 0)))

(define (fib n)
	(let (f '(0 1))
		(dotimes (i (- n 1)) (push (+ (f -1) (f -2)) f -1))
		(f -1)
	)
)

(define (odd-fibs n)
	(accumulate cons '()
		(filter-stream odd
			(map-stream fib (enum-interval 1 n))
		)
	)
)

Results of running this in newlisp:

Code Select Expand
> (odd-fibs 30)
(2 8 34 144 610 2584 10946 46368 196418 832040)
> (time (odd-fibs 30))
5

Title: Re: Streams in newLISP
Post by: Elica on February 24, 2008, 10:47:28 PM

~~Quote from: "itistoday"~~Note: This was originally a response to Pavel in his thread, but I figure it deserves its own thread.

Yes, absolutely. I was thinking to do the same. Anyway, is there a way to post few images? I have the paper which I'm talking about only as scanned images.

I'd like to show you the paper, so that you could see all the nice examples in it. After this I'll demonstrate how each lisp example can be done in Logo (of course, I mean Elica Logo), and then it might be easier to reimplement them in newLisp ... or it might just give some ideas for other features... or in the worst case by reimplementing you will have some proof-of-concept that newLisp's streams are fine...

So, the first problem is how to give you the images... I can upload them temporarily somewhere on www.elica.net, but it would be nice if they are available for longer than this temporarity(sic)

Title: Re: Streams in newLISP
Post by: Elica on February 24, 2008, 10:55:44 PM

~~Quote from: "Elica"~~Anyway, is there a way to post few images?

The scanned paper is about 1000* pages, their size is around 1MB (all of them). I can try modifying the images to reduce the size, but this could make reading harder...

The paper is called "Concept oriented learning environments - a project using sequences in Scheme", written by Herbert Loethe, presented at EuroLogo 2003. The images I have are scanned from the proceedings of the conference.

_________

~~[size=75]~~* binary, of course[/size]

Title:
Post by: itistoday on February 27, 2008, 03:12:58 PM

I haven't read that paper, but yeah if you want to post some links up go for it. :-)

In another thread (//http) Lutz showed me an interesting function that I was able to use to do memoization with delay (thanks Lutz!). He wrote two versions of this 'memoize' function, one uses linked-lists and another uses B-trees I think.

First, the new version of delay:

Code Select Expand
(define-macro (delay)
	(let (memo-func-name (sym (string (args 0 0) "-memo")))
		(if (nil? (sym memo-func-name memo-func-name nil))
			(letex (a (args 0 0) b memo-func-name) (memoize a b)))
		
		(letex (params (rest (args 0)))
			(letex (f (cons memo-func-name 'params))
				(fn () f)
			)
		)
	)
)

It calls memoize which takes a function and creates a new memoized function with "-memo" tacked onto its name as shown here:

Code Select Expand
> (delay (+ 1 1)) 
(lambda () (+-memo 1 1))

Here are the two versions of memoize:

Code Select Expand
(define-macro (memoize func mem-func) 
	(set (sym mem-func mem-func) 
		(letex (f func m (sym "mem" mem-func)) 
			(lambda () 
				(or (and m (lookup (args) m)) 
					(last (push (list (args) (apply f (args))) m))
				)
			)
		)
	)
)

; using contexts to do lookup
(define-macro (memoize func mem-func) 
	(set (sym mem-func mem-func) 
		(letex (f func  c mem-func) 
			(lambda () 
				(or (context c (string (args))) 
					(context c (string (args)) (apply f (args)))
				)
			)
		)
	)
)

I used the odd-fibs function to do benchmarks, and discovered some interesting peculiarities. First, this kind of memoization severely degraded performance on the first run, however, it also improved it greatly if the same exact code was executed again:

Code Select Expand
> (time (odd-fibs 50))
16
> (time (odd-fibs 50))
2

Previously, without memoization, you would get these kinds of results:

Code Select Expand
> (time (odd-fibs 50))
10
> (time (odd-fibs 50))
10

Also, the second version of 'memoize' (the one that uses contexts to do lookups), is just a little slower than the first (by about a millisecond in my tests). However, since it has a faster Big-O time, I think that it'll be faster once there are more stored solutions inside of the memoized functions memory.

Compare these results to running the standard (non-stream) version of odd-fibs:

Code Select Expand
(define (odd-fibs-standard n , temp fiblist)
	(for (i 1 n)
		(set 'temp (fib i))
		(if (odd temp)
			(push temp fiblist -1)
		)
	)
	fiblist
)

Which consistently got very fast times:

Code Select Expand
> (time (odd-fibs-standard 50))
1
> (time (odd-fibs-standard 50))
1

Note that the memoized version comes close to this when run a second time.

Is it worth it? I'm not sure on that. I think it depends on how you're using the streams, and what kind of algorithm you have, because just changing parameters to your function calls will likely result in slowdowns as shown here:

Code Select Expand
> (time (odd-fibs 10))
3
> (time (odd-fibs 15))
5
> (time (odd-fibs 50))
18
> (time (odd-fibs 49))
20
> (time (odd-fibs 49))
2

Title:
Post by: itistoday on February 27, 2008, 05:19:49 PM

Playing around some more with this I discovered something interesting.

Code Select Expand
> (time (odd-fibs 50))
16
> (time (odd-fibs 49))
20
> (time (odd-fibs 48))
21
> (time (odd-fibs 47))
21
> (time (odd-fibs 46))
26

I wanted to see what happened if I kept going, so I wrote a function (fibs-test) to do this for me:

Code Select Expand
(define (fibs-test n)
	(for (i n 1)
		(let (duration (time (odd-fibs i)))
			(println i " " duration)
		)
	)
)

This function calls odd-fibs starting from n and goes down to 1 (I used 50 for n). I ran it using both memoization functions. The results are shown below. The blue line represents the list-based memoization function, and the green line is the one that uses the context-based memoization function:

(//%3C/s%3E%3CURL%20url=%22http://www.kinostudios.com/images/memoization.png%22%3Ehttp://www.kinostudios.com/images/memoization.png%3C/URL%3E%3Ce%3E)

"Huh, that's interesting" I thought. I did a second test, this time going the other way, from 1 to 50:

(//%3C/s%3E%3CURL%20url=%22http://www.kinostudios.com/images/memoization2.png%22%3Ehttp://www.kinostudios.com/images/memoization2.png%3C/URL%3E%3Ce%3E)

The results from the context-based memoization are practically identical (which makes sense since it's a self-balancing tree), but this time the list-based one was even worse, clearly showing exponential properties. Let's look at the list-based ones overlapped on one another:

(//%3C/s%3E%3CURL%20url=%22http://www.kinostudios.com/images/memoization3.png%22%3Ehttp://www.kinostudios.com/images/memoization3.png%3C/URL%3E%3Ce%3E)

Edit: updated explanation, previous one was flawed

So what's happening? In the first run (running odd-fibs from 50 to 1), (enum-interval 1 50) is called. This gets memoized to enum-interval-memo, and the result is added to the list with '(1 50) as the key. As this iteration continues, '(2 50) is added to the list, '(3 50), and so on. In other words, for the entire run of (odd-fibs 50), no cached result is used, and so it just computes it normally. Keep in mind however, that enum-interval-memo:mem keeps growing on each call, and because no key is ever used again in the way we're running the test, it has to search the entire list on each call! This is because next iteration, the keys will be '(1 49), '(2 49), etc. Since, on the first run, we started with the largest number (50), at that point the list is very small (initially empty), thus it doesn't take very long to traverse it. So it should be obvious why when you go in the opposite direction, it takes such a long time. When you start from 1 and go to 50, by the time you get to computing the most difficult fib-interval (1-to-50), the list is gigantic!

When we switched over to the context-based memoize function, even though again no cached results were used from enum-interval (since the key depends on both the first parameter and the second one, which changed each time), not having to traverse a list helped a *LOT*. The red-black tree that contexts use is self-balancing, and so the order in which we add keys to it doesn't really affect the height of the tree, thus you get nice O(log(n)) search times.

Don't forget though, it's not just enum-interval that's being memoized, map-stream and filter-stream are being memoized too! This helps a lot, especially on the second run (see below).

So indeed, based on this, I'd say definitely go with the second version of memoize! :D

Update:

What's nice about the way (delay) is written is that you can customize the memoized function if you want! For example, since enum-interval doesn't really do much computation anyways, you can just do this:

Code Select Expand (set 'enum-interval-memo:enum-interval-memo enum-interval)

There is very little difference between the performance of doing that or sticking to the default context-based memoized version of enum-interval. The real savings comes from memoizing map-stream and filter-stream (which contain the results of (fib n)), as seen when you run the 50-to-1 test again... (see the red line).

(//%3C/s%3E%3CURL%20url=%22http://www.kinostudios.com/images/memoization4.png%22%3Ehttp://www.kinostudios.com/images/memoization4.png%3C/URL%3E%3Ce%3E)

btw, I realize the edit count on this post is getting ridiculous... I'll try to keep it in the single digits ;-)

Title:
Post by: Elica on February 27, 2008, 08:22:22 PM

~~Quote from: "itistoday"~~I haven't read that paper, but yeah if you want to post some links up go for it. :-)

I'm more than willing to show the paper, but cannot find where to post the scanned pages. This is the only form of the paper which I have. I do not have it online. And did not manage to find it on the web.

Do you know any free repository where the images will stay for a long time?

Title:
Post by: itistoday on February 28, 2008, 01:24:10 PM

~~Quote from: "Elica"~~Do you know any free repository where the images will stay for a long time?

Putfile.com (//http)?

Btw, I updated the explanation above, so if you (or anyone else) read the old version, I recommend reading it again, as I woke up this morning and realized I had made a mistake in my previous explanation.

Title:
Post by: Elica on February 29, 2008, 09:28:49 AM

Thanks. I'm now waiting for a reply from the paper's author. I do not like to post the paper without permission... and I hope that he has the paper online.

Meanwhile I will post the examples and the expected result as text. I have them as comments in my Logo program...

Warning 1. The LISP code is typed by me by hand. I have not verified it. So, there might be some typos...

Warning 2. I will split the examples in several posts...

Title:
Post by: Elica on February 29, 2008, 09:36:06 AM

INTRO

While waiting for permission to post the original paper, I will show you the examples. I hope that you may find them interesting -- specially the more complex ones at the end.

I am curious whether you can reimplement them in newLisp. Well, I'm sure you can, because I have done them in Elica Logo.

NOTE! The author's terminology is to use 'sequence' instead of 'stream'.

So, let me first enumerate the sequence functions:

seq - creates a sequence

head-el - returns the first element

tail-seq - returns the subsequence without the first element

shs - shows a sequence

sshs - shows a sequence of sequences

The semantic relations between these functions are:

(seq (head-el x) (tail-seq x)) is x

(head-el (seq h t)) is h

(tail-seq (seq h t)) is t

Title:
Post by: Elica on February 29, 2008, 09:50:55 AM

SIMPLE SEQUENCES

Constant sequence consist only a constant value.
Code Select Expand (define (constant-seq c) (seq c (constant-seq c))) (shs (constant_seq 1)) 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Arithmetic sequence has starting element and a rule (function) to generate the next element.
Code Select Expand (define (arithmetic next-el a) (seq a (arithmetic next-el (next-el a))))

Let's define multiples of 5 by the rule:
Code Select Expand (define (add-5 n) (n + 5)) (define multiples-5 (arithmetic add-5 5)) (shs (multiples-5)) 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, ...

Sequence of natural numbers is arithmetic sequence:
Code Select Expand (define nat (arithmetic (lambda (n) (n + 1)) 1)) (shs (nat)) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

Title:
Post by: Elica on February 29, 2008, 10:04:48 AM

MAP SEQUENCES

General rule-based sequence generator:
Code Select Expand (define (seq-by-rule next-el a) (seq a (seq-by-rule next-el (next-el a))))

Let's map a square function on the sequence of natural numbers:
Code Select Expand (define (map-seq f x) (seq (f (head-el x)) (map-seq f (tail-seq x)))) (define (square n) (n * n)) (define seq-of-squares (map-seq square nat)) (shs (seq-of-squares)) 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...

Let's use the same thinking for elementary operations on sequences; sums, differences and products.
Code Select Expand (define (seq-op op x y) (seq (op (head x) (head y) (seq-op op (tail-seq x) (tail-seq y)))) (define (seq+ x y) (seq-op sum x y)) (define (seq- x y) (seq-op difference x y)) (define (seq* x y) (seq-op product x y)) (shs (seq+ (seq-of-squares) (nat))) 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ... (shs (seq- (seq-of-squares) (nat))) 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, ... (shs (seq* (seq-of-squares) (nat))) 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, ...

Note! The test cases are translated from Logo to Lisp, and I'm not good in Lisp, so I'm not sure about the parentheses. For example, I do not know which one is the correct:

(shs (seq* (seq-of-squares) (nat)))

or

(shs (seq* seq-of-squares nat))

So, please, fix the examples if needed.

Title:
Post by: Elica on February 29, 2008, 10:53:16 AM

MORE EXAMPLES

Let's define the sequence of natural numbers in another way:
Code Select Expand (define seq1 (constant-seq 1)) (define nat (seq 1 (seq+ seq1 nat))) (shs (seq1)) 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... (shs (nat)) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

Let's now define difference and sum.
Code Select Expand (define (diff-seq x) (seq- (tail-seq x) x)) (define (sum-seq x) (seq (head-el x) (seq+ (tail-seq x) (sum-seq x)))) (shs (diff-seq (seq1))) 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... (shs (diff-seq (nat))) 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... (shs (diff-seq (seq-of-squares))) 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, ... (shs (sum-seq (seq1))) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... (shs (sum-seq (nat))) 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

A note by me (because you cannot see the text). Aggregation and differential sequences use the same sequence twice but with a shift of one element. For example, if the sequence is 1, 4, 7, 10, 13, 16,... then difference is (tail-seq x)-x = (4-1), (7-4), (10-7), ... = 3, 3, 3, ...

Title:
Post by: Elica on February 29, 2008, 11:18:46 AM

FACTORIAL, FLOATING-POINT SEQUENCES, E=2.71828..., SQRT

Let's define the sequence for factorial, for reciprocal values and for calculating constant e:

Code Select Expand (define fact-seq (seq 1 (seq* nat fac-seq))) (define (reciprocal x) (quotent 1.0 x)) (define e-series (sum-seq (map-seq reciprocal fact-seq))) (shs (fact-seq)) 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, ... (shs (e-series)) 1, 2, 2.5, 2.66666666666666667, 2.70833333333333333, 2.71666666666666667, 2.71805555555555556, 2.71825396825396825, 2.71827876984126984, 2.71828152557319224, ...

Note! Just now I start to think that I use too many parentheses. So maybe (shs e-series) should be correct, while (shs (e-series)) might be wrong...

Now, let's do calculation of square root by the Heron method.
Code Select Expand (define (heron-next-interval-2 xi) (let ((left (car xi)) (right (card xi))) (let ((next-right ((left + right) * 0.5))) (list (2 / next-right) next-right)))) (define heron-internal-seq-2 (seq-by-rule heron-next-interval-2 (list 1 2))) (define approximation interval-seq epsilon) (let ((xi (head-el interval-seq))) (if (((cadr xi) - (car xi)) < epsilon) (car xi) (approximation (tail-seq interval-seq) epsilon)))) (shs heron-interval-seq-2) [1 2], [1.33333333333333333 1.5], [1.41176470588235294 1.41666666666666667], [1.41421143847487002 1.4142156862745098], [1.41421356237150019 1.41421356237468991], [1.41421356237309505 1.41421356237309505], [1.41421356237309505 1.41421356237309505], [1.41421356237309505 1.41421356237309505], [1.41421356237309505 1.41421356237309505], [1.41421356237309505 1.41421356237309505], ... (approximation heron-interval-seq-2 0.00001) 1.41421143847487002

Title:
Post by: Elica on February 29, 2008, 11:33:15 AM

COLLATZ SEQUENCE

The Collatz sequence is easy to generate, but is still unsolved problem. Let's first define the sequence:

Code Select Expand (define (collartz-next n) (if odd? n) (3 * n + 1) (n / 2))) (define (collatz-seq x) (seq-by-rule collatz-next x)) (shs (collatz_seq 6) 15) 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...

Let's go one level up and define a sequence of all Collatz sequences.

Code Select Expand (define seq-all-collatz-seq (map-seq collatz-seq nat)) (shss seq-all-collatz-seq 10 10) 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, ... 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, ... 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, ... 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ... 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, ... 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, ... 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, ... 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ... 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, ... 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

If somebody has a hypotheses about multiples of 5, then:
Code Select Expand (define seq-multiple-5-collatz-seq (map-seq collatz-seq multiples-5)) (shss seq-multiple-5-collatz-seq) 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, ... 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ... 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, ... 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, ... 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, ... 30, 15, 46, 23, 70, 35, 106, 53, 160, 80, ... 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, ... 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, ... 45, 136, 68, 34, 17, 52, 26, 13, 40, 20, ... 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, ...

Now let's define finding the index of the first appearance of 1 (the unproven fact is that each Collatz sequence independent on the initial number goes to 1):
Code Select Expand (define (index-first-1 x) (if ((head-el x) = 1) 1 (1 + (index-first-1 (tail-seq x))))) (define index-first-1-seq (map-seq index-first-1 seq-all-collatz-seq)) (shs index-first-1-seq 40) 1, 2, 8, 3, 6, 9, 17, 4, 20, 7, 15, 10, 10, 18, 18, 5, 13, 21, 21, 8, 8, 16, 16, 11, 24, 11, 112, 19, 19, 19, 107, 6, 27, 14, 14, 22, 22, 22, 35, 9, ...

A generalization of a Collatz sequence -- a sequence machine. Two functions are given for this sequence generating machine. Follows the definition, a test example and the result;
Code Select Expand (define (seq-machine f1 f2) (lambda (n) (if (odd? n) (f1 n) (f2 n)))) (define (seq-by-seq-machine f1 f2 a) (seq-by-rule (seq-machine f1 f2) a)) (define example-seq (seq-by-machine (lambda (n) (3 * n + 5)) (lambda (n) (n / 2)) 15)) (shs example-seq 30) 15, 50, 25, 80, 40, 20, 10, 5, 20, 10, 5, 20, 10, 5, 20, 10, 5, 20, 10, 5, 20, 10, 5, 20, 10, 5, 20, 10, 5, 20, ...

Title:
Post by: Elica on February 29, 2008, 11:42:31 AM

That's all folks. I hope that you can do the examples in newLisp too.

And again, sorry for the many wrong parentheses... I believe you will find the right path in the maze of bugs and typos.

Good luck!

Title: Re: Streams in newLISP
Post by: Elica on February 29, 2008, 11:54:44 AM

~~Quote from: "itistoday"~~
I tried:

Code Select Expand > (print-stream integers)

And it printed up to 678 and then crashed:

<snip>

This is simply because newLISP won't allow you to recurse infinitely. You can change the stack size using the -s option when running newlisp.

Instead of making examples with interval (instead of really unlimited streams), you can just redefine print-stream to have one more parameter, namely how many elements to print.
Code Select Expand (print-stream {stream} {count})

Hm! You say it crashes because of the stack! Are there tail-calls in newLisp? They will resolve all problems with recursion if tail-recursion is used (when possible).

Title:
Post by: cormullion on March 01, 2008, 01:45:06 AM

Interesting stuff here, if a little advanced for me - but what are the newLISP definitions of:

seq - creates a sequence

head-el - returns the first element

tail-seq - returns the subsequence without the first element

shs - shows a sequence

sshs - shows a sequence of sequences

These and the functions they call need to be defined before all these sequences can be executed, I think...?

Title:
Post by: Elica on March 01, 2008, 02:11:08 AM

Absolutely.

The point is that if someone is going to try these examples in newLisp, (s)he has to write these functions too. Their code is not mentioned in the original paper. I have no idea whether they are a part of Scheme Lisp or are made by the author.

I only have the Elica Logo implementaitons of these functions, which I made in such a way, as to be able to recreate all examples.

For those who are interested, here are the Logo definitions (the code especially for seq is rather tricky as it copies the local variables of the caller -- this might not be needed in a dynamicaly scoped environment):
Code Select Expand to seq :data :tail make local "$ ask caller [localnames] while :$<>[ ] [ make local (first :$) ask caller se [:] (first :$) make "$ bf :$ ] delete "$ end to head_el :seq output :seq.data end to tail_seq :seq output ask "seq [run :tail] end to shs :seq :count if not local? "count [ make local "count 10 ] make local "res [] repeat :count [ make "res lput word head_el :seq char 44 :res make "seq tail_seq :seq ] print bf bl (print :res) "... end make "shs.onminrightinputs 1 to shss :seq :count if not local? "count [ make local "count 10 ] repeat :count [ shs head_el :seq make "seq tail_seq :seq ] end make "shss.onminrightinputs 1

Title: Re: Streams in newLISP
Post by: newBert on March 01, 2008, 06:54:44 AM

~~Quote from: "Elica"~~
Hm! You say it crashes because of the stack! Are there tail-calls in newLisp? They will resolve all problems with recursion if tail-recursion is used (when possible).

No tail-recursion optimization in NewLISP, as in many Lisp moreover (except OpenLisp, I believe, and probably some others).

I miss that in NewLisp, and the lexical scoping by default too ;)

Only Scheme offers both but it is less pragmatic than NewLISP (and a little bit "scattered" among its numerous implementations) <= just a personal opinion :)

P.S.: I like a lot the conciseness of Elica, and its initial "minimalism" which allows us to do everything (or nearly)

Title:
Post by: itistoday on March 01, 2008, 09:06:29 AM

~~Quote from: "cormullion"~~Interesting stuff here, if a little advanced for me - but what are the newLISP definitions of:

seq - creates a sequence

head-el - returns the first element

tail-seq - returns the subsequence without the first element

shs - shows a sequence

sshs - shows a sequence of sequences

These and the functions they call need to be defined before all these sequences can be executed, I think...?

Arghh!! That was the point of this entire thread! cormullion, see the first couple of posts in this thread. seq = cons-stream, head-el = head, tail-seq = tail, shs = print-stream, etc...

Title:
Post by: itistoday on March 01, 2008, 09:46:48 AM

Thanks for the examples Elica, from what I saw there definitely where syntactical mistakes but they weren't so bad that someone familiar with newLISP couldn't easily fix them. Unfortunately I don't have enough time right now to go through them and write newLISP versions, but I think that anyone who's read this thread, and knows a little about streams/sequences could easily do it since most of the basic tools for making streams in newLISP are there for them. :-)

Title:
Post by: Elica on March 01, 2008, 09:58:12 AM

~~Quote from: "itistoday"~~...since most of the basic tools for making streams in newLISP are there for them...

I'd say not most, but all. Theoretically, to have complete support for streams one need only constructor and two selectors (for head and tail). They are like CONS/CAR/CDR for lists.

So, if these three functions are implemented correctly, and if the underlying mechanism of the Lisp is OK, then this is all what is needed to be able to re-implement the examples above and any other example.

Oh, yes, printing a stream would be helpful, but this is a kind of 'debugging' function, not vital for the stream processing itself.

Title:
Post by: itistoday on March 01, 2008, 10:02:37 AM

~~Quote from: "Elica"~~I'd say not most, but all. Theoretically, to have complete support for streams one need only constructor and two selectors (for head and tail). They are like CONS/CAR/CDR for lists.

Good point. :-)

~~Quote~~Oh, yes, printing a stream would be helpful, but this is a kind of 'debugging' function, not vital for the stream processing itself.

And that's there as well, without tail-call recursion unfortunately. :-

Title:
Post by: Elica on March 01, 2008, 10:27:56 AM

~~Quote from: "itistoday"~~...without tail-call recursion unfortunately.

What about iteration? It does not gulp down the stack...

Title:
Post by: itistoday on March 01, 2008, 10:38:02 AM

~~Quote from: "Elica"~~What about iteration? It does not gulp down the stack...

lol! Sorry, that's what I get for sticking too close to my scheme-inspired source for all things stream.

Here it is, this'll go forever if necessary:

Code Select Expand (define (print-stream s) (while (not (empty-stream? s)) (print (head s) " ") (set 's (tail s)) ) "done" )

:-D

Title:
Post by: newBert on March 01, 2008, 11:10:00 AM

~~Quote from: "Elica"~~
~~Quote from: "itistoday"~~...without tail-call recursion unfortunately.

What about iteration? It does not gulp down the stack...

This reminds me a passage from "Code Patterns in newLISP" (//http): Recursion or iteration? (//http)

In any case we can get through!

;)

Title:
Post by: itistoday on March 01, 2008, 11:15:08 AM

~~Quote from: "newBert"~~This reminds me a passage from "Code Patterns in newLISP" (//http): Recursion or iteration? (//http)

;)

It's just that I was translating Scheme code (which supports tail-call recursion) to newLISP. Tail-call recursion is just as fast as iteration (because they're pretty much the same thing, no?)

Title:
Post by: newBert on March 02, 2008, 01:59:07 AM

~~Quote from: "itistoday"~~It's just that I was translating Scheme code (which supports tail-call recursion) to newLISP.

That's what I do most of the time

;)

~~Quote from: "itistoday"~~Tail-call recursion is just as fast as iteration (because they're pretty much the same thing, no?)

Personally, I prefer 'tail-call recursion' that I find more intuitive, clearer and more elegant. And I regret it is not optimized in newLISP.

:)

P.S.: that's why I'm still hesitant between Scheme and newLISP (with a slight preference for newLISP ... )

Title:
Post by: Elica on March 02, 2008, 04:23:02 AM

~~Quote from: "newBert"~~P.S.: that's why I'm still hesitant between Scheme and newLISP (with a slight preference for newLISP ... )

Why hesitant? Enjoy both!

Say ~~[size=117]~~NO[/size] to software monogamy.

Title:
Post by: xytroxon on March 02, 2008, 08:00:03 AM

~~Quote from: "newBert"~~
~~Quote from: "Elica"~~
~~Quote from: "itistoday"~~...without tail-call recursion unfortunately.

What about iteration? It does not gulp down the stack...

This reminds me a passage from "Code Patterns in newLISP" (//http): Recursion or iteration? (//http)

In any case we can get through!

;)

After consulting the oracle of all knowledge, I found this:

//http://en.wikipedia.org/wiki/Common_Lisp
~~Quote~~
Lastly, the Scheme standards documents require tail-call optimization, which the CL standard does not. Most CL implementations do offer tail-call optimization, although often only when the programmer uses an optimization directive. Nonetheless, common CL coding style does not favor the ubiquitous use of recursion that Scheme style prefers -- what a Scheme programmer would express with tail recursion, a CL user would usually express with an iterative expression in do, dolist, loop, or (more recently) with the iterate package.

That makes it official, iteration IS the CORRECT way to do it! ;) LOL

Title:
Post by: newBert on March 02, 2008, 08:51:20 AM

~~Quote from: "Elica"~~
~~Quote from: "newBert"~~P.S.: that's why I'm still hesitant between Scheme and newLISP (with a slight preference for newLISP ... )

Why hesitant? Enjoy both!

Say ~~[size=117]~~NO[/size] to software monogamy.

I agree ... but I have to take into account the limitations of my machine :D

I already have installed many Logo(s), including Elica and aUCBLogo that I really enjoy, PLT-Scheme, OpenLisp, FBSL (a "Freestyle" Basic for Windows), and occasionally Caml, Python and CLisp with the intention to compare...

... and I admit that sometimes it's all Greek (or Latin) to me ;)

But its really true that one enriches the other, and vice versa. I do not conceive to use only one programming language. Two or three seem acceptable in order to not disperse excessively :)

Moreover it's time that I do the "housework" :D

Well, I keep newLisp and Scheme, and Elica and aUCBLogo, and FBSL (because it is a interpreted Basic, flexible, fast and efficient). And I continue to study while having fun, or to have fun while studying. Because "I do not want to die stupid", as we say in French.

Regards,

B.

:)

Title:
Post by: newBert on March 02, 2008, 09:29:59 AM

~~Quote from: "xytroxon"~~That makes it official, iteration IS the CORRECT way to do it! ;) LOL

... and what about the newLISP way? LOL again

;)

Title:
Post by: Elica on March 04, 2008, 07:50:02 AM

~~Quote from: "Elica"~~While waiting for permission to post the original paper...

I got a permission. Also, the author was so kind to send me the paper in PDF. I have uploaded it (temporarily) here:

http://elica.net/download/loethe.pdf

Title:
Post by: m35 on March 04, 2008, 09:49:44 AM

Thank you for sharing this Elica

Title:
Post by: itistoday on March 04, 2008, 12:41:21 PM

~~Quote from: "Elica"~~I got a permission. Also, the author was so kind to send me the paper in PDF. I have uploaded it (temporarily) here:

http://elica.net/download/loethe.pdf

Awesome, thanks for doing that, I've downloaded it and have added it to the list of things I'm going to read. :-)

newLISP Fan Club

Forum => Anything else we might add? => Topic started by: itistoday on February 23, 2008, 03:51:06 PM