Skip to content

Instantly share code, notes, and snippets.

@Heimdell
Last active July 6, 2019 14:13
Show Gist options
  • Save Heimdell/a36b7b81081b95ece36665e2d9fd609d to your computer and use it in GitHub Desktop.
Save Heimdell/a36b7b81081b95ece36665e2d9fd609d to your computer and use it in GitHub Desktop.

Preface

In this document I will try to design a simple scripting language in informal way and describe why did I choose this or that feature to be present.

Guidelines

The language to be designed must be

  • simple;
  • ortogonal in features (no 2 features should do the same thing);
  • intuitive;
  • contain as least special cases as required for comfortable use;
  • doesn't break its own premises.

Elements

Scope

The scope is static; each name used must be declared. You cannot manipulate the scope in the runtime (we're not a LISP).

If a name declared shadows another name, it must be prefixed with a shadows keyword. If you add a shadows prefix when the variable isn't shadowing anything, it should give a warning.

Functions and values

Lets look on one of the worst cases: javascript.

function f(x) {
  f_body;
  return f_result
}

function g(y, z) {
  g_body;
  return g_result
}

var x = g(4, "foo")

f(5)

Honestly, we don't need the return keyword. The result of the function is its body (we will deal with side-effect later in a clever way, I promise).

The other thing we don't need is {}. We might replace { with =, and the } with, well, nothing? Let's try that.

fun f(x)    = f_body;
fun g(y, z) = g_body;

var x = g(4, "foo");

f(5)

Wow, so short, much nice. You know what? We have different declarations for functions and so called "vars" (as if we're ever going to reassign them!). We have them for no damn reason.

I quite like the approach of ML-family languages, where you define everything with let. However, they require

let
  rec f  x     = ...
  and g (y, z) = ...

  x = g (4, "foo")

in
  f (...)

constructs to designate that f and g can call each other. That's a nuisance. Lets define things like that:

let
  f x = ...
  g (y, z) = ...

  x = g (4, "foo")


f (5)

or like that

let f x = ...
let g (y, z) = ...
let x = g (4, "foo")

f(5)

In both cases, f and g are considered to be inside one let-block and therefore able to call each other.

Also, notice we've dropped the () around f's argument. Why? Because ()-thing is used to group. There's nothing to group in one argument.

Local definitions

You might ask, what if I have this?

function vector_norm(x, y) {
  function sqr(x) {
    return x * x
  }
  return sqrt(sqr(x) + sqr(y))
}

And I will answer - you do that:

let vector_norm (x, y) =
  let sqr x = x * x

  sqrt (sqr x + sqr y)

Nice and clean.

Curried functions

We have this function in javascript:

function f (x, y) {
  return function (z) {
    return x * (y + z)
  }
}

Yeah, it returns another function. Why? Because you want to do

[1,2,3].map(foo(4,5))

The map method expects a function as an argument, and you don't want to write

[1,2,3].map(function (z) {return foo(4,5,z) })

because that's messy as hell.

Let's write it like that:

let f (x, y) = fun z => x * (y + z)

Hmm, no, still messy. How about...

let f (x, y) z = x * (y + z)

Yeah! Much bettah!

Also, let's declare as much functions curried as possible.

Instead of

let add (x, y) = x + y

lets write

let add x y = x + y

Then application of this functions from this:

add(1, 2 + 3)

becomes this:

add 1 (2 + 3)

Operator/funcall priorities

You remember we dropeed () in definitons? There is another change we have to make after that.

Look onto this expression:

let a = sin x + cos y

it actually means this:

let a = (sin(x)) + (cos(y))

So, the priority of funcall is maximal, and every operator has lower priority than that.

Let-blocks

So, let essentially works like this:

let
  <definitions>
  <more-definitions>
  ...

let
  <even-more-definitions>
  ...

...

<body>

The indentation of first token after let keyword will decide the level at which all definitions of the block should start. (So, we're not nailed down to 2 space indent). All sequental let-blocks share scope. After all the let-blocks there is a single expression. Function body can only be a naked expression, or a let-block. The let-block does not share indentation with other let-blocks, they may have different indentation level.

So, the following code

let
  sqr x = x * x

  field_density g m r =
    let inv x = 1 / x

    g * m * inv (sqr r)

field_density g_const 1000 42

means

let {
  sqr x = x * x;

  field_density g m r =
    let {
      inv x = 1 / x;
    }
    g * m * inv (sqr r);
}
field_density g_const 1000 42;

Objects

Javascript objects are quite nice, actually.

let qux = "hello"

{
  foo: (x, y) => ...,
  bar:  x     => ...,
  x:    1,

  qux, // <- we _captured_ that thing

  method(z) {
    return z + 1
  },

  willBeInNextJSVersion(w) => w - 1,
}

... there is still a lot of things that are bad.

  1. The field declarations are comma-separated. Why not semicolon? Actually, how about that: both , and ; are allowed separators for object field.
  2. The bodies of declarations cannot refer to each other, even methods.
  3. Inconsistency. We have fields in form of x: 1 and methods. And lambda-fields. I prefer all declarations to be in form of let x = ... and captures to be simply x.

Let's fix that:

let qux = "hello"

{
  let foo (x, y) = bar(x) + y; (* we are referring to `bar` below here *)
  let bar  y     = y + x;

  let x = 1;

  let qux;

  let method    z = z + 1;
  let thatThing w = w - 1;
}

Hmm, too much let. It doesn't do anything here. We're in one scope - the object itself.

Second try:

let qux = "hello"

{
  foo (x, y) = ...;
  bar  x     = ...;

  x = 1;

  qux;

  method    z = z + 1;
  thatThing w = w - 1;
}

Much better.

Private fields

There are two ways of doing it.

First is "you ain't gonna need it":

let
  sqr x = x * x
  add (x, y) = x + y
{
  foo (x, y) = add (sqr x, sqr y)
}

Here, we "export" the foo field and sqr remains hidden, yet accessible in object.

Second way is

{
  private
    sqr x = x * x
    add (x, y) = x + y

  foo (x, y) = sqr x + sqr y
}

where private makes a block, like let does.

I think we can allow both. Second way will be translated into first during compilation, anyway.

Subobjects

Sometimes, you have 2-3 finctions that depend on a private one; and you want rest of your object to be independent of that.

{
  {
    private
      sqr x = x * x

    foo x = sqr x + 1
    bar x = sqr x - 1
  }

  qux x = x + 1
}

Sometimes, you want to extend your object.

extend thing {
  foo z = z - 1
}

You know what? I'll make extend a function. Yeah. You can't access private fields of thing anyway.

Somethimes, you want to access public fields though, and not via .-syntax. Well, I have not-that-good news for ya. I decide to have static scope. It means, if you use a name, somewhere in the file this name is declared.

Therefore, to get fields in unqualified manner, you should pattern-match the object:

let {foo, quz} = thing

Let's go back to object updates. We can change extend a bit: now the last parameter is not an "update" object, but an update function!

extend thing fun {foo, quz} => {
  bar x = foo x + qux 1
}

Do you see what I did there? The function pattern-matches its argument to request fields foo and quz out of it.

You know what? This fun keyword for functions makes it harder to read. Let's replace it with... \?

extend thing \{foo, quz} => {
  bar x = foo x + qux 1
}

I think, it didn't become worse, at the very least.

Modules

We will definitely need to add structure to our program.

For simplicity, the name of the current module will be derived from its path.

Submodules

Sometimes, you want to prepare your code to splitting onto submodules, yet still want it to reside in one file for a bit. For that we present a module keyword.

let bar x = x + 1

let parser = module {
  foo = bar x  (* will not compile, both `bar` and `x` are outside of the `module` keyword *)
}

let x = 1

What is does? It prohibits for enclosed expression the access to the outside scope.

Imports

We need some things to get in that submodule scope, though. And there is an import keyword for that.

(in foo/bar.scr)

let
  import control.functor {map, fill}
{
  stream = module {
    ...
  }

  parser = module
    let
      import foo.bar.stream as stream
    {
      ...
    }
}

That seems nice.

The import of control.functor is unqualified: map and fill are accessible directly.

The import of foo.bar.stream is qualified: you have to use stream.makeStream to access its contents.

If you drop that as stream you will have to do it like foo.bar.stream.makeStream, which is probably not what you want. There's no way to dump contents of the module into current scope. All imports are either qualified or you have to manually enumerate the names to be imported.

Exports

That's even simpler. We don't need any keywords for that.

The module body is expression. If it happens to be an object, we can say that it exports all the public fields of that object.

The recursive imports are allowed. Since we have static scope, we can find a name which is an import loop and throw a "linker" error.

Algebraic datatypes

Congrats, we've reached the scary part.

What is an "algebraic datatype"? Its a "sum of products", where sum is + and product is *.

What does it mean?

Well, if we simplify things beyond the point mathematicians start hitting us with books, product is a tuple. Or an object.

This code declares a constructor of a "product" object:

let point x y z = {x, y, z}

See? Products are easy.

Basically, each object is a "product" of its fields.

Why is it called that? Sorry, won't explain - this ain't a category theory lecture.


Okay, what's a "sum"? We will take a look on a particular case called "designated sum".

What the hell does it mean, you ask? That means, each component of the sum is given a name.

Each component of a sum is a product with a name. To put is simply - component of a sum is a variant of object of whole type. We will call them constructors later. We call them that, because they are functions that return a constructed object.

They are also called case classes in Scala and data classes in Kotlin (so the programmers will not run away in fear).

Let's look onto an example.

let list = {
  Push  {head, tail}
  Empty

  let headOrElse l def =
    match l with
    | Push {head} -> head
    | Empty       -> def

  let l123 = Push(1, Push(2, Push(3, Empty)))
}

This code declares a "list type". We have 2 variants:

  1. Push {tail, tail} - this is a variant of the list object that has fields head and tail. It represents a Push of some head element into some other tail list. It doesn't do anything, it just, yo know, represents - I mean "holds that data".
  2. Empty - it represents an empty list, therefore no fields.

Then it matches over some list, checks which constructor was used to build the object and retrieves a field.

If you still don't get it, please have this messy js chunk, which does the exact same thing.

class List {
  class Push extends List {
    constructor (head, tail) {
      Object.assign(this, {head, tail})
    }
  }

  class Empty extends List {
    constructor () {}
  }

  static headOrElse(l, def) {
    switch (l.constructor) {
      case Push:  return l.head
      case Empty: return def
    }
  }

  static l123 = new Push(1, new Push(2, new Push(3, new Empty())))
}

The match is basically nanotech-level switch, which can not only select a branch by an int or a string, but deconstruct the object to a arbitrary depth. You can't fallthrough from a branch to another branch. You also have no way to deconstruct a function - for obvious reasons.

Assuming you get what constructor is, let's remember that it has a name. The usual perks of "being named" apply: it can be imported, exported, you can assign it to a name.

Fast-match

I would also like to have ?:-style analog of match. The hell, I will steal this operator.

Lo and behold!

let safeTail l = l is Push {tail} ? tail : Empty

It is actually ... "is" ...[ "{"..."}" ] "?" ... ":" ...-operator, and this is what match-expression will be translated into.

If-statement

We can say "you ain't gonna need this", because

let if bool selectors =
  match bool with
  | True  -> selectors.then
  | False -> selectors.else

let and a b = if (a) {
  then = if (b) {
    then = True
    else = False
  }
  else = False
}

(oh, the language is lazy, btw, so that's actually fine)

... but I like to have multi-way if. Like that:

let
  fib x = if
    | x == 0 -> 1
    | x == 1 -> 1
    | else   -> fib (x - 1) + fib (x - 2)

I also like to have it embedded into match as well.

match l with
| Push {head} if
  | isOdd? head -> head

| Empty -> 0

Here if none of the if-branches apply, it fallsthrough to the next branch. If no branch apply at all, it's an irrecoverable error.

Strings

Typical strings. With interpolation. Like that:

let x = 1
let y = "foo"
let str = "x = {% x %}, y = {% y %}"

The syntax was selected, because it makes it easy to distinguish interpolators on lexer phase.

Tuples

These things:

let foo = (1, 2)
let foo_1 = foo._1
let foo_2 = ._2 foo

Yes, ._2 is a function that retrieves field _2 from its argument. It is more useful than you can imagine. Also, .foo retrieves field foo. And .+ retrieves operator +, but it becomes a function.

Tuples make things very simple. You remember those arguments?

let foo (x, y) = x + y

foo (1, 2)

They are tuples now! And, of course, tuples can be pattern-matched in match blocks as well.

I'm thinking about adding fields ._3, ._4 and so on, to the tuples with appropriate length.

Also, tuples are kinda-lists, so maybe we should add a .rest field? It will cut first argument off a tuple. in case of (a, b) (which silently is (a, (b, ())), it will return (b, ()). So, our tuples are proper-LISP lists!

And the .length field is mandatory, ofc.

The single concern is - we have to make a tuple constructor(s?). Should we call them (), (,()), (,), (,,), (,,,)... or Tuple0, Tuple1, Tuple2...? I like first variant more. Oh, about variants - the tuple is a "canoncal" "product" from a "sum of products" story.

We actually need only 2 constructors - (,) (2-tuple) and () (0-tuple).

There are 2 ways to match a tuple:

match x with
(* way 1*)
| (42, a, b) -> a + b          (* Notice we require 1st elem to be 42 here.
                                * This will match only tuple with length 3.
                                *)
| (a, x)     -> a - x          (* this will only match tiple with a length of 2 *)
| (a, ...xs) -> (a + 2, ...xs) (* this wil match any tuple with length >= 1
                                * We also have _spliced_ xs here.
                                *)

Names

We need to establish something. There are 4 kinds of names:

  1. values - a, b, rest
  2. constructors - A, B, Rest
  3. operators - +, *, >>=
  4. operators-constructors - ::, :>, :@?

Operators (and operators-constructors!) are just names that happen to be used as operators. If you wrap it with (), you make it just a name.

(* Three entirely equal functions *)
let add      = (+)
let add2 x   = (+) x
let add3 x y = (+) x y

(* Three entirely equal functions, as well *)
let push      = (::)
let push2 x   = (::) x
let push3 x y = (::) x y

Values (and constructors!) are just names that are happen to be used normally. If you wrap them with `, they can be made into operators.

let add = (+)
let sum = 1 `add` 2 `add` 3

This is just a syntax. This is the single difference between names and operators. We will turn the AST into S-expression along the interpretation process, and names and operators will become one thing.

Lists

We have all the machinery now.

let l = [1,2,3,4]
let r = [
  1
  2
  3
  4
]

let g = (1) :: (2) :: (3) :: (4) :: Nil  (* this is what l and r will actually be *)

match g with
| [a, b, 4, d]    -> a      (* match a list of given length *)
| [a, b, ...rest] -> a + b  (* match a list with given prefix *)
| a :: b :: rest  -> a - b  (* the same as previous, in "desugared" mode *)
| []              -> 0      (* the empty list *)
| Nil             -> 0      (* also the empty list *)

The list will be desugared into g-version. We will have Nil and :: ctors in some pervasive-module. Notice the parenthes! They are here to disambiguate operator priorities!

Operator priorities

This theme is very slippery. But I want to implement the best scheme I know.

  1. Sometimes, we will have qualified operators. Even if its qialified, it's an op.

    let foo = {
      let (+?) a b = a - b
    }
    
    let bar = 1 foo.+? 42

    It looks outright bad. However, in case of name-turned-into-op its not that bad.

    let parser = {
        let or l r = ...
    }
    
    let intOrString = int `parser.or` string
  2. We will not have integer priorities, like infix left 5 @>->--, --<-<@.

    Instead, we will have relative priorities.

    arith = trasitive operator group
     infix      ^    tighter than *, /
     infix left *, / tighter than +, -
     infix left +, -
    
     all             looser  than bitwise
     all             tighter than comparison

    This means:

    1. We declare operator group "arith";
    2. bitwise and comparison are imported;
    3. ^ has more priority than *, /, + and - (because "transitive");
    4. * and \ have more priority than + and -;
    5. *, /, + and - have left associativity;
    6. ^ has no associativity (requires parens if chained);
    7. all operators have less priority that any of the "bitwise" group;
    8. all operators have more priority that any of the "comparison" group;
    9. arith, bitwise and comparison objects will exist in runtime (for simplicity of implementation), but any usage aside from import/export and declaring a group is prohibited; you can't pattern-match them either.

    Also, if the group is not transitive, to use op1 and op2 in the same expr, they have to be related directly.

    If operators are not related directly, are not related transitive inside a group or their groups aren't related directly, you need parens to diambiguate them. Parser (actually, another block) will enforce that.

Side effects

How do we do our IO?

Like this:

main = do (io)
  putStrLn "Hello"
  name <- getLine
  putStrLn "Hello, {% name %}!"
  return name

This is exactly the same as

main = do (io)
  ()   <- putStrLn "Hello"
  name <- getLine
  ()   <- putStrLn "Hello, {% name %}!"
  return name

Which will be preprocessed into

main = 
  putStrLn "Hello"              io.>>= \() ->
  getLine                       io.>>= \name ->
  putStrLn "Hello, {% name %}!" io.>>= \() ->
  io.return (name)

Names like return (IT'S A NAME!), throw (YES, THIS IS TOO), catch (NAME, YES) and some more will be taken from provided object (in our case, io).

The >>= operator functions like Promise#then from js.

main = 
  putStrLn("Hello").then(_ =>
    getLine.then(name =>
      putStrLn(`Hello, {name}!`).then(_ =>
        Promise.resolve(name)
      )
    )
  )

Preface

The actual language will be translated into IL first; here I will describe that IL.

Language

Variable

Just a variable.

Let-expression

Expression in form

let
  y = x
  x = 1
  foo = \x -> plus x 1  (* all functions are written as lambdas *)
y

All declarations in a block are mutually recursive, even values are.

Calls

Each function has only 1 argument.

So

f x y

means

(f(x))(y)

If-match

"A universal matching construct"

This construct is used to match Variants, Objects and Constants. Since booleans are Variants, we're equipped to do all kinds of stuff.

It has the following syntax:

<subject> "is" <prism> [ "{" <fields> "}" ] "?" <yes-branch> ":" <no-branch>

It can be chained on <no-branch>.

Examples:

pt is Point {x, y} ? plus x y : 0

fib = \x ->
  (equal x 0) is True ? 1 :
  (equal x 1) is True ? 1 :
    plus (fib (minus x 1)) (fib (minus x 2))

Object creation

Since let-block already deals with scoping, this thing only enumerates the fields to be included in object.

let
  x = 1
  y = plus z 2
  z = 3
{x, y}

We collect the requested values and create a stack frame.

Creation of lambda

Normal lambda, as you expect.

\x -> plus x 1

Creation of prism

Point {x, y, z}

You cannot assign prism to another name and use it in if-match.

Constants

Integer, float-point and string constants are accepted. Strings aren't interpolatable.

Evaluation

Runtime

We have a stack of frames.

Each frame is a map from names to values.

Values are immutable. I may or may not add possible mutable values in future.

Variable

We perform lookup on the stack. If the variable is not found, an exception is thrown.

Let-block

We convert the block of definitions into a stack frame and then evaluate body with that additional frame on the stack.

Definitions-to-frame

To convert the definitions to frame, we must evaluate the bodies with that very frame we must end with on top of the current stack.

We make the frame depend on itself (fsharp compiler makes it Lazy behind the scene), and delay the evaluations of the bodies to the moment someone calls the definition.

Lambda

We construct a closure (its a lambda which from now on additionally holds the current stack).

Call

We force the evaluation of function, and apply it to a lazily-evaluated argument.

Application

If the function is a closure, we add assign formal argument to be factical one in the stack from the closure, and eval the closure body with that stack.

If the function is a prism, we convert it to the field accumulator and re-run application.

Accumulator is a (maybe, partially) constructed object. It has

  1. a reference to a prism;
  2. a frame of fields that are already bound;
  3. a list of not-yet-bound (free) fields.

If accumulator has no free fields, an exception is thrown.

If accumulator has a free field, it is removed from "free" list and assigned to be the argument in the frame.

If the function is a builtin, it's invoked with the argument

If the function is an error, it ignores the argument and the same error is returned.

Otherwise, an exception is thrown, since our "function" is not a function at all.

Object creation

We collect values for the selected names and build a frame.

If-match

We force the evaluation of the subject.

If its an error, the same error is returned. Otherwise, we try to deconstruct it.

If the deconstruction is successful (it returns a stack frame with requested fields), we run yes-branch with that frame-with-fields on top of the stack. Otherwise, we run no-branch with the stack unchanged.

Deconstruction

We have special prisms for each constant type.

We also have a special prism for objects. It checks if object has all fields the if-match operator is requesting.

The prism for variants checks if the variant was built with the same prism, and then extracts requested fields.

If Built-in function, closure or prism is being deconstructed, an exception is thrown.

If the prism cannot deconstruct the subject, the call is unsuccessful (but no exception is thrown).

Prisms

A prism is returned.

Constants

A constant is returned.

{-# language RecursiveDo #-}
import Control.Monad.Catch
import Control.Monad.Reader
import qualified Data.Map as Map
import Data.Map (Map)
import System.IO.Unsafe (unsafeInterleaveIO)
-- | The "source" of IL.
data AST
= Var { astName :: Name }
| Let { astContext :: Map Name AST -- ^ declarations in let-block
, astBody :: AST
}
| Call { astFunc :: AST
, astArg :: AST
}
| IFMatch { astSubject :: AST -- ^ subject of pattern-match
, astPrism :: Prism -- ^ structure to be matched
, astProjection :: [Name] -- ^ fields to be extracted
, astYes :: AST -- ^ success route
, astNo :: AST -- ^ failure route
}
| Create { astNames :: [Name] } -- ^ names to be included into obj
| Lambda { astName :: Name
, astBody :: AST
}
| Constant { astConstant :: Constant }
deriving (Show)
data Constant
= Integer Integer
| String String
| Float Double
deriving (Show)
-- | A variant of structure
data Prism = Prism
{ prismCtor :: Name -- ^ constructor name
, prismArgs :: [Name] -- ^ field names
}
deriving (Eq, Show)
type Name
= String
----
data Value
= EConstant Constant
| EObject (Map Name Value) -- ^ object carries an eval context
| EClosure Ctx Name AST -- ^ lambda is a closure
| EPrism Prism
| EBIF BIF
| EVariant Prism (Map Name Value) [Name] -- ^ collected args and free args
| EError String
deriving (Show)
-- | Evaluation context
type Ctx = [Map Name Value]
-- | Built-in function
data BIF = BIF { bifName :: Name, runBIF :: Value -> IO Value }
instance Show BIF where
show = bifName
data NameNotDefined
= NameNotDefined Name
deriving (Show)
data Oversaturated
= Oversaturated Prism (Map Name Value)
deriving (Show)
data Undersaturated
= Undersaturated Prism (Map Name Value) [Name]
deriving (Show)
data NotAFunction
= NotAFunction Value
deriving (Show)
data CannotDeconstruct
= CannotDeconstruct Value Prism [Name]
deriving (Show)
instance Exception NameNotDefined
instance Exception Oversaturated
instance Exception Undersaturated
instance Exception NotAFunction
instance Exception CannotDeconstruct
eval :: AST -> ReaderT Ctx IO Value
eval (Var name) = do
lookupVar name
-- The scope of let becomes another stack frame.
eval (Let scope ast) = do
frame <- evalScope scope
local (frame :) $ do
eval ast
-- We delay the evaluaion of argument.
eval (Call f x) = do
f <- eval f
x <- lazily $ eval x
apply f x
eval (IFMatch subj prism fields yes no) = do
subj <- eval subj
case subj of
-- An error consumes everything.
EError msg -> do
return $ EError msg
-- We can only deconstruct variant by prism if all args were supplied.
EVariant p acc []
| p == prism -> do
let frame = Map.filterWithKey (\k _ -> k `elem` fields) acc
local (frame :) $ do
eval yes
| otherwise -> do
eval no
-- Object can be deconstructed by empty-named prism.
EObject acc | prismCtor prism == "" -> do
if all (`Map.member` acc) fields
then do
let frame = Map.filterWithKey (\k _ -> k `elem` fields) acc
local (frame :) $ do
eval yes
else do
eval no
EVariant p acc free -> do
throwM $ Undersaturated p acc free
subj -> do
throwM $ CannotDeconstruct subj prism fields
eval (Create names) = do
values <- mapM lookupVar names
return $ EObject (Map.fromList (zip names values))
-- Lambda is turned into a closure.
eval (Lambda name ast) = do
ctx <- ask
return $ EClosure ctx name ast
eval (Constant constant) = do
return $ EConstant constant
apply :: Value -> Value -> ReaderT Ctx IO Value
apply (EError msg) _ = do
return $ EError msg
apply (EBIF bif) val = do
lift $ bif `runBIF` val
-- Before applying a closure, we restore eval ctx and assign (arg = val).
apply (EClosure ctx name ast) val = do
local (const ctx) $ do
local (Map.singleton name val :) $ do
eval ast
-- If applying a prism, we start argument collection.
apply (EPrism p) val = apply (EVariant p Map.empty (prismArgs p)) val
-- If there are unassigned fields, assign the topmost.
apply (EVariant p acc (name : names)) val = do
return $ EVariant p (Map.insert name val acc) names
apply (EVariant p acc []) val = do
throwM $ Oversaturated p acc
apply f _ = do
throwM $ NotAFunction f
-- The scope of let-block is recursive (hence `mdo`).
evalScope :: Map Name AST -> ReaderT Ctx IO (Map Name Value)
evalScope decls = mdo
frame <- local (frame :) $ mapM (lazily . eval) decls
return frame
lazily :: ReaderT x IO a -> ReaderT x IO a
lazily action = ReaderT $ \arg ->
unsafeInterleaveIO $ action `runReaderT` arg
-- Search the context for a name.
lookupVar var = do
ctx <- ask
maybe (throwM $ NameNotDefined var)
return $ foldr search Nothing ctx
where
search frame rest = Map.lookup var frame `orElse` rest
Just a `orElse` b = Just a
Nothing `orElse` b = b
#nowarn "62" // ml-style templates
#nowarn "40" // recursive values
type ast =
| Var of name // x
| Let of let_body // let foo = 1, bar x = foo + x in bar
| Call of call_body // f x
| IfMatch of if_match_body // pt is Point? {x, y} -> x + y : 0
| Create of name list // {x, y, z}
| Lambda of lambda_body // \x -> f x
| Prism of prism // Push {head, tail}
| Constant of constant // "foo"
and let_body =
{ scope : (name, ast) Map
body : ast
}
and call_body =
{ f : ast
x : ast
}
and if_match_body =
{ subject : ast
prism : prism
fields : name list
yes : ast
no : ast
}
and prism =
{ ctor : name
fields : name list
}
and lambda_body =
{ arg : name
body : ast
}
and constant =
| Int of int
| String of string
| Float of double
and name = string
////
type value =
| VConstant of constant
| VObject of frame
| VClosure of closure_body
| VPrism of prism
| VBIF of bif
| VVariant of variant_body
| VError of string
and frame = (name, value Lazy) Map
and stack = frame list
and closure_body =
{ stack : stack
arg : name
body : ast
}
and bif = value Lazy -> value Lazy
and variant_body =
{ ctor : prism
bound : frame
free : name list
}
let letrec scope body =
Let
{ scope = Map.ofList scope
body = body
}
type node = (value, ast) either ref
and ('a, 'b) either =
| Left of 'a
| Right of 'b
////
exception Undefined of name
exception Oversaturation of variant_body * value Lazy
exception NotAFunction of value
exception CannotDeconstruct of value
let lookup (stack : stack) (name : name) : value Lazy =
let rec loop =
function
| frame :: _
when Map.containsKey name frame ->
frame.[name]
| _ :: rest ->
loop rest
| [] ->
raise <| Undefined name
loop stack
let rec eval (stack : stack) (ast : ast) : value Lazy =
match ast with
| Var name ->
lookup stack name
| Let block ->
let frame = evalScope stack block.scope
eval (frame :: stack) block.body
| Call call ->
let f = eval stack call.f |> force
let x = eval stack call.x
apply stack f x
| Create names ->
let values = List.map (lookup stack) names
lazy (Seq.zip names values |> Map.ofSeq |> VObject)
| IfMatch matcher ->
let subj = eval stack matcher.subject |> force
match subj with
| VError msg -> lazy (VError msg)
| _ ->
match deconstruct matcher.prism matcher.fields subj with
| Some frame -> eval (frame :: stack) matcher.yes
| None -> eval stack matcher.no
| Lambda lam ->
lazy
(VClosure
{ stack = stack
arg = lam.arg
body = lam.body
})
| Prism p ->
lazy (VPrism p)
| Constant c ->
lazy (VConstant c)
and deconstruct
(prism : prism)
(fields : name list)
(value : value)
: frame option
=
match prism.ctor, value with
| "", VObject frame ->
if Seq.forall (fun field -> Map.containsKey field frame) fields
then
Some <| Map.filter (fun k _ -> Seq.contains k fields) frame
else
None
| "0", VConstant (Int _)
| "'", VConstant (String _)
| "0.0", VConstant (Float _) ->
Seq.zip prism.fields [lazy value]
|> Map.ofSeq
|> Some
| _, VVariant variant when prism = variant.ctor ->
Some <| Map.filter (fun k _ -> Seq.contains k fields) variant.bound
| _, VBIF _
| _, VClosure _
| _, VPrism _ ->
raise <| CannotDeconstruct value
| _ ->
None
and evalScope
(stack : stack)
(scope : (name, ast) Map)
: (name, value Lazy) Map
=
let rec frame =
Map.map
(fun _ v -> lazy (force <| eval (frame :: stack) v))
scope
frame
and apply stack f x =
match f with
| VClosure clos ->
let stack' = Map.ofList [clos.arg, x] :: clos.stack
eval stack' clos.body
| VPrism prism ->
let structure =
VVariant
{ ctor = prism
bound = Map.empty
free = prism.fields
}
apply stack structure x
| VVariant variant ->
match variant.free with
| field :: rest ->
lazy VVariant
{ variant with
free = rest
bound = Map.add field x variant.bound
}
| [] ->
raise <| Oversaturation (variant, x)
| VBIF bif ->
bif x
| VError msg ->
lazy (VError msg)
| f ->
raise <| NotAFunction f
and force x = x.Force()
letrec
[ "y", Var "x"
"x", Constant (Int 1)
]
(Var "y")
|> eval []
|> (fun x -> x.Force())
|> printfn "%A"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment