Giter Site home page Giter Site logo

moon-lang's Introduction

Moon

Moon is an minimal, JIT-compilable, portable and secure code-interchange format. It is:

  • Safe: Moon isolates logic from side-effects, allowing you to securely run code from untrusted sources.

  • Fast: when compiled to JS, it beats popular libs by a large margin.

  • Compact: Moon has a canonical binary format for very small bundles.

  • Decentralized: Moon imports are hash-addressed, recursively resolved from IPFS.

  • Small: this entire implementation, for example, is a 7.5K JS file (gzipped).

Formally, Moon is just untyped λ-calculus extended with numbers, strings and maps.

Usage / Examples

Running code

To evaluate some code, simply use Moon.run():

const Moon = require("moon-lang")();

const program = `
  maximum = array =>
    (for 0 (get array "length") 0 index => result =>
      value = (get array (stn index))
      (if (gtn value result)
        value
        result))
  (maximum [1 7 6 9 5 2 8])
`;

console.log(Moon.run(program));

This is safe to do no matter the code contents, because Moon runs fully sandboxed.

Compiling Moon to a native function

You can also JIT-compile it to fast native functions:

const Moon = require("moon-lang")();

const factorial = Moon.parse(`n =>
  (for 1 (add n 1) 1 i => result =>
    (mul i result))
`);

console.log(factorial(4));

Decompiling a native function to Moon

And the other way around:

const Moon = require("moon-lang")();

const pair = Moon.parse("a => b => [a b]");

console.log(Moon.stringify(pair(1)));

Loading code from IPFS

Moon can recursivelly import hash-addressed terms from IPFS:

const Moon = require("moon-lang")(); 

(async () => {

  const sum = Moon.parse(await Moon.imports(`n =>
    // Imports array library from IPFS
    List = zb2rha9PW5Wnvhvz1n7pxXFZoMzeD3NxKYdZUHgxEsbhW8B4D
    reduce = (List "foldr")
    range = (List "range")

    (reduce (add) 0 (range 0 n))
  `));

  console.log(sum(5000000));

})();

Saving code to IPFS

It can also easily publish those terms:

const Moon = require("moon-lang")();

(async () => {

  const cid = await Moon.save("x => (mul x 2)");
  console.log(cid);

  const double = Moon.parse(await Moon.imports(cid));
  console.log(double(7));
  
})();

Performing side-effects (IO)

Moon itself is pure, but it can perform side-effective computations by injecting the effects from the host language. To avoid the "callback-hell", you can use Moon's monadic notation:

do = zb2rhkLJtRQwHz9e5GjiQkBtjL2SzZZByogr1uNZFyzJGA9dX

askPowerLevel = loop@ lazy =>
  | power =< (do "prompt" "What is your power level? ")
    (if (gtn (stn power) 9000)
      | (do "print" "No, it is not.")>
        (loop 0)
      | (do "print" "Ah, that's cute!")>
        (do "stop"))

(askPowerLevel 0)

You can run the code above using moon-tool:

moon runio zb2rhjR4sMEiMQ9m9bNCnavSUjEDzUvSrtAhuJStRWHcvNzb8

Optimizing code

  1. Use # to fully inline an expression.

  2. Use {fast:true} option (faster, only tradeoff is it can't be decompiled).

  3. Don't use recursive algorithms (map, reduce, etc.) directly on arrays; convert to churh-lists to enable fusion.

(async () => {

// Notice the hash (#): it fully inlines an expression, making it 8x faster.
const dotCode = `# x0 => y0 => z0 => x1 => y1 => z1 =>
  Array = zb2rhYmsjmQuJivUtDRARcobLbApVQZE1CwqhfnbBxmYuGpXx
  a = [x0 y0 z0]
  b = [x1 y1 z1]
  (Array "sum" (Array "zipWith" (mul) a b))
`;

// Also, use {fast:true}
const dot = Moon.parse(await Moon.imports(dotCode), {fast:true});

// Call it a ton of times
var dots = 0;
for (var i = 0; i < 1000000; ++i) {
  dots += dot(1)(2)(3)(4)(5)(6);
}
console.log(dots);

// Check the difference on the output
console.log(Moon.compile(await Moon.imports(dotCode)));

})();

Exporting Moon libs to npm

See this repository.

CLI

Check out moon-tool.

TODO

  • Time limit option

moon-lang's People

Contributors

alexvansande avatar marcoonroad avatar tloriato avatar victortaelin avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

moon-lang's Issues

An idea about infix functions.

Infix functions as a syntactic sugar can be burden for the compiler. On the other hand they make code much more readable.

So what if we allowed only infixr, infixl and infix (you could not specify precedence) and the type would be inferred by compiler (you cannot specify it yourself):

  • contains > => it is infixr
  • contains < => it is infixl
  • contains both or none => it is infix

So for example $> and >>= is infixr, <$ is infixl, <$> and == is infix.

listL = cons => nil => (cons 1 (cons 2 (cons 3 (cons 4 nil))))

listL = (:>) => nil => 1 :> 2 :> 3 :> 4 :> nil



listR = cons => nil => (cons (cons (cons (cons nil 4) 3) 2) 1)

listR = (<:) => nil => nil <: 4 <: 3 <: 2 <: 1

Replace Primitive term with Apply?

I've been thinking about the Primitive term. I know you need it for the compiler in order to know you cannot optimize pass it, but I think it shouldn't be an explicit term. I think it can be derived from Apply.

If all Primitives are just Applies, then be up to the runtime to provide functions of the matching name. The compiler should automatically just output non-defined Applies as dependencies (which I believe it already does)

Another issue is the binary format. It looks like you have encoded pris into binary, which I think makes the binary format far less stable. We would need to rev the binary format every time we added/removed a pri.

However, I think we can have the benefit of both worlds. We can add a "predef set" to the binary format. The predefs would map pri function names to short binary codes. This way you can have a stable binary format and be able to add/remove pris in the future with different predef sets. The runtime can just error if it sees a predef set it does not have.

Lambda calculus with named arguments.

I have stumbled upon this paper which explores the idea of extending lambda calculus with named arguments:

pair = fst => snd => fun =>
    (fun item1= fst  item2= snd)
triplet = fst => snd => thd => fun =>
    (fun item1= fst  item2= snd  item3= thd)

the cool thing about this, is that every function that works with pair will also work with triplet

snd = item2 => item2

(pair fst= 2017  snd= "Hello") snd // returns "Hello"
(triplet fst= 2017  snd= "Hello"  thd= "World") snd // also returns "Hello"

What do you think, would it be a worthwhile to explore this area? It looks like its going to work really well with partiall application and scott encoded data structures!

Should Moon have a type system? Should it keep primitive JSON?

Moon's core is simple and good enough to solve the problem of transporting code around safely. That works in the short term. Despite that, it might not be perfect and I see how some slight variations of it could be better on the long term. Some considerations:

  1. Should it have a type system?

If so, it should probably follow the philosophy of @Gabriel439's Morte and be based on the calculus of constructions. Here is an example of how Moon could look:

-- maps a function to a church-encoded list
map =
  -- Polymorphic types
  Type a => 
  Type b =>

  -- Function arguments
  (a -> b) func =>
  (List a) list =>

  -- Church-encoding of returned value
  Type r => 
  (a -> r -> r) cons => 
  a nil =>

  -- Returned value
  (list r (a head => cons (func head)) nil)

There are many problems with this idea, though. The Calculus of Constructions can't express inductive proofs, prove 0 != 1 and, perhaps more importantly to us, it can't express O(1) matching natively (although that is still possible with a few axioms, as shown here). We can get those with Fix, but lose consistency. But do we care about that? Moreover, what about inference? I think that shouldn't be part of the core (because it can be part of the editor, either hiding or auto-completing programs where possible).

  1. Should it actually have Num, Str and Map as primities?

If there is a type system, those things could be detected and compiled to the fast representations. Moreover, an editor could stringify strings as strings, lists as lists, etc., so the user wouldn't notice the difference. As such, I believe it would be safe to leave those out; only problem is I didn't have the time to try those things yet. If we do, in fact (other than the minor considerations above), Moon decays to being identical to Morte (i.e., just the calculus of constructions), which would be ideal.

I believe the answer to those questions should be "yes" and "no" respectivelly, but, for now, those pending details are not allowing me to actually go and do it that way.

Is Free more efficient in moon?

I have recently read an article called modern functional programming which makes some nice use of free monads (currently moon is using Free to express IO, but instead of ADT it uses strings).

The only problem with Free is its poor performance (unless you have supercompiler) - at least that's why it is slow in languages like Haskell. But isn't moon different, because it has #?

Is there something I can help you with?

I guess it would be best to create a separate issue, which lists things you would like to get sooner or later implemented, sorted from easiest to hardest.

How to compile following expressions to moon?

It seems like Let expressions do not play well with the idea of keeping AST:

-- applies function to every element of list
map _ [] = []
map f (x:xs)= f x : f xs

compiles to

map = f => list => (list
    Nil
    x => xs => (Cons (f x) (map f xs)))

but what happens if I want to keep the comment?

comment = msg => expr => expr
(comment "applies function to every element of list"
map = ... )

passing Let expression to function does not make sense, what shall I do?

Moon and run time errors.

I think it would be wise to allow only IO functions to throw run time errors.

What is your opinion?

Feature : Extractors.

Extractors look like a really nice feature, for illustration:

match [1] ([x]. x) ([]. 0) -- returns  1
match [ ] ([x]. x) ([]. 0) -- returns  0

You can define your own if you want:

pattern (Some x <- [x])
pattern (None   <- [ ])
match (Some x) ([x]. x) ([]. 0) -- returns  1
match  None    ([x]. x) ([]. 0) -- returns  0

Naturally it can be implemented on top of moon already, but if I would serialize my higher language (with extractors) into moon (that does not have them) and then deserialize it back I am going to lose all my abstraction.

Incomplete interop with JavaScript

You have implemented a runtime in JavaScript and moon-lang is meant to be called from JavaScript, yet there lacks faculties to return null, booleans, or arrays from moon-lang.

Is your goal to be useful from JavaScript, or are you just using JavaScript because its everywhere?

If you intend to have different non-JavaScript runtimes, then what you have today is fine.

However, my goals with deft is to interop fully with JavaScript, which means we might not be able to share runtimes/syntaxes

Make parentheses truly mathematical.

Currently parentheses always mean application, but it would be so much better, if they would behave like mathematical ones. Then we would gain:

1. Let without parentheses

( foo = something1 a b c d
  bar = something2 e f g
  baz = something3 v w x y
) foo bar baz

2. Nice monadic syntax

askPowerLevel = loop@ lazy =>
  do "prompt" "What is your power level?"  power =>
    if (gtn (stn power) 9000)
    ( do "print" "No, it is not."  _ =>
      loop 0 )
    ( do "print" "Ah, that's cute!"  _ =>
      do "stop" )

Can we optimize lambda (scott) encoding, to work well with todays hardware?

Since positive numbers are encoded as a function application:

one f x = f x
two f x = f ( f x )
three f x = f ( f ( f x ) )

it is trivial to optimize those expressions on the current hardware as

nTimes = builtin_vonneumann_apply_n_times
one f x = nTimes 1 f x
two = nTimes 2
three = nTimes 3

I think Idris does something similar for Nat = S Nat | Z.

  • Do we want to have this optimization for numbers?
  • Can we use similar optimization / compressioin for other primitives? (Perhaps automatically)

Replace Let term with Map?

Why does moon-core contain Let constructor when it also has Map?

Both gives names to expressions. But Map can also group multiple expressions under the same name, providing a simple module system.

Feature: Variable number of arguments seems really powerful!

I have not realized until now, how powerful actually that feature is

  • It greatly reduces boilerplate: map, zipWith, zipWith3, ... become just single map

  • It leads to some pretty elegant one liners: transpose x = (apply map list x)

  • And most importantly it allows you to resemble imperative blocks of code.

(andThen '(1 2 3)
  (map (add 1))
  (filter (lt 3))
  (take 10)
)

Understanding Lexer.

I read trough the moon-syntax.js, because I wanted to try out few ideas, but it is not exactly easy to understand (no type signatures, giant functions, no comments). The biggest obstacle so far for me were the function lifted and arguments of parse(vs, li, isKey, isPri).

What does function lifted do and what is the purpose of vs and li?

Also, what are the types of E T and S ?

Thanks!

Any plans for dev tools?

I really like this project (even though I don't understand a lot) but it's kinda hard for me to program without some text-editor support. Are there any plans to make some dev-tools with stuff like syntax highlight, auto-completion, or anything alike? I really like Ramda's online REPL for instance (http://ramdajs.com/repl/) and I use it every time I have to fiddle with an unknown function or just have fun with ramda.

I could volunteer to do something like Ramda's REPL but I'd need some help to deeply understand moon better (I'm not super good at FP and I'm accepting reading suggestions). Since apparently it's a fully declarative lang we could have some nice stuff like visual code editors that doesn't suck :)

Proposal: Documentation.

So I think every moon file should like this:

-- concatenates two lists   -- part of doc string
this : -- right now will behave as special version of doc string
  List = a => b => 
    ((a -> b -> b) -> b -> List a b)
  (List a b)
  -> (List a c)
  -> (List a c)

this =
  xs => -- list -- part of doc string
  ys => -- list -- part of doc string
    val => end => (xs val (ys val end))

-- EXAMPLES --

val = ...
end = ...

(this end end) == end
(this end (val 1 end)) == (val 1 end)
(this (val 1 end) end) == (val 1 end)
(this (val 1 end) (val 2 end)) == (val 1 (val 2 end))

The type signature should behave like a comment right now and later can be replaced with real type system.

REPL then should have available three commands: :type :documentation :example with obvious consequences.

I have already rewritten whole list library with this style, yet this requires some changes on the compiler part ->, : and optionally ==, which I might do on my own if you do not have time.

Problems with lambda encoding.

True  a _ = a
False _ a = a

not bool = bool False True

I see two problems with lambda encoded (scott in this case) data types.

1. It requires laziness for constructors with zero arguments.

True [] [1..1e+20] currently evaluates both the first and second branch, which is extremely inefficient.

2. It does not allow join related optimizations.

It is not possible to fuse b => not (not b) into b => b because we do not know, what b does with its arguments. On the other hand with Haskell ADT it is simple to optimize not . not into id because

not . not

\b -> not (not b)

\b -> not $ case b of
  True -> False
  False -> True

\b -> case b of
  True -> not False
  False -> not True

\b -> case b of
  True -> True
  False -> False

\b -> b

alternative syntax

I see you are a fan of terse functional programming syntax, but I don't think that is easy for people to pick up.

If you want moon-lang to be easier to learn for the everyday js dev, you'll need to use a more familiar syntax.

I don't think we even need to choose the one-true-syntax. I think we can just have 2 equivalent syntaxes with two different parsers building the same terms. Crazy idea, we can have a single canonical AST that the compiler understands, but have multiple AST/parser/syntaxes. We can then do AST to AST translation bi-directionally. This would mean we can instantly switch between different syntaxes.

Here's my straw man to get the discussion going: https://github.com/Pyrolistical/moon-lang/pull/1/files

Some features:

Additional sugar:

  • 'abcdef'.Slice(1, 3) desugared to Slice('abcdef', 1, 3)
  • 4 + 3 desugars to Add(4, 3) (never write x => y => x + y again, just use Add)
  • x.y and x['y'] desugars to Get(x, 'y')

Applying a bunch of sugar would turn:

strings => {
  len = Get(strings, 'length')
  For(0, len, '', i => result => {
    str = Get(strings, String(i))
    Concat(result, str)
  })
}

into

strings =>
  For(0 strings.length, '', i => result =>
    Concat(result, strings[i])
  )

Which you would then promptly replace with reduce

Bang notation and argument order.

I have been playing a little bit with bang notation and I have found it plays pretty poorly with current argument order (Verb First Subject Last).

-- `flip` wouldn't work, but `flip n` could, it is rather verbose though
|(a =< a => flatMap a as
  b =< b => flatMap b bs
  c =< c => flatMap c cs
  wrap (tuple 3 a b c))

With SFVL on the other hand it feels very natural.

|(a =< flatMap as
  b =< flatMap bs
  c =< flatMap cs
  wrap (tuple 3 a b c))

But then we could not write

transformation = list => (flatMap doC (flatMap doB (flatMap doA list)))

We obviously need some way to flip arguments in a pleasant way, so I thought we might provide syntax to turn any function to infixl.

transformation = list =>
  (list
    .flatMap doA
    .flatMap doB
    .flatMap doC)

and we could represent this syntax as . = x=>x (. flatMap doC (. flatMap doB (. flatMap doA list))), so we can later deserialize it back.

I am still wondering whether this solution isn't too complicated... What do you think?

Concatenative lambda calculus.

I have recently read Why Concatenative Programming Matters and got very interested in it. The advantages are:

  • You can get rid of Lambda and Var for MUCH smaller price, than you could in lambda calculus.
  • Functions can return multiple values. Not just tuples.
  • "Parallel compiler is a plain old map-reduce."
  • It is very efficient (stack based).
  • It is well researched topic. JVM and CPython bytecode are build on top of concatenative programming.
  • Concise, point free, less parentheses (=> small binary size).

The only disadvantage is, some functions are harder to express (but that is a real minority) which can be solved by syntactic sugar (or introducing , - post bellow) and ultimately we should not care about it, since moon is exchange format in the first place.

Records as basic data structure.

Have you thought about using records as basic data structure?.

Showcase:

  • function call
    (add 1 2)

  • dynamically sized data structure ~ list, map, set, vector, etc
    [1 (add 1 2)]

  • tuple is a record with fields 1, 2 .. n
    {1 (add 1 2)}

  • record with fields a, b
    {a=1 b=(add 1 2)}

  • field access

{a=1}.a
(.a {a=1}) -- .a is just a function
  • simple module system
echo {add  = (a. b. (add a b))} > ./foo.moon
echo {main = (foo.add 1 2)}     > ./bar.moon
run-moon ./bar.moon
3
  • let in expression
(let {a=1} (add a 1))
  • to keep some methods private you just use let
    ./foo.moon
(let 
  {inc  = (a. (add a 1))}
  {main = (inc 10)})
echo {main = (foo.inc 1)}     > ./bar.moon
run-moon ./bar.moon

error: record `foo` does not have field `inc`

Church vs Scott vs ??? Encoding.

I want to compile data (e.g. ADT) to moon

  • How do I decide which encoding should I use?
  • Does any simple rule exist?
  • Can it be automated or do I need some clever heuristic?

Updating dependencies with IPFS.

I have few problems with current package system. Listing from most important to the least:

1) It really makes testing your code inconvenient because

  • moon save requires internet connection.
  • moon run requires internet connection 90% of time
  • You have to run the command each time you change something.
  • You will often publish a code to IPFS just to realize, your code does not work.

2) One file changes, everything changes

  • One file modification requires manual update of its hash in every other file in your package.
  • Every file modification bumps the version of your package.
  • Git diffs are going to be crazy.

3) The hash is opaque.

  • How am I supposed to know to which version of List this hash zb2rhWevr8r6R66PNjESCuhiL9dkKUZKT8yMeCU2D97NoH5zC points to ? ( The answer is none, it points to Maybe.moon ).

Bang notation vs pattern matching.

It looks like | a =<(prompt "How are you?") could be simply replaced with | a = prompt "How are you?" where the second version is using simple pattern matching in let.

The big advantage is, we can pattern match on multiple arguments, and we don't need < and > anymore (and it is IMHO easier to understand):

(| a b = tuple 2 10 20
 | c = tuple 1 30
 d = 40
 add a (add b (add c d))) -- returns 100

The disadvantage is you have to write | _ = print "Hello" instead of (print "Hello")> and you cannot use ... <foo ... anymore, which might be a good thing, since it is really hard to understand code that contains multiple binds in one line.

Feature: Space indentation makes parentheses optional.

I am an advocate of Occam's razor and LISP languages are usually glaring example of unnecessary duplication of work.

Why do you need to wrap your code in parentheses, when compiler can do it for you?

(andThen '(1 2 3)
   (map (add 1))
   (filter (lt 3))
   (take 10))

Do you see the pattern?

  1. Eery line starts with (
  2. If the following line has the same indentation as the current one
    - then place ) at the end of line.
    - else place ) at the end of the last line with same indentation.

Thats it. Homoiconity is preserved and we get pleasant looking (even to javascript folks) expression.

andThen '(1 2 3)
   map (add 1)
   filter (lt 3)
   take 10

Moon module system.

  • Obtaining packages trough hash string seems a bit cumbersome to me. How do I find hash code of my function, will I have to open browser and search it? What if there is a typo in hash and its going to fetch a completely different function - such a bug might be hard to spot?

  • The get function is currently the only dynamic function in core ( it can output expressions with different types ). Do we really want this function? It will cause problems if we would like to migrate to types in the future. And it will also mess up some static optimizations.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.