> Мы читаем одинаковые формулировки и трактуем его совершенно по разному.

Это вы о чем? Формулировки чего читаем? Кого трактуем?

В математике от подобного защищает формализм

От чего защищает?

предметом рассуждений являются абстракции, а не действительность.

Так это же замечательно.

хм... молодец, анонимус

>> Кстати, насчет существования независимо от людей.

У неандертальцев была математика?

муравьи, например, вполне умеют считать до пяти. man «муравьиные алгоритмы». А неандертальцы были попродвинутее хомо сапиенсов, которые их тупо сожрали (выжили не самые умные, а самые агрессивные).

и если лисперы могут называть свои S-выражения алгебраическими типами данных, то почему же мы не можем называть алгебраические типы данных S-выражениями?

А в GHC есть Template Haskell, который идеологически близок к лисповским макросам, с той только разницей, что они стоят по разные стороны относительно катаморфизма: лисп как списки, хаскель как алгебраические типы с соответствующей типизацией.

Это какое-то непонимание вызванное неправильной интерпретацией чьих-то слов :) Просто ни один лиспер не называл s-выражения алгебраическими типами данных (по крайней мере всерьёз). А всё потому что связи никакой нет - АТД относятся к семантике, а s-выражения относятся к синтаксису.

Вот на примере GHC - схема стадий компиляции. Где тут место s-выражениям (если бы они были)? Это в HsSyn, после операции Parse - если бы в Haskell исходили из минимального скобочного синтаксиса и вместо большой структуры data HsExpr id (в ghc/compiler/HsSyn/HsExpr.lhs) взяли бы минимальную из возможных:

data FooExpr id
  = FooAtom id                        -- ^ atoms
  | FooCons (FooExpr id) (FooExpr id) -- ^ lists

с возможностью оперировать этими объектами наряду с другими примитивными типами (которые возникают как Literals позже в CoreSyn) то такой язык принадлежал бы семейству лисп(ов). При этом что было бы удобно - собственно минимальность и регулярность синтаксиса, что неудобно - меньшая читаемость (разный сахар) и отсутствие паттерн-матчинга по expressions (в CL вы в макросах смотрите на первое «слово» в списке чтобы понять что тут - определение функции, if, или let, а в TH вы сразу используете паттерн-матчинг по expressions; в plt-scheme/racket в этом отношении пошли по пути более близкому к haskell чем к CL).

Теперь где место АТД (определяемым пользователем) - дальше, ближе к CoreExpr, там где выполняются typechecking и desugaring.

Короче, это разные вещи которые никак не сочетаются - возможность работать с expression и вводить (формально) полные (параметрические) АТД.

Вот, кстати, в одной книжке про Haskell написано следующее:

The programming language that will be our tool for this is Haskell, a member of the Lisp family.

;) Это не правильно потому что

• В Haskell не следуют идеологии минимального синтаксиса и синтаксических объектов как обычных примитивных типов (атомы и списки, составляющие код, также данные соответствующих типов).
• Нет прямого доступа к типовому universe (T).
• Нет прямого доступа к квантификаторам над типами (or, and). это и предыдущее есть, конечно, в рамках системы F, но в виде отдельной системы (система типов)).
• И нет правил вывода для присваивания (потому что его нет :).

С другой стороны:

• Функциональные вещи одинаковы и там и там (это, наверно, имел в виду автор той цитаты).
• (Алгебраические вещи) всё что касается типов и введения АТД - тоже самое. Т.е. я хочу сказать, что способ мыслить о типах и данных в CL никак не отличается от способа мыслить о них в Haskell. По крайней мере в общем, что касается деталей - в Haskell, конечно, этим аспектам уделяют гораздо больше внимания (как и функциональщине).

а почему не (b -> c) -> (a -> b) -> (a -> c) ?

скорее всего это у них карринг головного мозга, видимо они отождествляют x -> y -> z и x -> (y -> z)

Скорее всего операция (->) правоассоциативна. (a -> b) -> c -> d то же что и (a -> b) -> (c -> d), т.е. приоритет самой правой операции ясен и без скобок.

>А всё потому что связи никакой нет - АТД относятся к семантике, а s-выражения относятся к синтаксису.

Вот мне всегда казалось что главная особенность лиспа - умение работать с AST, а S-выражения - всего лишь базис, синтаксис.

Я не думаю, что базис (урощенно) atom-list священен. И как только какой-то язык позволяет работать с AST, то подвиньтесь: в полку языков-делающих-то-же-самое-что-и-лисп прибыло. Хотя технически лиспами они не являются.

Какая разница на каком уровне компиляции возникает возможность работы с AST? Да, согласен, в лиспе это делается очень рано. Но, ИМХО, главное не «на каком уровне», а «когда». Да хоть на самой последней стадии, перед непосредственной генерацией кода, но ВО ВРЕМЯ КОМПИЛЯЦИИ.

Кроме того, свой вклад вносит динамическая природа лиспа. Но пожалуйста, в CL есть возможность проверять структуру объектов, получившихся в результате обработки S-выражений... А в таком случае мы имеем право говорить о структуре. А раз мы говорим о структуре, так мы можем говорить и о типах.

Далее, если S-выражение (на синтаксическом уровне), «разворачивается» в какой-то объект (на семантическом уровне), причем со структурой не обязательно соответствующей исходному S-выражению, то опять мы можем говорить о катаморфизме.

В не-лисп языках ситуация обратная: у нас есть объект (пофиг как полученный), так что нам мешает с помощью того же катаморфизма «свренуть» его в любое XYZ-выражение, с любым выбранным базисом?

А если это происходит во время компиляции? Тогда я не понимаю где техническая разница между лиспом и не-лиспом.

Что касается синтаксиса.

Вот мне всегда казалось что главная особенность лиспа - умение работать с AST, а S-выражения - всего лишь базис, синтаксис.

S-выражения это _минимальный_ возможный «базис» в котором можно представить синтаксические объекты любых других языков (определяемых любой грамматикой, например BNF). То есть s-выражениями можно кодировать любой синтаксический объект - языка си, языка хаскель и т.п., причём однозначно кодировать (и однозначно декодировать). А вот какой-нибудь не минимальный базис (с лишними правилами в BNF) может не подойти для однозначного изоморфизма с каким-либо другим языком. Это свойство минимальности приводит к свойству расширяемости - нужна не просто возможность работать с AST, но и возможность расширять целевой язык, т.е. добавлять новые продукции к его грамматике и сопоставлять им новые семантические атрибуты.

Я не думаю, что базис (урощенно) atom-list священен. И как только какой-то язык позволяет работать с AST, то подвиньтесь: в полку языков-делающих-то-же-самое-что-и-лисп прибыло. Хотя технически лиспами они не являются.

Ну хорошо, пусть мы ввели в качестве синтаксического Expression такую грамматику (она отражает минимальный лисп):

data Expr = Atom Atom
          | Cons Expr Expr

Что такое атом - вообще говоря, пока нет списков, свойство объекта быть атомом это свойство принадлежать типовому universe, что в лиспе атом - в другом языке вообще любой объект. И cons - пара элементов, причём элементы типа Expr (это РТД) или тот же атом. С помощью cons-пар можно кодировать списки, произвольные деревья и некоторого вида графы. Синтаксические деревья тоже кодируются такими cons-парами. Таким образом парсер (даже «читатель», т.к. он очень прост) это:

read :: String -> Expr

и имея

(lambda (x y) (+ x y))

мы интерпретируем (lambda ...) как лямбду не потому что это конструктор (LambdaExpr ...) а потому что это s-выражение с первым символом lambda (в памяти - (cons 'lambda (cosn ...))). Аналогично, (+ ...) аппликация функции + т.к. первый символ списка - '+.

А теперь возьмём любой контекствно-свободный язык, и будем отражать его BNF (или продукции):

data AnyExpr = Constr_1 ...
             | Constr_2 ...
             ...
             | Constr_n

почему он однозначно «влазит» в лисп? Потому что:

Constr_i ... => (cons 'Constr_i (cons ...)), i = 1 .. n

т.е. конструктор Foo соответсвует s-выражению (foo ...) (в памяти (cons 'foo (cons...))) с первым символом 'foo. И наоборот.

И теперь:

Какая разница на каком уровне компиляции возникает возможность работы с AST? Да, согласен, в лиспе это делается очень рано. Но, ИМХО, главное не «на каком уровне», а «когда». Да хоть на самой последней стадии, перед непосредственной генерацией кода, но ВО ВРЕМЯ КОМПИЛЯЦИИ.

Понятно что во время компиляции, но всё же главное «как». В лиспе у нас минимально возможный синтаксический «базис» -> к нему можно свести всё что угодно. В хаскеле у нас не минимальный «базис» -> к нему нельзя свести всё что угодно. Поясняю - мы классифицируем данный синтаксический объект по первому символу в s-выражении, количество символов счётно, следовательно у нас счётное количество синтаксических объектов. Скажем, мы можем ввести форму lambda2 и придать ей произвольное свойство (как форме времени компиляции - стратегия call by macro expansion, т.е. вообще форма с произвольным смыслом трансляции). В хаскеле мы не можем дополнить data HsExpr (compiler/HsSyn/HsExpr.lhs) этой новой формой lambda2, т.к. эта структура фиксирована. Иначе говоря, язык не расширяется до произвольного. Лисп расширяется до произвольного языка (то что там «на вид» - не важно, всё равно любой язык изоморфен своей скобочной форме), а хаскель - всегда хаскель. И это не хорошо и не плохо, в хаскеле можно следовать обычной практике - вводить DSL языки, разбирать их parsec-ом, можно вводить расширяемые DSL языки (тот же лисп, хотя не обязательно, я согласен с тем что «скобочки - значит лисп» и «лисп - значит скобочки» это два неверных утверждения). Но всё это не отменяет того факто что сам хаскель как язык фиксирован (фиксированный BNF у него, условно представляется в compiler/HsSyn/HsExpr.lhs, core language тоже фиксирован - compiler/coreSyn/coreSyn.hs). Лисп как язык не фиксирован, т.к. нет фиксированного множества (продукции + семантическии атрибуты), всегда может появиться новая продукция с новым семантическим аттрибутом.

Вот поэтому хаскель не лисп.

Теперь насчёт типов.

Кроме того, свой вклад вносит динамическая природа лиспа. Но пожалуйста, в CL есть возможность проверять структуру объектов, получившихся в результате обработки S-выражений... А в таком случае мы имеем право говорить о структуре. А раз мы говорим о структуре, так мы можем говорить и о типах.

Далее, если S-выражение (на синтаксическом уровне), «разворачивается» в какой-то объект (на семантическом уровне), причем со структурой не обязательно соответствующей исходному S-выражению, то опять мы можем говорить о катаморфизме.

Пусть я написал

(defstruct foo
  (a nil :type fixnum)
  (b nil :type fixnum))

или

data Foo
  = Foo { a :: Int
        , b :: Int }
  deriving ( Eq, Show )

функция

parse :: String -> Expr

прочла это в синтаксический объект - в первом случае в s-выражение с атомами, во втором - в подробный объект подробного АТД (с конструкторами DataDefinition и т.п.). И что дальше? В обоих случаях на этапе компиляции должны определиться несколько функций - функция конструктор (аллокация структуры в плоской памяти), аккессоры (доступ к полям структуры по смещению в плоской памяти), сравнения (fold функции and по результату map сравнения по всем полям), печати и т.п. В обоих случаях все эти функции определяются автоматически (в этом удобство абстракции введения АТД). Ещё можно на этапе компиляции делать type checking.

Foo 1 "2"

очевидно, не пройдёт его, а

(make-foo :a 1 :b "2")

пройдёт (имеется в виду тот слабый type inference что есть в некоторых реализациях CL) и вызовет рестарт в runtime. В данном случае это недостаток CL, т.к. динамики тут нет - типизация статическая, так что нужно выводить. Это в случае

(let ((a 5))
  ...)

вывести a :: Int нельзя, т.к. нет гарантии что один из побочных эффектов не сделает a <- «5» (тут динамика).

Короче, по части синтаксиса (возможность работать с AST, возможность расширять целевой язык новыми продукциями и их семантическими атрибутами) я вижу разницу. По части типов я особой разницы не вижу, только в CL не реализован (не невозможно, а просто не сделано) более мощный вывод типов, вместо этого есть рестарты в рантайме.

А вместо

17 - 3 - 4 - 5,

ты тоже напишешь

((17 - 3) - 4) - 5?

Или ума все же хватит скобочки лишние не тыкать?

Правую ассоциативность с левой не путай. Левая всем привычная, а вот правая - наоборот, и лучше бы ставить скобки.

>Правую ассоциативность с левой не путай. Левая всем привычная, а вот правая - наоборот, и лучше бы ставить скобки.

Глупости. Кому это всем?

«правая ассоциативность» это другое название карринга головного мозга

где доказательство, что очевидное соотвествите между Fun(X,Y,Z) и Fun(X, Fun(X,Y)) сохраняет *все* необходимые в программировании свойства, в том числе вычислительную сложность?

если таковое имеется, давай ссылку (а про изоморфизм в математическом смыле изоморфизма отображений и не заикайся)

а пока доказательства нет, я буду различать Fun(X,Y,Z) и Fun(X, Fun(X,Y))

но мне показалось, что в достаточно очевидной стековой модели имеются проблемы, хотя доказать это еще не успел

Fun(X, Fun(Y,Z)) конечно же

>«правая ассоциативность» это другое название карринга головного мозга

Ты понимаешь, что эти вещи вообще нихера не связаны?

где доказательство, что очевидное соотвествите между Fun(X,Y,Z) и Fun(X, Fun(X,Y))

АТМТА дыже исправленный вариант «Fun(X, Fun(Y,Z))» херня.

Да и вообще, никто не мешает делать некаррированные функции.

Надо понимать, что X -> Y -> Z и X -> (Y -> Z) - одно и то же, но вот (X, Y) -> Z уже совсем другое.

если таковое имеется, давай ссылку (а про изоморфизм в математическом смыле изоморфизма отображений и не заикайся)

какой лютый пиз*** с желание вы****ться >.<

> АТМТА дыже исправленный вариант «Fun(X, Fun(Y,Z))» херня.

true

Надо понимать, что X -> Y -> Z и X -> (Y -> Z) - одно и то же, но вот (X, Y) -> Z уже совсем другое.

trrrue

какой лютый пиз*** с желание вы****ться >.<

true

> Надо понимать, что X -> Y -> Z и X -> (Y -> Z) - одно и то же, но вот (X, Y) -> Z уже совсем другое.

напомню, что речь шла о функции compose, которая принимает 2 аргумента, так что она как раз и имела тип, который ты называешь (X, Y) -> Z

этот тип может быть записан как X -> Y -> Z (хотя неясно, уложится ли в твою голову то, что оператор -> может быть НЕассоциативным вообще — ни право, ни лево); естественно, может быть записан записан нормальными людьми, а не теми, которые внесли в хаскель недоказанную (?) эквивалентность

какой лютый пиз*** с желание вы****ться >.<

какие эмоции!!! какой накал!!! а я ведь всего-то попросил ссылку на доказательство

интересно, что будет, если я тут напишу доказательство противоположного?

>> какой лютый пиз*** с желание вы****ться >.<

true

я начинаю подозревать, что хаскель головного мозга заразен...

принимает 2 аргумента, так что она как раз и имела тип, который ты называешь (X, Y) -> Z

Нет, у того, что ты написал один аргумент - тупл.

этот тип может быть записан как X -> Y -> Z

Нет, не может, здесь два аргумента. Эту функцию можно частично применить (f x) и получить в результате функцию типа Y -> Z.

Не рокет саенс вроде.

> какие эмоции!!! какой накал!!! а я ведь всего-то попросил ссылку на доказательство

Нет, ты начал бросаться терминами, в которых ничерта не смыслишь, начал приводить неверные примеры (зато с кучей пафоса впридачу)

интересно, что будет, если я тут напишу доказательство противоположного?

Мм? Ты? Ты не понимаешь, что такое частичное применение, карринг, и не понимаешь, что обозначает и как интерпретируется запись сигнатуры функции (но в то же время бросаешься эпитетами «хаскель головного мозга»).

Для доказательства ещё дорасти нужно (хотя бы попытаться чётко сформулировать, что же те собираешься доказывать, для начала).

> Кому это всем?

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

> Нет, не может, здесь два аргумента.

Нет, не два. Вообще, в языках с принудительным каррингом функций многих аргументов не существует - только функции одного.

fail

> > Кому это всем?

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

Скажи, ты знаешь Си?

Какая ассоциативность у: = += -= *= /= %= <<= >>= &= ^= |= ! ~ ++ — + - (type) * & sizeof?

Попимо арифметических операций есть и другие, и есть операции с естественной для человека правой ассоциативностью

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

Правую ассоциативность с левой не путай. Левая всем привычная, а вот правая - наоборот

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

В haskell правоассоциативны по крайней мере (.) (композиция функций), (++) (конкатенация списков) и ($) (применение функции), ну и (->) (хотя такой функции и нет, точнее есть операция с типовой стороны, не с функциональной).

и лучше бы ставить скобки.

Ага, то есть надо вот так: ((((((5*4)*3)*2)+1)+2)+3), а ещё лучще так: ((+) ((+) ((+) ((*) ((*) ((*) 5 4) 3) 2) 1) 2) 3) :)

>напомню, что речь шла о функции compose, которая принимает 2 аргумента, так что она как раз и имела тип, который ты называешь (X, Y) -> Z

Речь шла о функции композиции с типом X -> Y -> Z.

этот тип может быть записан как X -> Y -> Z

Не может. Типы (X, Y) -> Z и X -> Y -> Z совершенно разные.

хотя неясно, уложится ли в твою голову то, что оператор -> может быть НЕассоциативным вообще — ни право, ни лево

Нет не может :D. То есть, с точки зрения математического понятия ассоциативности, оператор -> и так не ассоциативен (x -> y) -> z не то же самое, что x -> (y -> z). Но вот с точки зрения «информатики». Правоассоциативность или левоассоциативность - лишь приоритет выполнения операций.

естественно, может быть записан записан нормальными людьми, а не теми, которые внесли в хаскель недоказанную (?) эквивалентность

Ты таки нихрена не понял. Еще раз. Типы (X, Y) -> Z и X -> Y -> Z совершенно разные. Если у тебя прям так шило в заднице, то сделай себе свою собственную композицию:

compose :: ((b -> c), (a -> b)) -> a -> c

compose (f, g) = \x -> f $ g x

> Какая разница - привычно или нет? Если есть операция с неким приоритетом и ассоциативностью, то скобки ставят только тогда когда хотят изменить этот приоритет по умолчанию и эту ассоциативность по умолчанию. В математике это привычная практика для любых инфиксных значков.

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

> Попимо арифметических операций есть и другие, и есть операции с естественной для человека правой ассоциативностью

Есть только 4 естественные для человека инфиксные операции, это + (с вариациями типа ++) - * /, причем тут не важно что именно делает операция, а важно, как именно она обозначается. Все 4 перечисленные операции левоассоциативны и * / всегда имеют более высокий приоритет, чем + -. Вне зависимости от того, как операции определены. Все остальные операции не являются естественными и при их использовании следует расставлять скобки, чтобы код не стал обфусцированным говном из = += -= *= /= %= <<= >>= &= ^= |= ! ~ ++ — + - (type) * & sizeof, которое не разберешь без таблицы приоритетов.

С каких пор операция присваивания стала неестественной?

P.S. Не нужно использовать слово «ественный» в смысле «привычный с начальной школы»

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

REPL всё равно удобнее, чем write-save-compile-run-test

«Естественная» операция присваивания вообще значения не возвращает и никак не ассоциативна. Ни слева, ни справа.

Да ну. Вы ни разу не писали a = b = 1 + 5 ?

> Нормальных людей как минимум не возбуждают списки, алгебраические типы или субтиповые полиморфизмы.

может не возбуждают, но доставляют

> Да ну. Вы ни разу не писали a = b = 1 + 5 ?

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

>это частный геморрой сишечки и ей подобных, в нормальных императивных статически-типизированных языках операция присваивания ничего не возвращает

Очень спорно насчет нормальных. И при чем тут статическая типизация?