Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
89 lines (63 sloc) 5.66 KB

path_semantics

A research project in path semantics, a re-interpretation of functions for expressing mathematics

Blog posts:

What is path semantics?

Here is a cheat sheet to show how it looks like: Path Semantics Cheat Sheet

Functional programming has been an active research area for dependently types. In this notation, a new semantics that re-interprets functions takes a step beyond dependently types.

Very briefly, path semantics is about things like:

  • How functions are constructed and connected
  • How to express relationships between functions in a more strict way than equations
  • What can be predicted about output of functions from something about the input
  • What it means to refer to a function (function identity)
  • What you can do with functions, given some class of knowledge about them is available
  • What kind of structures are related to some class of functions

See the wiki for more information.

Why use path semantics?

Some problems require more powerful mathematical tools than others, e.g. AI safety research.
Path semantics grounds meaning in "intrinsic complexity" of functions, similar to computational type theory,
but builds up higher order concepts that stretches into the domain of philosophy.
Therefore, path semantics offers an integrated understanding of semantics spanning a wide area of applications.

An advantage of path semantics is that one can translate to and from other languages.
There are many such "bridges", from Logic to Lojban.
Among the most important connection is between probability theory and computation,
which is formalized in path semantics.

Is this a new programming language?

A new kind of programming language.

The project is about defining a new category of programming languages that satisfy a different method of expression compared to traditional languages. The ideas are original, but inspired by recent advancement in type theory.

Goals:

  • Create efficient algorithms that find paths
  • Find deductive rules
  • Find rules for well formed expressions
  • Find applicable areas (machine learning etc.)
  • Find generalizations (probability theory etc.)

Previous work

Some ideas are taking from unpublished work. I have been asked to publish it but have not gotten time to do it yet.

Earlier, I explored ways to encode information into a generalized version of Adinkra diagrams to model states of discrete systems. The idea is since Adinkra diagrams are constructed by labeling the edges after specific rules, one could extract rules from edges of similar diagrams representing systems.

These diagrams have a reflective property that allows related concepts to be expressed with variations in a systematic way, intuitively described as "context modelling". This background knowledge, together with dependently type experiments, served as rationale for developing the notation.

While suitable to model context in various applications, a problem is super exponential growth in memory usage. Path semantics constructs a space that appear similar to the structure of such diagrams, but compresses the information in a human readable form.

The diagrams have some important properties:

  • Can be described fully using only an array of integers [a, b, c, ...]
  • Uses direct group product as building block [a, b] x [c, b] = [a, b, c, d]
  • The class with lowest complexity, [2, 2, ...], are edges of hypercubes, as in Adinkra diagrams
  • All diagrams are subset of itself in a single dimension [N], which has the highest complexity

For algorithms to compute with these diagrams, see Context in the discrete library.