Implement a Lisp macro system

/prog/, do you know of a tutorial or a paper on implementing a Lisp macro system from scratch? It could be Scheme macros, it could be really simple macros, anything would be helpful.

Strong AI Perl NewConcept Module and June 4th Tiananmen Massacre Remembrance

https://groups.google.com/d/msg/comp.lang.perl.misc/Ob2Z3wnG09M/ItrWoFUKvHQJ

In the porting of Mentifex MindForth into Perl,
the Strong AI sine-qua-non NewConcept module is
a "stub" in your free open-source Perl AI code.

http://ai.neocities.org/AiSteps.html describes
the process of creating a Strong AI not only in
Perl but in any programming language and in any
natural human language relying on Unicode input.

The purpose of the NewConcept module is to aid
in the machine learning of new words in English
and in the formation of mental concepts tagged
associatively by acoustic words and governed by
a linguistic superstructure for logical thinking.

http://mind.sourceforge.net/newcept.html explains
the pre-existing NewConcept module in non-Perl AI.
We still need to code the OldConcept module that
recognizes the input of a previously known idea,
but first we have to develop prerequisite modules
such as AudRecog for the auditory recognition of
keyboard characters standing in for acoustic sound.

We do this Perl AI coding in somber remembrance of
the upcoming June 4th anniversary of the bloody and
still unpunished massacre of innocent young Chinese
students pleading for freedom and democracy in that
not-so-long-ago springtime of youthful aspiration.
We remember the news reports coming in each day as
the happy students built a replica of the American
Statue of Liberty donated by the French to New York.
We saw the students festooning Tiananmen Square with
artwork and handbills breathlessly discussing the
future of China under democracy and self-determination.

Then on June 4th the still-in-power Chinese government
killed the happy young students and left piles of bodies
bleeding to death on the pavement of Tiananmen Square.

When you hold that iPhone to your ear, can you hear
the screams of the students shot down in bloody murder?
We Perl AI coders, mavericks and revolutionaries to the
core, must call for the condemnation and boycot of all
corporations that do greedy bu$ine$$ with the murderous
Chinese government. Why, they can't even run a railroad.

The Chinese government officials make a big show of
calling for the removal of corruption, which to us
Perl coders resolves to the removal and overthrow of
the student-killing Chinese government and the end
to American companies doing bu$ine$$ over dead bodies.

The top Chinese officials not only kill students but
also steal from Chinese society by granting ownership
of Chinese assets to their children and grandchildren.
If Western news media report on the plunder of China
by the killers and their "princeling" families, then
the reporters are banned from the Chinese mainland.

"Let one hundred flowers blossom," let one hundred
American technology workers infiltrate the companies
doing bu$ine$$ with the evil Chinese murderers and
let the illegitimate Chinese government suspect all
Americans working in China as potential subversives
cooperating with the Chinese democratic underground
in furtherance of the overthrow of the government and
the bringing to justice of the murderers of June 4th.

Mentifex
--
http://www.tiananmenuniv.net
http://www.nlg-wiki.org/systems/Mind.Forth
http://aihub.net/artificial-intelligence-lab-projects
https://aa5new.wordpress.com/2015/05/13/mindforth-ist-echte-wissenschaft

input(?) -> process(?) -> output(?)

>>3
The problem is that macros can call functions and functions can call macros. After parse, I don't even have a valid AST, because it's got arbitrary macros that need to be expanded first. So the compiler would first need to find macro definitions (only the toplevel definitions or all of them? Haven't decided yet), then find all functions called in those macro definitions, then try to expand all the macros called in the bodies of those functions, etc etc. Compiling Lisp seems to be a horribly undecidable problem.

For example, how should I handle a situation like this?

(defmacro (mac-1)
(func-1))

(defmacro (mac-2)
(func-2))

(defun (func-1)
(mac-2))

(defun (func-2)
(mac-1))

The tool/concept you need to implement a hygienic macro system is that of a syntactic-closure: ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1049.pdf

>>5
Very nice, thank you. Will definitely try to use those. But syntactic closures do not address the halting problem. Should I just set up a maximum depth of recursion for macroexpansion, and crash whenever it's exceeded by recursive macros?

>>4
When you encounter a defmacro, add the macro definition to the table of defined macros. When parsing forms, check if the first symbol is a symbol for a macro that has been defined so far. You cannot use a macro if it's defmacro has not yet been processed.

A lisp file is not read. It is not a list of function definitions. It's a sequence of lisp commands that are run as if they were typed at the read eval print loop, except there isn't an implicit print. You don't run through a series of function definitions. You execute commands, some of which define functions, others define macros, and some define classes. Others may change a global variable or use an if statement to determine how a function should be defined.

Lisp sources are not files meant for examination and traversal. They contain code which is run. Code is interpreted and expanded using the state of the lisp environment. Functions and macros are defined by adding entries in tables in the environment. The semantics of a lisp program are best understood by looking at the state of the lisp environment after it has been loaded, not the text that generated the state.

>>6
Why are you trying to halfass a solution to an undecidable problem?

>>6
the halting problem is no problem

yes the macro system is turing complete

just expand the macros though..

if the programmer writes a macro that expands forever then the compiler will run out of memory and crash, no problem.

Don't try to limit expansion with a recursion depth or anything. that could break some valid macros

If the programmer writes a macro that doesn't terminate, she can hit control-c during compilation to enter the debugger and get a stack trace to see where compilation is. Then she can fix her non-terminating macro.

>>10

she
her

Women don't program. Go back to your SJW sites, bitch.

>>7
Well, that's very pathetic, I don't want my Lisp to be victim of "can't use before define" disease. Even Haskell is smarter than that. Probably gonna do several passes through the source:

1) get all toplevel defmacros
2) expand all toplevel macro calls to see if they define any macros
3) recursively descend into all code-paths, adding locally-defined macros to the environment from (1) and (2) and imported packages, and expanding shit.

>>12
But you'll have to report a compile error for

(defmacro foo () (bar))
(defmacro bar () (foo))

anyways. You may as well force the programmer to order them.

>>13
But why should I report a compile error for

(defmacro foo () (bar))
(defmacro bar () '(format t "hax my anus"))

?

>>13
this isn't an error. you should support it.

>>11
Have you read your SICP today?

>>14
I concede it would be nice to be able to do that in most cases. But unmanaged cyclic dependencies can become a real pain. Imagine 5k of code with unordered dependencies. You edit it and a cyclic dependency appears. You fix it, but your change causes 30 other cyclic dependencies to appear. If you don't stay on top of the dependency graph, it can become unmanageable. A way to organize it is to just keep it topologically ordered to begin with. Use-before definition works best when cyclic dependence isn't a problem.

>>17
Well, full-scale languages do support mutually recursive definitions, e.g. OCaml via let rec. You're saying it's hard as hell to do and I shouldn't bother for my toy language?

>>18
Functions and macros are two different things. When you see a function call while compiling code, you don't need to know what the function is at compile time (unless you want to inline). You just need to know that the name refers to a function, and you can give it the right address to jump to later. But when you encounter a macro during compilation, you need to know what the macro is, or you can't continue compilation. Your only choice is to delay compilation of the function until you know the definition of the macro. So it's hard. You could try to solve the problem, and it is solvable to an extent, but you will have to report errors for macros that attempt to use each other cyclically.

you guys are making this a lot more complex than it needs to be

OP specified lisp though ^^

The problem is that macros can call functions and functions can call macros

are you sure your macro's aren't just functions?

Once upon a time, long ago, there was a company of Lisp programmers. It was so long ago, in fact, that Lisp had no macros. Anything that couldn't be defined with a function or done with a special operator had to be written in full every time, which was rather a drag. Unfortunately, the programmers in this company--though brilliant--were also quite lazy. Often in the middle of their programs--when the tedium of writing a bunch of code got to be too much--they would instead write a note describing the code they needed to write at that place in the program. Even more unfortunately, because they were lazy, the programmers also hated to go back and actually write the code described by the notes. Soon the company had a big stack of programs that nobody could run because they were full of notes about code that still needed to be written.

In desperation, the big bosses hired a junior programmer, Mac, whose job was to find the notes, write the required code, and insert it into the program in place of the notes. Mac never ran the programs--they weren't done yet, of course, so he couldn't. But even if they had been completed, Mac wouldn't have known what inputs to feed them. So he just wrote his code based on the contents of the notes and sent it back to the original programmer.

With Mac's help, all the programs were soon completed, and the company made a ton of money selling them--so much money that the company could double the size of its programming staff. But for some reason no one thought to hire anyone to help Mac; soon he was single- handedly assisting several dozen programmers. To avoid spending all his time searching for notes in source code, Mac made a small modification to the compiler the programmers used. Thereafter, whenever the compiler hit a note, it would e-mail him the note and wait for him to e-mail back the replacement code. Unfortunately, even with this change, Mac had a hard time keeping up with the programmers. He worked as carefully as he could, but sometimes-- especially when the notes weren't clear--he would make mistakes.

The programmers noticed, however, that the more precisely they wrote their notes, the more likely it was that Mac would send back correct code. One day, one of the programmers, having a hard time describing in words the code he wanted, included in one of his notes a Lisp program that would generate the code he wanted. That was fine by Mac; he just ran the program and sent the result to the compiler.

The next innovation came when a programmer put a note at the top of one of his programs containing a function definition and a comment that said, "Mac, don't write any code here, but keep this function for later; I'm going to use it in some of my other notes." Other notes in the same program said things such as, "Mac, replace this note with the result of running that other function with the symbols x and y as arguments."

This technique caught on so quickly that within a few days, most programs contained dozens of notes defining functions that were only used by code in other notes. To make it easy for Mac to pick out the notes containing only definitions that didn't require any immediate response, the programmers tagged them with the standard preface: "Definition for Mac, Read Only." This--as the programmers were still quite lazy--was quickly shortened to "DEF. MAC. R/O" and then "DEFMACRO."

Pretty soon, there was no actual English left in the notes for Mac. All he did all day was read and respond to e-mails from the compiler containing DEFMACRO notes and calls to the functions defined in the DEFMACROs. Since the Lisp programs in the notes did all the real work, keeping up with the e-mails was no problem. Mac suddenly had a lot of time on his hands and would sit in his office daydreaming about white-sand beaches, clear blue ocean water, and drinks with little paper umbrellas in them.

Several months later the programmers realized nobody had seen Mac for quite some time. When they went to his office, they found a thin layer of dust over everything, a desk littered with travel brochures for various tropical locations, and the computer off. But the compiler still worked--how could it be? It turned out Mac had made one last change to the compiler: instead of e-mailing notes to Mac, the compiler now saved the functions defined by DEFMACRO notes and ran them when called for by the other notes. The programmers decided there was no reason to tell the big bosses Mac wasn't coming to the office anymore. So to this day, Mac draws a salary and from time to time sends the programmers a postcard from one tropical locale or another.

- http://www.gigamonkeys.com/book/macros-defining-your-own.html

What is it about these that make me feel so warm and fuzzy?

[Macro]

defmacro name lambda-list [[ {declaration}* | doc-string ]] {form}*

defmacro is a macro-defining macro that arranges to decompose the macro-call form in an elegant and useful way. defmacro has essentially the same syntax as defun: name is the symbol whose macro definition we are creating, lambda-list is similar in form to a lambda-list, and the forms constitute the body of the expander function. The defmacro construct arranges to install this expander function, as the global macro definition of name.

Any sufficiently complicated defmacro contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

>>19
A macro is a function from s-exp to s-exp that is run during compilation. The only difference is that mutually recursive functions crash at runtime, while macros crash at macroexpansion time.

Bumping good thread.

>>4

macros can call functions

Function calls only happen at runtime.

>>28
You've never used Lisp, have you?

>>29
I don't see what difference that makes.

>>30
That much is obvious.

>>27
This thread turned to shit after >>24.

>>4

The problem is that macros can call functions and functions can call macros. After parse, I don't even have a valid AST, because it's got arbitrary macros that need to be expanded first

Common Lisp doesn't solve it in any way. Just require explicitly stating what macros should be compiled before the module compilation. Scheme just separates compilation into modules.

>>30
It's that function calls can happen at macroexpansion time, too. In fact, it's the only way to implement recursive macros.

(defmacro hello-worldize (body)
(a-function body))

(defun a-function (sexp)
(list
'progn
'(format t "Hello /prague/!~%")
sexp))

(hello-worldize (format t "Will you hax my anus?~%"))

>>33
The Scheme solution is probably the sanest one, I'll take it, thanks.

>>34

The Scheme solution is probably the sanest one, I'll take it, thanks.

It is not always convenient to separate stuff into several modules, which usually reside in different files.

>>34
It's easier to just order your definitions. The dependence between functions and macros intermix a lot. There isn't a clear separation into 2 or 3 modules. It's more like 10 or 13. My code looks like

(defun ...)
(defun ...)
(defmacro ...) ;; These macros use the functions above
(defmacro ...)

(defun ...) ;; These functions use the two macros above
(defun ...)
(defun ...)
(defun ...)
(defmacro ...) ;; These macros use everything defined above
(defmacro ...)

And so on. My programs alternate like this ten times on average.

>>26
Macros are invoked at compile time. But you can't invoke a macro until it's been defined, and all the functions it calls have been defined. You can't define a macro or a function until you macroexpand its definition. During macro expansion of a body, you may have to invoke the macro you are trying to define.

>>33
What if you want to use your functions inside of your macro?