# Delsh

Delsh is a shell language designed to be used with the Doze operating system. It's based on Lisp, and designed for ease-of-use on the command line.

## Lexical Conventions

The following characters are whitespace and not part of any tokens other than string literals: space, horizontal tab, vertical tab, line feed, carriage return.

Line comments can be started with a semicolon, and end once a newline character (either a carriage return or a line feed) is found. Block comments begin with `#|` and end with `|#`.

Delge defines the following punctuation tokens:

```
(     )     '     #     .
```

Identifiers may start with any symbol which is not a decimal digit, whitespace, a semicolon, or a punctuation mark. The following symbols may contain digits. There are currently no reserved words in the language.

String literals are expressed by a set of quotation marks (`"`). Any byte can be put within the quotation marks, including newlines and null terminators. However, a terminal shell should output UTF-8. Escape sequences are defined by using a backslash; and then either an `x` followed by two hexadecimal digits, or a `u` followed by six hexadecimal digits (which will be encoded as a UTF-8 character of the specified code point). The following escape codes are also provided for convenience.

```
\0 - NUL TERMINATOR (0x00)
\n - NEWLINE (0x0A)
\r - CARRIAGE RETURN (0x0D)
\t - HORIZONTAL TAB (0x09)
\\ - BACKSLASH (0x5C)
```

Numbers are represented as a series of decimal digits (0-9), optionally followed by a decimal point and more digits. They may be preceded with a plus or minus sign. Numbers are encoded as a 64-bit decimal number.

## Syntax

The following is the Delsh grammar, represented as EBNF.

```
program = {command}
command = list | statement
statement = atom {s-expression} NEWLINE
s-expression = {prefix} suffix
prefix = "#" | "'"
suffix = list | atom
list = "(" {list-item}  ")"
list-item = s-expression | "."
atom = IDENTIFIER | STRING | NUMBER
```

Note that each item in a program is assumed to be a function call of some kind. If an atom appears at the top level of a program, then it is assumed to be the first item of a list, and will be treated as such until a top-level line feed or carriage return is reached. Note that new lines are allowed inside of s-expressions that are part of an unenclosed command. Newlines will will only terminate a command when they appear outside of an s-expression.

The two kinds of s-expressions are lists and atoms. An atom can be an identifier, a string, or a number. A list is a singly-linked list of cons pairs The `car` (head) of a list will contain a value, and the `cdr` will contain another s-expression. An empty list is replaced with the `NIL` atom. A proper list ends with a node containing its final value as the `car` and `NIL` as the `cdr`. When representing a list as syntax, `(a . b)` creates a list node with `a` as the `car` and `b` as the `cdr`. When there are multiple values with no dot between them, such as `(a b c d)`, a proper linked list will be created as `(a . (b . (c . (d . NIL))))`. It is possible to create an improper linked list by defining several values with no dot, and then ending with a dot, i.e. `(a b c . d)`. It is a syntax error to create a list with more than one dot. A dot must be followed by exactly one s-expression.

An s-expression may be preceded by a pound symbol (#) and a apostrophe ('). A pound symbol must come before an apostrophe. A pound symbol without an apostrophe is a syntax error. An apostrophe is allowed to appear on its own. Using `'` before an s-expression will return the s-expression, rather than the value that the expression evaluates to. Using `#'` before an s-expression will return the function object associated with the s-expression.

## Evaluation

A Delsh program is evaluated by running the `eval` function on each top-level s-expression. The `car` of the s-expression is evaluated to determine the function object that will be called. Each of the elements in the `cdr` are then eagerly evaluated and then passed into the function, left-to-right. If the s-expression is an atom, then nothing will happen. It is an error to use an expression that does not evaluate to a function object as the `car` of a top-level s-expression.

A shell can be implemented by running `(loop (print (eval (read))))`. This creates a read-eval-print loop (REPL). Additionally `read` can be redefined to make pretty prompts and other niceties.

## Builtins

- `atom?`: Returns T if the argument is an atom, and NIL otherwise
- `is?` Returns T if the two atoms are the same atom, and NIL otherwise
- `car`: Gives the first element of a cons pair `(car (1 2)) = 1`
- `cdr`: Gives the second element of a cons pair `(cdr (1 2)) = '(2)`
- `cons`: Creates a cons pair `(cons a b) = '(a . b)`
- `ff`: Ignoring parentheses, returns the first atom `(ff ((a b) c) = a`
- `subst`: Replaces all instances of $1 in $3 with $2
- `equal?`: Returns T if the arguments are the same s-expression
- `null?`: Returns T if the argument is NIL
- `cadr`: `(cadr x) = (car (cdr x))`
- `cdar`: `(cdar x) = (cdr (car x))`
- `caar`
- `cddr`
- `caaar`
- `caadr`
- `cadar`
- `caddr`
- `cdaar`
- `cdadr`
- `cddar`
- `cdddr`
- `append`: Concatenate two linked lists
- `among?`: Checks if $x appears in $y
- `pair`: Zips two lists `(pair (a b c) (w (x y) z)) = ((a w) (b (x y)) (c z))`
- `assoc`: In a list of pairs, gets the value`(assoc 2 ((1 "a") (2 "b") (3 "c")))`
- `sublis`: Replace values in $2 when they appear in the association list ($1)
- `apply`: The 2nd expression is a list of arguments to be applied to the function
- `+`: Adds the arguments `(+ 1 2 3) = 6`
- `-`: Subtracts the arguments `(- 3 1) = 2`
- `*`: Multiplies the arguments `(* 1 2 3) = 6`
- `/`: Divides the arguments `(/ 15 2) = 7.5`
- `%`: Returns the remainder of an integer division `(% 15 4) = 3`
- `sqrt`: Returns the square root of a number `(sqrt 16) = 4`
- `negate`: Returns the additive inverse `(negate x) = (* x -1)`
- `list`: Creates a list `(list a b c) = '(a b c)`
- `quote`: Does not evaluate the s-expression `(quote a) = 'a`
- `if`: If $1 is not nil, evaluate $2, otherwise evaluate $3
- `while` Runs $2 in a loop until $1 is false
- `and`: Returns the first non-nil argument. This short-circuits.
- `or`: Returns the first nil argument. This will short circuit.
- `not`: Returns T if the argument is NIL, otherwise NIL
- `lambda`: Creates a function. ie: `(lambda (x) (+ x 1))`
- `defun`: Creates a named function. ie: `(defun add-one (x) (+ x 1))`
- `set`: Sets the value of an atom
- `read`: Reads an s-expression from the console
- `eval`: Evaluates an s-expression, taking an optional pair list of variables
- `print`: Prints an s-expression
- `loop`: Runs an s-expression in a loop, forever