No se puede crear con el lenguaje aplicar la función estática?

https://stackoverflow.com/questions/3693447

02-10-2019
|

Pregunta

He leído que con un lenguaje de tipos estáticos como Scala o Haskell no hay manera de crear o proporcionar una función apply Lisp:

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

o tal vez

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

¿Es esta una verdad?

Solución

Una aplicación total es difícil en un lenguaje estático.

En Lisp Aplicar Aplica una función a una lista de argumentos. Tanto la función y la lista de argumentos son los argumentos de aplicar.

Aplicar puede utilizar cualquier función. Eso significa que este podría ser cualquier tipo de resultado y los tipos de argumentos.
Aplicar toma argumentos arbitrarias de longitud arbitraria (en Common Lisp la longitud está limitada por un valor constante específico de la implementación) con tipos arbitrarios y posiblemente diferentes.
Aplicar devuelve cualquier tipo de valor devuelto por la función que tiene como argumento.

¿Cómo sería una verificación de tipos que sin subvertir un sistema de tipo estático?

Ejemplos:

(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

ejemplo Interacción:

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

Ahora un ejemplo con la REMOVE función. Vamos a eliminar el carácter a partir de una lista de cosas diferentes.

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

Tenga en cuenta que también se puede aplicar aplica en sí, ya que es una función de aplicación.

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

También hay una ligera complicación debido a que la función de transformación toma un número arbitrario de argumentos, donde sólo los últimos necesidades argumento sea una lista:

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

¿Cómo lidiar con eso?

relajarse reglas tipo de cheques estáticos
Restringir SOLICITAR

Uno o ambos de arriba tendrá que ser hecho en un tipo de forma estática típica comprueban Lenguaje de Programación. Ni le dará una forma estática totalmente comprobado y se aplican plenamente flexible.

Otros consejos

Es perfectamente posible en un lenguaje de tipos estáticos. Toda la manivela de java.lang.reflect se trata de hacer eso. Por supuesto, el uso de la reflexión le da la seguridad de tipos todo lo que tiene con Lisp. Por otro lado, si bien no sé si hay lenguas tipos estáticos de apoyo de estas características, me parece que se podría hacer.

Te voy a enseñar cómo Calculo Scala podría extenderse a apoyarlo. En primer lugar, vamos a ver un ejemplo más simple:

def apply[T, R](f: (T*) => R)(args: T*) = f(args: _*)

Esto es real código Scala, y funciona, pero no va a funcionar para cualquier función que recibe tipos arbitrarios. Por un lado, la notación T* devolverá un Seq[T], que es una secuencia de tecleado homegenously. Sin embargo, hay secuencias heterogéneamente-mecanografiadas, como la nodo Hlist .

Por lo tanto, en primer lugar, vamos a tratar de utilizar HList aquí:

def apply[T <: HList, R](f: (T) => R)(args: T) = f(args)

Eso se sigue trabajando Scala, pero que poner una gran restricción en f diciendo que debe recibir una HList, en lugar de un número arbitrario de parámetros. Digamos que utilizamos @ a hacer la conversión de parámetros heterogéneos a HList, de la misma manera conversos * de parámetros homogéneos a Seq:

def apply[T, R](f: (T@) => R)(args: T@) = f(args: _@)

No estamos hablando de la vida real Scala más, pero una mejora hipotética a la misma. Esto parece bastante a mí, si T que se supone que es un tipo por la notación parámetro de tipo. Podríamos, tal vez, simplemente extender la misma manera:

def apply[T@, R](f: (T@) => R)(args: T@) = f(args: _@)

Para mí, parece que podría funcionar, sin embargo, que puede haber ingenuidad por mi parte.

Vamos a considerar una solución alternativa, una función de unificación de listas de parámetros y las tuplas. Digamos Scala finalmente había unificado lista de parámetros y tuplas, y que todas las tuplas eran subclase a un Tuple clase abstracta. Entonces podríamos escribir lo siguiente:

def apply[T <: Tuple, R](f: (T) => R)(args: T) = f(args)

. Cómo hacer una clase abstracta Tuple sería trivial, y la lista de unificación tupla / parámetro no es una idea descabellada.

La razón por la que no se puede hacer eso en la mayoría de lenguajes de tipos estáticos es que casi todas optar por tener un tipo de lista que se limita a las listas uniformes. con tipo raqueta es un ejemplo de un lenguaje que se puede hablar de listas que no son uniformemente escrito (por ejemplo, tiene una Listof para las listas uniformes, y List para una lista con una longitud estáticamente conocido que puede ser no uniforme) - pero todavía se asigna un tipo limitado (con listas uniforme) para apply de la raqueta, ya que el verdadero tipo es extremadamente difícil de codificar.

Es trivial en 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

Aceptar, sin tipo:

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

Tal vez mezclada `funcall` y `apply`, así:

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

Es posible apply escribir en un lenguaje estáticamente con tipo, siempre y cuando las funciones se escriben de una manera particular. En la mayoría de los idiomas, funciones tienen parámetros individuales terminados ya sea por un rechazo (es decir, no invocación variadic), o una mecanografiada aceptan (es decir variadic invocación posible, pero sólo cuando todos los parámetros adicionales son de tipo T). He aquí cómo usted puede modelar esto en 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]]

Tenga en cuenta que esto no hace cumplir de buena formación (aunque sí existen límites tipo para eso, creo), pero se entiende la idea. A continuación, han apply define así:

apply[T, U]: (TypeList[T], (T => U)) => U

Sus funciones y, a continuación, se define en términos de la lista de cosas del tipo:

def f (x: Int, y: Int): Int = x + y

se convierte en:

def f (t: TypeList[Cons[Int, Cons[Int, Reject]]]): Int = t.head + t.tail.head

y funciones variadic como esta:

def sum (xs: Int*): Int = xs.foldLeft(0)(_ + _)

convertido en esto:

def sum (t: TypeList[Accept[Int]]): Int = t.xs.foldLeft(0)(_ + _)

El único problema con todo esto es que en Scala (y en la mayoría de otras lenguas estáticas), los tipos no son de primera clase suficiente para definir los isomorfismos entre cualquier estructura de estilo y los contras de una tupla de longitud fija. Debido a que la mayoría de los lenguajes estáticos no representan funciones en términos de tipos recursivos, usted no tiene la flexibilidad para hacer cosas como esta de forma transparente. (Macros cambiaría esto, por supuesto, así como fomentar una representación razonable de los tipos de función en el primer lugar. Sin embargo, utilizando el rendimiento apply impacta negativamente por razones obvias.)

En Haskell, no hay ningún tipo de datos para las listas de múltiples tipos, aunque creo que se puede hackear algo como esto, junto con el misterioso clase de tipos Typeable. Tal como lo veo, lo que buscas es una función que toma una función, una que contiene exactamente la misma cantidad de valores según sea necesario por la función y devuelve el resultado.

Para mí, esto se ve muy familiares para Haskell uncurryfunction, sólo que toma una tupla en lugar de una lista. La diferencia es que una tupla tiene siempre el mismo número de elementos (por lo (1,2) y (1,2,3) son de diferentes tipos (!)) Y el contenido no puede ser escrita a máquina arbitraria.

La función uncurry tiene esta definición:

uncurry :: (a -> b -> c) -> (a,b) -> c
uncurry f (a,b) = f a b

Lo que necesita es algún tipo de uncurry que está sobrecargado en una forma de proporcionar un número arbitrario de params. Pienso en algo como esto:

{-# 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

Pero esto sólo funciona si todos los tipos involucrados son conocidos por el compilador. Por desgracia, la adición de un Fundep hace que el compilador recopilación de basura. Ya que no soy un gurú Haskell, tal vez domeone más sabe, Cómo corregir esto. Lamentablemente, no sé cómo archieve esto más fácil.

REANUDARÁN: apply no es muy fácil en Haskell, aunque posible. Supongo, nunca lo necesitará.

Editar Tengo una idea mejor ahora, dame diez minutos y te presentar algo whithout estos problemas.

tratar pliegues. probablemente son similares a lo que usted quiere. acaba de escribir un caso especial de la misma.

Haskell: foldr1 (+) [0..3] => 6

incidentalmente, foldr1 es funcionalmente equivalente a foldr con el acumulador inicializado como el elemento de la lista.

hay todo tipo de pliegues. todos ellos técnicamente hacen lo mismo, aunque de manera diferente, y podrían hacer sus argumentos en diferentes órdenes. foldr es sólo uno de los más simples.

esta página , leí que "Aplicar es como funcall, excepto que su argumento final debe ser una lista;. los elementos de esa lista son tratados como si fueran argumentos adicionales a un funcall"

En Scala, funciones puede tener por varargs (argumentos variadic), al igual que las nuevas versiones de Java. Puede convertir una lista (o cualquier objeto Iterable) en más parámetros vararg usando el Ejemplo notación :_*:

//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)

De hecho, incluso Java puede hacer esto. Java varargs se puede pasar ya sea como una secuencia de argumentos o como una matriz. Todo lo que tendría que hacer es convertir su List Java para una matriz para hacer lo mismo.

El beneficio de un lenguaje estático es que impediría que para aplicar una función a los argumentos de los tipos incorrectos, por lo que creo que es natural que sería más difícil de hacer.

Dada una lista de argumentos y una función, en Scala, una tupla sería mejor captura de los datos, ya que puede almacenar valores de diferentes tipos. Con esto en mente tupled tiene cierto parecido con 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

En función de un argumento, en realidad hay apply:

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

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

Creo que si se piensa que se aplican como el mecanismo para aplicar una función de primera clase a sus argumentos, a continuación, el concepto es allí en Scala. Pero sospecho que apply en Lisp es más potente.

En Haskell, para hacerlo de forma dinámica, ver Data.Dynamic, y dynApp en particular: http://www.haskell.org/ghc/docs/6.12.1/html/libraries/base/Data-Dynamic.html

Ver suyo dinámico para Haskell, en C, los punteros de función void se puede lanzar a otros tipos, pero que tendría que especificar el tipo de echarlo a. (Creo, no lo han hecho los punteros de función en un tiempo)

Una lista en Haskell sólo puede almacenar valores de un tipo, por lo que no se podía hacer cosas divertidas como (apply substring ["Foo",2,3]). Tampoco Haskell tiene funciones variadic, por lo (+) tan sólo puede tomar dos argumentos.

Hay una función en Haskell $:

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

Pero eso es sólo muy útil, ya que tiene muy baja prioridad, o como pasa alrededor Höfs.

Me imagino que podría ser capaz de hacer algo como esto utilizando tipos de tupla y FUNDEPS sin embargo?

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

supongo que es una especie de 'uncurryN', ¿verdad?

Editar : esto no tiene realmente compilar; @ sustituida por la respuesta de FUZxxl.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow

No se puede crear con el lenguaje aplicar la función estática?

Aceptar, sin tipo:

Tal vez mezclada funcall y apply, así:

Tal vez mezclada `funcall` y `apply`, así: