Streams in newLISP

[Elica]

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

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

[Elica]

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

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

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


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

[Elica]

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

[itistoday]

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

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

[Elica]

...without tail-call recursion unfortunately.

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

[itistoday]

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

[newBert]

...without tail-call recursion unfortunately.

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

 This reminds me a passage from  http://www.newlisp.org/CodePatterns.html">"Code Patterns in newLISP": http://www.newlisp.org/CodePatterns.html#walking">Recursion or iteration?



In any case we can get through!

;)