Implementing Data Structures with Symbols.

.


Implementing Data Structures with Symbols


Original Lisp had only symbols as atoms. Symbol names, if used on the same way variables are used in mathematics, are flexible enough to support wide variety (all?) data structures.

For instance, matrices 2 x 2 can be implemented with symbols as a11 instead of a[1,1] in some other language, or (a 1 1) in Lisp and names could be created as needed.

The code will be more complicated and less efficient than if matrices are directly supported by language, but neither one is essential problem - complexity of the code can be "abstracted away" with functions, and computational complexity is increased only for factor of constant * log n where n is the number of used symbols (if symbol reaching in Lisp is implemented efficiently.) Newlisp code follows.

(define (matrix-element m i j)
  (sym (append (string m) (string i) (string j))))

(define (set-matrix m m11 m12 m21 m22)
  (for(i 1 2)
    (for(j 1 2)
      (set (matrix-element m i j)
           (nth (+ (* 2 (- i 1)) (- j 1))
                (list m11 m12 m21 m22))))))
  
(define (println-matrix m)
  (for(i 1 2)
    (for(j 1 2)
       (println m "[" i "," j "]=" 
          (eval (matrix-element m i j))))))
          
(define (multiply-matrix a b c)
  (for(i 1 2)
    (for(j 1 2)
      (set (matrix-element c i j) 0)
      (for(k 1 2)
         (set (matrix-element c i j)
              (+ (eval (matrix-element c i j))
                 (* (eval (matrix-element a i k))
                    (eval (matrix-element b k j)))))))))

(set-matrix (quote X) 1 2 3 4)
(set-matrix (quote Y) 2 3 4 5)
(multiply-matrix (quote X) (quote Y) (quote Z))
(println-matrix (quote Z))

---------------------------
Program output

Z[1,1]=10
Z[1,2]=13
Z[2,1]=22
Z[2,2]=29


4 comments:

  1. Erlang, which derives its basic syntax directly from Prolog, uses syms exactly like that, as meaningful entities, which in other langs would be implemented with vars, or strings.

    E.g. messages between erlang processes are passed as symbols.

    I do not see why meaningful syms cannot be used in other languages, too.

    You are perfectly right.

    ReplyDelete
  2. I got this comment privately from anonymous commenter. As it contributes to discussion, and there is no explicit confidence requirement I decided to publish it. Commenter can contact me if he objects to publishing.

    ---

    Erlang, which derives its basic syntax directly from Prolog, uses syms exactly like that, as meaningful entities, which in other langs would be implemented with vars, or strings.

    Eg messages between erlang processes are passed as symbols.

    I do not see why meaningful syms cannot be used in other languages, too.

    You are perfectly right.

    ----

    ReplyDelete
  3. I could probably tell even more:
    Erlang uses syms as meaningful semantic entities not only because it follows tradition from Prolog (in 'logical_programming' it's kind of natural to have syms stand for words, as it basically manipulates 'predicates'). Syms are naturally immutable, created once and never changed, and in Erlang it serves a purpose, eliminating potential conflicts in parallel distributed computing - no chance that the same var gets assigned to in different places dragging into the pot all kinds of race conditions and need for locks.

    In Newlisp which allows sending serialized content to remote instances for remote evaluation, it may make full sense too - when Newlisp uses Erlang-like programming.
    Now with 'messaging' btw parent and child added, this interesting way to architect programs becomes available to Newlisp too, and who knows, messaging with lists of syms (instead of lists of vars or lists of constant strings) might make sense.

    Basically, syms with meaningful names are just one more kind of entities, and whether and how to use them depends probably on how convenient they are to manipulate - with the bulit-in means a given language provides.
    (i.e. how easy it is to match them, compare on their names - or whether one would need to cast syms into strings to do recognition and manipulation etc. etc.)

    But inherent immutability is one more reason to view syms as more than named placeholders for values, as vars do.

    p.s. i am 'unixtechie' at newlisp forum. i post anonymously because i dislike the idea that my wanderings around the Net should be easily tracked by god knows whom, for god knows what purposes, and forever.
    So i just did not enter my auth credentials when posted my first comment

    ReplyDelete
  4. More of the same commenter:
    ---
    I could probably tell even more:

    Erlang uses syms as meaningful semantic entities not only because it follows tradition from Prolog (in 'logical_programming' it's kind of natural to have syms stand for words, as it basically manipulates 'predicates'). Syms are naturally immutable, created once and never changed, and in Erlang it serves a purpose, eliminating potential conflicts in parallel distributed computing - no chance that the same var gets assigned to in different places dragging into the pot all kinds of race conditions and need for locks.

    In Newlisp which allows sending serialized content to remote instances for remote evaluation, it may make full sense too - when Newlisp uses Erlang-like programming.
    Now with 'messaging' btw parent and child added, this interesting way to architect programs becomes available to Newlisp too, and who knows, messaging with lists of syms (instead of lists of vars or lists of constant strings) might make sense.

    Basically, syms with meaningful names are just one more kind of entities, and whether and how to use them depends probably on how convenient they are to manipulate - with the bulit-in means a given language provides.
    (ie how easy it is to match them, compare on their names - or whether one would need to cast syms into strings to do recognition and manipulation etc. etc.)

    But inherent immutability is one more reason to view syms as more than named placeholders for values, as vars do.
    ---

    ReplyDelete