readme

diff --git a/README.md b/README.md
new file mode 100644 (file)
index 0000000..2649e86
--- /dev/null
+++ b/README.md
@@ -0,0 +1,64 @@
+# minfp: a minimal pure lazy functional language
+
+`minfp` is a functional programming language that aims to be as small as
+possible while still being feature rich.
+Most of the code is taken up by type checking.
+
+```
+$ wc -l *.[id]cl
+   23 ast.dcl
+   25 ast.icl
+    5 builtin.dcl
+   13 builtin.icl
+   12 check.dcl
+  168 check.icl
+    6 gen.dcl
+   39 gen.icl
+    7 int.dcl
+   49 int.icl
+   59 main.icl
+   10 parse.dcl
+  124 parse.icl
+   13 scc.dcl
+   41 scc.icl
+  594 total
+```
+
+### Features
+
+- Polymorphic type inference for the Hindley-Milner type system
+- Support for let polymorfism
+- Reasonable interpreter
+
+### CFG
+
+```
+minfp    := function+
+function := (op+ ['infixr' | 'infixl'] digit+ | id) id* '=' expr ';'
+expr     := expr op expr
+          | '\' id '.' expr
+          | '(' op+ ')'
+          | '\' id '.' expr
+          | '-'? digit*
+          | 'True' | 'False'
+          | 'code' id
+          | id
+id       := alpha (alnum)*
+op       := '!' | '|' | '@' | '#' | '$' | '%' | '^' | '&' | '*' | '=' | '+'
+          | '/' | '?' | '-' | '_' | '|' | ''' | '"' | '\' | ''' | '<' | '>'
+          | '.' | ':'
+alpha    := a | b | .. | z | A | B | .. | Z
+digit    := 0 | 1 | .. | 9
+alnum    := alpha | digit
+```
+
+A program always has to have a `start` function that takes no arguments.
+
+### Code instructions
+
+See `builtin.icl` for all builtin instructions that you can use with `code`
+
+### Todo
+
+- Code generation
+- ADTs

diff --git a/builtin.dcl b/builtin.dcl
new file mode 100644 (file)
index 0000000..1d2606a
--- /dev/null
+++ b/builtin.dcl
@@ -0,0 +1,5 @@
+definition module builtin
+
+from check import :: Scheme
+
+builtin :: [([Char], Scheme)]

diff --git a/builtin.icl b/builtin.icl
new file mode 100644 (file)
index 0000000..33c67e6
--- /dev/null
+++ b/builtin.icl
@@ -0,0 +1,13 @@
+implementation module builtin
+
+import Data.Func
+import check
+
+builtin :: [([Char], Scheme)]
+builtin =
+       [(['_if'],  Forall [['_ift']] $ TBool --> TVar ['_ift'] --> TVar ['_ift'] --> TVar ['_ift'])
+       ,(['_eq'],  Forall [['_eq']]  $ TInt --> TInt --> TBool)
+       ,(['_mul'], Forall [['_mul']] $ TInt --> TInt --> TInt)
+       ,(['_add'], Forall [['_add']] $ TInt --> TInt --> TInt)
+       ,(['_sub'], Forall [['_sub']] $ TInt --> TInt --> TInt)
+       ]

diff --git a/check.icl b/check.icl
index 76cde8c..e27f446 100644 (file)
--- a/check.icl
+++ b/check.icl
@@ -14,7 +14,7 @@ import Data.Map => qualified put, union, difference, find, updateAt
 import Data.Maybe
 import Text
 
-import ast, scc
+import ast, scc, builtin
 
 check :: [Function] -> Either [String] (Expression, [([Char], Scheme)])
 check fs
@@ -22,7 +22,7 @@ check fs
        | length dups > 0 = Left ["Duplicate functions: ":[toString n\\[(Function n _ _):_]<-dups]]
        = case partition (\a->a=:(Function ['start'] _ _)) fs of
                ([], _) = Left ["No start function defined"]
-               ([Function _ [] e:_], fs) = (\x->(e, x)) <$> runInfer (infer preamble (makeExpression fs e))
+               ([Function _ [] e:_], fs) = (\x->(e, x)) <$> runInfer (infer (fromList builtin) $ makeExpression fs e)
                ([Function _ _ _:_], _) = Left ["Start cannot have arguments"]
 
 makeExpression :: [Function] Expression -> Expression
@@ -54,15 +54,6 @@ instance toString Type where
        toString (a --> b) = concat ["(", toString a, " -> ", toString b, ")"]
 
 :: TypeEnv :== Map [Char] Scheme
-preamble :: TypeEnv
-preamble = fromList
-       [(['_if'],  Forall [['_ift']]
-               $ TBool --> TVar ['_ift'] --> TVar ['_ift'] --> TVar ['_ift'])
-       ,(['_eq'],  Forall [['_eq']]  $ TInt --> TInt --> TBool)
-       ,(['_mul'], Forall [['_mul']] $ TInt --> TInt --> TInt)
-       ,(['_add'], Forall [['_add']] $ TInt --> TInt --> TInt)
-       ,(['_sub'], Forall [['_sub']] $ TInt --> TInt --> TInt)
-       ]
 :: Subst :== Map [Char] Type
 
 :: Infer a :== StateT [Int] (WriterT [([Char], Scheme)] (Either [String])) a

diff --git a/tests/preamble.mfp b/tests/preamble.mfp
index 8f579a1..b984811 100644 (file)
--- a/tests/preamble.mfp
+++ b/tests/preamble.mfp
@@ -22,4 +22,4 @@ even i = if (i == 0) True (odd (i - 1));
 odd i = if (i == 0) False (even (i - 1));
 
 //start = on;
-start = \f. \g. \a. \b. f (g a) (g b);
+start = ($) id 42;