Menu

Show posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Show posts Menu

Messages - rickyboy

Pages 1 2 3 4 5 ... 41
#31
newLISP in the real world / Re: Group the elements of a list
May 29, 2019, 04:29:26 PM
Quote from: "ralph.ronnquist"A recursive solution could be something like this:
Code Select
(define (trans s (x s) (f (and s (curry intersect (first s)))))
  (if s (trans (rest s) (cons (unique (flat (filter f x))) (clean f x))) x))
Perhaps there is something faster.

Looks good, Ralph!  I don't think I could do it faster.  I prefer your code anyway because it's understandable.



This is what I see.  The input s is a list of sets where each member set relates each of its members to one another.  For instance, if one of the members of s is (1 2 3) each of 1, 2 and 3 are related to any other.  In math terms, if the input s describes a (symmetric) relation R, then it is the case that 1R2, 2R1, 1R3, 3R1, 2R3 and 3R2 are all true.



So, for instance, the first member of your example input (13 1) implies both 13R1 and 1R13 (when example input describes R).  This is because, I don't see the input to trans as any different kind of "stuff" as its eventual output -- they are both relation "descriptions" -- except that the output is guaranteed to describe a transitive relation.



Now, when looking at the input set instead as a set of "links" of a graph (as you described them), then your function trans has to be assuming that all the "links" it finds in the input are bi-directional, or in other words, the "links" describe non-directed edges.  Here I note that this assumption does not go unmentioned in your posting, because your posting said "join all sub-lists that share some element (transitively)" which to me says "the links are non-directed edges."  Just an observation in case someone else didn't catch that.



The recursive step of trans conses the partial transitive relation descriptor member (set) containing link (first s) (by absorption/subsumption), namely (unique (flat (filter f acc))), to the subset of partial transitive relation descriptor members in x which are mutually exclusive to link (first s), namely (clean f acc). (Whew! <wipes-brow/>)



When I use your trans to compute transitive closures in the future, I will pair it with something like the following which generates a predicate for it.


Code Select
(define (make-symmetric-relation S)
  (letex ([S] S)
    (fn (x y)
      (exists (fn (s) (and (member x s) (member y s)))
              '[S]))))
Here's a terrible test that shows it in action.


Code Select
(define (test-trans input x y)
  (let (R     (make-symmetric-relation input)
        Rt    (make-symmetric-relation (trans input))
        yesno (fn (x) (if x 'yes 'no)))
    (list ;; is (x,y) in the original relation?
          (yesno (R x y))
          ;; is (x,y) in the transitive closure?
          (yesno (Rt x y)))))
For instance, (8 15) is in the original relation; so, it will also be in the transitive closure.  (9 13) is not in the original relation, but it is in the transitive closure. (9 15) is in neither.


Code Select
> (define input
    '((13 1) (9 19) (4 13) (4 12) (15 8) (3 15) (7 5) (9 4) (11 0) (0 5)))
> (test-trans input 8 15)
(yes yes)
> (test-trans input 9 13)
(no yes)
> (test-trans input 9 15)
(no no)
Thanks again!  Your function is now added to my quiver! :)
#32
newLISP in the real world / Re: Group the elements of a list
May 28, 2019, 12:02:55 PM
Right on, fdb!  Lutz wins this round! :)
#33
newLISP in the real world / Re: Nesting level of a list
May 27, 2019, 04:26:18 PM
Excellent, fdb!  Faster than mine by about a factor of 3 (on the sample input)! 2.5 times faster than the original.
#34
newLISP in the real world / Re: Nesting level of a list
May 27, 2019, 07:52:03 AM
Here's another way to do it.


Code Select
(define (nesting lst)
  (if (null? lst) 0
      (atom? lst) 0
      (+ 1 (apply max (map nesting lst)))))

You be the judge if it's "better".  Beware though that, although the code length is shorter, timing tests show that it is slightly *slower* than the original.  map has to create more cells, so the slowdown is probably due to that -- which also means increased space overhead!  So, maybe you should stick with the original. :)
#35
newLISP and the O.S. / Re: Compile script to .exe with attached files
May 13, 2019, 05:18:03 AM
Quote from: "HPW"Hello,



Just one question: Can't you combine your 3 lsp files into one?

That would be the easiest way.



Regards

Good point, HPW.



On another note, I am glad that Ralph posted his scripts which turn loads and file reads ("dynamic inclusion") into "includes" ("static inclusion"), but only for the files the user indicates during the build invocation. This allows for other files, such as application configuration files, to be included dynamically. Clever!
#36
newLISP in the real world / Re: slice with negative "int-length"
April 24, 2019, 01:56:46 PM
Ah, I see what you did -- you put in the runtime checks on the bounds of the argument values.  Very nice!



I'd suggest commenting it a bit.  I do this in my own code when I believe there is a chance that it will take me more than 5 seconds to re-parse and understand it when I return to read it in the future -- and I have noticed that my future self always thanks my past self for doing it! :D


Code Select
(define (myslice xs idx (len (if (< idx 0)
                                 (- idx)
                                 (- (length xs) idx))))
  (if ;; 1. For degenerate `idx` cases, return "empty", rather than
      ;; signalling an exception.
      (or (>= idx (length xs))
          (< idx (- (length xs))))
      (if (list? xs)   '()
          (string? xs) "")
      ;; 2. Normal `idx` cases
      (let (;; ensure `idx` is in positive form, before we proceed
            ;; further.
            idx (if (>= idx 0)
                    idx
                    (+ idx (length xs))))
        (if (< len 0)
            (slice xs
                   ;; ensure that the index argument is not out of
                   ;; bounds.
                   (let (new-idx (+ 1 idx len))
                     (if (>= new-idx 0) new-idx 0))
                   ;; ensure that the length argument is not out of
                   ;; bounds.
                   (let (abs-len (abs len))
                     (if (<= abs-len (+ 1 idx)) abs-len (+ 1 idx))))
            (slice xs idx len)))))
#37
newLISP in the real world / Re: slice with negative "int-length"
April 23, 2019, 07:09:31 AM
We might want to add one more thing.  Notice that we can omit the length argument in slice.


Code Select
> (slice '(0 1 2 3 4 5) 3)
(3 4 5)
> (slice '(0 1 2 3 4 5) -3)
(3 4 5)

But not so with our version of myslice (from the previous post).


Code Select
> (myslice '(0 1 2 3 4 5) 3)

ERR: value expected in function + : len
called from user function myslice

But that's just a small fix away.


Code Select
(define (myslice xs idx (len (if (< idx 0)
                                 (- idx)
                                 (- (length xs) idx))))
  (if (< len 0)
      (slice xs (+ 1 idx len) (abs len))
      (slice xs idx len)))

Check:


Code Select
> (myslice '(0 1 2 3 4 5) 3)
(3 4 5)
> (myslice '(0 1 2 3 4 5) -3)
(3 4 5)

Now, let's regression test the negative length code (which is what you were really after) to convince ourselves that this fix didn't break that part of the code.


Code Select
> (myslice '(0 1 2 3 4 5) 2 -2)
(1 2)
> (myslice '(0 1 2 3 4 5) 4 -3)
(2 3 4)
> (myslice '(0 1 2 3 4 5) 4 -1)
(4)
> (myslice "newLISP" 4 -2)
"LI"

Seems to be OK.
#38
newLISP in the real world / Re: slice with negative "int-length"
April 23, 2019, 06:24:33 AM
Maybe it would have been better if the manual had said instead: "If int-length is negative, slice will take the parameter as offset counting from the end and copy up to but not including that offset."



As far as the answer to your second question, I believe that all you need to do is transform the index and length arguments, when the length argument is negative.


Code Select
(define (myslice xs idx len)
  (if (< len 0)
      (slice xs (+ 1 idx len) (abs len))
      (slice xs idx len)))

Here's another version with implicit slicing.  It's supposed to be faster, but arguably less readable.


Code Select
(define (myslice xs idx len)
  (if (< len 0)
      ((+ 1 idx len) (abs len) xs)
      (idx len xs)))

Beware, though, when your calling code exceeds the ends of the string or list argument -- sometimes you get errors, other times it wraps.


Code Select
> (myslice "newLISP" 4 -6)
"P"
> (myslice "newLISP" 4 -7)
"SP"
> (myslice "newLISP" 4 -75)

ERR: invalid string index
called from user function myslice

Of course, you can add checks for these conditions to myslice, if you want.
#39
newLISP in the real world / Re: libtls for TLS in newLISP
April 20, 2019, 01:16:34 PM
Quote from: "Kirill"Happy Easter!

With a name like Kirill, surely you know that Easter (Pascha) is really next week. ;)  Христос воскресе!
#40
newLISP in the real world / Re: Are '(true nil) and '(true) is equal?
April 10, 2019, 06:16:58 PM
Another way to exhibit the problem:


Code Select
> (= '(1 2 3 nil nil) '(1 2 3))
true
> (= '(1 2 3 nil nil nil) '(1 2 3))
true
> (= '(1 2 3 nil nil nil nil) '(1 2 3))
true
> ;; and so on ...

In nl-math.c, when the evaluation of any of the above expressions gets to `compareLists()` and `left` has the `nilSymbol`. `right` has the `nilCell` (because it's "bottomed out" already).  Then when `compareCells(left, right)` is called, it happily reports "equal!" because `isNil(left)` (nl-math.c:1034) and `isNil(right)` (nl-math.c:1036) are both true.  This is because, the `isNil()` macro doesn't distinguish between `nilSymbol` ("nil") and `nilCell` (the "end of a list" marker):


Code Select
newlisp.h:450:#define isNil(A) ((A)->type == CELL_NIL || ((A)->type == CELL_SYMBOL && (A)->contents == (UINT)nilSymbol))
Lutz, all the best fixing this, because I know you don't want the fix to break the behavior of the other comparison operators.
#41
newLISP in the real world / Re: Are '(true nil) and '(true) is equal?
April 10, 2019, 04:45:54 PM
Looks like a bug to me.  At the very least, I believe that it should be a desirable property for the `=` operator to act as a symmetric relation, that is, that `(= a b)` and `(= b a)` return the same boolean value (for any `a` and `b`).



More fundamentally, the manual says that for all the relational operators: "List expressions can also be compared (list elements are compared recursively)."  Your example of `(= '(true nil) '(true))` evaluating to `true` contradicts that assertion.



Nice find, BTW!
#42
newLISP newS / Re: Development release newLISP v.10.7.4
March 30, 2019, 11:01:14 AM
Thanks, Lutz!  And thanks to Kirill for finding this!
#43
newLISP and the O.S. / Re: Newlisp-Apache-CGI Issues Again
March 29, 2019, 07:50:05 PM
Good catch, Ralph. I read that message wrong (but yet there is the response header name, right there between the two single quotes).  Didn't help that duke's OP didn't have the entire message there to begin with. Kinda faked me out. dukester! lol ;)
#44
newLISP newS / Re: Development release newLISP v.10.7.4
March 29, 2019, 04:14:47 PM
Kirill, I get the same:


Code Select
$ uname -rsm
FreeBSD 12.0-RELEASE amd64
$ fetch http://www.newlisp.org/downloads/development/SHA1.txt
$ fetch http://www.newlisp.org/downloads/development/newlisp-10.7.4.tgz
$ cat SHA1.txt; sha1 newlisp-10.7.4.tgz
SHA1(newlisp-10.7.4.tgz)= 5a3ce129f43138773abdc479a03512699e8a4256
SHA1 (newlisp-10.7.4.tgz) = 7b4e1f84d878a101dbe761fdd68bbfafe819e9f9
#45
newLISP and the O.S. / Re: Newlisp-Apache-CGI Issues Again
March 29, 2019, 04:09:43 PM
duke, I wasn't saying for Lutz to look at it, but for *you* to look at it.  lol!



No worries, I get it.  I've been there many times.  We do indeed have to make that determination: whether to spelunk or not.  :) Sometimes, it's not worth it, especially when we have time constraints.  I hope you get some time here and there to mess around with it ... and succeed!



All the best! rickyboy
Pages 1 2 3 4 5 ... 41