What's new in Tridash 0.5

Recently I released version 0.5 of the Tridash programming language. You can read more about why I wrote Tridash in my previous post. This post provides an overview of the new features this version brings.

Official website: https://alex-gutev.github.io/tridash/

Improved Semantics

This version brings a significant refinement to the semantics of the language.

Non-Strict Evaluation Strategy

The previous version did not have a formal evaluation strategy. Generally all nodes were strictly evaluated, that means their values were always computed, with some special exceptions made for if, and, or expressions. The new version formalizes a non-string evaluation strategy for all nodes, which means the value of a node is only computed if it is actually used, and the special exceptions have been removed. if, and, or are now ordinary functions (meta-nodes).

A strictness analysis phase determines whether the value of an argument to a function is always used and thus may be evaluated prior to being passed to the function. This is an optimization step which allows arguments to be by value which is more efficient than passing a thunk which computes the value later.

The new evaluation strategy also allows for proper tail-call elimination of any function call in tail position. This means a constant amount of stack space is used regardless of the depth of the recursion. Coupled with strictness analysis, this ensures that a constant amount of stack space is used by arguments which serve as accumulators.

Failure Values

Failure values are a special class of values which trigger a failure of the current operation, when evaluated. When a function argument, which evaluates to a failure, is evaluated, the evaluation of the function is terminated and a new failure value is returned. Failures are used to represent the absence of a value, failure of an operation or special classes of values such as the empty list.

The idea behind using a special failure value is that the main application logic can focus on the actual computation taking place without having to check whether an error occurred. Instead the error handling code can be separated from the main application logic.

Example

Consider that an integer needs to be parsed from an input x. The parsed integer value is then used in some computation, for simplicity let's say we add 1 to the value and display the result. An integer value is parsed from a string with the int function.

int(x) + 1 -> output

If an integer cannot be parsed from the string value entered in x, the int function returns a failure value. As a result the evaluation of int(x) + 1 will also result in a failure value, and no output being displayed.

To display an error message, prompting the user to enter a correct value, we simply need to check whether output evaluates to a failure. The fails? function returns true if its argument evaluates to a failure:

if(fails?(output), "Please enter a valid integer!", "") -> error

The node error evaluates to the string "Please enter a valid integer!" if the node output evaluates to a failure, which happens when an integer cannot be parsed from x, otherwise it evaluates to the empty string.

Failure values may also have an optional type which allows the cause of the failure to be distinguished.

Handling Failures with Explicit Contexts

Each binding is established to a particular context of a node. This version allows this context to be specified explicitly using the @ operator. The left-hand side of the operator is the node and the right-hand side is the context identifier, which can be any valid identifier.

When a multiple bindings are established to the same context, the bindings established later in the source code are only activated if the result of all previous bindings is a failure value. This is the means by which failures are handled.

Example

x -> y @ c

1 -> y @ c

In the example, above, node y is bound to the value of x in the explicit context with identifier c. If x evaluates to a failure value, the next binding in the context is activated thus y is set to the value 1.

Variants of the @ operator allow a binding to be activated only if it is of a particular type.

List Data Structure

A linked list data structure was added. The list is also used to represent the argument list, of functions taking a variable number of arguments, and is used to represent Tridash expressions when passed to macros.

The empty list is represented by a failure value with a special type Empty. Representing the empty list as a failure value simplifies the implementation of certain list processing functions.

Example: Implementation of map

map(f, list) :
    list !- cons(f(head(list)), map(f, tail(list)))

The !- function checks whether the first argument evaluates to a failure value, if so the failure value is returned otherwise the value of the second argument is returned. In the example, above, if list is empty it will evaluate to the failure value with type Empty thus this value is returned from the function. Otherwise a new list is created with apply f on the first element of the list and applying f on the remaining elements of the list, using a recursive call to the map function.

Macros

A function can be marked as a macro. As a result the function is invoked at compile-time with the arguments being the raw expressions rather than the computed argument values. The return value of the function is interpreted as a Tridash expression which replaces the macro expression. Identifiers are represented by a special symbol type and function call expressions are represented by a list with the function/operator in the first element of the list and the arguments in the remaining elements. This representation is heavily inspired by the representation of S-Expressions in the Lisp languages.

Macros can be used to extend the language in ways which is not possible with simple functions.

Example: Implementation of <- macro

<-(a, b) : list(&(->), b, a)

This allows bindings to be specified in the reverse order, e.g. x -> y can be specified as y <- x.

The & operator is a special operator that returns the node object, at compile-time, for a given node which can then be substituted in an expression returned by the macro function. In the example above, the -> meta-node is returned, thus the expression returned by the <- function is an expression of the -> operator.

Another form of macros are offered, in which a bind -> expression with a function expression on the right-hand side, can be replaced by a set of one or more bind expressions. This is used in pattern matching.

Pattern Matching

A new unique form of pattern matching is added in version 0.5. Nodes can be matched to patterns by specifying a binding with the pattern (a function expression) on the right-hand side of the -> operator. The source node, on the left hand side of ->,  is then matched to the pattern. Matching of a pattern means that the argument nodes of the pattern are bound to values for which the function returns a value that is equivalent to the source node. If there is no such value, the argument nodes evaluate to failures.

Example

x -> int(y)

Node y is bound to the value of x if x is an integer, otherwise it evaluates to a failure.

Example

x -> list(1, int(y), z)

This example demonstrates constant patterns, and nested patterns. Nodes y and z are bound to the second and third elements of the list stored in x, if the value of x is a list of three elements, of which the first is the number 1 and the second is an integer. Otherwise both y and z evaluate to failures.

Multiple binding patterns involving a single argument node can be established, in which case the node evaluates to the value corresponding to the first pattern that matched.