Table of Contents for Programming Languages: a survey

Chapter : Data

bool

fixed length list (array)

list

S-expression

dict/associative array/hashtable

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

struct/record

enum

http://docs.python.org/dev/library/enum.html

note: this link describes the benefits of enums over just using preprocessor macros, e.g. C #defines: http://codingrelic.geekhold.com/2008/10/ode-to-enum.html

multidim array/table

dataframe

string

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

regex

int, real

arbitrary precision arith

sized vs. mathy numeric types

pattern matching

ML, Haskell

OMeta: parsing on data http://www.vpri.org/pdf/tr2008003_experimenting.pdf

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)
  {
    v.visitIntExp(this);
  }}

class AddExp? extends Expression { Expression e1, e2;

  void accept(ExpressionVisitor v)
  {
    v.visitAddExp(this);
  }}

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) 
  { 
    e.e1.accept(this); 
    System.out.print(" + "); 
    e.e2.accept(this); 
  } } " -- example from nice.sourceforge.net/visitor.html

variable binding within pattern matching

todo: haskell example

e.g. Apple Swift (note this Apple Swift example and some others are from https://developer.apple.com/library/prerelease/ios/referencelibrary/GettingStarted/LandingPage/index.html ):

" 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)")
    }"

Python pattern matching

https://www.python.org/dev/peps/pep-0636/

Specification https://www.python.org/dev/peps/pep-0634/

Motivation and Rationale https://www.python.org/dev/peps/pep-0635/

Tutorial https://www.python.org/dev/peps/pep-0636/

pointer

ADTs

GADTs

'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 http://docs.scala-lang.org/tutorials/tour/case-classes.html

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

possible features:

• constructor parameters are public fields (e.g. scala)

autogenerated methods

Common examples:

• (recursive) structural equality (e.g. in Scala case classes, Haskell derives)
• toString (e.g. in Scala case classes, Haskell derives)
• comparison (e.g. Haskell derives)
• read (e.g. Haskell derives)
• scala case classes: http://docs.scala-lang.org/tutorials/tour/case-classes.html
• haskell derives: https://en.wikibooks.org/wiki/Haskell/Classes_and_types#Deriving , http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/deriving.html

unboxed types

garbage collection

first-class queries

LINQ

first-class functions

relations

first-class types

first-class metaprogrammy stuff

macros, calls continuations, call stacks, ASTs/expressions

Views

Wadler http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps 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 )

  (0..5)>>.say;

(thanks [2])

Lists

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

Dicts

Trees

Graphs

labeled, hyper, etc

..and graph dbs

http://www.hypergraphdb.org/docs/hypergraphdb.pdf

Relations

Strings

ACID databases

transactions

Hierarchical filesystems

cursors

and 'cd' and 'pwd' in filesystems

Block devices

Packets (and packet-switching)

headers

Streams, pipes, channels (and circuit-switching)

seek

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

structs

access (sub)field

iterators

.next()

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

• channels: send every value over a channel.
• callbacks: provide an iteration function which takes a callback function.
• Closures: let a closure return the next value when called.
• Iterators: create a separate iterator type with e.g. HasNext?()/Next() methods.

cons cells

cons, head, tail

S-exprs

other magic methods/protocols

get/set

find

compare-and-swap

match

destructuring bind

todo

datomic?

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

eg http://stackoverflow.com/questions/24700762/or-patterns-in-haskell

Ocaml has them.

pattern synonyms

https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/syntax-extns.html#pattern-synonyms

Haskell has them.

LINQ

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:

• from new_identifier in data_source: data_source is the identifier of the data source upon which the query will be run; new_identifier is the 'range variable' which will be bound to items being queried
  • note: you can have multiple 'from's chained together via a transformation expression in place of data_source, eg "from phrase in phrases; from word in phrase.Split(' ')"
• also 'join', see below

filtering:

• where boolean_expression: filters, accepting only elements for which boolean_expression is true
• OfType?: filters based on the ability of values to be cast to the specified type (note: no C# query expression syntax)
• also 'join', see below

ordering and grouping and partitioning and element operations:

• orderby expression_to_sort_upon (ascending

• reverse: reverse the ordering (note: no C# query expression syntax)
• group expression_on_items by expression_to_group_upon (into new_identifier_for_groups)
  • there is also ToLookup?, which creates a dict of groups instead of a list of groups (note: no C# query expression syntax)
• skip: Skips elements up to a specified position (note: no C# query expression syntax)
• skipWhile: skips while a condition is true (note: no C# query expression syntax
• take: dual of skip; takes elements up to a specified position (note: no C# query expression syntax)
• takeWhile: dual of skipWhile (note: no C# query expression syntax)
• ElementAt?: Returns the element at the specified index
• ElementAtOrDefault?: ElementAt?, or a default value if the index is out of range
• First: the first element of a collection, or the first element that satisfies a condition.
• FirstOrDefault?, Last, LastOrDefault?
• Single: returns the only element of a colletion, or the only element that satisfied a condition
• SingleOrDefault?

joining:

• join new_identifier in data_source on join_expression: introduces a new range variable bound to a new data source like 'from', and then filters the results of both data sources to only those that satisfy join_expression

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

• all: do all of the elements in a sequence satisfy the condition?
• any: do any of the elements in a sequence satisfy the condition?
• contains: does the sequence contain the specified element?

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

• Average, Min, Max, Sum
• Count: Counts the collection, optionally only those elements that satisfy a predicate
  • LongCount? for large collections
• Aggregate: custom aggregation operation

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

• distinct: (like 'uniq')
• except: set difference
• intersect
• union
• Concat: concatenates two sequences

transforming/mapping and projection:

• select map_expression: maps map_expression over the results (used for projection, amongst other things)

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

• DefaultIfEmpty?: if the collection is empty, replaces it with a collection containing a single item, which is the default value of the item type
• Empty: empty collection
• Range: a collection that contains a sequence of numbers
• Repeat: a collection that contains one repeated value

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

• SequenceEqual?: are two sequences equal?

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)
  {
      Console.WriteLine(customerGroup.Key);
      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...

"

Links:

• https://en.m.wikipedia.org/wiki/Language_Integrated_Query
• Introduction to LINQ Queries (C#)
• Getting Started with LINQ in C#
• Language-Integrated Query (LINQ) (C#)
• Standard Query Operators Overview (C#)
• Introduction to LINQ (C#)
• MSDN: LINQ: .NET Language-Integrated Query

SIMD vectors

GCC Vector extensions has:

• Vectors contain power-of-two numbers of items where each item is a basic integer or float type
• Vectors support elementwise +, -, *, /, unary minus, ^,

• Vectors of integers support bitshifts: 1
• For convenience, if a binary vector operation is given a scalar, the scalar is repeated to form a vector
• Vectors support elementwise comparison: ==, !=, <, <=, >, >=
• In C++, vectors support ternary ?, the logic operators !, &&,

• Vectors support a shuffle operation

Unions

Untagged unions

Tagged unions

https://harelang.org/tutorials/introduction/#tagged-unions-in-depth

---

todo: 'fluids' eg https://www.gnu.org/software/guile/docs/master/guile.html/Fluids-and-Dynamic-States.html#Fluids-and-Dynamic-States

---

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

the common ones:

• acyclic (ie you can't make a cyclic data structure)
• flat (ie you can have a composite whose items are scalars (eg a list of integers), but not a composite whose items are other composites (eg a list of lists))
• homogeneous lists (ie you can't have lists whose items are of different types)
• immutable and doesn't contain pointers/references to anything else which is mutable

---

Range

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:

• The range 0..n is the set of indices into a zero-based-indexing array of size n
• You can specify an empty range by making the left and right specifier the same number

---

Using

https://odin-lang.org/docs/overview/#using-statement

---

embed initialization

https://golang.org/pkg/embed/

---

algebraic data types (ADTs)

great explanation of ADTs and their use for "Encoding and Enforcing Invariants in the Type System", with an example, in https://gregoryszorc.com/blog/2021/04/13/rust-is-for-professionals/ section "Encoding and Enforcing Invariants in the Type System".

---

immutable value structs

eg Python's @dataclass

eg Ruby's https://blog.saeloun.com/2022/11/22/data-immutable-object.html

---

Links

• http://canonical.org/~kragen/memory-models/