Кто хотел лисп, компилирующийся в C++?

Ну да, Integer тоже магия.

Можешь считать, что на самом деле для описания типа (для разработчика языка) доступно http://clhs.lisp.se/Body/t_satisf.htm.

То есть:

(define-type Any (satisfies (lambda (x) #t))
(define-type Integer (satisfies integer?))
...

Если бы как в CL не было требования на статическую проверку типов, то тип так и должен определяться. В обычном (не Typed) Racket любой тип определяется просто предикатом.

Обозначает что A1, A2, A3... подтипы T.

Ну да. В свою очередь A1..An подтипы Integer, значит T - подтип Integer.

Нет.

Да.

1 <| Integer

Ага.

1 <| yoba

Да. и Yoba <| Integer. Иначе как я смог передать Yoba в функцию, которая требует Integer?

Обрати внимание:

> (+ (my-id 5) 1)
- : Integer [more precisely: Positive-Index]
6

То есть Positive-Index - подтип Integer. Аналогично:

> (my-id 5)
- : Integer [more precisely: yoba]
5

Можешь считать, что на самом деле для описания типа (для разработчика языка) доступно

Оно и доступно:

#lang typed/racket

(define-type MyInteger (Refinement exact-integer?))

(: my+ (MyInteger -> Integer))
(define (my+ x)
  (if (exact-integer? x) 
      (+ x 1)
      0))

Ну так покажи мне как задефайнить свой тип MyAny с теми же свойствами что и Any.

Т.е. по-твоему базис любого языка — это магия? Так бы и сказал.

Кроме того, если бы можно было определить такой новый тип, то Any был бы не Any.

Кроме того, если бы можно было определить такой новый тип, то Any был бы не Any

(define-type MyAny (Refinement (lambda (x) #t))

    for (auto i = 0; i < 10; ++i)
        printf("%d\n", i);

	xorl	%ebx, %ebx
.L3:
	movl	%ebx, %edx
	xorl	%eax, %eax
	movl	$.LC0, %esi
	movl	$1, %edi
	addl	$1, %ebx
	call	__printf_chk
	cmpl	$10, %ebx
	jne	.L3

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

0_o

В скале же подобное есть, в смысле List[Nothing] — Nothing самый нижний тип, так что для List[Nothing] можно сконструировать только List()/Nil, но не List(что-то). А в рантайме — ну односвязные списки они и есть списки.

это ж просто функция

это ж просто функция

Хз. Но в http://xathrya.web.id/blog/2012/10/22/guide-to-lambda-closure-in-c11/ пишут, что «[&](...) {...}» — замыкание

Например,

int min_len = 0;
cin >> min_len;
return global_address_book.find( [&] (const string& addr) { return addr.length() >= min_len; } );

#lang typed/racket

(define-type MyAny (Refinement (lambda (x) #t)))

. Type Checker: parse error in type;
 expected a valid type
  given: (x) in: (x)

Racket 6.0.1, чего не хватает?

чего не хватает

Хм... оказывается своё предикат не работает.

(define-type MyString (Refinement string?)) работает. А вот

(: any? (Any -> Boolean))
(define (any? x) #t)
(define-type MyAny (Refinement any?))

Всё равно даёт ошибку :-(

В общем, Experimental...

Должен. Ты же не будешь сравнивать:

Они ведь и так работает? В смысле, не даёт сравнивать.

ах да плюсы же нынче такое из коробки могут, ок

В скале же подобное есть, в смысле List[Nothing]

В Racket тоже есть: Null

Подобное Racket я и имел в виду. List[Nothing] <: List[A] для любого A. Правда

scala> List("2").tail
res1: List[String] = List()

scala> 1 :: List("2").tail
res2: List[Any] = List(1)

scala> 1 :: List("2").tail.asInstanceOf[List[Nothing]]
res3: List[Int] = List(1)

Хм... оказывается своё предикат не работает.

Если только из нетипизированного модуля require сделать.

Подобное Racket я и имел в виду. List[Nothing] <: List[A]

Не, тут смысл в том что в racket есть выделенный тип именно для пустого списка. И именно этот тип для пустого списка является подтипом. То есть не List[Nothing] <: List[A], а Null <: (Listof A)

Когда компилятор может гарантировать что мы консим к пустому списку (типа Null) то все ок, а если не может - получим как и в скале (Listof Any).

не List[Nothing] <: List[A], а Null <: (Listof A)

type Null = List[Nothing]

val nil: Null = Nil

Когда компилятор может гарантировать что мы консим к пустому списку (типа Null) то все ок

> 1 :: nil
res1: List[Int] = List(1)

Просто это дальше никак не полезно

def tail[A](xs: List[A]): List[A] = xs.tail

scala> tail(1 :: nil)
res2: List[Int] = List()
// !~ Null

вместо

> cdr
- : (All (a b) (case-> ((Pairof a b) -> b : ((! False @ (cdr) 0) | (False @ (cdr) 0)) (cdr 0)) ((Listof a) -> (Listof a))))

0_o

Ой ой ой, какой ты умный. Ты мне AST покажи.

После раскрытия макросов остаётся язык с функциями и http://www.lispworks.com/documentation/HyperSpec/Body/03_ababa.htm. Т.е. dotimes раскрывается, остаётся tagbody и т.п., они компилируются в такой же код, что и сишный for (чего там, можно считать, что за компиляцию for отвечает код подобный коду макроса dotimes).

CCL:

;;; (dotimes (i 10) (print i))
         (xorl (% save0.l) (% save0.l))          ;    [13]
         (jmp L48)                               ;    [16]

;;; (print i)
L18
         (movq (% save0) (% arg_z))              ;    [18]
         (movl ($ 8) (% nargs))                  ;    [21]
         (movq (@ 'PRINT (% fn)) (% temp0))      ;    [26]
         (nop)                                   ;    [33]
         (callq (@ 10 (% temp0)))                ;    [34]
         (leaq (@ (:^ L0) (% rip)) (% fn))       ;    [37]

;;; (dotimes (i 10) (print i))
         (addq ($ 8) (% save0))                  ;    [44]
L48
         (cmpq ($ 80) (% save0))                 ;    [48]
         (jl L18)                                ;    [52]

^ только вызов print навороченный, что не имеет отношения к макросам и их влиянию на оптимизации.

ECL — Кто хотел лисп, компилирующийся в C++? (комментарий).

они компилируются в такой же код, что и сишный for.

В данном примитивном случае - да. А вот если навернуть макрос на макрос и завернуть в макрос, то приличный с виду код к компилятору попадает в виде портянки из goto на goto, завёрнутое в goto.

Понятно, что на выходе будут одни jmp, но умный компилятор мог бы выбросить или сократить код, если бы оперировал не с портянкой goto, а с исходным структурированным кодом. ИМХО.

Обычно работают на уровне IR, то есть если раскрытый лисп это IR0 (у SBCL дальше IR1, IR2, asm, binary) и нам нужен, например, unrolling, то делаем его в макросе, до IR0, который будет уже готовым, то есть цикл (dotimes) реализует макрос, после искать условия и т.п. уже не нужно, нужно решать проблемы как уметь прыгать по меткам из go в выражениях (другая задача, циклы уже прошли). А если пропустить IR на котором нужно делать оптимизации X до IR на котором эти оптимизации проводить проблематично, то конечно ерунда получится :)

Что-то ты переборщил с типом cdr.

> cdr
- : (All (a b) (case-> (-> (Pairof a b) b) (-> (Listof a) (Listof a))))

v5.3.6 так пишет.

и нам нужен, например, unrolling, то делаем его в макросе, до IR0, который будет уже готовым

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

Ну сделали мы анроллинг в макросе, а теперь надо ещё block transform, а потом ещё чего нибудь - так мы весь компилятор в макрос запихнём.

Да нет, компилятор уже есть для IR0, он там может себе что угодно делать (как gcc — -fdump-tree-*, то же tagbody/go для циклов). Вообще, если сравнивать типичный язык без макросов с оптимизирующим компилятором, то сравнивать с IR0, то есть лиспом без макросов и его оптимизирующим компилятором. А назначение макросов по задумке именно в расширении компилятора и добавлении специальных форм, они должны писать IR0 — делать какие-то оптимизации или нет это их дело. Я про unrolling заговорил потому что вот SBCL не делает (ни слова на все сорцы, и вообще он мало что делает с циклами по сравнению с gcc), поэтому можно делать в макросе.

Или взять LLVM — что там для циклов и почему ему не нужно знать AST, понимать что это цикл, догадываться где условие выхода и тп? :)

он там может себе что угодно делать

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

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

Не получится, т.к. в лиспе много сделано на макросах, без макросов это будет «метаассемблер» с примитивщиной, типа tagbody/go, let и т.д.

про unrolling заговорил потому что вот SBCL не делает

А как он будет его делать, если компилятор получает на вход не цикл, как единицу компиляции, а его «развертку» в виде goto? В итоге компилятор не заморачиваясь транслирует goto в jmp один к одному. Вот и весь сказ.

А как он будет его делать, если компилятор получает на вход не цикл, как единицу компиляции, а его «развертку» в виде goto

Racket делает. Все макросы могут разворачиваться как до конца, так и до имён стандартной библиотеки. Компилятор видит оба варианта.

К слову, в CL запрещено менять макросы из модуля CL, так что никто не мешает в конкретной реализации dotimes не разворачивать, а сразу передавать компилятору. Тогда оптимизации не будет только при извращении типа (eval (macroexpand '(dotimes (i 10) ...))).

Он там не может делать что угодно, потому что он не видит исходный код.

http://gcc.gnu.org/onlinedocs/gccint/Tree-SSA-passes.html

http://llvm.org/docs/Passes.html, http://llvm.org/docs/LangRef.html

http://en.wikipedia.org/wiki/Static_single_assignment_form

А как он будет его делать, если компилятор получает на вход не цикл, как единицу компиляции, а его «развертку» в виде goto?

Он строит CFG (у SBCL IR1 это тоже CFG).

Попробуй

clang -S -O0 -emit-llvm loop.c -o loop.ll
clang -S -O3 -emit-llvm loop.ll -o loop-opt.ll

Не получится, т.к. в лиспе много сделано на макросах, без макросов это будет «метаассемблер» с примитивщиной, типа tagbody/go, let и т.д.

Ну ок (как только найдём пример проблемы).

Как малознакомому с CL можешь посоветовать, что почитать о написании высокопроизводительного кода на CL? Интересует обработка большого количества данных на локальном компе.

А llvm и gcc делают loop unrolling на голом ssa cfg, где никакими for-ами и не пахнет. Так что не тупи и rtfm!

Бугурт от goto - первейший признак ламера.

что почитать о написании высокопроизводительного кода на CL

http://t-b-o-g.blogspot.ru/2009/12/brians-brain-on-common-lisp-take-3.html

Просто это дальше никак не полезно

Просто более точный тип. Ну там как Vector<5> вместо просто Vector.

В данном примитивном случае - да. А вот если навернуть макрос на макрос и завернуть в макрос, то приличный с виду код к компилятору попадает в виде портянки из goto на goto, завёрнутое в goto.

Нормальный компилятор свернет это в циклы.

благодарю

Вот для примера, loop.c:

void foobar(int);

void loop() {
    for (int i = 0; i < 4; ++i)
        foobar(i);
}

gcc -std=c99 -O1 -S -fdump-tree-all -fdump-rtl-all -funroll-all-loops loop.c

В начале получится общий для всех языков GCC ORIGINAL/GIMPLE (было бы не очень хорошо реализовывать все оптимизации для всех фронтендов снова и снова) который выглядит примерно так (loop.c.003t.original, loop.c.004t.gimple):

    int i = 0;
    goto <D.1596>;
    <D.1595>:;
    foobar (i);
     ++i;
    <D.1596>:;
    if (i <= 3) goto <D.1595>; else goto <D.1597>;
    <D.1597>:;

уже метки и условные и безусловные goto. Потом он преобразуется в CFG и SSA (loop.c.012t.cfg, loop.c.016t.ssa) который выглядит примерно так же (только в виде графа / SSA). http://gcc.gnu.org/onlinedocs/gccint/Tree-SSA-passes.html выполняются на нём, в т.ч. unrolling для небольших циклов, loop.c.115t.cunroll:

  int i;
  unsigned int ivtmp_2;
  unsigned int ivtmp_13;
  unsigned int ivtmp_19;
  unsigned int ivtmp_25;

  <bb 2>:
  foobar (0);
  i_12 = 1;
  ivtmp_13 = 3;
  foobar (i_12);
  i_18 = i_12 + 1;
  ivtmp_19 = ivtmp_13 + 4294967295;
  foobar (i_18);
  i_24 = i_18 + 1;
  ivtmp_25 = ivtmp_19 + 4294967295;
  foobar (i_24);
  i_5 = i_24 + 1;
  ivtmp_2 = ivtmp_25 + 4294967295;
  return;

более сложный unrolling выполняется даже ещё позже во время http://gcc.gnu.org/onlinedocs/gccint/RTL-passes.html на RTL (loop.c.186r.loop2_unroll).

В случае LLVM

clang -S -O0 -emit-llvm loop.c -o loop.ll

даст IR с теми же метками и br с условиями и без

  %i = alloca i32, align 4
  store i32 0, i32* %i, align 4
  br label %1

; <label>:1                                       ; preds = %6, %0
  %2 = load i32* %i, align 4
  %3 = icmp slt i32 %2, 4
  br i1 %3, label %4, label %9

; <label>:4                                       ; preds = %1
  %5 = load i32* %i, align 4
  call void @foobar(i32 %5)
  br label %6

; <label>:6                                       ; preds = %4
  %7 = load i32* %i, align 4
  %8 = add nsw i32 %7, 1
  store i32 %8, i32* %i, align 4
  br label %1

; <label>:9                                       ; preds = %1
  ret void

Выкидываем сишный исходник и оптимизируем сам IR.

clang -S -O1 -emit-llvm loop.ll -o loop-opt.ll

  br label %1

; <label>:1                                       ; preds = %1, %0
  %i.01 = phi i32 [ 0, %0 ], [ %2, %1 ]
  tail call void @foobar(i32 %i.01) #2
  %2 = add nsw i32 %i.01, 1
  %exitcond = icmp eq i32 %2, 4
  br i1 %exitcond, label %3, label %1

; <label>:3                                       ; preds = %1
  ret void

clang -S -O2 -emit-llvm loop.ll -o loop-opt.ll

  tail call void @foobar(i32 0) #2
  tail call void @foobar(i32 1) #2
  tail call void @foobar(i32 2) #2
  tail call void @foobar(i32 3) #2
  ret void

14: 1 1401 31.7 1401 31.7 1401 31.7 - «foreign function sigprocmask»

Ужос, шо там за код-то такой?

А, это же не оптимизированный. Но всё равно интересно

Там же ссылки есть http://t-b-o-g.blogspot.com/2009/10/brians-brain-on-common-lisp.html http://t-b-o-g.blogspot.com/2009/10/brians-brain-on-common-lisp-take-2.html

Лол, а мне всё равно не ясно. Я подумал на этот их (gc :full t), но нифига. Сделал ситуацию с подчисткой многа внепакетных символов. И що бы ви думали? Никакого sigprocmask даже близко. Да и не должно быть, ЕМНИП, там сигналы не блокируются, а прога входит в pseudo-atomic section сначала.

То ли архитектура не та, то ли SBCL так сильно поменялся, то ли я чего-то упускаю