why are there [v e c t o r s] in Lisp?

why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

One of the things I like the most with Lisp is the way
it is typed and written. It is just so much more
enjoyable both to type and read. And otherwise
interact with (e.g., the help). Long words are
prefered, with everything spelled out - compare
`gnus-action-message-log' to the argc, argv, etc.
of typical C! Also dashes instead of the ugly
underscore, which is less readable, and slower as well
(two keys instead of one for the dash) - and then to
think of the worst case, the CamelCase of Java (no pun
intended - still, better keep the sick bags nearby!).
And then while not exactly ugly, who needs the curly
braces to delimit functions (virtually all other
languages, apparently), or for that matter the square
brackets of array indexes and iteration? Or the
semi-colon to delimit expressions and statements?
They are just a bit tricky to type (except for the
semi-colon) and they make the code look like an
anthill - for no reason as Lisp shows. But there is
one thing that clouds the perfect sky - vectors.
I realized this when I was thinking about this. Why is
there a special syntax for vectors? In linear algebra,
an n-dimensional vector is a sequence of n numbers,
and collectively they make for something that has
direction and magnitude (in particular, it doesn't
have a position). But whatever the math, isn't that (a
sequence of numbers) something that the lists of Lisp
can handle just as well, or actually better, as it
will be more generic (a lot of stuff that doesn't work
on "real" Lisp vectors will work on vectors that are
also lists). And using lists doesn't mean nobody
cannot write hundreds of "math vector" specific stuff
to modify those list vectors! Right?

Have a look:

    (vectorp [1 2 3]) ; t

    (vectorp '(1 2 3)) ; nil - really?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Aurélien Aptel]

I'm just nitpicking, but:

On Fri, Oct 16, 2015 at 3:12 AM, Emanuel Berg <embe8573@student.uu.se> wrote:
> direction and magnitude (in particular, it doesn't
> have a position). But whatever the math, isn't that (a

The direction and the position you're talking about are geometry
concepts. Linear algebra is just a tool that can be used to model many
things e.g. in mechanics to represent forces, in euclidian geometry to
represent positions *or* directions, you can even used them to model
text documents [1] etc. In pure linear algebra, "direction" and
"position" are not defined for vectors. You could argue that elisp is
using vectors to model a specific concept (constant time random access
objects) and as such deserves its own notation, different from the
list.

See? It's all a matter of perspective.

1: https://en.wikipedia.org/wiki/Vector_space_model

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Aurélien Aptel <aurelien.aptel+emacs@gmail.com>
writes:

> The direction and the position you're talking about
> are geometry concepts. Linear algebra is just a tool

What do you mean "just" a tool?

> that can be used to model many things e.g.
> in mechanics to represent forces, in euclidian
> geometry to represent positions *or* directions, you
> can even used them to model text documents [1] etc.
> In pure linear algebra, "direction" and "position"
> are not defined for vectors. You could argue that
> elisp is using vectors to model a specific concept
> (constant time random access objects) and as such
> deserves its own notation, different from the list.

It seems to be like this:

- in terms of linear algebra, a plain, finite list
  with one and the same base data type as elements is
  a vector as good as any

- in terms of modeling, you can do all sorts of things
  with this concept

- in terms of Elisp programming, the vector type
  shouldn't necessarily be thought of as a linear
  algebra concept but rather another data structure
  that can be used for many purposes, just like the
  Elisp list, only most often specific purposes are
  better suited for one or the other

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Jude DaShiell]

vectors are how elisp got used to write functions that do statistics I 
think.  The vmean() function being one example and vmedian() being 
another.  Unfortunately org-mode hasn't got a vmode() function to go 
along with those two which is why I use datamash to calculate my helath 
statistics.

On Sat, 17 Oct 2015, Aur?lien Aptel wrote:

> Date: Fri, 16 Oct 2015 21:11:23
> From: Aur?lien Aptel <aurelien.aptel+emacs@gmail.com>
> To: "help-gnu-emacs@gnu.org" <help-gnu-emacs@gnu.org>
> Subject: Re: why are there [v e c t o r s] in Lisp?
> 
> I'm just nitpicking, but:
>
> On Fri, Oct 16, 2015 at 3:12 AM, Emanuel Berg <embe8573@student.uu.se> wrote:
>> direction and magnitude (in particular, it doesn't
>> have a position). But whatever the math, isn't that (a
>
> The direction and the position you're talking about are geometry
> concepts. Linear algebra is just a tool that can be used to model many
> things e.g. in mechanics to represent forces, in euclidian geometry to
> represent positions *or* directions, you can even used them to model
> text documents [1] etc. In pure linear algebra, "direction" and
> "position" are not defined for vectors. You could argue that elisp is
> using vectors to model a specific concept (constant time random access
> objects) and as such deserves its own notation, different from the
> list.
>
> See? It's all a matter of perspective.
>
> 1: https://en.wikipedia.org/wiki/Vector_space_model
>
>

-- 

Re: why are there [v e c t o r s] in Lisp?

[Nick Dokos]

Jude DaShiell <jdashiel@panix.com> writes:

> vectors are how elisp got used to write functions that do statistics I
> think.  The vmean() function being one example and vmedian() being
> another.  Unfortunately org-mode hasn't got a vmode() function to go
> along with those two which is why I use datamash to calculate my
> helath statistics.
>

You mean *Calc* does not have a vmode() function: org spreadsheets
piggy-back on calc for vmean() (a.k.a. calc-vector-mean) and vmedian()
(a.k.a.  calc-vector-median). And indeed Calc does not define a vmode()
function. I think - without any inside knowledge - that's because the
mode can be very dependent on the distribution and different
circumstances would require different definitions (e.g. a multimodal
distribution with a bunch of maxima, not all the same: is the mode the
global maximum or is it the list of all the maxima? or perhaps a list of
a subset of the maxima - and in that case, which ones? Part of the
difficulty would be classifying a given empirical distribution - i.e. a
vector of values - as one or another of these multimodal distributions,
so that Calc would know which definition to use. But your *particular*
case might not require such classification (you know what kind of
distribution you have), in which case a specialised vmode() can be
written - but it would not apply in general).

--
Nick

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> It seems to be like this:
>
> - in terms of linear algebra, a plain, finite list
>   with one and the same base data type as elements is
>   a vector as good as any
>
> - in terms of modeling, you can do all sorts of things
>   with this concept
>
> - in terms of Elisp programming, the vector type
>   shouldn't necessarily be thought of as a linear
>   algebra concept but rather another data structure
>   that can be used for many purposes, just like the
>   Elisp list, only most often specific purposes are
>   better suited for one or the other

Yes.  One could give a precise mathematical definition of computing
objects.  Usually, computing objects would have a complicated and
trivial mathematical description, that wouldn't entirely correspond to
the usual mathematical objects used, but some mapping is possible: this
is how and why you can "represent" the usual mathematical objects with
computing objects.

If you want to see an example, of a precise mathematical definition of
the computing object, have a look at the last chapter of r5rs. 

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Aurélien Aptel <aurelien.aptel+emacs@gmail.com> writes:

> I'm just nitpicking, but:
> […]
> In pure linear algebra, "direction" and "position" are not defined for
> vectors. 

Well once you define dot-product, you have defined implicitely angles
and therefore direction.

    A⋅B = |A|×|B|×cos(∠AB)
    A⋅B/(|A|×|B|) = cos(∠AB)

    For a vector V and a base (In), 
    (cos(∠VIn))=(V⋅In/|V|) defines the direction of the vector V.

    If (In)=((δin)), then (V⋅In/|V|) = V/|V|
    which shows that any vector defines a direction by itself.

The essence of vector is to define a direction and a magnitude.  Notably
for vector spaces without a finite basis, V/|V| is still the direction
of the vector V, intrinsically (every unitary vector is a distinct
direction).

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> The essence of vector is to define a direction and
> a magnitude. Notably for vector spaces without
> a finite basis, V/|V| is still the direction of the
> vector V, intrinsically (every unitary vector is
> a distinct direction).

Yes, but perhaps what Aurélien Aptel said (vectors in
linear algebra being a tool concept to model just
about anything) is analogous to the vectors of Elisp
being data structures that can hold data for virtually
any purpose? And then, why aren't the Elisp vectors
simply called "arrays" like everywhere else?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Barry Margolin]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 949 bytes --]

In article <876126w0t8.fsf@debian.uxu>,
 Emanuel Berg <embe8573@student.uu.se> wrote:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
> 
> > The essence of vector is to define a direction and
> > a magnitude. Notably for vector spaces without
> > a finite basis, V/|V| is still the direction of the
> > vector V, intrinsically (every unitary vector is
> > a distinct direction).
> 
> Yes, but perhaps what Aurélien Aptel said (vectors in
> linear algebra being a tool concept to model just
> about anything) is analogous to the vectors of Elisp
> being data structures that can hold data for virtually
> any purpose? And then, why aren't the Elisp vectors
> simply called "arrays" like everywhere else?

Traditionally in Lisp, "array" has meant multi-dimensional arrays, while 
"vector" means 1-dimensional arrays.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Barry Margolin <barmar@alum.mit.edu> writes:

> Traditionally in Lisp, "array" has meant
> multi-dimensional arrays, while "vector" means
> 1-dimensional arrays.

Got it!

I don't think I would have asked the original question
if they (the vectors) were called arrays because then
there's no association to linear algebra and the array
is a well-known data structure concept.

But now that I know I don't mind vectors being called
vectors, because that is what they are, and it is cool
to have this specific a terminology!

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> Barry Margolin <barmar@alum.mit.edu> writes:
>
>> Traditionally in Lisp, "array" has meant
>> multi-dimensional arrays, while "vector" means
>> 1-dimensional arrays.
>
> Got it!
>
> I don't think I would have asked the original question
> if they (the vectors) were called arrays because then
> there's no association to linear algebra and the array
> is a well-known data structure concept.

Obviously not.

And linear algebra deals with matrices and tensors etc, which are
arrays!



> But now that I know I don't mind vectors being called
> vectors, because that is what they are, and it is cool
> to have this specific a terminology!

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Obviously not.
>
> And linear algebra deals with matrices and tensors
> etc, which are arrays!

They are not called arrays but matrices so there is no
confusing the data structure array with the linear
algebra concept matrix.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Javier]

Emanuel Berg <embe8573@student.uu.se> wrote:
> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
> 
>> Obviously not.
>>
>> And linear algebra deals with matrices and tensors
>> etc, which are arrays!
> 
> They are not called arrays but matrices so there is no
> confusing the data structure array with the linear
> algebra concept matrix.

If you want to avoid confusions with linear algebra you can use the
word 'tuples' instead of 'vectors', like in Python.

https://en.wikipedia.org/wiki/Tuple

One question: is a Python tuple exactly the same as a Lisp vector?

Re: why are there [v e c t o r s] in Lisp?

[Javier]

Javier <nospam@nospam.com> wrote:
> If you want to avoid confusions with linear algebra you can use the
> word 'tuples' instead of 'vectors', like in Python.

Anyway, no need to do that. Lisp terminology is fine as it is.

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Javier <nospam@nospam.com> writes:

> Emanuel Berg <embe8573@student.uu.se> wrote:
>> "Pascal J. Bourguignon" <pjb@informatimago.com>
>> writes:
>> 
>>> Obviously not.
>>>
>>> And linear algebra deals with matrices and tensors
>>> etc, which are arrays!
>> 
>> They are not called arrays but matrices so there is no
>> confusing the data structure array with the linear
>> algebra concept matrix.
>
> If you want to avoid confusions with linear algebra you can use the
> word 'tuples' instead of 'vectors', like in Python.
>
> https://en.wikipedia.org/wiki/Tuple
>
> One question: is a Python tuple exactly the same as a Lisp vector?

Well, the tuple notion is tained, notably by some purely functional
programming language, where only a single argument can be passed to a
function (and therefore multiple arguments are packed into a single
tuple), and where multiple resulting values are similarly packed into a
single tlupe to have a single value result.


In emacs lisp and CL, we have multiple argument functions, and if you
consider a vector to be a tuple, you cannot pass it easily to functions:

    (apply (function +) (coerce [1 2 3] 'list))

when you'd just write +[1 2 3] in some language.

And in CL we have multiple values results, but they're not a tuple,
since multiple values are not reified:

  (let (q r)
     (setf (values q r) (truncate 10 3))  
     (list q r))
  --> (3 1)

In emacs lisp, there's no such thing.  
With (require 'cl), values is actually list:

    (values 1 2 3) --> (1 2 3)

which you can handle with destructuring-bind:

    (destructuring-bind (q r) (values (truncate 10 3) (rem* 10 3))
       (list q r))
    --> (3 1)

but this still doesn't make a tuple, and there's no help from the
language to deal with vector results.

So a Python tuple is not like a lisp vector at all.
(but nothing prevents you to implement in lisp something like Python
tuples and using vectors to represent them).


(setf lexical-binding t)

(defmacro tuple (&rest arguments) `(vector ,@arguments))

(defmacro define-tupled-function (name parameters &rest body)
  (let ((tuple (gensym)))
    `(defun ,name (,tuple)
       (let (,@(let ((index -1))
                 (mapcar (lambda (parameter)
                           (list parameter `(aref ,tuple ,(incf
                                                           index))))
                         parameters)))
         ,@body))))

(defmacro tuple-setq (var-tuple val-tuple)
  (let ((tuple (gensym)))
    `(let ((,tuple ,val-tuple))
       ,@(map 'list (let ((index -1))
                      (lambda (var)
                        `(setq ,var (aref ,tuple ,(incf index)))))
           var-tuple))))

(define-tupled-function addsub (a b) (tuple (+ a b) (- a b)))

(let (s d)
  (tuple-setq [s d] (addsub [2 3]))
  (list s d))
;; --> (5 -1)

(addsub [2 3])                   --> [5 -1]
(addsub (addsub [2 3]))          --> [4 6]
(addsub (addsub (addsub [2 3]))) --> [10 -2]

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Well, the tuple notion is tained, notably by some
> purely functional programming language

There are "tuples" in linear algebra books as well,
where tuples are pairs, and n-tuples are vectors (or
lists) with n elements.

Anyway, instead of inventing a new terminology that is
supposedly less confusing it is better just to learn
the one used. In this case it is very simple at that
(1D - vector, 2D or more - array).

Otherwise it will be even more confusion as some
people are used to the old terminology, to the point
where there is diverging sets. This happens all the
time with no worries, however in programming it is
especially unpractical as all those functions would
still be using "vector" and not tuple or whatever, and
the people calling them tuples would be lost and think
them gone.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> Obviously not.
>>
>> And linear algebra deals with matrices and tensors
>> etc, which are arrays!
>
> They are not called arrays but matrices so there is no
> confusing the data structure array with the linear
> algebra concept matrix.

Nobody but you is confusing arrays with matrices, since they're not the
same thing. 

vectors are arrays.
matrices are arrays.
tensors are arrays.

But you don't have arrays when you only have vectors (like in C).



Notice how in CL, there's a distinction between a 3-vector and a
1,3-matrix, or a 1,1,3-array:

cl-user> (make-array '(3))
#(0 0 0)
cl-user> (make-array '(1 3))
#2A((0 0 0))
cl-user> (make-array '(1 1 3))
#3A(((0 0 0)))

Or similary, there's a distinction between a 3,4-matrix and a
1,3,4-array:

cl-user> (make-array '(3 4))
#2A((0 0 0 0) (0 0 0 0) (0 0 0 0))
cl-user> (make-array '(1 3 4))
#3A(((0 0 0 0) (0 0 0 0) (0 0 0 0)))
cl-user> 


It's a trivial notion of subclass/superclass, if you had any object
oriented knowledge.

That said, while CL distinguishes a vector subclass of arrays, it
doesn't name a matrix subclass.


In emacs lisp, since we don't have arrays, only vectors, we have to use
tricks like in C to implement matrices or tensors:

   (type-of (make-array '(2 3))) --> vector

Happily, emacs lisp helps a little, creating a vector of vector:

   (make-array '(2 3))           --> [[nil nil nil] [nil nil nil]]

   (aref (make-array '(2 3)) 0)  --> [nil nil nil]


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Nobody but you is confusing arrays with matrices,
> since they're not the same thing.
>
> vectors are arrays. matrices are arrays.
> tensors are arrays.

In the abstract sense, a list is a vector and a vector
is a matrix and a matrix is an array. And an array,
if 1-dimensional, is a list.

In the math world there are vectors and matrices (and
more :).

In the programming world there are lists and arrays
which can implement various math concepts including
vectors and matrices.

In many programming languages, 1-dimensional arrays
are called arrays as well as multidimensional arrays.
In Lisp, 1-dimensional arrays are called vectors.
Because of this, one might think they are to be used
specifically to do the vectors of linear algebra.
But this isn't so.

Conceptually everything is arrays, and everything is
matrices - only to reduce confusion it makes sense to
keep the terminology apart, with the exception of Lisp
1-dimenisonal arrays, which should be called vectors,
because that is what that are called and that word is
used when you use them in code. And they are vectors
as well, so there is not harm calling them that.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> The essence of vector is to define a direction and
>> a magnitude. Notably for vector spaces without
>> a finite basis, V/|V| is still the direction of the
>> vector V, intrinsically (every unitary vector is
>> a distinct direction).
>
> Yes, but perhaps what Aurélien Aptel said (vectors in
> linear algebra being a tool concept to model just
> about anything) is analogous to the vectors of Elisp
> being data structures that can hold data for virtually
> any purpose? And then, why aren't the Elisp vectors
> simply called "arrays" like everywhere else?

Because everybody else got it wrong: they don't have (multidimensional)
arrays, they only have vectors (even when they have syntactic sugar to
make vectors of vectors, they aren't arrays).

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> Why is there a special syntax for vectors? 

To make it easy to introduce literal vectors in your programs.

Without this syntax, you would only have run-time constructors, and you
would have to write more complex code.

For example, the equivalent of:

    (defun permut-0213 (x)
       (aref [0 2 1 3] x))

would have to be written as:

   (defun permut-0213 (x)
      (aref (load-time-value (vector 0 2 1 3)) x))

or:
    
   (let ((permut (vector 0 2 1 3)))
     (defun permut-0213 (x)
        (aref permut x)))


> In linear algebra, an n-dimensional vector is a sequence of n numbers,
> and collectively they make for something that has direction and
> magnitude (in particular, it doesn't have a position). But whatever
> the math, isn't that (a sequence of numbers) something that the lists
> of Lisp can handle just as well, or actually better, as it will be
> more generic (a lot of stuff that doesn't work on "real" Lisp vectors
> will work on vectors that are also lists). And using lists doesn't
> mean nobody cannot write hundreds of "math vector" specific stuff to
> modify those list vectors! Right?

Right.  And why have strings too!


> Have a look:
>
>     (vectorp [1 2 3]) ; t
>
>     (vectorp '(1 2 3)) ; nil - really?

    (vectorp "123")       ; --> nil - why? :-( 

    (sequencep [1 2 3])  ; --> t
    (sequencep '(1 2 3)) ; --> t
    (sequencep "123")    ; --> t

In Common Lisp, strings are vectors are sequence.
And in CL, vectors are arrays, which may be multi-dimensional, but
there's no such thing in emacs lisp.


The reason why there is a vector data type distinct from the list data
type is purely an optimization reason.  In ACL2, for example, there are
only "lists". https://en.wikipedia.org/wiki/ACL2



In lisp, there are no lists.  There's no list abstract data type.  There
are only cons cells, which are used to build linked lists of cons cells.

Here, a cons cell is represented with a box split in two parts, the car
and the cdr:

    +---+---+
    | * | * |-->
    +---+---+
      |
      v


Therefore a list such as (1 2 3 4 5) will be actually a cons cell:
 (1 . (2 . (3 . (4 . (5 . nil))))), which can be drawn as:

+-----------------------------------------------------------+
| (1 2 3 4 5)                                               |
|                                                           |
| +---+---+   +---+---+   +---+---+   +---+---+   +---+---+ |
| | * | * |-->| * | * |-->| * | * |-->| * | * |-->| * |NIL| |
| +---+---+   +---+---+   +---+---+   +---+---+   +---+---+ |
|   |           |           |           |           |       |
|   v           v           v           v           v       |
| +---+       +---+       +---+       +---+       +---+     |
| | 1 |       | 2 |       | 3 |       | 4 |       | 5 |     |
| +---+       +---+       +---+       +---+       +---+     |
+-----------------------------------------------------------+

The problem is that to find the ith element in the list, we have to walk
i cons cells:

    (defun elt (s i)
       (etypecase s
         (null nil)
         (cons (if (zerop i)
                  (car s)
                  (elt (cdr s) (1- i))))))

elt is therefore O(n) for lists of length n, which is rather slow for
such a basic access.



The solution is to use internally an indexed data structure: contiguous
memory blocks, for which we can compute the address in O(1):


+-----------------------------------------------------------+
| [1 2 3 4 5]                                               |
|                                                           |
| +-----+-----+-----+-----+-----+                           |                          
| |  *  |  *  |  *  |  *  |  *  |                           |                         
| +-----+-----+-----+-----+-----+                           |                         
|    |     |     |     |     |                              |                      
|    v     v     v     v     v                              |
|  +---+ +---+ +---+ +---+ +---+                            |
|  | 1 | | 2 | | 3 | | 4 | | 5 |                            |
|  +---+ +---+ +---+ +---+ +---+                            |
+-----------------------------------------------------------+


To find the address of the ith slot, we only have to multiply i by the
size of the slots, and add the address of the start of the vector:

(defun elt (s i)
  (etypecase s
    (null nil)
    (cons (if (zerop i)
              (car s)
              (elt (cdr s) (1- i))))
    (vector (%deref (%address (+ (%address-of s)
                                 (* i (%size-of-element-of s))))))))

All the operations performed for the vector case are O(1), therefore elt
for vectors is O(1), which is much faster than for list, notably when
the index is not small.

Furthermore, notice that this kind of vector addressing often benefit
from addressing modes implemented in the processor, so you don't really
have to compile it from lisp; the implementation will have a native
vector indexing operator that will translate to a single inline
processor instruction:

;; in CCL:
cl-user> (disassemble (lambda (s i)
                        (declare (optimize (speed 3) (space 3) (safety 0) (debug 0)))
                        (declare (type simple-vector s) (type fixnum i))
                        (svref s i)))
L0
    (leaq (@ (:^ L0) (% rip)) (% fn))       ;     [0]
    (pushq (% rbp))                         ;     [7]
    (movq (% rsp) (% rbp))                  ;     [8]
    (pushq (% arg_y))                       ;    [11]
    (pushq (% arg_z))                       ;    [12]
    (movq (@ -5 (% arg_y) (% arg_z)) (% arg_z)) ;    [13]
    (leaveq)                                ;    [18]
    (retq)                                  ;    [19]
nil
cl-user> 

Notice how the access to the vector slot is reduced to the single ix86
instruction:

    (movq   (@ -5 (% arg_y) (% arg_z))    (% arg_z))

(The offset -5 is introduced to remove the type tag in the address of
the vector).




Now, of course, (car l) will be faster than (aref v 0)
and (cadr l) might also be faster than (aref v 1), but already, (cadr l)
requires two memory accesses (read the cdr of l, read the car of that
cdr), while (aref v 1) only needs one memory access (the movq above), 
so even if movq with it's implied multiply and add will probably be
faster than a memory access, more so nowadays when processor (register)
speed have become much faster than memory accesses.



Therefore the lesson is that if you have to use elt (nth) on a list, in
a loop, you definitely do not want to do that if the list is more than
one or two elements.


Instead, either process the elements in the list in order using car/cdr,
or use a vector for random access.




In the case of emacs lisp, the difference is hidden in the virtual
machine, you would have to look at the C code:

(disassemble (lambda (s i) (aref s i)))
byte code:
  args: (s i)
0       varref    s
1       varref    i
2       aref      
3       return    

(disassemble (lambda (l i) (nth i l)))
byte code:
  args: (l i)
0       varref    i
1       varref    l
2       nth       
3       return    

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

>> Why is there a special syntax for vectors? 
>
> To make it easy to introduce literal vectors in
> your programs.

OK, if you do it all day long that is an advantage
just as I wouldn't want to do strings as lists, not
that I use that much strings - however there is a flaw
to the analogy and that is: having a string instead as
a list isn't nearly as readable or editable as is
a string - compare

    (print "message")
    (print '(m e s s a g e))

while I don't see any such difference with [1 2 3] and
'(1 2 3)!

Perhaps if you did a special syntax highlight for the
squared vectors that would make them more visible and
easily detected along with all the other parenthesised
code - again, only if you have tons of vectors this
would make for any practical difference. (It might
look cool tho.)

> Without this syntax, you would only have run-time
> constructors, and you would have to write more
> complex code.

... why? If lists are vectors, which they are in terms
of what they hold and how they look, then you don't
need more code compared to vectors, on the contrary
you need less code!

> For example, the equivalent of:
>
>     (defun permut-0213 (x)
>        (aref [0 2 1 3] x))
>
> would have to be written as:
>
>    (defun permut-0213 (x)
>       (aref (load-time-value (vector 0 2 1 3)) x))

What I mean is, the list '(0 2 1 3) is already
a vector, why not just leave it at that?

> Therefore a list such as (1 2 3 4 5) will be
>  actually a cons cell: (1 . (2 . (3 . (4 . (5 .
>  nil)))))

Indeed, but the same argument as I just made for
strings can be applied here as well:

1) Strings and lists are so common so they should look
   their best, which is why we can't have strings
   lists or lists cons cells, because then they don't
   even look like what they are.

2) Vectors are not that common, but just because
   something is less common doesn't mean it should be
   treated worse, fine - still, '(1 2 3) doesn't look
   any worse than [1 2 3] - even in math books the
   square brackets are sometimes not square, but
   parenthesis (denoting lists, ordered n-paris, or
   vectors!).

The rest of the post I appreciate and especially the
the ASCII figures.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Random832]

Emanuel Berg <embe8573@student.uu.se> writes:
> ... why? If lists are vectors, which they are in terms
> of what they hold and how they look, then you don't
> need more code compared to vectors, on the contrary
> you need less code!

The thing is, a vector in elisp terms is a specific type of object. It's
in contiguous memory, and you can't take its cdr. It is an array whereas
a list is a linked list.

Maybe in some platonic ideal lisp there wouldn't be a difference, but in
elisp there is.

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Random832 <random832@fastmail.com> writes:

>> ... why? If lists are vectors, which they are in
>> terms of what they hold and how they look, then you
>> don't need more code compared to vectors, on the
>> contrary you need less code!
>
> The thing is, a vector in elisp terms is a specific
> type of object. It's in contiguous memory, and you
> can't take its cdr. It is an array whereas a list is
> a linked list.
>
> Maybe in some platonic ideal lisp there wouldn't be
> a difference ...

Indeed, this is what I think!

If a list just contains say a bunch of known integers
that don't need to be computed, is there anything that
stops this list from being stored in "contiguous
memory" with the list functions as well as the
constant access time "vector" functions available?

By the way: in my previous post strings were mentioned
and it sounded like they were sugar for lists of chars
- this isn't the case (you can't `car' a string) but
it could have been and it isn't harmful (I think) to
think of strings that way.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Random832]

Emanuel Berg <embe8573@student.uu.se> writes:
> If a list just contains say a bunch of known integers
> that don't need to be computed, is there anything that
> stops this list from being stored in "contiguous
> memory" with the list functions as well as the
> constant access time "vector" functions available?

Well, what happens if you cdr that list? Does it make a
copy? Wasted memory, wasted time, won't track if you change
the original. Yeah, yeah, in platonic ideal lisp you *can't*
change lists, but this is the real world, where even scheme
lets you do it. Does it keep a reference to the original
list? Then what if you take the cd^{4000}r of a list of
5000, then throw away the original?  Wasted memory
again. Java used to have this issue with strings. I suppose
you could have the underlying array somehow know what the
earliest index that a reference actually exists for is, and
magically throw away everything before it during garbage
collection, if there's too much wasted space. But that seems
rather a lot of work.

> By the way: in my previous post strings were mentioned
> and it sounded like they were sugar for lists of chars
> - this isn't the case (you can't `car' a string) but
> it could have been and it isn't harmful (I think) to
> think of strings that way.

The thing is, if you can car a string people will wonder why
you can't cdr it. And with mutable objects it's hard to make
cdr work right. (fsvo "right")

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Random832 <random832@fastmail.com> writes:

> The thing is, if you can car a string people will
> wonder why you can't cdr it. And with mutable
> objects it's hard to make cdr work right. (fsvo
> "right")

You can't `car' a string or do anything with it that
requires it to be a list, because it isn't. If you try
to car it, the string will fail the `listp' test.
But because it is natural to think of strings as lists
of chars, perhaps from the C days of, say

    char *str = malloc(strlen(argv[argc - 1]));

or actually because it is normal for humans to think
of strings that way, it should be pointed out - and
now that has happened - that the "string" syntax isn't
a shorthand for creating lists of chars.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> Random832 <random832@fastmail.com> writes:
>
>> The thing is, if you can car a string people will
>> wonder why you can't cdr it. And with mutable
>> objects it's hard to make cdr work right. (fsvo
>> "right")
>
> You can't `car' a string or do anything with it that
> requires it to be a list, because it isn't. If you try
> to car it, the string will fail the `listp' test.
> But because it is natural to think of strings as lists
> of chars, perhaps from the C days of, say
>
>     char *str = malloc(strlen(argv[argc - 1]));
>
> or actually because it is normal for humans to think
> of strings that way, it should be pointed out - and
> now that has happened - that the "string" syntax isn't
> a shorthand for creating lists of chars.

In emacs lisp it'd be difficult to do it, but in Common Lisp it's
trivial:

(defpackage "EB-LISP"
  (:use "COMMON-LISP")
  (:shadow "CAR" "CDR" "CONSP" "LISTP")
  (:export . #.(let ((syms '()))
                 (do-external-symbols (s "COMMON-LISP" syms)
                   (push (symbol-name s) syms)))))
(in-package "EB-LISP")

(defun car (x)
  (if (vectorp x)
      (aref x 0)
      (cl:car x)))

(defun cdr (x)
  (if (vectorp x)
      (if (< 1 (length x))
          (make-array (1- (length x))
                      :element-type (array-element-type x)
                      :displaced-to x
                      :displaced-index-offset 1)
          '())
      (cl:cdr x)))

(defun consp (x)
  (or (vectorp x) (cl:consp x)))

(defun listp (x)
  (or (vectorp x) (cl:listp x)))


(defpackage "EB-LISP-USER"
  (:use "EB-LISP"))
(in-package "EB-LISP-USER")

(loop :for string := "hello world" :then (cdr string)
       :while string
       :collect (car string))
;; --> (#\h #\e #\l #\l #\o #\  #\w #\o #\r #\l #\d)



Instead, in emacs-lisp you can prefix your symbols: eb-lisp-car
eb-lisp-cdr etc…  (and you have to implement more things yourself, since
there are no displaced arrays, etc).

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> In emacs lisp it'd be difficult to do it, but in
> Common Lisp it's trivial

I didn't say I wanted strings not to be

    "strings"

but

    '(32 9 13 105 10 103)

But having the vector

    [1 2 3]

as

    '(1 2 3)

wouldn't be bad if the computer could figure out on
its own the most efficient way to store and interact
with the data.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> In emacs lisp it'd be difficult to do it, but in
>> Common Lisp it's trivial
>
> I didn't say I wanted strings not to be
>
>     "strings"
>
> but
>
>     '(32 9 13 105 10 103)
>
> But having the vector
>
>     [1 2 3]
>
> as
>
>     '(1 2 3)
>
> wouldn't be bad if the computer could figure out on
> its own the most efficient way to store and interact
> with the data.

As I said, you could write a compiler performing global analysis to
determine how you use a given object in the data flow, and therefore
store the literal as a list or as a vector.

One complication would be I/O. The data flow analysis could let the
compiler determine that some object read shall be stored as a vector or
as list, but the reading function wouldn't know that from the external
syntax, and it would need an additionnal type parameter.

Notice that this introduces some kind of static typing which is rather
contrary to the lisp spirit and makes thing so bad in serializing
non-lisp like languages.


At this point, the best you could do is to start writing your own
compiler to implement this idea, and see whether it's a good idea or
not.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> As I said, you could write a compiler performing
> global analysis to determine how you use a given
> object in the data flow, and therefore store the
> literal as a list or as a vector.
>
> One complication would be I/O. The data flow
> analysis could let the compiler determine that some
> object read shall be stored as a vector or as list,
> but the reading function wouldn't know that from the
> external syntax, and it would need an additionnal
> type parameter.
>
> Notice that this introduces some kind of static
> typing which is rather contrary to the lisp spirit
> and makes thing so bad in serializing non-lisp
> like languages.
>
> At this point, the best you could do is to start
> writing your own compiler to implement this idea,
> and see whether it's a good idea or not.

I'm not suggesting anyone do this. It sounds to much
like the C preprocessor. The gain is diffuse from
where I sit.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> As I said, you could write a compiler performing
>> global analysis to determine how you use a given
>> object in the data flow, and therefore store the
>> literal as a list or as a vector.
>>
>> One complication would be I/O. The data flow
>> analysis could let the compiler determine that some
>> object read shall be stored as a vector or as list,
>> but the reading function wouldn't know that from the
>> external syntax, and it would need an additionnal
>> type parameter.
>>
>> Notice that this introduces some kind of static
>> typing which is rather contrary to the lisp spirit
>> and makes thing so bad in serializing non-lisp
>> like languages.
>>
>> At this point, the best you could do is to start
>> writing your own compiler to implement this idea,
>> and see whether it's a good idea or not.
>
> I'm not suggesting anyone do this. 

I'm definitely suggesting  you do that!  You definitely need to learn
something, and writing your own compiler, and implementing that idea
would be the best way for you to learn it.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Random832 <random832@fastmail.com> writes:

> Emanuel Berg <embe8573@student.uu.se> writes:
>> If a list just contains say a bunch of known integers
>> that don't need to be computed, is there anything that
>> stops this list from being stored in "contiguous
>> memory" with the list functions as well as the
>> constant access time "vector" functions available?

Emanuel, notice that in some implementations of lisp in the 1980s, there
was an optimization for lists called cdr-coding which stored the list
when it was copied as a vector of consecutive elements (eliminating thus
the cdr, which basically was reduced to a bit in tag of the slot).  This
still allowed to call cdr (instead of derefencing that slot, we'd just
increment the address in the vector).  But if you used rplacd, then it
had to "split" the cdr-coded vector, creating a new cons cell where to
store the new cdr pointer.

    (copy-list '(1 2 3 4 5))

would create a vector of CARs and point to the first one.  The slot
would have a bit set indicating that the CDR has been eliminated, and
the CAR of the next cell is stored in the next address:

+-----------------------------------------------------------+
| list = (1 2 3 4 5)   +----------------------------f       |
|   |                  |                                    |
|   v                  v                                    |
| +-----+-----+-----+-----+-----+-----+                     |                          
| |  * '|  * '|  * '|  * '|  *  | NIL |                     |                         
| +-----+-----+-----+-----+-----+-----+                     |                         
|    |     |     |     |     |                              |                      
|    v     v     v     v     v                              |
|  +---+ +---+ +---+ +---+ +---+                            |
|  | 1 | | 2 | | 3 | | 4 | | 5 |                            |
|  +---+ +---+ +---+ +---+ +---+                            |
+-----------------------------------------------------------+

The last cell would be a CDR (so the preceeding slot doesn't have the
bit in the tag set), pointing to a following cons cell or cdr vector, or
the atom in the dotted list (here, NIL, to indicate the end of the
list).

Now the problem occurs when you use rplacd in the middle of the list:
                                                             
(let* ((list (list 1 2 3 4 5))
       (f    (nthcdr 3 list)))
  (rplacd (cddr list) (list* 4.0 4.2 (cddddr list)))         
  (list list f))
--> ((1 2 3 4.0 4.2 . #1=(5))
     (4 . #1#))

To do that in the presence of cdr-coding, we have to introduce a new
cons cell for 4, and more problematic, we have to scan the whole memory
for references to this cell, and update them (in this case, the variable
f must now point to a new cons cell, instead of in the middle of the
cdr-vector):


+-----------------------------------------------------------+
| list = (1 2 3 4 5)                                        |
|   |                                                       |
|   |                      +-----+-----+-----+              |
|   |                  +-->|  * '|  *  |  *  |              |
|   |                  |   +-----+-----+-----+              |
|   |                  |      |     |     |                 |
|   |                  |      v     v     |                 |
|   |                  |    +---+ +---+   |                 |
|   |                  |    |4.0| |4.2|   |                 |
|   |                  |    +---+ +---+   |                 |
|   |                  |                  |                 |
|   |                  |     +------------+<-----------+    |
|   |                  |     |        f-------+        |    |
|   |                  |     |                |        |    |
|   v                  v     v                v        |    |
| +-----+-----+-----+-----+-----+-----+     +---+---+  |    |                          
| |  * '|  * '|  *  |  *  |  * '| NIL |     | * | * |--+    |                         
| +-----+-----+-----+-----+-----+-----+     +---+---+       |                         
|    |     |     |           |                |             |                      
|    v     v     v           v                v             |
|  +---+ +---+ +---+       +---+            +---+           |
|  | 1 | | 2 | | 3 |       | 5 |            | 4 |           |
|  +---+ +---+ +---+       +---+            +---+           |
+-----------------------------------------------------------+

> Well, what happens if you cdr that list? Does it make a
> copy? 

cdr'ing is no problem you just increment your pointer.

> Wasted memory, wasted time, won't track if you change
> the original. Yeah, yeah, in platonic ideal lisp you *can't*
> change lists, but this is the real world, where even scheme
> lets you do it. Does it keep a reference to the original
> list? Then what if you take the cd^{4000}r of a list of
> 5000, then throw away the original?  Wasted memory
> again. Java used to have this issue with strings. I suppose
> you could have the underlying array somehow know what the
> earliest index that a reference actually exists for is, and
> magically throw away everything before it during garbage
> collection, if there's too much wasted space. But that seems
> rather a lot of work.
>
>> By the way: in my previous post strings were mentioned
>> and it sounded like they were sugar for lists of chars
>> - this isn't the case (you can't `car' a string) but
>> it could have been and it isn't harmful (I think) to
>> think of strings that way.
>
> The thing is, if you can car a string people will wonder why
> you can't cdr it. And with mutable objects it's hard to make
> cdr work right. (fsvo "right")

It's rplacd which becomes much more complex.

Also, when you program with such a system, you might be afraid that
rplacd leads to fragmented chains, and will have a tendency to call
copy-list to compact them.  But indeed, copy-list means that less
structure is shared, and therefore would waste time and memory.  This is
what they do in C++ and why they believe lists are costly.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Random832]

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> Random832 <random832@fastmail.com> writes:
>> Well, what happens if you cdr that list? Does it make a
>> copy? 
>
> cdr'ing is no problem you just increment your pointer.
>
>> The thing is, if you can car a string people will wonder why
>> you can't cdr it. And with mutable objects it's hard to make
>> cdr work right. (fsvo "right")
>
> It's rplacd which becomes much more complex.

You didn't mention my issue with "list of 5000 elements, cdr
4000 times" - does the garbage collector know to discard the
first 4000 elements which are no longer reachable?

> Also, when you program with such a system, you might be afraid that
> rplacd leads to fragmented chains, and will have a tendency to call
> copy-list to compact them.

Hmm... can the garbage collector compact them?

>  But indeed, copy-list means that less
> structure is shared, and therefore would waste time and memory.  This is
> what they do in C++ and why they believe lists are costly.

Also with this kind of list I think you still lose the
ability to have constant-time indexing, since you have to
check every cell for the cdr bit.

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Random832 <random832@fastmail.com> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>> Random832 <random832@fastmail.com> writes:
>>> Well, what happens if you cdr that list? Does it make a
>>> copy? 
>>
>> cdr'ing is no problem you just increment your pointer.
>>
>>> The thing is, if you can car a string people will wonder why
>>> you can't cdr it. And with mutable objects it's hard to make
>>> cdr work right. (fsvo "right")
>>
>> It's rplacd which becomes much more complex.
>
> You didn't mention my issue with "list of 5000 elements, cdr
> 4000 times" - does the garbage collector know to discard the
> first 4000 elements which are no longer reachable?

Well, I don't know if the implementations that had cdr-coding could
collect the prefix of the vector of cars that wasn't referenced anymore.
It's a little complexity for the garbage collector, but not too hard to
implement. The problem is more when you want to discard the 1 element
which is no longer reachable: this becomes quite costly.


>> Also, when you program with such a system, you might be afraid that
>> rplacd leads to fragmented chains, and will have a tendency to call
>> copy-list to compact them.
>
> Hmm... can the garbage collector compact them?

Compacting lists at garbage collection time is indeed a good idea, when
you have cdr-coding.  On the other hand, I believe the implementations
that had cdr-coding had a simple mark-and-sweap garbage collector, not a
copying one.  Some archeology would be in order there.


>>  But indeed, copy-list means that less
>> structure is shared, and therefore would waste time and memory.  This is
>> what they do in C++ and why they believe lists are costly.
>
> Also with this kind of list I think you still lose the
> ability to have constant-time indexing, since you have to
> check every cell for the cdr bit.

Of course.  Worse, to have O(1) indexing, you'd need to know the length
in advance, and this is what is killing, you cannot have an efficient
length when you have mutation and structure sharing.  rplacd would have
to update an unbound number of length slots.




However, it is possible to have a compiler that will map lists to
vectors in the generated code, as long as this compiler is able to
perform global analysis to ensure the semantics.  With global analysis,
you can easily determine whether there is structure sharing, whether
rplaca is used, and determine the length of the list at compilation time
or know to store it.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>>> Why is there a special syntax for vectors? 
>>
>> To make it easy to introduce literal vectors in
>> your programs.
>
> OK, if you do it all day long that is an advantage
> just as I wouldn't want to do strings as lists, not
> that I use that much strings - however there is a flaw
> to the analogy and that is: having a string instead as
> a list isn't nearly as readable or editable as is
> a string - compare
>
>     (print "message")
>     (print '(m e s s a g e))
>
> while I don't see any such difference with [1 2 3] and
> '(1 2 3)!

This is not what you asked above.  You asked:

     Why is there a special syntax for vectors? 

What you have to compare is:
 
     "message"

with:

     (load-time-value
       (let ((string (make-string 7)))
          (setf (aref string 0) ?m
                (aref string 1) ?m
                (aref string 2) ?m
                (aref string 3) ?m
                (aref string 4) ?m
                (aref string 5) ?m
                (aref string 6) ?m)
          string))



Now, concerning the use of lists vs. strings, you answered the question
of why the special syntax yourself. to make it more readable.

Notice that in early lisp, there was no character and no string, only
lists and symbols.  Characters were represented by single-character
symbols, and strings by symbols.  There were functions implode and
explode:


    (defun implode (charsyms)
      (intern (map 'string (lambda (sym) (aref (symbol-name sym) 0))
                           charsyms)))

    (defun explode (sym)
      (map 'list (lambda (char) (intern (string char))) 
           (symbol-name sym)))

    (explode 'message)                  ; --> (m e s s a g e)
    (implode '(h e l l o \  w o r l d)) ; --> hello\ world


> Perhaps if you did a special syntax highlight for the
> squared vectors that would make them more visible and
> easily detected along with all the other parenthesised
> code - again, only if you have tons of vectors this
> would make for any practical difference. (It might
> look cool tho.)

Vector in general are vectors of t, that is they can take any type of
element.  Strings are vectors of character. Having a distinct syntax
here let you avoid the risk of error introducing a non-character in the
literal vector.


>> Without this syntax, you would only have run-time
>> constructors, and you would have to write more
>> complex code.
>
> ... why? If lists are vectors, which they are in terms
> of what they hold and how they look, then you don't
> need more code compared to vectors, on the contrary
> you need less code!

I'm assumed that you didn't ask the question you wanted to ask too.

There are DIFFERENT TYPES.  

As much as possible, for pre-defined types, lisp provides different
literal syntaxes, so that you can introduce in your programs literal
objects of those different types.  I showed in all my examples why
having such literal syntax is so useful: because constructing objects of
those types yourself takes a lot more of code.


>> For example, the equivalent of:
>>
>>     (defun permut-0213 (x)
>>        (aref [0 2 1 3] x))
>>
>> would have to be written as:
>>
>>    (defun permut-0213 (x)
>>       (aref (load-time-value (vector 0 2 1 3)) x))
>
> What I mean is, the list '(0 2 1 3) is already
> a vector, why not just leave it at that?

Right but this is not the question you asked. You asked about literal
syntax, I'm answering about literal syntax.


>> Therefore a list such as (1 2 3 4 5) will be
>>  actually a cons cell: (1 . (2 . (3 . (4 . (5 .
>>  nil)))))
>
> Indeed, but the same argument as I just made for
> strings can be applied here as well:
>
> 1) Strings and lists are so common so they should look
>    their best, which is why we can't have strings
>    lists or lists cons cells, because then they don't
>    even look like what they are.
>
> 2) Vectors are not that common, but just because
>    something is less common doesn't mean it should be
>    treated worse, fine - still, '(1 2 3) doesn't look
>    any worse than [1 2 3] - even in math books the
>    square brackets are sometimes not square, but
>    parenthesis (denoting lists, ordered n-paris, or
>    vectors!).
>
> The rest of the post I appreciate and especially the
> the ASCII figures.

The rest of the post answers to the question why there are different
types.


Now, nothing prevents you to travel back to 1960, and ignore those
additionnal types, using only lists, symbol and numbers.

Notice by the way that in emacs lisp, we lack structure types.  We can
still implement them using vectors (or lists), and write program using
the structure abstraction.  If you want to write programs using vector
or string abstractions without using actual vector or string type
objects you can do so.  You might have to avoid a few modern libraries,
but it would be no problem to rewrite the required library functions
using only the list type: this is 1960 technology.

    (defstruct point x y)
    (make-point :x 2 :y 3)
    ;; --> [cl-struct-point 2 3]

    (defstruct (vect (:type list)) x y)
    (make-vect :x 2 :y 3)
    ;;  --> (2 3)

    (defstruct (vect3 (:type list) :named) x y z)
    (make-vect3 :x 2 :y 3 :z 4)
    ;; --> (vect3 2 3 4)

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Now, concerning the use of lists vs. strings, you
> answered the question of why the special syntax
> yourself. to make it more readable.

With lists and strings this makes sense but with
vectors it is only more readable in the face of all
the surrounding Lisp, which otherwise would look the
same, because in isolation a parenthesised vector is
just as readable as one in square brackets. But they
aren't used in isolation but indeed amid Lisp so yes,
the special syntax makes it more readable by just
a bit. Again, especially if combined with a special vector
highlight.

Why the syntax is there at all is to provide fast
(faster) access to the vector data type which has
other time and space properties than do lists.
Because in the "platonic" sense, as Random put it,
there aren't any differences between lists and
vectors, at least not between lists which carry data
of a uniform type (e.g., a bunch of integers), so this
difference is on the implementation side where vectors
are allocated in cohesive memory which, because the
uniform type and total length are known, it makes for
constant access time.

> Now, nothing prevents you to travel back to 1960 ...

Save for physics, I'd go in a heartbeat... Only I'd
put a blind eye to the politics, hallucinogens and
computer infancy are sure appealing enough.

> Notice by the way that in emacs lisp, we lack
> structure types. We can still implement them using
> vectors (or lists), and write program using the
> structure abstraction. If you want to write programs
> using vector or string abstractions without using
> actual vector or string type objects you can do so.

Yeah, all the math stuff would be just as easy to do
with lists. It is the computer stuff with memory
access O(whatever) that is the difference.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:
> Why the syntax is there at all is to provide fast
> (faster) access to the vector data type which has
> other time and space properties than do lists.

ABSOLUTELY NOT.

For example, in C++ you have vectors and lists, 
but you don't have any literal syntax for them.

You can have fast and slow data structures without having any literal
syntax for it.


Why do you keep confusing the two concepts?




>> Now, nothing prevents you to travel back to 1960 ...
>
> Save for physics, I'd go in a heartbeat... Only I'd
> put a blind eye to the politics, hallucinogens and
> computer infancy are sure appealing enough.

Yes. That's an idea I have for a startup that would provide the complete
experience for periods lasting years or more, of reconstituted
historical periods.  If we collect enough information about the sixties,
we should be able to reproduce a simulated environment with real-time
feeds (radio, TV, newspapers), and of course, a living environment
(harder work would be to reconstitute things like food quality, but we
should be able to provide a good approximation).

There are already companies that can provides newpapers or things like
that.

For a higher fee, I guess we could even provide a 60's job.  For
example, we could find a remote COBOL job, and provide it to a
programmer with punch card/printer interfaces.

>> Notice by the way that in emacs lisp, we lack
>> structure types. We can still implement them using
>> vectors (or lists), and write program using the
>> structure abstraction. If you want to write programs
>> using vector or string abstractions without using
>> actual vector or string type objects you can do so.
>
> Yeah, all the math stuff would be just as easy to do
> with lists. It is the computer stuff with memory
> access O(whatever) that is the difference.

Hence the choice of ACL2, since it's purpose is to do the maths more
than fast implementation.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Random832]

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> Emanuel Berg <embe8573@student.uu.se> writes:
>> Why the syntax is there at all is to provide fast
>> (faster) access to the vector data type which has
>> other time and space properties than do lists.
>
> ABSOLUTELY NOT.
>
> For example, in C++ you have vectors and lists, 
> but you don't have any literal syntax for them.
>
> You can have fast and slow data structures without having any literal
> syntax for it.
>
>
> Why do you keep confusing the two concepts?

There are certainly situations where having a literal syntax can make
the language fast*er*. For example, in Python, the lack of a literal
syntax for the frozendict and frozenset type means it has to do a
runtime lookup on the name to make sure it hasn't been overridden, and
it means they, despite being immutable objects, can't participate in a
constants pool.

C++ doesn't have any such mechanism to have uncertainty about what type
a class name refers to, but a compiler would have to be very clever
indeed to do the kind of optimized construction for arbitrary classes
that it can do for types such as arrays and POD-structs for which
literals do exist.

Basically, a literal syntax doesn't make a type faster in general, but
for many languages and many real-world implementations it can certainly
make the specific action of constructing an object faster. Having a
literal syntax means that the object can be completely pre-built at
compile time, and for an immutable object it simply copies a pointer,
and for a mutable object (in some cases) it can simply copy a block of
memory. Whereas suppose make-vector were reassigned or advised.

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Random832 <random832@fastmail.com> writes:

> Basically, a literal syntax doesn't make a type
> faster in general, but for many languages and many
> real-world implementations it can certainly make the
> specific action of constructing an object faster.

At the very least, it makes it faster to type the
type! :)

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

>> Why the syntax is there at all is to provide fast
>> (faster) access to the vector data type which has
>> other time and space properties than do lists.
>
> ABSOLUTELY NOT.
>
> For example, in C++ you have vectors and lists, but
> you don't have any literal syntax for them.
>
> You can have fast and slow data structures without
> having any literal syntax for it.
>
> Why do you keep confusing the two concepts?

The original question was why there is a special
syntax for vectors, even as lists are perfectly fitted
to be vectors.

The question was not why there are lists AND vectors.
But that issue is also interesting so that discussion
wasn't wasted on anyone who read it (perhaps).

As for the syntax, the "literal"

    [1 2 3]

is a faster and more readable way than

    (vector 1 2 3)

to tell the computer when it should use what, because
the computer isn't advanced enough to figure this out
on it own.

> For a higher fee, I guess we could even provide
> a 60's job. For example, we could find a remote
> COBOL job, and provide it to a programmer with punch
> card/printer interfaces.

If we did this good enough to a guy who recently had
a car crash and lost his memory for a couple of weeks,
probably he wouldn't mind if his new life was better
than his old...

    You know, I know that this steak doesn't exist.
    I know when I put it in my mouth, the Matrix is
    telling my brain that it is juicy and delicious.
    ... Ignorance is bliss. (Cypher)

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Barry Margolin]

In article <mailman.491.1445056308.7904.help-gnu-emacs@gnu.org>,
 Emanuel Berg <embe8573@student.uu.se> wrote:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
> 
> >> Why the syntax is there at all is to provide fast
> >> (faster) access to the vector data type which has
> >> other time and space properties than do lists.
> >
> > ABSOLUTELY NOT.
> >
> > For example, in C++ you have vectors and lists, but
> > you don't have any literal syntax for them.
> >
> > You can have fast and slow data structures without
> > having any literal syntax for it.
> >
> > Why do you keep confusing the two concepts?
> 
> The original question was why there is a special
> syntax for vectors, even as lists are perfectly fitted
> to be vectors.
> 
> The question was not why there are lists AND vectors.
> But that issue is also interesting so that discussion
> wasn't wasted on anyone who read it (perhaps).
> 
> As for the syntax, the "literal"
> 
>     [1 2 3]
> 
> is a faster and more readable way than
> 
>     (vector 1 2 3)
> 
> to tell the computer when it should use what, because
> the computer isn't advanced enough to figure this out
> on it own.

Which is similar to the reason why we have literal lists:

    '(1 2 3)

when you could just use

    (list 1 2 3)

Literals are just a convenience feature. When arrays were added to 
MacLisp, they didn't have a literal syntax. Common Lisp added the syntax 
#(1 2 3) for them (and a more general syntax for multi-dimensional 
arrays). Common Lisp also added a syntax for structure literals.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>>> Why the syntax is there at all is to provide fast
>>> (faster) access to the vector data type which has
>>> other time and space properties than do lists.
>>
>> ABSOLUTELY NOT.
>>
>> For example, in C++ you have vectors and lists, but
>> you don't have any literal syntax for them.
>>
>> You can have fast and slow data structures without
>> having any literal syntax for it.
>>
>> Why do you keep confusing the two concepts?
>
> The original question was why there is a special
> syntax for vectors, even as lists are perfectly fitted
> to be vectors.

You did it again.  You are asking why apples are of a certain color,
even as peaches have a kernel.

The two things are totally unrelated.


> The question was not why there are lists AND vectors.

If the question excludes this, then then original question is "why there
is a special syntax for vectors?".  And I gave you the answer: because
otherwise you would have to build vectors are run-time using a more
complex expression and a more complex algorithm.  Also, the compiler
couldn't perform the optimization it is allowed to perform on literal
objects, namely coalescing of equal literals, and storing them in ROM.


> But that issue is also interesting so that discussion
> wasn't wasted on anyone who read it (perhaps).
>
> As for the syntax, the "literal"
>
>     [1 2 3]
>
> is a faster and more readable way than
>
>     (vector 1 2 3)
>
> to tell the computer when it should use what, because
> the computer isn't advanced enough to figure this out
> on it own.

I don't know what you mean by "this" in "figure this out on its own".

The speed is irrelevant here, there are semantic differences:

(setf print-circle t)
(loop repeat 3 collect [1 2 3])        --> (#1=[1 2 3] #1# #1#)
(loop repeat 3 collect (vector 1 2 3)) --> ([1 2 3] [1 2 3] [1 2 3])


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> You are asking why apples are of a certain color,
> even as peaches have a kernel.

OK - why is that?

> I don't know what you mean by "this" in "figure this
> out on its own".

As I know you know, there are languages (e.g., SML)
that do have types but still it isn't compulsory to
spell them out in the code. The types are instead
inferred, "leaving the programmer free to omit type
annotations while still permitting type checking." [1]

> The speed is irrelevant here, there are semantic
> differences:
>
> (setf print-circle t) (loop repeat 3 collect [1 2 3])
> --> (#1=[1 2 3] #1# #1#) (loop repeat 3 collect
> (vector 1 2 3)) --> ([1 2 3] [1 2 3] [1 2 3])

It is since several posts clear that lists and vectors
are two different general-purpose data structures,
with different properties with respect to access times
and memory allocation policy, and also with different
methods to interact with the data - because they are
different types.

In particular, the vector is a 1-dimensional array,
and not an implementation/tool to specifically do
linear algebra or any other math or science discipline
that uses vectors as the modeling building blocks.
This is not to say that cannot happen, just as it can
happen with lists being the base data structure.

[1] https://en.wikipedia.org/wiki/Type_inference

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> You are asking why apples are of a certain color,
>> even as peaches have a kernel.
>
> OK - why is that?


Because the presence of a data type in a language is unrelated to the
presence of a syntax for literal objects of that type.

For example, in lisp, there is a syntax for a list data type.

But there is no list data type in lisp! 
Non-empty lists are actually cons cells, 
and the empty list is actually a symbol!

And in emacs lisp, there's a buffer type, but there's no literal syntax
for buffers objects!

    Syntax:        Type:
    -------        -------
    (1 2 3)        No type
    [1 2 3]        vector
    No syntax      buffer
(And of course, you have the case:
    No syntax      No type
for nothing).

So all the combinations are possible, which shows that having a literal
syntax for objects and having types in a language are two totally
unrelated things.



>> I don't know what you mean by "this" in "figure this
>> out on its own".
>
> As I know you know, there are languages (e.g., SML)
> that do have types but still it isn't compulsory to
> spell them out in the code. The types are instead
> inferred, "leaving the programmer free to omit type
> annotations while still permitting type checking." [1]

Again, you are confusing everything.  This type inference has nothing to
do with what has been discussed so far, this is yet another totally
unrelated thing.

Type inference let the compiler infer the type of the _variables_, so
you don't have to declare the type of the _variables_.  

But in lisp, variables are not typed, it's the values that are typed,
therefore type inference is mostly useless.

Type inference can still be useful in a lisp compiler, since it allows
to produce code that is a little more efficient: you can avoid
generating type dispatches and type checks in expressions using a
variable, when you can infer that this variable will always hold values
of a certain type.

For inference, writing

    (let ((a (vector 1 2 3)))
       (aref a 2))

    (let ((a [1 2 3]))
       (aref a 2))

have the exact same effect: in both case the compiler can infer that a
is always bound to a vector of 3 elements, and therefore it can avoid
testing whether 2 is bigger or smaller than the size of the vector, or
that the value bound to a is indeed a vector before calling aref.

In the case of emacs lisp since aref can be used with the disjoints data
types: vector, string, char-table, bool-vector and byte-code, there are
actually five different aref functions!  The aref function must test the
type of the first argument, and depending on this type, it calls one of
the five type-specific aref functions.  With type inference, it could
call directly the aref for vectors.

But as you can see from the two examples above, this has absolutely
nothing to do with literal syntaxes or the existance of a given data
type.



>> The speed is irrelevant here, there are semantic
>> differences:
>>
>> (setf print-circle t) (loop repeat 3 collect [1 2 3])
>> --> (#1=[1 2 3] #1# #1#) (loop repeat 3 collect
>> (vector 1 2 3)) --> ([1 2 3] [1 2 3] [1 2 3])
>
> It is since several posts clear that lists and vectors
> are two different general-purpose data structures,
> with different properties with respect to access times
> and memory allocation policy, and also with different
> methods to interact with the data - because they are
> different types.

Why are you writing this paragraph in the context of an example showing
only vector objects?

You are completely blind, you didn't realize what happened there.

In the first case, since [1 2 3] is one single literal object, it is
always this single literal object that is collected.  We obtain
therefore a list containing three times this very same single literal
object, which is represented with the #=/## syntax.

In the second case, since (vector 1 2 3) is an expression that builds a
new vector, called 3 times it will produce 3 different vectors!  And
therefore we obtain a list with 3 different unrelated vectors.


In the first case, since we have a list of literal vectors, we cannot
modify thse literal vectors (the single unique literal vector), without
obtaining nasal daemons.  So instead I will produce a list containing
three times the same mutable vector unique, to show you what happens
when we modify a slot in the first vector of the list:

    (let* ((unique (copy-seq [1 2 3]))
           (vs (loop repeat 3 collect unique)))
      (setf (aref (elt vs 0) 0) 0)
      vs)
    --> (#1=[0 2 3] #1# #1#)

    (setf print-circle nil)
    (let* ((unique (copy-seq [1 2 3]))
           (vs (loop repeat 3 collect unique)))
      (setf (aref (elt vs 0) 0) 0)
      vs)
    --> ([0 2 3] [0 2 3] [0 2 3])
          *       *       *

Since we have a unique single vector, when we modify it, we see the
modification in all the occurences of the very same single vector.

On the other hand, in the second case, where we have tree different
vectors, if we modify the first slot of the first vector, then only the
first vector is modified, and the modification is seen only in the first
vector which is different from the two others:

    (let ((vs  (loop repeat 3 collect (vector 1 2 3))))
      (setf (aref (elt vs 0) 0) 0)
      vs)
    --> ([0 2 3] [1 2 3] [1 2 3])
          *       *       *

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Because the presence of a data type in a language is
> unrelated to the presence of a syntax for literal
> objects of that type. ...
>
> So all the combinations are possible, which shows
> that having a literal syntax for objects and having
> types in a language are two totally
> unrelated things.

They are two different things but they are not
unrelated. If a language offers features A, B, and C,
then it should come in with a syntax a, b, and c to
facilitate the usage of them features.

> Type inference can still be useful in a lisp
> compiler, since it allows to produce code that is
> a little more efficient: you can avoid generating
> type dispatches and type checks in expressions using
> a variable, when you can infer that this variable
> will always hold values of a certain type.
>
> For inference, writing
>
>     (let ((a (vector 1 2 3))) (aref a 2))
>
>     (let ((a [1 2 3])) (aref a 2))
>
> have the exact same effect: in both case the
> compiler can infer that a is always bound to
> a vector of 3 elements, and therefore it can avoid
> testing whether 2 is bigger or smaller than the size
> of the vector, or that the value bound to a is
> indeed a vector before calling aref.

Inference can be based on the methods used to interact
with the object of the variable. For example the
predicates. If there is an `if' form with a predicate
test for a string (`stringp') and then an `error' if
the variable doesn't hold the string, depending on the
context and the sophistication of the inference
mechanism, it can be deducted the function should be
used with a string as value for a particular argument.
But again this is nothing I ever yearned for...

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> Because the presence of a data type in a language is
>> unrelated to the presence of a syntax for literal
>> objects of that type. ...
>>
>> So all the combinations are possible, which shows
>> that having a literal syntax for objects and having
>> types in a language are two totally
>> unrelated things.
>
> They are two different things but they are not
> unrelated. If a language offers features A, B, and C,
> then it should come in with a syntax a, b, and c to
> facilitate the usage of them features.

We agree, but you don't seem to realize the number of programming
languages that don't respect this rule.

And even lisp, for example, doesn't have a literal syntax for a lot of
lisp data type, such as hash tables or CLOS objects.  I mentionned emacs
lisp buffers, but a lot of emacs editing data structures don't have any
literal syntax.

There are still constructors and accessors to manipulate those types, at
run-time.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> And even lisp, for example, doesn't have a literal
> syntax for a lot of lisp data type, such as hash
> tables or CLOS objects. I mentionned emacs lisp
> buffers, but a lot of emacs editing data structures
> don't have any literal syntax.

Most likely the need for such syntax is proportional
to the frequence by which the feature is used.
Interestingly this is how this whole thread started.
I thought the vectors of Lisp were for Linear algebra
and the special syntax stroke me as very uncalled for
and out of place, ~equivalent to bash or zsh having
a special char to denote the imaginary unit of complex
numbers! Now that I know it isn't so I don't think the
syntax is bad. Actually, I'm curious about CL and
using the industrial Lisps to do "real" programs,
where types, data structures, memory usage, come to
play once again. That was always present in C and C++
but all this Elisping has made them wane. It is
probably a good thing, at least in the setting of
Emacs and how I and most people (I think) use it.
But it is always interesting to do new things. One can
dream...

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Robert Thorpe]

Emanuel Berg <embe8573@student.uu.se> writes:
> Now that I know it isn't so I don't think the
> syntax is bad. Actually, I'm curious about CL and
> using the industrial Lisps to do "real" programs,
> where types, data structures, memory usage, come to
> play once again.

There's one thing that Pascal didn't mention directly....  In some cases
having literal syntax in Lisp is more important than in other
languages.  In Lisp we have the function "read" which can read in
anything that has a read syntax.  Let's say you have a program that has
an data file format.  That file can be stored using "print" and
read-back using "read".  For example, configuration could be stored as a
list.  That list could contain other lists, strings and vectors.  Read
and print eliminate the need to write a parser.  As a side-effect they
may make the file human readable.  That makes having a vector or array
syntax more useful.  Let's say the program is a CAD package and it's
storing a 3D model.  That would use a lot of arrays.  If Lisp had no
literal array syntax then lists would have to be used, then converted to
arrays later.  That could be very inefficient for large models.

Another issue is code generators.  Often they produce tables that are
best stored in arrays.  Take parser generators for example.  Let's say a
lisp dialect has the syntax (v '(1 2 3)).  The function "v" means turn
the following list into an array.  For human usage that would be fine,
the delay in translating lists to arrays would be small.  But, for
generated code it could be a problem.  Last time I looked, the parser
generators for C++ used C arrays because C++ lacks literal array syntax
for C++ arrays.

BR,
Robert Thorpe

Re: why are there [v e c t o r s] in Lisp?

[Barry Margolin]

In article <mailman.557.1445177952.7904.help-gnu-emacs@gnu.org>,
 Emanuel Berg <embe8573@student.uu.se> wrote:

> I thought the vectors of Lisp were for Linear algebra
> and the special syntax stroke me as very uncalled for
> and out of place,

It's curious that you would think that a language primarily intended for 
programming an EDITOR would have a feature for linear algebra.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Barry Margolin <barmar@alum.mit.edu> writes:

> It's curious that you would think that a language
> primarily intended for programming an EDITOR would
> have a feature for linear algebra.

Because of the name! Nothing else.

I've never seen "vector" in programming having this
meaning. In OpenGL (GLSL) there were (is) a vector
type but I thought of that as dealing with
math/graphical vectors, not to store arbitrary data:

    /* https://www.opengl.org/wiki/Data_Type_(GLSL) */
    vec4 someVec;
    someVec.x + someVec.y;
    
But if I *now* may think about it further, it is not
that strange a thought.

Emacs was never a minimalist system so I'm not
surprised to find anything in it. (Or surprised to
think I found something, in this case.)

Also, no matter how useful it (Emacs) might be to
writers, journalists, and basically anyone who thinks,
reads, and writes, I suppose it still has its
stronghold with programmers and science people.
And linear algebra, isn't that the math discipline
which is closest to computer science? (Along with
automata theory and discrete math, perhaps.)

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Random832]

Emanuel Berg <embe8573@student.uu.se> writes:
>
> Because of the name! Nothing else.
>
> I've never seen "vector" in programming having this
> meaning. In OpenGL (GLSL) there were (is) a vector
> type but I thought of that as dealing with
> math/graphical vectors, not to store arbitrary data:

C++ is another example of a language which has a "vector" type for
the purpose of storing arbitrary data. So does Java, though its use
is discouraged (for technical reasons relating to threading
synchronization overhead) in favor of ArrayList.

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> And even lisp, for example, doesn't have a literal
>> syntax for a lot of lisp data type, such as hash
>> tables or CLOS objects. I mentionned emacs lisp
>> buffers, but a lot of emacs editing data structures
>> don't have any literal syntax.
>
> Most likely the need for such syntax is proportional
> to the frequence by which the feature is used.

Yes.  There is also some historical reasons, the older the type, the
best/more literal syntax it has.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: why are there [v e c t o r s] in Lisp?

[Barry Margolin]

In article <87pp0eckss.fsf@kuiper.lan.informatimago.com>,
 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote:

> Emanuel Berg <embe8573@student.uu.se> writes:
> > Why the syntax is there at all is to provide fast
> > (faster) access to the vector data type which has
> > other time and space properties than do lists.
> 
> ABSOLUTELY NOT.
> 
> For example, in C++ you have vectors and lists, 
> but you don't have any literal syntax for them.
> 
> You can have fast and slow data structures without having any literal
> syntax for it.
> 
> 
> Why do you keep confusing the two concepts?

When he said "faster access", I think he just meant that the syntax 
makes it more convenient to use them, not that the code runs faster.

Like the way Javascript's object literals make it very easy to use them 
to implement named options to functions, rather than putting this into 
the basic argument processing syntax like Lisp and Python do.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Barry Margolin <barmar@alum.mit.edu> writes:

> When he said "faster access", I think he just meant
> that the syntax makes it more convenient to use
> them, not that the code runs faster.

Yes :$

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Barry Margolin]

In article <mailman.428.1444957396.7904.help-gnu-emacs@gnu.org>,
 Emanuel Berg <embe8573@student.uu.se> wrote:

> One of the things I like the most with Lisp is the way
> it is typed and written. It is just so much more
> enjoyable both to type and read. And otherwise
> interact with (e.g., the help). Long words are
> prefered, with everything spelled out - compare
> `gnus-action-message-log' to the argc, argv, etc.
> of typical C! Also dashes instead of the ugly
> underscore, which is less readable, and slower as well
> (two keys instead of one for the dash) - and then to
> think of the worst case, the CamelCase of Java (no pun
> intended - still, better keep the sick bags nearby!).
> And then while not exactly ugly, who needs the curly
> braces to delimit functions (virtually all other
> languages, apparently), or for that matter the square
> brackets of array indexes and iteration? Or the
> semi-colon to delimit expressions and statements?
> They are just a bit tricky to type (except for the
> semi-colon) and they make the code look like an
> anthill - for no reason as Lisp shows. But there is
> one thing that clouds the perfect sky - vectors.
> I realized this when I was thinking about this. Why is
> there a special syntax for vectors? In linear algebra,
> an n-dimensional vector is a sequence of n numbers,
> and collectively they make for something that has
> direction and magnitude (in particular, it doesn't
> have a position). But whatever the math, isn't that (a
> sequence of numbers) something that the lists of Lisp
> can handle just as well, or actually better, as it
> will be more generic (a lot of stuff that doesn't work
> on "real" Lisp vectors will work on vectors that are
> also lists). And using lists doesn't mean nobody
> cannot write hundreds of "math vector" specific stuff
> to modify those list vectors! Right?
> 
> Have a look:
> 
>     (vectorp [1 2 3]) ; t
> 
>     (vectorp '(1 2 3)) ; nil - really?

Lists and vectors have different performance characteristics. With 
lists, it's easy to insert and delete elements anywhere in the sequence, 
you just add another cons in the cdr chain, but accessing the nth 
element is O(n). With vectors, inserting and deleting is expensive, 
because you have to shift all the following elements over to make room 
(and appending may require moving the whole thing, because you didn't 
allocate enough room in the original location), but accessing the nth 
element can be done in constant time.

So lists are good for flexible data structures that you typically access 
linearly, while vectors are good for random-access data. Also, because 
vectors are stored in contiguous memory, they generally exhibit better 
locality -- this was more important in the days when RAM was expensive 
and limited, because paging was more likely when you had a large working 
set.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Barry Margolin <barmar@alum.mit.edu> writes:

> Lists and vectors have different performance
> characteristics. With lists, it's easy to insert and
> delete elements anywhere in the sequence, you just
> add another cons in the cdr chain, but accessing the
> nth element is O(n). With vectors, inserting and
> deleting is expensive, because you have to shift all
> the following elements over to make room (and
> appending may require moving the whole thing,
> because you didn't allocate enough room in the
> original location), but accessing the nth element
> can be done in constant time.
>
> So lists are good for flexible data structures that
> you typically access linearly, while vectors are
> good for random-access data. Also, because vectors
> are stored in contiguous memory, they generally
> exhibit better locality -- this was more important
> in the days when RAM was expensive and limited,
> because paging was more likely when you had a large
> working set.

Right, the international press is happy with
this answer.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Robert Thorpe <rt@robertthorpeconsulting.com> writes:

> Emanuel Berg <embe8573@student.uu.se> writes:
>> Now that I know it isn't so I don't think the
>> syntax is bad. Actually, I'm curious about CL and
>> using the industrial Lisps to do "real" programs,
>> where types, data structures, memory usage, come to
>> play once again.
>
> There's one thing that Pascal didn't mention directly....  In some cases
> having literal syntax in Lisp is more important than in other
> languages.  In Lisp we have the function "read" which can read in
> anything that has a read syntax.  Let's say you have a program that has
> an data file format.  That file can be stored using "print" and
> read-back using "read".  For example, configuration could be stored as a
> list.  That list could contain other lists, strings and vectors.  Read
> and print eliminate the need to write a parser.  As a side-effect they
> may make the file human readable.  That makes having a vector or array
> syntax more useful.  Let's say the program is a CAD package and it's
> storing a 3D model.  That would use a lot of arrays.  If Lisp had no
> literal array syntax then lists would have to be used, then converted to
> arrays later.  That could be very inefficient for large models.

Indeed, and this is why there are reader macros, print-object, (and also
make-load-form and make-load-form-saving-slots) in CL: the language
doesn't provide a reader syntax for all its data types because there
aren't enough characters in the standard character set ;-) but it
provides the user to define its own reader syntaxes, for predefined lisp
classes and for user defined lisp classes.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk