Комментарии 36
Интересно. Но не понятно. А как в случаи растущего выражения (цикла) происходит обработка и загрузка дерева?
Загрузка происходит как обычно, выражение символ за символом поступает извне через корень и слева направо укладывается на аппаратное дерево. Мы в этот момент ещё не знаем что выражение растущее.
Когда начинается обработка, дерево начнёт расти: условно говоря, базовый комбинатор 'S' умеет захватывать свободные поддеревья и копировать туда свой (третий) аргумент. Ну и программисту надо позаботиться об условии выхода из цикла, чтобы не было бесконечного роста.
Когда начинается обработка, дерево начнёт расти: условно говоря, базовый комбинатор 'S' умеет захватывать свободные поддеревья и копировать туда свой (третий) аргумент. Ну и программисту надо позаботиться об условии выхода из цикла, чтобы не было бесконечного роста.
НЛО прилетело и опубликовало эту надпись здесь
может и нет, но Вы привели «слабые» аргументы: «Ваши проблемы сконцентрировались вокруг понятия ВЫЧИСЛЕНИЯ, если формулу вычислять, то это будет фон-Неймоновская система(вид сбоку)», а если формулу Доказывать или Упрощать, то может и есть :)
НЛО прилетело и опубликовало эту надпись здесь
«Неразрешимость планировщика графа» — значит только то, что навернуться на Y-комбинаторе можно, «слабость» в том, что это обязательно делать, если можно ограничится редукцией графа, а мапить уже на других архитектурах. А про вычисления — я имел в виду, что не все вычисления сводятся к NP- полным вычислениям, иногда можно решать и O(n) задачи.
НЛО прилетело и опубликовало эту надпись здесь
Это я и сказал ))) вопрос в том, зачем биться «об стену» не решаемых задач??? инженерное искусство состоит в решении тех задач, которые можно решить на текущем технологическом уровне. Например мы не можем на двоичном компьютере представить число Пи, и поделить его на 3 — не можем, но найти приближение — вполне.
Спасибо, посмотрю внимательнее, но по-моему «REDUCERON» это всё-таки не совсем то, «Each G-machine instruction can in turn be translated to a sequence of regular CPU instructions and executed by a PC» то есть, их «графовая память» не самодостаточна.
Понимаю, как неказисто пока всё выглядит, и с какими фундаментальными трудностями придётся иметь дело, но я пока верю в шанс найти подходящую задачку, и сделать под неё решение.
Нету у меня памяти, граф самодостаточен, наружу только корень торчит.
Понимаю, как неказисто пока всё выглядит, и с какими фундаментальными трудностями придётся иметь дело, но я пока верю в шанс найти подходящую задачку, и сделать под неё решение.
На этом можно было бы закончить, но есть упорные люди, и они столкнулись со следующей проблемой: memory mapping.
Нету у меня памяти, граф самодостаточен, наружу только корень торчит.
1) Почему отказались от двоичных типов (адресное пространство можно былобы разделить; были «машины указателей», для них фон Неймановское «бутылочное горлышко» было не так проблемотично; проблема разреженности могла бы быть уменьшина при отказе от «нумералов», симулировать все типы функционально… очень муторно, и вся эффективность будет потрачена на их симмуляцию)
2) X-комбинатор можно былобы довавить ()
3) где Y-комбинатор будет остановлен (где берете память на сохранение дерева)?
4) многомерность — интересная идея: можно использовать адресное пространство, как код комбинатора: '''s(addr1,addr2,add3) ->S-Base:[...addr1,addr2,add3...]; ''k(addr1,addr2) -> K-Base:[… addr2 ...]; 'i(expression) -> SAA-Base:[… addr-of-sequence-exspression ...]
ах. да:
5) а pi-исчисления не будет? хотя бы в форме Linda
2) X-комбинатор можно былобы довавить ()
3) где Y-комбинатор будет остановлен (где берете память на сохранение дерева)?
4) многомерность — интересная идея: можно использовать адресное пространство, как код комбинатора: '''s(addr1,addr2,add3) ->S-Base:[...addr1,addr2,add3...]; ''k(addr1,addr2) -> K-Base:[… addr2 ...]; 'i(expression) -> SAA-Base:[… addr-of-sequence-exspression ...]
ах. да:
5) а pi-исчисления не будет? хотя бы в форме Linda
1 — Я не отказался, просто двоичный аналог нумералов Чёрча мне пока не по зубам, хотя сделать его определённо можно. (Кстати, если кто-нибудь знает готовые работы по теме, напишите пожалуйста.)
2,5 — Спасибо, посмотрю.
3 — Остановить можно: f(f(f(f...) необязательно вычислять полностью, в какой-то момент f просто игнорирует свой аргумент.
4 — не очень понял.
2,5 — Спасибо, посмотрю.
3 — Остановить можно: f(f(f(f...) необязательно вычислять полностью, в какой-то момент f просто игнорирует свой аргумент.
4 — не очень понял.
1- я думал, что когда CPU получает 'i(...) идет запрос в сопроцессор
3- выше был ворос, куда эти f(f(f...) складываются, и прежде чем игнорить аргумент f(a) в него нужно заглянуть, и ''k(_,_) может быть не первой командой, в результате стек будет рости, а если ''y будет внутри ''y… ой
4- я только предложил, моно не обращать внимания
3- выше был ворос, куда эти f(f(f...) складываются, и прежде чем игнорить аргумент f(a) в него нужно заглянуть, и ''k(_,_) может быть не первой командой, в результате стек будет рости, а если ''y будет внутри ''y… ой
4- я только предложил, моно не обращать внимания
Тоже хотел спросить про pi исчисление. Концепция взаимодействующих процессов через канала мне кажется хорошо ляжет на вашу реализацию.
Так же можно посмотреть на модель акторов.
Обе эти модели выводимы из ламбды, верифицируемы и полны по тьюрингу.
Так же можно посмотреть на модель акторов.
Обе эти модели выводимы из ламбды, верифицируемы и полны по тьюрингу.
У аппаратчиков эта идея называется Dataflow Architecture, ни один десяток лет уже умы будоражит:
ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&queryText=dataflow+architecture
ПЛИС сама по сути является Dataflow-процессором: Массив операционных элементов: LUT'ов, DSP-блоков, Памятей, которые соединяются по заданной программе на Verilog. Актуальный вопрос в том, можно ли придумать удобный язык программирования для такой архитектуры, т.к. Verilog и VHDL в каком-то смысле низкоуровневые ассемблеры. Сейчас актуальными являются попытки компиляции из C/C++ и OpenCL для ПЛИС, т.к. эти языки популярны среди программистов.
ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&queryText=dataflow+architecture
ПЛИС сама по сути является Dataflow-процессором: Массив операционных элементов: LUT'ов, DSP-блоков, Памятей, которые соединяются по заданной программе на Verilog. Актуальный вопрос в том, можно ли придумать удобный язык программирования для такой архитектуры, т.к. Verilog и VHDL в каком-то смысле низкоуровневые ассемблеры. Сейчас актуальными являются попытки компиляции из C/C++ и OpenCL для ПЛИС, т.к. эти языки популярны среди программистов.
По моему представлению, Dataflow это что-то вроде системы конвейеров на заводе, перестройка на лету и движение данных в разных направлениях там не характерны.
Да, похоже на разновидность Dataflow Architecture, мне почему-то вспомнилась transport-triggered architecture и FleetZERO. С другой стороны, автор говорит, что «система работает как клеточный автомат, только не «решеткообразный» а древовидный». Хотелось бы понять, клеточный автомат вообще — это переупрощение железа за счёт переусложнения софта как здесь
en.wikipedia.org/wiki/One_instruction_set_computer
или в придачу к экзотичности программирования ещё и железо будет сложным?
en.wikipedia.org/wiki/One_instruction_set_computer
или в придачу к экзотичности программирования ещё и железо будет сложным?
transport-triggered architecture — возможно, хотя по первому впечатлению там не подразумевается столь полная децентрализация.
FleetZERO -кажется скорее про «самосинхронные схемы» — совсем низкоуровневую асинхронность, без тактового сигнала и триггеров. Но синергия тут возможна, … была бы, выживи проекты :(
У меня в мечтах изучить Chisel HDL и отделить в описании машины уровень сети от логики ноды.
FleetZERO -кажется скорее про «самосинхронные схемы» — совсем низкоуровневую асинхронность, без тактового сигнала и триггеров. Но синергия тут возможна, … была бы, выживи проекты :(
переупрощение железа за счёт переусложнения софтаНу, замысел-то не переусложнять, а использовать другую организацию процесса вычислений, да и железо, реализующее потенциально бесконечную сеть может оказаться весьма не простым.
У меня в мечтах изучить Chisel HDL и отделить в описании машины уровень сети от логики ноды.
Если замысел не переусложнять, то может быть использовать что-то более распространенное, чем Chisel HDL? Скажем те немногие встроенные возможности функционального программирования, которые есть в MATLAB? Может оказаться, что для комбинаторного программирования их хватит
en.wikipedia.org/wiki/Function-level_programming
Кстати, Википедия в статье Компьютер_для_операций_с_функциями пишет, что вычислительная машина для операций с функциями была предложена и разработана Карцевым в 1967 году. Реконфигурировать её на лету вряд ли получится, но сама идея использовать двойную сумму в системе счисления интересна…
en.wikipedia.org/wiki/Function-level_programming
Кстати, Википедия в статье Компьютер_для_операций_с_функциями пишет, что вычислительная машина для операций с функциями была предложена и разработана Карцевым в 1967 году. Реконфигурировать её на лету вряд ли получится, но сама идея использовать двойную сумму в системе счисления интересна…
Если замысел не переусложнять, то может быть использовать что-то более распространенное, чем Chisel HDL?...Chisel для описания аппаратуры самой машины, а не программ для неё.
Компьютер_для_операций_с_функциямиТам я так понимаю, ориентировано на перемножение матриц, это другое.
Там я так понимаю, ориентировано на перемножение матрицДа, в компьютере для военных (функционально-операторная М-9), нужно ожидать алгоритмов DSP, в частности, БПФ. Вы упоминали язык Falgol, интересно какая архитектура была бы оптимальной для него? Кстати, вот совсем свежая попытка применить lambda-подобный язык для проектирования самосинхронных схем
www.delayinsensitive.com/download.html
Компиляция C-кода в HDL не новая идея, реконфигурирование в рантайме поддерживают далеко не все ПЛИС, но тоже бывает.
То, то работает в симуляторе с неограниченными ресурсами бесполезно, если это нельзя запустить на реальной ПЛИС.
Мне лично было бы более понятно и интересно, если бы вы написали обзор существующих решений подобного рода, их недостатки, а затем бы сосредоточились на новизне именно вашего подхода и его преимуществах по сравнению с существующими.
То, то работает в симуляторе с неограниченными ресурсами бесполезно, если это нельзя запустить на реальной ПЛИС.
Мне лично было бы более понятно и интересно, если бы вы написали обзор существующих решений подобного рода, их недостатки, а затем бы сосредоточились на новизне именно вашего подхода и его преимуществах по сравнению с существующими.
Чтобы что-то прошить в ПЛИС даже в рантайм, вы прошивку должны подготовить заранее, я надеюсь сделать возможным как реконфигурирование, так и подготовку прошивки из спецификации на лету.
На ПЛИС не имеет смысла запускать сейчас, но это совсем простая, не оптимизированная версия. По моему мнению, предложенные в статье меры могут существенно изменить ситуацию.
Чукча не читатель, чукча писатель. Обзор решений я не потяну. Могу только повторить, что близкие аналоги (очень простые локально связанные ядра, практически, клеточный автомат, способный выполнять функциональные программы) мне не известны.
На ПЛИС не имеет смысла запускать сейчас, но это совсем простая, не оптимизированная версия. По моему мнению, предложенные в статье меры могут существенно изменить ситуацию.
Один из вариантов не-фон неймановской архитектуры реализованный в кристалле habrahabr.ru/post/226773/
Вы дерево прямо в ПЛИС помещаете? А из внешней памяти не получится?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Не-фон неймановский компьютер на базе комбинаторной логики