7 ms·

Thanks for the legit answer. What do you mean about reprensentational "links"?

Nevermark 2y ago
Direct links are done with addresses. When you use lists to define a data structure, you can linearize the whole structure. I.e. (... (...) ... ( ... ) ... ... ) What you can't do is have some leaf of the structure refer back to a higher point in the structure. Which is what you need to represent a graph. I.e. any point can refer to any other point. So instead, you linearize but use symbols to define a referencable point, and then to refer to it. I.e. ( ... (....) (define a ( ... )) ... ( ... ( ... a .... ) ... a ... ) ... ) In this case, "define a" indicates that the next list isn't just accessible at that location, but wherever "a" appears later. And then we reference it in more then one place later. This allows not only tree-like structures to be linearized, but graphs. Everything is still lists, and lists-of-lists, but just as symbol or number elements can appear at more than on place, now lists in the structure can be referenced in more than once place. All done with just pairs of addresses and symbols. Even numbers can be built out of pairs of addresses and symbols. I.e. a binary number: (one one zero one zero zero one zero) Of course, a friendly language is going to add lots of notation on top of address-pairs and symbols, for numbers, looping, functions, decimal number, etc. to make common code and data forms much easier to type and read than a jungle of parentheses. -- This is very much the reason we have defined and referenced symbols in all code (or complete data languages). So that linear text can describe a graph. And the same process occurs, first the text is parsed into a tree (parsing), then at some point, symbols defining references are replaced with addresses of symbol definitions (linking). The result is code can be a graph. We can have two functions that call each other, etc. Not just tree expressions.
- guerrilla 2y ago
  I see, interesting. I never really thought about LISP as low-level. It was always just something that I implement in C however I want to. You gave me a bit of a new perspective on it.
  - Nevermark 2y ago
    Yes. Low level can mean two things. Low level in implementation, meaning a representation that matches the native hardware data, code and storage conventions. The advantage being hardware-level representations are the easiest to optimize for that hardware. But also mathematically, where low level means simplest and fewest primitive abstractions that allow easy representation and manipulation of code and data. LISP's paired references and symbolic linking are very low level in that sense. The advantage here is that with so few abstractions, code and data relationships are easy to define, analyze, transform, as well as evaluate. And small numbers of simple abstractions are very easy to implement. As you obviously know from experience. I have also created several little LISPs in aid of other projects. Another language I have recreated opportunistically is FORTH. It can be viewed as a trade off between being low-level with respect to hardware, and in terms of simple abstractions. Not as flexible as LISP, but more efficient on typical hardware. Its basic abstractions consists of two dynamic lists. The first, a stream (a running list) of instructions that manipulate data on the second, a stack (a dynamic list we append and remove items from). And symbols for linking.
    - guerrilla 2y ago
      Yes, I know what you mean. I'm reading McCarthy's original paper now and what I'm noticing is that not all of it is low level in the second sense. For example, mathematically cond would be implemented with copairing/matching over left- and right-injections. Coproduct is the dual category to the product category that pairs belong to, so would be more natural than the higher-level cond, but much less efficient in practice.

Direct links are done with addresses. When you use lists to define a data structure, you can linearize the whole structure. I.e. (... (...) ... ( ... ) ... ... ) What you can't do is have some leaf of the structure refer back to a higher point in the structure. Which is what you need to represent a graph. I.e. any point can refer to any other point. So instead, you linearize but use symbols to define a referencable point, and then to refer to it. I.e. ( ... (....) (define a ( ... )) ... ( ... ( ... a .... ) ... a ... ) ... ) In this case, "define a" indicates that the next list isn't just accessible at that location, but wherever "a" appears later. And then we reference it in more then one place later. This allows not only tree-like structures to be linearized, but graphs. Everything is still lists, and lists-of-lists, but just as symbol or number elements can appear at more than on place, now lists in the structure can be referenced in more than once place. All done with just pairs of addresses and symbols. Even numbers can be built out of pairs of addresses and symbols. I.e. a binary number: (one one zero one zero zero one zero) Of course, a friendly language is going to add lots of notation on top of address-pairs and symbols, for numbers, looping, functions, decimal number, etc. to make common code and data forms much easier to type and read than a jungle of parentheses. -- This is very much the reason we have defined and referenced symbols in all code (or complete data languages). So that linear text can describe a graph. And the same process occurs, first the text is parsed into a tree (parsing), then at some point, symbols defining references are replaced with addresses of symbol definitions (linking). The result is code can be a graph. We can have two functions that call each other, etc. Not just tree expressions.

guerrilla 2y ago
I see, interesting. I never really thought about LISP as low-level. It was always just something that I implement in C however I want to. You gave me a bit of a new perspective on it.
- Nevermark 2y ago
  Yes. Low level can mean two things. Low level in implementation, meaning a representation that matches the native hardware data, code and storage conventions. The advantage being hardware-level representations are the easiest to optimize for that hardware. But also mathematically, where low level means simplest and fewest primitive abstractions that allow easy representation and manipulation of code and data. LISP's paired references and symbolic linking are very low level in that sense. The advantage here is that with so few abstractions, code and data relationships are easy to define, analyze, transform, as well as evaluate. And small numbers of simple abstractions are very easy to implement. As you obviously know from experience. I have also created several little LISPs in aid of other projects. Another language I have recreated opportunistically is FORTH. It can be viewed as a trade off between being low-level with respect to hardware, and in terms of simple abstractions. Not as flexible as LISP, but more efficient on typical hardware. Its basic abstractions consists of two dynamic lists. The first, a stream (a running list) of instructions that manipulate data on the second, a stack (a dynamic list we append and remove items from). And symbols for linking.
  - guerrilla 2y ago
    Yes, I know what you mean. I'm reading McCarthy's original paper now and what I'm noticing is that not all of it is low level in the second sense. For example, mathematically cond would be implemented with copairing/matching over left- and right-injections. Coproduct is the dual category to the product category that pairs belong to, so would be more natural than the higher-level cond, but much less efficient in practice.