Inf / Array

array

Ziele

  1. foundation
    • collection framework, via arrays
    • query sprache
    • brauchen wir objectIds, wenn wir nur immutalbe objects haben
    • computational approach: inbuilt things are cheap, not like a semantic equal on functions!
    • problem with datastructures: array (Prolog, StandardML Lists) can be simulated by functions, but costs are different! costs depend on mutable objects are different for single update or array copy ⇒ what is functional cost?
  2. semantische db, sql Mängel
    • Namen für Joins mit leichter wiederverwendbarkeit
    • Datentypen im LegoSystem (z.B. Tupel überall wo ein atomic value erlaubt ist, Operationen auf allen TupelElementen mit bestimmten Datentype, NamensPattern usw..), Metadaten Operationen
    • ddl, constraint language ⇒ immutable objects
    • eigentlich möchten wir ein Array Syntax entwickeln, aber mit Rekursion können wir alles machen! Wir bräuchten also (fast) ebenso mächtige Alternative anstelle der Rekursion!
  3. Problems
    • Rekursion über list enthält implizit Reihenfolge - das ist aber meist überspezifiziert!
      • pick random function
      • pick random und reduce/combine wie in java streams
      • oder split: sum = fun(a) if size(a) = 0 then 0 elif size(a) = 1 then a[0] else b = split(a); sum(b[0]) + sum(b[1]); endFun
    • aber rekursion ist einfacher: sum = fun(a) if size(a) = 0 then 0 else a[0] + sum(a[1..]); endFun
    • oder funktional sum = fun(a) iterate(0, e → e[0], +)
      • where = fun(f) = iterate([], e → if f(e) then [e] else [] endIf endFun, &)
    • eigentlich gilt da auch schon für Array, meist brauchen wir container ohne Reihenfolge
    • update of singel element ==> fun(a, i, e) sub(a, 0, i) & [e] & sub(a,i+1, size(a)) endFun ist einfach, aber vielleicht brauchen wir das als elementarOperation?

Syntax

  • U = Universe of base type values including (disjoint)
    • Bool = {true, false}
    • Integer
  • V = Values: U plus tuples and functions: disjoint Union (of minimal closure)
    • U
    • Arr = Arrays = V*
    • Fun = Functions
  • Arr: a ∈ Arr ⇔
    • size(a) ∈ Nat,
    • a[i] ∈ U for i ∈ [0, size(a)-1]
    • [u0, u1, ... un-1] ∈ Arr with [..., ui, ... ][i] = ui
    • concat
    • sub(a, b, e) = subarray von [a[b], ..., a[e-1]]
  • Fun defined by the following recursive syntax for fun
    • fun = fun(newVar*) e endFun
    • p = u | var | ( e ) | p( e* ) | p? [ e* ] | if e then e else e endIf | fun
    • u = constant from U
    • e = p | op e | e op | e op e | forward newVar+ | newVar = e | e ; e
    • op = operands including
      • usual operands for Bool and Int
      • & for array concatenation
      • lifting operators to arrays mittels syntax oder explizite Funktionen? a = b ⇒ fun(a,b) if size(a) <> size(b) then false elif size(a) = 0 then true else a[0] = b[0] and eq(sub(a, 1), sub(b,1)) endIf
      • firstNE = fun(a, b, op, ee, aLo, bLo) laEq = fun(i) if i >= size(a) or i >= size(b) then i-1 elif a[i] <> b[i] then i-1 else laEq(i+1) endFun; l = laEq(0); if l >= size(a) then if l >= size(b) then ee else aLo endIf else if l>=size(b) then bLo else op(a[l], b[l]) endIf
    • predefined functions
      • size: Arr → Nat
      • sub: Arr × Nat × Nat → Arr: subarray
      • isBase, isArray, isFun: U → Bool
      • operators can bee used as functions, if syntax allows both, operator is preferred -- how implement overloaded operators on base types?
      • args: Fun → Nat number of arguments

variables

  • variable are immutable, instanciated by assignment or function call
  • variables nested by function scope, including formal parameters
  • variable scope: procedure nested (algol like)
  • forward: use only after definition (function call, not definition, d.h. rekursiv alle forwards aufgelöst - ist x=fun spezialfall oder nicht?)

List

List: null oder

  • ele: List → V
  • next: List → List
  • List: U × List → List: Constructor
  • terminating condition
  • array2list = fun(a) if a.size = 0 then List[] else List[a[0], array2list(sub(a, 1))] endIf

ListAlgebra

Operators on List:

  • l is an expression yielding a list
  • f is an expression used as a function with implicit arguments argument l: List
  • l where f:
    fun(lst, f) if args(f) = 1 then
    w1 = fun(l) if l = null then null elif f(l.ele) then List(l.ele, w1(l.next)) else w1(l.next) endIf endFun; w1(lst);
else
    w2 = fun(l, a) if l = null then null else r = f(l.ele, a); if r[0] then List(l.ele, w2(l.next, r)) else w2(l.next, r) endIf endIf endFun; w2(lst, null);
endIf
  • l map f: transform each element
  • l order f: sort
  • l flat
  • l group f: (a group f flat ms) = (a ms) ...
  • l ms: MultiSet tuples [ele, count]
  • l set

Beispiel

  • row_numer() over(partition by p order by o) = fun(lst, p, o) lst group p map (l order o map if a = null then [[0] & l.ele, 0] else [[a[1]+1] & l.ele, [a1]+1] endif) flat

named tuples

  • named tuples: a 'as' '[' newVar (',' newVar)* ']'
  • Suche 1) Variables 2) named Elements (erstes oder eindeutig?)
  • für where usw.: sind fuctions, aber mit implizit parameter von letztem from (oder group by usw.) -- aber braucht 2 Namen, einen für collection, einen für ele, z.B. mit query oder Apostroph, oder Operator ArrayItBelongsTo

Syntax Erweiterung

  • p = .... | p '.' nat | p '.' name | p'[' (string or nat)+ ']'

ddl / constraints

  1. equal immer deep equal, object Identifier of Array is irrelevant!
  2. isSubArray(s, a) ⇔ ∃ p: s = a where p
  3. isSubMulti(s, a) ⇔ ∃ p, o: s = a where p order o
  4. isSubSet(s, a) ⇔ ∃ p: s 2set = a where p 2set
  5. orthogonales Konzept von entity- baseValued und single- multiValued attributes