Prototyping a new language with Haskell

Hi all!

I'm prototyping a new language with Haskell. Once I get the semantics right, I'll probably implement it more efficiently with straight C++ and LLVM. I hope to have something interactive soon. Here's the overview -

Luna is intended to expose functional, object-oriented, and most importantly, 'language-oriented' programming paradigms in one simple and machine-efficient language. It has optional dynamic binding. The 'language orientation' paradigm is what makes the optional dynamic binding so important. Luna is general purpose. It has two syntaxes - sexp and meta, with the latter being used by default and being translated to sexp for macro processing. Macro processing is what makes the direct translation to sexp so important.


Syntaxes -

Here's the sexp syntax (which is admittedly not super pretty) -

;; line comment

{function {fibFast n}
    {if {less n 2}
        {fibUp n 2 1 0}}}

{function {fibUp max count x y}
    {if {equal max count}
        {add x y}
        {fibUp max {add count 1} {add x y} x}}}

{function {factorial n}
    {if {lessEqual n 1}
        {mul n {factorial {subtr n 1}}}}}

{add 5 {mul 4 2}}
{mul 5 {add 4 2}}
{add 5 {abs {mul 4 2}}}
{add 1 {add v1 {dot v2 v3}}}
{assoc y x} ;; association list lookup
{tuple {1 2 3}}

Here's the meta syntax that maps one-to-one and is usable interchangeably with sexp syntax. It is column-sensitive once the colon is introduced. Meta syntax is transformed to sexp syntax before macro processing -

;; line comment

function: fibFast(n)
    if: n < 2
        fibUp(n 2 1 0)

function: fibUp(max count x y)
    if: max = count
        x + y
        fibUp(max count + 1 x + y x)

function: factorial(n)
    if: n <= 1
        n * factorial(n - 1)

4 * 2 + 5
+(4 2) * 5
abs(4 * 2) + 5
dot(v2 v3) + v1 + 1
1; 2; 3


All symbol resolution in the lexical scope of 'static' will be resolved statically. All resolution in the 'dynamic' scope will be resolved dynamically. The default scope when none is specified is 'static'.

    function: fibFast(n)
        if: n < 2
            fibUp(n 2 1 0)

    function: fibUp(max count x y)
        if: max = count
            x + y
            fibUp(max count + 1 x + y x)


This is an overview of the definition functions -

[listed in order of likely implementation]

val: x(7) y(5) expression ;; bind immutable value(s) over an expression
var: x(7) y(5) expression ;; bind mutable variable(s) over an expression
vlz: x(1 + 1) expression ;; bind an expression to a name over another expression
function: fn(x y) expression ;; declare a function
lambda... ;; create a lambda
macro... ;; define a lisp-style macro
class... ;; class like in CLOS
data... ;; an algebraic data type
alias... ;; a type alias


Type inference - Types will be inferred where not specified. The type inference for the prototype will use the Hindley-Milner algorithm. Type inference algorithm will be the same for symbols resolved at compile-time with static binding as those resolved at run-time with dynamic binding.


Miscellanea -
meta: expression ;; specifies the enclosed expression may not use `{' or `}' sexp symbols. Prevents the two syntaxes from being used together unnecessarily.


So, anyways, that's the design so far. I ultimately hope I can get C-style programmers to consider using it.

Edit: Updated to current design.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Dynamic binding for metaprogramming ?

I'm sorry if that sounds like an obvious question, but I don't understand how you make the relation between dynamic binding and metaprogramming. I always considered that it was the simple structure of LISP ASTs, as well as careful design, that enabled macros, and not any kind of dynamic binding.

Never meta-programming I didn't like

The word "metaprogramming" is used to mean everything from prosaic code generators to macros to staged compilation to type level programming to Smalltalk/Ruby style "mutate the structure of my program at runtime, please." I would guess that byranedds is focused on the last of these.

Yeah, the metaprogramming

Yeah, the metaprogramming techniques from Ruby / Python are what I had in mind.

If you have python/ruby

If you have python/ruby monkey patching in mind, maybe you should change your description where you say that "dynamic binding enables the expressiveness and metaprogramming features of lisp" (emphasis mine).

Quite right. TBH, the ideas

Quite right.

TBH, the ideas are still so vague in my head, that I'm not yet able to properly articulate them. What I do know for sure is that what we have is either wrong or not quite bridging the gap between the mainstream and the true power of our machine.

However, once I start implementing this language, I am sure that things will crystallize and most of my oversights will be revealed.

It's hard to separate development from the learning process itself :)

Good question...

...I'll try to come up with a motivating example.

Another thing I wanted to do

Another thing I wanted to do by posting is to to gather some feedback. Does anyone see any glaring flaws with the proposal so far? As far as language design goes, I'm still quite naive and am probably clueless in many aspects. So I wouldn't be surprised if I've screwed up something obvious.


First of the first, what's

First of the first, what's the selling points ?

It looks like Python, what is the advantage comparing to Python or Boo ?
If speed is a target, why not use C/D/OCaml/Haskell... ?
Dynamic/static binding can be easily done by function pointers in C. It is a feature, but I don't think it is enough to people's attention.

Some words of advice

Regarding the question of how to evaluate a new language, and how creators should motivate they work, I very much appreciate Frank Atanassow's Some words of advice on language design. Quote:

Before you go off inventing new programming languages, please ask yourself these questions:
1. What problem does this language solve? How can I make it precise?
2. How can I show it solves this problem? How can I make it precise?
3. Is there another solution? Do other languages solve this problem? How? What are the advantages of my solution? of their solution? What are the disadvantages of my solution? of their solution?
4. How can I show that my solution cannot be expressed in some other language? That is, what is the unique property of my language which is lacking in others which enables a solution?
5. What parts of my language are essential to that unique property?

Fantastic Advice!

1. In a few words, I am creating this language because I wish I had it to use every time I sit down to write code. Writing code in mainstream languages is just too painful. And getting others to adopt existing non-mainstream languages like common lisp and ocaml does not seem to be promising.

The primary aim of this is to enable metalinguistic abstraction development techniques alongside modern programming techniques such as OOP for 'soft' real-time software development. It is multi-paradigm because that's what game software generally requires (games being my domain). Its efficiency should make it reliably fast enough for unusually constrained architectures. Its syntax renders it palatable to mainstream programmers. Its underlying semantic power will make it terse, readable, parsable, and ultimately liberating.

It should enable a classic OO paradigm (perhaps like CLOS) for efficient simulation building (the primary requirement in game development). It should have a powerful inferential type system for succinctness and safety. Its optional dynamic typing should enable program-semantics to be generated at run-time to allow embedded DSL programming (a must for the various types of game scripting).

Now, this all sounds buzz-wordy, but these are ALL techniques that are necessary when developing non-trivial game software. Lacking any one of these means you have to implement an ad hoc, poorly specified, bug-ridden, inefficient versions of these features from scratch every time you start a new project or (if you dare some reuse) engine...

Well, that is, if you want to write maintainable code...

Though in reality, since writing maintainable code requires implementing all these features from scratch in a C-style language, most people opt to write throwaway code instead...

But due to time constraints, the throwaway code gets reused, entropied further, shipped anyway, then reused again...

But I digress...

The syntax is primarily determined by an isomorphic mapping to sexprs. Making the syntax uber-expressive, 'mathematical' or 'english-like' is not a big priority. A one-to-one mapping with sexprs is the main priority. This is to enable a reasonable macro programming experience. All expressions are reduced to sexpr form before being processed by macros.

Other than the sexpr mapping constraint, the syntax merely need be good enough to get other mainstream programmers to consider adopting the language.

2. It solves the problem when it enables me to use metalinguistic abstraction and OO techniques in a terse, machine-efficient manner.

3. Lisp solves the problem well except for the efficiency constraints and acceptable (to the mainstream, anyway) syntax. Too many things like function resolution need to be calculated at compile-time for efficiency purposes. And C-style programmers have historically shown an inability to accepts common lisp's syntax.

4. I can't prove a negative, but am happy to see contradicting evidence.

5. See 1.

Oh, and I forgot to touch on

Oh, and I forgot to touch on the major challenges for the language.

I think the biggest intellectual challenge will be figuring out how to implement both the static and dynamic binding semantics so they integrate cleanly and clearly to the user. I'm not aware of much existing research done on the subject. If the language does nothing else, it might at least raise some new questions.

The other challenge is getting anyone interested in trying it. 'If you build it, they will come' is never true :)

The final challenge is, of course, actually building the thing to the point of usability and fulfilling its promise of real efficiency.

It looks okay so far...

...but I am curious: how does it compare to, say, Lua? You seem to have a lot of "noise" dedicated to specifying just how your syntax is meant to be statically or dynamically bound - is it necessary, or is it a remnant of the work-up you're doing, for simulation purposes?

Lua is dynamically-typed.

Lua is dynamically-typed. Luna is intended to be statically-typed by default with a simple and clear escape hatch to dynamic typing without changing languages.

Luna is intended to expose functional, object-oriented, and most importantly, 'language-oriented' programming paradigms in one simple-as-possible language. The last paradigm is what makes the dynamic escape hatch so important. Luna is general purpose. Lua, AFAIK, is a procedural language and seems to be purposed primarily toward scripting.

Bolting on type systems

You talk about a "powerful inferential type system" and I can not see any typing rules specified for your language. I will admit that I did not understand most of what you just said, but history has shown that it is very hard to bolt on a (working) type system on an existing language -- it is a much better idea to design the language with the type system in mind, or even at the same time.

The type system will definitely not be bolted on -

I haven't gone into any specifics about the type system because I'm honestly not sure which I will choose. I think the type system I'm most likely to build the language around will be similar to Ocaml's, but I need to do more research to that end. The type system at minimum should support algabraic data types and destructuring / pattern matching as well as transitive immutability. I don't see a big need for monads in the language and Haskell's type system just seems much more rich than I would need, but great respect to all of it nonetheless.

Binding Context Switching

I'm not liking the duplication of each syntactical element with 'sta/dyn'. I'm thinking that the ability to change binding contexts could make more sense. For example -

    function: fibFast(n)
        if: n < 2
            fibUp(n 2 1 0)

    function: fibUp(max count x y)
        if: max = count
            x + y
            fibUp(max count + 1 x + y x)

- would mean that all symbol resolution in the lexical scope of stabind will be resolved statically. All resolution in the dynbind scope will be resolved dynamically. This also means that the binding context would have no effect on the definition or meaning of any symbols.

Hopefully this is an improvement. I'll have to change the whole top post if this approach makes more sense.

Any thoughts?

After thinking about it, it

After thinking about it, it seems like this is the proper solution. I updated the top post to reflect the newer design.


Please see policy document about desgin discussions on LtU.