ref: f1ea96e3b500fdd088c8c89889d5daec2cbcb3dc
dir: /doc/lang.txt/
The Myrddin Programming Language Jul 2012 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. 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 At the current stage of development, not all of these keywords are implemented within the language.[1] 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 interchangable. They will both be referred to "endline"s thoughout 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 restricitions 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" 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', '\u1234'[3] Boolean literals are either the keyword "true" or the keyword "false". eg: true, false Funciton 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. Where a truth value is required, any type with the builtin trait 'tctest' can be used in all of these. 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 statemments, 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 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() ;; 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 keyord '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 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 = %i\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. 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 suficient 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. 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' true bool false bool true/false are boolean literals 123 $t::(tcint,tcnum,tctest) Integer literals get a fresh type variable of type with the constraints for int-like types. 123.1 $t::(tcfloat,tcnum,tctest) 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 'tcnum' for both the num-unary: - + Number binops require the constraint 'tcnum'. 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 importer's 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 %i, %i is %i\n", x, y, max(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 %i\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 fasion. 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. */ cosnt length_cm = {;...} 6.3. Collections: 7. STANDARD LIBRARY: 8. GRAMMAR: 9. FUTURE DIRECTIONS: BUGS: [1] TODO: trait, default, protect, [2] TODO: exponential notation. [3] TODO: \uDDDD escape sequences not yet recognized [4] TODO: currently the only sequence literal implemented is the unindexed one