path: root/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[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