1

Basic cons-cell sticks together two arbitrary things and is the basic unit that allows a construction of linked lists and arbitrary data objects. Question: is there a reason to stick with this simplistic language design descision (for instance, in all lisp families)?
Why not use fixed length arrays for this purpose (or some nested stacks)? I can't foresee any problems with that, but there are clear advantages of a more "packed" memory, less pointer resolution and less "dead-weight" cons-cells to define hierarchy of the data.

artemonster
  • 744
  • 4
  • 27
  • 6
    Most Lisps will have many data structures not made of cons cells: numbers, symbols, strings, vectors, multidimensional arrays, structures/records, classes/instances, hash-tables, ... – Rainer Joswig Dec 31 '15 at 11:34
  • I don't think set-cdr! would be easy to implement with nested stacks or fixed arrays. You can also build quite a bit more complex structures than linked lists. (Binary trees, random access list, queues and deques) and the implementation such cells in C is straightforward. Representing the code itself in this sort of structure (nested lists) internally also makes it easier to implement a macro system. You can do weird things behind the scenes and still be lispy like clojure does but main reason that it's done there is limitations in the Java VM. – WorBlux Jan 02 '16 at 16:11
  • more importantly, faster access, O(1) or near that. Clojure does that. – Will Ness Jan 10 '16 at 20:24

2 Answers2

3

You have titled your question “Functional Programming: why pair as a basic constructed unit?”, but this title does not reflect correctly the fact that many important and well known functional languages (e.g. Haskell, F#, Scala, SML, Clojure etc.) have either algebraic data types or different collection of data structures, in which the pair is just one of the different type of constructors, if even available. The situation is similar for other multiparadigm languages, that have support for functional programming, like C++, Java, Objective-C, Swift, etc.

In all these cases the pair, if present, is exactly “basic” as an array, a record, or list, or any other type of data constructor.

What is left is the family of Lisp languages, notably Common Lisp and Scheme, that, beside having a rich set of data structures, like those cited in the comment of Rainer Joswig, use the pair for an important task: as basic data constructor to represent programs.

The fact that Lisp code is a s-expression (that is a list of lists and atoms) has foundamental consequences, the most notable of all being the rising of macro systems, that allow programmers to create easily new syntax, or even new domain-specific languages.

Renzo
  • 26,848
  • 5
  • 49
  • 61
2

Renzo's answer about other structures in functional programming is spot on. Function programming is about aligning programming with logic and mathematics, where expressions denote values, and there's no such thing as a side effect. (Of course, in practice, we need side effects for I/O, etc.) Functional programming doesn't require the singly linked list as a fundamental construct.

Lists are one of the things that make Lisps lispy, though. One of the reasons that pairs are so common in the Lisp family of languages may be that ordered pairs are very easy to implement in the lambda calculus that Lisps are inspired by. (I say "inspired by" rather than "based on" because after the syntax and use of lambda to denote anonymous functions, there's plenty of difference, and it's best not to assume that things about one apply to the other.) See the answer to Use of lambda for cons/car/cdr definition in SICP for a quick lesson in how cons, car, and cdr can implemented using nothing but lexical closures.

Community
  • 1
  • 1
Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353