(* 
   exp.sml - `SML type exponentiator'

   This is a simple demonstration of the fact that the typechecking
   algorithm for Standard ML is exponential in the worst case.  This
   program implements such a worst case.

   Finding the source of exponential complexity is left as an execrise
   to the compiler.

   Author: Sergey Berezin (sergey.berezin@cs.cmu.edu)
   Version: 1.0
   Keywords: SML, typechecker, exponential, complexity

   Copyright (C) 2001 Sergey Berezin

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*)

fun f1(true, x) = x
  | f1(false, x) = 0

fun f2(true, f) = f
  | f2(false, f) = f1

fun f3(true, f) = f
  | f3(false, f) = f2

fun f4(true, f) = f
  | f4(false, f) = f3

fun f5(true, f) = f
  | f5(false, f) = f4

fun f6(true, f) = f
  | f6(false, f) = f5

fun f7(true, f) = f
  | f7(false, f) = f6

fun f8(true, f) = f
  | f8(false, f) = f7

fun f9(true, f) = f
  | f9(false, f) = f8

fun f10(true, f) = f
  | f10(false, f) = f9