Simple and short Lisp that encompasses all features?

Whatever is on your mind, whether Lisp related or not.
Post Reply
new(to(lisp))
Posts: 4
Joined: Tue Aug 30, 2016 8:23 pm

Simple and short Lisp that encompasses all features?

Post by new(to(lisp)) » Tue Aug 30, 2016 8:29 pm

As a hobby, I'm trying to come up with a way to display lisp code without the parentheses. My idea is to present it as a type of tree, like the following first draft, modeled after an abstract syntax tree but not allowed to branch left and right (visually), only to the right, in order to fit in a text editor. (A software text editor would be able to collapse branches just like they currently do with code folding).

Code: Select all

(+ 3 7 (* (+ 5 10))

+
├─3
├─7
└─*
  └─+
    ├─5
    └─10
This way, you would just follow the tree down, even if it had multiple branches, top to bottom and left to right.
You would immediately be able to tell how complicated a lisp is just by its vertical and horizontal size.
You would immediately be able to tell how nested a lisp is just by it's right to left size.
You would quickly be able to tell how branched a lisp is based on the number of conditionals.

However to truly make it robust, I need a starting lisp that isn't too hard to play around with, but also represents each feature.

Perhaps I need one lisp per feature instead.

I'm not a lisper, I was hoping someone good at lisp could help me get started with some arbitrary examples to use as test cases while building tree drafts.

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: Simple and short Lisp that encompasses all features?

Post by sylwester » Thu Sep 01, 2016 5:51 am

Lisp code is an AST tree so you making an alternative representation of the same. In Lisp languages lists are used to represent trees.

As a suggestion on a minimalistic lisp consider the original McCrathy spec except labels. Thus:

special forms: cond, lambda, quote
functions: cons, car, cdr, symbolp (atom), eq

That's it. WIth this you can compute all possible calculations. If you want numbers you need more primitive functions, but numbers are not interesting.
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p

new(to(lisp))
Posts: 4
Joined: Tue Aug 30, 2016 8:23 pm

Re: Simple and short Lisp that encompasses all features?

Post by new(to(lisp)) » Thu Sep 01, 2016 6:34 pm

Thank you for your reply. I will investigate what you said. It seems strange that I would need all of that to use lisp for all possible calculations, are you sure I don't need just lambda?

Code: Select all

(define (if p a b) (p a b)))
(define (true a b) (a)) <-- note the parens around a
(define (false a b) (b)) <-- note the parens around b

(if true (lambda () 2) (lambda () 4))
Regardless, my idea has evolved since I made that post (it took a while to get approved as my first post)

Below are the results of further brainstorming. I believe this idea hasn't been done before for lisp, I'm somewhat sure it's a good idea, but what remains to be discovered is if it's technologically possible to implement.

since this forum does not support expanding the code sections, here is a picture
Image

Code: Select all

; the idea is that the most readable form of lisp may be attainable by first converting lisp into an unambiguous abstract syntax tree, and then performing formatting operations on that tree to display the same code in a syntactically-sugary way

; example 1
; conventional lisp form
(sqrt (+ (* (- (/ (+ 1 2) (+ 2 3)) 10) 2) 1))

; idealized human readable form (the goal)
sqrt(1+(2*(10-(1+2)/(2+3))))

; step 1, convert the lisp into a form that exposes the number of arguments and their evaluation order, step by step, unambiguously by following the abstract syntax tree structure
<list> ┬ sqrt
       └ <list> ┬ +
                ├ 1
                └ <list> ┬ *
                         ├ 2
                         └ <list> ┬ -
                                  ├ 10
                                  └ <list> ┬ /
                                           ├ <list> ┬ +
                                           │        ├ 1
                                           │        └ 2
                                           └ <list> ┬ +
                                                    ├ 2
                                                    â”” 3

; step 2, take the above tree structure, apply syntactic sugar to it in order to compact it into a human-readable tree form below (only one tree level for this example)
─ sqrt(1+(2*(10-(1+2)/(2+3))))

; example 2

; conventional lisp form
(define (factorial n)(if (<= n 1)1(* n (factorial (- n 1)))))

; idealized human readable form (the goal)
factorial(n), if n <= 1, then n = 1, else n = n * factorial(n - 1)

; step 1, convert the lisp into a form that exposes the number of arguments and their evaluation order, step by step, unambiguously by following the abstract syntax tree structure
<list> ┬ define
       ├ <list> ┬ factorial 
       │        └ n         
       └ <list> ┬ if          
                ├ <list> ┬ =
                │        ├ n
                │        └ 1
                ├ 1           
                └ <list> ┬ *  
                         ├ n
                         └ <list> ┬ factorial 
                                  └ <list> ┬ -
                                           ├ n
                                           â”” 1

; step 2, take the above tree structure, apply syntactic sugar to it in order to compact it into a human-readable tree form below (four tree levels for this example, one for each distinct abstract action as far as the human is concerned)
┌ factorial n
├ if n <= 1
├ then n = 1
â”” else n = n * factorial(n - 1)

; by editing this tree, you would be editing the expanded AST underneath, and therefore editing the same conventional lisp without knowing it
; in the end, when saving the file, the code should be stored in conventional lisp

new(to(lisp))
Posts: 4
Joined: Tue Aug 30, 2016 8:23 pm

Re: Simple and short Lisp that encompasses all features?

Post by new(to(lisp)) » Thu Sep 01, 2016 6:56 pm

To clarify my point, and I hope this does clarify things:
To achieve the idealized human-readable form when we are writing and reading lisp code, it is assumed that it's extremely complicated to take conventional lisp code, such as

Code: Select all

(sqrt (+ (* (- (/ (+ 1 2) (+ 2 3)) 10) 2) 1))
and allow a user to read it and write it as

Code: Select all

sqrt(1+(2*(10-(1+2)/(2+3))))
(not just for this case, but for any valid lisp code)

All of this needs to be possible while still saving code in the conventional lisp style in the background.
The reason it's so complicated to implement is because a user could easily type ( and ) characters, or add more operators, and the software that needs to turn that into valid lisp code would be too easily confused without an intermediate step.

The solution I'm suggesting is an intermediate step of turning the conventional lisp code into a full abstract syntax tree which has 0 parentheses in the tree, and only one operator per branch.

Code: Select all

<list> ┬ sqrt
       └ <list> ┬ +
                ├ 1
                └ <list> ┬ *
                         ├ 2
                         └ <list> ┬ -
                                  ├ 10
                                  └ <list> ┬ /
                                           ├ <list> ┬ +
                                           │        ├ 1
                                           │        └ 2
                                           └ <list> ┬ +
                                                    ├ 2
                                                    â”” 3
this tree is then reformatted into the readable code, such as

Code: Select all

sqrt(1+(2*(10-(1+2)/(2+3))))
to the end user.

the end user may then write more operators, like instead of 1 + 1, they type 1 + 2 * 3, and a new branch is created in the tree, in the background, because a new operator was introduced (and only one operator can be on one branch). There would be unique rules for mathematical operators, such as identical operators can be repeated on the same branch (1 + 2 + 3 + 4 + 5 would just turn into + 1 2 3 4 5 on the same branch).
Parentheses could be typed by the end user, and turned into another branch, or leaf, on the abstract syntax tree in the background.

In summary, by converting lisp into a tree, then the tree into human readable syntactic sugar, you don't actually impose any character-typing limitations on the user, and you don't actually change the syntax of lisp, you merely format it differently, kind of like displaying data to a user in the form of a table, rather than a comma separated list. Different formatting can help readability. It's primarily useful for representing data structures. In lisp, code is data. That's why I feel this solution is unique to lisp.

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: Simple and short Lisp that encompasses all features?

Post by sylwester » Sat Sep 03, 2016 2:33 pm

new(to(lisp)) wrote: It seems strange that I would need all of that to use lisp for all possible calculations, are you sure I don't need just lambda?
Lambda calculus and all languages that have closures you can do all calculations and data manipulations and representations with closures (evaluated lambdas). McCharthys lisp was dynamicly bound and thus an evaluated lambda has no closure and thus it's by itself not turing complete. Lexical languages are somewhat easier to compile while dynamicly bound languages are easier to interpret and I have no idea which direction you are going.

Know that the only lambda implementation is extremely hard to expand or make useful programs with. When I researched before making my Lisp, Zozotez, I noticed that a language needed more than the primitives to be turing complete in order to be successful. I would need primitives that decode / encode nested closures to read or print and that is less trivial than to implement the dynamic eager language with all the needed primitives for it to be useful.

Looking at your post it seems you are trying to take the beautiful lisp syntax and make it ambigious by introducing operator precedens and infix. If you want something like that why don't you choose an algol dialect where it has been a feature since the 60s? Looking at the "idealized human readable form" you might be better off programming the algol dialect "Python".

Also note there have been countless failed attempt at removing the magic parentheses:
Sweet expressions: http://readable.sourceforge.net/
cl-2dsyntax: http://hyperprostor.g6.cz/lisp/cl-2dsyntax/

Both of those are CL projects but they could easily be ported to Scheme, but the interest for such syntax is low amongst lispers.
A lisp with a few less parentheses are ok though. Paul Graham's Arc and Rich Hickey's Clojure did this.
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p

new(to(lisp))
Posts: 4
Joined: Tue Aug 30, 2016 8:23 pm

Re: Simple and short Lisp that encompasses all features?

Post by new(to(lisp)) » Sat Sep 03, 2016 8:13 pm

I'm trying to create an unambiguous lisp format, which models to lisps Abstract Syntax Tree in the background, but in the foreground doesn't leave anything important hidden to the programmer as he's writing or reading the code.

This would not be a new language, it's a new formatting for the same language, lisp (probably common lisp or something)
The difference is that when you format an existing language differently, it's displayed differently to the user, but still maintains the same exact source code.

for example the "if" syntax in common lisp is
(if test-form then-form else-form)

this is human readable, somewhat, until you actually write it and read it later, then mental gymnastics has to go on.
and you have to go to the docs to see it in this readable form, otherwise again, mental gymnastics (memorization recall)

imagine if it just displayed it to you when you wrote "if"

if <- typed by the user
test expression <-typed by the software which formats the lisp for the user in a friendly way, the "test expression" is an in-line comment prefixed before the code and cannot be edited or removed, it's just inert, it doesn't affect the source code, it is just eye candy for the user
then <-typed by the software which formats the lisp for the user in a friendly way, the "then" is an in-line comment, it doesn't affect the source code, it is just eye candy for the user
else <- typed by the software which formats the lisp for the user in a friendly way, the "else" is an in-line comment, it doesn't affect the source code, it is just eye candy for the user

the primary reason this fails in other languages and complicates the syntax is because it's not inert syntax, it actually means something in python if you type "then", and consequently you can't use "then" as a function name or something
in this new formatting idea, comments would be a different color, have a bold font, or some other distinction, and would automatically be read-only, so there is a rich helping-syntax without actually complicating the source code

the abstract syntax tree of lisp would be used to generate the new format, so that it can be converted back to lisp, minus the inert comments, at save-time or run-time.

to be clear I'm not saying you can't decipher lisp code as it currently is, just that you have to perform a lot of mental gymnastics, especially in complicated code, just to understand the syntax. this isn't really due to parentheses I don't think, it's due to a uniform syntax in lisp blending everything together so well, with textual, inert hints, at what each piece does, you can make it human-readable. since these hints would not be part of the languages syntax, they dont get in the way or cause lisp to lose its power.

kazinator
Posts: 1
Joined: Thu Feb 08, 2018 6:57 pm

Re: Simple and short Lisp that encompasses all features?

Post by kazinator » Thu Feb 08, 2018 7:16 pm

You don't need simulated (or real) line drawing characters to achieve the layout. Just indentation.

Original:

Code: Select all

(+ 3 7 (* (+ 5 10))
One node per line:

Code: Select all

(+ 3
   7
   (* (+ 5
         10))))
Or, even more expanded vertically like your example:

Code: Select all

(+             ;; +
   3           ;; ├─3
   7           ;; ├─7
   (*          ;; └─*
     (+        ;;   └─+
        5      ;;     ├─5
        10)))) ;;     └─10
We haven't changed the syntax at all, just whitespace.

Literally, the atoms in the left diagram, a valid S-exp are almost in the same relative positions as in the line drawing diagram on the right.

Post Reply