Re: Learning Lisp

[Enrique Sánchez]

thanks for the link, Jimmie.

Enrique.

Re: Fixed-point scaling and lookup tables

[Enrique Sánchez]

Hi Lindsay,

yes, Picolisp has been a great tool for me as well to explore algorithms
and datastructures.

You used the high level implementation of fastNth (took around 15 seconds)
instead of the
low level implementation (it took 3 seconds).

In fact, taken both implementations in isolation (without all that high
level code inside the loop), the low level implementation is 30 times
faster than the high level one on average.

The idx mechanism is a perfect implementation of associative array
functionality when the set of keys is a set of arbitrary strings.
But what happens when the set of keys is a more restricted set like a
sequence of numbers? That is a common scenario and I have seen people
implement that using idx, because Picolisp readily offers that solution.

I think that the Digital Search Tree structure (dst) is the perfect
solution for such a restricted set of keys (array functionality), perfect
in terms of memory space (keys are implicit, not stored), in terms of
execution time (no need to compare keys), and in terms of not needing to
change picolisp internally in order to implement arrays.

A dst complements idx, it does not substitute it.

Here is the code needed to compile the low level implementation of fastNth:

(load "@lib/gcc.l")
(gcc "fast" NIL 'fastNth)

any fastNth(any ex) {
   any x = cdr(ex);
   int n = (unDig(EVAL(cadr(x)))>>1) - 1;
   x = EVAL(car(x));
   NeedVar(ex,x);

   int i;
   int A = 7 & n;
   int B = 7 & (n >>= 3);
   int C = 7 & (n >>= 3);
   int D = 7 & (n >>= 3);
   int E = 7 & (n >>= 3);
   int F = 7 & (n >>= 3);
   int G = (n >> 3);

   for (i = 0; i < G; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < F; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < E; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < D; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < C; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < B; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < A; ++i) x = cdr(x);
   return x;
}
/**/

the /**/ is an end-delimiter.

Enrique.

Re: Fixed-point scaling and lookup tables

[Enrique Sánchez]

For a much faster solution than the idx mechanism, look at this:

http://www.mail-archive.com/picolisp@software-lab.de/msg05199.html

It would be nice if Picolisp had this generic fastNth function,
in order to solve this kind of lookup accesses.

Enrique.

Re: the hash function

[Enrique Sánchez]

 initSeed() should be improved, by doing more than simply adding up the
 32-bit or 64-bit digits, at least in case of symbols. Any proposals?

I discovered these collisions while comparing the picolisp hash function
with the djb2 string hash function, that didn't have that problem.
May be a solution could be to use the djb2 hash function:

(de djb2 (S)
   (let A 5381
  (for C (chop S)
 (setq A ( 65535 (+ (* 33 A) (char C ) ) )



-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

the hash function

[Enrique Sánchez]

Hello,

I found some strange behaviour in the hash function.

When applied to numbers, it works ok, but when applied
to strings, it leads to a huge number of collisions. 

An example:
# ==

(setq N 5
  Lnumbers (range 1 N)
  Lstrings (mapcar format (range 1 N)) )

(prinl uniq hashed values, using  N  different numbers: 
   (length (uniq (mapcar hash Lnumbers))) )

(prinl uniq hashed values, using  N  different strings: 
   (length (uniq (mapcar hash Lstrings))) )

(bye)

# ==
# PRINTED RESULTS:
# 
# uniq hashed values, using 5 different numbers: 5
# uniq hashed values, using 5 different strings: 10271
# ==

enrique.




-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Re: A system to access very large lists by index

[Enrique Sánchez]

 Alternatively, you might consider putting it inline into the Lisp source
 
(load @lib/gcc.l)
 
(gcc fast NIL 'fastNth)
 
any fastNth(any ex) {
   any x = cdr(ex);
   ...
}
/**/

thank you, I will try that.

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

A system to access very large lists by index

[Enrique Sánchez]

This is a system to access very large lists by index.

First of all, let me say, that the idea for this started
in another thread some days ago. There, I proposed another
idea, with the same goal.

I have to say that overall, Alex, you were right. I insisted
too much, defending that system.

It is my opinion, that the biggest objection, was the need
to make use of C heap space outside of the regular picolisp
cell pool.

Now, here is exposed, another system for the same goal.


HELPER LIST
---
We need a helper function to build an index list from the
large original list:

(de leap (L)
   (make (for (P L P (nth P 9)) (link P))) )

(de helper (L)
   (leap(leap(leap(leap(leap(leap L)) )

We initialize the original list, and build the helper list:

(setq A (need 200 0) # two million elements list
  B (helper A) )

At my computer, the helper function takes 0.050 seconds to
index this 2 million elements list. It would take 0.003 seconds
to index an 5 elements list, for reference.


fastNth PRIMITIVE
-
We now define a new primitive function, in order to traverse
the helper list. (I have added it to the /src/subr.c file of
the picolisp source code).

any doFastNth(any ex) {
any x = cdr(ex);
int n = (unDig(EVAL(cadr(x)))1) - 1;
x = EVAL(car(x));
NeedVar(ex,x);

int i;
int A = 7  n;
int B = 7  (n = 3);
int C = 7  (n = 3);
int D = 7  (n = 3);
int E = 7  (n = 3);
int F = 7  (n = 3);
int G = (n  3);

for (i = 0; i  G; ++i) x = cdr(x); x = car(x);
for (i = 0; i  F; ++i) x = cdr(x); x = car(x);
for (i = 0; i  E; ++i) x = cdr(x); x = car(x);
for (i = 0; i  D; ++i) x = cdr(x); x = car(x);
for (i = 0; i  C; ++i) x = cdr(x); x = car(x);
for (i = 0; i  B; ++i) x = cdr(x); x = car(x);
for (i = 0; i  A; ++i) x = cdr(x);

return x;
}

(*) I had to add as well this line to /src/pico.h:
   any doFastNth(any);

(*) And this line to /src/tab.c:
   {doFastNth, fastNth},


PICOLISP EQUIVALENT FUNCTION

(de fastNth (L N)
   (dec 'N)  # convert 1-offset convention to 0-offset
   (let  (A ( 7 N)
  B ( 7 (setq N ( 3 N)))
  C ( 7 (setq N ( 3 N)))
  D ( 7 (setq N ( 3 N)))
  E ( 7 (setq N ( 3 N)))
  F ( 7 (setq N ( 3 N)))
  G ( 3 N) )
  (nth L (inc G) (inc F) (inc E) (inc D) (inc C) (inc B) (inc A)) ) )


TIMING FUNCTIONS:
-
We now define the timing functions:

(de access (N) # a million times nth execution to the N nth-element
   (do 10
  (nth A N) (nth A N) (nth A N) (nth A N) (nth A N)
  (nth A N) (nth A N) (nth A N) (nth A N) (nth A N) )
T )

(de access-fast (N) # a million times fastNth execution to the N nth-element
   (do 10
  (fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N)
  (fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N) )
T )

Results:
(access 1) =  0.081 seconds - Time Reference!
(access-fast 1)   = 0.081 seconds,  same time
(access-fast 10)  = 0.085 seconds,  1.05 times slower
(access-fast 100) = 0.095 seconds,  1.17 times slower
(access-fast 1000)= 0.115 seconds,  1.42 times slower
(access-fast 1)   = 0.118 seconds,  1.47 times slower
(access-fast 10)  = 0.124 seconds,  1.53 times slower
(access-fast 100) = 0.139 seconds,  1.71 times slower
(access-fast 200) = 0.139 seconds,  1.71 times slower


RESULTS
---
On average, the fastNth accessor, coded in C, is only 1.5 times slower
than a pure array C implementation. The helper list is always 1/7th
the size of the original large list.

This system makes the access to very large lists by index a reality,
the only thing required is a new fastNth primitive function.

It is my opinion, that a little primitive like this, is worthwhile to
have in the picolisp toolbox.

The Picolisp equivalent function showed, is on average 45 times slower
than a pure array C implementation. 

Best Regards
Enrique.

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Re: A pragmatic solution to using arrays in picolisp

[Enrique Sánchez]

I've changed my mind.

If we have a linear list for which we need fast access, we can do
another thing:  Instead of substituting the list with an array
structure, we can keep the list and use an array as a helper of the
original list.

That means that instead of storing the elements of a linear list in
the buckets of the array and getting rid of the list, we can store
the cdr's of the list and keep the list.

So we can get rid of the 'get: and 'set: functions, that are very
rigid, and break the Lisp programming style, as you said, and have only
a 'nth: accessor.

This has two advantages:

1. First (the big advantage) is that we retain all the usual list
functions at our disposal, restoring Lisp programming style.

2. The patch to the garbage collector gets simpler:

for (int i=1; i=current; i++) # loop thru each array
   if (void **p=arrays[i]) # only if array hasn't been disposed of
   markAll(p[1]); # we only need to traverse the first bucket

--
So, recapitulating we would have only 3 functions:

(setq *Ram (array (need 131072 0)))
(nth: *Ram 5)
(dispose *Ram)

This use of arrays as helpers associated with some lists, instead of
substitutes of lists, makes arrays even more segregated from the core
of the language. I think that makes them more acceptable.


-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Re: A pragmatic solution to using arrays in picolisp

[Enrique Sánchez]

On 2015-02-15 02:29, Alex Gilding wrote:
 One cheap workaround for this would simply be to have a nogc function that
 temporarily disables the GC around a piece of code. If you're crunching data 
 in
 arrays, you probably want to isolate that operation in its own little
 high-performance block anyway.

I would add some code to the garbage collector, 
in order to keep the array items protected.

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Re: A pragmatic solution to using arrays in picolisp

[Enrique Sánchez]

 thanks for your ideas and elaborations!   


 
thank you for having created picolisp

 Personally, I must say that I am against using arrays
 in PicoLisp, and wrote it up a few years ago in:  
 
   
  
   http://picolisp.com/wiki/?arrayAbstinence

Yes, I have read it. I agree more or less with it.

 Can you give me an example where you need a list with 65536 elements, in  

 a Lisp program? Normally you would use some kind of tree to maintain  

 larger data structures, and you example of using helper list does 

 exactly that. 


If I had a 65536 elements array at my disposal, the first thing I
would do is to couple it to the cute 'hash picolisp function (whose
output is 1..65536) in order to have very good hash tables. (I could
use binary trees instead, hash tables are simpler and a little faster,
binary trees are more powerful).

If one is interested in building virtual machines in picolisp, I think
that one needs arrays, to emulate flat memory above all, but as well
to execute the machine instructions efficiently by table dispatching.

   

 Besides this, technically your implementation looks good. 

 
 It breaks the Lisp programming style though. You can't use the rich set   

 of list-manipulation functions on arrays. To do anything interesting, 

 you have to either fetch the whole array (or parts of it) into a list,

 or operate one by one by accessing individual elements. Very tedious.

I use lists for most tasks, as usual, it's only at very selected
places that I would reach for an array for random access.

 You have to take care of garbage collecting these arrays by yourself, 

 i.e. to know when a given array is no longer needed. and this 

 inconvenience alone destroys the possible advantage of an array.  


Given a function markAll(CELL*) that marks all cons-cells reachable
from a given cell, we can just insert the following code in the
garbage collector marking phase, so that the contents of all arrays
can be protected from being sweeped.

for (int i=1; i=current; i++) # thru each array
   if (void **p=arrays[i]) # only if array hasn't been disposed of
  for (int j=1; j=size(p); j++) # thru each bucket
 markAll(p[j]);

These 4 lines of code (plus the creation and disposing code) are the
price to pay (I think) for having arrays in picolisp.


Enrique.

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

A pragmatic solution to using arrays in picolisp

[Enrique Sánchez]

1) A pragmatic solution
2) Some timing results and a workaround


1) A PRAGMATIC SOLUTION
---
Is there a price to be paid for having arrays in the language?

Well, if the picolisp machine has to be changed, in order to support
another data type, more tag bits, then I would say that is a big price
to be paid.

But an array doesn't necessarily need to be another data type.

An array can be used in the same way as file handles are used in
operating systems, with no need to change the picolisp machine.

Examples of array definition:

(setq *Ram (array 65536))
(setq *Rom (array 65536))
(setq *Per (array (permute (range 1 65536

afterwards - *Ram= 1, *Rom= 2, *Per= 3

The function 'array takes one parameter
   a number,
   or an already built list.

In general, things like (setq A (array N)) would trigger something
like this in C:

int current;
arrays[++current] = malloc(N * (sizeof CELL*));
return makeNUMBER(current);

Arrays would be internally arrays of pointers to CELLS,
and externally just an integer handle.

So we could use arrays thru 4 functions:

(setq *Ram (array 65536))
(get: *Ram 5)
(set: *Ram 5 (33 52 8 91))
(dispose *Ram)

NOTES:
1) The function 'array could possibly return the memory pointer of the
newly allocated array instead of the integer handle, for speed.

2) I suppose that the garbage collector would have to keep track of
all those CELL pointers in the array, that are outside of the reach of
the picolisp symbol table. That would be the price to pay, I think
a smaller price than adding another datatype.

3) The array, as defined here, would not be addressable as a
whole, as a structure, because it's physically outside of the main
cell heap. But the elements could be manipulated individually thru
'get: and 'set: , and that is the main purpose of arrays.



2) SOME TIMING RESULTS AND A WORKAROUND
---

(setq A (need 65536)) # big array as list

(de normalAccess (N)  # 5 accesses to the N nth-element
   (do 5000
  (nth A N) (nth A N) (nth A N) (nth A N) (nth A N)
  (nth A N) (nth A N) (nth A N) (nth A N) (nth A N) ) )

(bench (normalAccess 1))  gives 0.007 seconds
(bench (normalAccess 100))  gives 0.020 seconds (2.85 times slower)
(bench (normalAccess 5))  gives 9.100 seconds (1300 times slower)


This is a workaround using a helper list to traverse a big list:

# Diagram of a 64k list and its helper index list:
#A  =  (0 ... 256 ... 512 ... 768 ... 65535) --- original list
#   | |   |   |
#AA =  (0 1   2   3 ... 255) --- index list

(de index256 (L)
   (make
  (for (P L P (nth P 257))
 (link P) ) ) )

(de nth256 (L N)
   (nth L
  (inc (/ N 256))
  (inc ( 255 N)) ) )

(setq A (need 65536)) # original list
(setq AA (index256 A)) # index list

(de indexedAccess (N)  # 5 accesses to the N nth-element
   (do 5000
  (nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N)
  (nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N) )

(bench (indexedAccess 5))  gives 0.140 seconds (20 times slower)

So we have converted a 1300-times-slower access into a 20-times-slower
access.






-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Re: stdin and (key)

[Enrique Sánchez]

Hi,

 I released a new version, with an improved 'ctty'. Now the standard I/O
 channels are better initialized: 'ctty' checks the console parameters,
 and properly clears the buffers, so that reading from standard input
 (both raw or cooked) should work.

This is awesome!
Thank you, now it works flawlessly!

Is there a way to know whether a script is called inside a pipe or not?
example: (if (insidePipe?) (yes!) (no!))

Regards,
Enrique.

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Re: stdin and (key)

[Enrique Sánchez]

(call test -t 0)

thanks Alex,
now one can make a pager like the unix 'more' utility in Picolisp. Reading
the text from stdin and reading the keyboard to move around the text.

Enrique.
-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

stdin and (key)

[Enrique Sánchez]

Dear list,

I am writing a script that reads stdin and uses the function
(key). But when I call it like:
$ cat file.txt |script.l
(key) does not wait for a keypress.
How could I force (key) to wait for a keypress?

This is the script:
***
#!/usr/bin/picolisp /usr/lib/picolisp/lib.l

(load @lib/misc.l)

(in NIL
   (until (eof)
  (prinl (line)) ) )

(prinl Press Key...) (key)
(bye)
***
Thank you,
Enrique





-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Subscribe

[Enrique Sánchez]

Hello Enrique =?iso-8859-1?Q?S=E1nchez?= petenr...@gmail.com :-)
You are now subscribed


-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe