Mars: a hybrid imperative-declarative higher-order language | Hacker News Reader

Mars: a hybrid imperative-declarative higher-order language

mars-lang.appspot.com

70 pointsplesner54 comments

Mixing imperative and functional paradigms is a really interesting point in the design space, and has gotten me (begrudgingly) interested in statically-typed languages. I noticed writing Common Lisp that I preferred to write code in a functional style, but occasionally I'd want to bury an imperative update somewhere. Putting a comment saying: "this should be the only use of SETF in the whole algorithm" isn't the most satisfying solution.

Languages like Common Lisp and Dylan (and SML) have mixed imperative and functional paradigms in a non-controlled way for awhile, but there is some interesting work going on about how to do it in a more controlled way. Much of this work involves limiting aliasing and mutability, or expressing imperative features an effect system, or some combination of the two.

Rust is probably the most mainstream example of the former, but Mezzo is another language exploring this area: http://protz.github.io/mezzo. The basic idea is that if you've got the unique reference to an object, or a tree of objects, you can modify it without worrying about how it will affect the rest of the program. Koka is a language that focuses more on the latter, expressing the imperative characteristics of a function through an effect system: http://arxiv.org/pdf/1406.2061.pdf (section 2.1). The basic idea here is similar to Java's exception specifications. If the set of objects potentially modified by a function must be part of its type, then you can use the type system to keep you from modifying an object, or calling a function that does, in a context where the rest of the program doesn't expect that object to be modified.

Then of course there are monads which aren't too inappropriately described as the pattern of expressing controlled imperative features in the type system.

The difference between monads and the kind of effects system used in Koka is that in Koka, effects are inferred, whereas with monads, they have to be stated up-front. Koka also allows you to mix effects, e.g. a function can be `<io, st<h>, ndet>`, meaning that it reads/writes files, reads/writes memory in heap `h`, and is non-deterministic. Effect variables are akin to higher-kinded polymorphism, so that e.g. `map` can be polymorphic in the effect of the mapping function.

>in Koka, effects are inferred

Monadic types can be inferred most of the time in Haskell, it's just considered good practice to include a type signature for every function.

>Koka also allows you to mix effects, e.g. a function can be `<io, st<h>, ndet>`

This can be done with Monad transformers, although it's a little awkward at the moment. There are various proposals for better composition here, and I suspect sooner or later someone will work out a good solution.

>`map` can be polymorphic in the effect of the mapping function.

`mapM` is polymorphic over monadic functions. `map` doesn't handle monadic functions (unless you just want a list of monadic values), but since they're kind of different operations, I think it's preferable to have different functions for each.

mtl has been around for a while now and using any the monads from the mtl transformers library is very inferrable, although like any inference it returns the most general type possible and it's generally just good practice to forward declare the type.

    example = do
      a <- ask
      modify (+ a)
      b <- get
      tell [b]

GHC correctly infers:

    example :: (Num s, MonadState s m, MonadReader s m, MonadWriter [s] m) => m ()

As others have stated, that's all done as libraries in Haskell in a variety of ways.

I'd be interested in knowing how the order of the combined effect types are resolved in Koka, though. For instance, in `<io, ndet>` the ndet effect will end up conducting a search. How do the (observable) io side effects get woven into that search? In particular, how does Koka know the proper ordering?

In Haskell, you'd be forced to eventually declare an order to your monad stack (although most functions can be agnostic to the particular choice). So in this instance, you would write `LogicT IO a` to indicate that the non-determinism gets resolved first while most functions would be of the form `(MonadIO m, MonadLogic m) => m a` where the parenthesized set of constraints is unordered.

Hm... if I understand correctly, the `ndet` effect isn't non-determinism in the sense of amb, but rather non-determinism in the sense or random. I.e., there is no search, it's just producing a random number.

Ah, sorry. The question still holds, though it's less obvious what it means with this effect stack. Perhaps a more obvious example would be failing, stateful computation written as follows as an order-free restricted type in Haskell

    ( MonadPlus , MonadState s ) => m a

Given some concrete choices of monads to witness those effects like MaybeT and StateT there are two "orders" we can stack them.

    MaybeT (StateT s Identity) a
    StateT s (MaybeT Identity) a

where Identity forms the "effect free" base of our stack. While functions which operate on types with the order-free signature work for each stack, ultimately the stacks represent different combined effects. In particular, the `StateT s (MaybeT Identity)` stack throws away state if the computation fails while `MaybeT (StateT s Identity)` does not.

    run1 :: StateT s (MaybeT Identity) a 
         -> s -> Maybe (s, a)
         -- failure captures the result state

    run2 :: MaybeT (StateT s Identity) a
         -> s -> (s, Maybe a)
         -- result state always produced, failure captured
         -- only in the result value

So, ultimately the semantics of your effect set depend upon the ordering of your effects. At least in Haskell. I'd be interested to see how Koka handles it.

If I understand Koka correctly, it's type system is purely descriptive, and has no effect on runtime. Having said that, Koka is a strict, eager language (at least currently, as it's compiled to JavaScript), so effects happen in the order that they appear in code. It doesn't support "handlers" like Haskell or Bauer & Pretnar's Eff.

Eagerness doesn't really matter for this purpose. It has more to do with "overriding" or priority of effects. I'll just look into it later. Thanks!

If it's anything like purescript's extensible records effect system then there are "handlers" which determine effect order/priority (see http://www.purescript.org/posts/Eff-Monad/)

On the topic of Lisp and monads, it occurred to me recently that Lisp "lists" are actually rose trees, and rose trees are a free monad. Which winds up being a more Haskelly take on "In Lisp, you're writing out the AST".

You can also do this in Haskell using the State monad and do notation.

That sounds a lot like the uniqueness types in languages Clean or Mercury for that matter. So is Mars a functional language with a linear/affine type or is there more to it. Wish Clean enjoyed more eyeballs than it does.

Something that bugs me in Haskell, and which Mars inherits as it is mostly the same semantics - you've taken the effort to create a good type system with optional types and type checking, only to decide to not actually use them for some common operations you're performing in the language (namely, head/tail).

    ?> Nil.head
    Runtime Error: List instance has no field 'head'

Such runtime errors could easily be avoided by making head/tail return Maybe, and using Nothing in the case of Nil. This hardly complicates code, but it provides the correct behavior, particularly when it comes to doing "records" properly. The Mars docs give an example of how I consider copying Haskell's semantics directly without improving them leads to flawed code.

    type Foo:
        X(u :: Num, v :: Num)
        Y(v :: Num)

There's nothing wrong with `v` here, as it is total, but you can easily introduce a runtime error by using `u` incorrectly.

    ?> x = Y(1)
    ?> x.u
    Runtime Error: Foo instance has no field 'u'

This is why using records in combination with sum types in Haskell is widely considered a bad idea. It's a misfeature as far as I'm concerned. If given the chance to redo Haskell's awful record system, I'd fix it.

The problem can be trivially avoided by making `u` return `Maybe Num` in this example, where it returns Nothing for Y and `Just 1` for X. Ideally, the compiler should check if field names are total over the constructors - if not, it should automatically return an optional type. If the fields are total there's no need. I doubt there would be any noticeable performance cost to moving the error to compile time - particularly because you don't actually need to use it in internal implementations of map/fold and such - you could have an internal function which mimics the current behavior, but don't expose it from the module.

Yeah, the Prelude in Haskell has a lot of warts.

Interestingly, if you use some of the Template Haskell derivations for lenses you get this record-of-sum optionality resolved at least partly.

(I am the designer of Mars.)

You make an interesting point. I haven't decided if I agree with you, but here are my thoughts.

If I understand you, you're saying that x.v should have type Num, but x.u should have type Maybe(Num) (because u is not totally covered). That sounds like a very bad thing, because it means that if I were to change the type so that u is covered, by changing Y to:

Y(u :: Num, v :: Num)

then suddenly everywhere I refer to x.u would break, because x.u would now have type Num, not Maybe(Num).

If I was to go for the "safe" option, it would have to be that all fields return a Maybe no matter what (and I think that would make fields quite unpleasant to use).

I think a better plan (which I've designed but didn't implement -- and I realise that now executing this plan would require a backwards incompatible version of the language) would be to do a simple static analysis of switch statements which records exactly which constructors a variable might have at any given program point, and make it a compile-time error to access a field of a variable unless it is provable that the variable has that field.

So in general, x.u would be a compile error. But this code would be legal, and never generate a runtime error:

switch x: case X: whatever(x.u)

You could also do error checking up front to avoid nesting your code too much:

switch x: case Y: error("blah") # Guaranteed to have a 'u'. whatever(x.u)

(For the record, I actually didn't blindly copy Haskell's semantics in this instance; I came up with this scheme myself and then only later discovered that Haskell had the exact same scheme!)

I'll give that I didn't give thought to what would happen if you later added u, but on the other hand, I'd consider that changing Y (if you expose it from the module) is a breaking change in any circumstance. If we consider for example, a Haskell equivalent with pattern matching.

    data Foo = X { u :: Int, v :: Int }
             | Y { v :: Int }

    bar :: Foo -> ...
    bar (X u v) = ...
    bar (Y v) = ...

If "u" were then added to Y, this pattern matching would break - the names of the fields don't matter in this case - the arity does. We just can't add to Y here without going through every pattern match on Foo to fix it.

The only case where changing Y is not a "breaking change" is if Y is never exported from the module - one of Haskell's most underused features is the ability to hide constructors and expose custom functions in their place - such functions would easily allow adding to Y (but not change the function y) without breaking the public interface - we need a default value for u though.

    module Foo (Foo, x, y) where

    data Foo = X Int Int
             | Y Int Int

    x :: Int -> Int -> Foo
    x = X

    y :: Int -> Foo
    y = Y defaultU

    defaultU = 0

    u :: Foo -> Maybe Int
    u (X a _) = Just a
    u _ = Nothing

    v :: Foo -> Int
    v (X _ b) = b
    v (Y b) = b

Just manually expanding what records do, except you have more control over changes to it - if you expect changes, you probably want to do this. The caveat is that you can no longer pattern match over X/Y from outside the module - unless you expose "isX, isY" functions, and use -XViewPatterns or some other extension. I actually prefer manually expanding things out this way because I consider Haskell's record system to be so poor.

It's not just a poor record system, but also the idea of encapsulation. To me, exposing constructors is like making the guts of your classes public in an OOP language - allowing any outsider to access fields really leads to tightly coupled code, and makes it difficult to introduce changes like the one you've suggested.

Consider a trivially modified list class where we want to optimise the performance of `length` if it were used frequently. I could define a data type for it with an extra "Int" field to hold the length.

    data LList a = Nil | Cons Int a (LList a)

What would I expose from this module? Almost certainly not the constructors, because I wouldn't want a consumer arbitrarily inserting integers, nor should they need to include it in their pattern matches - what I really want is to expose exactly the same "Cons" and "length" functions as the regular list which doesn't contain the head index.

    cons :: a -> LList a -> LList a
    cons a Nil = Cons 1 a Nil
    cons a (Cons n h t) = Cons (n + 1) a (Cons h t) 
    
    length :: LList a -> Int
    length Nil = 0
    length (Cons n _ _) = n

This is really what we want to expose, the constructors themselves don't matter - exposing constructors is only even useful in the cases where the structure of the type maps exactly to the operations we want to perform on it from outside the module, and thus we don't need to "hide" anything. It's not all that common, more often than not you want to hide things (OOP wasn't created by accident). Most haskell programmers think like C programmers - in terms of data rather than the operations you perform on the data.

If we continue this OOP analogy to the record syntax, we're treating Foo as some object exposing its public fields and some constructor functions.

    public class Foo {
        public Int u;
        public Int v;

        private Foo(Int u, Int v) {
            this.u = u;
            this.v = v;
        }
        
        private Foo(Int v) {
            this.v = v;
        }

        public static Foo X(Int u, Int v) { 
            return new Foo(u, v); 
        }

        public static Foo Y(Int v) {
            return new Foo(v);
        }
    }

Now, if we construct Foo.Y(1), and attempt to access `u`, we get the dreaded "NullReferenceException". In Haskell and Mars we've simply renamed `null` to "Runtime error", but it's effectively the same thing.

To me it's a design flaw. Optional obviates the need for null when used properly. I'm not sure what would be the best way to go about it - whether my previous suggestion, or making all fields Maybe, restricting records to types with only one constructor, or just do away with records altogether, because they're ultimately unnecessary. Writing out your own constructor functions gives you more flexibility, and having record syntax is not all that useful compared to say, using lenses.

To me, automatic Maybe inference seems correct. I don't think the concerns about types being broken (when one makes `u` total) are valid. That's really the point of a strong type system. You get the errors at compile time and they show you that the semantics of your program are inconsistent. My only issue with it is that it's a little too "magical". I'd rather that the behavior of record functions be more explicit. That makes lenses seem more attractive, as you mentioned.

Mm. The native library looks difficult to use and primitive (http://bazaar.launchpad.net/~mgiuca/mars/trunk/view/head:/li...) making this interesting in a theoretical sense, but not really in any practical sense (to me, at least).

To be fair, they admit it isn't usable for "real" software:

  About Mars
  ...
  Mars is an experiment, not a full-featured programming
  language. You can use it for playing with the boundaries
  between imperative and declarative programming, but we
  don't recommend you write real software with it.

This looks really good. What prevents them from committing this language to the public? Their About ("we don't recommend you write real software with it") is really off-putting for me because I can think of a fantastic use case for this in my current line of work but what does this even mean? I should expect compiler bugs? Conflicted.

What do you mean "committing to the public"? The source code is available, and it's GPL 3.0.

And I think their caveat is clear: they consider the language a research project at the moment, and not only do they not have enough confidence in the reliability for real-world use, they probably don't want the implied responsibility.

(I am the creator of Mars).

Yeah, it basically means a few things:

1. This is a research project. It doesn't have any support and if there are future versions, they might change the language in backwards-incompatible ways (but I will generally follow proper practices and bump the major version number in that case).

2. I am reaching the end of my PhD and I don't anticipate spending a lot of, if any, time working on Mars.

3. The language as it currently stands isn't very palatable to use for real-world software, basically because it is missing a lot of features. I've compiled a brief list here: http://mars-lang.appspot.com/docs/faq.html#what-features-is-...

I think if you were to play with it a bit, you would start to realise how primitive the language actually is ;)

Sorry to disappoint you. Having said that, the source code is fully available and GPL, so there is no technical or legal reason why you can't use it in any way you like.

Calling functional programming declarative seems like a bit of a stretch to me. I understand the reasoning. Still, when I read the headline I was imagining something pretty different.

---

The language looks pretty good. I think for most programmers some kind of vanilla ML would work well.

I hate the double colon, it's so unpythonic.

I believe the 'as' keyword would be more smooth:

    def hello(name as String) as String:
        var greeting as String
        greeting = 'Hello '+name
        return greeting

This isn't Python. :: is common in many languages, especially functional ones (which aren't just using it as a scope resolution operator).

Not sure what place "unpythonic" has as a criticism of a language other than Python. (As a matter of personal taste, I too prefer "as." Probably because I do most of my work in Python. But who cares?)

Reminds me of Cobra http://cobra-language.com/

And boo http://boo.codehaus.org

Even that isn't smooth enough for me. Why is the 'var as' still there? it's superfluous, ofcourse we're declaring a variable, there's nothing else that makes sense at that point. Why not:

  def hello(String name) as String:
        String greeting
        greeting = 'Hello '+name
        return greeting

which is how a lot of other languages are doing it. On the other hand, maybe I just don't like writing syntax that doesn't add any meaning :p

While definitely superfluous, it arguably makes it easier to read and scan.

I think that's a matter of habit. I've gotten far more used to the more condensed syntax, so for me that's faster to read and scan. I tend to prefer languages where there is little syntax wasted as a consequence.

C style type annotations that put type before name were never as elegant as pascal style annotations that put name before type. They are also more consistent.

elegance is debatable, and consistency is a matter of how the rest of the language is built. But you can still eliminate the superfluousness (is that a word?) by using

  greeting as String

or even

  greeting :: String

Either is fine, though my preference would then go to the latter option, since it'll be faster when scanning.

Having a language keyword which means "we are now defining a new variable" makes parsing easier, and you run into less ambiguity. See: http://en.wikipedia.org/wiki/Most_vexing_parse

Ambiguity in the language is a whole problem of its own. Ambiguity in parsing is also ambiguity in writing, so a language should avoid it all cost. It's true that forcing actions to come with extra words is a way to do that, but it's by no means the only one. It's possible to strive for non-ambiguity without extra syntax.

A good example of this case would be Java (like it or not):

  String Hello(String name) {
    String greeting;
    greeting = "hello " + name;
    return greeting;
  }

Say of the braces and the semicolons what you will, but the core syntax is unambiguous and doesn't have a single word that doesn't have semantic meaning.

I was exclusively talking about parsing ambiguity.

Using a keyword to introduce entity definitions (variables, functions, packages, etc.) gives the language more space to grow in syntax without worrying about such ambiguities later. You can construct a grammar without any ambiguities that does not use such keywords - such as with your example of Java - but you're going to have to keep this pitfall in mind anytime you change the grammar.

That's true, it does make it easier to evolve the syntax. The negative side of demanding a terse syntax is clear enough in the C# 6 changes (http://msdn.microsoft.com/en-us/magazine/dn683793.aspx), which are really showing a lot of bloat.

It's possible to debate the positive side too, but I do agree that constructing a language with a verboser non-semantic grammar is easier.

For things like "var" and "def", I'm coming to see them as a smidgen of up-front verbosity to prevent much later monstrosities.

You are completely ignoring error recovery, which these days of language-aware IDEs is much more important than optimal conciseness.

ArnoldC or go home.

  LISTEN TO ME VERY CAREFULLY hello
  I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE name
  GET TO THE CHOPPER greeting
  . . .
  ENOUGH TALK
  GIVE THESE PEOPLE AIR
  I'LL BE BACK greeting
  HASTA LA VISTA, BABY

(I have a truly marvelous ArnoldC string library (with string concatenation), which this margin is too narrow to contain.)

Of course, the comparison may not be very illuminating given that all ArnoldC variables are Int16s.

I'll counter your ArnoldC with http://shakespearelang.org/ But only because

  You are as brave as the sum of a fat little stuffed misused dusty old rotten codpiece and a beautiful fair warm peaceful sunny summer's day

is pure art.

I personally use "is" in my own pythonic language (name is string), "as" sounds like coercion rather than being constraining.

I believe it the usage of 'as' comes from the idea that whatever value the variable contains, it should be seen AS and present itself AS the type you're supplying. It doesn't need to be a string, it just needs to act 'as' a string.

Actually, they could of borrowed from Python 3's type annotation syntax! [1]

    def hello(name : String) -> io String:

[1] http://legacy.python.org/dev/peps/pep-3107/

Colon already means block in Python, overloading it for type annotations (ala pascal) would make the parser more complex and less error tolerant. Besides it is inconsistent, you really want

    def hello(name : string) : io String

The only reason they didn't do that is because colon also means block....

    Function hello(ByVal name As String) As String
        Dim greeting As String
        greeting = "Hello" + name
        Return greeting
    End Function

Great. I've thought about making a language with similar concepts, but I just can't get myself to make a proper stab at it. Not motivated enough. Perhaps scared of failing. I don't know.

Just try it.

At university, many of my fellow students wrote their own LISP, to get started with it.

I wrote a few DSLs in XML, which is rather easy too.

With this knowledge it is easier to learn new languages :)

The concepts are the important part. You can get a long way with a nasty interpreter to see if your concepts play out. :-)

If it's a "deep" concept, I'd pick a simple representation that I can implement without much cognitive overhead (a basic Lispish or Forthish stacks-and-registers syntax is usually something I can spin up in a few minutes) and then start layering my concepts in.

Some of the things you think will be awesome will end up just being wrong or inefficient, but you'll cut the loop down really quickly.

It makes it really easy to compare your hypotheses. If you want to factor them into a more conventional syntax model (c, python, haskell, etc.) you can always learn that along the way.

In fact, if you want to get really simple about it, write the code you would want to write and hand interpret it. You can get really far with simple pre-processors written in whatever text or AST manipulation environment with which you feel comfortable. (I'm notorious for being lazy and writing 50-pass compilers, just writing 10 to 200 line features and chaining them, all in a ghetto RPN.)

You won't fail. I worked through the How to Write Your Own Freaking Awesome Programming Language ebook. I made some toy languages and put them on Github (https://github.com/mattgreen/learning-language-design/tree/m...).

It's so much fun!

First time I ever saw on appspot.com 503 over quota message.

Are Google that measly with the bandwidth allocations?

Apparently you only get 1GB per day. I've enabled billing now so it's back on its feet.

Looks a lot like Python.

Reply on news.ycombinator.com