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.
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.
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.
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 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.
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.
(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).
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).
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.
$ clisp -q
[1]> (typep nil '(and symbol list))
T
[2]> (typep :foo '(and symbol list))
NIL
[3]> (typep '(1 2) '(and symbol list))
NIL
[4]> (typep '(1 2) '(or symbol list))
T
[5]> (typep 3 '(or symbol list)
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.
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.
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.)
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.
But [Lisp] won't enforce those things at compilation time
in the type system, because it doesn't have one.
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.
Check out Henry Baker's Comfy 65 Compiler[1] to see how far a little lisp changes an assembler language.
[1]: http://home.pipeline.com/~hbaker1/sigplannotices/sigcol04.pd...
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.
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).
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.
(and cond1
cond2
cond3)
We already do something similar with our algol-like languages:
if((cond1 || cond2) && (cond3 || cond4)
&& (cond5 || cond6)
&& (cond7 || cond8))
(if (and (or cond1 cond2)
(or cond3 cond4)
(or cond5 cond6)
(or cond7 cond8)) n P k = n! / (n - k)!
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...
https://en.wikibooks.org/wiki/Standard_ML_Programming/Expres...
https://wiki.haskell.org/Infix_operator#Using_prefix_functio...
(FWIW Scala allows postfix operators, though you'd have to put the n! in brackets)
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.
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}$
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 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.
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.
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.
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.
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.
EDIT: Which is obviously impossible if you assume a Turing Complete macro expansion language.
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.
The way you express DSLs is something that needs to be understood by language tooling, so it belongs in the language spec.
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.
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.
It doesn't take much imagination.
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.
I expect that not that many C++ tools that do not use libclang will remain.
A good example of such a thing would be something like https://github.com/kframework/c-semantics
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.
syntax-parse only gets you so far[1].
Maybe even have a series of examples that illustrate solutions you keep mentioning so others can learn and apply them. Just a thought. :)
If so, then I suppose I misunderstood you original claim, but I won't apologize because your claim was very opaque to anyone who doesn't know you.
[1] An example of what I mean would be xtext.
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]).
[1] https://github.com/combinatorylogic/mbase
[3] http://stackoverflow.com/questions/12532552/what-part-of-mil...
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.
That can only be true if your supposed "tree" actually contains loops. What language do you know of that generates cyclical parse structures?