A Haskell Programmer Tries to Learn Racket

Anything that increases the already considerable weirdness of http://www.twitch.tv/directory/all can't be bad. ;)

Going a little Abelson&Sussman, the utility of cons persists because it is a powerful abstraction. Fitting into registers was, as a scholastic might say, an as accidental feature as the input line voltage of a toaster [110 @ 60Hz makes things easier in this part of the world but isn't intrinsic to making crisp English muffins].

cons is useful for dealing with linked memory structures, including singlely linked lists and particularly singly linked lists where the stored value in each list element is a pointer because it abstracts over all the pointers. Writing code to process and manipulate and pass pointers is idiomatic in C. Using pointers is idiomatic Lisp.

Your barfing code shows why cdr and car persist. They are also powerful abstractions due to their rules of combination and probably because their rules of combination aren't constrained by a bias toward English language. There ain't no synonyms for "caddr" and "cdddr" in English or Python.

The idea that lists should be everywhere replaced by structs is assembly in any language thinking (also known as C). Lists provide a standard interface. Each struct definition creates a new data type.

It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. Alan J. Perlis, Epigram 9.

Show me a language with >1 implementation where at least two are completely compatible. Common Lisp has one of the best track records in this aspect. C, C++ and JavaScript are all far worse.

To a man with a Haskell all the world is a nail...and every nail has a type and requires a special hamner. I.e.:

    (define side-effect (cons print "This is not an IO monad"))

    (define its-already-generic (cons number->string 4))

The more I think about Lisp the more I believe that the best reference language is C. [1] Lisp took form as a first step away from assembly, not a first step toward the singularity. What is garbage collection but some lazy programner automating memory management?

The mistake is to take the ideological fanaticism of Lispheads for ideological purity of the language. There is none. Even the great schism of Lisp1 versus Lisp is rooted largely in arguments from precedent...and precedent for Lisp is largely that it can shave a few precious bytes and register loads by allowing a single symbol to point to more things.

[1] Or Cobol.

> 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]         ; #
     ;      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.