Power is a weakness in a programming language, not a strength - some of the most interesting research languages today are not even Turing-complete. It's easy to add expressiveness to a clunky language; it's much harder to add limits to an expressive language that prevent expressing nonsense.
"Expressive power" and "computational power" aren't the same thing.
Turing's original Universal Machine (you know, the moving read/write head over an indefinitely long tape of symbols) is not expressive at all; a simple task like adding two integers on that machine requires a completely arcane, verbose piece of gobbledygook to be prepared on the tape, where you cannot tell at a glance which part of it is the program, and which is the integers to be added. It is less expressive than 4 + 4 in a calculator language that doesn't have loops.
Expressive power is, in its barest essence, the freedom to assign an arbitrary meaning, from some domain, to a new combination of symbols, such that every symbol in that combination refers to some entity in that domain only.
It behooves us to have a general-purpose language with as much expressive power as we can get our hands on.
It is not hard at all to add restrictions in domain languages created inside an expressive language. For instance if you make an x86-64 assembler in Lisp, it will be just as restricted as any other assembler; it will diagnose unrecognized opcodes, bad addressing modes, etc.
> For instance if you make an x86-64 assembler in Lisp, it will be just as restricted as any other assembler; it will diagnose unrecognized opcodes, bad addressing modes, etc.
I've written one such assembler in Common Lisp. It was rather straight-forward and generated nice code. Debugger came practically free.
Lisp is a language for symbolic computing. Values are not so valuable as computations and trees. If the level you're working at is too restrictive you're free to invent a new algebra for symbols at a higher level in terms of the lower-level primitive symbols. It's the same power one gets from manually calculating sums to inventing a language for expressing all sums. How you choose to represent things has great power in your ability to reason about them.
> For instance if you make an x86-64 assembler in Lisp, it will be just as restricted as any other assembler; it will diagnose unrecognized opcodes, bad addressing modes, etc.
But it won't enforce those things at compilation time in the type system, because it doesn't have one. You might have a macro that checks them, but it would be ad-hoc.
Another commenter already said that Common Lisp indeed does have a type system. It's possible to circumvent, but that's Lisp for you.
You can very easily write an assembler in Haskell that doesn't verify any of that stuff statically. Learning to do advanced kinds of static verification with Haskell's type system is actually rather difficult, and usually requires language extensions.
Using a macro that checks those things seems like it could be a very pragmatic way to provide safety. It might also let you verify properties that would be hard to figure out how to verify using only Haskell-style type checking.
Indeed, Haskell programmers often use QuickCheck to do ad-hoc verification of type class laws, for example, since they can't be proven in the type system.
You can write Lisp that is de facto statically typed, and good compilers take advantage of it. If we write (cons a b), that piece of program text has a type, which is a cons. Given (let ((c (cons a b))) ... (car c) ...) the Lisp compiler can generate efficient code to access c, without a run-time type check that c is a cons, based on c inheriting the type from the cons expression, and not being subject to any assignment in its scope. If we regard it as a parametrized type, not knowing what a and b is, it is the expression "for all types x, for all types y, the type of (cons x y) is: cons cell of x and y".
> Learning to do advanced kinds of static verification with Haskell's type system is actually rather difficult
Perhaps. But it benefits greatly from being a consistent way of doing things: everyone does their static verification the same way, because the language supports exactly one way of doing it.
> and usually requires language extensions.
Sometimes. But again at least those extensions are relatively standardized, rather than completely ad-hoc as a macro can be.
> Indeed, Haskell programmers often use QuickCheck to do ad-hoc verification of type class laws, for example, since they can't be proven in the type system.
Yeah, that's one of the reasons I'm excited about Idris. But even in your example, QuickCheck is again a standardized way of doing this.
Well, all you need to do in a macro to provide error checking is to assert or raise a condition when something is wrong. That's pretty standard.
In Haskell land, you can do wonderful things like Servant, the statically verified API server—but that kind of code is very advanced, and written by a shadowy cabal of type level wizards. I think there is less of a standardized way of doing this stuff than one might expect.
I'm not really sure what you mean by "standardized." Common Lisp is an actual ANSI standard... But you seem to be referring to the existence of common practices.
I'm not convinced that the problem you describe is actually a problem, and I'm not convinced that Haskell or Idris will end up being more successful in the mainstream than Lisp.
(I'm a huge fan of Haskell, Agda, and static/dependent typing, for the record.)
> Well, all you need to do in a macro to provide error checking is to assert or raise a condition when something is wrong. That's pretty standard.
Sure, but the conditions that lead you to do that can be arbitrary Turing-complete code. IIRC in unextended Haskell what you can do at type-level is more restricted; certainly you're guided towards a particular way of structuring your constraints. That in turn makes it more practical for other tools to support your constrained sublanguage.
I think the future of programming lies in constrained (BWIM non-Turing-complete) languages and provably correct code. I guess we'll find out.
I didn't respond to that because I don't debate with thinkers who equate "type" with "static type". Not that I don't want to, but I haven't historically found it possible (at least in a productive way).
Common Lisp's type system isn't optional. The language is strongly typed. Type goes away (in a sense) when you add declarations. That is to say, if you tell Lisp that, say, some variable contains a fixnum, then (in code compiled with safety 0) it just believes your declaration, and it's up to you to ensure that it's not a lie (else the behavior is undefined). The type system isn't optional in any other sense.
It's optional for an implementation to provide static checks and optimizations based on type, which is different. "Static type" and "type" are not synonyms.
Common Lisp code is safe by default; you can't use an object of type X as if it were one of type Y.
A spec that says adding a fixnum to a string produces a possibly-runtime error isn't a type system, it's just a particular instance behaviour. Types are by definition associated to terms in a language.
(That isn't to say that that kind of runtime behaviour isn't valuable or doesn't provide (some of) the same functionality as a type system. But it's not what the word "type" means).
> Types are by definition associated to terms in a language.
This is true, within a particular paradigm, which isn't the be-all and end-all of what "type" means in computer science.
All kinds of things are type. For instance, "JPEG file" or "alphanumeric character" are both type terms.
You don't get to dictate to everyone one narrow definition of a term that has an obviously broad applicability in numerous contexts.
If we are discussing Common Lisp, and you want to get properly pedantic about what "type" means, the way you can do that is to look up its definition in the ANSI CL glossary, which says:
"type n. 1. a set of objects, usually with common structure, behavior, or purpose."
Or you can use it in a broader way which is compatible with this concept.
If you insist that it means something else which is not compatible with the glossary definition, and you still want to talk about Lisp, then I'm afraid it's not productive; you are more interested in engaging in a conflict about word semantics: which "camp" gets to "own" the ideologically precious word, such as "type".
Usually how we can resolve that conflict is to split our vocabulary into different words. You can have "type", I don't need it; I will call it this other thing that the CL glossary refers to "genus". Now type can be the property of a syntactic term in a program, and genus refers to sets of objects which have something in common.
I'm mostly interested in genus systems, and type systems in their context (agreement between the type of a program term, and the genus of the run-time thing it operates on).
I don't think Lisp could even be said to have a genus system - to have a "system" for dealing with sets of objects implies having a way to talk about those sets, do set operations (intersection/union/product) etc.
But in any case, any genus-but-not-type system is irrelevant to my original point: that when writing an x86-64 assembler in lisp (as an embedded DSL), any enforcement of restrictions at compile time would have to be expressed as ad-hoc macros, because there is no (language-standard) type system in which to declare them.
If I make an assembler in Lisp, compile it and ship it to you so that you can apply it to your assembly language programs, it wouldn't work so well for me to be diagnosing your assembly language problems in my compile time.
I'd prefer a language where I don't have to write a domain language from scratch and write a program that can enforce its rules at runtime. Rather I'd like to be able to express my domain code in the language itself, so that my users don't have to learn (and I don't have to create) a new language. That requires a consistent way of restricting things at compile time, which is very hard to retrofit - if I ever want to be able to enforce that programs don't do certain things, the language needs to not offer unrestricted access to those things.
If you express your domain code in the language yourself, users still have to learn and understand what you have done.
What you write in a language has its own de facto language, whether you capture its conventions in a notation or not.
Simply knowing the elements of the language in which that work is done isn't enough. Otherwise you could just memorize a language reference manual and call yourself a software engineer.
Or could just argue that since the program in any modern language is written in UTF-8, and the users know that already, they have nothing to learn.
There are still things to learn, and you may still need to adapt tools, but it's a lot easier to work with an "embedded" DSL than an "external" one. You still need to define the nouns and verbs of your domain, but you don't have to define a whole new grammar.
> Lisp isn't any one thing, it's a language family.
Which is rather the problem. Types, in particular, are only useful if everyone has them - optional add-on typing has been tried for many languages, but I've never known it be successful.
Typed Racket <https://docs.racket-lang.org/ts-guide/> is pretty successful in the Racket community. It's also prompted some pessimistic papers about gradual sound typing, since it's hard to avoid a performance hit when imposing type safety on untyped code using contracts. On the other hand, that performance hit is in part typechecker/compiler implementation dependent and in part dependent on the granularity of the added typing (e.g. typing modules or functions vs typing subexpressions).
Typed Racket code often gains a speedup over untyped Racket, since sound typing allows the elision of contracts and other runtime overheads for safety. There is no penalty at all for invoking Typed Racket code from untyped code, either in terms of performance or in terms of what the untyped-language programmer needs to know.
Note that we've made big improvements in the performance of Typed Racket's generated contracts just since that paper was written, so many things are now better.
My point was that making generalizations about Lisp is like making generalizations about languages with C-like (perhaps more correct ALGOL-like) syntax. Most people wouldn't make a statement about Java and assert that it applied to C++, too. This is why saying that Lisp has no type system doesn't make much sense. There are many completely different languages that use s-expression notation, and they all have different feature sets, much like all the C-like languages.
>Power is a weakness in a programming language, not a strength
The truth is that Lisp is not the right language for any particular
problem. Rather, Lisp encourages one to attack a new problem by
implementing new languages tailored to that problem. Such a language
might embody an alternative computational paradigm […] A linguistic
approach to design is an essential aspect not only of programming but
of engineering design in general. Perhaps that is why Lisp […] still
seems new and adaptable, and continues to accommodate current ideas
about programming methodology.
One of them is that, each time you read a new program, you have to learn a new language. Probably no language benefitted / suffered from this more than Lisp.
Any signficant project in any language has a "dictionary" of custom identifiers, whose vocabulary you have to learn if you want to become a maintainer.
The thousand functions in a big C program are just as much a language, as some Lisp macros.
The functions all do something. That something isn't "transform the code", but that doesn't matter; if you're looking at the function call and don't know what it does, you're just as lost.
Basically, if you're reading Lisp, you go from "outside in" and just assume that everything you see whose definition you are not familiar with is a macro.
Well-behaved code follows certain unwritten conventions. For instance, it avoids creating confusion by exhibiting multiple completely independent uses of the same symbols in the same scope. So for instance if we have (frobozz a b) wrapped in a lexical scope where we have (let (a b) ...) in effect, this well-behavedness principle tells us that the a and b symbols in (frobozz a b) refer to these variables. So, we can probably lay aside our suspicion that, for instance, frobozz is redefining some unrelated a in terms of some unrelated b. However, frobozz might be a macro; so we can't cast aside our suspicion that either a or b has its value clobbered. (Same in Pascal or C++, with ordinary functions: frobozz(a, b) could take VAR parameters or references, respectively).
This isn't really the case. Some libraries are all macros, some libraries have no macros, but most have a few macros that quickly fall into general patterns: some macros for setting up and tearing down context safely (with-thing macros), others for iterating some data structure without revealing its internals (do-thing macros), generally simple stuff.
> One of them is that, each time you read a new program, you have to learn a new language
Which is not bad at all. You still have to do it with the programs written in the same language built with different libraries and targeting the different problem domains. In the latter case the language is obscuring the essence of the code.
And if you're using a well designed DSL, and you're familiar with the problem domain, it will be readable naturally, just like a pseudocode.
A lot of domain languages need infix operators though. And even if you understand the domain, it's hard to read and refactor code in the presence of unrestricted macros, whereas in a language where such DSLs are implemented via the type system the tooling will understand that.
Why do they need infix operators? Most programmers already use prefix notation with function calls. Infix is primarily restricted to mathematical and logical operations, but the prefix (lisp style, taking an arbitrary number of arguments) is pretty clear when written neatly:
(and cond1
cond2
cond3)
(NB: multiple lines like this would really only be used for a lot of conditions or longer expressions.)
We already do something similar with our algol-like languages:
But at that point it's no longer the language of the domain. If you're going to support writing mathematics that looks like the mathematics that mathematicians write then you need infix operators, because mathematics is written with infix operators. Similarly for many other domains.
That is incorrect; the notation (op arg1 arg2) isn't the surface syntax that is preferred by some practitioners working in that domain. However, it corresponds 1:1 to its abstract syntax.
There are ways to provide infix independently. That is to say, one person can develop this domain specific syntax, and another can develop or customize an infix engine for it.
In Common Lisp, there is a well known "infix.cl" module that provides mappings like a[b,c] -> (aref a b c), f(x, y) -> (f x y), a + b -> (+ a b) and so on.
This isn't understood as creating a new language as such; it's just a sugar. I think it allows new operators to be added with custom precedence and associativity. Or you can hack it however you want.
I've never seen it used in any production code.
The main purpose it serves is to satisfy people who want to know that it can be done; after that it turns out that they don't actually want it done. They just don't want to work with a language that can't do it.
The only program I'm aware of which actually supports writing mathematics that looks like the mathematics mathematicians write (the actual 2D notation) is Tilton's Algebra: written in Common Lisp.
The various mathematics languages out there fail.
Oh, and not to mention that mathematicians have been trained to work with this:
$\sin{(\frac{\pi}{2}-\theta)} = \cos{\theta}$
That's not such a bad example; I can still sort of see the trig identity in that if I squint my eyes.
Even still, mathematics isn't entirely infix. And outside computer algebra systems, you'll be hard pressed to find examples of the postfix operations expressed as postfix in programming environments. !, for example. What language allows you to express:
n P k = n! / (n - k)!
as the above? `n P k` will become something like `nperms n k`, factorial will be moved to prefix as `fact n / fact (n - k)`. We're already diverging from the domain language, there's no reason to consider a more logically consistent framework in this case than one that seems to have arbitrarily moved some things from infix to prefix, postfix almost universally to prefix, and left some infix as infix.
SML allows you to have an infix function named "P", and Haskell allows something similar, although you have to quote it with backticks and can't use a capital letter to start a function name...
In Prolog you have the ability to create new postfix operators. Of course Prolog being a logic language and not a functional language, along with '!' being used for 'cut' opens up another can of worms.
You're right as far as you go, but it's not an all-or-nothing thing. Most languages won't let you write mathematics exactly like mathematicians do, but the closer you can get the better. For many cases avoiding infix entirely would be a big cost.
(FWIW Scala allows postfix operators, though you'd have to put the n! in brackets)
> Most languages won't let you write mathematics exactly like mathematicians do, but the closer you can get the better
See Wolfram Mathematica for example.
Also, one of my usual DSL tricks is to allow arbitrary TeX in identifiers, which, combined with the literate programming tricks, allows to write very idiomatic mathematical expressions as a code.
Mathematics isn't written with infix operators alone. Mathematics is written in a fancy 2d notation with all kinds of operator types: infix, prefix, postfix, around-fix, sub-fix, super-fix.
If you look at actual software for maths - several famous ones were written in Lisp like Macsyma, Reduce and Axiom - they provide more than infix.
And? DSLs can have any syntax you like. And any type system you want.
And DSLs done the right way, via macros, are much better in integrating with tools than any ad hoc interpreted DSLs would ever be able to. You can easily have syntax and semantic highlighting infered, with auto indentation, intellisense and all the bells and whistles. For no extra cost.
> And DSLs done the right way, via macros, are much better in integrating with tools than any ad hoc interpreted DSLs would ever be able to. You can easily have syntax and semantic highlighting infered, with auto indentation, intellisense and all the bells and whistles. For no extra cost.
No you can't. If the macro is arbitrary code then no tool can offer those things - there's no way to offer intellisense if you don't know what strings are meaningful in the language, and an unconstrained macro could use anything to mean anything.
You know how GNU Bash is customizeable with custom completion for any command, so that when you're, say, in the middle of a git command, it will complete on a branch name or whatever?
Similarly, we can teach a syntax highlighter, completer or whatever in some IDE how to work with our custom macro.
Sure - but at that point we've lost a lot of the value of having a standardized language at all. The whole point of a language standard is that multiple independent tools can be written to work with it - that your profiler and your linter and your compiler can be written independently, because they'll be written to the spec. If everyone has to customize all their tools to work with their own code, that's a lot of duplicated effort. Better to have a common standard for how you embed DSLs in the language, so that all the tools already understand how to work with them.
It is a broken approach. A much better way is to have a standard protocol (see slime for example, or IPython, or whatever else), and use the same tools as your compiler does, instead of reimplementing all the crap over and over again from the language standard.
I expect that not that many C++ tools that do not use libclang will remain.
libclang is just an example, maybe not an ideal one. But, yes, I'm advocating for an executable language spec, one that you'd use as a (probably suboptimal, but canonical) implementation.
Yes you can - as soon as you start wrapping your arbitrarily complex macros into a custom syntax. I am easily doing this stuff with any language I am adding macros and extensible syntax to.
Of course I can. If my tools are communicating with my compiler, they know everything it knows. I have a single tiny generic Emacs mode (and a similar Visual Studio extension) that handles all the languages designed on top of my extensibility framework.
It's trivial. Any PEG parser I add on top automatically communicates all the highlighting, indentation data and all that to the tools (and it's inferred from the declarative spec, no additional user input is required). Underlying typing engines do the same, for the nice tooltips and code completion. The very compiler core doest the same with all the symbol definitions, dependencies, etc. Easy.
This sounds very interesting :) And I think Colin Flemming is doing something similar in Cursive? In any case, I'd like to see more of what you are talking about - do you have any more documentation of it, a writeup, blog post or video?
If I understand it correctly, Cursive is something different, they don't want to run an inferior Clojure image (unlike Slime, for example), but reproducing a lot of Clojure functionality with their massively complex static analysis tools. But I might get it wrong, all the information I have about Cursive came from one of its advocates who is very aggressively against the very idea of an inferior REPL for an IDE.
I've got some code published, but not that much in writing, planning to fix it some time later. See the stuff at my github account (username: combinatorylogic). Relevant things there are Packrat implementation, literate programming tools and an Emacs mode frontend.
Exactly! You end up defining your macros in a particular restricted subset of lisp, and your tooling for Emacs and Visual Studio has to know about that particular subset. Other people writing similar macros will no doubt have their own, subtly different subset, and their own integrations for their subset. But since your way of writing declarative specs for language customization isn't standardized, you can't use each other's tool integrations.
The way you express DSLs is something that needs to be understood by language tooling, so it belongs in the language spec.
No. Tools do not know anything about the restrictions. In fact they work with a wide range of languages, not just lisp. The only "restriction" is a protocol, built into the macro expander, syntax frontend and compiler core.
So, in your rot13 example compiler would rat all the new identifiers with their origins to the tools.
> So, in your rot13 example compiler would rat all the new identifiers with their origins to the tools.
How can the compiler know which identifier connects to which origin, unless because the macro complied with some standard/restriction/protocol? From a certain perspective all I'm suggesting is making these protocols part of the language standard - that is, define the DSL that's used to define DSLs, rather than allowing macros to consist of arbitrary code.
> Yes you can - as soon as you start wrapping your arbitrarily complex macros into a custom syntax.
Well, by that definition you get exactly the same if the host language of your DSL is statically typed and doesn't use macros. Custom syntax is custom syntax and whether tools/IDEs understand it has nothing to do with the host language.
Of course macro+syntax extension got absolutely nothing to do with what you can achieve in a language without macros.
And, no, you did not understand. Any custom syntax you're adding (if the right tools are used, like mine, for example) would automatically become available for your IDE and all the other tools, because they're reusing the same compiler front-end.
> And, no, you did not understand. Any custom syntax you're adding (if the right tools are used, like mine, for example) would automatically become available for your IDE and all the other tools, because they're reusing the same compiler front-end.
Just being able to execute the macro isn't enough for the IDE though. E.g. if a macro is "rot13 all identifiers in this block" then sure the IDE can run it, but it can't offer sensible autocompletion inside the block without understanding more about the structure of the macro.
IDE does not execute the macro - it knows the result of its expansion from the compiler. And compiler keeps a track of all the identifiers and their origins.
The IDE can autocomplete the rot13ed identifiers from outside, perhaps. But it can't possibly suggest rot13ed identifiers inside the macro block for autocomplete, because it can't possibly know that that's what the macro does.
Why? You know which macro made the identifiers. You know what this macro consumed. In most practically important cases this is sufficient.
But, yes, you cannot do it with the Common Lisp approach, where macros operate on bare lists, not the scheme-like syntax objects. The problem here is that the lists had been stripped from the important location metadata. For this reason I had to depart from the simple list-based macros and using custom syntax extension with rich ASTs underneath. Still, on top of a Lisp.
Even with location information, if the IDE's going to offer autocomplete inside the macro it would need to be able to invert the way the macro transforms identifiers, which is not possible to do to arbitrary code.
I agree that this is very rarely practically important - but if you think about it that's precisely the fact that a more restricted alternative to macros should be adequate.
> And? DSLs can have any syntax you like. And any type system you want.
While you're technically correct, as a practical matter you won't implement a type system/type checker for all the DSLs you create. (Nor do I believe you'll even do it for anything approaching a majority.). Obviously, I'm using the impersonal "you" here.
Implementing real type systems is hard and mostly rather tedious work.
I have a nice DSL which makes building complex type systems (including dependent) trivial and fun. So I do not mind adding typing to pretty much any kind of DSLs, including the smallest of them.
I still think you should have some links bookmarked to drop in conversations like this. Bookmarked so you can just type a name rather than waste time looking. Many in these discussions might think you're speculating or have some toy project rather than the interesting one I found digging through your old posts that backs up your claims.
Maybe even have a series of examples that illustrate solutions you keep mentioning so others can learn and apply them. Just a thought. :)
Actually I do have a such a framework [1], but this is not my point here. My point was that it's relatively trivial to implement such a collection of DSLs on top of pretty much any sufficiently powerful (i.e., CL-like macros) meta-language.
If you don't have a ready to use language construction framework targeting your meta-language, just build one. Easy.
As for typing specifically, the approach is rather fun and simple. Firstly, you'd need something like Prolog. It's really not that much, you can quickly build a passable implementation in just a couple of dozens of lines of code in pretty much any language. See miniKanren [2] for example. Then, any kind of typing is done easily: write a simple pass over your AST (may require some preparation passes, like resolving the lexical scope - but this is useful for all other things too), that will spit out Prolog equations for each expression node that needs typing. Then execute your Prolog code and get your types back. An implementation won't look any more complicated than a formal specification of a type system in a paper, using the type equations (as in [3]).
At this point "what is a language?" (or perhaps "what should a language be?") becomes a more than academic question. In a language with arbitrary macros one could potentially implement any language on top of that language. If we're using the term by analogy to human language, to my mind the key factor is the ability of implementations with no previous interaction to communicate (that is, how much can one express in a way that another will understand (and how deeply)). Arbitrary macros allow anything to be expressed, but it is very difficult for tools to understand the meaning of arbitrary code.
Of course. But, as I said, you don't have to restrict your macros, you only have to add a bit of a protocol on top of them in order to make them play nicely with all the tools.
And then you'll get the most powerful programming environment possible - building arbitrarily complex hierarchies of languages, with a cost of adding a new language being close to zero, and with a free support from all your tools, for no extra cost.
Actually, while building such a hierarchy I naturally came to a number of "restrictions", although they're not enforced. I prefer to build compilers using chains of very trivial transforms, each implemented with at most a total language (or a simple term rewriting for most of the cases). It also helps to maintain a nice interaction with the tools.
All compilers translate a text stream into a tree structure during parsing, so arguing that some language "needs" infix is saying that there is some tree structure out there that can't be traversed depth-first rather than breadth-first.
That can only be true if your supposed "tree" actually contains loops. What language do you know of that generates cyclical parse structures?
