summaryrefslogtreecommitdiff
path: root/doc/lang.txt
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2014-06-18 01:10:30 -0400
committerOri Bernstein <ori@eigenstate.org>2014-06-18 01:10:30 -0400
commitf6e53709407611de940092c9d73e63926723252f (patch)
tree320c6d9474ba1eb51f2dc88640e9edd0d1672a55 /doc/lang.txt
downloadmc-f6e53709407611de940092c9d73e63926723252f.tar.gz
Merge pull request #1 from akoshibe/master
added sockproto values
Diffstat (limited to 'doc/lang.txt')
-rw-r--r--doc/lang.txt832
1 files changed, 832 insertions, 0 deletions
diff --git a/doc/lang.txt b/doc/lang.txt
new file mode 100644
index 0000000..008c95a
--- /dev/null
+++ b/doc/lang.txt
@@ -0,0 +1,832 @@
+ 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[e] Index
+ x[from,to] Slice
+
+ Precedence 12:
+ ++x Preincrement
+ --x Predecrement
+ *x Dereference
+ &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
+