Ah - brings back memories of the old teletype I first used that had an actual mechanical bell that rang if it got that. Similar to https://trmm.net/Model_ASR33_Teletype
As mentioned in the user guide, just like Lisp, Bel is still in its formal phase, and not usable as a programming language yet. The idea is to extend the formal phase for a longer time, before diving into the implementation.
Welcome back pg. You should check out Jetbrains MPS, they are doing cool stuff with projectional editing. Which could mean no more brackets. I read via Twitter that they recently announced MPS for Web in Amsterdam yesterday, unfortunately I missed the conference because of my home situation :). Luckily they filmed the presentations so I will be waiting for them on YouTube.
Scheme is the teaching version of Lisp that gets used in a lot of first year university CS classes, you can probably work through an online syllabus pretty quickly if you have experience in another language.
In my experience: just pick one that you'll be using, e.g. Emacs Lisp or something for scripting, and dive into practice. Most of a lisp is little different from other imperative-functional languages, except for a taste of weirdety from the 60s and more functional freedom.
You could pick something like ClojureScript if you're using JS elsewhere―in the Lumo incarnation to avoid JVM's compilation and startup time. Though ClojureScript does add a level of complication. Other transcompiling variants like Fennel or Hy are also feasible but are probably poor on documentation and tools for a beginner.
Get a copy of The Little Schemer and follow it step by step in Racket, which is freely downloadable. It is better when learning to experience Lisp in this way than to read an explanation of why Lisp is good. It activates a different part of your brain. For many people, it feels like a dormant part of your brain has just awakened for the first time.
For me, the biggest advantage of Lisp dialects is that they make it easy to introduce very powerful and far-reaching abstractions - and idiomatic good code encourages these. For some tasks that's pretty awesome, for example anything that has to do with classic symbolic A.I. or expert systems. You abstract every data type your program uses and write small functions that operate on these types. It's similar to classical OOP, except that you're not forced to use OOP for everything but can instead use a more functional style.
Another big advantage is the syntax, because it almost doesn't exist. The language allows you to focus on the semantics whereas the syntax of expressions becomes neglectable. S-expressions are also among the main reasons why abstractions work so well in Lisp.
Finally, and this only applies to CommonLisp: CommonLisp is very complete in terms of language capabilities. It has static and dynamic types, lexical and dynamic scoping, has OOP and allows for functional programming, and so on. It has less artificial limitations than any of the more recent languages. It doesn't attempt to "hold your hand" by e.g. disallowing the use of OOP with multiple inheritance because "it's bad for you", or any such nonsense. Most LISP dialects also have garbage collection, which saves you from crashes and saves a lot of development time.
In the same way it's an improvement over other Lisp dialects. There's no huge hole in Arc that Bel fixes. Just a lot of things that are weaker or more awkward or more complicated than they should be.
> The code I wrote to generate and test the Bel source is written in Arc
Was this during bootstrapping, or is this still the case? Or in other words, do you now edit bel.bel directly or are there arc files you edit that compile into bel.bel?
It's still the case. bel.bel is generated by software. Most of the actual code is Arc that I turn into Bel in generating it. E.g. the interpreter and anything called by it, and the reader. But code that's only used in Bel programs, rather than to interpret or read Bel programs, can be and is written in Bel.
I had to change Arc a fair amount to make this work.
Curiously, enough, though, I found doing development in Bel was sufficiently better that I'd often edit code in bel.bel, then paste a translated version into the file of Arc code, rather than doing development in the latter. This seemed a good sign.
I love the idea of trying to build a mathematically pure language. I wonder how far it is possible to use optimisation techniques to make Bel efficient. For example, can the representation of strings as pairs be automatically optimised to a sequence of characters?
Yes, I believe lisps virtually always do that in practice, as does Haskell if you use certain string types (fp languages have their roots to lisp even though they have different syntax).
But lisps are dynamically typed, so to make them run fast you'd need to use a speculating jit compiler like GraalVM. They're more like python, performance wise without it.
One thing you can say for Bel for sure is that it will give implementors lots of opportunities to develop new optimization techniques. That's partly humorously euphemistic, but also true.
It admittedly is, just as it is for most other people: there are very few "serious" prorgams I can name that were written in Lisp, in spite of its venerated heritage.
There's no shortage of options in the programming language field, so one would be a fool to stick with a language they don't enjoy working in.
On the other hand, other languages use bunch of different characters and they all have different meanings and have to be in different places depending on lots of things.
In Lisp, you just have () and they are always in the same place, meaning the same thing.
This is a good point, in that Lisp is better than the other languages. But why not go all the way, and drop the parens? If the goal of Bel is to be a "good language", with shorter programs, why oh why not also strive for shorter syntax?
I love Lisp and have gotten more good constructive feedback from the Lisp community than anywhere else (with the Haskell community being a close second), but I don't understand why there's only been a dozen or so serious attempts to do Lisp without parens (I-Expressions being the best so far, better than the subsequent Wisp, etc). There should be 1,000x attempts.
This should be the top priority of most Lisp researchers. I of course think my Tree Notation is the solution, but I could easily be wrong, and there could be a better way, but the () need to go!
"why not go all the way, and drop the parens?" because no one found something that is simpler and shorter than just using parens. I-expressions are made up of invisible characters and my feeling is that not a lot of people who write lisp likes any sort of invisibility in their software.
For me, using parens is not a deal-breaker, as it's a relatively simple to use for dividing up things. Beats using invisible characters or many different characters.
At bottom something is necessary to delimit expressions. Going from () to semantic indentation is trading one delimiter for another, isn't it? Not exactly dropping the parens for free.
Break or fixed width delimiters are different than enclosing delimiters.
There's no longer any parens matching.
And not 2 things to keep track of (notice how Bel is both using parens but also following a whitespace convention for readability--that is then stripped and ignored by the compiler).
And also, your program is never in a syntactic error state--such things no longer exist. Semantic errors are still there, of course, but a whole class of errors goes puff.
> But why not go all the way, and drop the parens?
Because Lisp is not about 'parens', but that code is written in a serialized form of Lisp data and that it can be both written as externalized textual data and as actual data (by calling functions which work directly over this data).
> dozen or so serious attempts to do Lisp without parens
> This should be the top priority of most Lisp researchers.
There are many more interesting areas for progress. A Lisp without s-expression-based syntax is not a main Lisp and will form a new language group - which has happened multiple times in the past - but it won't replace the main core Lisp languages.
Good references, thanks. I took a fresh look at CGOL and was again impressed.
> Because Lisp is not about 'parens',
Exactly, so why keep them around?
When you ditch the parens, things become easier. You no longer start your programs with a syntax error. You no longer even have syntax errors. Program concatenation is easier. Dictation of programs is easier: you speak "add 2 3" instead of "open parens add 2 3 close parens". Program synthesis is easier....
> A Lisp without s-expression-based syntax is not a main Lisp and will form a new language group
All I'm saying is put S-Expressions into normalized form (indented cleanly), drop the parens, and voila, everything can still work, and you've reduced things to their simplest form.
Because Lisp source code is written in a data-structure using nested lists and nested lists are written as s-expressions with parentheses. The same Lisp code can be executed by an s-expression-based interpreter.
> When you ditch the parens
Again, the parens are not what Lisp is about, it is the nested lists as source code: internally and externally. It just happens that the lists are written with ( and ).
What you propose is essentially not just getting rid of 'parens', but dropping the source code idea based on explicit list representation.
> , things become easier.
Code generation, manipulation and transformation becomes harder.
> You no longer even have syntax errors.
How so?
> Program concatenation is easier.
How so? Lisp actually makes many forms of source code transformations easy.
> All I'm saying is put S-Expressions into normalized form (indented cleanly), drop the parens, and voila, everything can still work, and you've reduced things to their simplest form.
But then we no longer have the 'Lisp code is explicitly written in a list-based data structure' idea, which is very powerful and still relatively simple.
Language with syntax based on textual representations already exist many and there is a place for a programming language which works slightly differently.
It's possible to drop the explicit s-expression syntax, as has been demonstrated many times over history, but then the has a different look and feel. It becomes something different then and loses basic Lisp features or makes them considerable harder to use.
One can say 'why keep the wheels around'? We can do that, but either the car won't drive very well or one would transform it into something else: a boat, a plane, a sled, .. It would lose its 'car nature'.
> What you propose is essentially not just getting rid of 'parens', but dropping the source code idea based on explicit list representation.
No, I keep the nested list representation of data (as does I-Expressions: https://srfi.schemers.org/srfi-49/srfi-49.html), you just ditch the enclosing parens in favor of whitespace (or, to be more precise, in favor of 3 syntactic tokens: atomBreakSymbol, nodeBreakSymbol and edgeSymbol; by convention space/" ", newline/"\n", and space/" ").
>> You no longer even have syntax errors.
>How so?
See for yourself: https://jtree.treenotation.org/designer/. Try to generate a syntax error, it's impossible. For the same reason you don't have syntax errors at the binary notation. I think this is a very, very important hint that there is something important going on here that ties into something in nature (I don't know what that is but seems like there is a fancy prize to the person who can explain that in mathy terms). However, using the openParenSymbol and closeParenSymbol style of delimiters, you do have syntax errors--unbalanced parens.
>> Program concatenation is easier.
> How so?
This one is mildly easier, but comes up all the time. We have a Tree Language called Grammar for building other Tree Languages (and yes, Grammar itself has an implementation in Grammar). We have a Tree Language called Hakon that compiles to CSS. And we have one called Stump that compiles to HTML. Want to build a new language called "TreeML" that has both? Just `cat hakon.grammar > treeml.grammar; cat stump.grammar >> treeml.grammar` and you are just about done (just concat your new root node). You don't have to worry about adjusting any parens at the tails. A minor improvement, but lots of little things like that add up.
> but then the has a different look and feel. It becomes something different
This might be true. It seems you are taking the stand that Tree Notation is something different than Lisp (which I actually lean to agreeing with), while most lispers have given me the flippant response "congratulations! you've reinvented lisp/s-expressions". I think both arguments have merit. We will see where it goes and perhaps although the differences with parens S-Expressions are slight, perhaps there will always be a separate niche for parens lisp.
That's not an EXPLICIT list representation, where the nesting is notated by explicit characters.
It's also harder to use in interactive interfaces like REPLs, debuggers, etc., where Lisp lists don't need to have vertical layout.
> you do have syntax errors--unbalanced parens.
if you use a structure editor for Lisp you don't have unbalanced parentheses. In editors with support for s-expressions, unbalanced parentheses are basically not an issue.
> cat hakon.grammar
Yeah, Lisp works very differently. It does not use grammars like that. Lisp uses procedures in readtables to read s-expressions. Parsing the code is then done by the evaluator traversing the source or by the compiler traversing the source, with an integrated source code transformation phase (macro expansion).
We load a bunch of macros into Lisp and they then are available incrementally.
There are syntax-based structure editors (for example they were in Interlisp-D), but they always have limits, since macros can do arbitrary source transformations on s-expressions and those are not based on grammars.
You are really looking for a very different language experience. Lisp with s-expressions works very different from what you propose.
That's why I say: it's not about dropping parentheses, you propose to get rid of some of the core parts of Lisp (how programs are represented, parsed, etc.) and give it a different user interface. That's fine, but it is no longer Lisp like we know it.
Other syntaxes and IDEs for those have been done several times in Lisp-based language implementation. For example the Sk8 multimedia development tool from Apple had implemented something like AppleScript on top of Lisp. The multimedia applications were implemented in an AppleScript like language (actually it was kind of the first AppleScript implementation) with an IDE for that - implemented in Lisp.
The original dream of Lisp was to have algol-like M-Expressions and use s-expressions only for data inside M-expressions. But the internals of Lisp were implemented with s-expressions and M-expressions were manually translated into s-expressions. Breaking into a Lisp execution and looking into the interpreter state then revealed the s-expression representation of code to the developer.
> That's fine, but it is no longer Lisp like we know it.
I think this is fine, and now I can direct future commenters who tell me we've just "reinvented lisp" to your thread.
Really helpful links, and I am looking forward to watching that youtube video later this week when I have a moment. Thanks so much for all the information.
<beginExasperation> I don't understand how people who everywhere else love minimalism, refuse to give up the unnecessary parens (whitespace suffices). If the advice is not to look at them, and they are not needed, why have them at all! Every lisp program begins with a syntax error! That doesn't cause alarm bells to go off in people's heads? The commenter above says because parens-less lisp has been tried for 60 years and hasn't caught on it's evidence that it won't work. Sixty years is a blink! Binary notation is 330 years old. Indian numerals about 1,000 years old. Lisp is still in its infancy and things can be improved. </endExasperation>
Who said they aren't needed? They are the structure that supports Lisp's simplicity and consistency, which is what the good things come from. If you take them out, it gets complicated and isn't worth it.
The first good implementation I'm aware of is Egil Möller's from 2003 (https://srfi.schemers.org/srfi-49/srfi-49.html). My independently researched prediction in 2017 was that no one will ever discover a place where parens or other visible syntax is needed. That sets up an easy proof by contradiction (and I've built a database of over 10k languages so far, looking for a single scenario where you would need them, and haven't found one yet). Here are 19 demo languages covering lots of scenarios demonstrating utility without parens (https://github.com/treenotation/jtree/tree/master/langs). A glaring hole though, now that I think about it, is that I don't have a good Lisp-like Tree Language. I think a Bel Tree Language would be an excellent example project (and I'm happy to assist anyone who wants to make an attempt, and if no one has the bandwidth and it's not done by next year perhaps I'll find the time to give it a go).
> They are the structure that supports Lisp's simplicity and consistency, which is what all the good things come from.
I agree with this, but would say they are "one" structure, not "the", and that there are other options (I have one idea in tree notation, but not ruling out that there are more, perhaps better ones).
> If you take them out, it gets complicated and isn't worth it.
I agree with this, but think there is a future tipping point related to tooling. Tree Notation was quite terrible 2 years ago, but now with type checking, syntax highlighting, autocomplete, I hate to use Lisp and other languages (everything feels unfinished, because I know the syntax characters can be removed).
I think we'll hit a tipping point where the tooling for Lisp without parens is good enough that the benefits of dropping them make dropping them a no-brainer. Could I be wrong? Sure, it's a forecast/prediction. But I want to encourage people to invent new alternatives, to try everything under the sun, and not to settle that they are somehow needed. We can make it better.
> "I think we'll hit a tipping point where the tooling for Lisp without parens is good enough that the benefits of dropping them make dropping them a no-brainer."
Any such tooling tipping point would likely make the syntax of the underlying representation irrelevant. What to view the logic in tree notation? Or how about with the parens? Or the parens, but so faint you can't see them? Or collapsing aspects of the code you're not currently concerned with? What gets eventually transformed into the 1s and 0s executed by the machine, and its various representations along the way are really not the concern of the person writing at the top of that stack, at least not most of the time.
Personally I find the added vertical space by tree notation very distracting and that it breaks the scan of my reading. But that's my personal preference, and something that could be addressed with tooling. And that's the point: same thing can be said with the parens of lisp or other editing/IDE tooling.
I happen to like fine-tipped pens, while others enjoy the smoothness of thicker rollerballs. Is one better than another? Do the benefits of one make using it to the exclusion of others a no-brainer? Does my enjoyment of fine-tipped pens preclude others from developing new pen types or new writing implementations all together? Might my evangelism for fine-tipped pens turn people off from exploring the perfection that is the Uni-ball Signo UM-151 0.28mm (in blue-black ink, of course)?
To each their own. Find the medium that best helps you express your message. And that may not be the same for others. And that's okay.
This is a great, analogy thanks (and as a novice to pen culture, but an avid pen and paper user, should I get myself some Uni-ball Signo UM-151 0.28mm?'s).
> Is one better than another?
Rollerballs and fine-tipped pens are probably equivalent, on an order of magnitude scale. However, surely we can agree that both are far superior to feather or dipped pens?
I am forecasting the difference between parens free Lisp and status quo Lisp will resemble the chasm between dip pens and fountain pens.
Lots of Lispers say, "dip pens are fine! After a while you don't even notice you are dipping them." Whereas I see a future where a lot more can get done easier because we don't have to waste time dipping our pens.
>More than anything else, I think it is the ability of Lisp programs
to manipulate Lisp expressions that sets Lisp apart. And so no one
who has not written a lot of macros is really in a position to compare
Lisp to other languages. When I hear people complain about Lisp's
parentheses, it sounds to my ears like someone saying: "I tried one of those bananas, which you say are so delicious. The white part was ok, but the yellow part was very tough and tasted awful."
To make this more clear, lets' look at one example of pg's code. In verbatim it looks like this:
(mac case (expr . args)
(if (no (cdr args))
(car args)
(let v (uvar)
`(let ,v ,expr
(if (= ,v ',(car args))
,(cadr args)
(case ,v ,@(cddr args)))))))
For Lisp programmer it looks like this:
mac case (expr . args)
if no (cdr args)
car args
let v (uvar)
`let ,v ,expr
if = ,v ',(car args)
,cadr args
case ,v ,(@cddr args)
Lisp code relies on indentation for readability. Lisp aware editor knows how to automatically indent the code because it has been explicitly told. Only few of the inner parenthesis convey semantic information to the programmer.
The Julia language is very lispy at its heart, giving you access to the AST and having "true" macros. The surface syntax however is akin to Python or Matlab. Granted, doing AST manipulations in Julia is more cumbersome than in Lisp, but AFAIK the language creators actually discourage the (over)use of macros, as the resulting mini-languages can make it difficult for outsiders/newcomers to understand or maintain the code.
Other techniques to make them less prominent is to use a text face or syntax highlighting to make them less prominent, e.g:
https://github.com/tarsius/paren-face/
It's not that Lisp has many more parens as that it's simplicity mandates only 1 block structure is used to define s-expressions (lisp's AST), whereas other languages adopt multiple syntaxes for defining their different blocks structures, e.g. () {} [] <>, lisp only uses ().
I wished that, too, when I was first learning Lisp. Now, thirty years or so later, I like the parentheses. Lisp did something to me along the way.
Syntax has some quality that affects what it feels like to write code. Call it flavor, maybe; or feeling. Lisp feels good to me. It didn't feel good at first, but it gradually won me over.
I'm not the only one. Your perspective is valid, but most every Lisp programmer I've met shared it at some point, before Lisp changed their minds.
Part of it is that lisp's syntax is simple and regular enough for editors to automate a bunch of simple editing tasks. They indent things for you in a standard way. They can grab whole subexpressions and move them around and transpose them whole and so forth. Most other languages are so syntactically complicated that it's hard to make an editor do that very well.
Part of it is that the same simplicity and regularity make it tractable, even easy, to walk, transform, and generate code from Lisp expressions. That characteristic leads to things like this essay linked in another comment: http://lists.warhead.org.uk/pipermail/iwe/2005-July/000130.h...
Nowadays Lisp expressions feel to me like strings of pearls, each one containing meaning, and each one composed fractally of other pearls of meaning. They are simultaneously structurally sound and malleable. I long ago stopped wanting to get rid of the parentheses.
Some time around 1992 or so, Apple acquired a Lisp company named Coral Software and formed a team intended to invent a programming language for its research and development teams. the Advanced Technology Group and other research teams liked Lisp and Smalltalk and similar languages because of how quickly they could build working prototypes with them, but they didn't like the process of converting their successful experiments into Pascal, C, or C++ code. It was too hard, took too long, and lost too many features along the way. They wanted a new language; one that would be as flexible and congenial for experimentation as Lisp and Smalltalk, but that could also ship production code suitable for the more constrained systems that Apple customers mostly had.
The Coral group, renamed Apple Cambridge, designed a language called Ralph. It was a Lisp. More specifically, it was Scheme, but built on a runtime and type system based on a subset of CLOS, with some influence from Smalltalk and functional languages, and with system features for cleanly separating the development environment from delivered programs.
It was my favorite programming language ever. Eventually, amid some amusing shenanigans, Apple officially renamed it Dylan.
Along the way, the Dylan team heard over and over and over from non-Lispers that they wanted a non-Lispy syntax. Initially, the compiler people sort of shrugged and said, "sure, that's easy enough to do." And it is. There's been no shortage of unparenthesized syntaxes designed for Lisp in the roughly sixty years since it was introduced. None of them has ever really caught on (and that should probably tell us something about what a good idea it is, but never mind).
Dylan design meetings discussed creating a parser for an "infix syntax". The general idea was to create such a thing to mollify the non-Lispers. I even supported it. My argument was that it was a superficial matter, and if it attracted more users, it would be all to the good.
I was wrong.
I didn't appreciate just how helpful Lisp syntax is until I got hold of a Lisp that had an infix syntax. It was bulkier and more cumbersome. It was less pleasant to work with. It wasn't as easy to recognize the boundaries of expressions. Editors had a harder time working with it, so they weren't as nimble.
Of course, I could always switch back to the parenthesized syntax...until that was removed.
Same here. I liked Dylan in the early days when it had parentheses, but when they went away I completely lost interest in the language. Shortly afterwards, Apple and everybody else did too.
An old argument, as you say, but as tech changes, the constraints sustaining it may fall away.
One trend in javascript is using a style checker to enforce a uniquely-defined textual representation for any given ast. To relieve increasing-novice developers of code layout worries. Which makes that textual javascript simply an ast printed representation, an un/dump format. And editing it, is semantic representational editing of an ast.
That's more purely an ast, than even a file of s-expressions would be. Where for instance, rearranging which expressions are on a line ending with a comment can be problematic. Tasteful manual textual layout of code is sacrificed for tooling and humans not having to preserve and care about layout.
Representational editing of an ast means you can use any surface syntax you'd like. Parentheses, infix, operator precedence, concatenative, COBOLish verbosity, or whatever. Any losslessly reversible transformation is fair game. Including conversion between statement-based and expression languages. Layout becomes merely an editor customization, like colorization.
Which isn't to say it's entirely isolated from culture, style, and tooling. And thus that syntax multiplicity could have community costs. But perhaps it makes the choice a less binary thing, more amenable to tuning. The constraint that a language necessarily has exactly one syntax, modulo colors and fonts, seems to be relaxing.
() is equivalent to an empty list and nil according to this notation, in which case both would be proper lists. But according to pg, in bel, (a b . c) is not a proper list.
Think of a proper list like a degenerate tree with all the values on the left and structure on the right. A dotted list puts the last value on the right, where nil would usually be.
Dotted lists are pretty rare. They mostly show up in association lists, where key/value pairs are stored as
((name . dave) (type . user))
and adding a pair to the front of the list shadows any other pairs with the same key.
While I think this is the correct interpretation, I do not think it's actually implied by the language specification. In fact, I think the notation (a b . c) is simply undefined -- there's no way to formally deduce what it means from what is defined.
> 2. When the second half of a pair is a list, you can omit the dot before it and the parentheses around it. So (a . (b ...)) can be written as (a b ...).
That defines (a b . c). Edit: Note that (b . c) is a list.
It doesn't. That definition applies only to expressions like (a b c) which do not contain the dot operator at all. (a b . c) is not of the form specified. Moreover, every object of the sort defined via (a b c ...) is a proper list, and (a b . c) is, as described in the specification, not a proper list, so it can't be covered by that definition. It's true that (b . c) is a list, but the form (b . c) does not occur in the expression (a b . c) so this isn't relevant. (You'd need the expression under analysis to instead be (a (b . c)).)
That would only be true if (b . c) were a proper list. But it’s not. Strictly speaking, it’s not even a list if you go by the definition of list provided before your quoted rule. It’s later called a “dotted list” to distinguish it from a list, which must be nil-terminated.
Your position boils down to claiming that the rule you quoted is intended to cover lists as well as dotted lists. As stated, it only covers the former, which leaves (a b . c) undefined.
So you agree it’s ambiguous and one cannot formally deduce the meaning of the expression without making assumptions. One must assume that objects that don’t fit the definition of list can be substituted in for lists within some contexts (but not all).
Beyond that, dotted lists are introduced via the undefined example (a b . c), which requires one to go even further and make a second assumption (namely, assume the intention was to refer to (a . (b . c)), then assume the quoted transformation rule applies to certain non-lists allowing that to be rewritten as (a b . c)).
It is not the case that dotted lists don't fit the definition of list. What you point to as a definition wasn't a definition. Just examples. A definition would describe it as the minimal set of objects meeting those criteria. (A non-minimal set could include circular lists and/or pairs whose cdr is not a list.)
Since the document does use list in ways that encompass dotted lists and goes out of its way to define proper lists, we can infer that list includes dotted lists. Also, it's a long-running convention that the term "proper X" implies there are other kinds of X's.
I'd disagree with you on that. If the document can't clearly define the terms it's using, it cannot function as a formal specification of a language. The writing as it stands now is far too ambiguous to serve such a role. You have no reasonable retort to me except to say that the definition wasn't even a definition, and after that there is indeed no more abstract definition you can even point to. You're left using undefined terms to defend your interpretation as the "correct" one. That's not sufficient to defend the document as a specification. In fact, that's just further criticism of it.
Like I said, I'm confident your interpretation is the intended one. But you cannot prove it as such, and that's where we disagree.
I never claimed it was a formal specification. The question was, is the meaning of (a b . c) defined, and the answer is, yes, because (b . c) is a list.
"Also by convention, the cdr of the last cons cell in a list is nil. We call such a nil-terminated structure a proper list. In Emacs Lisp, the symbol nil is both a symbol and a list with no elements. For convenience, the symbol nil is considered to have nil as its cdr (and also as its car)."
It definitely needs to be defined. Using only the paper, I assumed from the previous definitions that (a b . c) should be parsed as (x y) where x = a and y = b . c which can be re-written using only pair notation as (x . (y . nil) ) or (a . ((b . c) . nil)) and this made it very confusing to try to figure out what is meant by "improper."
Even if a definition for the notation (a b . c) is added, an example of such an improper list fully broken down into pairs would certainly still be appreciated by us readers who don't already think in Lisp :)
Think of the period symbol as the root of a branch in a tree. A true list has all left branches empty. A "dotted list" has to items on both branches at the very tip.
Lists are made of cons cells, and a cons cell is simply a two-element array. In a list, the first element of a cons cell contains data and the second element contains a pointer to the next cons cell in the list.
How then should we represent the last cons cell in a list? We have two choices for what goes in the second element of the last cons cell:
1. The last piece of data, or
2. Nothing; i.e. a special non-pointer pointer. In Lisp this is called nil.
If we choose option 1 it's harder for code that traverses the list to be sure it has reached the end. It's also harder to splice a new element (a new cons cell) onto the end of the list dynamically.
Option 1 is the "dotted" form of ending a list and option 2 is the "proper" form.
Option 2 is more common in Lisp. From a type theory point of view, Option 2 restricts the second element of a cons cell to contain either a pointer to a cons cell or nil. This makes reasoning about code, compiling code, and optimizing code easier.
That's a crude approximation of what Mathematica can do. Not all (in fact, very few) irrational numbers are computable. Yet among the computable numbers, what our computers can represent in any language is but a small subset of them. (Although computable numbers are equinumerous with the naturals.)
> Yet among the computable numbers, what our computers can
> represent in any language is but a small subset of them.
This is only true because of physical limitations of the machine (say, it has only finite memory). In the same way not all Turing machines cannot be implemented on actual computers. This is not a restriction of the languages we use. There is nothing stopping an actual programming language representing all computable real numbers.
> (Although computable numbers are equinumerous with the naturals.)
This is only true in classical mathematics. In constructive mathematics we are free to assume that all real numbers are computable (And hence, not equinumerous with the naturals, per cantor’s argument).
There are many possible representations of real numbers which could in theory be used in programming languages.
For instance, you could represent them as functions which given a natural number produces a rational approximation – say f(n) should be a rational number closed than 1/2ⁿ to the number you represent (Cauchy sequences). Then addition of two numbers f and g, would be[0] the function (f+g)(n) ≔ f(n) + g(n), where + denotes rational summation on the left-hand side.
Or you could have a function which given a rational number input produces a boolean which tells you if the real number is less than the input. (Dedekind cuts)
No mainstream language has real numbers as a primitive[2]. In fact, not many languages have even arbitrary integers as a primitive type. But many mainstream languages have functions as first class objects, and therefore there is nothing stopping you from using them to represent real numbers.
Not all of these representations are created equal. For instance if you wanted to represent real numbers as a function which gives you the n-th digit in the decimal expansions, you cannot implement addition. This because you would have to look arbitrarily far into the digits of each number to decide even the first digit.[1]
Someone is bound say "Oh, but that is just computable numbers and there are only countably many of those". This is true if you accept classical logic. In constructive mathematics (which is most relevant to computer science), however, one can only prove that there is a surjection from the natural numbers (but there is no constructive bijection). In fact it is consistent to assume all real numbers are computable.
[0]: Most likely, you want (f+g)(n) ≔ f(n+1) + g(n+1) to get a close enough approximation, but this is a technicality.
[1]: Imagine 0.00000⋯ + 0.99999⋯. At any point later the first number could become non-zero and the first digit would be 1. Or the second number could become smaller than 9 and the result would have to have first digit 0. No way to tell what the result would be without looking at infinitely many digits.
[2]: I know of at least one, non-mainstream, language which had built-in support for real numbers. It is called RealPCF – and I am not sure it was even implemented on a computer, or if it was just a theoretical construct.
There is by definition no irrational number in any language implementation that runs on a finite machine unless it is either a stream (which is still finite when realized) or an approximation.
It's strange that the description of the language [0] starts using numbers without introducing them at first and then far later in the file says that they are implemented as literals. I didn't get to see the source code yet (I'm on mobile and have to randomly tap the text of the linked article to find links…), but I don't understand the point of this nor if it's just a semantic choice or actually implemented that way (I don't see how).
HN: How do you get an intuitionistic understanding of computation itself? While Turing Machines kind of make sense in the context of algorithms, can I really intuitively understand how lambda calculus is equivalent to Turing machines. Or how Lambda Calculus can solve algorithms? What resources helped understanding these concepts?
I can share my experience, because I was asking myself the same question 6 years ago...
My approach was to try and build a Lisp -> Brainfuck compiler. My reasoning was: Brainfuck is pretty close to a Turing machine, so if I can see how code that I understand gets translated to movement on a tape, I'll understand the fundamentals of computation.
It became an obsession of mine for 2 years, and I managed to develop a stack based virtual machine, which executed the stack instructions on a Brainfuck interpreter. It was implemented in Python. You could do basic calculations with positive numbers, define variables, arrays, work with pointers...
On one hand, it was very satisfying to see familiar code get translated to a large string of pluses and minuses; on the other, even though I built that contraption, I still didn't feel like I "got" computation in the fundamental sense. But it was a very fun project, a deep dive in computing!
My conclusion was that even though you can understand each individual layer (eventually), for a sufficiently large program, it's impossible to intuitively understand everything about it, even if you built the machine that executes that program. Your mind gets stuck in the abstractions. :)
So... good luck! I'm very interested to hear more about your past and future experiences of exploring this topic.
I wasn't aware, no. However, interpreting Brainfuck code is the easy part, as I've learned. The hard part was creating a "runtime" that understands memory locations aka. variables.
Most of the project was figuring out things similar to that. You get to appreciate how high-level machine code on our processors really is! When things like "set the stack pointer to 1234" are one instruction, instead of 10k.
I wrote a book to help answer these questions: https://computationbook.com/. It won’t necessarily be right for you (e.g. the code examples are in Ruby) but the sample chapter may help you to decide that for yourself.
I had a small homework on lambda-calculus and Turing machines equivalence when I was an undergrad (during my third year of uni iirc). It's in French but you may be able to follow by looking at the "code" parts. In it I use pure lambda-calculus to simulate a universal Turing Machine. It's probably not done the best not the more canonical way, but it's what I got while discovering lambda-calculus at the same time, so it might be good as a starting point for where you're at now. You can find the paper here: https://pablo.rauzy.name/files/lambdacalcul.pdf. Hope it helps!
478 comments
[ 4.3 ms ] story [ 306 ms ] thread- GLaDOS (Portal 2)
\bel"
Maybe it’ll come back in fashion one day.
How does one get started learning a Lisp variant (in terms of learning resources/guides), and why use Lisp over other languages?
You could pick something like ClojureScript if you're using JS elsewhere―in the Lumo incarnation to avoid JVM's compilation and startup time. Though ClojureScript does add a level of complication. Other transcompiling variants like Fennel or Hy are also feasible but are probably poor on documentation and tools for a beginner.
"A bad day writing code in Scheme is better than a good day writing code in C." —David Stigant
In another man's opinion, "Common Lisp is the best language to learn programming":
https://oneofus.la/have-emacs-will-hack/2011-10-30-common-li...
Another resource for learning Common Lisp is Stuart C. Shapiro's Common Lisp: An Interactive Approach: https://cse.buffalo.edu/~shapiro/Commonlisp/
Another big advantage is the syntax, because it almost doesn't exist. The language allows you to focus on the semantics whereas the syntax of expressions becomes neglectable. S-expressions are also among the main reasons why abstractions work so well in Lisp.
Finally, and this only applies to CommonLisp: CommonLisp is very complete in terms of language capabilities. It has static and dynamic types, lexical and dynamic scoping, has OOP and allows for functional programming, and so on. It has less artificial limitations than any of the more recent languages. It doesn't attempt to "hold your hand" by e.g. disallowing the use of OOP with multiple inheritance because "it's bad for you", or any such nonsense. Most LISP dialects also have garbage collection, which saves you from crashes and saves a lot of development time.
...sorry to be that guy.
The way Lisp began: http://paulgraham.com/rootsoflisp.html
A guide to the Bel language: https://sep.yimg.com/ty/cdn/paulgraham/bellanguage.txt?t=157...
The Bel source: https://sep.yimg.com/ty/cdn/paulgraham/bel.bel?t=1570864329&
Some code examples: https://sep.yimg.com/ty/cdn/paulgraham/belexamples.txt?t=157...
Was this during bootstrapping, or is this still the case? Or in other words, do you now edit bel.bel directly or are there arc files you edit that compile into bel.bel?
I had to change Arc a fair amount to make this work.
Curiously, enough, though, I found doing development in Bel was sufficiently better that I'd often edit code in bel.bel, then paste a translated version into the file of Arc code, rather than doing development in the latter. This seemed a good sign.
But lisps are dynamically typed, so to make them run fast you'd need to use a speculating jit compiler like GraalVM. They're more like python, performance wise without it.
There's no shortage of options in the programming language field, so one would be a fool to stick with a language they don't enjoy working in.
The solution is not to look at the parens. It's a bit like not listening to tinnitus, which is harder for some than for others. Tools help.
Beautiful. I'm stealing that, with your permission?
In Lisp, you just have () and they are always in the same place, meaning the same thing.
I love Lisp and have gotten more good constructive feedback from the Lisp community than anywhere else (with the Haskell community being a close second), but I don't understand why there's only been a dozen or so serious attempts to do Lisp without parens (I-Expressions being the best so far, better than the subsequent Wisp, etc). There should be 1,000x attempts.
This should be the top priority of most Lisp researchers. I of course think my Tree Notation is the solution, but I could easily be wrong, and there could be a better way, but the () need to go!
For me, using parens is not a deal-breaker, as it's a relatively simple to use for dividing up things. Beats using invisible characters or many different characters.
There's no longer any parens matching.
And not 2 things to keep track of (notice how Bel is both using parens but also following a whitespace convention for readability--that is then stripped and ignored by the compiler).
And also, your program is never in a syntactic error state--such things no longer exist. Semantic errors are still there, of course, but a whole class of errors goes puff.
Because Lisp is not about 'parens', but that code is written in a serialized form of Lisp data and that it can be both written as externalized textual data and as actual data (by calling functions which work directly over this data).
> dozen or so serious attempts to do Lisp without parens
MLISP, Lisp2, Logo, ML, Clisp, Dylan, RLISP, SKILL, CGOL, Julia, ...
> This should be the top priority of most Lisp researchers.
There are many more interesting areas for progress. A Lisp without s-expression-based syntax is not a main Lisp and will form a new language group - which has happened multiple times in the past - but it won't replace the main core Lisp languages.
> Because Lisp is not about 'parens',
Exactly, so why keep them around?
When you ditch the parens, things become easier. You no longer start your programs with a syntax error. You no longer even have syntax errors. Program concatenation is easier. Dictation of programs is easier: you speak "add 2 3" instead of "open parens add 2 3 close parens". Program synthesis is easier....
> A Lisp without s-expression-based syntax is not a main Lisp and will form a new language group
All I'm saying is put S-Expressions into normalized form (indented cleanly), drop the parens, and voila, everything can still work, and you've reduced things to their simplest form.
Because Lisp source code is written in a data-structure using nested lists and nested lists are written as s-expressions with parentheses. The same Lisp code can be executed by an s-expression-based interpreter.
> When you ditch the parens
Again, the parens are not what Lisp is about, it is the nested lists as source code: internally and externally. It just happens that the lists are written with ( and ).
What you propose is essentially not just getting rid of 'parens', but dropping the source code idea based on explicit list representation.
> , things become easier.
Code generation, manipulation and transformation becomes harder.
> You no longer even have syntax errors.
How so?
> Program concatenation is easier.
How so? Lisp actually makes many forms of source code transformations easy.
> All I'm saying is put S-Expressions into normalized form (indented cleanly), drop the parens, and voila, everything can still work, and you've reduced things to their simplest form.
But then we no longer have the 'Lisp code is explicitly written in a list-based data structure' idea, which is very powerful and still relatively simple.
Language with syntax based on textual representations already exist many and there is a place for a programming language which works slightly differently.
It's possible to drop the explicit s-expression syntax, as has been demonstrated many times over history, but then the has a different look and feel. It becomes something different then and loses basic Lisp features or makes them considerable harder to use.
One can say 'why keep the wheels around'? We can do that, but either the car won't drive very well or one would transform it into something else: a boat, a plane, a sled, .. It would lose its 'car nature'.
No, I keep the nested list representation of data (as does I-Expressions: https://srfi.schemers.org/srfi-49/srfi-49.html), you just ditch the enclosing parens in favor of whitespace (or, to be more precise, in favor of 3 syntactic tokens: atomBreakSymbol, nodeBreakSymbol and edgeSymbol; by convention space/" ", newline/"\n", and space/" ").
>> You no longer even have syntax errors.
>How so?
See for yourself: https://jtree.treenotation.org/designer/. Try to generate a syntax error, it's impossible. For the same reason you don't have syntax errors at the binary notation. I think this is a very, very important hint that there is something important going on here that ties into something in nature (I don't know what that is but seems like there is a fancy prize to the person who can explain that in mathy terms). However, using the openParenSymbol and closeParenSymbol style of delimiters, you do have syntax errors--unbalanced parens.
>> Program concatenation is easier.
> How so?
This one is mildly easier, but comes up all the time. We have a Tree Language called Grammar for building other Tree Languages (and yes, Grammar itself has an implementation in Grammar). We have a Tree Language called Hakon that compiles to CSS. And we have one called Stump that compiles to HTML. Want to build a new language called "TreeML" that has both? Just `cat hakon.grammar > treeml.grammar; cat stump.grammar >> treeml.grammar` and you are just about done (just concat your new root node). You don't have to worry about adjusting any parens at the tails. A minor improvement, but lots of little things like that add up.
> but then the has a different look and feel. It becomes something different
This might be true. It seems you are taking the stand that Tree Notation is something different than Lisp (which I actually lean to agreeing with), while most lispers have given me the flippant response "congratulations! you've reinvented lisp/s-expressions". I think both arguments have merit. We will see where it goes and perhaps although the differences with parens S-Expressions are slight, perhaps there will always be a separate niche for parens lisp.
That's not an EXPLICIT list representation, where the nesting is notated by explicit characters.
It's also harder to use in interactive interfaces like REPLs, debuggers, etc., where Lisp lists don't need to have vertical layout.
> you do have syntax errors--unbalanced parens.
if you use a structure editor for Lisp you don't have unbalanced parentheses. In editors with support for s-expressions, unbalanced parentheses are basically not an issue.
> cat hakon.grammar
Yeah, Lisp works very differently. It does not use grammars like that. Lisp uses procedures in readtables to read s-expressions. Parsing the code is then done by the evaluator traversing the source or by the compiler traversing the source, with an integrated source code transformation phase (macro expansion).
We load a bunch of macros into Lisp and they then are available incrementally.
There are syntax-based structure editors (for example they were in Interlisp-D), but they always have limits, since macros can do arbitrary source transformations on s-expressions and those are not based on grammars.
https://www.youtube.com/watch?v=2qsmF8HHskg
You are really looking for a very different language experience. Lisp with s-expressions works very different from what you propose.
That's why I say: it's not about dropping parentheses, you propose to get rid of some of the core parts of Lisp (how programs are represented, parsed, etc.) and give it a different user interface. That's fine, but it is no longer Lisp like we know it.
Other syntaxes and IDEs for those have been done several times in Lisp-based language implementation. For example the Sk8 multimedia development tool from Apple had implemented something like AppleScript on top of Lisp. The multimedia applications were implemented in an AppleScript like language (actually it was kind of the first AppleScript implementation) with an IDE for that - implemented in Lisp.
https://opendylan.org/_static/images/sk8.jpg
Apple Dylan had an IDE written in Lisp for infix Dylan.
https://www.macintoshrepository.org/_resize.php?w=640&h=480&...
https://www.flickr.com/photos/nda/4738803235
http://www.dylanpro.com/picts/dylanProjectBrowser.gif
https://pbs.twimg.com/media/D0KY_rGV4AAJfxH.png
The original dream of Lisp was to have algol-like M-Expressions and use s-expressions only for data inside M-expressions. But the internals of Lisp were implemented with s-expressions and M-expressions were manually translated into s-expressions. Breaking into a Lisp execution and looking into the interpreter state then revealed the s-expression representation of code to the developer.
Then the cat was out of the bag...
I think this is fine, and now I can direct future commenters who tell me we've just "reinvented lisp" to your thread.
Really helpful links, and I am looking forward to watching that youtube video later this week when I have a moment. Thanks so much for all the information.
Really? So if we dd some block of bytes from /dev/random, that is valid?
If so, that's not a very good requirement to have, I'm afraid.
- cranky new lisper
The first good implementation I'm aware of is Egil Möller's from 2003 (https://srfi.schemers.org/srfi-49/srfi-49.html). My independently researched prediction in 2017 was that no one will ever discover a place where parens or other visible syntax is needed. That sets up an easy proof by contradiction (and I've built a database of over 10k languages so far, looking for a single scenario where you would need them, and haven't found one yet). Here are 19 demo languages covering lots of scenarios demonstrating utility without parens (https://github.com/treenotation/jtree/tree/master/langs). A glaring hole though, now that I think about it, is that I don't have a good Lisp-like Tree Language. I think a Bel Tree Language would be an excellent example project (and I'm happy to assist anyone who wants to make an attempt, and if no one has the bandwidth and it's not done by next year perhaps I'll find the time to give it a go).
> They are the structure that supports Lisp's simplicity and consistency, which is what all the good things come from.
I agree with this, but would say they are "one" structure, not "the", and that there are other options (I have one idea in tree notation, but not ruling out that there are more, perhaps better ones).
> If you take them out, it gets complicated and isn't worth it.
I agree with this, but think there is a future tipping point related to tooling. Tree Notation was quite terrible 2 years ago, but now with type checking, syntax highlighting, autocomplete, I hate to use Lisp and other languages (everything feels unfinished, because I know the syntax characters can be removed).
I think we'll hit a tipping point where the tooling for Lisp without parens is good enough that the benefits of dropping them make dropping them a no-brainer. Could I be wrong? Sure, it's a forecast/prediction. But I want to encourage people to invent new alternatives, to try everything under the sun, and not to settle that they are somehow needed. We can make it better.
Any such tooling tipping point would likely make the syntax of the underlying representation irrelevant. What to view the logic in tree notation? Or how about with the parens? Or the parens, but so faint you can't see them? Or collapsing aspects of the code you're not currently concerned with? What gets eventually transformed into the 1s and 0s executed by the machine, and its various representations along the way are really not the concern of the person writing at the top of that stack, at least not most of the time.
Personally I find the added vertical space by tree notation very distracting and that it breaks the scan of my reading. But that's my personal preference, and something that could be addressed with tooling. And that's the point: same thing can be said with the parens of lisp or other editing/IDE tooling.
I happen to like fine-tipped pens, while others enjoy the smoothness of thicker rollerballs. Is one better than another? Do the benefits of one make using it to the exclusion of others a no-brainer? Does my enjoyment of fine-tipped pens preclude others from developing new pen types or new writing implementations all together? Might my evangelism for fine-tipped pens turn people off from exploring the perfection that is the Uni-ball Signo UM-151 0.28mm (in blue-black ink, of course)?
To each their own. Find the medium that best helps you express your message. And that may not be the same for others. And that's okay.
> Is one better than another?
Rollerballs and fine-tipped pens are probably equivalent, on an order of magnitude scale. However, surely we can agree that both are far superior to feather or dipped pens?
I am forecasting the difference between parens free Lisp and status quo Lisp will resemble the chasm between dip pens and fountain pens.
Lots of Lispers say, "dip pens are fine! After a while you don't even notice you are dipping them." Whereas I see a future where a lot more can get done easier because we don't have to waste time dipping our pens.
>More than anything else, I think it is the ability of Lisp programs to manipulate Lisp expressions that sets Lisp apart. And so no one who has not written a lot of macros is really in a position to compare Lisp to other languages. When I hear people complain about Lisp's parentheses, it sounds to my ears like someone saying: "I tried one of those bananas, which you say are so delicious. The white part was ok, but the yellow part was very tough and tasted awful."
To make this more clear, lets' look at one example of pg's code. In verbatim it looks like this:
For Lisp programmer it looks like this: Lisp code relies on indentation for readability. Lisp aware editor knows how to automatically indent the code because it has been explicitly told. Only few of the inner parenthesis convey semantic information to the programmer.https://chrisdone.com/posts/z/
https://shaunlebron.github.io/parinfer/ https://www.youtube.com/watch?v=K0Tsa3smr1w
Other techniques to make them less prominent is to use a text face or syntax highlighting to make them less prominent, e.g: https://github.com/tarsius/paren-face/
It's not that Lisp has many more parens as that it's simplicity mandates only 1 block structure is used to define s-expressions (lisp's AST), whereas other languages adopt multiple syntaxes for defining their different blocks structures, e.g. () {} [] <>, lisp only uses ().
Syntax has some quality that affects what it feels like to write code. Call it flavor, maybe; or feeling. Lisp feels good to me. It didn't feel good at first, but it gradually won me over.
I'm not the only one. Your perspective is valid, but most every Lisp programmer I've met shared it at some point, before Lisp changed their minds.
Part of it is that lisp's syntax is simple and regular enough for editors to automate a bunch of simple editing tasks. They indent things for you in a standard way. They can grab whole subexpressions and move them around and transpose them whole and so forth. Most other languages are so syntactically complicated that it's hard to make an editor do that very well.
Part of it is that the same simplicity and regularity make it tractable, even easy, to walk, transform, and generate code from Lisp expressions. That characteristic leads to things like this essay linked in another comment: http://lists.warhead.org.uk/pipermail/iwe/2005-July/000130.h...
Nowadays Lisp expressions feel to me like strings of pearls, each one containing meaning, and each one composed fractally of other pearls of meaning. They are simultaneously structurally sound and malleable. I long ago stopped wanting to get rid of the parentheses.
Some time around 1992 or so, Apple acquired a Lisp company named Coral Software and formed a team intended to invent a programming language for its research and development teams. the Advanced Technology Group and other research teams liked Lisp and Smalltalk and similar languages because of how quickly they could build working prototypes with them, but they didn't like the process of converting their successful experiments into Pascal, C, or C++ code. It was too hard, took too long, and lost too many features along the way. They wanted a new language; one that would be as flexible and congenial for experimentation as Lisp and Smalltalk, but that could also ship production code suitable for the more constrained systems that Apple customers mostly had.
The Coral group, renamed Apple Cambridge, designed a language called Ralph. It was a Lisp. More specifically, it was Scheme, but built on a runtime and type system based on a subset of CLOS, with some influence from Smalltalk and functional languages, and with system features for cleanly separating the development environment from delivered programs.
It was my favorite programming language ever. Eventually, amid some amusing shenanigans, Apple officially renamed it Dylan.
Along the way, the Dylan team heard over and over and over from non-Lispers that they wanted a non-Lispy syntax. Initially, the compiler people sort of shrugged and said, "sure, that's easy enough to do." And it is. There's been no shortage of unparenthesized syntaxes designed for Lisp in the roughly sixty years since it was introduced. None of them has ever really caught on (and that should probably tell us something about what a good idea it is, but never mind).
Dylan design meetings discussed creating a parser for an "infix syntax". The general idea was to create such a thing to mollify the non-Lispers. I even supported it. My argument was that it was a superficial matter, and if it attracted more users, it would be all to the good.
I was wrong.
I didn't appreciate just how helpful Lisp syntax is until I got hold of a Lisp that had an infix syntax. It was bulkier and more cumbersome. It was less pleasant to work with. It wasn't as easy to recognize the boundaries of expressions. Editors had a harder time working with it, so they weren't as nimble.
Of course, I could always switch back to the parenthesized syntax...until that was removed.
Okay, the surface syntax was clunki...
One trend in javascript is using a style checker to enforce a uniquely-defined textual representation for any given ast. To relieve increasing-novice developers of code layout worries. Which makes that textual javascript simply an ast printed representation, an un/dump format. And editing it, is semantic representational editing of an ast.
That's more purely an ast, than even a file of s-expressions would be. Where for instance, rearranging which expressions are on a line ending with a comment can be problematic. Tasteful manual textual layout of code is sacrificed for tooling and humans not having to preserve and care about layout.
Representational editing of an ast means you can use any surface syntax you'd like. Parentheses, infix, operator precedence, concatenative, COBOLish verbosity, or whatever. Any losslessly reversible transformation is fair game. Including conversion between statement-based and expression languages. Layout becomes merely an editor customization, like colorization.
Which isn't to say it's entirely isolated from culture, style, and tooling. And thus that syntax multiplicity could have community costs. But perhaps it makes the choice a less binary thing, more amenable to tuning. The constraint that a language necessarily has exactly one syntax, modulo colors and fonts, seems to be relaxing.
It would be straightforward to create a version of Bel that is a Tree Language without parens. I'd be happy to assist.
Must be hidden somewhere or not showing in my browser (firefox android with ad blockers)
Edit: I think I understand now, hmm.
Dotted lists are pretty rare. They mostly show up in association lists, where key/value pairs are stored as
and adding a pair to the front of the list shadows any other pairs with the same key.That defines (a b . c). Edit: Note that (b . c) is a list.
Your position boils down to claiming that the rule you quoted is intended to cover lists as well as dotted lists. As stated, it only covers the former, which leaves (a b . c) undefined.
Beyond that, dotted lists are introduced via the undefined example (a b . c), which requires one to go even further and make a second assumption (namely, assume the intention was to refer to (a . (b . c)), then assume the quoted transformation rule applies to certain non-lists allowing that to be rewritten as (a b . c)).
Since the document does use list in ways that encompass dotted lists and goes out of its way to define proper lists, we can infer that list includes dotted lists. Also, it's a long-running convention that the term "proper X" implies there are other kinds of X's.
Like I said, I'm confident your interpretation is the intended one. But you cannot prove it as such, and that's where we disagree.
https://www.gnu.org/software/emacs/manual/html_node/elisp/Co...
It's not a form allowed by all the preceding rules, and I wasn't sure what it meant either.
Even if a definition for the notation (a b . c) is added, an example of such an improper list fully broken down into pairs would certainly still be appreciated by us readers who don't already think in Lisp :)
How then should we represent the last cons cell in a list? We have two choices for what goes in the second element of the last cons cell:
1. The last piece of data, or
2. Nothing; i.e. a special non-pointer pointer. In Lisp this is called nil.
If we choose option 1 it's harder for code that traverses the list to be sure it has reached the end. It's also harder to splice a new element (a new cons cell) onto the end of the list dynamically.
Option 1 is the "dotted" form of ending a list and option 2 is the "proper" form.
Option 2 is more common in Lisp. From a type theory point of view, Option 2 restricts the second element of a cons cell to contain either a pointer to a cons cell or nil. This makes reasoning about code, compiling code, and optimizing code easier.
Workaround is to view full site (link at the bottom)
https://en.m.wikipedia.org/wiki/Computer_algebra
> represent in any language is but a small subset of them.
This is only true because of physical limitations of the machine (say, it has only finite memory). In the same way not all Turing machines cannot be implemented on actual computers. This is not a restriction of the languages we use. There is nothing stopping an actual programming language representing all computable real numbers.
> (Although computable numbers are equinumerous with the naturals.)
This is only true in classical mathematics. In constructive mathematics we are free to assume that all real numbers are computable (And hence, not equinumerous with the naturals, per cantor’s argument).
For instance, you could represent them as functions which given a natural number produces a rational approximation – say f(n) should be a rational number closed than 1/2ⁿ to the number you represent (Cauchy sequences). Then addition of two numbers f and g, would be[0] the function (f+g)(n) ≔ f(n) + g(n), where + denotes rational summation on the left-hand side.
Or you could have a function which given a rational number input produces a boolean which tells you if the real number is less than the input. (Dedekind cuts)
No mainstream language has real numbers as a primitive[2]. In fact, not many languages have even arbitrary integers as a primitive type. But many mainstream languages have functions as first class objects, and therefore there is nothing stopping you from using them to represent real numbers.
Not all of these representations are created equal. For instance if you wanted to represent real numbers as a function which gives you the n-th digit in the decimal expansions, you cannot implement addition. This because you would have to look arbitrarily far into the digits of each number to decide even the first digit.[1]
Someone is bound say "Oh, but that is just computable numbers and there are only countably many of those". This is true if you accept classical logic. In constructive mathematics (which is most relevant to computer science), however, one can only prove that there is a surjection from the natural numbers (but there is no constructive bijection). In fact it is consistent to assume all real numbers are computable.
[0]: Most likely, you want (f+g)(n) ≔ f(n+1) + g(n+1) to get a close enough approximation, but this is a technicality.
[1]: Imagine 0.00000⋯ + 0.99999⋯. At any point later the first number could become non-zero and the first digit would be 1. Or the second number could become smaller than 9 and the result would have to have first digit 0. No way to tell what the result would be without looking at infinitely many digits.
[2]: I know of at least one, non-mainstream, language which had built-in support for real numbers. It is called RealPCF – and I am not sure it was even implemented on a computer, or if it was just a theoretical construct.
[0] https://sep.yimg.com/ty/cdn/paulgraham/bellanguage.txt?t=157...
HN: How do you get an intuitionistic understanding of computation itself? While Turing Machines kind of make sense in the context of algorithms, can I really intuitively understand how lambda calculus is equivalent to Turing machines. Or how Lambda Calculus can solve algorithms? What resources helped understanding these concepts?
I'm currently following http://index-of.co.uk/Theory-of-Computation/Charles_Petzold-... and a bunch of other resources in the hope I'll "get" them eventually.
My approach was to try and build a Lisp -> Brainfuck compiler. My reasoning was: Brainfuck is pretty close to a Turing machine, so if I can see how code that I understand gets translated to movement on a tape, I'll understand the fundamentals of computation.
It became an obsession of mine for 2 years, and I managed to develop a stack based virtual machine, which executed the stack instructions on a Brainfuck interpreter. It was implemented in Python. You could do basic calculations with positive numbers, define variables, arrays, work with pointers...
On one hand, it was very satisfying to see familiar code get translated to a large string of pluses and minuses; on the other, even though I built that contraption, I still didn't feel like I "got" computation in the fundamental sense. But it was a very fun project, a deep dive in computing!
My conclusion was that even though you can understand each individual layer (eventually), for a sufficiently large program, it's impossible to intuitively understand everything about it, even if you built the machine that executes that program. Your mind gets stuck in the abstractions. :)
So... good luck! I'm very interested to hear more about your past and future experiences of exploring this topic.
https://www.gnu.org/software/guile/manual/guile.html#Support...
See this question that I asked (and later answered myself) around that time: https://softwareengineering.stackexchange.com/questions/2847...
Most of the project was figuring out things similar to that. You get to appreciate how high-level machine code on our processors really is! When things like "set the stack pointer to 1234" are one instruction, instead of 10k.
http://tromp.github.io/cl/Binary_lambda_calculus.html#Brainf...