1. Куча / Говнокод #23660

    0

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    Alg Root;
    arg x, y;
    	Root = getRoot(x, y, 1);
    end;
    
    Sub getRoot;
    arg x, y, r;
    	if Power(r, x) < y then
    		getRoot = getRoot(x, y, r + 1);
    	else
    		if Power(r, x) = y then
    			getRoot = r;
    		else
    			getRoot = r - 1;
    		end;
    	end;
    end;
    
    Sub Power;
    arg x, y;
    	if 0 < y then
    		Power = x * Power(x, y - 1);
    	else
    		Power = 1;
    	end;
    end;

    Написал напитоне простой интерпретатор функционального языка из учебника по теоретическим основам информатики, давайте обсудим
    https://hastebin.com/ocadegapuv.py

    сам учебник, в котором описывается язык и семантика (глава про функциональные программы)
    http://www.ict.edu.ru/ft/003627/lect1.pdf

    В оп-коде пример программы, которую ему можно скормить
    (вычисляет целую часть корня степени x из числа y).

    Подскажите, для начала, как распознать и развернуть в цикл хвостовую рекурсию.
    И если кто напитоне работает, этот код вообще котируется, или есть явное палево?

    Запостил: vistefan, 18 Января 2018

    Комментарии (53) RSS

    • СЕО: #python #напитон #функциональщина #лаба
      Ответить
    • похоже на поцкаль
      Ответить
    • > Подскажите, для начала, как распознать и развернуть в цикл хвостовую рекурсию.

      сам так далеко не заходил (лень). и твой код не читал (TL;DR).

      на практике. сначала строится AST. AST для интертрепации можно использовать, но оно слегка рекурсивное и поэтому слегка неудобно.

      поэтому часто/типично из AST делается линейное плоское представление: часто те же самые AST ноды, но списком вместо дерева + jump/goto & return для управление контролем.

      теперь, когда у тебя есть плоский список нодов (часто называемых BB - basic block) для исполнения, можно начинать делать и оптимизации. tail recursion - это когда у тебя вызов самое себя, с последующим ретурном. вместа ретурна - впиливаешь goto на начало списка нодов aka начало функции.
      Ответить
      • > поэтому часто/типично из AST делается линейное плоское представление: часто те же самые AST ноды, но списком вместо дерева + jump/goto & return для управление контролем.

        к слову, самый простой/убогий способ постоения плоского представления, это tracing: почти как бы интерпретируешь код рекурсивно, но заходишь во все бранчи нодов, и вместо исполнения этих нодов, ты их складываешь в список. но нужно будет еще и гото генерировать, при выходе из рекурсии, на конец родительского(?) нода.

        ЗЫ я пошёл пиво. ждите бормандов и комманду функциональщиков - они вам лучше/больше расскажут.
        Ответить
        • Когда развернешь дерево в линию, появится новая проблема -- области видимости. Язык функциональный, функции чистыми должны быть, надо следить, что ты им разрешаешь. Так что понадобится стек областей видимости, но его, тоже можно сделать "плоским" (зависящим от размера доступной памяти, а не размера системного стека). Это я, конечно, попробую.

          Вообще вышло смешно, учебник 2003-го года, я только написал интерпретаторы для языка с метками и функционального языка, как узнал, что пару месяцев назад вышло второе издание книги, где всё поменялось.
          Ответить
          • > Когда развернешь дерево в линию, появится новая проблема -- области видимости

            Так ты проверяй области видимости и строй окружение заранее, пока AST есть.
            Ответить
            • Вот этого я не понял, расскажи подробнее.

              Мне сразу всю "память" исполняемой программы создать, со всеми переменными, для каждой функции, а потом при разворачивании дерева в линию запомнить, какая функция какой области соответствует?

              Вряд ли ты это имел ввиду, тогда рекурсию не получится сделать, функция сама на себя сайд-эффектить будет.
              Ответить
              • > какая функция какой области соответствует?

                Что-то я ничего не понимаю. Область видимости нужна только для компилятора, при исполнении ничего проверять уже не надо.

                Под все переменные функции можно вообще один список выделить (назовём его VARS). Во время прохода по дереву
                для каждого объявления переменной (x) можно добавлять новую запись в VARS (n = len(VARS) + 1),
                (x = 5) превращать в (VARS[n] = 5)
                (y = x + z) превращать в (VARS[i] = VARS[n] + VARS[j]).

                Для проверки областей видимости таскаешь стек мап-скопов, при входе в нод с объявлениями переменных добавляешь новую мапу в стек, при выходе — выкидываешь мапу.

                После прохода все имена переменных будут заменены индексами в VARS. Никаких "областей видимости" уже не будет, всё было проверено при обходе AST. Этот VARS можно на стеке разместить при желании.

                Если захочется нормальные замыкания сделать, модель надо усложнять.
                Ответить
                • Точно, спасибо.
                  Ответить
                • > Если захочется нормальные замыкания сделать, модель надо усложнять.

                  отделение "переменной" от "значения переменной" + правильные syntax/run-time контексты + GC. (для простоты от синтакс контекстов можно отказатся.) давно руки чешутся попробовать поковырять. но лень, потому что для полноты надо гц прикручивать, что бы контекст и его содержимое освобождать.
                  Ответить
                  • > гц
                    Ну сделай с подсчетом ссылок.
                    Ответить
                    • да, ты прав. для тривиальных случаев (>95% практически) этого должно хватить.

                      у меня ассоциация с гц это графы. а графы я не люблю.
                      Ответить
                    • к слову, у кого есть какие исторические реализации лиспа (из 60х или 70х)?

                      интересно как они тогда гц делали.
                      Ответить
                      • > интересно как они тогда гц делали

                        сегфолтились, когда память кончалась
                        Ответить
    • посмотрел в сырцы.

      учись писать FSMы, или пользуйся yacc/bison/этц - потому что что-то путное сделать будет и нудно и трудно и много писанины.

      для питона какие-то либы парсеры то же есть.
      Ответить
      • > учись писать FSMы

        Я, можно сказать, с этой целью и взялся за интерпретатор. А как их писать? Кучу кейсов я написал, что-то не очень. Наверное лучше делать массив токенов для каждой существующей в языке структуры и проверять, не выпадает ли из него код.

        Расскажите, чуваки, как кодят конечные автоматы на С обычно?
        Ответить
        • Каждый токен - регулярное выражение.
          Каждая регулярка - детерминированный конечный автомат.
          Все ДКА для токенов собираются в один "пучок", минимизируются и приводятся к недетерминированному конечному автомату.
          Этот НКА и работает лексическим анализатором. По сути, он ищет самый длинный встретившийся токен, применяя все регулярки разом.
          Делать это руками - то еще удовольствие; если нет академического интереса - лучше взять готовый инструмент, в противном случае придется спать в обнимку с книгой дракона. Как мне кажется, никакой источник информации лучше не расскажет.
          В общем, удачи :) Да пребудут с тобой анал, минет, кордебалет.
          Ответить
          • > приводится к недетерминированному
            Как из ДКА получается НКА, и как он вообще лексический анализ делает, если он недетерминированный, не пойму?

            > если нет академического интереса
            Ох как есть

            > книга дракона
            Это про LLVM что-то? Линкани.
            Ответить
            • https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/
              Ответить
            • https://ru.m.wikipedia.org/wiki/Компиляторы:_принципы,_технологии_и_инст рументы
              Это книга про построение компилятора, от начала до конца. Первых глав хватит, чтобы построить простенький интерпретатор.

              Различие ДКА и НКА в том, что первый может находиться в нескольких состояниях, а второй - в одном.
              Входной поток подает автомату символ - он переходит в новое состояние. Дошел до конечного состояния - сгенерировал токен, сбросился до начального состояния.

              Лучше скачай книгу, там есть ответы на твои вопросы с примерами. Я уже не особо много помню, да и не описать все это в комментариях.
              Ответить
              • > Различие ДКА и НКА в том, что первый может находиться в нескольких состояниях, а второй - в одном.

                А ты их не перепутал? Наоборот, детерминированный -- в одном.
                Ответить
                • Да, с терминологией могу попутать за давностью лет, извиняй.
                  Ответить
                  • Ничего, Хомячок, всё равно ты замечательный тип.
                    Ответить
              • > чтобы построить простенький интерпретатор
                Хех, надо всё-таки прочитать эту книгу...

                Недавно хотел по-быстрому выдрать данные из скриптов factorio, а получился кривой интерпретатор lua с вот таким говнищем вместо парсера:
                if tokens.next_is('return'):
                    tokens.get_token()
                    if stop_at:
                        if tokens.peek_token()[0] in stop_at:
                            return Return([])
                    args = []
                    while True:
                        args.append(parse_expression(tokens))
                        if tokens.has_tokens() and tokens.next_is(','):
                            tokens.get_token()
                            continue
                        break
                    return Return(args)
                Ответить
                • Это на чем?
                  Ответить
                  • пистон, очевидно
                    Ответить
                    • Это понятно. Модуль какой?
                      Ответить
                      • __main__, очевидно.
                        Ответить
                        • __petrosyan__.py
                          Ответить
                          • Ну я имел ввиду, что самописное всё, скорее всего. А чо там такого-то, class Tokens() на массиве с четырьмя методами?
                            Ответить
                      • Модуль re.

                        Токены регулярками откусываются, AST из них собирается вон теми говноифами и потом интерпретируется через метод execute прикрученный прямо к нодам AST...

                        Хуяк-хуяк и распарсен.
                        Ответить
                        • З.Ы. Кто там писал, что исполнять прямо по AST неудобно? :3
                          Ответить
                          • Я даже не пробовал что-то другое исполнять.
                            Ответить
                          • я.

                            по аст исполнение медленее, чем по плоскому списку.

                            на плоском списке делается как минимум гото оптимизация - в то время как просто обход аст, и скипание чисто синтаксических конструкций, тоже время отъедает.

                            или тупо: в два раза меньше нодов обходить - в два раза быстрее интертрепация. :-)

                            ЗЫ и это уже не говоря об обработке ошибок где в глубине аст.
                            Ответить
                            • Про пирфоманс соглашусь.

                              > обработке ошибок где в глубине аст
                              В обработчиках нод возвращаешь результат/ошибку. На интересных нодах (вызовы функций) пополняешь бектрейс ошибки инфой о координатах ноды в исходнике... Терпимо, в принципе.

                              З.Ы. Ну и при прямом исполнении AST goto довольно сложно реализовать, в отличие от структурных while/for/if (х.з., минус ли это).
                              Ответить
                              • на аст очень сложно оптимизировать. как раз потому что там все структурно. оптимизация на аст это трансформация дерева, что есть отдельный геморой.
                                Ответить
        • > Кучу кейсов я написал, что-то не очень.

          поэтому народ и чинит уже 3 десятилетия yacc/bison. туториалов там завались.

          > Наверное лучше делать массив токенов для каждой существующей в языке структуры и проверять, не выпадает ли из него код.

          это проблему не решает - тебе все равно придется писать кучи херни.

          самый читабельный вариант который видел это калейдоскоп дема из llvm: https://llvm.org/docs/tutorial/LangImpl01.html

          я лично для домашних мелких поделок продолжаю клепать парсеры FSMами с switch/case-ами, потому что там все фичи "доступны", как типа контекстно-зависимая токенизация. расширять их и переписывать мука - но это можно делать в code-monkey режиме. (парсер чего-то tcl/лиспо-образного - https://github.com/Kervius/ktr/blob/fork-minsk-001/Minsk/min.cc#L618 )

          народ хвалит antlr - но у меня до него так руки и не дошли.
          Ответить
          • > yacc, bison, antlr
            Генераторы парсеров у меня как-то не зашли. С парсер-комбинаторами, практика показывает, возни на порядок меньше. Да, DSL не такой DSистый, но зато затрат на интеграцию с остальным кодом нет.
            Ответить
            • я так понимаю, что народ с yacc/bison как раз поэтому и страдает, что он "облегчает" интеграцию с кодом: в {} ты пишешь вполне обычный код - твой код.

              бизону в 3й версии вроде бы прикрутили поддержку крестов: он генерит теперь класс - с вставками твоего кода. и вроде даже с какими-то exception-safe гарантиями. (это теоретически решает мою старую проблему невозможности вернуть ошибку или просто остановится на ошибке - кроме как exit().)

              ЗЫ сам еще не пробовал - https://www.gnu.org/software/bison/manual/html_node/C_002b_002b-Parsers.html#C_002b_002b-Parsers
              надо будет поковырять, потому что само-писаные парсеры мне тоже больше нравятся (их можно отлаживать/этц) но когда дело доходит до расширения языка, то там хоть удавись.
              Ответить
            • Парсер-комбинатор это просто набор отдельных [самописных] парсеров?
              Ответить
              • Это библиотека, которая предоставляет основные примитивы и средства компоновки этих примитивов в произвольно сложные парсеры.
                -- http://book.realworldhaskell.org/read/using-parsec.html
                
                import Text.ParserCombinators.Parsec
                
                csvFile = endBy line eol
                line = sepBy cell (char ',')
                cell = quotedCell <|> many (noneOf ",\n\r")
                
                quotedCell = 
                    do char '"'
                       content <- many quotedChar
                       char '"' <?> "quote at end of cell"
                       return content
                
                quotedChar =
                        noneOf "\""
                    <|> try (string "\"\"" >> return '"')
                
                eol =   try (string "\n\r")
                    <|> try (string "\r\n")
                    <|> string "\n"
                    <|> string "\r"
                    <?> "end of line"
                
                parseCSV :: String -> Either ParseError [[String]]
                parseCSV input = parse csvFile "(unknown)" input
                
                main =
                    do c <- getContents
                       case parse csvFile "(stdin)" c of
                            Left e -> do putStrLn "Error parsing input:"
                                         print e
                            Right r -> mapM_ print r
                Ответить
                • Тогда надо поковырять https://github.com/PhilippeSigaud/Pegged, к примеру. Кстати, на миксинах разумеется.

                  Или побаловаться и написать такое на Свифте.
                  Ответить
                  • > на миксинах
                    на хуиксинах

                    P.S. хаха, а ты похоже хуиксинщик http://govnokod.ru/23641
                    Ответить
                    • Не, просто интересуюсь возможностями и перспективами метапрограммирования, которое в 95% случаев нахер не нужно
                      Ответить
          • Попробуй Boost Spirit. Прикольная штука. Он правда только в LL парсеры может, но в большинстве случаев большего и не надо.
            Ответить
            • > прикольная штука
              Особенно прикольно компилить простенькую грамматику по 30 секунд и искать номер строки с опечаткой в километровой портянке с ошибками...
              Ответить
              • оно не так плохо. я как то давно пример компилировал.

                моя проблема была в том что оно множит бойлер-плейт крестовый (переиспользование кода == тучи мелких функций), и не сильно читабельно по сравнению с тем же yacc/bison (nested syntax highlighting специально для спирита сделать в редакторе будет не тривиально, учитывая что там будет еще крестовый код везде подмешан).

                с другой стороны, если пишешь что-то неправильно, то понять что именно от тебя хочет спирит - какая несовместимость типов - не тривиально. я с какой-то простой модификацией демы пол часа протрахался. другая модификация почему-то вообще игнорировалась. оно там как-то хитрожопо реализовано, потому что (если память не изменяет) сгенереная функция парсера относительно маленькая (и я так хер и понял в чем была моя ошибка).
                Ответить
              • Кто ж читает выхлоп компилятора. С плюсометушнёй нужно действовать примерно так: если добавление строчки кода сломало билд, нужно вернуться к состоянию, когда всё компилилось, добавить половину строчки, далее если билд не сломан, то проблема в другой половине, ну и т.д.
                Ответить
            • Я как-то попробовал spirit, и именно он помог мне понять, что кресты говно, подтолкнул выучить функциональщину, и это в конечном итоге помогло мне завести трактор в евросовок. Действительно прикольная штука.
              Ответить

    Добавить комментарий