wiki:ProgrammersVedanta

Vedanta

The term veda means "knowledge" and anta means "end", together - final knowledge, global optimum, closest possible approximation to Absolute (Truth, which is out there).


If one understands fundmanental underlying principles, one does not have to memorize all the details.

Fundamental notions from Math

Terminology and notation.

Symbols

a human-readable form to represent and bind to (associate with) Values.

Symbols (of an alphabet) are used to represent [concept of] Numbers.

3
1.5

Logically, all occurrences of [symbol] 3 referes to the same singleton which represents the concept of Natural Number 3.

or to establish associations (bindings)

x = 1

many Symbols may be associated with (or bound to) the same value which is called aliasing

y = x

Once bound, Symbols cannot be rebound.

Set

a distinct, homogeneous, possibly infinite group represented as a unit.

  • homogeneous (all elements are of the same kind)
  • un-ordered (has only notion of membership, but no particular order of elements)
  • no duplicate elements

The empty set is a group of 0 elements. The notation is {} .

The empty set could be a memeber of any Set.

Infinite sets

The set of Natural Numbers N

{1, 2, 3, ...}

The set of Integers Z

{... -2, -1, 0, 1, 2, ...}

To implement these we need lazy evaluation.

Set algebra

  • subset
  • proper subset
  • union
  • intersection
  • complement
  • cross product (produces a set of n-tuples)

Multi-sets

a Set which allows duplication of elements is called multiset


Tuple

a finite group of values in a particular order.

  • finite (usually very small)
  • ordered (has notion of a predecessor and successor elements)
  • heterogeneous (values of any kind)
  • allows repeated occurence of elements, like a Multiset

n-Tuple

each size of a Tuple forms its own kind.

a 2-Tuple is called a Pair

(1, 2)

3-Tuple is called a Triple

(1, 0, 1)

The empty tuple or 0-Tuple ()

The beautiful convention in Standard ML to define parameters of a procedure as a Tuple.

fun append([], ys) = ys
  | append(x::xs, ys) = x :: append(xs, ys)

Sequence

generalization of tuples to an ordered collection of elements.

  • membership
  • length (when finite)
  • ordering
  • duplicate elements

Infinite sequences usually called streams and require lazy evaluation

  • Abstraction

wrong or inadequate abstractions is the root of all evil everything is an expression which is reducible to a value every value is a first-class citizen

Types

  • the meta-language of types to define and constraint the data
  • types define distinct sets of atomic or compound values
  • a type is a name (a binding of a symbol) for a distinct set of values (partition)
  • technically - a data-constructor, which returns new value

Function types

  • functions are typed values, like everything else
  • functions (of arity 1) are values of type A -> B
  • each function value is a distinct mapping of values from set A to set B (which could be the same set)
  • a Functor is an even more abstract generalization of a function value

Strong typing

  • every value has a type, type-tags are immutable.
  • no implicit coersions - new values of another type are produced

Structured values

  • a compound value has its own structure - a set of typed slots
  • slots may be named or referenced by an offset (distinct order)
  • when a value has a structure it is defined in its type

Algebraic types

  • a type could have more than one data-constructor
  • which implies that it is non-atomic, it is an algebraic type
  • it is either defined by induction (definition refers to itself) or by defined by enumeration.
  • a value of such type has a distinct behavior or shape

Parametrized types

  • A type of another type. A List of Int. A type is a type.
  • such type defines a common shape of a "class" of compound values
  • Applying a type to another type yields a new distinct type value (int list)
  • technically - a type-constructor, which returns new types
  • such a new type is called a type-value (or an instance) in the meta-language of types.

Recursive types

  • The way of defining a recursive structure by induction.
  • Compositions of itselves. (cons of conses)
  • it is defined by induction - definition that refers to itself (defined in terms of itself).

Type-classes

  • type-classes define behavioral traits (-able)
  • by specifying which a set of interfaces to implement in order to be an...
  • which is a type-signature associated with a name (symbol)
  • such type is called an instance (of a type-class)

Correctness

  • contradictions are ruled out (does not exist)
  • types define "kinds" of the data values (shape, constraints and contracts)
  • A meta-language about expressions and values. (everything)

Modularity

  • the divide and conquer principle
  • modules are for partitioning (via interfaces) and structuring the code
  • divide into sub-problems until each function is well-understood (conquered)

Purity

  • literally nothing could go wrong (the same principles behind logic and math)
  • pure substitution, application of a set of reduction rules
  • the way of evaluation (reduction to a normal-form/value) of logic or math expressions/terms
  • referential transparency, clear separation of side-effects (by strong typing).

Laziness

  • laziness (call-by-name) push abstraction to its limit.
  • laziness imply better abstraction barriers (everything is a "stream")
  • laziness requires purity, laziness and effects does not coincide - they contradict each other.

Data First

  • Once the types are defined the design of the program follows.
  • Data-structures are defined in a meta-languages of types.
  • Algorithms and shape of functions reflect the shape of the data.

Induction

  • Inductive definition - a definition in terms of itself.
  • Recursive definition is a definition by induction.
  • Recursive data (defined in terms of itself) imply recursive processes (which calls itself).

Composeability

  • Pure function composition is the way of creating pipelines.
  • The notion of a Pipeline captures how molecular biology works. Mother Nature "knows" how it is better.
  • Types make sure (guarantee) that everything composes properly.

Functional DSLs

  • a functional meta-language of types (values are types)
  • a functional meta-language of modules (values are modules and bindings)
  • a meta-language of exceptions (a kludge)

String

a specialization of a Sequence to represent strings of an alphabet.

an alphabet is a nonempty finite set.

A = {a,b,c,d,e,f,g.h,i,j,k,lm,n,o,p,q,r,s,t,u,v,w,x,y,z};

A string [closed] over an alphabet is a finite sequence of symbols from that alphabet,

S1 = {h,e,l,l,o};
S2 = {w,o,r,l,d};

which usually written next to one another and not separated by commas.

"hello"
"world"

Language

A language is a Set of [well-formed] Strings.

List

a specialization of a Sequence to represent a arbitraty lists.

it all the notions a Sequence has (implements Interface) the difference is in its representation

[1, 2, 3]

a String could be represented as a List of Characters

['h','e','l','l','o',' ','w','o','r','l','d']

Character Set is a way to define a particualr Encoding of a text

Function

an object that sets up an input-output relationship (transformation).

  • takes an input and produces an output.
  • the same input always produces the same output.

Classic prefix notation is

f(x) = x + 1

where x and f are symbols.

Domain and Range

The set of possible inputs to the function is called its domain. The outputs of a function come from a set called its range.

Such relationsip it is also called a mapping.

The "maps to" notation is

x -> x + 1

This notation is also called an anonymous function.

Defining mappings

The identity function could be defined as

x -> x

The constant function (zero)

x -> 0

Tables

relationship (mapping) could be defined as a table.

immutable tables could be represented as functions.

Arity

The input to f is a k-tuple (a1, a2, ... , ak) and we call the as the arguments to f.

A function with k arguments is called a k-ary function, and k is called the arity of the function.

When n is 1, f has a single argument and f is called a unary function. When n is 2, f is a binary function.

Predicate fuctions

A predicate is a function whose range is {TRUE, FALSE}.

Infix notation

Binary functions (of exactly two arguments) could be written in Infix form with the symbol for the function placed between its two arguments 1 + 2 instead of add(1, 2)

A predicate function whose domain is a set of k-tuples A x x A is called a relation, a k-ary relation, or a k-ary relation on A.

A common case is a 2-ary relation, called a binary relation. When writing an expression involving a binary relation, we customarily use infix notation.

"Less than" is a relation usually written with the infix operation using symbol <. "Equality," is a relation written with the = symbol.

(relational databases)

n-relations are all?/every? and any?/some?

Associativity

Currying

f(x) = | 0 if x == 0
       | x if x < 0
       | x otherwise

Guards


Boolean logic


Fundamental notions from Computer Science

Procedures =

In Haskell the notation for mapping is

\x -> x + 1

In Lisps it is

(lambda (x) (+ 1 x))

Variable number of arguments

Optional parameters

keys

default values

Multimethods

it could have more than one methods, which is called multimethods

dispath is usually based on

  • number of the arguments
  • type of the arguments
  • and pattern matching on values

Pattern matching

functions could be defined using patterns

Abstract Data Types

Abstract Data Type is defined as a Set of procedures whose domain are values of that type.

Interfaces

Named Set of procedures is called interface.

In simple cases a type of a formal parameter could be defined as a Set of all possible values. Parameter list of a procedure could be represented as a Tuple

Protocols

a set of Rules and Constraints is called Protocol.


Last modified 7 weeks ago Last modified on Jan 4, 2020, 6:59:11 AM
Note: See TracWiki for help on using the wiki.