Library, interpreter, and CLI for Descript programming language.

Please see the README at https://bitbucket.org/jakobeha/descript-lang/src/master/README.md

Descript-lang

Simple programming language, work-in-progress.

The name comes from the philosophy that code "describes" what you want the computer to do.

Currently Implemented:

• Information can be encoded multiple ways in a single value.
• Minimal syntax, flexible (like LISP).
• Macros
• Refactoring - being developed alongside an IDE, descript-lang-vscode.

Future Plans:

• Gradual, "ad-hoc" typing
• Strict syntax and semantics, to reduce careless mistakes.

Setup

This is a Stack package. It should be installable via:

> stack install descript-lang

otherwise, clone this repository and install manually.

Examples

Skip to [[Overview]] for specific semantics. These examples are all located in docs/examples (not yet).

Most of these examples should actually compile in the current version of Descript. If not, they should compile in a future version. Any example could be modified in the future as the language develops.

Basic

Here's an example program:

//Records. These are data structures and function signatures.
//These records define natural numbers and addition.
Zero[]. //0 - in other languages this would be an ADT or singleton.
Succ[prev]. //1 + prev - in other languages this would be an ADT, structure, or object.
Add[a, b]. //a + b - in other languages this would be a function.

//Reducers. Reducers are like function implementations. These reducers "implement" Add.
Add[a: Zero[], b]: b //Adding 0 to anything produces 0.
Add[a: Succ[prev], b]: Add[a>prev, Succ[prev: b]] //Adding 1 + n to anything produces n + (1 + anything).

//The main value. In other languages this would be the "main" function.
//When the program is run, it will apply the reducers to this value and output the result.
Add[
  Succ[prev: Succ[prev: Succ[prev: Zero[]]]]
  Succ[prev: Succ[prev: Zero[]]]
]? //This encodes (2 + 3). What does it reduce to?

Assuming the above program is in a file named Basic.dscr, it can be evaluated in a terminal:

> descript-cli eval Basic.dscr
Succ[prev: Succ[prev: Succ[prev: Succ[prev: Succ[prev: Zero[]]]]]]

Types

The above example doesn't include types. Here's another example which does contain types. Notice that this example is exactly the same as the above example with some extra code (the types) added.

//Records. These are data structures and function signatures.
//These records define natural numbers and addition.
Nat[]. //A natural number - in other languages this would be a type.
Untyped[]. //Denotes that a value needs to be typed.
Zero[]. //0 - in other languages this would be an ADT or singleton.
Succ[prev]. //1 + prev - in other languages this would be an ADT, structure, or object.
Add[a, b]. //a + b - in other languages this would be a function.

//Reducers. Reducers are like function implementations. These reducers "implement" Add.
Add[a: Nat[], b: Nat[]] | Untyped[]: Nat[] //Adding naturals produces a natural.
Add[a: Zero[], b]: b //Adding 0 to anything produces 0.
Add[a: Succ[prev], b]: Add[a: a>prev, b: Succ[prev: b]] //Adding 1 + n to anything produces n + (1 + anything).

//More reducers. These reducers aren't really function implementations.
//In other languages, these would assign the types to the instances.
Zero[] | Untyped[]: Zero[] | Nat[] //Zero is a natural. Need `Zero[]` in RHS so it isn't consumed.
Succ[prev: Nat[]] | Untyped[]: Nat[] //1 + n is a natural if n is a natural. Don't need `Succ[...]` in RHS because the only part consumed is the type.

//The main value. In other languages this would be the "main" function.
//When the program is run, it will apply the reducers to this value and output the result.
Add[
  a: Succ[prev: Succ[prev: Succ[prev: Zero[] | Untyped[]] | Untyped[]] | Untyped[]] | Untyped[]
  b: Succ[prev: Succ[prev: Zero[] | Untyped[]] | Untyped[]] | Untyped[]
] | Untyped[]? //What does this reduce to?

This above program evaluated:

> descript-cli eval Types.dscr
Succ[prev: Succ[prev: Succ[prev: Succ[prev: Succ[prev: Zero[] | Nat[]] | Nat[]] | Nat[]] | Nat[]] | Nat[]] | Nat[]

Primitives and Built-ins

Descript has built-in support for basic things like numbers and addition. The following example:

Add[left, right].

Add[left: #Number[], right: #Number[]]: #Add[a: left, b: right]

Add[left: 3, right: 2]?

evaluated:

> descript-cli eval Primitive.dscr
5

Modules

Descript also allows one file to import another, via modules:

//Module declaration.
//If not provided, all files will implicitly have `module <filename>`.
//This is required for a file import other files outside its directory.
module Import

import Base{Add}

Exp2[5]?

evaluated:

> descript-cli eval Import.dscr
25

Compiled

All of the above examples would be considered "interpreted". A Descript program can also be compiled, if you make its main value reduce to code block - a record which represents source code.

import Base

Prgm[statement].
Print[text].

Prgm[statement: Code[lang: "C", content: String]]: Code[
  lang: "C"
  content: App3[left: "int main(string[] args) { ", center: statement>content, right: "}"]
]
Print[text: String]: Code[lang: "C", content: App3[left: "println(\"", center: text, right: "\");"]

Prgm[statement: Print[text: "Hello world"]]?

the above program evaluates:

> descript-cli eval Import.dscr
Code[lang: "C", content: "int main(string[] args) { println(\"Hello world!\"); }"]

but it can also be compiled:

> descript-cli compile Import.dscr

the above command will generate a new file, Import.c. When fed to a C compiler, this will create a simple "Hello world" program.

In the future, the Descript CLI will probably invoke the C compiler itself. Multi-file packages (compiled outputs) will also be implemented.

Syntax Sugar

... TODO Specify - what is the syntax sugar, and how should it be implemented?

Macros

... TODO Describe macros

Overview

See [[Specs]] for a full, more detailed specification.

There are 2 types of expressions - values and reducers. Values are unions of parts. Example: A[] | "B" | C[d: E[]]. There are 2 types of parts:

• Atoms: Numbers, strings. Examples: 4, "Hello", "B".
• Records: These are like records in Haskell - each record has a unique name, and can contain properties, which are other values. Examples: Hello[], Foo[content: 3], A[], C[d: E[]].

Reducers transform values, like functions in other language. Example: Foo[a: Bar[b]]: Baz[c: a>b]. They consist of an input value (Foo[a: Bar[b]]) and an output value (Baz[c: a>b]). Input and output values are special:

• Input values can contain properties without values. An example is the b in Bar[b].
• Output values can contain property paths. An example is a>c in Baz[c: a>c].

A reducer can be applied to a value if its input matches parts of it. The reducer consumes the parts of the value matched by its input, and produces extra parts using its output. Examples:

• Applying Foo[a: Bar[b]]: Baz[c: a>b] to Foo[a: Bar[b: Qux[d: 7]]] yields Baz[c: Qux[d: 7]].
• Applying Foo[a: Bar[b]]: Baz[c: a>b] to 8 | Foo[a: Bar[b: Qux[d: 7]]] | XML[z: 15] yields 8 | Baz[c: Qux[d: 7]] | XML[z: 15].
• Applying Foo[a: Bar[b]] | XML[z]: Baz[c: a>b] to 8 | Foo[a: Bar[b: Qux[d: 7]]] | XML[z: 15] yields 8 | Baz[c: Qux[d: 7]].
• You can't apply Foo[a: Bar[b]] | XML[z]: Baz[c: a>b] to Foo[a: Bar[b: Qux[d: 7]]] (XML[z] doesn't match anything).

Every program contains reducers, and a value called the query. The program is interpreted by taking the query, and applying the reducers to it as much as possible, until no reducers can be applied.

Reducers can also be applied to input and output values - in these cases, the reducers are macros.

... TODO Better overview:

• Improve readability
• Describe how input and output are matched/consumed/produced (preferrably not verbosely?)
• Maybe add record types and injections.