6 ms·

What is Symbolic Computation?

113 points by stevelosh 10y ago

agentultra 10y ago
Has anyone here read Programming in the 1990s or A Logical Approach to Discrete Mathematics? Symbolic computing is a powerful concept. How does one model something simple that we take for granted such as assignment? Here's a hint: look to Liebniz and Tony Hoare. Symbols and syntactic substitution give you powerful abstractions over expressions. Everything in Lisp is an expression. Symbols give you the ability to develop concepts built up from complex expressions. They let you reason about substitution, equivalence, etc. That's the real power: they're a tool that lets you think above the code. And as others have pointed out, Common Lisp is typed. Type-declarations, though optional, are amenable to static analysis. And the interesting thing about Lisp that I haven't explored much yet is the ability to generate a specification in a higher-level language like PVS perhaps and generate the type annotations from that. The implementation would then have to satisfy the annotations in order to validate the program. Nice article. A Gentle Introduction is a neat book.
shmerl 10y ago
In the simple sense, I understand symbolic computation as transformation of text. In more general sense, all information is based on symbols ("letters"), so transforming one information into another is a symbolic computation.
- wschroed 10y ago
  Amateur perspective here... My understanding is that it is the transformation of lists of symbols. This is one step above parsing characters/runes into more meaningful primitive data. Lisp has facilities for manipulating trees of data. The book Land of Lisp makes this distinction clear in an interesting way: they implement a text adventure, and they separate the notion of words or concepts (model) from their final string representation (view). For example, you can express a phrase with something like '(you see exits leading (exit east) , (exit west) , and (exit north)) or '(you see exits leading (series (exit east) (exit west) (exit north))) Run this through your parser for that list of lists of symbols, and you may end up with You see exits leading [east], [west], and [north]. where east, west, and north are highlighted if expressed on the console or converted into appropriate URLs if expressed in HTML. You can also imagine a potential here for language conversions. Along similar lines -- with due credit to the PAIP book -- you could separate the notion of some mathematical formula from its inputs. Do manipulations, simplifications, whatever, and THEN provide inputs. This suggests that with symbolic computation and some macros, you can assist the Lisp compiler in coming up with the speediest version of some formula. Or expression. Or template output. Not sure how to get an exact link to this comment, but look at sklogic's back-and-forth with me here for more uses of this: https://news.ycombinator.com/item?id=11589614 https://news.ycombinator.com/item?id=11589614
- amelius 10y ago
  Perhaps a better name would be "meta computation" or "abstract computation".
gue5t 10y ago
The difference between adding symbols to a language with product types (i.e. consing) and simply having algebraic data types in your language is that symbols are untyped, and so you're allowed to compare apples and oranges (they're inequal). This isn't terribly useful, as it's almost always a mistake to do it. If you do have a context in which you want to compare apples and oranges, algebraic datatypes force your hand to declare which types of things you'd like to compare across (e.g., specify that you're comparing any fruits, and that apples and oranges are fruits). This clarity helps form a clear mental model of how your software works and avoid bugs. Lisp is the "hold my beer, I know what I'm doing" of functional programming languages. It, like other languages that take this stance, should be laid to rest. Time has demonstrated that programmers do not know what we're doing, and need all the machine-provided help we can get.
- deleted 10y ago
  [deleted]
- sedachv 10y ago
  > The difference between adding symbols to a language with product types (i.e. consing) and simply having algebraic data types in your language is that symbols are untyped, and so you're allowed to compare apples and oranges (they're inequal). This isn't terribly useful, as it's almost always a mistake to do it. You are taking one trivial use case of Lisp-style symbols (enums) and completely ignoring their value as first-class identifiers that come as part of the language. > Lisp is the "hold my beer, I know what I'm doing" of functional programming languages. Lisp is not a functional programming language.
  - msdos 10y ago
    Lisp is not a functional programming language. ?
    - somethingsimple 10y ago
      It's a multi-paradigm language. You can use it for functional programming, but it's not strictly a functional programming language.
lispm 10y ago
Symbolic Computing means the computation of formulas which not only contain numbers and its operators, but also names which stand for something (a variable in some calculus, a function in some calculus, a plan operator, a note, ...). Thus McCarthy developed a language for computing with symbolic expressions: Lisp. One of the things he/they found out was that Lisp itself can be described as symbolic computation, shown by the eval procedure and by representing Lisp programs as Lisp data. But generally he had all kinds of applications in mind. One of the first applications were logic formalisms and algebra. In this case one can not only evaluate algebraic expressions, but also do computation with them... This is from an early Computer Algebra program (Macsyma), which was written in Lisp and whose development has roots back into the 60s. Though Macsyma is written in Lisp and provides a Read-Eval-Print-Loop, it does not use s-expression-based syntax. Instead it uses a syntax, which should be familiar to most people doing algebraic calculations. expr1 is a variable and we set it to a formula. (%i5) expr1:x^28 + 1; 28 (%o5) x + 1 we can sum two expressions: (%i6) expr1 + expr1; 28 (%o6) 2 x + 2 exponent: (%i7) expr1^expr1; 28 28 x + 1 (%o7) (x + 1) Let's factor an expression: (%i8) factor(expr1*3); 4 24 20 16 12 8 4 (%o8) 3 (x + 1) (x - x + x - x + x - x + 1) Subtract 1 and y from the expression: (%i9) % - 1 - y; 4 24 20 16 12 8 4 (%o9) - y + 3 (x + 1) (x - x + x - x + x - x + 1) - 1 Factor the expression: (%i10) factor(expr1); 4 24 20 16 12 8 4 (%o10) (x + 1) (x - x + x - x + x - x + 1) Subtract 1: (%i11) % - 1; 4 24 20 16 12 8 4 (%o11) (x + 1) (x - x + x - x + x - x + 1) - 1 Simplify it: (%i12) ratsimp(%); 28 (%o12) x Same idea: interactive computing with symbolic expressions, this time expressions from the domain of Algebra. The language also allows us to write programs: (%i14) myfact(n) := if n = 0 then 1 else n * myfact(n - 1)$ (%i15) myfact(10); (%o15) 3628800 It allows us to write functions for symbolic expressions, for example to implement integration, etc.
- 10y ago
diogofranco 10y ago
What an awesome resource to introduce someone to lisp. I would add "On Lisp" by Paul Graham to the final recommendations. If you don't mind quite a bit of opinionated writing, "let over lambda" can be a fun read too.
tambourine_man 10y ago
I think there's an extra "the" in the sentence: If you already know the some Lisp…
tropo 10y ago
Symbolic computation is when you evaluate a binary executable as a math expression. You might try to solve for inputs that cause a crash. It's difficult due to well-known issues with the famous halting problem, but in practice you can get useful things done.
- hcs 10y ago
  Are you thinking of symbolic execution?
eggy 10y ago
Peter Kogge's 'The Architecture of Symbolic Computers' is a great book on Lisp and Lisp machines and much more. It explains a lot of the questions this post has elicited.

113 points by stevelosh 10y ago

Has anyone here read Programming in the 1990s or A Logical Approach to Discrete Mathematics? Symbolic computing is a powerful concept. How does one model something simple that we take for granted such as assignment? Here's a hint: look to Liebniz and Tony Hoare. Symbols and syntactic substitution give you powerful abstractions over expressions. Everything in Lisp is an expression. Symbols give you the ability to develop concepts built up from complex expressions. They let you reason about substitution, equivalence, etc. That's the real power: they're a tool that lets you think above the code. And as others have pointed out, Common Lisp is typed. Type-declarations, though optional, are amenable to static analysis. And the interesting thing about Lisp that I haven't explored much yet is the ability to generate a specification in a higher-level language like PVS perhaps and generate the type annotations from that. The implementation would then have to satisfy the annotations in order to validate the program. Nice article. A Gentle Introduction is a neat book.

shmerl 10y ago

In the simple sense, I understand symbolic computation as transformation of text. In more general sense, all information is based on symbols ("letters"), so transforming one information into another is a symbolic computation.

wschroed 10y ago
Amateur perspective here... My understanding is that it is the transformation of lists of symbols. This is one step above parsing characters/runes into more meaningful primitive data. Lisp has facilities for manipulating trees of data. The book Land of Lisp makes this distinction clear in an interesting way: they implement a text adventure, and they separate the notion of words or concepts (model) from their final string representation (view). For example, you can express a phrase with something like '(you see exits leading (exit east) , (exit west) , and (exit north)) or '(you see exits leading (series (exit east) (exit west) (exit north))) Run this through your parser for that list of lists of symbols, and you may end up with You see exits leading [east], [west], and [north]. where east, west, and north are highlighted if expressed on the console or converted into appropriate URLs if expressed in HTML. You can also imagine a potential here for language conversions. Along similar lines -- with due credit to the PAIP book -- you could separate the notion of some mathematical formula from its inputs. Do manipulations, simplifications, whatever, and THEN provide inputs. This suggests that with symbolic computation and some macros, you can assist the Lisp compiler in coming up with the speediest version of some formula. Or expression. Or template output. Not sure how to get an exact link to this comment, but look at sklogic's back-and-forth with me here for more uses of this: https://news.ycombinator.com/item?id=11589614 https://news.ycombinator.com/item?id=11589614
amelius 10y ago
Perhaps a better name would be "meta computation" or "abstract computation".

gue5t 10y ago

The difference between adding symbols to a language with product types (i.e. consing) and simply having algebraic data types in your language is that symbols are untyped, and so you're allowed to compare apples and oranges (they're inequal). This isn't terribly useful, as it's almost always a mistake to do it. If you do have a context in which you want to compare apples and oranges, algebraic datatypes force your hand to declare which types of things you'd like to compare across (e.g., specify that you're comparing any fruits, and that apples and oranges are fruits). This clarity helps form a clear mental model of how your software works and avoid bugs. Lisp is the "hold my beer, I know what I'm doing" of functional programming languages. It, like other languages that take this stance, should be laid to rest. Time has demonstrated that programmers do not know what we're doing, and need all the machine-provided help we can get.

deleted 10y ago
[deleted]
sedachv 10y ago
> The difference between adding symbols to a language with product types (i.e. consing) and simply having algebraic data types in your language is that symbols are untyped, and so you're allowed to compare apples and oranges (they're inequal). This isn't terribly useful, as it's almost always a mistake to do it. You are taking one trivial use case of Lisp-style symbols (enums) and completely ignoring their value as first-class identifiers that come as part of the language. > Lisp is the "hold my beer, I know what I'm doing" of functional programming languages. Lisp is not a functional programming language.
- msdos 10y ago
  Lisp is not a functional programming language. ?
  - somethingsimple 10y ago
    It's a multi-paradigm language. You can use it for functional programming, but it's not strictly a functional programming language.

lispm 10y ago

Symbolic Computing means the computation of formulas which not only contain numbers and its operators, but also names which stand for something (a variable in some calculus, a function in some calculus, a plan operator, a note, ...). Thus McCarthy developed a language for computing with symbolic expressions: Lisp. One of the things he/they found out was that Lisp itself can be described as symbolic computation, shown by the eval procedure and by representing Lisp programs as Lisp data. But generally he had all kinds of applications in mind. One of the first applications were logic formalisms and algebra. In this case one can not only evaluate algebraic expressions, but also do computation with them... This is from an early Computer Algebra program (Macsyma), which was written in Lisp and whose development has roots back into the 60s. Though Macsyma is written in Lisp and provides a Read-Eval-Print-Loop, it does not use s-expression-based syntax. Instead it uses a syntax, which should be familiar to most people doing algebraic calculations. expr1 is a variable and we set it to a formula. (%i5) expr1:x^28 + 1; 28 (%o5) x + 1 we can sum two expressions: (%i6) expr1 + expr1; 28 (%o6) 2 x + 2 exponent: (%i7) expr1^expr1; 28 28 x + 1 (%o7) (x + 1) Let's factor an expression: (%i8) factor(expr1*3); 4 24 20 16 12 8 4 (%o8) 3 (x + 1) (x - x + x - x + x - x + 1) Subtract 1 and y from the expression: (%i9) % - 1 - y; 4 24 20 16 12 8 4 (%o9) - y + 3 (x + 1) (x - x + x - x + x - x + 1) - 1 Factor the expression: (%i10) factor(expr1); 4 24 20 16 12 8 4 (%o10) (x + 1) (x - x + x - x + x - x + 1) Subtract 1: (%i11) % - 1; 4 24 20 16 12 8 4 (%o11) (x + 1) (x - x + x - x + x - x + 1) - 1 Simplify it: (%i12) ratsimp(%); 28 (%o12) x Same idea: interactive computing with symbolic expressions, this time expressions from the domain of Algebra. The language also allows us to write programs: (%i14) myfact(n) := if n = 0 then 1 else n * myfact(n - 1)$ (%i15) myfact(10); (%o15) 3628800 It allows us to write functions for symbolic expressions, for example to implement integration, etc.

10y ago

diogofranco 10y ago

What an awesome resource to introduce someone to lisp. I would add "On Lisp" by Paul Graham to the final recommendations. If you don't mind quite a bit of opinionated writing, "let over lambda" can be a fun read too.

tambourine_man 10y ago

I think there's an extra "the" in the sentence: If you already know the some Lisp…

tropo 10y ago

Symbolic computation is when you evaluate a binary executable as a math expression. You might try to solve for inputs that cause a crash. It's difficult due to well-known issues with the famous halting problem, but in practice you can get useful things done.

hcs 10y ago
Are you thinking of symbolic execution?

eggy 10y ago

Peter Kogge's 'The Architecture of Symbolic Computers' is a great book on Lisp and Lisp machines and much more. It explains a lot of the questions this post has elicited.