?

Log in

Почему LISP? - Жить не можем без проблем! [entries|archive|friends|userinfo]
Жить не можем без проблем!

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Почему LISP? [Jan. 13th, 2011|02:05 pm]
Жить не можем без проблем!

ru_lisp

[aralex]

Как говорил Ворошилов, вопрос к Знатокам (к знатокам LISP-а в данном случае)! Почему таки LISP? Или, если конкретнее, вопроса три:

  1. Для каких именно задач LISP подходит больше, чем другие языки?
  2. За счёт чего для них он подходит больше?
  3. В чём именно выражается его преимущество?

Если не в лом, приведите, pls, коротенькие иллюстрации на LISP-е (или ссылочку на них). Заранее благодарен!

Исходно данный пост был размещён в сообществе ru_programming, но там Знатоков, способных ответить внятно и по сути, увы, не нашлось :(

linkReply

Comments:
From: (Anonymous)
2011-01-18 09:23 am (UTC)
> В императивном языке нет не только другой гарантии, но и такой тоже нет.

Есть. Если в спеках написано, что функция не совершает побочных эффектов - то это и есть пример подобной гарантии.

> Ох, ну я же говорил, подумайте лучше. Порядок вычисления f и g не совпадает - в этом суть примера.
map f . map g -> gggfff
map (f . g) -> gfgfgf

А, я неверно понял пример.
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-18 09:57 am (UTC)
"Если в спеках написано, что функция не совершает побочных эффектов - то это и есть пример подобной гарантии."

Как написать такой map, в который применяется к функциям в спеках которой написано, что она не совершает побочных эффектов, а к функциям, в спеках которых этого не написано - не применяется? Вот видите, значит это гарантии совсем не одного качества. Я же вроде бы подробно объяснил, что чистую функцию написать в императивном языке можно, но смысла в этом нет никакого, потому что использовать это на практике нельзя. В декларативном языке пользоваться чистотой можно. В этом и разница.
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-18 02:54 pm (UTC)
> Как написать такой map, в который применяется к функциям в спеках которой написано, что она не совершает побочных эффектов, а к функциям, в спеках которых этого не написано - не применяется?

Не надо подменять понятия. Мы говорим о гарантиях чистоты map, а не о гарантиях чистоты ф-й, к которым применяется map. И эта гарантия одинакова - что в хаскеле, что в лисп. Просто в спеке написано "мап чистый". Кстати, на счет независимости от пути редукции.
map f x, где х имеет тип List (IO ...) - результат может быть любым.
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2011-01-18 08:57 pm (UTC)
>И эта гарантия одинакова - что в хаскеле, что в лисп.

Да ничего подобного.

f :: (Int -> Int) -> [Int] -> [Int]
f g = map g

f (+1) -- всё Ok.
f (\x -> do { putStrLn "пуск ракет!"; return (x+1) }) -- ошибка проверки типов.

В лиспе второе на раз.

Та чушь, что вы несёте, она совсем не прекрасна, стихов недостойна.
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-19 04:17 am (UTC)
> Да ничего подобного.

Ну что же вы за бред снова несете? Я для особо одаренных повторю второй раз - речь о конкретно функциях map и . (ну или вообще о других базовых функциях), не чистоте тех ф-й, что вызывает map или чистоте каких-то других определенных через map вами лично. Указано у вас, что map - чистый, и эта чистота лежит на совести исключительно разработчиков компилятора. Разработчик говорит "все чисто" - и мы верим. Других гарантий не предоставляется. Кстати, а порядок вычисления map регламентируется? То есть тот факт, что сперва вычисляется первый элемент списка, потом второй, потом третий - но не вперемешку? Ну или если у нас рекурсивная реализация и там стоит map f (x:xs) = [f x] ++ (map f xs) - кто гарантирует, что сайдэффекты f будут вычислены до вызова map f xs?
(Reply) (Parent) (Thread)
From: ext_55374
2011-01-19 05:21 am (UTC)
> кто гарантирует, что сайдэффекты f будут вычислены до вызова map f xs?

У f нет сайдэффектов, по построению.
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-20 03:39 am (UTC)
> У f нет сайдэффектов, по построению.

Если ИО возвращает - есть. Вот мой вопрос и состоит в том - кто гарантирует, что сперва будет выполнено ИО первого аргумента ++? Как происходит вычисление ИО?
(Reply) (Parent) (Thread)
From: ext_55374
2011-01-20 04:56 pm (UTC)
Так ведь эффекты происходят не в момент вычисления map-а, а когда «попадают» в (>>):

Prelude> let xs = map (\t -> putStr "bang " >> print t) [11..13]
Prelude> xs

:1:0:
No instance for (Show (IO ()))
arising from a use of `print' at :1:0-1
Possible fix: add an instance declaration for (Show (IO ()))
In a stmt of a 'do' expression: print it
Prelude> :t xs
xs :: [IO ()]
Prelude> xs !! 1
bang 12
Prelude> foldl1 (>>) xs
bang 11
bang 12
bang 13
Prelude> foldl1 (>>) $ reverse xs
bang 13
bang 12
bang 11
Prelude>
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-21 02:22 am (UTC)
> Так ведь эффекты происходят не в момент вычисления map-а, а когда «попадают» в (>>):

Нет, >> не форсирует вычисление ИО (по крайней мере семантически, как оно там происходит в кишках компилятора - не важно) и не может этого делать, потому что иначе он должен уметь вычислять сперва первый аргумент, а потом второй - то есть быть энергичным. >> из двух вычислений конструирует третье вычисление, в котором второе следует за первым, но исполнение этих вычислений он не форсирует. И вообще программа на хаскеле не делает ничего - она возвращает монаду IO из main и сама не производит никаких вычислений, причем результат main этот мы всегда знаем на этапе компиляции то есть в рантайме программа на хаскеле ничего не делает, она еще при компиляции отработала. То есть то, что происходит в рантайме - лежит в ИО, и вот вопрос - как выполняется это ИО? Где семантика его исполнения?
вот
f x = getLine
map f [1..5]
понятно что мы считаем пять строк, но в каком порядке они будут лежать в списке? И почему в таком, а не в каком-то другом?
(Reply) (Parent) (Thread)
From: ext_55374
2011-01-21 02:56 am (UTC)
> Нет, >> не форсирует вычисление ИО (по крайней мере семантически, как оно там происходит в кишках компилятора - не важно) и не может этого делать, потому что иначе он должен уметь вычислять сперва первый аргумент, а потом второй - то есть быть энергичным.

«Да, я такой!» ©

Открываем libraries/base/GHC/IOBase.lhs, читаем:

{-|
A value of type @'IO' a@ is a computation which, when performed,
does some I\/O before returning a value of type @a@.  

There is really only one way to \"perform\" an I\/O action: bind it to
@Main.main@ in your program.  When your program is run, the I\/O will
be performed.  It isn't possible to perform I\/O from an arbitrary
function, unless that function is itself in the 'IO' monad and called
at some point, directly or indirectly, from @Main.main@.

'IO' is a monad, so 'IO' actions can be combined using either the do-notation
or the '>>' and '>>=' operations from the 'Monad' class.
-}
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))

unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #))
unIO (IO a) = a

instance  Functor IO where
   fmap f x = x >>= (return . f)

instance  Monad IO  where
    {-# INLINE return #-}
    {-# INLINE (>>)   #-}
    {-# INLINE (>>=)  #-}
    m >> k      =  m >>= \ _ -> k
    return x    = returnIO x

    m >>= k     = bindIO m k
    fail s      = failIO s


bindIO :: IO a -> (a -> IO b) -> IO b
bindIO (IO m) k = IO ( \ s ->
  case m s of 
    (# new_s, a #) -> unIO (k a) new_s
  )


Короче, всякие хитрые штуки творятся :)

> f x = getLine
f :: t -> IO String
> map f [1..5]
map f [1..5] :: [IO String]
> понятно что мы считаем пять строк, но в каком порядке они будут лежать в списке? И почему в таком, а не в каком-то другом?

Тоесть, это не просто строки, а строки, завёрнутые в монаду. А в списке всё будет лежать согласно купленным билетам:

Prelude> let f x = do u <- getLine ; putStrLn ("Hello, " ++ u ++ ", your score is " ++ show x)
Prelude> :t f
f :: (Show a) => a -> IO ()
Prelude> let xs = map f [1..5]
Prelude> :t xs
xs :: [IO ()]
Prelude> let y = foldl1 (>>) xs
Prelude> :t y
y :: IO ()
Prelude> y
aaa
Hello, aaa, your score is 1
bbb
Hello, bbb, your score is 2
ccc
Hello, ccc, your score is 3
ddd
Hello, ddd, your score is 4
eee
Hello, eee, your score is 5
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-21 05:43 am (UTC)
There is really only one way to \"perform\" an I\/O action: bind it to
@Main.main@ in your program.  When your program is run, the I\/O will
be performed.  It isn't possible to perform I\/O from an arbitrary
function, unless that function is itself in the 'IO' monad and called
at some point, directly or indirectly, from @Main.main@.


Вот именно об этом я и говорил. То есть программа на хаскеле возвращает из main некоторую программу на неопределенном языке, которая содержится в ИО, причем эта программа вычисляется в компайлтайме и в рантайме программа на хаскеле не делает ничего, все что делается - это выполнение ИО-программы. То есть хаскель - это не более чем система метапрограммирования, которая предназначена для порождения энергичных программ ленивым образом. Монада ИО содержит в себе куски АСТа и ваша программа на хаскеле в компайлтайме раскрывается в АСТ энергичной программы, другими словами хаскель - подмножества лисповой макросистемы :)
Но, однако, возникает вопрос:
1. Кто выполняет потом ИО-программу?
2. Как вообще эта ИО-программа представляется?
3. Какова семантика ИО-программы?
Пока мы этого не описали - мы не можем гарантировать, что хаскель порождает корректные ИО-программы, а тогда вся система типов хаскеля становится не нужна, потому что она ничего не доказывает и ничего не гарантирует.
(Reply) (Parent) (Thread)
From: ext_55374
2011-01-21 02:59 am (UTC)
Ещё можно так:

Prelude> let f x = getLine 
Prelude> let y = map f [1..5]
Prelude> :t mapM
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
Prelude> :t id
id :: a -> a
Prelude> let z = mapM id y
Prelude> :t z
z :: IO [String]


Круто, теперь вместо «списка экшенов» y мы имеем «экшен списка» z!

Prelude> z
om
nom
NOM
NOMNOMNOM
NOWAI!!!
["om","nom","NOM","NOMNOMNOM","NOWAI!!!"]
(Reply) (Parent) (Thread)
From: ext_55374
2011-01-20 05:21 pm (UTC)
Ещё пример:

Prelude> let xs = map (\t -> (readFile ("/tmp/" ++ t)) >>= print) ["a", "b", "c"]
Prelude> :t xs
xs :: [IO ()]

Идём в shell:
>echo 1 > /tmp/a ; echo 2 > /tmp/b ; echo 3 > /tmp/c

Назад в ghci:
Prelude> foldl1 (>>) $ reverse xs
"3\n"
"2\n"
"1\n"

Опять в shell:
>echo 11 > /tmp/a ; echo 22 > /tmp/b ; echo 33 > /tmp/c

Опять в ghci:
Prelude> foldl1 (>>) $ reverse xs
"33\n"
"22\n"
"11\n"
(Reply) (Parent) (Thread)
From: ext_55374
2011-01-20 05:22 pm (UTC)
То же самое будет, если let ys = foldl1 (>>) $ reverse xs и дёргать этот самый ys :: IO () вместо всего выражения.
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2011-01-19 07:57 am (UTC)
>Ну или если у нас рекурсивная реализация и там стоит map f (x:xs) = [f x] ++ (map f xs) - кто гарантирует, что сайдэффекты f будут вычислены до вызова map f xs?

В Хаскеле - система типов.

Прочитайте уже какое-нибудь руководство.
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-20 03:47 am (UTC)
При чем тут типы? С типами все просто и понятно, я спрашивал вас про модель вычисления ИО, а не про типы. Как вычисляется ИО после того, как мы вернули его из main?
(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-19 07:52 am (UTC)
"Не надо подменять понятия."

Ну и не подменяйте.

"Мы говорим о гарантиях чистоты map, а не о гарантиях чистоты ф-й, к которым применяется map"

Ну так map не чище функций к котором применяется. Поэтому о чистоте map имеет смысл говорить только в том случае, когда есть гарантия того, что применяется map только к чистой функции.

"И эта гарантия одинакова - что в хаскеле, что в лисп."

Ну повторите еще раз десять, думаете я что-то новое отвечу по сравнению с тем, что я уже на это ответил выше?

"map f x, где х имеет тип List (IO ...) - результат может быть любым."

Давайте вы не будете фантазировать, а прочтете что-нибудь про IO и попробуете сами, для этого даже хаскель устанавливать не нужно - можно в каком-нибудь codepad поэкспериментировать.
(Reply) (Parent) (Thread)