Невозможно создать функцию apply на статическом языке?

StackOverflow https://stackoverflow.com/questions/3693447

Вопрос

Я читал, что с помощью статически типизированного языка, такого как Scala или Haskell, невозможно создать или предоставить Lisp. apply функция:

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

или, может быть

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

Это правда?

Это было полезно?

Решение

Полное применение сложно на статическом языке.

При применении Lisp применяется функция в список аргументов. Как функция, и список аргументов являются аргументами для применения.

  • Применить может использовать любую функцию. Это означает, что это может быть любой тип результата и любые типы аргументов.

  • Применение принимает произвольные аргументы в произвольной длине (в общем Lisp длина ограничивается удельным постоянным значением осуществления) с произвольными и, возможно, различными типами.

  • Применить Возвращает любой тип значения, возвращаемого функцией, он получил в качестве аргумента.

Как один тип проверьте, что без подрыва системы статического типа?

Примеры:

(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

Пример взаимодействия:

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

Теперь пример с функцией удалить. Мы собираемся удалить персонажа A из списка разных вещей.

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

Обратите внимание, что вы также можете применить применить себе, поскольку Apply - это функция.

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

Существует также небольшое осложнение, потому что применяются функция, принимают произвольное количество аргументов, где только последний аргумент должен быть список:

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

Как справляться с этим?

  • Ослабьте правила проверки статического типа

  • Ограничить применение

Один или оба выше, должны быть сделаны в типичном языке программирования программирования. Ни один из них не даст вам полностью статически проверяемое и полностью гибкое применение.

Другие советы

Это вполне возможно на статически типизированном языке.Целый java.lang.reflect дело в том, чтобы сделать это.Конечно, использование отражения дает вам такую ​​же безопасность типов, как и в Лиспе.С другой стороны, хотя я не знаю, существуют ли статически типизированные языки, поддерживающие такую ​​возможность, мне кажется, что это можно сделать.

Позвольте мне показать, как, по моему мнению, Scala может быть расширена для ее поддержки.Сначала давайте посмотрим на более простой пример:

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

Это настоящий код Scala, и он работает, но он не будет работать ни для одной функции, принимающей произвольные типы.Во-первых, обозначение T* вернет Seq[T], который представляет собой гомогенно типизированную последовательность.Однако существуют гетерогенно типированные последовательности, такие как HList.

Итак, сначала попробуем использовать HList здесь:

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

Scala все еще работает, но мы наложили большое ограничение на f говоря, что он должен получить HList, вместо произвольного количества параметров.Допустим, мы используем @ осуществить преобразование разнородных параметров в HList, так же * преобразует однородные параметры в Seq:

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

Мы больше не говорим о реальной Scala, а говорим о ее гипотетическом улучшении.Мне это кажется разумным, за исключением того, что T предполагается, что это один тип согласно обозначению параметра типа.Возможно, мы могли бы просто расширить его таким же образом:

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

Мне кажется, это может сработать, хотя, возможно, это и наивность с моей стороны.

Давайте рассмотрим альтернативное решение, основанное на унификации списков параметров и кортежей.Допустим, в Scala наконец-то унифицирован список параметров и кортежи, и что все кортежи являются подклассами абстрактного класса. Tuple.Тогда мы могли бы написать это:

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

Там.Создание абстрактного класса Tuple было бы тривиально, и унификация списка кортежей/параметров не является надуманной идеей.

Причина, по которой вы не можете сделать это в большинстве статически напечатанных языках, заключается в том, что они почти все выбирают, чтобы иметь тип списка, который ограничен едиными списками. Типизированная ракетка является примером для языка, который может говорить о списках, которые не набираются равномерно (например, он имеет Listof Для единых списков и List Для списка с статически известной длиной, которая может быть неравной) - но все же он присваивает ограниченный тип (с едиными списками) для ракетки apply, поскольку реальный тип чрезвычайно трудно кодировать.

Это тривиально в 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 и apply, так:

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 На статически наведенном языке, до тех пор, пока функции набираются определенный путь. На большинстве языков функции имеют отдельные параметры, прекращенные либо подавлением (т. Е. Вариадиадийный вызов), либо набравшееся принять (т. Е. возможную возможную вариадию, но только тогда, когда все дальнейшие параметры имеют тип T). Вот как вы можете моделировать это в 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]]

Обратите внимание, что это не обеспечивает укрепление хорошо сформированной (хотя к тому, что границы типа существуют, я полагаю), но вы получаете идею. Тогда у вас есть apply Определяется так:

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

Затем ваши функции определяются с точки зрения списка типов.

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

становится:

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

И вариадические функции, такие как это:

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

стать этим:

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

Единственная проблема со всем этим заключается в том, что в Scala (и в большинстве других статических языков) типы недостаточно первого класса, чтобы определить изоморфизмы между любой структурой в стиле в минусе и кортежным корпусом. Поскольку большинство статических языков не представляют функции с точки зрения рекурсивных типов, у вас нет гибкости делать такие вещи, как это прозрачно. (Макрос изменит это, конечно, а также поощряет разумное представление типов функций в первую очередь. Однако, используя apply отрицательно влияет на производительность по очевидным причинам.)

В Haskell нет данных о данных для многоподъемных списков, хотя я считаю, что вы можете взломать что-то вроде этого вместе с таинственным Typeable Типекласс. Как я вижу, вы ищете функцию, которая принимает функцию, которая содержит точно такое же количество значений по мере необходимости функции и возвращает результат.

Для меня это выглядит очень знакомым для хэшкеллс uncurryФункция, просто то, что она принимает кортеж вместо списка. Разница в том, что кортеж всегда имеет одинаковое количество элементов (так (1,2) и (1,2,3) имеют разные типы (!)), и там содержимое может быть произвольным.

То uncurry Функция имеет это определение:

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

То, что вам нужно, это какой-то неопытный, который перегружен таким образом, чтобы обеспечить произвольное количество параметров. Я думаю о чем-то вроде этого:

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

Но это только работает, если бы все типы были известны компилятору. К сожалению, добавление фундамента приводит к тому, что компилятор отказывается от компиляции. Как я не хаскоэлл Гуру, может быть, Domeone еще знает, как это исправить. К сожалению, я не знаю, как проще преследовать.

Résumee: apply Не очень легко в Haskell, хотя возможно. Я думаю, вам никогда не понадобится.

Редактировать Теперь у меня есть лучшая идея, дайте мне десять минут, и я представляю вам что-то Whithout этих проблем.

попробуйте складки. Они, вероятно, похожи на то, что вы хотите. Просто напишите специальный случай.

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

Кстати, foldr1 функционально эквивалентен foldr С аккумулятором инициализированным как элемент списка.

Есть все виды складок. Все они технически делают одно и то же, хотя и по-разному, и могут сделать свои аргументы в разных заказах. foldr это только один из проще.

На эта страница, Я читал, что «Применить как Funcall, за исключением того, что его окончательный аргумент должен быть список; элементы этого списка обрабатываются так, как если бы они были дополнительными аргументами на Funcall».

В Scala функции могут иметь варярг (Вариадические аргументы), такие как новые версии Java. Вы можете преобразовать список (или любой намек) в больше параметров Vararg, используя обозначения :_* Пример:

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

На самом деле даже Java может сделать это. Java Varargs можно передавать как последовательность аргументов, либо как массив. Все, что вам нужно сделать, это конвертировать вашу Java List на массив, чтобы сделать то же самое.

Преимущество статического языка заключается в том, что он помешает вам применить функцию к аргументам неправильных типов, поэтому я думаю, что это естественно, что было бы сложнее сделать.

Учитывая список аргументов и функции в Scala, кортеж лучше всего захватить данные, поскольку он может хранить значения различных типов. С этим в мыслях tupled имеет некоторое сходство с 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

Для функции одного аргумента на самом деле есть apply:

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

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

Я думаю, что если вы считаете применением в качестве механизма для применения функции первого класса к его аргументам, то концепция в Scala. Но я подозреваю, что apply В Лисске более мощнее.

Для Haskell, чтобы сделать это динамически, см. Data.dynamic, и Dynapp в частности: http://www.haskell.org/ghc/docs/6.12.1/html/librariare/base/data-dynamic.html.

См. Его динамическую вещь для Haskell, в C, указатели функции пустоты могут быть выбраны на другие типы, но вам придется указать тип, чтобы отбрасывать его. (Я думаю, не сделал указателей по функциям через некоторое время)

Список в Haskell может хранить только значения одного типа, чтобы вы не могли сделать забавные вещи, как (apply substring ["Foo",2,3]). Отказ Не у вас нет вариадиадических функций, так (+) можно только принимать два аргумента.

В Haskell есть функция $:

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

Но это действительно полезно, потому что он имеет очень низкий приоритет, или, как проходит вокруг Hofs.

Я представляю, что вы сможете сделать что-то вроде этого, используя Tuple Types и Fundeps, хотя?

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

Я думаю, это своего рода «бесшуррин», не так ли?

Редактировать: это на самом деле не скомпилируется; заменил ответ @ fuzxxl.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top