Комментарии 24
Читали "Алгоритмические трюки для программистов" (Hacker’s Delight) Генри Уоррена-младшего? Там описан и этот "трюк", и многие другие. Например, как заменить целочисленное деление умножением и сдвигом. В те времена подобные "трюки" давали неплохую прибавку производительности.
Сам в своё время был фанатом форта. Увы, его беда что он абсолютно не защищен. В нём всё что есть, это ячейка памяти. Как на ассемблере. Что приводит к ошибкам, выявляемым только во время исполнения. Простейший пример - сложить два числа. Если одно из них целое другое с плавающей точкой, компилятор может и не догадаться, что целое нужно привести к формату с плавающей точкой и только потом складывать. Да, всё это можно предусмотреть в компиляторе. Но такой компилятор вряд ли уже поместится в нескольких килобайтах ROM. В нескольких килобайтах будет уже целевая программа, а не форт-система. Была у меня мысль прикрутить к нему статическую типизацию, но увы, руки так и не дошли.
Форт со статической типизацией это постскрипт, и лучше бы его обратно развидеть.
Главная беда форта что он придумывался для очень маленьких систем определённой архитектуры - мир вырос и архитектура эта больше не используется, его модель системы теперь даже для микроконтроллеров не подходит. Но как разминка для мозгов вполне полезен.
Про постскрипт честно говоря только слышал. Подробно что это такое не смотрел. Ну и есть несколько файлов в формате ps. Так что про типизацию в нём не знаю. Моя идея была сделать ОБЯЗАТЕЛЬНОЙ стековую диаграмму при определении каждого слова. Сейчас это просто необязательный (хотя и желательный) комментарий. Тогда компилятор на каждом шаге определения сможет отслеживать состояние стека, предотвращая ошибки типизации. Плюс появляются интересные плюшки. Например сложить любые два числа теперь можно одним единственным словом + , а нужный вариант (add, dadd, fadd и т.д.), компилятор найдёт сам. И можно реализовать поддержу на уровне IDE. Из недостатков - некоторые распространенные слова окажутся запрещёнными. Например ?DUP (если не равно нулю, то DUP иначе пропустить), т.к. состояние стека во время компиляции после него неизвестно.
Главная беда форта что он придумывался для очень маленьких систем определённой архитектуры - мир вырос и архитектура эта больше не используется, его модель системы теперь даже для микроконтроллеров не подходит.
Да я бы так не сказал. В конце концов всё упирается в компилятор, который необязательно должен быть простым и умещаться в несколько килобайт. Форт часто упрекают в излишней "косвенности". Он предпочитает короткие определения и вызывает множество подпрограмм, прежде чем доберется до делающего что-то кода. Но простые и распространенные слова( DUP, SWAP, + и т.п.) можно просто инлайнить. Хитрые манипуляции со стеком выкидывать, перекладывая всё на регистры. Данные при этом крутятся воуруг стека, а значит по-идее неплохо должны дружить с кешами. Думается код в итоге должен получаться не хуже чем на оптимизированном С. Высокоуровневую часть компилятор можно писать на чем угодно. А бекенд к конкретному микроконтроллеру прикручивать уже отдельно (хотя бы через тот же форт в конце концов). Получится что-то типа LLVM, но только для форта. Если кому-то из фортеров идея интересна, можем совместными усилиями попытаться реализовать.
я делал именно такой оптимизирующий компилятор в 96м году, под 80286 архитектуру, то что тогда было доступно. Собственно на этом и остыл - компилятор удался вполне, производительности программ я добился, с примерами на C посравнивал, но при этом понял что реальные и интересные задачи для меня лежат в другой области, а это получился хоть и навороченный но всётаки велосипед без особого будущего. Код к сожалению не сохранился, давно уж дело было.
Про идею сделать стековую диаграмму обязательной тоже думал, правда уже после, но так и не добрался чтобы попробовать. Но это была бы всетаки еще не типизация, скорее подобие контракта. Для типизации нужно было бы класть к каждому значению в стек еще и идентификатор типа и часто проверять в рантайме, а это убило бы производительность более чем полностью. Почему и вспоминаю постскрипт каждый раз - там именно так и сделали, и получилось невероятно тормознутое нечто. А на этапе компиляции отследить все типы для стека оставаясь в форте наверное невозможно, или же ограничим гибкость и придем либо к java, или к регистровой VM вместо стековой. Sun собственно этим путём и прошел со своим OpenBoot - в 80х у них там форт хорошо поработал в драйверах карточек, опыта они хорошо набрались, и когда возникла идея универсального кроссплатформенного языка для всей экосистемы, форт был на обсуждении, кое-каие материалы по проектам того времени попадались в сети. Ну вот, начали его профессионально улучшать и доулучшались до того что имеем :)
Для типизации нужно было бы класть к каждому значению в стек еще и идентификатор типа и часто проверять в рантайме, а это убило бы производительность более чем полностью.
Да, именно таким я стек себе и представлял. Содержащий пары (тип, значение). На производительность это никак не повлияет, ибо работает это только в форт-системе разработчика. Для целевой платформы компилируется программа либо без форт-системы (из которой стек данных возможно вообще будет выкинут при оптимизации), либо с простой форт-системой, с обычным стеком.
А на этапе компиляции отследить все типы для стека оставаясь в форте наверное невозможно, или же ограничим гибкость и придем либо к java, или к регистровой VM вместо стековой.
Ну стек исполнения с парами (тип, значение) в системе разработчика я представлял себе скорее как вспомогательное средство для отладки, трассировки и т.п. Для компиляции определения, создается отдельный стек компиляции, содержащий только типы, и инициализируемый левой частью стековой диаграммы. И по мере компиляции меняющий своё состояние. В конце состояние этого стека должно совпадать с правой частью диаграммы. Таким образом состояние стека постоянно отслеживается во время компиляции. Из ограничений я сейчас вижу только одно. Слово всегда должно начинаться в одном начальном и заканчиваться в одном конечном состоянии стека (глубина и типы). Например слово ?DUP запрещено, т.к. глубина стека может быть разной, в зависимости от того, нуль или не нуль лежит на стеке в начале исполнения. На самом деле всё немного сложнее. Например такие слова как DUP SWAP + и т.п. явно будут полиморфны и зависеть от типов лежащих на стеке (левая часть стековой диаграммы). Сейчас это делается разными словами для разных типов (например DUP для целого, DDUP для двойного, FDUP для плавающей точки и т.п.). Но т.к. типизация за одно бесплатно даёт нам и полиморфизм, логичнее иметь одно единственное слово DUP для всех типов, для которых эта операция осмысленна, а какая из реализаций будет выбрана, разбирается уже компилятор.
Это очевидное решение. Правда я не совсем понимаю чем ?DUP мешает? Ну надо чуть усложнить описание слов, добавить в него еще указание на возможное отсутствие изменения стека.
Можно предположить и возражение со стороны фортеров - добавление обязательного описания работы со стеком в каждое слово увеличит размер программы. Причем подозреваю значительно.
Да, можно начать с того что класс это DICTIONARY со всеми операторами данного типа, а идентификатор типа это указатель на словарь класса. Быстро приходим к парадигме "всё есть объект", потому что для целочисленных нужен свой словарь а для плавающих свой, с одинаковыми операторами. Продумываем систему выведения и приведения типов, хотим ли мы вообще неявное приведение (рисково и семантически сложно), или оставляем только явное. Далее, для большего удобства предпочитаем работать с переменными, всё равно компилятор их эффективно в VM разворачивает. Подправляем синтаксис, получаем на этом этапе вот: https://github.com/evincarofautumn/kitten/blob/master/examples/fibonacci.ktn
или как минимум вот: https://docs.factorcode.org/content/article-inference.html
Пробуем дальше и понимаем что без явного обращения к стеку можно и совсем обойтись, а заодно уж и от польской нотации отказаться, большинству пользователей всетаки инфиксная привычнее. Да и кривые скобки им визуально как-то понятнее, добавляем их тоже... И вуаля, благодаря Сану нашему ясному солнышку имеем сегодня прямую наследницу ForthVM в каждом смартфоне, но бегут на ней Java, Scala и Kotlin, плюс ещё сколько-то экспериментальных, тот же Factor на ней начинался.
Да, именно таким я стек себе и представлял. Содержащий пары (тип, значение).
У меня вопрос. Можно ли (теоретически) написать такой компилятор, который вычисляет тип каждого значения на стеке и следит за правильным использованием типов?
Я вот подумал, что в "Форт 1+" ))) типизацию нужно привязывать к значениям, которые лежат на стеке. Это позволит и динамические ошибки типизации ловить, и перегрузку слов по типизации ввести.
Кстати, обязательная нотация с типизацией уже придумана в StrongForth.
Мне когда-то попадалась то ли книга, то ли сайт с развёрнутой документацией по применению PostScript и если я правильно помню, то там автор какие-то чудеса творил на этом, казалось бы, "языке разметки". Помню, что орнул, но углубляться не стал - отложил на бесконечное "потом". Видимо, нужно опять находить тот источник. Интересно стало.
да, штука интересная, медленная только и синтаксис вырвиглазный. Самое главное в нём, это то что все что автоматические генераторы и драйверы печати на нём создают, все сгенерированные .ps документы, их дидактически нельзя рассматривать для знакомства в качестве примеров языка, там обычно столько всего наворочено, и обьём в сотни раз больше чем для содержащейся информации требуется. Нужно искать именно человеческие примеры и руководства, они лаконичнее
Вот кстати, если интересно, попалось очень старое руководство 85го года, очень доступно написано, с примерами и обширными комментариями: https://13thmonkey.org/documentation/Postscript/PostscriptBlueBook.pdf
А вот в архиве самих Адобов: https://www.adobe.com/jp/print/postscript/pdfs/PLRM.pdf
Пардон, update: https://habr.com/ru/articles/1104296/comments/#comment_30618938
Какое-то время назад готовил статью для Хабра о функциональном программировании на Forth )) ну что то из разряда ненормальное программирование just for fun о том, как я сделал на Forth стандартный набор функций для обработки списков - инверсия, конкатенация, фильтр, маппинг, свёртка, все это с функциями первого класса, которые можно передавать как аргументы (по сути ссылки на функции) и все такое. Но без тайпчекинга, хотя к некоторым функциям прикрутил своего рода примитивный тайпчекинг.
Там было материала даже не на одну статью а на небольшую серию, но что то потом руки опустились. Ведь теперь каждый может за пять минут себе такой набор функций навайбкодить.
Форт ценили за предельную надёжность
S" ABC" LAST1
и вся "предельная надежность" испарилась.
Это скорее пример плохой "дуракоустойчивоcти". И тут с вами не поспоришь - она у Forth на нуле.
И это приводит к ошибкам. Причем очень неочевидным, и появляющимся только в рантайме. Так что ныне существующую версию форта, для продакшена я бы никому не рекомендовал. Если интересно, написал выше, как это можно подлечить.
Я думаю, ваше утверждение по большей части справедливо относительно парадигмы мэйнстим-программирования: пишешь код, эпизодически тестируешь, когда дописал его до компилируемого состания. Но к программированию в Forth-среде оно менее применимо.
И ещё. Приведу цитату Трэвиса Бимана (разработчика zeptoforth): "Forth by its very nature is not meant to be a fool-proof language but rather is meant to be a language that allows a great amount of freedom to the user overall, and yes, that includes freedom to shoot yourself in the foot."
Так что все мои "возражения" не опровергают ваш главный тезис - "ныне существующую версию форта, для продакшена я бы никому не рекомендовал", а скорее подкрепляют его.
В контексте языков программирования "дуракоустойчивость" это первое что важно для надежности. Но есть конечно и другие особенности языков, которые влияют на надежность и там тоже у Forth все очень плохо.
Например мы обычно ожидаем от языка программирования, что он будет снижать когнитивную нагрузку на программиста. Что программист будет тратить свое время и внимание на то что действительно важно для решаемой задачи. И тут у ассемблеров, в том числе и у Forth, как макроассемблера виртуального стекового процессора, есть значительный недостаток. Они многословны, и заставляют программиста заниматься тем, что прекрасно умеет делать компилятор. Для обычных процессоров это распределение регистров, для стековых - манипуляции со стеком. DUP DUP в LAST1 как пример.
В нашем числе 12 самая правая единичка — третья слева (или вторая справа).
Наоборот или я что-то не понимаю?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Forth: Как найти и отделить самую правую единицу в двоичном числе