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 ... 41
#16
newLISP in the real world / Re: Timing function problem
September 19, 2019, 03:01:08 PM
I upgraded my newLISP.  Still works fine.


Code Select
$ ./newlisp
newLISP v.10.7.5 64-bit on BSD IPv4/6 UTF-8 libffi, options: newlisp -h

> (define (merge lstA lstB op) (sort (append lstA lstB) op))
(lambda (lstA lstB op) (sort (append lstA lstB) op))
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
594.7329999999999
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
594.78
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
596.348
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
596.448
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
596.001
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
595.079
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
594.71
#17
newLISP in the real world / Re: Timing function problem
September 19, 2019, 12:06:52 PM
Quote from: "cameyo"@ralph.ronnquist:

I have tried your function (in a fresh REPL), but the result are the same:
Code Select
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
1842.392
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
2290.107
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
2831.184
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
2993.474
The time grow...

Not for me:
Code Select
$ newlisp
newLISP v.10.6.2 64-bit on BSD IPv4/6 UTF-8 libffi, options: newlisp -h

> (define (merge lstA lstB op) (sort (append lstA lstB) op))
(lambda (lstA lstB op) (sort (append lstA lstB) op))
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
578.678
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
578.9450000000001
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
580.067
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
583.557
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
583.6799999999999
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
582.287
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
581.162
> (time (merge (sequence 1 500) (sequence 1 200) <) 500)
582.919
#18
newLISP in the real world / Re: Timing function problem
September 18, 2019, 10:29:20 AM
P.S. Calling your merge function with smaller inputs doesn't cause a ramp up of timings.


Code Select
(setq C '(4 3 2))
(setq D '(8 5 3 1))
(time (merge C D >) 500)

Here's the REPL output as I continually press Ctrl-x Ctrl-e (newlisp-eval) with my cursor on the time call (in Emacs).


Code Select
> 2.712
> 2.777
> 2.682
> 2.69
> 2.648
> 2.658
> 2.677
> 2.645
> 2.651
> 2.633

Larger inputs will obviously get you a deeper call stack as you "fake" iterate down the input lists.  So, the answer is probably somewhere there.
#19
newLISP in the real world / Re: Timing function problem
September 18, 2019, 10:17:24 AM
Yeah, I don't know precisely what's causing that, but when you use a loop (instead of an iterative recursive call), this problem goes away.


Code Select
(define (merge-via-loop lstA lstB op)
  (let (out '())
    (until (or (null? lstA) (null? lstB))
      (push (if (op (first lstB) (first lstA))
                (pop lstB)
                (pop lstA))
            out -1))
    (extend out (if (null? lstA) lstB lstA))))
First of all, I wouldn't use recursive tail calls for iteration in newLISP, as it doesn't optimize these calls (i.e., convert them to loops in the eval mechanism).  Just use the loop constructs (while, for, etc.) for iteration.



Second, your non-idiomatic code has nonetheless uncovered an interesting behavior in newLISP.  I would think that the time timings should NOT be increasing, yet they are.  Very interesting.  Hopefully, somebody smarter than I on this will reply.  Thanks!
#20
newLISP in the real world / Re: what's wrong with the use of apply append
September 03, 2019, 11:03:15 AM
QuoteThe symbol 'var which is passed to "append" has been binded to "b", why is the evaluator not able to see it?

The short answer is: because the quote prevents it from getting evaluated, as in:


Code Select
> (setq var "b")
"b"
> 'var
var
> var
"b"
Here, the single quote character (preceding var) prevents var from being evaluated (to its current value).  Actually the expression 'var is shorthand for (quote var) and that *does* get evaluated -- it's just that the newLISP evaluator has a special rule for quote expressions: don't evaluate quote's argument, just return it exactly as it was given.


Code Select
> (quote var)
var
The newLISP evaluator is exposed to the user via the primitive eval; so, one could evaluate the above quote expression "manually" (although in general, it's not considered good practice).


Code Select
> (eval (quote var))
"b"
QuoteAnd is this a mechanism from "lisp" or from "newlisp"?

All the lisps that I know of have this same behavior.  For example, take a Scheme:


Code Select
$ guile
guile> (define val "b")
guile> 'val
val
guile> (quote val)
val
guile> val
"b"
guile> (string-append "a" val)
"ab"
guile> (apply string-append '("a" val))

Backtrace:
In standard input:
   6: 0* [apply #<primitive-procedure string-append> ("a" {val})]
In unknown file:
   ?: 1  [string-append]
   ?: 2* [string-append "a" {val}]

ERROR: In procedure string-append:
ERROR: Wrong type (expecting string): val
ABORT: (wrong-type-arg)

guile> (apply string-append (list "a" val))
"ab"
Emacs Lisp:


Code Select
*** Welcome to IELM ***  Type (describe-mode) for help.
ELISP> (setq val "b")
"b"
ELISP> 'val
val
ELISP> (quote val)
val
ELISP> val
"b"
ELISP> (concat "a" val)
"ab"
ELISP> (apply #'concat '("a" val))
*** Eval error ***  Wrong type argument: sequencep, val
ELISP> (apply #'concat (list "a" val))
"ab"
#21
newLISP in the real world / Re: what's wrong with the use of apply append
September 03, 2019, 02:49:16 AM
What we were missing was the error message:


Code Select
> (setq var "b")
"b"
> (apply append '("a" var)) ;; I believe the result will be "ab", but what I get is error message.

ERR: string expected in function append : 'var
The problem is that in the expression '("a" var), var is getting quoted; so, you end up passing a symbol as the second argument to append and hence it complains (in the error message) that var (a symbol) is not something that it can do anything with.



(The subtle thing to notice at the end of the error message is the single quote character right before "var".)



Another way, the expression '("a" var) is a list of a string and a symbol:


Code Select
> '("a" var)
("a" var)
> (list '"a" 'var)
("a" var)
So, by substitution, these are equivalent:


Code Select
> (apply append '("a" var))

ERR: string expected in function append : 'var
> (apply append (list '"a" 'var))

ERR: string expected in function append : 'var
On the other hand, in the case of the expression (append "a" var), the evaluator gets a chance to evaluate var (an unquoted symbol) to its current runtime value ("b").



So, to answer your last question, something like this would work:


Code Select
> (apply append (list "a" var))
"ab"
Hope that helps.
#22
newLISP in the real world / Re: Create polynomials
August 27, 2019, 05:43:23 PM
Here's a version of the lambda builder that constructs the body according to the https://en.wikipedia.org/wiki/Horner%27s_method">method of Horner.


Code Select
(define (make-poly-horner coeffs)
  (push (if (< (length coeffs) 2)
            (first coeffs)
          (apply (fn (acc c)
                   (list 'add c (cons 'mul (list 'x acc))))
                 coeffs
                 2))
        (copy '(fn (x)))
        -1))
To give you an idea of what this looks like:


Code Select
> (make-poly-horner (list 3 2 1))
(lambda (x) (add 1 (mul x (add 2 (mul x 3)))))
#23
newLISP in the real world / Re: Pathological floating point problems
July 13, 2019, 02:04:47 PM
That's very cool.  And a good thing to keep in mind when doing computer arithmetic.



But, your code could be much shorter -- it would then be more readable to others (and to you, months or years later :).


Code Select
(define (rat n d)
  (let (g (gcd n d))
    (map (curry * 1L)
         (list (/ n g) (/ d g)))))

(define (+rat r1 r2)
  (rat (+ (* (r1 0) (r2 1))
          (* (r2 0) (r1 1)))
       (* (r1 1) (r2 1))))

(define (-rat r1 r2)
  (rat (- (* (r1 0) (r2 1))
          (* (r2 0) (r1 1)))
       (* (r1 1) (r2 1))))

(define (*rat r1 r2)
  (rat (* (r1 0) (r2 0))
       (* (r1 1) (r2 1))))

(define (/rat r1 r2)
  (rat (* (r1 0) (r2 1))
       (* (r1 1) (r2 0))))

(define (bank)
  (letn (e (rat 106246577894593683L
                39085931702241241L)
         balance (-rat e (rat 1 1)))
    (for (i 1 25)
      (setq balance (-rat (*rat balance (rat i 1))
                          (rat 1 1)))
      (println i { } balance { }
               (div (first balance)
                    (last balance))))
    balance))
#24
Whither newLISP? / Re: pseudo-random number generator
July 13, 2019, 11:00:26 AM
I'm not an expert at PRNGs, but here is the implementation in newlisp.



https://github.com/kosh04/newlisp/blob/develop/nl-math.c#L1709-L1764">https://github.com/kosh04/newlisp/blob/ ... 1709-L1764">https://github.com/kosh04/newlisp/blob/develop/nl-math.c#L1709-L1764
#25
newLISP in the real world / Re: Sum of digits
June 03, 2019, 03:35:21 AM
Getta via il 9.  :)  https://en.wikipedia.org/wiki/Casting_out_nines">https://en.wikipedia.org/wiki/Casting_out_nines
#26
newLISP newS / Re: newLISP language support for Visual Studio Code
June 01, 2019, 04:37:44 PM
Nice!



I would collab but I don't use VS Code (nor linux, nor windows, nor mac). :)



(However, I just sent a PR on your other gh project.)  Best, --Rick
#27
newLISP in the real world / Re: Maximum Product Sublist
May 30, 2019, 02:18:03 PM
Quote from: "cameyo"Hi rickyboy

Hi cameyo! :)


Quote from: "cameyo"the sublist must contains only contiguous elements.

But your functions are useful anyway :-)

Ah, ok!  Then my updated maxProd function is still very similar to my original.


Code Select
(define (maxProd lst)
  ;; lst must contain integers; note use of integer op `*`.
  (apply max
         (map (fn (prods) (apply * prods))
              (sublists lst))))
The difference is that the expression (remove '() (powerset lst)) is now replaced by the expression (sublists lst), which generates a list of the sublists (contiguous) of lst.



And this indeed yields the same results as your function does.


Code Select
> (maxProd '(6 -3 -10 0 2))
180
> (maxProd '(-1 -3 -10 0 60))
60
> (maxProd '(-2 -3 0 -2 -40))
80
> (maxProd '(-1 -2 -3))
6
> (maxProd '(0 -1))
0
> (maxProd '(0 0 0 0))
0
I leave the definition of sublists is a reader exercise.  This is how I get to "leave fun on the table," as Ralph did earlier. :)
#28
newLISP in the real world / Re: Maximum Product Sublist
May 30, 2019, 11:57:08 AM
Here's my version.


Code Select
(define (maxProd lst)
  ;; lst must contain integers; note use of integer op `*`.
  (apply max
         (map (fn (prods) (apply * prods))
              (remove '() (powerset lst)))))
You'll need these functions.


Code Select
(define (mappend) (apply append (apply map (args))))
(define (powerset s)
  (if s
      (mappend (fn (x) (list (cons (s 0) x) x))
               (powerset (1 s)))
      '(())))
However, my code gets different answers for your inputs, so maybe I don't understand the problem statement.


Code Select
> (maxProd '(6 -3 -10 0 2))
360   ; i.e., (* 6 -3 -10 2)
> (maxProd '(-1 -3 -10 0 60))
1800   ; i.e., (* -3 -10 60)
> (maxProd '(-2 -3 0 -2 -40))
480   ; i.e., (* -2 -3 -2 -40)
> (maxProd '(-1 -2 -3))
6
> (maxProd '(0 -1))
0
> (maxProd '(0 0 0 0))
0
#29
newLISP in the real world / Re: Group the elements of a list
May 30, 2019, 11:08:36 AM
While I was exploring all the code, I believe that I found a bug.



The following identity should hold: the reachability of the transitive closure of input is the same as the reachability of input.


Code Select
>
(set-equal? (reachability input)
            (reachability (transD input)))

nil
Hmmm.  What's going on?


Code Select
> (reachability (transD input))
((0 5) (1) (3 15 8 8) (4 13 1 1 12) (5) (7 5)
 (8) (9 19 4 13 1 1 12 13 1 1 12) (11 0 5 5)
 (12) (13 1) (15 8) (19))
Ok, looks like some of the reaches don't have unique elements.  Here's one in particular.


Code Select
> (reach (transD input) 9)
(9 19 4 13 1 1 12 13 1 1 12)
Looks like we need a unique in the reach function.


Code Select
(define (reach s n (f (fn (x) (= n (x 0)))))
  (cons n (if s (unique (flat (map (curry reach (clean f s))
                                   (map (curry nth 1) (filter f s))))))))
Now, it works.


Code Select
> (reach (transD input) 9)
(9 19 4 13 1 12)
And the identity in fact holds, as expected.


Code Select
>
(set-equal? (reachability input)
            (reachability (transD input)))

true
#30
newLISP in the real world / Re: Group the elements of a list
May 30, 2019, 10:42:52 AM
Quote from: "ralph.ronnquist"Then, how do you go the other way? I.e. how do you reduce into the smallest number of pairs, or at least find a sub list so that implied relationships are omitted from the list?

Well, I perceive that you know the answer already, so I thank you for letting us share in the fun. :)



Here is a function untransD which removes the implied relationships.  It does so by considering each edge edge in s which can be viewed as the pair (src dst) (although dst is not needed here).  The clean fn answers the question "Is edge implied?"  That will be true when the reach of src, after we remove edge from s, is the same is the reach of src under s.


Code Select
(define (untransD s)
  (clean (fn (edge)
           (let (src (edge 0)
                 remove (fn () (apply replace (args))))
             (= (reach s src)
                (reach (remove edge s) src))))
         s))
Aside. For people not familiar with newLISP, note the remove function (defined in the let bindings).  It appears as if it is only doing what the intrinsic replace does; so, why not just say (replace edge s) instead of (remove edge s)?  The reason for not doing that is subtle.  The  replace primitive is destructive, and we don't want s to change during the runtime of untransD.  Defining remove as we've done here turns it into a non-destructive removal function (because of the calling model of newLISP: a copy gets passed the a function, not a reference).



But perhaps from a (software engineering) contracts point-of-view, we shouldn't rely on the order of the outputs of the reach calls (i.e., its stability).  Even though we can see the code of reach, we can also "play it safe" by assuming that we cannot see the implementation and thus replace the usage of = with the usage of another equality predicate where the order doesn't matter.  There may be a better way to do this, but here's one.


Code Select
(define (set-equal? A B)
  (= (sort A) (sort B)))
The primitive sort is also destructive; however, we don't need A and B (which are copies themselves) for anything else in the scope of this function (after we are done "smashing" them :).  Happily, we can reuse set-equal? in our testing.



First, let's recall what running transD on the example input (input) does.


Code Select
> input
((13 1) (9 19) (4 13) (4 12) (15 8) (3 15) (7 5)
 (9 4) (11 0) (0 5))
> (transD input)
((0 5) (3 15) (3 8) (4 13) (4 1) (4 12) (7 5)
 (9 19) (9 4) (9 13) (9 1) (9 12) (11 0)
 (11 5) (13 1) (15 8))
Now, let's see untransD in action.


Code Select
> (untransD (transD input))
((0 5) (3 15) (4 13) (4 12) (7 5) (9 19) (9 4)
 (11 0) (13 1) (15 8))
Well, the order is different, but it sorta looks a lot like input (by "eyeballing" it).  So, how can we test this a little better?  It seems that we should be able to say that transD and untransD are inverses of each other.  Let's try that.



First, note that the example input itself is devoid of implied relationships.


Code Select
> (set-equal? input (untransD input))
true
That means the following identity should hold.


Code Select
> (set-equal? input (untransD (transD input)))
true

Quote from: "ralph.ronnquist"newlisp is fun :)

Indeed! :)
Pages 1 2 3 4 ... 41