Om
Main Page

Table of Contents

Introduction

The Om language is:

The Om language is not:

License

This program and the accompanying materials are made available under the terms of the Eclipse Public License, Version 1.0, which accompanies this distribution.

For more information about this license, please see the Eclipse Public License FAQ.

Using

The Om source code can be used for:

Downloading

The Om source code is downloadable from the Om GitHub repository:

Dependencies

Programs

To run scripts which build the dependency Libraries and generate the build project, the following programs are required:

To build the Documentation in the build project, the following additional programs are required:

To ensure that correct programs are used, programs should be listed in the command line path in the following order:

Libraries

The following libraries are required to build the Om code:

Building

A build project, containing targets for building the interpreter, tests, and documentation, can be generated into "[builds directory path]/Om/projects/[project]" by running the appropriate "generate" script from the desired builds directory:

Arguments include the desired project name (required), followed by any desired CMake arguments.

By default, this script automatically installs all external dependency libraries (downloading and building as necessary) into "[builds directory path]/[dependency name]/downloads/[MD5]/build/[platform]/install". This behaviour can be overridden by passing paths of pre-installed dependency libraries to the script:

Interpreter

The Om.Interpreter target builds the interpreter executable as "[Om build directory path]/executables/[platform]/[configuration]/Om.Interpreter". The interpreter:

Test

The Om.Test target builds the test executable, which runs all unit tests, as "[Om build directory path]/executables/[platform]/[configuration]/Om.Test". These tests are also run when building the RUN_TESTS target (which is included when building the ALL_BUILD target).

Documentation

The Om.Documentation target builds this documentation into the following folders in "[Om build directory path]/documentation":

Including

Om is a header-only C++ library that can be incorporated into any C++ or Objective-C++ project as follows:

For more in-depth usage of the library, see the Om code documentation.

Language

Syntax

An Om program is a combination of three elements—operator, separator, and operand—as follows:

program.png

Operator

An operator has the following syntax:

operator.png

Backquotes (`) in operators are disregarded if the code point following is not a backquote, operand brace, or separator code point.

Separator

A separator has the following syntax:

separator.png

Operand

An operand has the following syntax:

operand.png

Functions

The Om language is concatenative, meaning that each Om program evaluates to a function (that takes a program as input, and returns a program as output) and the concatenation of two programs (with an intervening separator, as necessary) evaluates to the composition of the corresponding functions.

Prefix Notation

Unlike other concatenative languages, the Om language uses prefix notation. A function takes the remainder of the program as input and returns a program as output (which gets passed as input to the leftward function).

Prefix notation has the following advantages over postfix notation:

Evaluation

Only the terms (operators and operands) of a program are significant to functions: separators are discarded from input, and are inserted between output terms in a "normalized" form (for consistent formatting and proper operator separation).

There are three fundamental types of functions:

Programs are evaluated as functions in the following way:

For example, program "A B" is the concatenation of programs "A", " ", and "B". The separator evaluates to the identity operation and can be disregarded. The programs "A" and "B" evaluate to functions which will be denoted as A and B, respectively. The input and output are handled by the composed function as follows:

Any programs may be concatenated together; however, note that concatenating programs "A" and "B" without an intervening separator would result in a program containing a single operator "AB", which is unrelated to operators "A" or "B".

Operations

All operation implementations provided are documented in the Operation module.

Data

There are no traditional data types in the Om language: every data value is represented by an operand.

Panmorphism

The Om language uses a unique panmorphic type system, from Ancient Greek πᾶν (pan, "all") and μορφή (morphē, “form”), in which all data values are exposed exclusively through a common immutable interface.

In the case of the Om language, every data value is entirely represented in the language as an operand. Any operation will accept any operand as a valid input and interrogate its data solely through its contained program (a sequence of operator, separator, and/or operand). The operation is then free to process the data however is appropriate, and any operand that it produces as output can then be interrogated and processed by the next operation in the same way.

Implementation

Although any operand can be treated as containing a literal array of operand, operator and/or separator elements, the implementation of operands takes advantage of some optimizations:

Operations in a program can be ordered by the programmer to increase performance by minimizing conversions between program implementations, but it is not necessary for obtaining a correct computation. Where relevant, an operation will document the program implementation types of its inputs and outputs to allow for this optional level of optimization.

Programs

All program implementations provided are documented in the Program module.

Examples

The following program contains a single operand containing an operator "Hello,", a separator " ", and another operator "world!":

The following program contains a single operand containing an operator "Hello,", a separator " ", and an operand "{universe!}" which in turn contains a single operator "universe!":

Note that separators are significant inside operands:

Operands can be dropped and copied via the drop and copy operations:

The drop operation can therefore be used for comments:

The choose operation selects one of two operands, depending on whether a third is empty:

An operation without sufficient operands evaluates to itself and whatever operands are provided:

The quote and dequote operations add and remove a layer of operand braces, respectively:

Operands can be popped from and pushed into:

A new operator definition can be provided with the define operation, where the first operand is treated as containing a Lexicon with operator-to-operand mappings, and the second operand contains the program to evaluate using the defined operator:

Any string can be used as an operator, with separators and operand braces escaped with a backquote:

Unicode is fully supported:

Strings are automatically normalized to NFD, but can be explicitly normalized to NFKD using the normalize operation:

Recursion is very efficient in the Om language, due to (a) the "eager" evaluation model enabled by prefix concatenative syntax (i.e. data is consumed immediately rather than being left on a stack), and (b) the non-recursive evaluation implementation in the evaluator that minimizes memory overhead of recursive calls and prevents stack overflow. The following example uses recursion to give the minutes in a colon-delimited 24-hour time string:

Each step of an evaluation can be represented as a program. The following is the above program broken down into evaluation steps, where the code that is about to be replaced is bold, and the latest replacement is italicized:

The rearrange operation provides operand name binding, allowing for a more applicative style. The following example is a simplistic implementation of a left fold, along with an example call:

define
{
	[Fold]<- {
		rearrange
		{
			rearrange
			{
				dequote
				choose
				quote Result
				pair pair pair {[Fold]<-} Function Result Remainder
				Remainder
			}
			{Result Remainder}
			dequote Function Base <-[terms] Source
		}
		{Function Base Source}
	}
}
{
	[Fold]<- {[literal]<-} {} {1 2 3}
}

The result is {321}.

The example works as follows:

A few things should be noted about the above example:

Contributing

There are several ways to contribute to the Om project:

Developing

Om is written in modern, portable C++ that adheres to the Sparist C++ Coding Standard.

Note: Because this is an early-stage project, there are not yet any compatibility guarantees between versions.

Forking

Om code can be forked from the Om GitHub repository.

Building

See the Using section for instructions on building the code.

Adding or Removing Files

When adding or removing files from source, re-run the "generate" script from the build directory to update the project.

Adding Operations

Additional native functionality can be added to the Om language by implementing new operations in C++.

There are two ways to implement an operation: as a composite operation, or an atomic operation.

To implement a composite operation, or an atomic operation that consumes no operands:

To define an atomic operation that consumes one or more operands:

For any operation implementation, code must be added to the operation header that inserts the operation into the system when the header is included, as follows (where WhateverOperation is a stand-in for the name of the operation class):

namespace {
static Om::Language::System::Definition<WhateverOperation> const theWhateverDefinition;
}

Adding Programs

New data types can be added to the Om language by extending Om::Language::Program and defining the functions necessary to instantiate the class. Use existing programs as a guide.

Program types should be defined in the Om::Language namespace.

Analyzing Code

Some basic free static analysis tools can be applied to the Om code:

Analyzing Test Coverage

The Om.Test target of the Xcode project generates test coverage data that can be viewed as follows:

Submitting Changes

Changes can be submitted to Om via pull request.

Reporting Issues

Issues are reported and tracked with the Om GitHub issue tracker.

Before reporting an issue, please search existing issues first to ensure that it is not a duplicate.

Funding

The Om language is currently a spare-time project of one person. If you would like to speed the development of the Om language in either a general or domain-specific direction, please contact me at information@sparist.com.

References and Thanks

The following additional reading may help explain some of the concepts that contributed to the Om language:

Thanks to all of the people who contributed to: