From e641250705517611f422540d8ba3fe021e6068b3 Mon Sep 17 00:00:00 2001
From: pimjager <pim@pimjager.nl>
Date: Wed, 13 Apr 2016 21:01:50 +0200
Subject: [PATCH] Added examples from markus

---
 examples/Markus/assignment_to_builtin.spl     | 13 ++++++
 examples/Markus/higher_order_functions.spl    | 38 ++++++++++++++++
 examples/Markus/identity(2).spl               | 45 +++++++++++++++++++
 examples/Markus/infinite_type_shouldfail.spl  |  6 +++
 examples/Markus/multiple_recursion.spl        | 14 ++++++
 examples/Markus/multiple_recursion_values.spl | 24 ++++++++++
 examples/Markus/overloading.spl               |  7 +++
 .../polymorphic_value_again_shouldfail.spl    | 11 +++++
 .../Markus/polymorphic_value_shouldfail.spl   | 14 ++++++
 examples/Markus/recursion.spl                 | 14 ++++++
 .../Markus/self_application_shouldfail(1).spl |  6 +++
 examples/Markus/stress_test.spl               |  8 ++++
 sem.icl                                       |  1 -
 13 files changed, 200 insertions(+), 1 deletion(-)
 create mode 100644 examples/Markus/assignment_to_builtin.spl
 create mode 100644 examples/Markus/higher_order_functions.spl
 create mode 100644 examples/Markus/identity(2).spl
 create mode 100644 examples/Markus/infinite_type_shouldfail.spl
 create mode 100644 examples/Markus/multiple_recursion.spl
 create mode 100644 examples/Markus/multiple_recursion_values.spl
 create mode 100644 examples/Markus/overloading.spl
 create mode 100644 examples/Markus/polymorphic_value_again_shouldfail.spl
 create mode 100644 examples/Markus/polymorphic_value_shouldfail.spl
 create mode 100644 examples/Markus/recursion.spl
 create mode 100644 examples/Markus/self_application_shouldfail(1).spl
 create mode 100644 examples/Markus/stress_test.spl

diff --git a/examples/Markus/assignment_to_builtin.spl b/examples/Markus/assignment_to_builtin.spl
new file mode 100644
index 0000000..dc53a37
--- /dev/null
+++ b/examples/Markus/assignment_to_builtin.spl
@@ -0,0 +1,13 @@
+// Do you allow this program?
+
+blaat(x) :: [a] -> Bool
+{
+  return True;
+}
+
+f()
+{
+  // This tries to assign to the built-in function isEmpty.
+  // Adapt this line if your isEmpty is called differently.
+  isEmpty = blaat;
+}
diff --git a/examples/Markus/higher_order_functions.spl b/examples/Markus/higher_order_functions.spl
new file mode 100644
index 0000000..717f881
--- /dev/null
+++ b/examples/Markus/higher_order_functions.spl
@@ -0,0 +1,38 @@
+// Depending on your design decisions this might or might not compile.
+// In our course we don't require higher-order functions.
+// In fact, our grammar doesn't even allow function types in type signatures.
+// Anyway, this could be an idea for assignment 4.
+
+map(f, list)
+// This doesn't parse according to our grammar
+// :: (a -> b) [a] -> [b]
+{
+  if( isEmpty(list) )
+    return [];
+  else
+    return f(list.hd) : map(f, list.tl);
+}
+
+foldl(f, z, list)
+{
+  if( isEmpty(list) )
+    return z;
+  else
+    return foldl(f, f(z, list.hd), list.tl);
+}
+
+// Some operators wrapped in a function.
+plus(x, y) { return x + y; }
+and(b, c) { return b && c; }
+ge18(x) { return x >= 18; }
+
+// Sums all the elements of an Int list.
+sum(list) { return foldl(plus, 0, list); }
+
+// Checks whether all elements in a list of Booleans are True
+all(list) { return foldl(and, True, list); }
+
+// Checks whether in a list of numbers everybody is older than 18
+allOlderThan18(list) { return all(map(ge18, list)); }
+
+main() { return; }
diff --git a/examples/Markus/identity(2).spl b/examples/Markus/identity(2).spl
new file mode 100644
index 0000000..96232a2
--- /dev/null
+++ b/examples/Markus/identity(2).spl
@@ -0,0 +1,45 @@
+// Various versions of the identity function
+
+// Identity for integers
+// The type signature forces the function to have a more concrete type than it could have.
+id_int(x) :: Int -> Int
+{
+  return x;
+}
+
+
+// Polymorphic identity with type signature
+id_poly_with(x) :: a -> a
+{
+  return x;
+}
+
+
+// Polymorphic identity without type signature
+// Type checking should figure out the type forall a . a -> a
+id_poly_without(x)
+{
+  return x;
+}
+
+
+// Clumsy polymorphic identity
+// Type checking should give type forall a . a -> a
+id_poly_wtf(x)
+{
+  var a = x;
+  var b = a;
+  var c = b;
+  return c;
+}
+
+
+// Clumsy identity for integers
+// Type checking should give type Int -> Int
+id_int_wtf(x)
+{
+  var a = x;
+  Int b = a;
+  var c = b;
+  return c;
+}
diff --git a/examples/Markus/infinite_type_shouldfail.spl b/examples/Markus/infinite_type_shouldfail.spl
new file mode 100644
index 0000000..603cec0
--- /dev/null
+++ b/examples/Markus/infinite_type_shouldfail.spl
@@ -0,0 +1,6 @@
+// An example from the slides. This should give a type error.
+
+f(x)
+{
+  return f( (x, x) );
+}
diff --git a/examples/Markus/multiple_recursion.spl b/examples/Markus/multiple_recursion.spl
new file mode 100644
index 0000000..8676358
--- /dev/null
+++ b/examples/Markus/multiple_recursion.spl
@@ -0,0 +1,14 @@
+// Generates a list of zeros and ones
+
+flip(n, l)
+{
+  if( n <= 0 )
+    return l;
+  else
+    return flop(n-1, 0:l);
+}
+
+flop(n, l)
+{
+  return flip(n, 1:l);
+}
diff --git a/examples/Markus/multiple_recursion_values.spl b/examples/Markus/multiple_recursion_values.spl
new file mode 100644
index 0000000..171ee5a
--- /dev/null
+++ b/examples/Markus/multiple_recursion_values.spl
@@ -0,0 +1,24 @@
+// Do you allow this?
+// Explain why or why not.
+
+var ones = 1:ones;
+
+var flip = 0:flop;
+var flop = 1:flip;
+
+// What about this?
+var flup = (flap.hd):flup;
+var flap = (flup.hd):flap;
+
+
+
+// For testing
+take(n, list)
+{
+  if( n <= 0 )
+    return [];
+  else
+    return list.hd : take(n-1, list.tl);
+}
+
+main() { print(take(10,flip)); }
diff --git a/examples/Markus/overloading.spl b/examples/Markus/overloading.spl
new file mode 100644
index 0000000..754da17
--- /dev/null
+++ b/examples/Markus/overloading.spl
@@ -0,0 +1,7 @@
+// At this point you maybe don't see what the problem is.
+// Wait until you try to implement your code generator.
+
+equal(x, y)
+{
+  return x == y;
+}
diff --git a/examples/Markus/polymorphic_value_again_shouldfail.spl b/examples/Markus/polymorphic_value_again_shouldfail.spl
new file mode 100644
index 0000000..a9bda2e
--- /dev/null
+++ b/examples/Markus/polymorphic_value_again_shouldfail.spl
@@ -0,0 +1,11 @@
+// Another variant of the polymorphic value problem.
+
+// This is perfectly fine
+var tuple1 = (1:[], True:[]);
+
+// This should fail.
+var l = [];
+var tuple2 = (1:l, True:l);
+
+
+main() { return; }
diff --git a/examples/Markus/polymorphic_value_shouldfail.spl b/examples/Markus/polymorphic_value_shouldfail.spl
new file mode 100644
index 0000000..0b868ee
--- /dev/null
+++ b/examples/Markus/polymorphic_value_shouldfail.spl
@@ -0,0 +1,14 @@
+// This is an example why you need the value restriction.
+// This program should give a type error in some way.
+
+// The empty list [] usually has polymorphic type forall a.[a], but you
+// cannot give the variable l this type. See below what can go wrong.
+var l = [];
+
+f()
+{
+  // If l has polymorphic type forall a . [a], the next two lines are possible.
+  l = 1:l;
+  l = True:l;
+  return;
+}
diff --git a/examples/Markus/recursion.spl b/examples/Markus/recursion.spl
new file mode 100644
index 0000000..6dbd124
--- /dev/null
+++ b/examples/Markus/recursion.spl
@@ -0,0 +1,14 @@
+// Greatest common divisor,
+// "The granddaddy of all algorithms, because it is the oldest nontrivial
+// algorithm that has survived to the present day." -- Don Knuth
+
+// This one only works for positive n, m
+gcd(m, n)
+{
+  if( n < m )
+    return gcd(n, m);
+  else if( n == m )
+    return n;
+  else // n > m
+    return gcd(m, n - m);
+}
diff --git a/examples/Markus/self_application_shouldfail(1).spl b/examples/Markus/self_application_shouldfail(1).spl
new file mode 100644
index 0000000..41397da
--- /dev/null
+++ b/examples/Markus/self_application_shouldfail(1).spl
@@ -0,0 +1,6 @@
+// A classic from computer science.
+// The function \x.x x can not be typed in let-polymorphic type systems.
+f(x)
+{
+  return x(x);
+}
diff --git a/examples/Markus/stress_test.spl b/examples/Markus/stress_test.spl
new file mode 100644
index 0000000..11e52b2
--- /dev/null
+++ b/examples/Markus/stress_test.spl
@@ -0,0 +1,8 @@
+// Uncomment lines one by one. How far can you take your compiler?
+
+f0(x) { return (x, x); }
+f1(x) { return f0(f0(x)); }
+// f2(x) { return f1(f1(x)); }
+// f3(x) { return f2(f2(x)); }
+// f4(x) { return f3(f3(x)); }
+// f5(x) { return f4(f4(x)); }
diff --git a/sem.icl b/sem.icl
index 7af3b20..eb626f6 100644
--- a/sem.icl
+++ b/sem.icl
@@ -105,7 +105,6 @@ typeExpr (VarExpr p (VarDef ident fs)) = gets (\(st, r)->'Map'.get ident st)
     >>= \mt->case mt of
         Nothing = liftT $ Left $ UndeclaredVariableError p ident
         Just t = unify t fs
-
 typeOp2 :: Expr Expr Op2 [Type] Type -> Env Type
 typeOp2 e1 e2 op ts ret = typeExpr e1 >>= \t1-> typeExpr e2 >>= \t2->
     unify t1 t2 >>= \t3->if (isMember t3 ts) (pure ret)
-- 
2.20.1