Cannot create apply function with static language?

Question

I have read that with a statically typed language like Scala or Haskell there is no way to create or provide a Lisp apply function:

(apply #'+ (list 1 2 3)) => 6

or maybe

(apply #'list '(list :foo 1 2 "bar")) => (:FOO 1 2 "bar")
(apply #'nth (list 1 '(1 2 3))) => 2

Is this a truth?

Answer 1

A full APPLY is difficult in a static language.

In Lisp APPLY applies a function to a list of arguments. Both the function and the list of arguments are arguments to APPLY.

• APPLY can use any function. That means that this could be any result type and any argument types.

• APPLY takes arbitrary arguments in arbitrary length (in Common Lisp the length is restricted by an implementation specific constant value) with arbitrary and possibly different types.

• APPLY returns any type of value that is returned by the function it got as an argument.

How would one type check that without subverting a static type system?

Examples:

(apply #'+ '(1 1.4))   ; the result is a float.

(apply #'open (list "/tmp/foo" :direction :input))
; the result is an I/O stream

(apply #'open (list name :direction direction))
; the result is also an I/O stream

(apply some-function some-arguments)
; the result is whatever the function bound to some-function returns

(apply (read) (read))
; neither the actual function nor the arguments are known before runtime.
; READ can return anything

Interaction example:

CL-USER 49 > (apply (READ) (READ))                        ; call APPLY
open                                                      ; enter the symbol OPEN
("/tmp/foo" :direction :input :if-does-not-exist :create) ; enter a list
#<STREAM::LATIN-1-FILE-STREAM /tmp/foo>                   ; the result

Now an example with the function REMOVE. We are going to remove the character a from a list of different things.

CL-USER 50 > (apply (READ) (READ))
remove
(#\a (1 "a" #\a 12.3 :foo))
(1 "a" 12.3 :FOO)

Note that you also can apply apply itself, since apply is a function.

CL-USER 56 > (apply #'apply '(+ (1 2 3)))
6

There is also a slight complication because the function APPLY takes an arbitrary number of arguments, where only the last argument needs to be a list:

CL-USER 57 > (apply #'open
                    "/tmp/foo1"
                    :direction
                    :input
                    '(:if-does-not-exist :create))
#<STREAM::LATIN-1-FILE-STREAM /tmp/foo1>

How to deal with that?

• relax static type checking rules

• restrict APPLY

One or both of above will have to be done in a typical statically type checked programming language. Neither will give you a fully statically checked and fully flexible APPLY.

Answer 2

A list in Haskell can only store values of one type, so you couldn't do funny stuff like (apply substring ["Foo",2,3]). Neither does Haskell have variadic functions, so (+) can only ever take two arguments.

There is a $ function in Haskell:

($)                     :: (a -> b) -> a -> b
f $ x                   =  f x

But that's only really useful because it has very low precedence, or as passing around HOFs.

I imagine you might be able to do something like this using tuple types and fundeps though?

class Apply f tt vt | f -> tt, f -> vt where
  apply :: f -> tt -> vt

instance Apply (a -> r) a r where
  apply f t = f t

instance Apply (a1 -> a2 -> r) (a1,a2) r where
  apply f (t1,t2) = f t1 t2

instance Apply (a1 -> a2 -> a3 -> r) (a1,a2,a3) r where
  apply f (t1,t2,t3) = f t1 t2 t3

I guess that's a sort of 'uncurryN', isn't it?

Edit: this doesn't actually compile; superseded by @FUZxxl's answer.

Answer 3

On this page, I read that "Apply is just like funcall, except that its final argument should be a list; the elements of that list are treated as if they were additional arguments to a funcall."

In Scala, functions can have varargs (variadic arguments), like the newer versions of Java. You can convert a list (or any Iterable object) into more vararg parameters using the notation :_* Example:

//The asterisk after the type signifies variadic arguments
def someFunctionWithVarargs(varargs: Int*) = //blah blah blah...

val list = List(1, 2, 3, 4)
someFunctionWithVarargs(list:_*)
//equivalent to
someFunctionWithVarargs(1, 2, 3, 4)

In fact, even Java can do this. Java varargs can be passed either as a sequence of arguments or as an array. All you'd have to do is convert your Java List to an array to do the same thing.

Answer 4

The benefit of a static language is that it would prevent you to apply a function to the arguments of incorrect types, so I think it's natural that it would be harder to do.

Given a list of arguments and a function, in Scala, a tuple would best capture the data since it can store values of different types. With that in mind tupled has some resemblance to apply:

scala> val args = (1, "a")
args: (Int, java.lang.String) = (1,a)

scala> val f = (i:Int, s:String) => s + i
f: (Int, String) => java.lang.String = <function2>

scala> f.tupled(args)
res0: java.lang.String = a1

For function of one argument, there is actually apply:

scala> val g = (i:Int) => i + 1
g: (Int) => Int = <function1>

scala> g.apply(2)
res11: Int = 3

I think if you think as apply as the mechanism to apply a first class function to its arguments, then the concept is there in Scala. But I suspect that apply in lisp is more powerful.

Answer 5

See his dynamic thing for haskell, in C, void function pointers can be casted to other types, but you'd have to specify the type to cast it to. (I think, haven't done function pointers in a while)

Answer 6

It's trivial in Scala:

Welcome to Scala version 2.8.0.final ...

scala> val li1 = List(1, 2, 3)
li1: List[Int] = List(1, 2, 3)

scala> li1.reduceLeft(_ + _)
res1: Int = 6

OK, typeless:

scala> def m1(args: Any*): Any = args.length
m1: (args: Any*)Any

scala> val f1 = m1 _
f1: (Any*) => Any = <function1>

scala> def apply(f: (Any*) => Any, args: Any*) = f(args: _*)
apply: (f: (Any*) => Any,args: Any*)Any

scala> apply(f1, "we", "don't", "need", "no", "stinkin'", "types")
res0: Any = 6

Perhaps I mixed up funcall and apply, so:

scala> def funcall(f: (Any*) => Any, args: Any*) = f(args: _*)
funcall: (f: (Any*) => Any,args: Any*)Any

scala> def apply(f: (Any*) => Any, args: List[Any]) = f(args: _*)
apply: (f: (Any*) => Any,args: List[Any])Any

scala> apply(f1, List("we", "don't", "need", "no", "stinkin'", "types"))
res0: Any = 6

scala> funcall(f1, "we", "don't", "need", "no", "stinkin'", "types")
res1: Any = 6