Table of Contents for Programming Languages: a survey

Chapter : Data


fixed length list (array)



dict/associative array/hashtable

what can be a key? can you add hash fns to custom data?



note: this link describes the benefits of enums over just using preprocessor macros, e.g. C #defines:

multidim array/table



unicode? bytestring?

string interpolation

some syntaxes:

"$x" e.g Perl

"{x}" e.g. Hoon

"%d" % (x) e.g. Python

"\(x)" e.g. Yeti, Apple Swift

`${x + 1}` in Javascript ES6


int, real

arbitrary precision arith

sized vs. mathy numeric types

pattern matching

ML, Haskell

OMeta: parsing on data

in an object-oriented language without reflection or pattern-matching, the only way to make behavior conditional upon object class is through methods (which are polymorphic on the type of the object they are a part of). In such a case, if it is desired for the behavior of a method depend on its arguments, the Visitor pattern can be used (e.g.

" package syntax;

abstract class ExpressionVisitor? { abstract void visitIntExp(IntExp? e); abstract void visitAddExp(AddExp? e); }

abstract class Expression { abstract void accept(ExpressionVisitor? v); }

class IntExp? extends Expression { int value;

  void accept(ExpressionVisitor v)

class AddExp? extends Expression { Expression e1, e2;

  void accept(ExpressionVisitor v)

The interest of this construction is that it is now possible to define operations on expressions by subclassing ExpressionVisitor?. This can even be done in a different package, without modifying the expression hierarchy classes.

Behaviour can now be defined on Expressions

package tools;

class PrettyPrint? extends ExpressionVisitor? { void visitIntExp(IntExp? e) { System.out.print(e.value); }

  void visitAddExp(AddExp e) 
    System.out.print(" + "); 
  } } " -- example from

variable binding within pattern matching

todo: haskell example

e.g. Apple Swift (note this Apple Swift example and some others are from ):

" let size = (20, 40)

    switch size {
    case let (width, height) where width == height:
      println("square with sides \(width)")
    case (1..10, 1..10):
      println("small rectangle")
    case let (width, height):
      println("rectangle with width \(width) and height \(height)")




'pattern matching' is a key operation on these; this is a SWITCH statement on the form of the data ('form' meaning which is the outermost constructor; this is then extended to be a nested top-down pattern from the outermost constructor to some ways in), combined with a destructuring bind in each case.

As a control primitive, pattern matching on ADTs can be thought of as if the nested query on the form of the constructor is a shortcut for a bunch of nested if-thens. Since ADTs and pattern matching are generally seen together in languages, ADTs are closely related to a control structure, too.

case classes

ADTs for OOP

e.g. scala

the point is to be able to perform pattern matching, possibly with guards

possible features:

autogenerated methods

Common examples:

unboxed types

garbage collection

first-class queries


first-class functions


first-class types

first-class metaprogrammy stuff

macros, calls continuations, call stacks, ASTs/expressions


Wadler 1987

Fancy list literals

In some languages, a..b means "the list with every value x such that a <= x <= b, in order". Eg 0..5, eg 'a'..'z', eg 'A'..'Z'

In Perl6, a..b are expanded in place when concatenated with ',', for example a list of the alphanumeric characters may be written ('a'..'z','A'..'Z',0..9) (todo: am i understanding that correctly?)

In Perl6, a..^b is like a..b but with b excluded, ie a <= x < b.

In Perl6, ^x is shorthand for 0..x

In Perl6, lazy list literals can be constructed by putting "... *" at the end. Eg:

 constant fibonacci-list = 0, 1, 1, &[+] ... *;

or, rephrasing &[+]:

 constant fibonacci-list = 0, 1, 1, * + * ... *;

Perl6 has 'deductive lists':

constant powers-of-two = 2, 4, 8, 16, 32, 64 ... *;

In Perl6, lists can be made 'auto-threading' via the '>>' postfix operator.

(thanks [1])

Auto-threading lists

In Perl6, lists can be made 'auto-threading' via the '>>' postfix operator. Eg:

  1. prints the numbers 0..5 each on it's own line,
  2. possibly randomized,
  3. possibly each in it's own thread ( texas version )

(thanks [2])


Lazy sequences

"Lazy sequences are the sort of thing that you don't care about until you need to process a ten-million-line file (or whatever) and suddenly find that your program is slowing down for pointless memory allocations up-front -- then they become unbelievably important. " -- drostie




labeled, hyper, etc

..and graph dbs



ACID databases


Hierarchical filesystems


and 'cd' and 'pwd' in filesystems

Block devices

Packets (and packet-switching)


Streams, pipes, channels (and circuit-switching)


version control

versioned dbs?

also, Multiversion concurrency control (MVCC) as a database implementation technique (vs locking)

versioned dbs that can reconsutruct state as of some point in the past?

storage choices

flat plaintext files that can be version controlled, vs databases

plaintext works esp well for idempotent, journaled, or slowly/rarely concurrently 'mutating' stuff eg accounting, source code

ACID dbs work esp. well for multiuser ACID usage with changes of small granularity

object/relational divide


access (sub)field



in the absence of language-supported iterators, some ways to implement equivalent functionality (quoted and paraphrased from [3]):

cons cells

cons, head, tail


other magic methods/protocols





destructuring bind



patterns and pattern matching on ADTs

view patterns

"a new form of pattern, ... that means apply an "expression to whatever we're trying to match against, and then match the result of that application against the pattern" -- [4]

Haskell has them.

OR patterns


Ocaml has them.

pattern synonyms

Haskell has them.


example in C# (adapted from [5]):

        int[] numbers = new int[7] { 0, 1, 2, 3, 4, 5, 6 };
        // numQuery is an IEnumerable<int>
        var numQuery =
            from num in numbers
            where (num % 2) == 0
            select num;
        foreach (int num in numQuery) {
            Console.Write("{0,1} ", num);

Some LINQ operations

data sources:


ordering and grouping and partitioning and element operations:

descending): sort the results


quantifier operations (note: no C# query expression syntax):

aggregations (note: no C# query expression syntax):

set and other whole-sequence operations (note: no C# query expression syntax):

transforming/mapping and projection:

generation (note: no C# query expression syntax):

comparison (note: no C# query expression syntax):

See [6].

more examples

from cust in customers where cust.City == "London" orderby cust.Name ascending select cust;

queryCustomersByCity is an IEnumerable<IGrouping<string, Customer>> var queryCustomersByCity = from cust in customers group cust by cust.City;

  // customerGroup is an IGrouping<string, Customer>
  foreach (var customerGroup in queryCustomersByCity)
      foreach (Customer customer in customerGroup)
          Console.WriteLine("    {0}", customer.Name);

custQuery is an IEnumerable<IGrouping<string, Customer>> var custQuery = from cust in customers group cust by cust.City into custGroup where custGroup.Count() > 2 orderby custGroup.Key select custGroup;

var innerJoinQuery = from cust in customers join dist in distributors on cust.City equals dist.City select new { CustomerName? = cust.Name, DistributorName? = dist.Name };

" In LINQ you do not have to use join as often as you do in SQL because foreign keys in LINQ are represented in the object model as properties that hold a collection of items. For example, a Customer object contains a collection of Order objects. Rather than performing a join, you access the orders by using dot notation:

from order in Customer.Orders...



SIMD vectors

GCC Vector extensions has:

, &, ~, %


todo: 'fluids' eg


Often in low-level or minimalist languages, one sees constraints on fundamental composite data structures.

the common ones:



When specifying a way to create a sequence of consecutive integers (a range), two common choices are right-exclusive ranges (e.g. 1..3 means 1,2) and inclusive ranges (e.g. 1..3 means 1,2,3).

Inclusive ranges are more intuitive.

Right-exclusive ranges have some advantages:






1. ,