Coffeehouse Thread

8 posts

Prototyping a New Language With Haskell

Back to Forum: Coffeehouse
  • 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.

    An individualist is he who is saving himself from all those who are saving the world.
    Last modified
  • User profile image

    For starters, you are going to need a new name.  Luna has already been used multiple times for language projects.

    The point of this additional syntax of sexp (another horrible name) completely escapes me.  If you want to do some sort of internal translation, fine.  But having more than one syntax exposed to the user is a recepie for fail.

    So this is basically Lisp/Scheme with static typing?  I don't mean to be negative, but I don't see how this is going to appeal to C-family programmers.  They are going to find a much more attractive package in the functional extensions to existing C-family languages, and the static-typed functional capability in F#.  It seems your real target is traditional functional programmers looking for better performance. 

    Well, have fun with it.  Maybe it will turn into the next big thing.


  • User profile image

    Do you have a home page with some more documentation and examples? It's always fun to play with these things.

  • User profile image


    New name: can do. I don't really like the name Luna anyhow Smiley

    The name 'sexp': This is a common shorthand name for the concept of 'symbolic expressions'. Same with mexp which is short for meta-expressions. So, I don't know how I would change that. I could give it a friendler name in the language documentation, but it might just cause confusion for existing functional programmers.

    The point of sexps: An s-expression syntax is necessary for comfortably implementing good internal DSLs using real macros. When it comes to the language-orientation pradigm, C-style syntax is inadequate (at least for internal DSLs). For this reason, I fear that C-style languages are an evolutionary dead end.

    The point of mexps in addition to sexps: Mexps are much visually superior (at least in the eyes of C-style programmers like myself) to the sexp syntax. So the two syntaxes are both quite necessary. Again, with the meta(expr) function, you can force code to use only the mexp syntax, so it shouldn't be confusing.

    The reason I believe C-style programmers will consider using the language is because it looks very similar to Python or Ruby. Many C-style programmers love Python or Ruby and their biggest reason for not using Lisp is the parens of its pure sexp syntax. I think the language I'm designing is right up C-style programmer's alleys because it's -

    • Static for near-C run-time performance
    • Static for beyond-C safety
    • Visually appealling (for the many C'ers that like Python or Ruby)
    • Many, many times more powerful than C or its derivatives due to real macros and optional dynamic typing and evaluation.

    But again, because C-style languages can't comfortably do real macros, I fear they are a dead end. When (or if) C-style programmers come to believe this as I do, I hope they will consider this language as an alternative.

    As to it turning into the next big thing - well, perhaps if I got some support or funding (and the idea actually proves to be sane) I could make it happen. Without it, I'm not sure if it could be much more than a potentially interesting toy.

    Life is hard Sad

    An individualist is he who is saving himself from all those who are saving the world.
    Last modified
  • User profile image


    Once I have something stable to play with, I'll look at putting up a site. However, I'm swamped with my current full-time programming job, so it's going to take a while yet Smiley

    An individualist is he who is saving himself from all those who are saving the world.
    Last modified
  • User profile image

    This is a bit tangential but I think blurring the line between "compile time" and "run time" is the most interesting current/coming trend in language design. There's an interesting paper by Simon Peyton-Jones, Tim Sheard and Mark Shields on how dynamic typing can be treated as a form of type inference that runs partly at compile time and partly at runtime: (in PostScript, unfortunately for most Windows users).

  • User profile image

    @contextfree`: Very interesting research.

    Overall, I get this feeling that there is so much great synergy between static and dynamic typing that new languages should be exploring it. Nothing more painful than being trapped strictly in just one or the other.

    An individualist is he who is saving himself from all those who are saving the world.
    Last modified
  • User profile image

    Just wanted to bump as the design has changed quite a bit (see first post). Sadly, I've been super busy with work, so the implementation is going very, very slow. Finally, I've been trying to think of a new name, but nothing seems to stand out except for names that have already been taken by other languages. Maybe something named after a gem stone. Gem stones are pretty.


    Another reply to Ryan B - perhaps the sexp syntax should be hidden from the user by enabling meta: mode by default.


    Right, gonna put my head back down now. Sorry for the bump Smiley

    An individualist is he who is saving himself from all those who are saving the world.
    Last modified

Comments closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums, or Contact Us and let us know.