Formal Languages

Remco Bloemen

2014-02-27

Classical languages

Classically formal languages are serial. Using brackets the language can express hiearchical structures. Using bound variables the languages can contain arbitrary expressions?

Problem areas: complex structures, reflection, self-reference.

Lambda calculus: one can dispense entirely with multiple inputs and multiple outputs by currying the inputs. However, I think this is unnatural.

Proposed alternative

Concepts, applications and definitions.

The fundamental entity of the language is understood as an application (as in “a concept that is applied” not as in a piece of software). An application has a number of arguments and results. Sentences can be constructed by composing applications, one connects all the inputs of the algorithms to the outputs of others.

Well-formed sentences have exactly one output assigned to every input and contain no cycles.

Now that the concept of application is understood, there is a second concept required, that of definition.

A concept