non possono creare applicano funzione con linguaggio statico?

https://stackoverflow.com/questions/3693447

02-10-2019
|

Domanda

Ho letto che con un linguaggio a tipizzazione statica come Scala o Haskell non v'è alcun modo per creare o fornire una funzione apply Lisp:

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

o forse

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

Si tratta di una verità?

Soluzione

Un APPLICARE completo è difficile in un linguaggio statico.

In Lisp APPLICARE applica una funzione a un elenco di argomenti. Sia la funzione e la lista di argomenti sono argomenti da applicare.

Applica possibile utilizzare qualsiasi funzione. Ciò significa che questo potrebbe essere qualsiasi tipo di risultato e qualsiasi tipo di argomento.
APPLICARE prende argomenti arbitrari di lunghezza arbitraria (in Common Lisp lunghezza è limitata da un valore specifico costante attuazione) con tipi arbitrari e possibilmente differenti.
Applica restituisce alcun tipo di valore che viene restituito dalla funzione è arrivato come un argomento.

Come sarebbe un tipo di controllo che, senza sovvertire un sistema di tipo statico?

Esempi:

(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

Esempio Interazione:

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

Ora un esempio con la funzione REMOVE. Stiamo per rimuovere il carattere di una da un elenco di cose diverse.

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

Si noti che è anche possibile applicare applicare per sé, in quanto si applicano è una funzione.

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

C'è anche una piccola complicazione perché la funzione APPLICAZIONE prende un numero arbitrario di argomenti, dove solo gli ultimi esigenze argomento una lista:

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

Come affrontare questo?

allentare le norme controllo di tipo statico
limitare APPLICARE

Una o entrambe sopra dovrà essere fatto in un tipico tipo statico controllati linguaggio di programmazione. Né vi darà una completamente statico controllato e completamente flessibile APPLICABILE.

Altri suggerimenti

E 'perfettamente possibile in un linguaggio a tipizzazione statica. L'intero java.lang.reflect thingy è di fare questo. Naturalmente, utilizzando la riflessione ti dà tanto la sicurezza di tipo come si deve con Lisp. D'altra parte, mentre non so se ci sono lingue staticamente tipizzati che supportano tale caratteristica, mi sembra che si poteva fare.

Mi permetta di mostrare come immagino Scala potrebbe essere esteso per sostenerlo. In primo luogo, vediamo un esempio più semplice:

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

Questo è vero codice Scala, e funziona, ma non funziona per qualsiasi funzione che riceve tipi arbitrari. Per prima cosa, il T* notazione restituirà un Seq[T], che è una sequenza homegenously digitato. Tuttavia, vi sono sequenze eterogeneo tipizzato come il HList .

Quindi, prima, cerchiamo di uso HList qui:

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

che è ancora alla Scala di lavoro, ma abbiamo messo una grande limitazione f dicendo che deve ricevere un HList, invece di un numero arbitrario di parametri. Diciamo che usiamo @ di effettuare la conversione da parametri eterogenei a HList, allo stesso modo in * convertiti parametri omogenei a Seq:

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

Non stiamo parlando di vita reale Scala più, ma un ipotetico miglioramento ad esso. Questo sembra ragionevolmente a me, se che T si suppone che sia un tipo dalla notazione parametro type. Potremmo, forse, solo estenderlo allo stesso modo:

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

A me, sembra che potrebbe funzionare, che comunque potrebbe essere ingenuità da parte mia.

Prendiamo in considerazione una soluzione alternativa, una seconda unificazione delle liste parametri e tuple. Diciamo che Scala aveva finalmente unificato lista dei parametri e tuple, e che tutte le tuple erano sottoclasse di una classe Tuple astratta. Poi potremmo scrivere questo:

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

. Fare una classe astratta Tuple sarebbe banale, e la lista tupla / parametro unificazione non è un'idea campata in aria.

Il motivo non è possibile farlo nella maggior parte delle lingue staticamente tipizzati è che quasi tutti scegliere di avere un tipo di elenco che è limitato alle liste uniformi. tipizzati Racket è un esempio di un linguaggio che si può parlare di liste che non siano uniformemente digitato (per esempio, ha un Listof per le liste uniformi, e List per una lista con una lunghezza noto staticamente che può essere non uniforme) - ma comunque assegna un tipo limitato (con le liste uniformi) per apply di racchetta, dal momento che il vero tipo è estremamente difficile da codificare.

E 'banale 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, senza 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

Forse ho confuso `funcall` e `apply`, così:

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

E 'possibile apply scrivere in un linguaggio staticamente tipizzato, a patto che le funzioni vengono digitati un modo particolare. Nella maggior parte delle lingue, funzioni hanno parametri individuali terminati mediante un rifiuto (cioè senza invocazione variadic), o un digitato accettare (invocazione cioè variadic possibile, ma solo quando tutte le ulteriori parametri sono di tipo T). Ecco come si potrebbe modellare questo a 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]]

Si noti che questo non impone ben formati (anche se di tipo limiti esistono per questo, credo), ma si ottiene l'idea. Allora avete apply definito in questo modo:

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

Le funzioni, poi, sono definiti in termini di lista cose tipo:

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

diventa:

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

e funzioni variadic come questo:

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

diventa questo:

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

L'unico problema di tutto questo è che in Scala (e nella maggior parte delle altre lingue statiche), i tipi non sono di prima classe sufficiente per definire i isomorfismi tra qualsiasi struttura contro-stile e una tupla di lunghezza fissa. Poiché la maggior parte linguaggi statici non rappresentano funzioni in termini di tipi ricorsivi, non avete la possibilità di fare cose come questa in modo trasparente. (Macro cambierebbe questo, naturalmente, nonché favorire una ragionevole rappresentazione di tipi di funzioni in primo luogo. Tuttavia, utilizzando prestazioni apply influisce negativamente per ovvie ragioni.)

In Haskell, non v'è alcun tipo di dati per il multi-tipi di liste, anche se credo, che si può incidere qualcosa di simile insieme whith il misterioso Typeable typeclass. Per come la vedo, siete alla ricerca di una funzione, che prende una funzione, una che contiene esattamente la stessa quantità di valori in base alle esigenze della funzione e restituisce il risultato.

Per quanto mi riguarda, questo sembra molto familiare a haskells uncurryfunction, solo che ci vuole una tupla invece di una lista. La differenza è che una tupla ha sempre lo stesso numero di elementi (così (1,2) e (1,2,3) sono di tipo diverso (!)) E il contenuto non ci può essere digitato arbitrario.

La funzione uncurry ha questa definizione:

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

Quello che vi serve è una sorta di uncurry che viene sovraccaricato in modo da fornire un numero arbitrario di params. Penso a qualcosa di simile:

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

Ma questo funziona solo, se tutti i tipi coinvolti sono noti per il compilatore. Purtroppo, l'aggiunta di un fundep fa sì che il compilatore alla compilazione rifiuti. Come io non sono un guru Haskell, forse domeone altro conosce, howto risolvere questo problema. Purtroppo, non so come archieve questo più facile.

Résumee: apply non è molto facile in Haskell, anche se possibile. Credo che, non avrai mai bisogno.

Modifica Ho un'idea migliore ora, dammi minuti dieci e ti presentare qualcosa whithout questi problemi.

provare pieghe. sono probabilmente simile a quello che si vuole. basta scrivere un caso speciale di esso.

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

Per inciso, foldr1 è funzionalmente equivalente a foldr con l'accumulatore inizializzato come elemento della lista.

ci sono tutti i tipi di pieghe. tutti tecnicamente fanno la stessa cosa, anche se in modi diversi, e potrebbero fare i loro argomenti in ordine diverso. foldr è solo uno di quelli più semplici.

questa pagina , ho letto che "Applicare è proprio come funcall, se non che il suo argomento finale dovrebbe essere una lista;. gli elementi della lista che sono trattati come se fossero ulteriori argomenti a una funcall"

In Scala, funzioni può avere varargs (argomenti variadic), come le versioni più recenti di Java. È possibile convertire un elenco (o qualsiasi altro oggetto Iterable) in più parametri vararg utilizzando l'esempio di notazione :_*:

//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 effetti, anche Java può fare questo. Java varargs può essere passato sia come una sequenza di argomenti o come un array. Tutto quello che avrebbe dovuto fare è convertire il vostro List Java ad un array di fare la stessa cosa.

Il vantaggio di un linguaggio statico è che impedirebbe di applicare una funzione agli argomenti di tipo non corretti, quindi penso che sia naturale che sarebbe stato più difficile da fare.

Dato un elenco di argomenti e una funzione, a Scala, una tupla sarebbe migliore acquisizione dei dati da esso può memorizzare i valori di tipo diverso. Con questo in mente tupled ha qualche somiglianza 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

Per funzione di un argomento, v'è in realtà apply:

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

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

Credo che se si pensa che si applicano come il meccanismo per applicare una funzione di prima classe ai suoi argomenti, allora il concetto è lì a Scala. Ma ho il sospetto che apply in Lisp è più potente.

Per Haskell, per farlo in modo dinamico, vedere Data.Dynamic, e dynApp in particolare: http://www.haskell.org/ghc/docs/6.12.1/html/libraries/base/Data-Dynamic.html

Vedere la sua cosa dinamica per Haskell, in C, puntatori a funzione vuoto può essere fusa ad altri tipi, ma che avrebbe dovuto specificare il tipo di gettare a. (Penso, non hanno fatto puntatori a funzione in un po ')

Un elenco in Haskell può memorizzare solo valori di un tipo, quindi non si poteva fare cose divertenti come (apply substring ["Foo",2,3]). Né Haskell hanno funzioni variadic, in modo da (+) può sempre e solo prendere due argomenti.

C'è una funzione di $ in Haskell:

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

Ma questo è realmente utile solo perché ha la precedenza molto bassa, o come passando intorno Hofs.

immagino si potrebbe essere in grado di fare qualcosa di simile utilizzando i tipi tuple e fundeps però?

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

credo che sia una sorta di 'uncurryN', non è vero?

Modifica : questo in realtà non compilare; sostituita da @ risposta di FUZxxl.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow

non possono creare applicano funzione con linguaggio statico?

OK, senza tipo:

Forse ho confuso funcall e apply, così:

Forse ho confuso `funcall` e `apply`, così: