What is a programmable programming language? (2019)

> Paralinguistic symbols

What’s that? I googled and am still confuzled.

So what's the difference between fexprs and macros? Can you give an example that illustrates it?

"Paralinguistic symbols as constituency"

You mean constituents? Or operands?

"Paralinguistic"

I think you mean syncategoremata?

"Iconic forms"

?

"vau calculus"

Interesting. For the interested, see: https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...

I think you will be more successful communicating your ideas if you use less obscure language. Assuming of course that you are actually trying to communicate ideas and not just trying to virtue signal intelligence or education by being intentionally obfuscated.

for Lisp see CLOS & MOP: object-oriented meta-programming in Lisp

https://en.wikipedia.org/wiki/The_Art_of_the_Metaobject_Prot...

The Pharo MOOC os a nice place to start getting familiar with the Smalltalk family. https://mooc.pharo.org/

> … in Smalltalk there is no source code.

Please explain why you think that might be "a good thing". (Assuming you do.)

Please explain what you think are the differences between "source code" and "an in-transit format" that would allow us to distinguish one from the other.

Yes, the first thing I thought of was FORTH.

Most? Which ones can’t you redefine?

The ‘normal’ way to redefine words in forth is a bit of cheating, though. Redefining a word merely introduces a word with a name that shadows that of the old, still existing word.

Words created before the definition still call the old implementation, and, depending on the implementation (a phrase that, I think applies to about any statement about forth) you can still find it when you walk the dictionary and call it.

Smalltalk is missing too, and that’s a bigger omission. When you redefine a function there, it starts getting used everywhere.

I wonder what a blog post written about this 50 years from now will look like. Would it still mention C and lisp? Would readers of said article still mention forth and smalltalk as missing? Also, what reasonably successful languages from the ‘60s/‘70s already are gone from the collective mind?

Being used today to write very popular OSes, I see C still being mentioned, but by then lisp might have fallen into the abyss of history (except for, probably, a few computer historians)

A great language, I cut some of my programming teeth with GraFORTH on Apple II in 1982/1983 in high school. I wish I still had some of my old floppy disks. I did some floating-horizon for plotting f(x,y) and some basic animations. A friend and I did some demo programs for a couple of local entrepreneurs (Romel and Ludimar in case you're out there) selling Apple II clones, the MicroEngenho, in Brasília. Our work, displayed at a trade show, made it onto the nightly news.

MicroEngenho: https://www.youtube.com/watch?v=Mu9CsdGHybw

EDIT: YouTube link

I think the usual reservation is that once you start showing how to write macros, it only follows with more questions. What's the syntax? What is quasiquoting? What is an unquote? Are arguments evaluated? Why not? What's code and what's data? How is it that a singly linked list data structure has anything to do with code that's executed?

...at which point it's almost more economical to just read a book about Lisp.

I think showing what instead of how can be instructive and motivating for some readers, but it definitely doesn't satisfy all of them.

I think this happens with a few interesting programming concepts. Haskell has its monads (person learns Haskell, gets excited when they start to grok monads, write a blog post explaining it in terms that make sense to them) and Lisp has macros (person learns Lisp, gets excited by macros, writes a blog post about it in a way that makes sense to them). It's sort of a rite of passage, only reason I don't have a monad blog post is because I made it too long so it sat for ages in my drafts and I lost the motivation to complete it :)

Take a look at Carp https://github.com/carp-lang/Carp

Coalton* is a language that interoperates natively with Common Lisp, and has a type system that exceeds the expressiveness of Haskell 98 (but not modern GHC Haskell).

It compiles to native, highly optimized machine code.

* https://coalton-lang.github.io/

Static typing is antithetical to the spirit of interactive development and a mutable language.

Common lisp is compiled to optimised native code.

CL is often seen as "dynamic" but it's better than that: we compile our code with a keystroke and we instantly get compile-time type warnings and errors. It is not fully statically typed, but it is still way better than say Python. Usually, type checks happen at the functions' boundaries: this expected a int but was given a string, this argument is declared but unused etc. Add in Coalton, and you're approaching a Haskell experience. And that happens in our tight read-eval-print-loop, the feedback is instant. We can also do many things at compile time (macros etc). It's better than one might think.

I do not have much personal experience, but SBCL's type inference is supposed to be decent/comparable to the Franz/Allegro/Lisp Works commercial options. I'm not sure if anyone has done "declare-density needed to achieve xyz perf" cross comparisons or the like.

There is also https://en.wikipedia.org/wiki/Stalin_(Scheme_implementation) which was doing lifetime analysis waaay back in the mid 90s, but I don't think Suskind had a declare system at all in Stalin. So, places where inference did not work were probably just "slow to be fixed by users tweaking code" to make inference better. I think he was mostly his own main user.

Both Coalton & Carp do look interesting. There can be complaints with how "prefix notation" scales to large expressions. Cython is a gradually typed Python, but late noughties ideas in metaprogramming/macros/etc. never quite took off.

There can be an undesirable effect of gradual/optional static types that code starts off "lazy" and then can require surprisingly large efforts to tighten down, especially in team settings. Even with profiling/90-10 heuristic rules, a later dev trying to optimize earlier lazy work can still be 10X, especially if type dynamism was really leaned upon. So, at least having an easy switch to force early/in-development static typing on original authors is likely a good thing (or at least strongly encourage with warnings...).

Shen is an interesting offering in this respect https://shenlanguage.org

Probably doesn't cover the 'optimized native code' part but it obviously could, like many programming languages it is, practically speaking, a one-man show.

Not only is Shen inherently statically-typed (it's not annotations over a dynamic core language) but the type system is based on sequent calculus and is expressive and powerful. It would be nice to see what a Nim-sized community could do with it over five to ten years.

As others hint, you don't need static typing to get optimized native code. For SBCL, you get native code already:

    * (defun adder (x y) (+ x y))
    * (disassemble 'adder)
    ; disassembly for ADDER
    ; Size: 37 bytes. Origin: #x541CEE1B                          ; ADDER
    ; 1B:       498B4510         MOV RAX, [R13+16]                ; thread.binding-stack-pointer
    ; 1F:       488945F8         MOV [RBP-8], RAX
    ; 23:       488BD6           MOV RDX, RSI
    ; 26:       488BFB           MOV RDI, RBX
    ; 29:       FF14250001A052   CALL QWORD PTR [#x52A00100]      ; SB-VM::GENERIC-+
    ; 30:       488B5DE8         MOV RBX, [RBP-24]
    ; 34:       488B75F0         MOV RSI, [RBP-16]
    ; 38:       488BE5           MOV RSP, RBP
    ; 3B:       F8               CLC
    ; 3C:       5D               POP RBP
    ; 3D:       C3               RET
    ; 3E:       CC10             INT3 16                          ; Invalid argument count trap

Because Common Lisp is dynamic, you can redefine adder with more information for the compiler to optimize with (such as types or ability to freely inline). The compiler is part of the runtime (which really ups the programmability of the language too, you can teach SBCL's compiler new optimization rules to output even better assembly). So if you Know What You're Doing, you can get rid of the generic add by declaring the expected argument and return types (e.g. a fixnum) and redefining the function:

    * (declaim (ftype (function (fixnum fixnum) fixnum) adder))
    (ADDER)
    * (defun adder (x y) (+ x y))
    WARNING: redefining COMMON-LISP-USER::ADDER in DEFUN
    ADDER
    * (disassemble 'adder)
    ; disassembly for ADDER
    ; Size: 35 bytes. Origin: #x541CE8DC                          ; ADDER
    ; DC:       498B4510         MOV RAX, [R13+16]                ; thread.binding-stack-pointer
    ; E0:       488945F8         MOV [RBP-8], RAX
    ; E4:       488D1C3E         LEA RBX, [RSI+RDI]
    ; E8:       488BD3           MOV RDX, RBX
    ; EB:       48D1E2           SHL RDX, 1
    ; EE:       700A             JO L0
    ; F0:       488D141B         LEA RDX, [RBX+RBX]
    ; F4:       488BE5           MOV RSP, RBP
    ; F7:       F8               CLC
    ; F8:       5D               POP RBP
    ; F9:       C3               RET
    ; FA: L0:   CC52             INT3 82                          ; OBJECT-NOT-FIXNUM-ERROR
    ; FC:       0E               BYTE #X0E                        ; RBX(s)
    ; FD:       CC10             INT3 16                          ; Invalid argument count trap

Note SBCL still has some safety and debugging bits in there. You can tell it you Really Know What You're Doing, and do so locally so you don't put the rest of your code at risk:

    * (defun adder (x y)
        (declare (optimize (speed 3) (safety 0) (debug 0)))
        (+ x y))
    WARNING: redefining COMMON-LISP-USER::ADDER in DEFUN
    ADDER
    * (disassemble 'adder)
    ; disassembly for ADDER
    ; Size: 9 bytes. Origin: #x541CEAB6                           ; ADDER
    ; 6:       4801FA           ADD RDX, RDI
    ; 9:       488BE5           MOV RSP, RBP
    ; C:       F8               CLC
    ; D:       5D               POP RBP
    ; E:       C3               RET

Because of the use of ftype, SBCL will let you know against certain kinds of errors elsewhere, at compile time:

    * (defun mistake () (adder 5 "5"))
    ; in: DEFUN MISTAKE
    ;     (ADDER 5 "5")
    ; 
    ; caught WARNING:
    ;   Constant "5" conflicts with its asserted type FIXNUM.
    ;   See also:
    ;     The SBCL Manual, Node "Handling of Types"
    ; 
    ; compilation unit finished
    ;   caught 1 WARNING condition
    MISTAKE

    * (defun mistake2 () (adder 5 (subseq "555" 0 1)))
    ; in: DEFUN MISTAKE2
    ;     (ADDER 5 (SUBSEQ "555" 0 1))
    ; 
    ; caught WARNING:
    ;   Derived type of (SB-KERNEL:VECTOR-SUBSEQ* SB-C::SEQ SB-C::START SB-C::END) is
    ;     (VALUES (SIMPLE-ARRAY CHARACTER (1)) &OPTIONAL),
    ;   conflicting with its asserted type
    ;     FIXNUM.
    ...

(You would normally see these as you go as you send forms or whole files/buffers to the REPL from your editor, but you can also hook up a sort of 'linting' tool to catch them earlier, or at least fail CI jobs. I use vim rather than emacs and can detect such issues at file save-time; with some work on the underlying tooling it would be possible to detect them when leaving insert mode or switching buffers.)

Of course, because Lisp is dynamic, these are just "warnings" because you can always just redefine (and recompile) these things to fix issues without having to restart your program, or recompile the whole system yet again. And when you leave debugging on or even increase its priority during development, you get an experience in iterative creation unmatched by anything else.

Same here. The advantage is that it works in any language.

Old lisp makers rule was "macro is like lambda, but with one extra eval in the original environment".

In other words: if your function is able to produce (+ 1 2), same function produces 3, when used as macro.

Sometimes you're writing code, and you want to be able to express an idea that your language does not elegantly support. But you know how to express the idea, but it takes a lot of boilerplate, or is just a massive nuisance to write.

Metaprogramming allows you to write a function that generates the boilerplate, and transparently use that function as if it's a brand new keyword in your programming language. That function in metaprogramming circles is called a "macro", not to be confused with C macros.

Stated another way: a macro = a function that takes as input the code you want to write, and provides as output code that your programming language can actually execute. (It's like a super miniature compiler.)

For example, let's pretend C is metaprogrammable.

Perhaps I want a new keyword "pfor" which is like "for" but executes the loop in parallel.

    int x[20];
    pfor(i = 0; i < 10; i++) {
        x[2*i] = expensive(2*i);
        x[2*i+1] = expensive(2*i+1);
    }

Here, we assume "expensive" is some really expensive function that maybe might take several seconds to execute, which is why we want to parallelize it.

This "pfor" is just a sort is pseudo code. In reality, you know how we would actually have to write this: make a loop in which we spawn 10 threads, set i to be a thread local variable in each, call a callback function in each thread

    void thread_callback(int i){
        x[2*i] = expensive(2*i);
        x[2*i+1] = expensive(2*i+1);
    }

and join the threads at the end. This would have the equivalent effect as our desired "pfor" keyword.

In a metaprogramming language, we can add this keyword by just telling the compiler what code to generate any time it sees "pfor". We could write something like

    macro pfor(var = init, cond, incr, body...) {
        symbol callback = generate_random_symbol();
        ```
        void $callback(int $var) {
            $...body;
        }
        vector threads;
        for($var = $init; $cond; $incr) {
            threads.push(make_thread($callback, $var));
        }
        for(t in threads)
            join_thread(t);
        ```
    }

The triple ``` starts a template, and the $ escapes a template. We have to generate a fresh symbol for the callback name so that they don't collide when we use "pfor" multiple times.

Now every time we use "pfor", the compiler will look at our homemade code generator function and write out the code for us.

So in effect by telling the compiler how "pfor" can be implemented in more basic code, we've added "pfor" to the language.

This isn't a separate tool however! It's not a pre-processor or anything like that. It's built in to the language (hence why it's a programming language paradigm).

It can mean a few different things, in this case it's about programs that manipulate the program source and produce new programs (or program segments). Think of a code generator that can take a DSL and turn it into some valid (for execution) code:

  for i in 1 to 10 do printf("%d\n", i)

Becomes (through a preprocessor in this hypothetical system) valid C as:

  for(int i = 1; i <= 10; i++) { printf("%d\n", i); }

Now that's not too interesting, but it is a bit (subjective) nicer looping syntax than C's straight syntax. In the Lisp case, macros allow you to take an arbitrary set of values (the parameters to the macro) and produce some other value or values in their place. This could be just executing the code to get a kind of compile time evaluation:

  (hypotehtical-expression-evaluator-macro (complex-computation-that-gets-reused-100-times-but-takes-10-minutes-each-time))

Or it could be more transformative, like Lisp's loop macro that lets you write an Algol-ish loop instead of a lisp-y loop (or using recursion or other approaches):

  (loop for i from 1 to 10 do (print i))

Which gets transformed into some other valid Lisp code (not on my laptop so not in a position to actually show the result).

David Moon's "Moon's Mark Down" is actually a pretty neat case of Lisp meta programming. He defines a macro defdot which will take a name for a particular directive for his markdown syntax and generate all the necessary functions so that things "just work". And when parsing, when a . is found at the start of a line, the correct handler is calculated and called. To add a new directive, you add a new defdot and that macro will create the relevant functions and register the new handler.

http://users.rcn.com/david-moon/MMD/HTML/index.html

http://users.rcn.com/david-moon/MMD/MMD.lisp

> eli5 metaprogramming

Metaprogramming is "programming programming". Consider "programming" as writing a series of steps for a computer to follow. Metaprogramming is writing a series of steps for a computer to follow to write a series of steps for a computer to follow.

When working with LISP, metaprogramming is just a normal way to program things that's built into the language. Rather than writing everything as a linear program as you would in conventional languages, you can write a program that "writes itself" (or modifies parts of itself).

While you could meta-program in many languages (using code generators and whatnot), in LISP this is easy because the programs themselves are written in a way that makes them easy to be manipulated by other parts of the program. This is why you'll see so many parentheses when looking at LISP code. The simplicity of the syntax is also what makes it so powerful.

Metaprogramming is a technique that often results in much shorter programs which can make single programmers very effective. The downside is that the higher level of abstraction (leaving ELI5 zone here, sorry) can make the workings of LISP programs quite opaque to newcomers as things seem a lot like magic. Therefore preserving the metaprogramming advantages in larger teams requires _especially_ good documentation and attention to design.

You write a program that writes part of the program for you.

What aspects of security are you seeking to understand vis-a-vis macros?

Macros are "just" functions whose inputs are S-expressions and outputs are S-expressions, and they are run at compile-time and not run-time. The semantics of the execution of a macro corresponds more or less to the semantics of Lisp itself, which, in a simplified view, can be completely understood in a first course in computer science (as in SICP).

Any statements about correctness of a macro will derive from statements about correctness of code more broadly, for which there's a lot of literature and is an ongoing active and popular field of research.

Any statements about the security implications of a macro will derive from (1) statements about the security of a compiler more generally and (2) statements about code more broadly, both of which have lots of literature, and both of which have active research communities.

I don't know if there are many useful things to frame around security and correctness about macros specifically (without resorting to the above derivations), which is probably why there's no literature that I know of about it.

What do macros have to do with security?

And what do you mean about doing what you mean it to? The semantics of macro expansion are well-defined.

Above the 10loc macro it's also identifying larger scale structure / needs in your logic but make it as invisible as possible in your code, as opposed to verbose indirections. And I believe there are 40+ years of people ensuring macros do what they're supposed to, and discovering all the subtle failures, in many dimensions. You can have OnLisp semi hygienic raw macros, scheme hygienic macro systems, Matthew Flatt siloed macro systems.. same goes for other metaprogrammable languages. I guess same goes for security.

Smaller programs are easier to understand and often you can be sure that they are correct just by looking at them.

Macros allows you to decompose and simplify problems in a way that is impossible with functions. Macros are especially good at removing boilerplate and writing syntactic glue code.

Since macros are programs making sure that they do what you meant them to do you can use similar techniques as you use for other programs: making them small and obvious, testing.

This is a fallacy* that is often repeated. It's like saying that nobody can work together on a Python project because everybody will create their own incompatible pet decorators.

Any reasonably run project will have standards and code review.

I have not, once, in my decade+ career writing Common Lisp professionally, run into a single instance where my peer programmers on a project have painted one another into silly corners due to unfettered use of macros of any ilk. It doesn't happen, because (1) code comes from some manner of requirements and (2) PRs are reviewed. Macros that don't make solutions easier to read and write for the team, not just a programmer are patently rejected.

* I feel this fallacy and others frequently come from people who hear about a relatively obscure feature or superpower of a language and—having never used it—then try to imagine pessimistic or pathological uses of said feature. Unfortunately, the speculation is usually flat-out wrong, and not even adjacent to some truth.

This was my experience with Ruby. The language makes it easy to create DSLs, so lots of libraries are implemented that way. To work on a large project you actually need to learn dozens of different languages. No thanks.

Short answer: Yes, but it's preferred to do something a little easier.

In Common Lisp, it's much easier if you prefix. It would totally be possible to do something like

    [A x y]

to be an array accessor at indexes x and y by defining reader macros for the characters '[' and ']'. And then one could define the reader macro for the character 'ᵀ' so that

    ᵀA

expands to the transpose of A. Then you could write

    [ᵀA x y].

If you didn't like this prefix thing, you could instead be more elaborate with '[' and parse something more complicated with postfix notation.