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?
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.
read with the problem of typing apply. A statically typed apply would obviously work only on lists of statically known length containing values of statically known types. The resulting apply will not be be the same as the Lisp version in the same way that a simple (lambda (f x) (f x)) is more restricted in a statically typed language. –
Fredric (lambda (f x) (f x)) example -- it can call them all too, yet a function like that is perfectly typeable in static languages. In many of them, you won't be able to use it with a read function, since there isn't one. A notable exception is Typed Racket, which is a statically typed language that can deal fine with such functions and statically-unknown values. –
Fredric apply, and with that you completely ignore an interesting problem that points at a real deficiency of popular type systems. –
Fredric reduce -- I mentioned it in lots of comments. But in any case, it's obvious that the real question is not your problem, since instead of addressing it your answer goes back to the dynamic vs static debate. –
Fredric apply is "tightly bound to the dynamically typed nature of Lisp" in exactly the same way that any other HOF is. It's easy to give examples that use read and other statically-unknown values (incl. functions) for all of these functions -- for example, (mapcar (read) (read)) is exactly the same kind of demonstration. Yet, I don't see any Lispers walking around claiming that you can't write mapcar in a statically typed language. –
Fredric apply rather than other HOFs, is best understood as a question on it, rahter than on the merits of dynamic typing. It's true that for most HOFs, a statically typed implementation is easy and results in a polymorphic type. But apply defies that on two fronts: first, the type itself is much more complicated, and second, apply is doing something that cannot be done without support from the language: it reifies a first-class value (lists) as a second class one (argument lists). All of that is the interesting stuff that you just ignored. –
Fredric mapcar ("It's specific purpose is to be able to call arbitrary functions with arbitrary argument lists that are computed at runtime"), still irrelevant. –
Fredric mapcar in a static language is not only possible, it's easy, and they all have one. –
Fredric mapcar is also "hard" to do in static languages. –
Fredric apply function in Typed Racket. –
Fredric It is perfectly possible in a statically typed language. The whole java.lang.reflect thingy is about doing that. Of course, using reflection gives you as much type safety as you have with Lisp. On the other hand, while I do not know if there are statically typed languages supporting such feature, it seems to me it could be done.
Let me show how I figure Scala could be extended to support it. First, let's see a simpler example:
def apply[T, R](f: (T*) => R)(args: T*) = f(args: _*)
This is real Scala code, and it works, but it won't work for any function which receives arbitrary types. For one thing, the notation T* will return a Seq[T], which is a homegenously-typed sequence. However, there are heterogeneously-typed sequences, such as the HList.
So, first, let's try to use HList here:
def apply[T <: HList, R](f: (T) => R)(args: T) = f(args)
That's still working Scala, but we put a big restriction on f by saying it must receive an HList, instead of an arbitrary number of parameters. Let's say we use @ to make the conversion from heterogeneous parameters to HList, the same way * converts from homogeneous parameters to Seq:
def apply[T, R](f: (T@) => R)(args: T@) = f(args: _@)
We aren't talking about real-life Scala anymore, but an hypothetical improvement to it. This looks reasonably to me, except that T is supposed to be one type by the type parameter notation. We could, perhaps, just extend it the same way:
def apply[T@, R](f: (T@) => R)(args: T@) = f(args: _@)
To me, it looks like that could work, though that may be naivety on my part.
Let's consider an alternate solution, one depending on unification of parameter lists and tuples. Let's say Scala had finally unified parameter list and tuples, and that all tuples were subclass to an abstract class Tuple. Then we could write this:
def apply[T <: Tuple, R](f: (T) => R)(args: T) = f(args)
There. Making an abstract class Tuple would be trivial, and the tuple/parameter list unification is not a far-fetched idea.
apply -- much like $ being close to a statically typed version of funcall. –
Fredric apply a sequence of function argument is not something in the language. It's a second class concept that you can't access directly. As for the question if it could work, of course it can -- I've pointed at Typed Racket... (It's just hard.) –
Fredric The reason you can't do that in most statically typed languages is that they almost all choose to have a list type that is restricted to uniform lists. Typed Racket is an example for a language that can talk about lists that are not uniformly typed (eg, it has a Listof for uniform lists, and List for a list with a statically known length that can be non-uniform) -- but still it assigns a limited type (with uniform lists) for Racket's apply, since the real type is extremely difficult to encode.
HList would be more like it -- an arbitrary-length data structure that is fully typed at each member. And there exist such for Scala and Haskell, by the way. –
Lugubrious () as the empty list. Deep wizardry is used to create functions working on arbitrary HLists, but to do much of anything useful all the types must still be known at compile-time. –
Quaver 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.
read with the problem of typing apply. A statically typed apply would obviously work only on lists of statically known length containing values of statically known types. The resulting apply will not be be the same as the Lisp version in the same way that a simple (lambda (f x) (f x)) is more restricted in a statically typed language. –
Fredric (lambda (f x) (f x)) example -- it can call them all too, yet a function like that is perfectly typeable in static languages. In many of them, you won't be able to use it with a read function, since there isn't one. A notable exception is Typed Racket, which is a statically typed language that can deal fine with such functions and statically-unknown values. –
Fredric apply, and with that you completely ignore an interesting problem that points at a real deficiency of popular type systems. –
Fredric reduce -- I mentioned it in lots of comments. But in any case, it's obvious that the real question is not your problem, since instead of addressing it your answer goes back to the dynamic vs static debate. –
Fredric apply is "tightly bound to the dynamically typed nature of Lisp" in exactly the same way that any other HOF is. It's easy to give examples that use read and other statically-unknown values (incl. functions) for all of these functions -- for example, (mapcar (read) (read)) is exactly the same kind of demonstration. Yet, I don't see any Lispers walking around claiming that you can't write mapcar in a statically typed language. –
Fredric apply rather than other HOFs, is best understood as a question on it, rahter than on the merits of dynamic typing. It's true that for most HOFs, a statically typed implementation is easy and results in a polymorphic type. But apply defies that on two fronts: first, the type itself is much more complicated, and second, apply is doing something that cannot be done without support from the language: it reifies a first-class value (lists) as a second class one (argument lists). All of that is the interesting stuff that you just ignored. –
Fredric mapcar ("It's specific purpose is to be able to call arbitrary functions with arbitrary argument lists that are computed at runtime"), still irrelevant. –
Fredric mapcar in a static language is not only possible, it's easy, and they all have one. –
Fredric mapcar is also "hard" to do in static languages. –
Fredric apply function in Typed Racket. –
Fredric 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
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
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
apply. –
Fredric apply in CL is simply "This applies function to a list of arguments.", and in R5RS it's defined as "Calls proc with the elements of the list [...] as the actual arguments. (In any case, I highly doubt your "near certainty".) –
Fredric apply in Lisp is equivalent to java.lang.reflect.Method#invoke in Java. No relation to folds whatsoever. –
Leila def apply[@T, R](f: (@T => R), args: @T*): R = f(args: _*), where @T stands for a list of types, and args was something like an HList. –
Lugubrious In Haskell, there is no datatype for multi-types lists, although I believe, that you can hack something like this together whith the mysterious Typeable typeclass. As I see, you're looking for a function, which takes a function, a which contains exactly the same amount of values as needed by the function and returns the result.
For me, this looks very familiar to haskells uncurryfunction, just that it takes a tuple instead of a list. The difference is, that a tuple has always the same count of elements (so (1,2) and (1,2,3) are of different types (!)) and there contents can be arbitrary typed.
The uncurry function has this definition:
uncurry :: (a -> b -> c) -> (a,b) -> c
uncurry f (a,b) = f a b
What you need is some kind of uncurry which is overloaded in a way to provide an arbitrary number of params. I think of something like this:
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
class MyApply f t r where
myApply :: f -> t -> r
instance MyApply (a -> b -> c) (a,b) c where
myApply f (a,b) = f a b
instance MyApply (a -> b -> c -> d) (a,b,c) d where
myApply f (a,b,c) = f a b c
-- and so on
But this only works, if ALL types involved are known to the compiler. Sadly, adding a fundep causes the compiler to refuse compilation. As I'm not a haskell guru, maybe domeone else knows, howto fix this. Sadly, I don't know how to archieve this easier.
Résumee: apply is not very easy in Haskell, although possible. I guess, you'll never need it.
Edit I have a better idea now, give me ten minutes and I present you something whithout these problems.
flatTuple function of the type flatTuple :: (a, b...) -> (a,(b,...)) and apply the elements to the function recursivly. But by some reason, the type system is not happy with my idea sniff –
Hambley It is possible to write apply in a statically-typed language, as long as functions are typed a particular way. In most languages, functions have individual parameters terminated either by a rejection (i.e. no variadic invocation), or a typed accept (i.e. variadic invocation possible, but only when all further parameters are of type T). Here's how you might model this in Scala:
trait TypeList[T]
case object Reject extends TypeList[Reject]
case class Accept[T](xs: List[T]) extends TypeList[Accept[T]]
case class Cons[T, U](head: T, tail: U) extends TypeList[Cons[T, U]]
Note that this doesn't enforce well-formedness (though type bounds do exist for that, I believe), but you get the idea. Then you have apply defined like this:
apply[T, U]: (TypeList[T], (T => U)) => U
Your functions, then, are defined in terms of type list things:
def f (x: Int, y: Int): Int = x + y
becomes:
def f (t: TypeList[Cons[Int, Cons[Int, Reject]]]): Int = t.head + t.tail.head
And variadic functions like this:
def sum (xs: Int*): Int = xs.foldLeft(0)(_ + _)
become this:
def sum (t: TypeList[Accept[Int]]): Int = t.xs.foldLeft(0)(_ + _)
The only problem with all of this is that in Scala (and in most other static languages), types aren't first-class enough to define the isomorphisms between any cons-style structure and a fixed-length tuple. Because most static languages don't represent functions in terms of recursive types, you don't have the flexibility to do things like this transparently. (Macros would change this, of course, as well as encouraging a reasonable representation of function types in the first place. However, using apply negatively impacts performance for obvious reasons.)
try folds. they're probably similar to what you want. just write a special case of it.
haskell: foldr1 (+) [0..3] => 6
incidentally, foldr1 is functionally equivalent to foldr with the accumulator initialized as the element of the list.
there are all sorts of folds. they all technically do the same thing, though in different ways, and might do their arguments in different orders. foldr is just one of the simpler ones.
foldl is prefereable in most cases. –
Hambley apply function only calls the function once, with the supplied list as its arguments. The OP's example doesn't fold the list 1,2,3 with the add function, it calls the add function once with the list 1,2,3 and the add function does the looping itself. –
Mize apply. –
Fredric apply, but for the specific example quoted in the question, they work as a substitute; so this answer would be a correct way of implementing the specific example in the question, but not as a general substitute for apply. –
Amin apply. –
Tuscan apply. For example -- "6" works fine too, and it's a much shorter program, even. –
Fredric 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.
apply is that the function that is being applied doesn't need to change. –
Fredric varargs:. OTOH, apply can be used with anything (even +, as the question shows). –
Fredric apply can work with any lisp function, including ones that are not variable arity. (I just edited it and added such an example.) –
Fredric apply it with a list of 20 elements, you'd get an error at run time. That would be a bug, not a feature. The closest type-safe equivalent would be converting Tuples into multiple parameters. Scala's functions do have a tupled method which converts the whole parameter list into one Tuple. –
Seldon (car nil) as a runtime error, since they don't encode the length of the list in the type. So we can learn from this that a statically-type-safe implementation of apply requires that your type system is one that can talk about lists of a specific length. (But that still leaves a lot to do.) –
Fredric 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.
For Haskell, to do it dynamically, see Data.Dynamic, and dynApp in particular: http://www.haskell.org/ghc/docs/6.12.1/html/libraries/base/Data-Dynamic.html
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)
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.
apply1 f t = f t, apply2 f (t1,t2) = f t1 t2, and so on... –
Camden $ is not a form of an apply function -- it is more like funcall, except limited to one argument which makes it useless in Lisp. (But the one-argument limitation is obviously not a problem in Haskell.) –
Fredric © 2022 - 2024 — McMap. All rights reserved.
Invokethat is likeapply. – Mizeapplyis such a program. – RieblingInvokefunction has been around since 1.0 so it uses reflection. Dynamically generating glue code is a 4.0 feature. – Mizeapplyandeval(especially a metarciculareval) are some of the programs that are often claimed by proponents of dynamic typing to be impossible to implement in statically typed languages. At least in practically existing ones. For example, if you look at the source code for Haskell'sdynApplyin theData.Dynamicmodule, which is probably the closest thing to Scheme'sapply, you will find that it uses theunsafeCoercefunction, which is basically the same as an unrestricted unsafe cast in C, and thus explicitly and deliberately circumvents the type system. – Rieblingevalwithout circumventing the type system somehow. In fact, if you plug all the holes and take static typing to its logical conclusion, it's provably impossible to write an interpreter for a language in itself at all. Having used Scheme and Ruby before moving to Haskell, I do miss this sort of thing sometimes... – Quaverapply, to a degree, at the condition that arguments types and arity are fixed at compile-time. – Cointon