Arc Forumnew | comments | leaders | submitlogin
Unification of tables, lists, and destructuring
2 points by Pauan 4997 days ago | 6 comments
So... this post here (http://arclanguage.org/item?id=4237) made me realize something: we can combine lists and tables into a single datatype... The left side is pgArc, and the right side is the proposal for Arubic:

  (obj x 1 y 2) -> (x: 1 y: 2)
  ((x 1) (y 2)) -> (x: 1 y: 2)
  (x 1 y 2)     -> (x: 1 y: 2)
But... in addition to offering a nice short syntax for tables, it has further benefits. You can now combine tables and lists:

  (= foo '(1 2 x: 3 y: 4))

  (car foo) -> 1
  foo.'x    -> 3
Essentially, this is treating it like an "improper" alist. This also blends nicely with keyword arguments:

  (def foo (a b c)
    (list a b c))

  (foo c: 3 b: 2 a: 1) -> (1 2 3)
And also with destructuring:

  (let '(a b c) '(1 c: 3 b: 2)
    (list a b c))

  -> (1 2 3)
There are still some questions, though... What should the following return?

  (car '(a: 1))
Should it return (a 1) or nil? Or perhaps the symbol 'a? What about the following?

  (let '(a b c) '(1 c: 2 3)
    (list a b c))
Should it return (1 3 2), (1 2 3), or (1 (c 2) 2)? In other words, are the keywords considered a sequential part of the list, just like an alist, or are they considered a separate and unordered thing, like a hash table?

Also, should (a: 1 b: 2) be considered identical to ((a 1) (b 2)), or should it be considered something different, in the same way that alists are different from tables, but serve a similar purpose?

Also, should it be (:a 1 :b 2) or (a: 1 b: 2)? I actually kinda like the former... I think I'll go with that.

Also also, I dislike the idea of introducing syntax that doesn't desugar into S-expressions... so how will that work with this proposal? Perhaps :a could desugar into (keyword a). That poses problems for destructuring, though:

  (let '((keyword a) (keyword b)) ...)

  (let '(:a :b) ...)
Unless I required nested destructuring to be quoted as well... but that would be freaky:

  (let '('(keyword a) '(keyword b)) ...)
Or... perhaps keywords shouldn't work with quote destructuring... in which case there's two alternate proposals:

  (let (keys a b c) foo ...)

  (let '(a b c) foo ...)
The nice thing about (keys) is that it's unambiguous and doesn't cause conflicts with destructuring. The downside is that it's a bit longer, and you can't combine list destructuring with table destructuring in a `let` block. You would need to use `with`:

  (with ((keys a b c) foo
         '(d e f)     foo)
    ...)
Which is pretty ugly. The downside of using '(a b c) to destructure keys is that it causes some tricky questions with regard to mixed-type lists, as I already demonstrated above with (1 c: 2 3)

Oh, by the way, I can also define `keys` so it works with functions too, so you could specify arguments that must be keyword args:

  (def foo ((keys a b c))
    ...)

  (foo 1 2 3)          ; doesn't work
  (foo :a 1 2 3)       ; still doesn't work
  (foo :a 1 :b 2 :c 3) ; this works
The downside is... then you wouldn't be able to use `apply` to generically call any function. For instance:

  (def foo ((keys a b)) ...)

  (def bar args
    (apply foo args))

  (bar :a 1 :b 2) ; doesn't work
So maybe I shouldn't do that. Python gets around this by having a special kwargs argument in addition to rest args, but that approach feels pretty "eh" to me. Seems overly complex for not much benefit.

Oh, that reminds me. How do you guys think keyword arguments should behave with regard to rest args? In the above example, when calling `bar`, it didn't have an `a` or `b` argument, so what should `args` be? Should it be nil, or should it be (1 2)?



2 points by aw 4996 days ago | link

(x 1 y 2) -> (x: 1 y: 2)

Do we need the colons? That is, if we leave them off, is there anything that doesn't work?

Association lists could be (x 1 y 2) instead of ((x 1) (y 2)), and ('(x 1 y 2) 'y) could be implemented to return 2.

I have a hack that implements ('((x 1) (y 2)) 'y) to return 2 so that I can use a!y with association lists; it would work as well if association lists were represented without the extra parentheses.

-----

1 point by Pauan 4996 days ago | link

"Do we need the colons? That is, if we leave them off, is there anything that doesn't work?"

Yes! It's necessary to distinguish between keyword args and normal args:

  (foo x y :a 3 :b 4)
Sure, you could define keyword args to be separate... but I like the idea of unifying them, since they serve such a similar purpose. Plus, I like that there's a syntatic difference between a list that is used for sequential lookup, and a list that's used for key/value lookup. You may disagree.

In any case, you can freely mix alists, plists, plists with keyword symbols, and ordinary tables in your own code. The question of this post is: should keyword plists be supported at all?

I'm leaning toward yes, assuming we can solve the questions I presented. And then, rather than making data types tables, I could make them keyword plists, which is probably better since the number of keys is usually small.

-----

1 point by waterhouse 4996 days ago | link

> Association lists could be (x 1 y 2) instead of ((x 1) (y 2))

Nice, I never consciously realized that. (I suppose we've been seeing it all along in replacing (let ((a 1) (b 2))) with (with (a 1 b 2)), but I never thought about remaking alists that way.) I think the single drawback of actually doing that is that O(n) lookup is now O(2n). [Obviously, if lookup time is a bottleneck, you probably should replace the alists with something else, like... tables! or AVL trees.]

-----

1 point by Pauan 4996 days ago | link

It's an old concept, known as plists[1]. Common Lisp has them, and uses the same syntax that I'm proposing.

By the way, one benefit of alists is that you can iterate over them easier:

  (each '(k v) '((a 1) (b 2) (c 3))
    ...)
Compared to the following, with a plist:

  (each '(k v) (pair '(a 1 b 2 c 3))
    ...)
Which, incidentally, uses `pair` to create an alist, then iterate over that... I was thinking about how to solve this, and figured a form of destructuring might help:

  (each :(k v) '(:a 1 :b 2 :c 3)
    ...)

  ; or this...?

  (each (:k v) '(:a 1 :b 2 :c 3)
    ...)
But that's still kinda up in the air at this point.

---

* [1]: http://www.gigamonkeys.com/book/practical-a-simple-database....

http://www.ida.liu.se/imported/cltl/clm/node108.html

http://www.augustana.ab.ca/~mohrj/courses/common/csc370/lect...

(Search for "property" to jump to the relevant portions.)

-----

1 point by Pauan 4996 days ago | link

Oh! By the way, I could define it so plists work with and without keyword symbols:

  ('(x 1 y 2) 'y)    -> 2
  ('(:x 1 :y 2) 'y)  -> 2
  ('(:x 1 :y 2) ':y) -> 2
This would also let you use arbitrary lists as indexes:

  ('((a b) 1 (c d) 2) '(c d)) -> 2

-----

1 point by Pauan 4996 days ago | link

I'm going to answer my own questions.

  (car '(:a 1)) -> (keyword a)


  (let '(a b c) '(1 :c 2 3)
    (list a b c))

  -> (1 (keyword c) 2)


  (:a 1 :b 2) -> ((keyword a) 1 (keyword b) 2)


  (let (:a :b :c) foo ...)
---

"The downside is... then you wouldn't be able to use `apply` to generically call any function."

Nope. It'll work fine. When a function has rest args, any keyword args that don't match will be passed verbatim into the rest args list. Thus:

  (def foo args args)

  (foo :a 1 :b 2) -> ((keyword a) 1 (keyword b) 2)
If the function doesn't have rest args, then calling it with a keyword arg that it doesn't recognize will result in an error:

  (def foo (a b c))

  (foo :d 1) -> error: invalid keyword argument 'd

-----