9 ms·

> http://en.wikipedia.org/wiki/First-class_data_type http://en.wikipedia.org/wiki/First-class_data_type Fair enough, pretend I said "first class syntactic obje

> http://en.wikipedia.org/wiki/First-class_data_type http://en.wikipedia.org/wiki/First-class_data_type Fair enough, pretend I said "first class syntactic object." > CL allows you to define libraries that can change even the basic surface syntax, for your convenience. Considering that there is more than enough defined in the specification, what benefits would be in having an "official" hash litteral syntax? Reader macros are powerful, no doubt. The benefit of building this into a language would mainly be syntactic regularity. CL as it stands has keyword args, alists, property lists, and real hash tables (probably amongst other things I don't know about), that all fill basically the same purpose of mapping names to values. If the creators of Common Lisp and its parent lisps had started with hash tables with standard reader syntax, they probably wouldn't have felt the need to introduce so many subtly different but conceptually identical concepts. Lua, for instance, uses its single table data structure both as syntax and as an internal representation for pretty much any case where it needs to map some names to some values; from keyword arguments to environments to "metatables" that provide fairly powerful metaprogramming support, they're all just tables that you can write literally and use the same functions to manipulate. You could say that alists fill this purpose and are even more syntactically regular since they're still sexps, but then why doesn't CL use alists for keyword args, and why don't Scheme's keyword arg extensions use alist syntax? Historical accident, or are alists just ugly? If you can admit that they're a little too ugly and verbose to include in function calls, then maybe you can see why I don't like writing alist literals. > The fact that you are mainly manipulating lists does not mean that everything is eventually represented as supposedly inefficient linked-list at runtime. I'm well aware that a compiler can easily expand keyword arguments into regular ones. I strongly doubt your compiler will transform all the literal alists in your program into hash tables, and replace all the alist-ref functions and so on operating on them with the equivalent hash table functions. As long as alists are more syntactically blessed than hash tables, people will use them where another data structure would be more appropriate.

lispm 13y ago
Assoc lists make little sense as argument lists. Named arguments are basically like property lists. The point of argument lists for functions in Common Lisp is that they enable a contract. This requires special built-in support in the language. I want to see during compile time if an arg is missing or additional. Example: the function WRITE takes several keyword arguments, but not :BAR. The compiler complains about wrong use. * (defun test () (write "foo" :bar 10)) ; in: DEFUN TEST ; (WRITE "foo" :BAR 10) ; ; caught WARNING: ; :BAR is not a known argument keyword. Now if you allow a hashtable or some other data structure to be passed, then it would also be great, if one could specify at definition time which keys it takes, their default values, etc. We also may want to find out which values were default values, and which were actually passed. The keyword argument facility for functions in Common Lisp provides all of that. This allows you compile-time checks for code and makes interfaces easier to use. Common Lisp also allows access to arguments as lists. This is simpler and more Lispy than using hash tables. For most purposes lists are useful enough and hash-tables would just add overhead.
ICWiener 13y ago
> I strongly doubt your compiler will transform all the literal alists in your program into hash tables, Time for experiment. SBCL doesn't, as far as I know. But you seem to imply that it is always better to use hash-tables, and I don't think so (even though hash-table can be implemented in a smart way, like in Lua). Under roughly 10 elements, alist result in shorter code. (defun my-fun (x) (declare (optimize (speed 3) (debug 3) (safety 0)) (type (member a b c) x)) (let ((a '((a . 10) (b . 21) (c . 31)))) (cdr (assoc x a :test #'eq)))) (disassemble #'my-fun) ; disassembly for MY-FUN ; Size: 53 bytes ; 04A7FF2F: 483B1592FFFFFF CMP RDX, [RIP-110] ; 'A ; no-arg-parsing entry point ; 36: 7511 JNE L1 ; 38: 488B0D91FFFFFF MOV RCX, [RIP-111] ; '(A . 10) ; 3F: L0: 488B5101 MOV RDX, [RCX+1] ; 43: 488BE5 MOV RSP, RBP ; 46: F8 CLC ; 47: 5D POP RBP ; 48: C3 RET ; 49: L1: 488B1D98FFFFFF MOV RBX, [RIP-104] ; '(B . 21) ; 50: 488B0D89FFFFFF MOV RCX, [RIP-119] ; '(C . 31) ; 57: 483B157AFFFFFF CMP RDX, [RIP-134] ; 'B ; 5E: 480F44CB CMOVEQ RCX, RBX ; 62: EBDB JMP L0 This is roughly equivalent to a "case" construct (not shown here). Then, this is what I have with a hash-table: (let ((table (make-hash-table :test #'eq))) (declare (optimize (speed 3) (debug 3) (safety 0))) (setf (gethash 'a table) 10) (setf (gethash 'b table) 21) (setf (gethash 'c table) 31) (defun my-fun-hash (x) (declare (optimize (speed 3) (debug 3) (safety 0)) (type (member a b c) x)) (gethash x table))) (disassemble #'my-fun-hash) ; disassembly for MY-FUN-HASH ; Size: 115 bytes ; 05467EB0: .ENTRY MY-FUN-HASH(X) ; (FUNCTION (#) ; (VALUES T # ..)) ; EE8: 8F4508 POP QWORD PTR [RBP+8] ; EEB: 488D65E8 LEA RSP, [RBP-24] ; EEF: 488B7805 MOV RDI, [RAX+5] ; EF3: 4C8BC7 MOV R8, RDI ; EF6: 498BF8 MOV RDI, R8 ; EF9: BE17001020 MOV ESI, 537919511 ; EFE: 488B05FBFDFFFF MOV RAX, [RIP-517] ; #<FDEFINITION object for SB-IMPL::GETHASH3> ; F05: B906000000 MOV ECX, 6 ; F0A: FF7508 PUSH QWORD PTR [RBP+8] ; F0D: FF6009 JMP QWORD PTR [RAX+9] ; F10: 6A20 PUSH 32 ; F12: B9604F4200 MOV ECX, 4345696 ; alloc_tramp ; F17: FFD1 CALL RCX ; F19: 59 POP RCX ; F1A: 488D490B LEA RCX, [RCX+11] ; F1E: E917FFFFFF JMP #x1005467E3A The function with an hash-table has a constant size relatively to the number of elements in the table, which is fully known at compile-time. The size of the code with a case/alist grows linearly with the number of elements. Now, let's compare speed. In the following versions, I have added more elements in the alist, just to be sure the code with an hash-table is the shortest (from 'a to 'l). (time (dotimes (i 10000000) (dolist (x '(a b c d e f g h i j k l)) (my-fun-hash x)))) (time (dotimes (i 10000000) (dolist (x '(a b c d e f g h i j k l)) (my-fun-case x)))) (time (dotimes (i 10000000) (dolist (x '(a b c d e f g h i j k l)) (my-fun x)))) Results: HASH: 2.491 seconds of real time 33,072 bytes consed ALIST: 0.852 seconds of real time 0 bytes consed CASE: 0.778 seconds of real time 0 bytes consed Even though in terms of footprint, the code tend to be larger with alist quite rapidly (10 elements), the resulting code is faster and does not allocate memory. Also, just to clarify, alist and property lists have a different behavior than hash-tables, namely that the sequential access allows you to shadow values from another list: if you write (cons (cons 'a b) older-alist), you have a new list where the value for key 'a is b, and where values for other keys are those found in older-list (even though older-list also contains key 'a). I don't quite remember what is my point anyway ;-) but it was fun to test the different behaviors.

lispm 13y ago

Assoc lists make little sense as argument lists. Named arguments are basically like property lists. The point of argument lists for functions in Common Lisp is that they enable a contract. This requires special built-in support in the language. I want to see during compile time if an arg is missing or additional. Example: the function WRITE takes several keyword arguments, but not :BAR. The compiler complains about wrong use. * (defun test () (write "foo" :bar 10)) ; in: DEFUN TEST ; (WRITE "foo" :BAR 10) ; ; caught WARNING: ; :BAR is not a known argument keyword. Now if you allow a hashtable or some other data structure to be passed, then it would also be great, if one could specify at definition time which keys it takes, their default values, etc. We also may want to find out which values were default values, and which were actually passed. The keyword argument facility for functions in Common Lisp provides all of that. This allows you compile-time checks for code and makes interfaces easier to use. Common Lisp also allows access to arguments as lists. This is simpler and more Lispy than using hash tables. For most purposes lists are useful enough and hash-tables would just add overhead.

ICWiener 13y ago

> I strongly doubt your compiler will transform all the literal alists in your program into hash tables, Time for experiment. SBCL doesn't, as far as I know. But you seem to imply that it is always better to use hash-tables, and I don't think so (even though hash-table can be implemented in a smart way, like in Lua). Under roughly 10 elements, alist result in shorter code. (defun my-fun (x) (declare (optimize (speed 3) (debug 3) (safety 0)) (type (member a b c) x)) (let ((a '((a . 10) (b . 21) (c . 31)))) (cdr (assoc x a :test #'eq)))) (disassemble #'my-fun) ; disassembly for MY-FUN ; Size: 53 bytes ; 04A7FF2F: 483B1592FFFFFF CMP RDX, [RIP-110] ; 'A ; no-arg-parsing entry point ; 36: 7511 JNE L1 ; 38: 488B0D91FFFFFF MOV RCX, [RIP-111] ; '(A . 10) ; 3F: L0: 488B5101 MOV RDX, [RCX+1] ; 43: 488BE5 MOV RSP, RBP ; 46: F8 CLC ; 47: 5D POP RBP ; 48: C3 RET ; 49: L1: 488B1D98FFFFFF MOV RBX, [RIP-104] ; '(B . 21) ; 50: 488B0D89FFFFFF MOV RCX, [RIP-119] ; '(C . 31) ; 57: 483B157AFFFFFF CMP RDX, [RIP-134] ; 'B ; 5E: 480F44CB CMOVEQ RCX, RBX ; 62: EBDB JMP L0 This is roughly equivalent to a "case" construct (not shown here). Then, this is what I have with a hash-table: (let ((table (make-hash-table :test #'eq))) (declare (optimize (speed 3) (debug 3) (safety 0))) (setf (gethash 'a table) 10) (setf (gethash 'b table) 21) (setf (gethash 'c table) 31) (defun my-fun-hash (x) (declare (optimize (speed 3) (debug 3) (safety 0)) (type (member a b c) x)) (gethash x table))) (disassemble #'my-fun-hash) ; disassembly for MY-FUN-HASH ; Size: 115 bytes ; 05467EB0: .ENTRY MY-FUN-HASH(X) ; (FUNCTION (#) ; (VALUES T # ..)) ; EE8: 8F4508 POP QWORD PTR [RBP+8] ; EEB: 488D65E8 LEA RSP, [RBP-24] ; EEF: 488B7805 MOV RDI, [RAX+5] ; EF3: 4C8BC7 MOV R8, RDI ; EF6: 498BF8 MOV RDI, R8 ; EF9: BE17001020 MOV ESI, 537919511 ; EFE: 488B05FBFDFFFF MOV RAX, [RIP-517] ; #<FDEFINITION object for SB-IMPL::GETHASH3> ; F05: B906000000 MOV ECX, 6 ; F0A: FF7508 PUSH QWORD PTR [RBP+8] ; F0D: FF6009 JMP QWORD PTR [RAX+9] ; F10: 6A20 PUSH 32 ; F12: B9604F4200 MOV ECX, 4345696 ; alloc_tramp ; F17: FFD1 CALL RCX ; F19: 59 POP RCX ; F1A: 488D490B LEA RCX, [RCX+11] ; F1E: E917FFFFFF JMP #x1005467E3A The function with an hash-table has a constant size relatively to the number of elements in the table, which is fully known at compile-time. The size of the code with a case/alist grows linearly with the number of elements. Now, let's compare speed. In the following versions, I have added more elements in the alist, just to be sure the code with an hash-table is the shortest (from 'a to 'l). (time (dotimes (i 10000000) (dolist (x '(a b c d e f g h i j k l)) (my-fun-hash x)))) (time (dotimes (i 10000000) (dolist (x '(a b c d e f g h i j k l)) (my-fun-case x)))) (time (dotimes (i 10000000) (dolist (x '(a b c d e f g h i j k l)) (my-fun x)))) Results: HASH: 2.491 seconds of real time 33,072 bytes consed ALIST: 0.852 seconds of real time 0 bytes consed CASE: 0.778 seconds of real time 0 bytes consed Even though in terms of footprint, the code tend to be larger with alist quite rapidly (10 elements), the resulting code is faster and does not allocate memory. Also, just to clarify, alist and property lists have a different behavior than hash-tables, namely that the sequential access allows you to shadow values from another list: if you write (cons (cons 'a b) older-alist), you have a new list where the value for key 'a is b, and where values for other keys are those found in older-list (even though older-list also contains key 'a). I don't quite remember what is my point anyway ;-) but it was fun to test the different behaviors.