2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Язык Factor
Сообщение20.12.2019, 23:16 
Заслуженный участник


27/04/09
28128
iifat
Компилированием ... из [ ... ] в слово и помещением ссылки на него в стек?

 Профиль  
                  
 
 Re: Язык Factor
Сообщение21.12.2019, 04:54 
Заслуженный участник


16/02/13
4105
Владивосток
Например. В зависимости от варианта Форта и фантазии автора. Ну, там ещё упоминаются операции конкатенации двух таких ссылок, что тоже отнюдь не бином Ньютона.

 Профиль  
                  
 
 Re: Язык Factor
Сообщение21.12.2019, 16:37 
Заслуженный участник


27/04/09
28128
Кстати с одной стороны такие скобки аналогичны λ-абстракции, а с другой — цитированию, и вот после этого может захотеться иметь и аналоги лисповым quasiquote и unquote, то есть выполнения некоторых подпоследовательностей и вставки того, что они положили в стек, перед «замораживанием». Интересно, есть ли они в Factor (скорее всего должны бы быть).

 Профиль  
                  
 
 Re: Язык Factor
Сообщение21.12.2019, 17:34 
Заслуженный участник


16/02/13
4105
Владивосток
arseniiv в сообщении #1431272 писал(а):
λ-абстракции
Оные абстракции предполагают указание формальных параметров, не?

 Профиль  
                  
 
 Re: Язык Factor
Сообщение21.12.2019, 18:33 
Заслуженный участник


27/04/09
28128
Потому-то и аналогия. Было слово, брало значения из стека (~ видимых переменных), но его закрыли в скобки, и теперь оно будет брать значения такие, какие ему попадут при вызове. Аналогично, call — аналогия аппликации, но не полная. Квазицитирование частично будет аналогом навешивания λ не на все свободно входящие переменные.

 Профиль  
                  
 
 Re: Язык Factor
Сообщение27.12.2019, 22:19 
Заслуженный участник


31/12/15
922
Пытаюсь понять "стэковый эффект". В Факторе при определении функции надо указывать её стэковый эффект. В простейшем случае это выглядит так
Код:
+ ( x y -- z )

что значит "функция + берёт два элемента из стэка и кладёт туда один элемент". На самом деле так тоже можно
Код:
+ ( x x -- x )

пока что важно только количество. Компилятор Фактора проверяет стэковый эффект и использует его для оптимизаций. Попробуем определить функцию twice, которая применяет некоторую функцию к аргументу два раза подряд. Если в стэке лежат элементы 0 [ 1 + ] и мы вводим команду twice, должно получиться 2 (результат применения [ 1 + ] к 0 два раза подряд). Определяем twice
Код:
: twice ( value quot -- result ) dup compose call ;

В скобках указан стэковый эффект. В стэке должны лежать value (в нашем случае 0) и quot ("цитата", выражение в квадратных скобках, в нашем случае [ 1 + ]). Слова value, quot, result можно заменить на другие, они только для удобства. Команда dup удваивает последний элемент стэка, получится
0 [ 1 + ] [ 1 + ]. Команда compose берёт композицию двух последних элементов, получится 0 [ 1 + 1 + ]. Команда call применяет последний элемент стэка к аргументам. Вводим команду twice - компилятор выдаёт ошибку "невозможно проверить стэковый эффект". Чтобы заработало, надо к определению twice добавить слово inline
Код:
: twice ( value quot -- result ) dup compose call ; inline

Насколько я понял, компилятор будет вместо слова twice вставлять его определение, в котором достаточно информации, чтобы проверить стэковый эффект во время компиляции. Короткие программы имеет смысл определять как inline. Если программа длинная, можно записать без inline, использовав call(
Код:
: twice ( value quot -- result ) dup compose call( x -- x ) ;

Обратите внимание на отсутствие пробела в команде call(
В скобках после call указан стэковый эффект цитаты, которая будет вызываться. В этом случае стэковый эффект будет проверяться не при компиляции, а во время выполнения программы, оптимизаций не будет.

 Профиль  
                  
 
 Re: Язык Factor
Сообщение27.12.2019, 23:03 
Заслуженный участник
Аватара пользователя


30/01/06
72407
george66 в сообщении #1432329 писал(а):
В Факторе при определении функции надо указывать её стэковый эффект. В простейшем случае это выглядит так
+ ( x y -- z )
что значит "функция + берёт два элемента из стэка и кладёт туда один элемент".

А если "берёт неизвестно сколько и кладёт неизвестно сколько"? Например, берёт $n+1$ элементов, где $n$ - верхний элемент стека, а кладёт обратно $2n$?

 Профиль  
                  
 
 Re: Язык Factor
Сообщение28.12.2019, 00:14 
Заслуженный участник


27/04/09
28128
Там разве нельзя записать тип функции вместо quot? Тогда и проверку компилятор мог бы делать. Скажем как-нибудь так это могло бы выглядеть: twice ( a ( a -- a ) -- a ). Посмотрите стековые эффекты compose и call — если они не встроены в механизм вывода и язык достаточно выразительный по части типов (вроде до такой степени уж должен был быть, когда я смотрел несколько лет назад), то можно будет увидеть, как выразить это. Тогда компилятор сможет убедиться без инлайна (что на мой взгляд не лучшее решение — инлайн должен бы быть одним, а отмена проверки типов на месте — другим, не связанным маркером).

На хаскеле этот тип выглядел бы (a ::: s -> a ::: s) ::: a ::: s -> a ::: s, хотя можно и проще: (s -> s) ::: s -> s. Вышенаписанному эффекту отвечает первый, а не второй, но самому определению отвечает именно что более общий второй; действительно, Munin как раз замечает, что функция может брать не один аргумент и возвращать тоже не один, в частности ей можно и ноль, и два и т. д., и определению это всё не противоречит, лишь бы она только складывала назад значения тех же типов что брала.

По поводу нотации и всего остального см. демонстративный модуль, который должен компилироваться в GHC. ↓ Если только нет опечаток.

код: [ скачать ] [ спрятать ]
Используется синтаксис Haskell
{-# language TypeOperators #-}
import Control.Category ((>>>)) -- композиция слева направо

-- определим гетерогенный cons, который будем писать навроде e1 ::: e2 ::: e3 ::: tail
data top ::: below = top ::: below deriving (Eq, Show)
infixr 5 ::: -- правоассоциативный и достаточно хваткий для удобства чтения кода
-- для дна стека можно использовать хоть и (), но оно нам не понадобится

-- ( a b -- c d ) записывается как тип b ::: a ::: below -> d ::: c ::: below:
-- b ложили последним, вот оно и в голове;
-- `below` — тоже переменная, названная так для понятности,
-- она обозначает неизменный низ стека

-- сии функции предполагаются уже определёнными где-то там,
-- но я приведу и определения чтобы можно было поиграть;

dup :: a ::: below -> a ::: a ::: below
dup (x ::: xs) = x ::: x ::: xs

call :: (stack1 -> stack2) ::: stack1 -> stack2
call (f ::: xs) = f xs

compose :: (stack2 -> stack3) ::: (stack1 -> stack2) ::: below -> (stack1 -> stack3) ::: below
compose (g ::: f ::: xs) = (f >>> g) ::: xs

-- интересующая функция:

twice = dup >>> compose >>> call
-- должен выводиться тип (stack -> stack) ::: stack -> stack
-- его можно унифицировать с предлагавшимся мной выше типом (a ::: s -> a ::: s) ::: a ::: s -> a ::: s
 


-- Сб дек 28, 2019 02:49:18 --

Ну чего, я сам полез смотреть. И:

• Псевдоцитирование действительно есть, ну может разве не такое как я думал: https://docs.factorcode.org/content/article-fry.html.

• Типы хитренькие вроде всё же есть. https://docs.factorcode.org/content/article-effects-variables.html, правда я бы не называл это row polymorphism, обычно то немного другое означает (неупорядоченные наборы типов, снабжённых метками, а тут упорядоченные и не снабжённые метками; и используются такие строки для определения extensible records и variants — а тут просто гетерогенный список, ей-диэдру).
george66, попробуйте вашей функции приделать ( ..a quot: ( ..a -- ..a ) -- ..a ), если я правильно понял.

 Профиль  
                  
 
 Re: Язык Factor
Сообщение28.12.2019, 05:50 
Заслуженный участник


31/12/15
922
Продолжаем, проснувшись от сна. Стэковый эффект многих inline-комбинаторов зависит от цитат, к которым они применяются (а комбинатор - это функция, которая применяется к цитатам). Чтобы задать их стэковый эффект, используют stack effect row variables. Сразу пример для стандартного комбинатора while
Код:
while ( ..a pred : ( ..a -- ..b ? ) body : ( ..b -- ..a ) -- ..b )

В стэке лежат друг за другом: группа элементов ..a, цитата pred и цитата body. Цитата pred имеет стэковый эффект
Код:
pred : ( ..a -- ..b ? )

что значит, она применяется к группе элементов ТОЙ ЖЕ ДЛИНЫ (поэтому одинаковое название ..a) и кладёт вместо них в стэк группу элементов ..b и поверх них логическое значение, обозначенное вопросительным знаком ?
Цитата body имеет стэковый эффект
Код:
body : ( ..b -- ..a )

она применяется к группе длины ..b и кладёт вместо них в стэк группу длины ..a
Вводим команду while, она применяет к исходной группе ..a предикат pred, получает ..b ?, смотрит значение истинности и либо заканчивает (выдавая ..b и убрав из стэка ?), либо применяет тело body и повторяет проверку.

 Профиль  
                  
 
 Re: Язык Factor
Сообщение28.12.2019, 13:06 
Заслуженный участник


31/12/15
922
Как пишет автор языка, стэковый эффект нужен для документации (гораздо легче понять программу, если указаны эффекты, что уже могу подтвердить), а также как примитивная система типов, позволяющая улавливать грубые ошибки. Но вообще, в Факторе есть настоящие типы
https://docs.factorcode.org/content/art ... rence.html
https://docs.factorcode.org/content/art ... tions.html

 Профиль  
                  
 
 Re: Язык Factor
Сообщение29.12.2019, 07:51 
Заслуженный участник


31/12/15
922
Код:
: qsort ( seq -- seq )
    dup empty? [
      unclip [ [ < ] curry partition [ qsort ] bi@ ] keep
      prefix append
    ] unless ;

Быстрая сортировка на Факторе. Сейчас будем разбираться. Функция qsort применяется к последовательности и выдаёт последовательность, соответственно стэковый эффект обозначен как ( seq -- seq ). Команда dup удваивает последовательность (на самом деле не саму последовательность, а ссылку на неё, для настоящего копирования есть команда clone). Предикат empty? проверяет на пустоту. Команда unclip отклипывает от последовательности первый элемент, стэковый эффект
Код:
unclip ( seq -- rest first )

К этому первому элементу (назовём его first) будет применена [ < ] curry, получится предикат [ first < ] сравнения с first по величине. Но прежде, чем это сделать, элемент first будет сохранён командой keep и возвращён в стэк потом, когда будет вычислена длинная цитата (после которой стоит keep). Команда partition применяется к последовательности rest и предикатной цитате [ first < ], применяет предикат по очереди ко всем элементам последовательности rest и выдаёт две последовательности - тех элементов, что меньше first и тех, что не меньше. Комбинатор bi@ применяет [ qsort ] к обеим получившимся последовательностям. После этого в стэке лежат две последовательности и элемент first (положенный туда командой keep). Приписываем first спереди ко второй последовательности командой prefix и соединяем две последовательности командой append.
Для сравнения быстрая сортировка на разных языках
http://rosettacode.org/wiki/Sorting_alg ... ort#Factor

 Профиль  
                  
 
 Re: Язык Factor
Сообщение29.12.2019, 12:22 
Заслуженный участник


31/12/15
922
Эта функция не является комбинатором, она не применяется к цитатам (а применяется к последовательности), поэтому её не надо объявлять как inline (хотя допустимо).
Теперь про дырявые цитаты (fried quotations). Дырявые цитаты начинаются с '[
Кладём в стэк 1, затем 2, затем дырявую цитату '[ _ + _ ] и что мы видим в стэке?
[ 1 + 2 ]

 Профиль  
                  
 
 Re: Язык Factor
Сообщение25.05.2020, 20:43 
Заслуженный участник


31/12/15
922
А если сделать Factor с типами и добавить индуктивные и зависимые типы, не заменит ли это Агду?

 Профиль  
                  
 
 Re: Язык Factor
Сообщение25.05.2020, 23:06 
Заслуженный участник


27/04/09
28128
Я бы подумал, что в этом случае разница будет не сильно более чем синтаксической. Если мы берём систему типов из какого-то языка почти полностью, то это обычно требует и рантайм подстроить соответствующе, и семантику конструкций языка дополнить, если изначально она хитрые типы не поддерживала. Конечно, разнообразие возможных идей останется, но от конкретно языка с именем Factor ничего кроме конкатенативного синтаксиса не останется (притом ещё и не синтаксиса всего; я копал в этом направлении и пришёл к выводу, что некоторые конструкции — типа например определений типоклассов или аннотирования типов к значениям по части синтаксиса самих типов — в конкатенативном оформлении как будто нечитаемы; да и вообще никто не говорил, что синтаксис определений в хорошем языке должен что-то общее иметь с синтаксисом выражений).

 Профиль  
                  
 
 Re: Язык Factor
Сообщение04.06.2020, 16:32 
Заслуженный участник


31/12/15
922
Обнаружил в Факторе обёртку llvm! Не устаёт удивлять. Сейчас напишу компилятор на Факторе с Фактора в llvm. И типов всяких развесистых добавлю, как в Агде.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group