Streams in newLISP

[itistoday]

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

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: You can get it... I've been playing around with this for several hours now, and here is what I have, I welcome everyone to try and improve upon this:

Code: Select all

(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)))
	)
)

I tried:

Code: Select all

> (print-stream integers)

And it printed up to 678 and then crashed:

Code: Select all

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: Or, of course, you can just use an iterative version of print-stream:

Code: Select all

(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 all

> (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)

[itistoday]

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 all

(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 all

> (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 all

> (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 all

		(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?

[itistoday]

nm - see below.

[itistoday]

Got it!

The problem is that this kind of list:

Code: Select all

(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 all

(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 all

> (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!

[itistoday]

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 all

(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:

Code: Select all

(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 all

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

[Elica]

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)

[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.
_________
* binary, of course

[itistoday]

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

In another thread 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 all

(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 all

> (delay (+ 1 1)) 
(lambda () (+-memo 1 1))

Here are the two versions of memoize:

Code: Select all

(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 all

> (time (odd-fibs 50))
16
> (time (odd-fibs 50))
2

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

Code: Select all

> (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 all

(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 all

> (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 all

> (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

[itistoday]

Playing around some more with this I discovered something interesting.

Code: Select all

> (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 all

(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:



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



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:



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 all

(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).



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

[Elica]

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?

[itistoday]

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

Putfile.com?

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.

[Elica]

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...

[Elica]

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

[Elica]

SIMPLE SEQUENCES

Constant sequence consist only a constant value.

Code: Select all

(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 all

(define (arithmetic next-el a)
  (seq a
    (arithmetic next-el (next-el a))))

Let's define multiples of 5 by the rule:

Code: Select all

(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 all

(define nat (arithmetic (lambda (n) (n + 1)) 1))

(shs (nat))
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

[Elica]

MAP SEQUENCES

General rule-based sequence generator:

Code: Select all

(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 all

(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 all

(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.

[Elica]

MORE EXAMPLES

Let's define the sequence of natural numbers in another way:

Code: Select all

(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 all

(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, ...

[Elica]

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 all

(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 all

(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

[Elica]

COLLATZ SEQUENCE

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

Code: Select all

(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 all

(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 all

(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 all

(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 all

(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, ...

[Elica]

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!

[Elica]

I tried:

Code: Select all

> (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 all

(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).

[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...?

[Elica]

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 all

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

[newBert]

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)

[itistoday]

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...

[itistoday]

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. :-)