ref: 7f4f1776a930dc9b80f099ca869b0827bbc54383
dir: /doc/lang.txt/
The Myrddin Programming Language
Jul 2012
Updated Dec 2015
Ori Bernstein
TABLE OF CONTENTS:
1. ABOUT
2. LEXICAL CONVENTIONS
3. SYNTAX
3.1. Declarations
3.2. Literal Values
3.3. Control Constructs and Blocks
3.4. Expressions
3.5. Data Types
3.6. Type Inference
3.7. Generics
3.8. Traits
3.9. Packages and Uses
4. TOOLCHAIN
5. EXAMPLES
6. STYLE GUIDE
7. STANDARD LIBRARY
8. GRAMMAR
9. FUTURE DIRECTIONS
1. ABOUT:
Myrddin is designed to be a simple, low-level programming
language. It is designed to provide the programmer with
predictable behavior and a transparent compilation model,
while at the same time providing the benefits of strong
type checking, generics, type inference, and similar.
Myrddin is not a language designed to explore the forefront
of type theory or compiler technology. It is not a language
that is focused on guaranteeing perfect safety. Its focus
is on being a practical, small, fairly well defined, and
easy to understand language for work that needs to be close
to the hardware.
Myrddin is a computer language influenced strongly by C
and ML, with ideas from Rust, Go, C++, and numerous other
sources and resources.
2. LEXICAL CONVENTIONS:
The language is composed of several classes of tokens. There
are comments, identifiers, keywords, punctuation, and whitespace.
Comments begin with "/*" and end with "*/". They may nest.
/* this is a comment /* with another inside */ */
Identifiers begin with any alphabetic character or underscore,
and continue with any number of alphanumeric characters or
underscores. Currently the compiler places a limit of 1024
bytes on the length of the identifier.
some_id_234__
Keywords are a special class of identifier that is reserved
by the language and given a special meaning. The set of
keywords in Myrddin are as follows:
castto match
const pkg
default protect
elif sizeof
else struct
export trait
extern true
false type
for union
generic use
goto var
if while
Literals are a direct representation of a data object within the source of
the program. There are several literals implemented within the language.
These are fully described in section 3.2 of this manual.
In the compiler, single semicolons (';') and newline (\x10)
characters are treated identically, and are therefore interchangeable.
They will both be referred to "endline"s throughout this manual.
3. SYNTAX OVERVIEW:
3.1. Declarations:
A declaration consists of a declaration class (i.e., one
of 'const', 'var', or 'generic'), followed by a declaration
name, optionally followed by a type and assignment. One thing
you may note is that unlike most other languages, there is no
special function declaration syntax. Instead, a function is
declared like any other value: by assigning its name to a
constant or variable.
const: Declares a constant value, which may not be
modified at run time. Constants must have
initializers defined.
var: Declares a variable value. This value may be
assigned to, copied from, and modified.
generic: Declares a specializable value. This value
has the same restrictions as a const, but
taking its address is not defined. The type
parameters for a generic must be explicitly
named in the declaration in order for their
substitution to be allowed.
In addition, there is one modifier allowed on declarations:
'extern'. Extern declarations are used to declare symbols from
another module which cannot be provided via the 'use' mechanism.
Typical uses would be to expose a function written in assembly. They
can also be used as a workaround for external dependencies.
Examples:
Declare a constant with a value 123. The type is not defined,
and will be inferred:
const x = 123
Declare a variable with no value and no type defined. The
value can be assigned later (and must be assigned before use),
and the type will be inferred.
var y
Declare a generic with type '@a', and assigns it the value
'blah'. Every place that 'z' is used, it will be specialized,
and the type parameter '@a' will be substituted.
generic z : @a = blah
Declare a function f with and without type inference. Both
forms are equivalent. 'f' takes two parameters, both of type
int, and returns their sum as an int
const f = {a, b
var c : int = 42
-> a + b + c
}
const f : (a : int, b : int -> int) = {a : int, b : int -> int
var c : int = 42
-> a + b + c
}
3.2. Literal Values
Integers literals are a sequence of digits, beginning with a
digit and possibly separated by underscores. They are of a
generic type, and can be used where any numeric type is
expected. They may be prefixed with "0x" to indicate that the
following number is a hexadecimal value, or 0b to indicate a
binary value. Decimal values are not prefixed, and octal values
are not supported.
eg: 0x123_fff, 0b1111, 1234
Floating-point literals are also a sequence of digits beginning with
a digit and possibly separated by underscores. They are also of a
generic type, and may be used whenever a floating-point type is
expected. Floating point literals are always in decimal, and
as of this writing, exponential notation is not supported[2]
eg: 123.456
String literals represent a compact method of representing a byte
array. Any byte values are allowed in a string literal, and will be
spit out again by the compiler unmodified, with the exception of
escape sequences.
There are a number of escape sequences supported for both character
and string literals:
\n newline
\r carriage return
\t tab
\b backspace
\" double quote
\' single quote
\v vertical tab
\\ single slash
\0 nul character
\xDD single byte value, where DD are two hex digits.
String literals begin with a ", and continue to the next
unescaped ".
eg: "foo\"bar"
Multiple consecutive string literals are implicitly merged to create
a single combined string literal. To allow a string literal to span
across multiple lines, the new line characters must be escaped.
eg: "foo" \
"bar"
Character literals represent a single codepoint in the character
set. A character starts with a single quote, contains a single
codepoint worth of text, encoded either as an escape sequence
or in the input character set for the compiler (generally UTF8).
They share the same set of escape sequences as string literals.
eg: 'א', '\n', '\u{1234}'
Boolean literals are either the keyword "true" or the keyword
"false".
eg: true, false
Function literals describe a function. They begin with a '{',
followed by a newline-terminated argument list, followed by a
body and closing '}'. They will be described in more detail
later in this manual.
eg: {a : int, b
-> a + b
}
Sequence literals describe either an array or a structure
literal. They begin with a '[', followed by an initializer
sequence and closing ']'. For array literals, the initializer
sequence is either an indexed initializer sequence[4], or an
unindexed initializer sequence. For struct literals, the
initializer sequence is always a named initializer sequence.
An unindexed initializer sequence is simply a comma separated
list of values. An indexed initializer sequence contains a
'#number=value' comma separated sequence, which indicates the
index of the array into which the value is inserted. A named
initializer sequence contains a comma separated list of
'.name=value' pairs.
eg: [1,2,3], [#2=3, #1=2, #0=1], [.a = 42, .b="str"]
A tuple literal is a parentheses separated list of values.
A single element tuple contains a trailing comma.
eg: (1,), (1,'b',"three")
Finally, while strictly not a literal, it's not a control
flow construct either. Labels are identifiers preceded by
colons.
eg: :my_label
They can be used as targets for gotos, as follows:
goto my_label
the ':' is not part of the label name.
3.3. Control Constructs and Blocks:
if for
while match
goto
The control statements in Myrddin are similar to those in many other
popular languages, and with the exception of 'match', there should
be no surprises to a user of any of the Algol derived languages.
Blocks are the "carriers of code" in Myrddin programs. They consist
of series of expressions, typically ending with a ';;', although the
function-level block ends at the function's '}', and in if
statements, an 'elif' may terminate a block. They can contain any
number of declarations, expressions, control constructs, and empty
lines. Every control statement example below will (and, in fact,
must) have a block attached to the control statement.
If statements branch one way or the other depending on the truth
value of their argument. The truth statement is separated from the
block body
if true
std.put("The program always get here")
elif elephant != mouse
std.put("...eh.")
else
std.put("The program never gets here")
;;
For statements come in two forms. There are the C style for loops
which begin with an initializer, followed by a test condition,
followed by an increment action. For statements run the initializer
once before the loop is run, the test each on each iteration through
the loop before the body, and the increment on each iteration after
the body. If the loop is broken out of early (for example, by a goto),
the final increment will not be run. The syntax is as follows:
for init; test; increment
blockbody()
;;
The second form is the collection iteration form. This form allows
for iterating over a collection of values contained within something
which is iterable. Currently, only the built in sequences -- arrays
and slices -- can be iterated, however, there is work going towards
allowing user defined iterables.
for pat in expr
blockbody()
;;
The pattern applied in the for loop is a full match statement style
pattern match, and will filter any elements in the iteration
expression which do not match the value.
While loops are equivalent to for loops with empty initializers
and increments. They run the test on every iteration of the loop,
and exit only if it returns false.
Match statements do pattern matching on values. They take as an
argument a value of type 't', and match it against a list of other
values of the same type. The patterns matched against can also contain
free names, which will be bound to the sub-value matched against. The
patterns are checked in order, and the first matching pattern has its
body executed, after which no other patterns will be matched. This
implies that if you have specific patterns mixed with by more general
ones, the specific patterns must come first.
Match patterns can be one of the following:
- Union patterns
These look like union constructors, only they define
a value to match against.
- Literal patterns
Any literal value can be matched against.
- Constant patterns
Any constant value can be matched against.
More types of pattern to match will be added over time.
Match statements consist of the keyword 'match', followed by
the expression to match against the patterns, followed by a
newline. The body of the match statement consists of a list
of pattern clauses. A patterned clause is a '|', followed by
a pattern, followed by a ':', followed by a block body.
An example of the syntax follows:
const Val234 = `Val 234 /* set up a constant value */
var v = `Val 123 /* set up variable to match */
match v
/* pattern clauses */
| `Val 123:
std.put("Matched literal union pat\n")
| Val234:
std.put("Matched const value pat\n")
| `Val a:
std.put("Matched pattern with capture\n")
std.put("Captured value: a = {}\n", a)
| a
std.put("A top level bind matches anything.")
| `Val 111
std.put("Unreachable block.")
;;
3.4. Expressions:
Myrddin expressions are relatively similar to expressions in C. The
operators are listed below in order of precedence, and a short
summary of what they do is listed given. For the sake of clarity,
'x' will stand in for any expression composed entirely of
subexpressions with higher precedence than the current current
operator. 'e' will stand in for any expression. Unless marked
otherwise, expressions are left associative.
BUG: There are too many precedence levels.
Precedence 14: (*ok, not really operators)
(,,,) Tuple Construction
(e) Grouping
name Bare names
literal Values
Precedence 13:
x.name Member lookup
x++ Postincrement
x-- Postdecrement
x# Dereference
x[e] Index
x[from,to] Slice
Precedence 12:
++x Preincrement
--x Predecrement
&x Address
!x Logical negation
~x Bitwise negation
+x Positive (no operation)
-x Negate x
Precedence 11:
x << x Shift left
x >> x Shift right
Precedence 10:
x * x Multiply
x / x Divide
x % x Modulo
Precedence 9:
x + x Add
x - x Subtract
Precedence 8:
x & y Bitwise and
Precedence 7:
x | y Bitwise or
x ^ y Bitwise xor
Precedence 6:
`Name x Union construction
Precedence 5:
x castto(type) Cast expression
Precedence 4:
x == x Equality
x != x Inequality
x > x Greater than
x >= x Greater than or equal to
x < x Less than
x <= x Less than or equal to
Precedence 3:
x && x Logical and
Precedence 2:
x || x Logical or
Precedence 1:
x = x Assign Right assoc
x += x Fused add/assign Right assoc
x -= x Fused sub/assign Right assoc
x *= x Fused mul/assign Right assoc
x /= x Fused div/assign Right assoc
x %= x Fused mod/assign Right assoc
x |= x Fused or/assign Right assoc
x ^= x Fused xor/assign Right assoc
x &= x Fused and/assign Right assoc
x <<= x Fused shl/assign Right assoc
x >>= x Fused shr/assign Right assoc
Precedence 0:
-> x Return expression
All expressions on integers act on two's complement values which wrap
on overflow. Right shift expressions fill with the sign bit on
signed types, and fill with zeros on unsigned types.
3.5. Data Types:
The language defines a number of built in primitive types. These
are not keywords, and in fact live in a separate namespace from
the variable names. Yes, this does mean that you could, if you want,
define a variable named 'int'.
There are no implicit conversions within the language. All types
must be explicitly cast if you want to convert, and the casts must
be of compatible types, as will be described later.
3.5.1. Primitive types:
void
bool char
int8 uint8
int16 uint16
int32 uint32
int64 uint64
int uint
long ulong
float32 float64
These types are as you would expect. 'void' represents a
lack of type, although for the sake of genericity, you can
assign between void types, return values of void, and so on.
This allows generics to not have to somehow work around void
being a toxic type. The void value is named `void`.
bool is a type that can only hold true and false. It can be
assigned, tested for equality, and used in the various boolean
operators.
char is a 32 bit integer type, and is guaranteed to be able
to hold exactly one codepoint. It can be assigned integer
literals, tested against, compared, and all the other usual
numeric types.
The various [u]intXX types hold, as expected, signed and
unsigned integers of the named sizes respectively.
Similarly, floats hold floating point types with the
indicated precision.
var x : int declare x as an int
var y : float32 declare y as a 32 bit float
3.5.2. Composite types:
pointer
slice array
Pointers are, as expected, values that hold the address of
the pointed to value. They are declared by appending a '#'
to the type. Pointer arithmetic is not allowed. They are
declared by appending a '#' to the base type
Arrays are a group of N values, where N is part of the type.
Arrays of different sizes are incompatible. Arrays in
Myrddin, unlike many other languages, are passed by value.
They are declared by appending a '[SIZE]' to the base type.
Slices are similar to arrays in many contemporary languages.
They are reference types that store the length of their
contents. They are declared by appending a '[,]' to the base
type.
foo# type: pointer to foo
foo[123] type: array of 123 foo
foo[,] type: slice of foo
3.5.3. Aggregate types:
tuple struct
union
Tuples are the traditional product type. They are declared
by putting the comma separated list of types within square
brackets.
Structs are aggregations of types with named members. They
are declared by putting the word 'struct' before a block of
declaration cores (ie, declarations without the storage type
specifier).
Unions are the traditional sum type. They consist of a tag
(a keyword prefixed with a '`' (backtick)) indicating their
current contents, and a type to hold. They are declared by
placing the keyword 'union' before a list of tag-type pairs.
They may also omit the type, in which case, the tag is
sufficient to determine which option was selected.
[int, int, char] a tuple of 2 ints and a char
struct a struct containing an int named
a : int 'a', and a char named 'b'.
b : char
;;
union a union containing one of
`Thing int int or char. The values are not
`Other float32 named, but they are tagged.
;;
3.5.4. Magic types:
tyvar typaram
tyname
A tyname is a named type, similar to a typedef in C, however
it genuinely creates a new type, and not an alias. There are
no implicit conversions, but a tyname will inherit all
constraints of its underlying type.
A typaram is a parametric type. It is used in generics as
a placeholder for a type that will be substituted in later.
It is an identifier prefixed with '@'. These are only valid
within generic contexts, and may not appear elsewhere.
A tyvar is an internal implementation detail that currently
leaks in error messages out during type inference, and is a
major cause of confusing error messages. It should not be in
this manual, except that the current incarnation of the
compiler will make you aware of it. It looks like '@$type',
and is a variable that holds an incompletely inferred type.
type mine = int creates a tyname named
'mine', equivalent to int.
@foo creates a type parameter
named '@foo'.
3.6. Type Inference:
The myrddin type system is a system similar to the Hindley Milner
system, however, types are not implicitly generalized. Instead, type
schemes (type parameters, in Myrddin lingo) must be explicitly provided
in the declarations. For purposes of brevity, instead of specifying type
rules for every operator, we group operators which behave identically
from the type system perspective into a small set of classes. and define
the constraints that they require.
Type inference in Myrddin operates as a bottom up tree walk,
applying the type equations for the operator to its arguments.
It begins by initializing all leaf nodes with the most specific
known type for them as follows:
3.6.1 Types for leaf nodes:
Variable Type
----------------------
var foo $t
A type variable is the most specific type for a declaration
or function without any specified type
var foo : t t
If a type is specified, that type is taken for the
declaration.
"asdf" byte[:]
String literals are byte arrays.
'a' char
Char literals are of type 'char'
void void
void is a literal value of type void.
true bool
false bool
true/false are boolean literals
123 $t::(integral,numeric)
Integer literals get a fresh type variable of type with
the constraints for int-like types.
123.1 $t::(floating,numeric)
Float literals get a fresh type variable of type with
the constraints for float-like types.
{a,b:t; } ($a,t -> $b)
Function literals get the most specific type that can
be determined by their signature.
num-binop:
+ - * / %
+= -= *= /= %
Number binops require the constraint 'numeric' for both the
num-unary:
- +
Number binops require the constraint 'numeric'.
int-binop:
| & ^ << >>
|= &= ^= <<= >>
int-unary:
~ ++ --
bool-binop:
|| && == !=
< <= > >=
3.7. Packages and Uses:
pkg use
There are two keywords for module system. 'use' is the simpler
of the two, and has two cases:
use syspkg
use "localfile"
The unquoted form searches all system include paths for 'syspkg'
and imports it into the namespace. By convention, the namespace
defined by 'syspkg' is 'syspkg', and is unique and unmerged. This
is not enforced, however. Typical usage of unquoted names is to
import a library that already exists.
The quoted form searches the local directory for "localpkg". By
convention, the package it imports does not match the name
"localpkg", but instead is used as partial of the definition of the
importers package. This is a confusing description.
A typical use of a quoted import is to allow splitting one package
into multiple files. In order to support this behavior, if a package
is defined in the current file, and a use statements imports a
package with the same namespace, the two namespaces are merged.
The 'pkg' keyword allows you to define a (partial) package by
listing the symbols and types for export. For example,
pkg mypkg =
type mytype
const Myconst : int = 42
const myfunc : (v : int -> bool)
;;
declares a package "mypkg", which defines three exports, "mytype",
"Myconst", and "myfunc". The definitions of the values may be
defined in the 'pkg' specification, but it is preferred to implement
them in the body of the code for readability. Scanning the export
list is desirable from a readability perspective.
4. TOOLCHAIN:
The toolchain used is inspired by the Plan 9 toolchain in name. There
is currently one compiler for x64, called '6m'. This compiler outputs
standard elf .o files, and supports these options:
6m [-h] [-o outfile] [-d[dbgopts]] inputs
-I path Add 'path' to use search path
-o Output to outfile
5. EXAMPLES:
5.1. Hello World:
use std
const main = {
std.put("Hello World!\n")
-> 0
}
TODO: DESCRIBE CONSTRUCTS.
5.2. Conditions
use std
const intmax = {a, b
if a > b
-> a
else
-> b
;;
}
const main = {
var x = 123
var y = 456
std.put("The max of {}, {} is {}\n", x, y, intmax(x, y))
}
TODO: DESCRIBE CONSTRUCTS.
5.3. Looping
use std
const innerprod = {a, b
var i
var sum
for i = 0; i < a.len; i++
sum += a[i]*b[i]
;;
}
const main = {
std.put("The inner product is {}\n", innerprod([1,2,3], [4,5,6]))
}
TODO: DESCRIBE CONSTRUCTS.
6. STYLE GUIDE:
6.1. Brevity:
Myrddin is a simple language which aims to strip away abstraction when
possible, and it is not well served by overly abstract or bulky code.
The code written should be a readable description of an algorithm,
aimed at conveying the essential operations in a linear and
straightforward fashion.
Write for humans, not machines. Write linearly, so that an algorithm
can be understood with minimal function-chasing.
6.2. Naming:
Names should be brief and evocative. A good name serves as a reminder
to what the function does. For functions, a single verb is ideal. For
local variables, a single character might suffice. Compact notation
is simpler to read, typographically.
Variables names should describe the value contained, and function
names should describe the value returned.
Good: spawn(myfunc)
Bad: create_new_thread_starting_at_function(myfunc)
The identifiers used for constant values are put in Initialcase.
Functions and types are in singleword style, although underscores are
occasionally necessary to specify additional information within
functions, due to the lack of overloading.
Good:
type mytype = int
var myvar : mytype
const Myconst = 42
union
`Tagone int
;;
Bad:
type MyType = int /* types are 'singleword' */
const my_func = {;...} /* function names should avoid _ */
const myconst /* constants start with Uppercase */
union
`sometag /* tags start with uppercase */
;;
Acceptable:
const length_mm = {;...} /* '_' disambiguates returned values. */
const length_cm = {;...}
6.3. Collections:
7. STANDARD LIBRARY:
This is documented separately.
8. GRAMMAR:
9. FUTURE DIRECTIONS:
BUGS:
[2] TODO: exponential notation.
[4] TODO: currently the only sequence literal implemented is the
unindexed one