8 ms·

Parentheses Are Just Typechecking

44 points by azhenley 5y ago

mananaysiempre 5y ago
In no particular order: - Lisp only needs parentheses because its operators have variable arity, that’s about as deep as the “type system” goes. - The concatenative languages wiki <https://concatenative.org https://concatenative.org> only lists Om <http://om-language.org http://om-language.org> among the (non-reverse) Polish notation concatenative languages, but its semantics are a bit more tricky than those for RPN languages when expressed in terms of left-to-right evaluation (stream processing, not stacks). - Unrelated, but see XY <http://www.nsl.com/k/xy/xy.htm http://www.nsl.com/k/xy/xy.htm> for a very elegant RPN semantics. - I think I’ve heard that the APL semantics is commonly described right to left so might be related? - The proposed Lisp-2 notation with a syntactic distinction between operators and operands strongly reminds me of how the Self expression syntax <https://handbook.selflanguage.org/2017.1/langref.html#expressions https://handbook.selflanguage.org/2017.1/langref.html#expres...> works (its main difference from Smalltalk).
- thrwaeasddsaf 5y ago
  > I think I’ve heard that the APL semantics is commonly described right to left so might be related? Not particularly related. It's just that every function is either monadic (operand on the right) or dyadic (infix). That makes it a case of not needing to explicitly specify where the function arguments start and end, still without using a stack; it is purely syntactic, and obvious (although you do need context to parse anything that uses user-defined things). Parentheses are still needed for the left operand of a dyadic function if it is to take an expression more complicated than a plain array. If you had functions of higher arity, then it would become necessary to add parens, delimiters, or a stack.
  - MaxBarraclough 5y ago
    I don't have anything substantive to add, just a nitpick: wouldn't unary be a better term than monadic here? In functional programming, monadic function is generally used to mean, well, a monadic function.
    - thrwaeasddsaf 5y ago
      Why is is better? It just seems different. APL's usage of monad predates its use in conjunction with modern functional programming languages, by the way. It goes back to the 60s, and there are plenty of books and papers where these terms are used that way. https://en.wikipedia.org/wiki/Monad_(functional_programming)#History https://en.wikipedia.org/wiki/Monad_(functional_programming)... I can't say I care too much which terms people use, but in context of APL, I prefer the terms that were used by Iverson and have been in print for more than half a century.
      - mananaysiempre 5y ago
        It is confusing, nevertheless, and perhaps merits clarification like any uncommon bit of language does. (Also like any uncommon bit of language, it may seem perfectly normal until people outside your usual circle point out they don’t understand you.) It would be interesting to track down where these terms came from. The typed functional programming usage of the term monad, being identical to the current mathematical usage, apparently comes[1] from Mac Lane’s classic Categories for the working mathematician (1971) and seems to be motivated by the preexisting term monoid (which I dislike, so that’s a bit disappointing). The use of monadic, dyadic, etc. for relations and operations of (what is now usually called) particular arity is, as far as I can tell, mostly obsolete in mathematics post 1960 or so except for the occasional use by logicians (particularly of a philosophical bent). I’ve found it[2] as far back as Russell and Whitehead’s Principia mathematica (1910–13), but don’t know where they got it from. Still, that explains the use in logic (not that it means it’s a good idea: most of notation in Russell and Whitehead[3] is now spectacularly obscure, and parts of it were obscure even at the time). [1]: https://english.stackexchange.com/a/30661 https://english.stackexchange.com/a/30661 [2]: https://en.wikisource.org/wiki/Russell_%26_Whitehead%27s_Principia_Mathematica/Introduction https://en.wikisource.org/wiki/Russell_%26_Whitehead%27s_Pri... [3]: https://plato.stanford.edu/entries/pm-notation/ https://plato.stanford.edu/entries/pm-notation/
- zajio1am 5y ago
  > Lisp only needs parentheses because its operators have variable arity, that’s about as deep as the “type system” goes. List needs parentheses because its parser does not depend on knowledge of operator's arity, it just parses generic abstract syntax tree. Arity is property of functions, not expressions, so you would need static type system to assigning arity-types to expressions. Also, you would still need parentheses to express structural data, where no operator arity is relevant.
RodgerTheGreat 5y ago
Logo is close to "a lisp with no parentheses", and it also doesn't have any special forms. You can have parens, but they are optional. Compare: item random size :list :list (item (random (size :list)) :list) It poses challenges for making parse-trees, though, especially since Logo traditionally has dynamic scope: you can't actually know the valence of a function until it is evaluated!
- throwamon 5y ago
  I'm not familiar with Logo. How are you supposed to know where parentheses are implicitly opened and closed?
  - RodgerTheGreat 5y ago
    If you know the valence (argument count) of a given word, you know how many following expressions to read, recursively. Parens in s-exprs simply make the valence an explicit syntactic feature of each evaluation. Some dialects of Logo have procedures which permit a variable number of arguments, and in those cases you might be required to include parens. In the places where you need a list (or block), square brackets are used. for example, a classic turtle-graphics phrase: repeat 4 [forward 10 right 90] The primitive `repeat` takes a number and a list, and evaluates the list. The list consists of the primitive `forward`, which takes a number, and then the primitive `right` which takes a number. As for how you parse Logo expressions into a tree form, the strategy I've taken in my interpreters is "don't". Parse everything into flat lists of words, and then at interpretation time peel off words one at a time, measure their valence, and recur.
    - throwamon 5y ago
      Oh, that makes sense. Your explanation made me realize I was assuming a few things about the language that apparently aren't true. Thank you.
mikewarot 5y ago
Stoical uses {} instead of () to do grouping, and is a reverse polish concatenative language. I tried to port it to 64 bit C, but my C foo isn't up to the task. http://stoical.sourceforge.net/documentation.php http://stoical.sourceforge.net/documentation.php
cratermoon 5y ago
Sort of. The parenthesis around an expression like (a b +) imply a result of some type. That type is defined by the whatever type promotion rules are in place for the operands and operators. Thus, if a and b are integers in the range -MIN_VALUE to MAX_VALUE, and + is defined as integer addition, then the 'type' implied by (a b +) is an integer in that range (or possibly an error condition, if under/overflow). The reason you don't see a stack language that evaluates from left to right is because then it wouldn't be a stack language.
- thrwaeasddsaf 5y ago
  But stack languages generally do evaluate left to right. I don't see why you couldn't do right to left. Makes no semantic difference. But the original post has a snippet that should not only be evaluated right to left, but also bottom to top. Unless their indentation implies hidden parens.
  - cratermoon 5y ago
    Yeah, I mean right-to-left, in response to the question the article asks: Why have I never seen... ...a stack language that evaluates right-to-left? it's because the tokens are evaluated in the order they are consumed by the parser. But now that I think about it, the tokens only look left-to-right because that's how the text is displayed. So what's really happening is that tokens are evaluated in FIFO, and there's no reason the tokens for (a b +) couldn't be written as (+ b a).
1-more 5y ago
>a Lisp that can drop nested parentheses when the meaning is clear from context It's not a lisp, but Elm with Aaron VonderHaar's elm-format does that and it is very pleasant.
ggm 5y ago
dominant is right to left reading cultures western In But it's entirely reasonable to ask why we didn't learn to think in right to left reading of stack order didn't nonetheless but oh sorry tub sselehtenon t'ndid oh sorry (trys again) bibn'ɟ nonɘɟ⑁ɘlɘƨƨ duɟ After all, treat your strings badly in Python and they do expose as .. lists .. which are .. stacks .. kinda.
taeric 5y ago
The parentheses are just one of the more portable ways of showing structure. Yes, sometimes they can be dropped, but then moving an expression might become ambiguous. This is easily seen in languages like yaml where moved code is not put with the intended indention level. Which isn't really contradicting anything here. At least, not intending to. Structure is a part of typing. And sometimes the structure is the least interesting part of the type.
vindarel 5y ago
On lisp and types, I prefer this article: https://alhassy.github.io/TypedLisp https://alhassy.github.io/TypedLisp a primer - let's explore Lisp's fine-grained type hierarchy! with a shallow comparison to Haskell.
gumby 5y ago
If comparing to something like Forth, I think it's better to consider the parens as push and pop operators.
bsedlm 5y ago
I go further, parenthesis are really just functions (in the mathematical sense); so all of first order logic comes down to making functions into variables (a la `y=f(...)`). It's crucial to not mix together these variable-functions and regular variables. The real cool thing is having two levels of "variableness" without ever acknowledging as such. That way you mix both levels of variability without ever blending them together. Similarly you also get to mix together a function description and its result; but like before, the mathematical formalisms will prevent any blending of both. in any case, I still some questions about quantifiers...
- sdbrady 5y ago
  My instincts say that you're saying something revelatory/insightful here, at least to me, but I'm not quite sure. Would you mind expounding, either with more context or more examples?
  - avador 5y ago
    I feel the same. The two levels of “variableness”, and the prohibition of mixing them, must have something to do with lazy vs eager evaluation, right?
- YeGoblynQueenne 5y ago
  >> I go further, parenthesis are really just functions (in the mathematical sense); so all of first order logic comes down to making functions into variables (a la `y=f(...)`). I don't get what you mean. Here's a quick reminder of first-order logic (FOL) syntax. In FOL, an atomic formula or atom is a predicate symbol followed by n ≥ 0 comma-separated terms in parentheses, where n is the arity of the predicate, terms are variables or functions, variables are quantified over functions and constants, a function is a function symbol followed by m ≥ 0 comma-separated terms in parentheses where m is the arity of the function and a constant is a function with arity 0. A FOL language consists of disjoint sets of predicate symbols and functions, and variables. So for example, suppose you have a language with set of predicate symbols S = {P/2} (i.e. P has arity 2), set of function symbols F = {ƒ/1} and set of variables V = {x, y}. We can create the following atoms: P(ƒ(x), y), P(x, ƒ(x)), P(ƒ(y), y), P(x, ƒ(y)), P(ƒ(ƒ(x)),y), P(x, ƒ(ƒ(y))), ... etc. We can combine atoms with the two quantifiers, ∀ and ∃ and the four logic operators ∧, ∨, → and ¬ to make well-formed formulae: ∀x∃y: P(ƒ(x), y)) ∨ P(x, ƒ(x)) etc. With this in mind, how is FOL making functions into variables? Can you explain this a bit?
djedr 5y ago
About this last point from the article: > Why have I never seen... > ...a Lisp that can drop nested parentheses when the meaning is clear from context? I once wrote a Lisp that dropped closing parentheses for one and zero-argument functions. This was done by introducing simple syntax sugar: foo | bar would be equivalent to foo[bar] in my Lisp -- this would be equivalent to the S-exp: (foo bar) My implementation used a syntax inbetween S- and M- expressions with brackets instead of parens and the first list element placed before the opening bracket, i.e. `f[x y z]` would mean `(f x y z)`. For zero-arg functions the syntax was: foo! same as: foo[] same as: (foo) This worked pretty well and in combination with currying would substantially reduce the overall amount of parens in the code. The `f[x]` syntax by itself also has the advantage of removing nesting for curried functions, i.e `(((f x) y) z)` becomes `f[x][y][z]`. In fact in this syntax two consecutive brackets `[[` were illegal. So it both eliminated consecutive opening parens and substantially reduced consecutive closing parens. This was an effort to fix the major readability problems for people coming into Lisp. For the curious, both the syntax and the language overall is described here (my master's thesis): https://djedr.github.io/masters_thesis.pdf https://djedr.github.io/masters_thesis.pdf (Chapter 2 in particular).
- celeritascelery 5y ago
  Interesting. Did you encounter any trade-offs or downsides in choosing this over a traditional s-expression style lisp? I am curious why this hasn’t been seen in a mainstream lisp before.
  - wgoodall01 5y ago
    This has been seen in a mainstream lisp before! (sort of) Wolfram Language uses almost this exact syntax—function application looks like f[x,y], but in all other respects, it works like a LISP would.
  - djedr 5y ago
    > Did you encounter any trade-offs or downsides in choosing this over a traditional s-expression style lisp? No downsides for `f[x]` instead of `(f x)`. It really does fix the problem of overnesting without any significant trade-off that I can see. Net value of this improvement is the highest. For `foo | bar` instead of `foo[bar]` I see some downsides from a minimalist point of view. Slight complexity is added to the parser. The `|` is right-associative which has to be kept in mind when reading the code: foo | bar | baz might be less clear/more difficult to grasp for somebody who is learning the language than: foo[bar[baz]] As for the zero-argument sugar `foo!` -- its value is marginal, so also might not be worth it from a minimalist point of view. > I am curious why this hasn’t been seen in a mainstream lisp before. Not sure. Certainly I have not seen this exact improvement anywhere before or since. I think it's mostly a matter of tradition. Somehow S-expressions stuck as the defining feature of Lisp and a fundamental ALGOL-like change like that would be too much to stay in the family, certainly not in the mainstream. Indeed, as @wgoodall01 mentions there is the Wolfram Language based around something similar to M-expressions, but it is neither mainstream nor (classified as) a Lisp. The syntax is also more complex overall. There is also Rebol[0] and its variants, but it is also not mainstream and diverges from Lisp substantially. Nothing else of note comes to mind. I think John McCarthy had the right idea with M-expressions. Perhaps the definition should have been a bit more minimal back then and today we would have a major Lisp with this sort of syntax. [0] https://en.wikipedia.org/wiki/Rebol https://en.wikipedia.org/wiki/Rebol
AvocadoCake 5y ago
>Then an expression like (Foo bar (Baz qux)) could be rewritten as (Foo bar Baz qux) Until you want to pass Baz as an argument of Foo. I understand the value of sugar in a language, but I also think that sometimes you don't need more than one way to skin a cat.
- earl_gray 5y ago
  I feel like I may have misunderstood the point of the article because this seems like an obvious explanation to me. A pair of parentheses in Scheme tells the interpreter that it needs to open a new environment, evaluate the expression inside, and return the value. If there aren't parentheses, the evaluator will look up the value of the symbol in the current environment. These are very different things and, it seems to me, mixing them would make it unnecessarily difficult to pass named functions as arguments. For example, (map car '((a b) (c d) (e f))) evaluates to '(a c e), while (map (car '((a b) (c d) (e f)))) yields an error. In this case, I don't want my interpreter to 'helpfully' add the parentheses in around car when it see it's a one-argument function that expects a list and the following expression is a list. And even if the interpreter is able to disambiguate it and thus avoid introducing errors, a huge benefit of the parentheses in Scheme is how easy is (as a human) to see the structure of your code at a glance. In my mind, introducing ambiguity here would only serve to undermine this while bring minimal benefit.
dukeofdoom 5y ago
I thought they denote a tree structure. At least that's how I remember it being in Scheme. You could follow the order of evaluation back to the root node. Something I wish was explained earlier, because initially I found all the parentheses confusing as Scheme was my intro to programming language.
- Kim_Bruning 5y ago
  This is true. It just so happens that stacks and trees can map to each other.
gilch 5y ago
Red and Rebol have prefix notation and no parentheses to delimit the arguments. That means you have to know the arity of each function to understand how to build the parse tree. This is apparently not as hard as it sounds, because natural languages work the same way, although they can be ambiguous, at least if you're familiar with all the functions.
massung 5y ago
> Why have I never seen... Simply put, limited history/experience. That's not a bad thing. Rediscovery is good, and often coming at things new, with ideas not weighed down by past thinking can allow for breakthroughs. > ...a stack language that evaluates right-to-left? APL, J, K, etc. > ...a stack language that allows parentheses as a sanity check? Factor. Not really parentheses, but there are stack languages that use the stack notation ( x -- x x ) to verify stack balance and some that even use the stack notation to validate types. Types and stack balance can even be inferred. > ...a Lisp that can drop nested parentheses when the meaning is clear from context? REBOL and now Red, et al. But, as @mananaysiempre stated in another comment, the primary use of parentheses in Lisp is due to functions that allow for variable arity.
renox 5y ago
If we're talking about different syntax for Lips are-there some Lisp-variant which use fn(arg1 arg2...) instead of (fn arg1 arg2 ...) ? I think that this is more readable as this reflects that the "role" of the first argument is different from the other arguments..
- djedr 5y ago
  I don't know of any such variant, and I've looked. There seems to be nothing. I had this idea too, and I implemented it, see my comment here[0]. The readability argument is arguably subjective -- `fn` can be seen as special on either side of the paren -- either way it's special because it's the thing next to the paren. The syntax is certainly more familiar for most people who had anything to do with math or ALGOL-like languages. What is objective about this syntax though is that it removes nesting for curried functions (see the linked comment for details). I think this is the right idea. [0] https://news.ycombinator.com/item?id=27625295 https://news.ycombinator.com/item?id=27625295
peter_d_sherman 5y ago
>"Consider this Scheme expression, taken from the Rosetta Code example for the Mandelbrot set: (boolean->integer (inside? (make-rectangular (+ x-offset (\* pixel-size i)) (- y-offset (\* pixel-size j)))) [...] Stack languages are a mirror image of Lisps, written in postfix rather than prefix notation. So a Forth-like version of this expression would be the same words in reverse, without the parentheses: j pixel-size * y-offset - i pixel-size * x-offset + make-rectangular inside? boolean->integer" PDS: I know about both LISP and Forth -- but until I read this article, I never made this simple, intuitive, elegant, and utterly brilliant -- connection! Yes, it's absolutely true! And it's utterly, utterly brilliant!!! To the Author: Thank you for writing this article!!!

44 points by azhenley 5y ago

In no particular order: - Lisp only needs parentheses because its operators have variable arity, that’s about as deep as the “type system” goes. - The concatenative languages wiki <https://concatenative.org https://concatenative.org> only lists Om <http://om-language.org http://om-language.org> among the (non-reverse) Polish notation concatenative languages, but its semantics are a bit more tricky than those for RPN languages when expressed in terms of left-to-right evaluation (stream processing, not stacks). - Unrelated, but see XY <http://www.nsl.com/k/xy/xy.htm http://www.nsl.com/k/xy/xy.htm> for a very elegant RPN semantics. - I think I’ve heard that the APL semantics is commonly described right to left so might be related? - The proposed Lisp-2 notation with a syntactic distinction between operators and operands strongly reminds me of how the Self expression syntax <https://handbook.selflanguage.org/2017.1/langref.html#expressions https://handbook.selflanguage.org/2017.1/langref.html#expres...> works (its main difference from Smalltalk).

thrwaeasddsaf 5y ago
> I think I’ve heard that the APL semantics is commonly described right to left so might be related? Not particularly related. It's just that every function is either monadic (operand on the right) or dyadic (infix). That makes it a case of not needing to explicitly specify where the function arguments start and end, still without using a stack; it is purely syntactic, and obvious (although you do need context to parse anything that uses user-defined things). Parentheses are still needed for the left operand of a dyadic function if it is to take an expression more complicated than a plain array. If you had functions of higher arity, then it would become necessary to add parens, delimiters, or a stack.
- MaxBarraclough 5y ago
  I don't have anything substantive to add, just a nitpick: wouldn't unary be a better term than monadic here? In functional programming, monadic function is generally used to mean, well, a monadic function.
  - thrwaeasddsaf 5y ago
    Why is is better? It just seems different. APL's usage of monad predates its use in conjunction with modern functional programming languages, by the way. It goes back to the 60s, and there are plenty of books and papers where these terms are used that way. https://en.wikipedia.org/wiki/Monad_(functional_programming)#History https://en.wikipedia.org/wiki/Monad_(functional_programming)... I can't say I care too much which terms people use, but in context of APL, I prefer the terms that were used by Iverson and have been in print for more than half a century.
    - mananaysiempre 5y ago
      It is confusing, nevertheless, and perhaps merits clarification like any uncommon bit of language does. (Also like any uncommon bit of language, it may seem perfectly normal until people outside your usual circle point out they don’t understand you.) It would be interesting to track down where these terms came from. The typed functional programming usage of the term monad, being identical to the current mathematical usage, apparently comes[1] from Mac Lane’s classic Categories for the working mathematician (1971) and seems to be motivated by the preexisting term monoid (which I dislike, so that’s a bit disappointing). The use of monadic, dyadic, etc. for relations and operations of (what is now usually called) particular arity is, as far as I can tell, mostly obsolete in mathematics post 1960 or so except for the occasional use by logicians (particularly of a philosophical bent). I’ve found it[2] as far back as Russell and Whitehead’s Principia mathematica (1910–13), but don’t know where they got it from. Still, that explains the use in logic (not that it means it’s a good idea: most of notation in Russell and Whitehead[3] is now spectacularly obscure, and parts of it were obscure even at the time). [1]: https://english.stackexchange.com/a/30661 https://english.stackexchange.com/a/30661 [2]: https://en.wikisource.org/wiki/Russell_%26_Whitehead%27s_Principia_Mathematica/Introduction https://en.wikisource.org/wiki/Russell_%26_Whitehead%27s_Pri... [3]: https://plato.stanford.edu/entries/pm-notation/ https://plato.stanford.edu/entries/pm-notation/
zajio1am 5y ago
> Lisp only needs parentheses because its operators have variable arity, that’s about as deep as the “type system” goes. List needs parentheses because its parser does not depend on knowledge of operator's arity, it just parses generic abstract syntax tree. Arity is property of functions, not expressions, so you would need static type system to assigning arity-types to expressions. Also, you would still need parentheses to express structural data, where no operator arity is relevant.

RodgerTheGreat 5y ago

Logo is close to "a lisp with no parentheses", and it also doesn't have any special forms. You can have parens, but they are optional. Compare: item random size :list :list (item (random (size :list)) :list) It poses challenges for making parse-trees, though, especially since Logo traditionally has dynamic scope: you can't actually know the valence of a function until it is evaluated!

throwamon 5y ago
I'm not familiar with Logo. How are you supposed to know where parentheses are implicitly opened and closed?
- RodgerTheGreat 5y ago
  If you know the valence (argument count) of a given word, you know how many following expressions to read, recursively. Parens in s-exprs simply make the valence an explicit syntactic feature of each evaluation. Some dialects of Logo have procedures which permit a variable number of arguments, and in those cases you might be required to include parens. In the places where you need a list (or block), square brackets are used. for example, a classic turtle-graphics phrase: repeat 4 [forward 10 right 90] The primitive `repeat` takes a number and a list, and evaluates the list. The list consists of the primitive `forward`, which takes a number, and then the primitive `right` which takes a number. As for how you parse Logo expressions into a tree form, the strategy I've taken in my interpreters is "don't". Parse everything into flat lists of words, and then at interpretation time peel off words one at a time, measure their valence, and recur.
  - throwamon 5y ago
    Oh, that makes sense. Your explanation made me realize I was assuming a few things about the language that apparently aren't true. Thank you.

mikewarot 5y ago

Stoical uses {} instead of () to do grouping, and is a reverse polish concatenative language. I tried to port it to 64 bit C, but my C foo isn't up to the task. http://stoical.sourceforge.net/documentation.php http://stoical.sourceforge.net/documentation.php

cratermoon 5y ago

Sort of. The parenthesis around an expression like (a b +) imply a result of some type. That type is defined by the whatever type promotion rules are in place for the operands and operators. Thus, if a and b are integers in the range -MIN_VALUE to MAX_VALUE, and + is defined as integer addition, then the 'type' implied by (a b +) is an integer in that range (or possibly an error condition, if under/overflow). The reason you don't see a stack language that evaluates from left to right is because then it wouldn't be a stack language.

thrwaeasddsaf 5y ago
But stack languages generally do evaluate left to right. I don't see why you couldn't do right to left. Makes no semantic difference. But the original post has a snippet that should not only be evaluated right to left, but also bottom to top. Unless their indentation implies hidden parens.
- cratermoon 5y ago
  Yeah, I mean right-to-left, in response to the question the article asks: Why have I never seen... ...a stack language that evaluates right-to-left? it's because the tokens are evaluated in the order they are consumed by the parser. But now that I think about it, the tokens only look left-to-right because that's how the text is displayed. So what's really happening is that tokens are evaluated in FIFO, and there's no reason the tokens for (a b +) couldn't be written as (+ b a).

1-more 5y ago

>a Lisp that can drop nested parentheses when the meaning is clear from context It's not a lisp, but Elm with Aaron VonderHaar's elm-format does that and it is very pleasant.

ggm 5y ago

dominant is right to left reading cultures western In But it's entirely reasonable to ask why we didn't learn to think in right to left reading of stack order didn't nonetheless but oh sorry tub sselehtenon t'ndid oh sorry (trys again) bibn'ɟ nonɘɟ⑁ɘlɘƨƨ duɟ After all, treat your strings badly in Python and they do expose as .. lists .. which are .. stacks .. kinda.

taeric 5y ago

The parentheses are just one of the more portable ways of showing structure. Yes, sometimes they can be dropped, but then moving an expression might become ambiguous. This is easily seen in languages like yaml where moved code is not put with the intended indention level. Which isn't really contradicting anything here. At least, not intending to. Structure is a part of typing. And sometimes the structure is the least interesting part of the type.

vindarel 5y ago

On lisp and types, I prefer this article: https://alhassy.github.io/TypedLisp https://alhassy.github.io/TypedLisp a primer - let's explore Lisp's fine-grained type hierarchy! with a shallow comparison to Haskell.

gumby 5y ago

If comparing to something like Forth, I think it's better to consider the parens as push and pop operators.

bsedlm 5y ago

I go further, parenthesis are really just functions (in the mathematical sense); so all of first order logic comes down to making functions into variables (a la `y=f(...)`). It's crucial to not mix together these variable-functions and regular variables. The real cool thing is having two levels of "variableness" without ever acknowledging as such. That way you mix both levels of variability without ever blending them together. Similarly you also get to mix together a function description and its result; but like before, the mathematical formalisms will prevent any blending of both. in any case, I still some questions about quantifiers...

sdbrady 5y ago
My instincts say that you're saying something revelatory/insightful here, at least to me, but I'm not quite sure. Would you mind expounding, either with more context or more examples?
- avador 5y ago
  I feel the same. The two levels of “variableness”, and the prohibition of mixing them, must have something to do with lazy vs eager evaluation, right?
YeGoblynQueenne 5y ago
>> I go further, parenthesis are really just functions (in the mathematical sense); so all of first order logic comes down to making functions into variables (a la `y=f(...)`). I don't get what you mean. Here's a quick reminder of first-order logic (FOL) syntax. In FOL, an atomic formula or atom is a predicate symbol followed by n ≥ 0 comma-separated terms in parentheses, where n is the arity of the predicate, terms are variables or functions, variables are quantified over functions and constants, a function is a function symbol followed by m ≥ 0 comma-separated terms in parentheses where m is the arity of the function and a constant is a function with arity 0. A FOL language consists of disjoint sets of predicate symbols and functions, and variables. So for example, suppose you have a language with set of predicate symbols S = {P/2} (i.e. P has arity 2), set of function symbols F = {ƒ/1} and set of variables V = {x, y}. We can create the following atoms: P(ƒ(x), y), P(x, ƒ(x)), P(ƒ(y), y), P(x, ƒ(y)), P(ƒ(ƒ(x)),y), P(x, ƒ(ƒ(y))), ... etc. We can combine atoms with the two quantifiers, ∀ and ∃ and the four logic operators ∧, ∨, → and ¬ to make well-formed formulae: ∀x∃y: P(ƒ(x), y)) ∨ P(x, ƒ(x)) etc. With this in mind, how is FOL making functions into variables? Can you explain this a bit?

djedr 5y ago

About this last point from the article: > Why have I never seen... > ...a Lisp that can drop nested parentheses when the meaning is clear from context? I once wrote a Lisp that dropped closing parentheses for one and zero-argument functions. This was done by introducing simple syntax sugar: foo | bar would be equivalent to foo[bar] in my Lisp -- this would be equivalent to the S-exp: (foo bar) My implementation used a syntax inbetween S- and M- expressions with brackets instead of parens and the first list element placed before the opening bracket, i.e. `f[x y z]` would mean `(f x y z)`. For zero-arg functions the syntax was: foo! same as: foo[] same as: (foo) This worked pretty well and in combination with currying would substantially reduce the overall amount of parens in the code. The `f[x]` syntax by itself also has the advantage of removing nesting for curried functions, i.e `(((f x) y) z)` becomes `f[x][y][z]`. In fact in this syntax two consecutive brackets `[[` were illegal. So it both eliminated consecutive opening parens and substantially reduced consecutive closing parens. This was an effort to fix the major readability problems for people coming into Lisp. For the curious, both the syntax and the language overall is described here (my master's thesis): https://djedr.github.io/masters_thesis.pdf https://djedr.github.io/masters_thesis.pdf (Chapter 2 in particular).

celeritascelery 5y ago
Interesting. Did you encounter any trade-offs or downsides in choosing this over a traditional s-expression style lisp? I am curious why this hasn’t been seen in a mainstream lisp before.
- wgoodall01 5y ago
  This has been seen in a mainstream lisp before! (sort of) Wolfram Language uses almost this exact syntax—function application looks like f[x,y], but in all other respects, it works like a LISP would.
- djedr 5y ago
  > Did you encounter any trade-offs or downsides in choosing this over a traditional s-expression style lisp? No downsides for `f[x]` instead of `(f x)`. It really does fix the problem of overnesting without any significant trade-off that I can see. Net value of this improvement is the highest. For `foo | bar` instead of `foo[bar]` I see some downsides from a minimalist point of view. Slight complexity is added to the parser. The `|` is right-associative which has to be kept in mind when reading the code: foo | bar | baz might be less clear/more difficult to grasp for somebody who is learning the language than: foo[bar[baz]] As for the zero-argument sugar `foo!` -- its value is marginal, so also might not be worth it from a minimalist point of view. > I am curious why this hasn’t been seen in a mainstream lisp before. Not sure. Certainly I have not seen this exact improvement anywhere before or since. I think it's mostly a matter of tradition. Somehow S-expressions stuck as the defining feature of Lisp and a fundamental ALGOL-like change like that would be too much to stay in the family, certainly not in the mainstream. Indeed, as @wgoodall01 mentions there is the Wolfram Language based around something similar to M-expressions, but it is neither mainstream nor (classified as) a Lisp. The syntax is also more complex overall. There is also Rebol[0] and its variants, but it is also not mainstream and diverges from Lisp substantially. Nothing else of note comes to mind. I think John McCarthy had the right idea with M-expressions. Perhaps the definition should have been a bit more minimal back then and today we would have a major Lisp with this sort of syntax. [0] https://en.wikipedia.org/wiki/Rebol https://en.wikipedia.org/wiki/Rebol

AvocadoCake 5y ago

>Then an expression like (Foo bar (Baz qux)) could be rewritten as (Foo bar Baz qux) Until you want to pass Baz as an argument of Foo. I understand the value of sugar in a language, but I also think that sometimes you don't need more than one way to skin a cat.

earl_gray 5y ago
I feel like I may have misunderstood the point of the article because this seems like an obvious explanation to me. A pair of parentheses in Scheme tells the interpreter that it needs to open a new environment, evaluate the expression inside, and return the value. If there aren't parentheses, the evaluator will look up the value of the symbol in the current environment. These are very different things and, it seems to me, mixing them would make it unnecessarily difficult to pass named functions as arguments. For example, (map car '((a b) (c d) (e f))) evaluates to '(a c e), while (map (car '((a b) (c d) (e f)))) yields an error. In this case, I don't want my interpreter to 'helpfully' add the parentheses in around car when it see it's a one-argument function that expects a list and the following expression is a list. And even if the interpreter is able to disambiguate it and thus avoid introducing errors, a huge benefit of the parentheses in Scheme is how easy is (as a human) to see the structure of your code at a glance. In my mind, introducing ambiguity here would only serve to undermine this while bring minimal benefit.

dukeofdoom 5y ago

I thought they denote a tree structure. At least that's how I remember it being in Scheme. You could follow the order of evaluation back to the root node. Something I wish was explained earlier, because initially I found all the parentheses confusing as Scheme was my intro to programming language.

Kim_Bruning 5y ago
This is true. It just so happens that stacks and trees can map to each other.

gilch 5y ago

Red and Rebol have prefix notation and no parentheses to delimit the arguments. That means you have to know the arity of each function to understand how to build the parse tree. This is apparently not as hard as it sounds, because natural languages work the same way, although they can be ambiguous, at least if you're familiar with all the functions.

massung 5y ago

> Why have I never seen... Simply put, limited history/experience. That's not a bad thing. Rediscovery is good, and often coming at things new, with ideas not weighed down by past thinking can allow for breakthroughs. > ...a stack language that evaluates right-to-left? APL, J, K, etc. > ...a stack language that allows parentheses as a sanity check? Factor. Not really parentheses, but there are stack languages that use the stack notation ( x -- x x ) to verify stack balance and some that even use the stack notation to validate types. Types and stack balance can even be inferred. > ...a Lisp that can drop nested parentheses when the meaning is clear from context? REBOL and now Red, et al. But, as @mananaysiempre stated in another comment, the primary use of parentheses in Lisp is due to functions that allow for variable arity.

renox 5y ago

If we're talking about different syntax for Lips are-there some Lisp-variant which use fn(arg1 arg2...) instead of (fn arg1 arg2 ...) ? I think that this is more readable as this reflects that the "role" of the first argument is different from the other arguments..

djedr 5y ago
I don't know of any such variant, and I've looked. There seems to be nothing. I had this idea too, and I implemented it, see my comment here[0]. The readability argument is arguably subjective -- `fn` can be seen as special on either side of the paren -- either way it's special because it's the thing next to the paren. The syntax is certainly more familiar for most people who had anything to do with math or ALGOL-like languages. What is objective about this syntax though is that it removes nesting for curried functions (see the linked comment for details). I think this is the right idea. [0] https://news.ycombinator.com/item?id=27625295 https://news.ycombinator.com/item?id=27625295

peter_d_sherman 5y ago

>"Consider this Scheme expression, taken from the Rosetta Code example for the Mandelbrot set: (boolean->integer (inside? (make-rectangular (+ x-offset (\* pixel-size i)) (- y-offset (\* pixel-size j)))) [...] Stack languages are a mirror image of Lisps, written in postfix rather than prefix notation. So a Forth-like version of this expression would be the same words in reverse, without the parentheses: j pixel-size * y-offset - i pixel-size * x-offset + make-rectangular inside? boolean->integer" PDS: I know about both LISP and Forth -- but until I read this article, I never made this simple, intuitive, elegant, and utterly brilliant -- connection! Yes, it's absolutely true! And it's utterly, utterly brilliant!!! To the Author: Thank you for writing this article!!!