# 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:

```repl
> 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:

```descript
//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:

```repl
> 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.

```descript
//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:

```repl
> 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:

```descript
Add[left, right].

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

Add[left: 3, right: 2]?
```

evaluated:

```repl
> descript-cli eval Primitive.dscr
5
```

### Modules

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

```descript
//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:

```repl
> 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.

```descript
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:

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

but it can also be compiled:

```repl
> 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