Daft

For the language named "da f t", see BIX Queue Subset.

Daft - multi-paradigm, logical, meta-programming language.

A language that falls into logical language category (as Prolog), but with functional and imperative features. It gives a programmer impression that he is coding in a functional/imperative language, while still everything is evaluated as in logical languages.

Daft is founded on a non-classical logic.

Main Features

• The language is homoiconic, which means the same data type is used for data and for code, enabling natural inspection and reflection capabilities.

• It is also homogenous, which means the same code concepts are used for all programming tasks, from the highest to the lowest level.

• The basic data structure is a mapping, which is extensional, that means any two objects yielding the same content are equal.

• There is no syntax difference between retrieving data from a mapping and calling a function.

• There are no reserved words. Any valid identifier may be used as a variable name. All language statements live in their own namespace and do not clash with user identifiers.

Logical features

• Each statement may succeed or fail. This is a concept similar to assertions and exceptions in other languages.

• The execution is based on a boolean-valued logic, which means there are different degrees of success and failure.

• Statements may be combined using all logical connectives, including negation and alternative. This gives the programmer ability to write incomplete and not fully specified functions. This also naturally allows to express "undefined behavior".

• A programmer may (and should) write specifications, functions that accept other functions and test them for certain properties.

• There is a feature central for logical languages: to make generate a function from its specification. This step is non-computable in general case.

• Each value and data type is a boolean value. That means, any two values may be taken conjunction, alternative and any value may be negated, yielding some other value.

Metaprogramming features fall into logical features category.

• A programmer can assert certain properties of a function, i.e. that it returns the result of some type.

• A programmer can even check certain properties of the assertions, i.e. if they are complete, that means only one function satisfies it.

• A complete series of assertions is called a specification.

• The specification may be used to check whether the function is correct.

• The specification may also be used to generate a function that satisfies them. This step is manifestly uncomputable. However, it can be solved in some simple cases.

• A programmer may write his own generators that yield functions from specifications.

• The compiler may also generate a function partially, that means to generate a function skeleton with some calls to nonexistent functions that it can not generate. The base function is valid if the child functions are valid. The compiler can generate specifications of the child functions. It is the role of the programmer to implement those.

• When checking functions against specifications, the operation of the compiler is analogous to a model checker. When generating functions from specifications, it is analogous to a theorem proover. When generating functions with unresolved external calls, it is analogous to a proof assistant.

Functional features

• The basic programmer's task is to define immutable values (constants) and functions returning values. There is no semantic difference between defining a constant and a function returning a constant. Both constructs may be used interchangebly.

• A variable has only one value inside a function. That means, every variable is immutable. This is the basic feature of functional languages.

• A variable however may be initialized implicitly. For example, if the variable a already has a value, then the variable b may be defined using a statement like: "a = b + 1". This will be transformed by the compiler to the explicit form: "b = a - 1".

• Under the hood, the compiler tries to find a valuation for all variables to satisfy all of the statements inside a function so that the whole function succeeds. This is an operation of a logical language. For the programmer it looks however as an operation of a functional language.

• Variables are implicitly bound by an existential quantifier by default. However there is a "for" statement which acts as a general quantifier. It's operation is similar to the "for loop" from imperative languages.

Objective features

• There language has a type hierarchy with subtyping, similar to that of object-oriented languages.

• The type system forms a lattice, that means there is a top type (supertype of all types, called usually "object" in most languages) and a bottom type (subtype of all types, usually called "void" or "null" in most languages). Any two types have a common supertype and a subtype.

• While in usual objective languages subtyping is based only on the existence of particular fields (TypeA is a subtype of TypeB only if it has all the fields of TypeB) with an optional covariance and contravariance (a type particular field of TypeA may be a subtype or supertype of the type of the respective field of TypeB), then the type system of the Daft language is much more rich. It is based on satisfying logical conditions. Type is a logical formula that tests if a particular value belongs to the respective type. One type is a subtype of another type if its formula implies the formula of the other type.

• Types are defined as functions that accept argument of any type and succeed or fail, depending on whether the argument belongs to the type being defined.

• The top type is equal to the value of "true" (a function that returns "true" for any input) and the bottom type is equal to "false" (the function that returns "false" for any input).

Imperative features

• Assertions on imperative features are evaluated in linear temporal logic.

• Operation of a program is based on events (also called signals) and handlers (also called slots).

• A programmer defines bindings (also called connections) between events and handlers.

Syntax outline

Comments and whitespace

• Daft is a free-form language, that means it ignores whitespace.
• Multi-character operators and reserved words must not contain whitespace inside.
• Any text after a hash character ("#"), not inside a string, is a comment until the end of the line.
• Any text inside delimiters consisting of a slash and a hash (opening: "/#", closing: "#/"), is a comment.
• A 'structured' comment may be created using the token "/#/" then taking curly brackets "{", "}". All content between the curly brackets is a comment. The content must satisfy certain syntax conditions:
  • Hash symbol ("#") and the comment tokens ("/#", "#/") form "embedded comments". Content inside such comments is not interpreted in any way.
  • Single quotes ' ' and double quotes " " must appear in pairs and must not contain newlines inside. These are called strings. Quotes inside embedded comments don't count.
  • All kinds of brackets ( ), [ ], { } must match correctly. Brackets inside strings or embedded comments don't count.

Identifiers and reserved words

• Valid characters in identifers are: lowercase and uppercase letters ("a"-"z", "A"-"Z"), underlined space sign ("_"), dollar sign ("$") and digits ("0"-"9"). Any valid character string not starting with a digit may be used as an identifier.

• All reserved words start with an exclamation mark ("!").

• Reserved words never clash with identifiers.

• An identifier may also be created by preceding a quoted string by an exclamation mark: (!'identifier', !"identifier"). In this case, any character may be included (!"~!@#$%^&*()`").

Built-in constants and literals

• Top and bottom boolean values: !true and !false

• Integers: 0, 1, 2, 7, 99

• Non-decimal and explicit-base integers:
  • binary: 0b10, 0b0010111, 0b11111, 0b100000001
  • octal: 0o12345670, 0o102050, 0o23457341
  • decimal: 0d1234567890, 0d234792340
  • hexadecimal: 0x123456789abcdef0, 0xa2f3e23a4b964c230

• Fractions:
  • implicit-base decimal: 0.12349, 3.1415926
  • binary: 0b0.00101
  • octal: 0o0.653401
  • explicit-base decimal: 0d0.12349
  • hexadecimal: 0x0.a321f01

• Strings (both delimiters are equivalent): 'a', 'abcD', "boob", "Alice". Strings must not contain newlines. There are no escape sequences.

Collection literals

• Lists: created with square brackets, items delimited by comma. Items may have 3 variants.
  • Simple items, just the value itself. The value will be accessible under the numeric argument equal to its position in the list.

    [ 1, 2, "abc", 0b10.01, 2, 1 ]

  • Key-value pair, separated by a colon. Key may be any type except a number. Values will be accessible under their numeric position and under the key as well. Keys must not appear twice.

    [ 'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6 ]

  • Identifier-value pair, separated by an assignment character. Values will be accessible under their numeric position and also under the string key derived from the identifier. Keys must not appear twice.

    [ a=1, b=2, c=3, d=4, e=5, f=6 ]

  • All these variants may be mixed in one list. Keys must not appear twice, including matching string and identifier pairs (i.e. ['a':1, a=2] is illegal).

    [ 1, b=2, 'c':3, 4, e=5, 'f':6 ]

• Sets: created with curly brackets, items delimited by comma. There may be multiple occurences of a key. Order doesn't matter.

{ 1, 2, "sss", !false }

• General mappings: created with curly brackets, key-value pairs separated by a colon, delimited by a comma. Keys must appear only once.

{ 1:"a", 2:"b", "zzz":0 }

Functions

Functions are created using curly brackets {}. Between them, statements are embedded, terminated by a semicolon. The semicolon allows to distinguish function definitionss from set constructors. Expression may be any value of any type or a special construction allowed only in functions.

{ 1; !true; { 1, 2 }; }

Inside a function, a keyword !arg may be used, meaning the function argument during a call. A function has always exactly one argument. Multi-argument functions are emulated using lists and mappings. Zero-argument functions are emulated using !false value.

Classes

Classes are created using !class keyword, followed by any value or function. Inside a class, a programmer may use keywords !self, !parent and !type.

• !self lets the object reference itself.
• !parent lets the object reference the parent object.
• !type lets the object reference its class (constructor).

!self and !parent identifiers also have special fields !parent and !type.

• !self.!parent is equivalent to !parent.
• !self.!type is equivalent to !type.
• !parent.!parent references parent of the parent object of the current object.
• !parent.!type references the class of the parent object.

!class { !true; !self; !parent; 1; }

Object creation

Objects (class instances) are created by calling the relevant class with some arguments.

constructor = !class { !arg[0] + 2; };
instance = constructor[1];

Function calls

Function calls are performed using square brackets, together with other symbols: fun[arguments]

There are 4 types of function calls:

• fun[*arg] - Direct argument call, the most basic variant.
• fun[] - No-argument variant, equivalent to fun[*!false].
• fun[arg0, arg1, arg2, ...] - Call-with-list variant, equivalent to fun[*[arg0, arg1, arg2, ...]]. All list variations are allowed.

Collection builders

Collection builder is a shorthand for calling a function on a collection of arguments, then grouping the results into a collection.

• [ * fun : collection ] - result is a list (basic variant), collection must be a list
• [ * fun1:fun2 : collection ] - result is a list (extended variant), collection must be a list
• { * fun : collection } - result is a set, collection must be a set
• { * fun1:fun2 : collection } - result is a mapping, collection must be a set

Field lookup

Field lookup is a special kind of function call:

• fun.field - equivalent to fun[*'field']

Operators

• All operators are binary unless specified.
• All operators are left-associative unless specified.
• There is a category of relational operators that are not associative. Instead a construction of the form: "a OP b OP c;" is transformed to the form: "a OP b; b OP c;".
• There are 'expression operators' that join expressions and yield expressions and 'statement operators' that join statements and yield statements.

Expression operators

Arithmetical

• unary postfix ` (prim)
• ** (power, right-associative)
• unary - (negativity)
• * (multiplication)
• / (real division)
• // (floor division)
• % (modulo)
• + (addition)
• - (subtraction)
• unary + (identity function, only for syntax purposes)

Lists

• unary -: (reversed list)
• unary +: (list with removed duplicates)
• /: (sorted list, right argument is the sorting order predicate)
• :: (list concatenation)
• &: (filtered list, right argument is the selector)
• unary *: (transform a set into a set of single-item lists of the set elements)
• *: (cartesian product, arguments are sets, result is a set of lists)
• %: (quotient set, right argument is an equivalence relation)

Collection relations

• <: (left is element of codomain of right)
• >: (right is element of codomain of left)
• <=: (subset, relational)
• <<: (proper subset, relational)
• !<: (not a subset, relational)
• >=: (superset, relational)
• >>: (proper superset, relational)
• !>: (not a superset, relational)

Boolean

• unary ~ (negation (NOT))
• & (conjunction (AND))
• ~& (negated conjunction (NAND))
• | (alternative (OR))
• ~| (negated alternative (NOR))
• ^ (exlusive disjunction (XOR), equivalent to the negated equivalence, but not relational)
• ~^ (negated exlusive disjunction, equivalent to the equivalence, but not relational)
• => (implication, right-associative)
• !=> (negated implication, right-associative)
• =< (reverse implication, right-associative)
• !=< (negated reverse implication, right-associative)
• <=> (equivalence, relational)
• <!=> (negated equivalence, relational)

Equality and ordering

• == (identical, relational)
• !== (not identical, relational)
• = (equal, relational)
• != (not equal, relational)
• < (less, relational)
• >= (not less, relational)
• > (greater, relational)
• <= (not greater, relational)

Statement operators

• /!/ (negation)
• juxtaposition (not really a symbol, equivalent to conjunction)
• && (conjunction)
• || (alternative)
• ^^ (exlusive disjunction, xor)
• !&& (negated conjunction)
• !|| (negated alternative)
• !^^ (negated exlusive disjunction, equivalence)
• ==> (implication)
• !==> (negated implication)
• ==< (reverse implication)
• !==< (negated reverse implication)
• <==> (equivalence, negated xor)
• <!==> (negated equivalence, xor)

Statements and expressions

• Expression is a syntactic structure composed of literals, operators and function applications.
• Statement is a syntactic structure composed of expressions, terminated with a semicolon.
• Statements may be joined into compound statements.
• Statements may be turned into expressions - function definition is exactly this.
• The whole program is a statement.

More formally:

• Every literal is an expression.
• Operator applied to some expressions is an expression.
• Function name applied to some arguments (which must be expressions) is an expression.
• Expression terminated with a semicolon is a statement.
• 'Statement composing operator' applied to some statements is a statement.
• Statement fenced with curly brackets is an expression (this is a function definition).

Semantics

Daft is a logical language, though it tries to syntactically mimic imperative, functional and object-oriented languages.

Variables

Variables are identifiers that can be assigned values.

Variables have their scope, that means, the same identifier may designate different variables depending on the context.

Variables come in two forms: "normal" and "loop". Normal are declared using '!var' keyword and are bound by existential quantifier. Loop are declared within '!for' loop and are bound by general quantifier.

Assertions

Assertion is a statement that produces a boolean result. Since every value in Daft may be used as boolean, any statement may be an assertion. Assertions may succeed if the resulting value is considered true or fail if it is considered false.

Assignments

Assignment is a special form of an assertion that contains a variable.

Code samples

!var x;
x = 2 + 2;

!var x;
4 = x + 2;