6 ms·

Agreed about linked lists; that virtually all functional languages make them the default/literal data structure is IMO a poor practical design choice (no matter

Agreed about linked lists; that virtually all functional languages make them the default/literal data structure is IMO a poor practical design choice (no matter how theoretically elegant) and is the primary culprit for their reputation for slowness. And the tendency for functional compile-to-JS langs to emulate linked lists in Javascript and keep them the default data structure is downright laughable.

DonaldFisk 10y ago
(Singly linked) lists are a functional data structure. You can manipulate them efficiently without modifying the lists you started with. You can't do that easily with arrays. So if you base your language around arrays, you're better off making it imperative. Lisp predated level 1 caches. I think it's better to design hardware around the software that runs on it (the Burroughs mainframe/Lisp machine approach), than design programming languages around the machines which run them (the C approach). In this case, it means finding a way to make non-local data references more efficient. Lisp's original reputation for slowness predated the use of Level 1 caches, and was because many early implementations ran on interpreters.
- clarkd99 10y ago
  I can 'efficiently modify the lists you started with' with a dynamic multi-type array and I have cache locality and random access. I have a single data structure with an 8 byte overhead, 2 byte overhead per node that can be used as a tuple array with direct lookup, a single linked list, double linked list, a queue, a stack, and a balanced binary search tree. This whole structure is allocated in a single contiguous memory chunk and is cache friendly. It can be serialized and un-serialized without any processing which would be required by a Lisp style linked list even if the list was just moved in memory, saved/restored to/from disk or transmitted to another computer. Lisp DOES predate level 1 cache but we DO have level 1 cache now and it dwarfs all other optimizations on modern computers. Wouldn't it be nice if the hardware was designed to optimize our languages instead of the other way around but I live in this universe rather than an alternate one. What matters is now, not decades ago.
  - DonaldFisk 10y ago
    I'd be interested to learn more about your language. Is there a web page about it, or a paper? Are you the D Clark who's at UCL? The way things are now can be changed. For most applications users care more about response times than CPU clock rates. Hardware has speeded up by several powers of ten (Moore's law) but software has at the same time slowed down (Wirth's law), resulting in little if any net gain, and that has nothing to do with the use of lists: most applications don't use them.
    - clarkd99 10y ago
      David Clark is like John Smith and no, I am not any famous person but I have been around the micro computer world for a very long time (1975). My website is www.rccconsulting.com where you will find an essay on the data structure I mentioned here called SLIST and some documentation and high level design for the system/language I am currently developing called MAX. Users do care more about response times (as you say) and instantaneous and 1/2 instantaneous are considered equal by end users. Most user developed code doesn't need optimization but the data structures that under pin that user code should be as performant as possible, just in case. Designing a language like Lisp or a special purpose language/system like I am creating have design criteria that is much different from the application programmer that is just trying to make stuff work. I have completed at least 1,000 projects big and small as an application programmer, as well as all the system programming I have done so I think I have a good incite into both points of view. >> use of lists; most applications don't use them You may be correct but most programs manipulate variable length character strings whether that is formatting, creating HTML documents, creating JSON data etc. Most currently used programming languages don't do variable length strings either well or efficiently. I also don't like the fact that almost all useful data must be manipulated and stored in database systems that reside somewhere other than my computer. My new system was designed to help solve that problem and more.
      - DonaldFisk 10y ago
        There's already a language called Max: https://cycling74.com/products/max/#.WFRNp-wWVpg https://cycling74.com/products/max/#.WFRNp-wWVpg Your SLIST sounds similar to data structures which go by various names in different languages, e.g. list in Python or ArrayList in Java. Common Lisp vectors support that functionality too. Your VCHAR presumably works in a similar way? I agree ASCIZ is a very inefficient way of representing strings, unless they're guaranteed to be very short.
- smitherfield 10y ago
  I would argue that there's no such thing as a "functional data structure." If a data structure maps poorly to existing functional languages, that's a symptom of an insufficiently powerful and generic type system. Say you have (pseudocode) Array(4 16 5 20) What's its type? Array Array<Int> Array<4> Array<Int 4> Array(Int Int Int Int) None of these lend themselves easily to paradigms other than imperative, true. But this is because they unnecessarily discard known information. The type of an array ought to be itself: assert Array(4 16 5 20) hasType Array(4 16 5 20) => Ok assert Array(4 16 5 20) hasType Array<Int> => Error("Expected Array<Int> but got Array(4 16 5 20). Hint: Typeclass Array<Int> cannot be directly instantiated") assert Array(4 16 5 20) hasTypeclass Array<Int> => Ok Fully functional and referentially transparent.
  - DonaldFisk 10y ago
    And if you want a new array whose first element is increased by one, you either have to allocate space for the entire array, modify the array, or use a different data structure.
    - smitherfield 10y ago
      No you don't, you merely need each index into an array to be a monad over all possible values it can contain. An array is itself and modifications are (take as arguments and return) its indices.
      - DonaldFisk 10y ago
        And how is that implemented under the hood?
        smitherfield 10y ago
        Same as in a higher-level statically typed imperative language: mutable arrays contained within larger dynamic buffers for amoritized constant-time append and prepend.

DonaldFisk 10y ago

(Singly linked) lists are a functional data structure. You can manipulate them efficiently without modifying the lists you started with. You can't do that easily with arrays. So if you base your language around arrays, you're better off making it imperative. Lisp predated level 1 caches. I think it's better to design hardware around the software that runs on it (the Burroughs mainframe/Lisp machine approach), than design programming languages around the machines which run them (the C approach). In this case, it means finding a way to make non-local data references more efficient. Lisp's original reputation for slowness predated the use of Level 1 caches, and was because many early implementations ran on interpreters.

clarkd99 10y ago
I can 'efficiently modify the lists you started with' with a dynamic multi-type array and I have cache locality and random access. I have a single data structure with an 8 byte overhead, 2 byte overhead per node that can be used as a tuple array with direct lookup, a single linked list, double linked list, a queue, a stack, and a balanced binary search tree. This whole structure is allocated in a single contiguous memory chunk and is cache friendly. It can be serialized and un-serialized without any processing which would be required by a Lisp style linked list even if the list was just moved in memory, saved/restored to/from disk or transmitted to another computer. Lisp DOES predate level 1 cache but we DO have level 1 cache now and it dwarfs all other optimizations on modern computers. Wouldn't it be nice if the hardware was designed to optimize our languages instead of the other way around but I live in this universe rather than an alternate one. What matters is now, not decades ago.
- DonaldFisk 10y ago
  I'd be interested to learn more about your language. Is there a web page about it, or a paper? Are you the D Clark who's at UCL? The way things are now can be changed. For most applications users care more about response times than CPU clock rates. Hardware has speeded up by several powers of ten (Moore's law) but software has at the same time slowed down (Wirth's law), resulting in little if any net gain, and that has nothing to do with the use of lists: most applications don't use them.
  - clarkd99 10y ago
    David Clark is like John Smith and no, I am not any famous person but I have been around the micro computer world for a very long time (1975). My website is www.rccconsulting.com where you will find an essay on the data structure I mentioned here called SLIST and some documentation and high level design for the system/language I am currently developing called MAX. Users do care more about response times (as you say) and instantaneous and 1/2 instantaneous are considered equal by end users. Most user developed code doesn't need optimization but the data structures that under pin that user code should be as performant as possible, just in case. Designing a language like Lisp or a special purpose language/system like I am creating have design criteria that is much different from the application programmer that is just trying to make stuff work. I have completed at least 1,000 projects big and small as an application programmer, as well as all the system programming I have done so I think I have a good incite into both points of view. >> use of lists; most applications don't use them You may be correct but most programs manipulate variable length character strings whether that is formatting, creating HTML documents, creating JSON data etc. Most currently used programming languages don't do variable length strings either well or efficiently. I also don't like the fact that almost all useful data must be manipulated and stored in database systems that reside somewhere other than my computer. My new system was designed to help solve that problem and more.
    - DonaldFisk 10y ago
      There's already a language called Max: https://cycling74.com/products/max/#.WFRNp-wWVpg https://cycling74.com/products/max/#.WFRNp-wWVpg Your SLIST sounds similar to data structures which go by various names in different languages, e.g. list in Python or ArrayList in Java. Common Lisp vectors support that functionality too. Your VCHAR presumably works in a similar way? I agree ASCIZ is a very inefficient way of representing strings, unless they're guaranteed to be very short.
smitherfield 10y ago
I would argue that there's no such thing as a "functional data structure." If a data structure maps poorly to existing functional languages, that's a symptom of an insufficiently powerful and generic type system. Say you have (pseudocode) Array(4 16 5 20) What's its type? Array Array<Int> Array<4> Array<Int 4> Array(Int Int Int Int) None of these lend themselves easily to paradigms other than imperative, true. But this is because they unnecessarily discard known information. The type of an array ought to be itself: assert Array(4 16 5 20) hasType Array(4 16 5 20) => Ok assert Array(4 16 5 20) hasType Array<Int> => Error("Expected Array<Int> but got Array(4 16 5 20). Hint: Typeclass Array<Int> cannot be directly instantiated") assert Array(4 16 5 20) hasTypeclass Array<Int> => Ok Fully functional and referentially transparent.
- DonaldFisk 10y ago
  And if you want a new array whose first element is increased by one, you either have to allocate space for the entire array, modify the array, or use a different data structure.
  - smitherfield 10y ago
    No you don't, you merely need each index into an array to be a monad over all possible values it can contain. An array is itself and modifications are (take as arguments and return) its indices.
    - DonaldFisk 10y ago
      And how is that implemented under the hood?
      - smitherfield 10y ago
        Same as in a higher-level statically typed imperative language: mutable arrays contained within larger dynamic buffers for amoritized constant-time append and prepend.