2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 Re: Язык Factor
Сообщение20.12.2019, 23:16 
iifat
Компилированием ... из [ ... ] в слово и помещением ссылки на него в стек?

 
 
 
 Re: Язык Factor
Сообщение21.12.2019, 04:54 
Например. В зависимости от варианта Форта и фантазии автора. Ну, там ещё упоминаются операции конкатенации двух таких ссылок, что тоже отнюдь не бином Ньютона.

 
 
 
 Re: Язык Factor
Сообщение21.12.2019, 16:37 
Кстати с одной стороны такие скобки аналогичны λ-абстракции, а с другой — цитированию, и вот после этого может захотеться иметь и аналоги лисповым quasiquote и unquote, то есть выполнения некоторых подпоследовательностей и вставки того, что они положили в стек, перед «замораживанием». Интересно, есть ли они в Factor (скорее всего должны бы быть).

 
 
 
 Re: Язык Factor
Сообщение21.12.2019, 17:34 
arseniiv в сообщении #1431272 писал(а):
λ-абстракции
Оные абстракции предполагают указание формальных параметров, не?

 
 
 
 Re: Язык Factor
Сообщение21.12.2019, 18:33 
Потому-то и аналогия. Было слово, брало значения из стека (~ видимых переменных), но его закрыли в скобки, и теперь оно будет брать значения такие, какие ему попадут при вызове. Аналогично, call — аналогия аппликации, но не полная. Квазицитирование частично будет аналогом навешивания λ не на все свободно входящие переменные.

 
 
 
 Re: Язык Factor
Сообщение27.12.2019, 22:19 
Пытаюсь понять "стэковый эффект". В Факторе при определении функции надо указывать её стэковый эффект. В простейшем случае это выглядит так
Код:
+ ( 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 
Аватара пользователя
george66 в сообщении #1432329 писал(а):
В Факторе при определении функции надо указывать её стэковый эффект. В простейшем случае это выглядит так
+ ( x y -- z )
что значит "функция + берёт два элемента из стэка и кладёт туда один элемент".

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

 
 
 
 Re: Язык Factor
Сообщение28.12.2019, 00:14 
Там разве нельзя записать тип функции вместо 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 
Продолжаем, проснувшись от сна. Стэковый эффект многих 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 
Как пишет автор языка, стэковый эффект нужен для документации (гораздо легче понять программу, если указаны эффекты, что уже могу подтвердить), а также как примитивная система типов, позволяющая улавливать грубые ошибки. Но вообще, в Факторе есть настоящие типы
https://docs.factorcode.org/content/art ... rence.html
https://docs.factorcode.org/content/art ... tions.html

 
 
 
 Re: Язык Factor
Сообщение29.12.2019, 07:51 
Код:
: 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 
Эта функция не является комбинатором, она не применяется к цитатам (а применяется к последовательности), поэтому её не надо объявлять как inline (хотя допустимо).
Теперь про дырявые цитаты (fried quotations). Дырявые цитаты начинаются с '[
Кладём в стэк 1, затем 2, затем дырявую цитату '[ _ + _ ] и что мы видим в стэке?
[ 1 + 2 ]

 
 
 
 Re: Язык Factor
Сообщение25.05.2020, 20:43 
А если сделать Factor с типами и добавить индуктивные и зависимые типы, не заменит ли это Агду?

 
 
 
 Re: Язык Factor
Сообщение25.05.2020, 23:06 
Я бы подумал, что в этом случае разница будет не сильно более чем синтаксической. Если мы берём систему типов из какого-то языка почти полностью, то это обычно требует и рантайм подстроить соответствующе, и семантику конструкций языка дополнить, если изначально она хитрые типы не поддерживала. Конечно, разнообразие возможных идей останется, но от конкретно языка с именем Factor ничего кроме конкатенативного синтаксиса не останется (притом ещё и не синтаксиса всего; я копал в этом направлении и пришёл к выводу, что некоторые конструкции — типа например определений типоклассов или аннотирования типов к значениям по части синтаксиса самих типов — в конкатенативном оформлении как будто нечитаемы; да и вообще никто не говорил, что синтаксис определений в хорошем языке должен что-то общее иметь с синтаксисом выражений).

 
 
 
 Re: Язык Factor
Сообщение04.06.2020, 16:32 
Обнаружил в Факторе обёртку llvm! Не устаёт удивлять. Сейчас напишу компилятор на Факторе с Фактора в llvm. И типов всяких развесистых добавлю, как в Агде.

 
 
 [ Сообщений: 32 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group