Код как данные и гомоиконность

Такие диалекты как Scheme, CL, Closure не обладают ни тем ни другим. Это все козни популяризаторов ФП.

код как данные — это помоему всякие хачкелисты употребляют в качестве аналога first class functions. (тут можно спорить, но впринципе можно и так называть)

гомоиконность — это другое, да читайте википукию.

Гомоиконность — код сам себе AST. Поэтому лиспы гомоиконны, например.

«Код как данные» значит, что в defmacro/define-syntax я имею полный доступ к телу макроса (к коду) и могу его обрабатывать как данные. По большому счёту идея применима к любому языку, где есть макросы, которые могут пользоваться функциями самого языка (например, tcl, ATS).

Гомоиконность - изоморфность синтаксиса и AST. То есть функция должна быть или всегда вначале (lisp, tcl), или всегда в конце (forth), но не где попало в зависимости от функции. Помогает при парсинге. Для лиспов актуально, если писать code-walker'ы, а не просто генераторы кода из DSL'я.

программы не могут манипулировать локальными символами

Это вообще при чем?

Это вообще при чем?

Ну, как бы, локальные символы, это тоже часть кода, я думал (и читал где-то, кажется), что code-as-data - это как раз возможность программы получить полный доступ к исходнику, и, поскольку прога не может «достать» часть исходника, это уже не то?

Закралось подозрение, что эти 2 термина, которые, зачастую употребляются как синонимы, означают, все же, разные вещи.

Естественно. «код как данные» - это наличие в ЯП встроенного типа, который позволяет представлять термы программы, гомоиконность - если ЯП является синтаксически лиспом, фортом или ассемблером.

Например, хачкиль или немерле имеют code as data, но не являются гомоиконными. Форт же не имеет code as data, хотя гомоиконен.

это наличие в ЯП встроенного типа, который позволяет представлять термы программы

И этот тип должен совпадать с типом, в который термы парсит компилятор - ну то есть ЯП должен иметь доступ к соответствующей парсинг-либе компилятора.

если ЯП является синтаксически ... ассемблером

???

RESETA EQU 1
INITA LDA A RESETA
STA A ACIA

сможешь сходу сказать где здесь команды?

Форт же не имеет code as data

Спорное утверждение. Code в Forth — последовательность (или стек). Immediate / postpone к этому стеку доступ имеют на чтение/запись. Словарь тоже можно доопределять через DOES>.

этот тип должен совпадать с типом, в который термы парсит компилятор

Не совпадать, а взаимнооднозначно транслироваться. По крайней мере в CL у современного компилятора внутреннее представление AST гораздо сложнее, чем список (там +лексическое окружение, типы, место в файле), но для целей макропреобразований достаточно списка.

Не совпадать, а взаимнооднозначно транслироваться.

Есть разница?:)

гомоиконность

это то самое голубое лобби в РПЦ?

Есть разница?:)

Когда трактуют как «совпадать», то рождаются такие монстры, как syntax в Scheme или scala.reflect.macros.Context в Scala.

А когда трактуют как «взаимнооднозначно транслироваться» и быть удобными для обработки, то получаем списки в CL, строки в TCL.

Я говорил о языке ассемблера (в узком смысле). То есть машкод, в котором вместо, собственно, кодов стоят мнемоники.

Спорное утверждение. Code в Forth — последовательность (или стек). Immediate / postpone к этому стеку доступ имеют на чтение/запись. Словарь тоже можно доопределять через DOES>.

Какая стандартная структура в форте используется для представления кода форта? Нет такой.

То есть машкод, в котором вместо, собственно, кодов стоят мнемоники.

Так я могу и BASIC обозвать гомоиконным. А что, в классическом BASIC, структура кода всегда «КОМАНДА [ПАРАМЕТР*]», разбивка по строкам... Но, в общем случае, BASIC включает в себя IF, а ассемблер метки и переменные.

Какая стандартная структура в форте используется для представления кода форта

Последовательность слов на стеке, естественно.

что код является first-class сущностью, его можно брать в качестве аргумента и возвращать в качестве значения

Ну теоретически можно предположить такой тип данных, который представляет код в языке без гомоиконности. Но без гомоиконности на практике это будут мегакостыли. Поэтому, обычно, эти термины эквивалентны.

теоретически можно предположить такой тип данных, который представляет код в языке без гомоиконности

scala.reflect.macros.Context

Nemerle с

macro for (init, cond, change, body) {
  <[ 
    $init;
    def loop () {
      if ($cond) { $body; $change; loop() } 
      else () 
    }; 
    loop ()
  ]>
}

for (i = 0, i < n, i = i + 2, a[i] = i)

а ассемблер метки и переменные.

Покажи мне метки и переменные в машкоде x86.

Последовательность слов на стеке, естественно.

Она не является first-class sitizen, то есть программным объектом. Я не могу ей оперировать. Так что не подходит.

Покажи мне метки и переменные в машкоде x86.

гм... ты предлагаешь считать «синтаксисом» последовательность байт? Причём команды разной длины, которая зависит от _значения_ первого (и иногда второго) байта. А все ассемблеры с мнемокодом имеют в синтаксисе метки и переменные. А также конструкции вида «cmp byte [eax + ecx], 0». Можешь для ней прикинуть AST и посмотреть на запись.

Последовательность слов на стеке

Я не могу ей оперировать.

ЧИВО??? В Форте ты наоборот ничем кроме состояния на стеке и состояния словаря не можешь оперировать. Это всё равно что сказать, что в лиспе список не «first-class sitizen» (наверное, всё-таки citizen).

Не вижу тут типа данных для работы с кодом. Тупой макрос, т.е. подстановка.

Тупой макрос, т.е. подстановка.

В случае Nemerle, согласен, пример плохой, wiki с документацией у них лежит, а устанавливать мне влом.

Давай на примере Scala:

object identityMacro {
    def impl(c: Context)(annottees: c.Expr[Any]*): c.Expr[Any] = {
    import c.universe._
    val inputs = annottees.map(_.tree).toList
    val (annottee, expandees) = inputs match {
    case (param: ValDef) :: (rest @ (_ :: _)) => (param, rest)
    case (param: TypeDef) :: (rest @ (_ :: _)) => (param, rest)
    case _ => (EmptyTree, inputs)
    }
    println((annottee, expandees))
    val outputs = expandees
    c.Expr[Any](Block(outputs, Literal(Constant(()))))
    }
}

Читает объект, генерирует его же, печатает промежуточные AST.

Ну и что, это же ад и израиль какой-то. При том что данный пример не делает никакой реальной работы.

А можешь запостить такую штуку: принимает кусок кода, заменяет все вызовы функции вида foo(a,b,c) на bar(a+b,a-c). Ну чтобы оценить, так сказать масштаб геморроя.

def recmatch(valdef: c.Expr[Any]): c.Expr[Any] = {
  valdef match
    { case <[ foo(a,b,c) ]> => <[ bar(a+b,a+c) ]>
      case List(vals) => map recmatch vals  
    }
}

def changeMacro(c: Context)(s: c.Expr[Any]) : c.Expr[Any] = {
  import c.universe._
  val value = s.tree match 
    {case Block(List(valdef),_) => recmatch(valdef) }
  c.Expr(value)
}

Кстати, на Nemerle нашёл документацию (https://github.com/rsdn/nemerle/blob/master/doc/presentation/macros-gpce04/me...). Этот пример будет выглядеть как

rec (e : Expre) : Expr
{
| <[ foo($a,$b,$c) ]> => <[ bar($a+$b,$a+$c) ]>
| <[ ..$exprs ]> => List.Map($exprs, rec)
}

macro changeMacro (e1) {
  def res = rec(e1)
  <[ res ]>
}

Спасибо, всё понятно. А ещё ругают лисп за обилие скобочек.

Кстати, этот код будет перемалывать sin(foo(3,4*cos(a*b),foo(99,sin(x),isOpen(file))) как надо да?

гм... ты предлагаешь считать «синтаксисом» последовательность байт?

Или мнемоников, которые изоморфны.

Причём команды разной длины, которая зависит от _значения_ первого (и иногда второго) байта.

Ну символы тоже, ВНЕЗАПНО могут быть разной длины. Это же никому не мешает.

ЧИВО??? В Форте ты наоборот ничем кроме состояния на стеке и состояния словаря не можешь оперировать.

Нет, не можешь. У тебя нету доступа в форте ни к стеку, ни к состоянию стека. Эти объекты не first-class. А должны быть first-class, понятное дело.

что в лиспе список не «first-class sitizen»

Но это не так. Я могу списки передавать в ф-и, как-то менять, из ф-й возвращать. Стек в форте я не могу передавать и изменять как объект. Вообще наличие стека в форте - это лишь _модель_. Никто тебе вообще не гарантирует что какой-то стек там есть - именно по-этому он и не может быть first-class.

Кстати, этот код будет перемалывать sin(foo(3,4*cos(a*b),foo(99,sin(x),isOpen(file))) как надо

Смотря что понимать под «как надо».

Этот код — полный аналог

(defmacro change (&body body)
  (labels ((rec (body)
             (cond 
               ((eq (car body) 'foo)
                (let ((a (second body))
                      (b (third body))
                      (c (fourth body)))
                    `(bar (+ ,a ,b) (+ ,a ,c))))
               ((listp body) (mapcar #'rec body))
               (t body))))
      (rec body)))                 

У тебя нету доступа в форте ни к стеку, ни к состоянию стека

Почему нету? Я всегда могу скопировать или переместить любое количество элементов из стека или на стек. Также могу узнать количество доступных элементов на стеке. Или что ты понимаешь под «доступом»?

Этот код — полный аналог

Ок. На мой взгляд код на лиспе гораздо более прозрачен.

На мой взгляд код на лиспе гораздо более прозрачен.

Вопрос привычки. На Scala много бойлерплейта из-за типизации и того, что макрос получает на вход не сразу список, а `(block ,@body). На Nemerle, по-моему, читается даже проще. Также как на Scheme:

(define-syntax change
  (syntax-rules 
   [(change (foo a b c)) (bar (+ a b) (+ a c))]
   [(change ((head ...) rest ...)) (((change head) ...)
                                    (change rest) ...)]
   [(change (body ...)) ((change body) ...))]))

Я всегда могу скопировать или переместить любое количество элементов из стека или на стек.

«Элементы стека» - можешь, при этом они только называются элементами стека - ведь, вообще говоря, тебе никто не гарантирует, что этот стек там есть.

Или что ты понимаешь под «доступом»?

first-class. То есть я могу взять и передать в ф-ю стек или что-то с ним сделать. Я этого в форте не могу (ну просто потому, что описание языка не предполагает наличия какого бы то ни было стека).

А как, например, на скале распарсить аналог выражения (+ x ...)?

То есть я могу взять и передать в ф-ю стек или что-то с ним сделать. Я этого в форте не могу

Любой вызов функции передаёт в неё стек. Если хочешь не менять текущий, можешь передать копию стека (скопировать в переменную, передать адрес).

просто потому, что описание языка не предполагает наличия какого бы то ни было стека

Брр, это уже дзен какой-то... «Forth is an imperative stack-based computer programming language and programming environment.» (c) Wikipedia.

И все функции (слова) определены в терминах «состояние стека до», «состояние стека после».

как, например, на скале распарсить аналог выражения (+ x ...)

Именно + там двухаргументный. Если ты про функции с произвольным числом аргументов, то для (foo x ...) -> x

match 
    {case Apply((NewTermName("foo"),List(args)) => args}

Если именно для + (a + b + ... + z), то только рекурсивной проверкой для AST (+ a (+ b (+ c ...))). Сходу я такое не напишу, но алгоритм очевиден — из каждого Apply можно проверить функцию и аргументы, затем рекурсивно проверять дальше.

Брр, это уже дзен какой-то... «Forth is an imperative stack-based computer programming language and programming

Всмысле конкантенативный. Но со стеком это никак не связано. Стек в данном случае просто удобная абстракция для описания семантики.

Любой вызов функции передаёт в неё стек.

Не стек, а объекты на нем лежащие (как я уже сказал - не факт что там есть вообще какой-то стек). Ну и на самом деле ф-и в форте вообще не вызываются (и никуда ничего не передается, понятное дело) - в конкантенативных ЯП композиция вместо аппликации :)

Суть в том, что стек не является первоклассным объектом. Я могу передать элемент из стека - но не могу передать стек. Так же как в обычных аппликативных ЯП - я могу передать лежащий объект на стеке, но не могу сам стек (хотя передачу замыкания, в некотором смысле, можно считать передачей стека)

И все функции (слова) определены в терминах «состояние стека до», «состояние стека после».

Да, но нету никакого способа работать с этим состоянием как с первоклассным объектом. Например у меня есть ф-я dup, которая удваивает объект. Если бы стек был первоклассным объектом я бы мог написать blah-blah dup - и тем самым удвоить стек.

Именно + там двухаргументный.

Ну да. Вот и в том состоит вопрос - в какое дерево раскроется выражение «2+2+2...», например, и как его матчить?

Если именно для + (a + b + ... + z), то только рекурсивной проверкой для AST (+ a (+ b (+ c ...)))

И при этом надо еще учесть лево-право ассоциативность оператора (ведь там может быть и не +, а что-то другое, с другой асоциативностью).

Вот тут сразу и разница между гомоиконным языком и негомоиконным в контексте простоты написания макросов.

Вот тут сразу и разница между гомоиконным языком и негомоиконным в контексте простоты написания макросов.

Если тебе в макросе нужен полноценный code-walker, то да. Но макросов такого класса можно пересчитать по пальцам одной руки. И если уж раз в год приспичило, то можно и потратить лишний день на разбор синтаксиса.

Основная проблема, на самом деле, в том, что в макросе постоянно вылазит представление AST в виде дерева. То есть вижу «<[ x < 10 ]>», думаю «Apply( Select(Ident(newTermName(„x“)), newTermName(»$less"), List(Literal(Constant(10))))". Потому что, если придётся писать match, то надо указывать соответствие именам узлов.

Но, возвращаясь к исходной посылке: если есть доступ к AST и функциям языка из макросов языка, то идея «code as data» работает в полной мере. То, что на Scala менее удобно, чем в Lisp работать со списками и деревьями, не мешает всё-таки с ними работать.

при этом надо еще учесть лево-право ассоциативность оператора

Считай аналогичной задачей для CL/Scheme: сделать сопоставление с (+ (+ a b) c d (+ (+ e f) g) ...). Явным образом написать нельзя, но коллектор + обходчик пишется тривиально.

Если бы стек был первоклассным объектом я бы мог написать blah-blah dup - и тем самым удвоить стек.

Ага. А если бы 2 было первоклассным объектом, то 2 dup возвращало бы 4. :-)

dup добавляет на голову стека новый экземпляр объекта, который был верхним.

То есть, можно сделать save-stack dup и получить на голове стека два адреса, указывающих на сохранённое состояние стека.

Кстати, именно удвоить стек можно так save-stack load-stack load-stack. Или примерно так (c dup):

save-stack 'load-stack body> dup >r >r 

Вообще говоря, не вижу разницы между доступом к стеку в форте и доступом к списку аргументов в лиспе. Список аргументов я тоже не могу передать, не построив из них структуру данных.

Эм, вот это выражение "(change (foo a b c)) (bar (+ a b) (+ a c))" гарантирует, что если что-то из a, b, c - выражение, то оно будет предварительно вычислено и «присвоено» соответствующему идентификатору?

LDA, STA :) Наверное. Это какой-нибудь пик?

Эм, вот это выражение "(change (foo a b c)) (bar (+ a b) (+ a c))" гарантирует, что если что-то из a, b, c - выражение, то оно будет предварительно вычислено и «присвоено» соответствующему идентификатору?

Только не предварительно. Если надо предварительно, то надо делать что-то вроде (change (foo a b c)) (let ((tmp a)) (bar (+ tmp b) (+ tmp c))

Подстановка идёт на уровне узлов дерева. Что слева написано после foo, то справа будет подставлено в шаблон выражения.

LDA, STA :) Наверное. Это какой-нибудь пик

Это моторола. 6800

Почти угадал. Из того, что я про неё видел, набор команд совершенно упоротый.

// мнение на объективность не претендует, именно что «видел»

Если тебе в макросе нужен полноценный code-walker, то да.

Ну какой же кодеволкер? Просто распарсить тривиальную конструкцию, которая встречается повсеместно.

Но, возвращаясь к исходной посылке: если есть доступ к AST и функциям языка из макросов языка, то идея «code as data» работает в полной мере.

Ну в том и дело, что не работает. Какой же он as data, если ты сам выше говоришь - нифига не as? :)

То, что на Scala менее удобно

И в этом как раз смысл. Гомоиконность исключительно потому и нужна, что становится более удобно. А без ее - менее удобно.

Считай аналогичной задачей для CL/Scheme: сделать сопоставление с (+ (+ a b) c d (+ (+ e f) g) ...).

И в чем проблема? Структура АСТ есть и совершенно четко соответствует коду же.

Явным образом написать нельзя

Как так нельзя? Ты же сам паттерн написал.

Ага. А если бы 2 было первоклассным объектом, то 2 dup возвращало бы 4. :-)

С чего вдруг? Еще раз - если мы передали dup объект, то после этого на стеке лежит два таких объекта. Если мы передадим dup стек - то на стеке должно лежать два стека, в итоге. Два объекта.

dup добавляет на голову стека новый экземпляр объекта, который был верхним.

Ну вот я хочу чтобы наверху стека лежал стек и после применения dup так оказалось два одинаковых стека.

Вообще говоря, не вижу разницы между доступом к стеку в форте и доступом к списку аргументов в лиспе. Список аргументов я тоже не могу передать, не построив из них структуру данных.

Можешь. Отличие в том, что можешь и иначе - есть встроенная возможность передавать данные списком. И вообще передавать код списком туда-сюда. С фортом такое не прокатывает, вообще говоря.

Ну и да, еще раз - в форте вообще нету аргументов и ничег оничему не передается. А ф-и не применяются. Аппликации в форте нету.

я хочу чтобы наверху стека лежал стек и после применения dup так оказалось два одинаковых стека

save-stack saved-stack dup

получишь пустой стек с двумя адресами на содержимое до команды

или save-stack load-stack saved-stack dup — стек + две его копии сверху.

Как так нельзя? Ты же сам паттерн написал

Это не паттерн это типа пример. В качестве тестов для паттерна

(+ (+ a b) c (+ d e) f)
(+ a b c (+ d e) f)
(+ (+ a (+ b c)) (+ d e) f)

Сможешь общий паттерн для этих АСТ сделать? Это аналогичная задача тому, что ты просишь на Scala «сделать паттерн для произвольного количества аргументов и произвольного количества операций + между ними»

А если надо полный аналог (+ x ...), то в Scala можно сделать q"(..$x).sum". Будет работать на (a,b,c).sum, (a,b,c,d,e).sum и т.д.

Какой же он as data, если ты сам выше говоришь - нифига не as

синтаксические проблемы несущественны. В лиспе цепочечные вызовы типа foo.a.b.c ужасно выглядят, но это же не значит, что в лиспе нет объектов.