Nim 1.0 • Hacker News Board

Re: Nim 1.0

#291

Post by thsealienbstrds » Wed, Sep 25, 2019, 3:37 PM UTC

lispm wrote: post #280

thsealienbstrds wrote: post #278

Earlier quoted context omitted.

Disclaimer: I only did a hobby project in Lisp once. But I did use some of the macro functionality. Judging by some of the comments here, it seems like the macro system has a similar approach as Lisp's macro system, which is also AST-based. Something I don't see here is macros that generate other macros, but the question is how much you really want that anyway (when I did that, I thought the syntax was horribly compl…

Lisp macros are not based on an AST. The macro forms in Lisp need to be valid s-expressions and begin with a macro operator. That's it.

Still, isn't it AST-based in the sense that the input of a Lisp macro is effectively a parsed syntax tree, just as in Nim?

Re: Nim 1.0

#293

Post by kazinator » Wed, Sep 25, 2019, 4:27 PM UTC

lispm wrote: post #292

thsealienbstrds wrote: post #291

Earlier quoted context omitted.

Still, isn't it AST-based in the sense that the input of a Lisp macro is effectively a parsed syntax tree, just as in Nim?

The only restriction is that it is a s-expression: a possibly nested list of data. There is no particular programming language syntax it is parsed against - it's parsed as data. For example this is a valid Lisp macro form (loop for i below 10 and j downfrom 20 when (= (+ i j) 9) sum i into isum of-type integer finally (return (+ j isum))) It returns 10. The LOOP macro parses it on its own - it just sees a list of dat…

The data has an AST. The AST is made of conses, and atoms. The atoms have a large variety of types. They are not "tokens", but objects. Tokens only exist briefly inside the Lisp reader. 123 and |123| are tokens; one converts to an integer node, one to a symbol node. (1 (2 3)) has an AST which is

    CONS
   /      \
  FIXNUM   CONS
  |        /   \
  1      CONS   SYMBOL
        /     \     \ 
      FIXNUM   CONS  NIL
        |      /   \
        2   FIXNUM  SYMBOL
              |        |
              3        NIL

Re: Nim 1.0

#294

Post by lispm » Wed, Sep 25, 2019, 6:41 PM UTC

kazinator wrote: post #293

lispm wrote: post #292

Earlier quoted context omitted.

The only restriction is that it is a s-expression: a possibly nested list of data. There is no particular programming language syntax it is parsed against - it's parsed as data. For example this is a valid Lisp macro form (loop for i below 10 and j downfrom 20 when (= (+ i j) 9) sum i into isum of-type integer finally (return (+ j isum))) It returns 10. The LOOP macro parses it on its own - it just sees a list of dat…

The data has an AST. The AST is made of conses, and atoms. The atoms have a large variety of types. They are not "tokens", but objects. Tokens only exist briefly inside the Lisp reader. 123 and |123| are tokens; one converts to an integer node, one to a symbol node. (1 (2 3)) has an AST which is CONS / \ FIXNUM CONS | / \ 1 CONS SYMBOL / \ \ FIXNUM CONS NIL | / \ 2 FIXNUM SYMBOL | | 3 NIL

> The data has an AST.

(not (eq 'has 'is))

But for an Abstract Syntax Tree for code we have more categories: function, operator, call, control structure, variable, class, ...

Re: Nim 1.0

#295

Post by thsealienbstrds » Wed, Sep 25, 2019, 8:31 PM UTC

lispm wrote: post #294

kazinator wrote: post #293

Earlier quoted context omitted.

The data has an AST. The AST is made of conses, and atoms. The atoms have a large variety of types. They are not "tokens", but objects. Tokens only exist briefly inside the Lisp reader. 123 and |123| are tokens; one converts to an integer node, one to a symbol node. (1 (2 3)) has an AST which is CONS / \ FIXNUM CONS | / \ 1 CONS SYMBOL / \ \ FIXNUM CONS NIL | / \ 2 FIXNUM SYMBOL | | 3 NIL

> The data has an AST. (not (eq 'has 'is)) But for an Abstract Syntax Tree for code we have more categories: function, operator, call, control structure, variable, class, ...

Fair enough I guess. If the Lisp macro system only sees parsed s-exps, in principle you still need to figure out for yourself what kind of construct you are dealing with on a higher level of abstraction. Nim's macro system seems to be operating on a higher level of abstraction in that regard.

Re: Nim 1.0

#296

Post by kazinator » Wed, Sep 25, 2019, 11:22 PM UTC

lispm wrote: post #294

kazinator wrote: post #293

Earlier quoted context omitted.

The data has an AST. The AST is made of conses, and atoms. The atoms have a large variety of types. They are not "tokens", but objects. Tokens only exist briefly inside the Lisp reader. 123 and |123| are tokens; one converts to an integer node, one to a symbol node. (1 (2 3)) has an AST which is CONS / \ FIXNUM CONS | / \ 1 CONS SYMBOL / \ \ FIXNUM CONS NIL | / \ 2 FIXNUM SYMBOL | | 3 NIL

> The data has an AST. (not (eq 'has 'is)) But for an Abstract Syntax Tree for code we have more categories: function, operator, call, control structure, variable, class, ...

That kind of tree is stipulated a particular form of compiler (well, parser) writing dogma revolving around C++/Java style OOP. You set up classes with inheritance representing various node types; everything has methods, and "visitors" walk the tree, and various nonsense like that.

If our code walker dispatches on pattern matches on the nested list structure of conses and atoms, we don't need that sort of encapsulated data structuring. The shapes of the patterns are de facto the higher level AST nodes. The code walking pattern case that recognizes (if test [then [else]]) is in fact working with an "if node". That AST node isn't defined in a rigid structure in the underlying data, but it's defined in the pattern that is applied to it which imposes a schema on the data.

If that's not an AST node, that's like saying that (1 95000) isn't an employee record; only #S(employee id 1 salary 95000) is an employee record because it has a proper type with a name, and named fields, whereas (1 95000) "could be anything".

Re: Nim 1.0

#297

Post by lispm » Thu, Sep 26, 2019, 5:32 AM UTC

kazinator wrote: post #296

lispm wrote: post #294

Earlier quoted context omitted.

> The data has an AST. (not (eq 'has 'is)) But for an Abstract Syntax Tree for code we have more categories: function, operator, call, control structure, variable, class, ...

That kind of tree is stipulated a particular form of compiler (well, parser) writing dogma revolving around C++/Java style OOP. You set up classes with inheritance representing various node types; everything has methods, and "visitors" walk the tree, and various nonsense like that. If our code walker dispatches on pattern matches on the nested list structure of conses and atoms, we don't need that sort of encapsulate…

Syntax trees are no nonsense and go way back before Java and visitors were hip.

The code walker is just another parser. It needs to know the Lisp syntax. It needs to know which parts of a LET form is a binding list, what a binding list looks like, it needs to know where declarations are and where the code body ist. It can then recognize variables, declarations, calls, literal data, etc, It needs to know the scope of the variables etc. Nothing of that is encoded in the LET form (since it is no AST), and needs to be determined by the code walker. Actually that's one of the most important uses: finding out what things are in the source code. Lisp does not offer us that information. That's why we need an additional tool. A code walker may or may not construct an AST.

No, (1 950000) is not an employee record. Only your interpretation makes it one. Other than that our default Lisp interpretation based on s-expressions: it's a list of two numbers. In terms of the machine it's cons cells, numbers, nil. Without further context, it has no further meaning.

Re: Nim 1.0

#298

Post by kazinator » Thu, Sep 26, 2019, 5:45 AM UTC

lispm wrote: post #297

kazinator wrote: post #296

Earlier quoted context omitted.

That kind of tree is stipulated a particular form of compiler (well, parser) writing dogma revolving around C++/Java style OOP. You set up classes with inheritance representing various node types; everything has methods, and "visitors" walk the tree, and various nonsense like that. If our code walker dispatches on pattern matches on the nested list structure of conses and atoms, we don't need that sort of encapsulate…

Syntax trees are no nonsense and go way back before Java and visitors were hip. The code walker is just another parser. It needs to know the Lisp syntax. It needs to know which parts of a LET form is a binding list, what a binding list looks like, it needs to know where declarations are and where the code body ist. It can then recognize variables, declarations, calls, literal data, etc, It needs to know the scope of…

Note that deciphering type tag info in a Lisp value can be called "parsing". Cases occur: for some values we have to chase a pointer into a heap to get more type info.

A Lisp function call does "parsing". (foo 1 2 3) has to figure out dynamically whether a (lambda (&rest args)) is being called or (lambda (a b c)) or (lambda (a b &optional c (d 42)) or whatever.

The #S(employee id 1 salary 95000) object also isn't an employee record without context and interpretation.

> it needs to know where declarations are and where the code body ist

The syntax can be subject to a fairly trivial canonicalizing pass, after which all these things are at fixed positions:

  (let ((a 3) b) (foo a)) ---canon-->  (let ((a 3) (b)) (declare) (foo a))

Now the variables are all pairs to which we can blindly apply car and cadr, the declarations are at caddr and the body forms at cdddr.

Re: Nim 1.0

#299

Post by lispm » Thu, Sep 26, 2019, 7:10 AM UTC

kazinator wrote: post #298

lispm wrote: post #297

Earlier quoted context omitted.

Syntax trees are no nonsense and go way back before Java and visitors were hip. The code walker is just another parser. It needs to know the Lisp syntax. It needs to know which parts of a LET form is a binding list, what a binding list looks like, it needs to know where declarations are and where the code body ist. It can then recognize variables, declarations, calls, literal data, etc, It needs to know the scope of…

Note that deciphering type tag info in a Lisp value can be called "parsing". Cases occur: for some values we have to chase a pointer into a heap to get more type info. A Lisp function call does "parsing". (foo 1 2 3) has to figure out dynamically whether a (lambda (&rest args)) is being called or (lambda (a b c)) or (lambda (a b &optional c (d 42)) or whatever. The #S(employee id 1 salary 95000) object also isn't an…

> Note that deciphering type tag info in a Lisp value can be called "parsing".

No. You are still operating on the level of s-expressions, a data format. The type-tag of LET is SYMBOL.

Here we have some Lisp code in the form of an s-expression:

   (let ((let 'let))
     ((lambda (let)
        (let ((let let))
          let))
      let))

All above LET have the same type tag, but in terms of syntax they have a different purpose in the form above: we have special operators, variable declarations, variable usage, data objects. I can't just car/cdr down the lists and call TYPE-OF. This always returns SYMBOL for LET.

On the level of a syntax tree we would want to know what it is in terms of syntactic categories: variable, operator, data object, function, macro, etc. Lisp source code has no representation for that and we need to determine that by parsing the code.

Re: Nim 1.0

#300

Post by lmm » Thu, Sep 26, 2019, 8:21 AM UTC

fluffything wrote: post #290

lmm wrote: post #187

Earlier quoted context omitted.

I see that as a downside, personally. It makes it a lot harder to understand what guarantees there are about with a given piece of code (rather than being able to look at the assembly and the language's own compiler, you would have to also understand C's rather odd semantics and the complex behaviour of many C compilers).

I don't follow. Nim uses C as an intermediate representation, just like many languages use LLVM-IR, Gimple, javascript, etc. If you care about the assembly a piece of code generates, you can just look at that. The generated C code that Nim emits looks like what it is: boring automatically-generated C code. If you wanted to debug the compiler, you could take a look at that, but most users don't have to.

C is a very complicated language with very complex compilers. The translation from C to assembly (under modern compilers) is hard to understand, even for "boring automatically-generated C code". Languages like LLVM-IR or Gimple are designed to be simple and translate more directly into assembly. I'd have the same complaint about javascript to a certain extent, but even though it's a full programming language it's a much simpler language than C and easier to introspect at runtime.