Skip to content

Instantly share code, notes, and snippets.

@othiym23

othiym23/ski.scala

Created Jun 19, 2011
Embed
What would you like to do?
the SK[I] combinator calculus encoded in Scala
/**
* Good luck!
*
* This represents the tersest possible translation of the SK[I] combinator
* calculus into Scala's version of the typed lambda calculus. Previous
* attempts used the direct encoding of the calculus into fully parameterized
* FunctionX objects, but that was both incomprehensible and unreadable.
* This version is still sort of hard to follow, given all of the type
* annotations, but is considerably more concise.
*
* Scala's inference rules are good enough to determine the return types,
* so they're mildly redundant here, but are also helpful to understanding
* what the combinators are doing, so I added them in.
*
* For a version of the SK[I] combinator calculus implemented in Scala's
* type system, see
*
* http://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-ski-calculus/
*
* The fact that this works shows that Scala's type system is Turing complete.
* I leave to you to decide whether this is a wondrous or terrible thing.
*
* I also leave to you to decide the practical utility of this code. It
* may or may not be interesting to people working on the 2011 ICFP
* contest.
*
* A trivial demonstration of the calculus at work:
*
* scala> val ii = SKI.i[Int]
* ii: (Int) => Int = <function1>
*
* scala> ii(4)
* res0: Int = 4
*
* scala> val ai = SKI.i[Any]
* ai: (Any) => Any = <function1>
*
* scala> ai(4)
* res1: Any = 4
*
* scala> ai("chowdah")
* res2: Any = chowdah
*
* Figuring out the parameterization for the set of SK[I] combinators in the
* canonical definition of Y would be a fun project.
*
* This naïve attempt doesn't work:
*
* def S = SKI.s[Any,Any,Any]
* def K = SKI.k[Any,Any]
* def I = SKI.i[Any]
* def Y = S (K (S(I)(I))) (S (S (K(S)) K) (K (S(I)(I))))
*
* The definition of SKI.i provides some clues as to how to proceed, but
* it's beyond me right now.
**/
object SKI {
def s[A,B,C]:(A => (B => C)) => (A => B) => (A => C) =
(f:A => B => C) => (g:A => B) => (x:A) => f(x)(g(x))
def k[A,B]:A => B => A =
(a:A) => (b:B) => a
def i[A]:A => A =
(s[A,A => A,A])(k[A,A => A])(k[A,A])
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment