Coffeehouse Post

Single Post Permalink

View Thread: Prototyping a New Language With Haskell
  • User profile image

    Hi all!

    I'm prototyping a new language with Haskell. Here's the overview -

    The Feather Programming Language is a 'language-oriented' programming language. It is intended to expose a blend of imperative, functional, object-oriented, and language-oriented programming paradigms in one simple, machine-efficient and general purpose language. It is a static language with a Hindley-Milner type-inferencing algorithm, but has optional dynamic resolution using H-M inferencing as well (perhaps using staged compilation as referenced in the post later in this thread). The 'language orientation' paradigm is what makes the optional dynamic binding so important. Run-time semantics-wise, it's quite similar with Common Lisp and Scheme. Feather has two syntaxes - sexp and mexp, with the latter being used by default and being translated to sexp for macro processing. Sexp syntax is available only in the symbolic context (mentioned later). Macro processing is what makes the direct translation to sexp so important.


    Syntaxes -

    Here's the sexp syntax. It is sensitive only to newline whitespace -

    // line comment.
    multi-line comment. /* nests. */
    Transition placeholders are not operators but symbols that are part of both sexp and mexp that help to clarify command invocations:
        -> is the 'right transition' placeholder.
        <- 'left transition' placeholder.
        ' 'bar transition' placeholder.
    Bar transition placeholders are replaced by new lines.
    {define {method {double x {}} ' {multiply x 2}}}
    {define {method {factorial n {}}
        {if {lessEqual n 1}
            {multiply n {factorial {minus n 1}}}}}}
    {define {method {fibinocciFast n {}}
        {if {less n 2}
            {fibinocciUp n 2 1 0}}}}
    {define {method {fibinocciUp max {count x y}}
        {if {equal max count}
            {add x y}
            {fibinocciUp max {add count 1} {add x y} x}}}}
    {define {function {selectExample {} {x y}}
        {select x
            0 -> {add x 1}
            1 -> {add x y}
            otherwise -> {time x y}}}}
    {quote 1} // get rid of this since ` is available in sexp?
    {instantiate Person "Jim"}
    {instantiate List `{1 2 3}}
    {instantiate AssociationList `{{a 3} {b 6}}}
    {instantiate Vector `{1 2 3}}
    {instantiate Tuple `{1 2 3}}
    {instantiate HashSet `{1 2 3}}
    {instantiate HashDictionary `{{a 3} {b 6}}}
    {add -5 {multiply 4 2}}
    {multiply 5 {add 4 2}}
    {add 5 {abs {multiply 4 2}}}
    {add 1 {add v1 {cross v2 v3}}}
    {char c} // character literal
    "string" // string literal
    {cons 1 {list 2}}
    {lambda {add _ 5}}
    {equal x 5}
    {assign x 5}
    {equal {cons x ys} {1 2}}
    {assign {cons x ys} {1 2}}
    {generateRange x y}
    {listComprehension {{x <- someList} {y <- {generateRange 1 5}} {odd y} {multiply x y}}}
    {filter {lambda {odd _}} {map {lambda {add _ 1}} {list {3 4 5 6}}}}
    {norm {cross {v1 v2}}}
    {conditional x {consequentAlternate y z}}
    {lamda {multiply _ {add _ 5}}}
    {lamda x {multiply  x {add x 5}}}
    {lamda {x y} {multiply x {add x y}}}
    {bitOr x 0xff}
    {bitAnd x 0xdd} 
    {bitShiftRight x 1}
    {asDestructure x {List Int}}
    {dynamicExpression {add 1 1}}
    {staticExpression {add 1 1}}
    {lazyExpression {add 1 1}}
    {strictExpression {add 1 1}}
    {parallelExpression ...}
    {memoizedExpression {multiple n m}
    {message jim {jump 5}}
    {message {jim sue} {walk 10}}
    {power n 2}
    {compose f g}

    Here's the meta syntax that maps one-to-one sexp syntax. It is column-sensitive as well as newline-sensitive. The column sensitivity is what makes the command: syntax work without need a special end-scope operator. Meta syntax is transformed to sexp syntax before macro processing. This code is the mexp mirror of the sexp code above, and you can deduce the mapping mechanics yourself -

    // line comment.
    multi-line comment. /* nests. */
    Transition placeholders are not operators but symbols that are part of both sexp and mexp that help to clarify command invocations:
        -> is the 'right transition' placeholder.
        <- 'left transition' placeholder.
        ' 'bar transition' placeholder.
    Bar transition placeholders are replaced by new lines.
    define: x.double() ' x * 2 // normally non-side-effecting, parameter-less methods should be getter properties instead
    define: n.factorial()
        if: n <= 1
            n * (n - 1).factorial()
    define: n.fibinocciFast()
        if: n < 2
            n.fibinocciUp(2, 1, 0)
    define: max.fibinocciUp(count, x, y)
        if: max = count
            x + y 
            max.fibinocciUp(count + 1, x + y, x)
    define: selectExample(x, y)
        select: x
            0 -> x + 1
            1 -> x + y
            otherwise -> x * y
    Person("Jim") // Person.constructor(String) gets the ctor with a String parameter
    $[1, 2, 3] // $ introduces a single character special symbol or multi-character alpha string symbol. Reserved for language designer. NOTE: List is a monad, btw.
    $c[[a, 3] [b, 6]] // $a reserved for arrays if the language gets them
    $v[1, 2, 3]
    $t[1, 2, 3]
    $s[1, 2, 3]
    $d[[a, 3] [b, 6]]
    4 * 2 + -5      // -5 and - 5 have different meaning due to white space
    (4 + 2) * 5     // fn (x) and fn(x) have different meaning due to white space
    (4 * 2).abs + 5 // abs is a property (more on this later)
    v2.cross(v3) + v1
    1 :: $[2]
    \_ + 5
    x = 5
    x := 5
    x :: ys = z // equality
    x :: ys := z // pattern match assignment
    $(x <- someList, y <- 1..5, y.odd, x * y) // also implements pattern match binding for discrimination like Haskell
    $[3, 4, 5, 6].map(\_ + 1).filter(\_.odd)
    x ?? y !! z // the ?? !! operators do not use distfixity or special-case evaluation. instead, the !! operator produce a lazy expression pair that the ?? operator then destructures and uses one of its members depending on its result.
    \_ * _ + 5          // preferred when individual lambda parameters are not used multiple times
    x ~> x * x + 5      // lambda with one parameter, x
    [x, y] ~> x * x + y // lambda with two parameters, x and y
    x .' 0xff // bit operators start with '.' to reserve the C-style symbols for other operators. No characters in a hex literal can be capitalized (including the 'x' separator)
    x .& 0xdd
    x .>> 1
    List Int >> x // like for naming a pattern in a pattern match expression
    $dynamic 1 + 1
    $static 1 + 1
    $lazy 1 + 1 // use lazy evaluation for a pure expression
    $strict 1 + 1 // use strict evaluation
    $parallel ... // parallelize a pure expression
    $memoized n * m // memoize a pure expression
    jim <' jump(5) // agent message
    [jim, sue] <' walk(10) // message to multiple agents
    n ^ 2
    f & g


    Note that the translation from mexp to sexp is purely syntactic, but some semantic checking must take place after the transformation using a map from the sexp back to the mexp. An example of semantic check that must be done is that the is used on method calls or method signatures only (and only said syntax is used).


    All symbol resolution in the lexical scope of 'static' will be resolved statically (that is, when the code is compiled). All resolution in the 'dynamic' scope will be resolved dynamically (that is, when the code is executed). The default scope when none is specified is 'static'. Static typing is not only intended for safety, but also forcing as many possible program decisions to compile time where possible in order to achieve maximum run-time efficiency.

    define: n.fibinocciFast()
        if: n < 2
            n.fibinocciUp(2, 1, 0)
    define: max.fibinocciUp(count, x, y)
        if: max = count
            x + y
            max.fibinocciUp(count + 1, x + y, x)


    This is an overview of the definition commands -

    {listed in order of likely implementation}

    define: x -> 10.0                          // define x as a Float of value 10. binding is scoped. A define of the same symbol never changes the underlying symbol, but shadows it instead.
    define: fn(x) ' expression                 // define a function
    define: ' expression               // define a method. A single context variable is required
    define: co: x y; ' expression              // define a command like the let and if commands
    define: x bi y p a ' expression            // define a binary operator like + and - with p precedence with a associativity. Precedence is part of a binop's type, and should probably be some sort of fractional number
    define: le x ' expression                  // define a left operator
    define: x ri ' expression                  // define a right operator... not sure how this would be used :)
    define: c.prop ' get x ' set x := value    // define property
    lambda...       // create a lambda. Callable as a function only
    methlambda...   // create a methlambda. like lambda, but used to pass methods. callable as a method only
    comlambda...    // create a comlambda. like lambda, but used to pass commands. callable as a command only
    bilambda...     // create a bilambda. like lambda, but used to pass binops. callable as a binop only
    leflambda...    // create a leflambda. like lambda, but used to pass leftops. callable as a leftop only
    rilambda...     // create a rilambda. like lambda, but used to pass rightops. callable as a rightop only
    proplambda...   // create a proplambda. callable as a property only
    let: x -> 7 ' expression                // define a value over an expression. values cannot be set.
    let: x -> var 7 ' expression            // define a variable over an expression. variables can be set
    let: [x -> 7, y -> var 5] ' expression  // define multiple items over an expression. sequential like lisp let*
    macro: y -> 5   // macro expands to expression
    macro...        // define a scheme-style hygienic macro. Invoked like a function.
    macro...        // like a macro, but invoked like a method
    macro...        // like a macro, but invoked like a command
    macro...        // like a macro, but invoked like a binop
    macro...        // like a macro, but invoked like a leftop
    macro...        // like a macro, but invoked like a rightop
    macro...        // like a macro, but invoked like a property
    [functional types]
    synonym...              // like Haskell type
    derivative...           // like Haskell newtype
    typeConstructor...      // like Haskell data
    typeClass...            // like Haskell class
    typeInstance...         // like Haskell instance
    [object system - could be done after the prototype]
    class... // class like in CLOS, but without the generality of a MOP. Ideally implemented as a library.
    [agent system - could be done after the prototype]
    agent... // agents are like arbitrarily parallelizable objects
    lazy x // marks a parameter (here x) as lazy-evaluated. This is a nice, simple substitute for some macros. A leftop.


    Error handling - Uses a system similar to scheme's Condition system.


    Literal numbers are Int by default -

    5(u)b               // (U)Byte - 8-bit
    5(u)s               // (U)Short - 16-bit
    5(u)                // (U)Int - 32-bit
    5(u)i2              // (U)Int2 - 64-bit
    5(u)i3              // (U)Int3 - 128-bit
    5.0                 // Float - 32-bit
    5f2                 // Float2 - 64-bit
    5f3                 // Float3 - 128-bit
    5n                  // Similar to Scheme numbers - no specific size. Does not implicitly mix with the strictly-sized numbers in any way. This can probably be implemented after the prototype.
    5(u)m               // (U)Macint – Machine-size integer


    The Universal type -

    All primitives, data types, and the base object type have an instantiation of the type class Universal which has the following properties -

    x.shown // printable string
    x.bytes // serializable bytes

    This allows you to put a number, a string, and an object into a single, well-typed List of Universal.


    Function type arrows –
    Function type arrows can use the same arrows as used elsewhere because types are always interpreted in a different context that normal expressions.
    -> - Describes a function of inferred, unspecified, or dependent purity
    => - Describes a pure function
    :> - Describes an impure function


    Type signatures of a function called 'double' from x to x where x is a Number -

    double @ x.method() => x '> Number x
    double @ command: x; => x '> Number x
    double @ leftop x => x '> Number x
    double @ x rightop => x '> Number x
    double @ => x '> Number x
    // all generalize to...
    double @ x => x '> Number x
    // as well as...
    x => x '> Number x


    Here is the type of map:
    map @ r a.method(a -> b) -> r b '> Functor r

    NOTE: since Vector is not a Functor, it must be converted to a List before being used with map, possibly with a simple list property.


    Miscellanea -

    Some code examples...

    define: selectExample(x, y)
        select: x
            0 -> x + 1
            1 -> x + y
            otherwise -> x * y
    // switch is like select, but requires hash and = type class instantiation, and is constant-time
    define: switchExample(x, y)
        switch: x
            0 -> x + 1
            1 -> x + y
            otherwise -> x * y
    define: chooseExample(x, y)
            x = 0 -> x + 1
            y = 1 -> x + y
            otherwise -> x * y
    // a function with a match command as the first expression can be compiled to one function for each statically-determinable match case and have the caller bound to the right one at compile time
    define: matchExample(m, n)
        match: m                // a pattern expression (EG - x :: xs) does not have access to outside variables, like m or n. otherwise it could accidentally pull globals or the like
            x :: xs -> x        // where m is x :: xs, x
            $t[x, x, ?] -> x    // where m is $t[x, x, ?], x
            5 -> m              // where m equals 5, m
            otherwise -> n      // n
    define: multiMatchExample(m, n)
        match: [m, n]
            [x :: xs -> x, x] -> n // where m is x :: xs and n equals x, n
            otherwise -> 0
    define: matchChainExample(m, n)
        match: m
            x :: xs -> x = 5 -> n // where m is x :: xs and x equals 5, n
            otherwise -> 0
    // for step comprehension like lisp progn
    define: stepsExample()
        steps: // not redundant since function definitions do NOT have implicit steps
            "Hi, ".print()
            "I am ".print()
    // for applicative comprehension
    define: apsExample(x, y)
            $[2, 3, 4]
    // shorhand for applicative comprehension
    ${lift(add), $[2, 3, 4], lift(4)}
    // for monad comprehension
    define: doExample(x, y)
            x <- f(0)
            y <- g(1)
            lift($t[x, y])
    // QUESTION: can list comprehensions be shorthand for do syntax?

    meta: expressions // specifies the enclosed expressions may not use '{' or '}' sexp symbols. Prevents the two syntaxes from being used together unnecessarily. Functions may only be called with the x.y(z) notation and commands can only be called with the x: y notation (and so on for the operators).

    symbolic: expressions // specifies the expressions may not use (, ), [, ], ',', :, etc. or infix operators.

    pretty: expressions // disallows arbitrary white spacing / formatting so that all code looks roughly the same no matter the author.

    ` is quote, ' is unquote, and $' is dollarQuote (like lisp at-quote). // the rest parameters with name rest

    import:> // very similar to Haskell's import, but much simpler and less error prone

    Module.thing // qualifies thing with module name. If . is ambiguous, we could use Module/thing instead.

    /// <Summary>Documentation comments are done almost exactly the same as in C#, except you can aim a comment from one place to a program element in another using a <Target> tag.</Summary>

    RULE: all expressions should be readable from left to right and top to bottom (with some exceptions like f & g).

    RULE: you can run any pure code at compile-time (define: for example is pure as it can never side-effect since it shadows).

    RULE: there are 3 types of function purity – pure, impure, and dependent. Only higher order functions can be dependent. A dependent function resolves to pure or impure depending on how it is invoked. If one or more of its incoming functors is impure, it becomes impure. Otherwise, its purity depends on whether it calls other impure functions.

    RULE: immutability always cascades down with recursive structures. You cannot have an immutable variable that is bound to a mutable list or an immutable list of mutable lists.

    RULE: All module, type, typeClass, class, and type / data constructor names start with an uppercase letter. This makes pattern matching much easier to use.

    RULE: Feather is a single namespace language with lexical scoping. No special symbol affixation is needed to pass a function - just mention it by name.

    RULE: nearly all functions must come from a module to be used, including operators on primitive types. This allows DSLs to avoid exposing operations that are not useful.

    RULE: the only time you need to qualify a name with the module is when it collides with another imported name.

    RULE: each implementation of Feather must have a self-compatible binary representation of all its objects. This allows entire object trees to be burned to disk (or ROM) and be reified directly back into memory to avoid the need for a serialization process, reflection-based or otherwise.

    RULE: operator precedence and associativity is the same as in C, but the flawed associativety of .& and .' will be fixed up.

    RULE: since this author despises noise in code, the compiler will warn about superfluous parenthesis / brackets, and give an error in pretty mode. Same for tabbed out // with no matching tabbed out // on adjacent lines.

    RULE: Like python and its recommended 'pythonic' style philosophy, there is a similar recommended philosophy in Feather. In Feather, there is always a single best way to do any one thing, and it should be obvious. This won't always be achievable, but is a good language goal.


    So, anyways, that's the design so far. I ultimately hope I can get C-style programmers to consider using it. If anyone see any big holes in it or has any feedback, please discuss it here.


    Another immediate question I have as a language implementer is, how do most language implementers fund their projects? I will be developing this language slowly over time, but I'd like to find some way to move it forward faster. Are there any companies out there that are interested in this type of project? If this language makes as much sense as I think it does, it might be timed just right to serve the growing interest in efficient, object-oriented, functional and 'language oriented' programming.