#! tinylisp.py
#! Parse a lambda for correctness.
#! Question: https://codegolf.stackexchange.com/q/233453/2338
#! My answer: https://codegolf.stackexchange.com/a/233925/2338
#! checks whether some element is contained in a list.
(d C #! for "contains"
(q ((E L) #! E = the element to be checked
#! L = the list in which the element is searched
(i (e L ())
0
(i (e E (h L))
1
(C E (t L))
)
)
)
)
)
#! checks whether a list has a specified length.
#! len = expected length
#! list = list to check
(d H #! for has-length
(q ((le li) #! le = the asserted length
#! li = the list to check
(i (e () li)
(e le 0)
(H (s le 1) (t li))
)
)
)
)
#! This is the main working force here.
#! I (for "is-valid") checks (recursively) whether a lambda expression is valid
#! in a given context of defined variable names.
(d I
(q ((L X)
#! L = candidate for a lambda function,
#! X (context) = list of defined variable names
(i (e (q abs) (h L))
(i (H 3 L)
(i (C (h (t L)) X)
0
(I (h (t (t L))) (c (h (t L)) X)))
0)
(i (e (q var) (h L))
(i (H 2 L)
(i (C (h (t L)) X)
1
0)
0
)
(i (e (q app) (h L))
(i (H 3 L)
(i (I (h (t L)) X)
(I (h (t (t L))) X)
0)
0)
0
)
)
)
)
)
)
#! V (for "verify") is the entry point to call from the outside.
#! `(V (...))` returns 1 when it's a valid lambda expression, 0 when it is not.
(d V
(q (()
(L)
(I L ())
)
)
)
```
#! tinylisp.py
#! Parse a lambda for correctness.
#! Question: https://codegolf.stackexchange.com/q/233453/2338
#! My answer: https://codegolf.stackexchange.com/a/233925/2338
#! checks whether some element is contained in a list.
(d C #! for "contains"
(q ((E L) #! E = the element to be checked
#! L = the list in which the element is searched
(i (e L ())
0
(i (e E (h L))
1
(C E (t L))
)
)
)
)
)
#! checks whether a list has a specified length.
#! len = expected length
#! list = list to check
(d H #! for has-length
(q ((le li) #! le = the asserted length
#! li = the list to check
(i (e () li)
(e le 0)
(H (s le 1) (t li))
)
)
)
)
#! This is the main working force here.
#! I (for "is-valid") checks (recursively) whether a lambda expression is valid
#! in a given context of defined variable names.
(d I
(q ((L X)
#! L = candidate for a lambda function,
#! X (context) = list of defined variable names
(i (e (q abs) (h L))
(i (H 3 L)
(i (C (h (t L)) X)
0
(I (h (t (t L))) (c (h (t L)) X)))
0)
(i (e (q var) (h L))
(i (H 2 L)
(i (C (h (t L)) X)
1
0)
0
)
(i (e (q app) (h L))
(i (H 3 L)
(i (I (h (t L)) X)
(I (h (t (t L))) X)
0)
0)
0
)
)
)
)
)
)
#! V (for "verify") is the entry point to call from the outside.
#! `(V (...))` returns 1 when it's a valid lambda expression, 0 when it is not.
(d V
(q (()
(L)
(I L ())
)
)
)
```
#! tinylisp.py
#! Parse a lambda for correctness.
#! Question: https://codegolf.stackexchange.com/q/233453/2338
#! My answer: https://codegolf.stackexchange.com/a/233925/2338
#! checks whether some element is contained in a list.
(d C #! for "contains"
(q ((E L) #! E = the element to be checked
#! L = the list in which the element is searched
(i (e L ())
0
(i (e E (h L))
1
(C E (t L))
)
)
)
)
)
#! checks whether a list has a specified length.
#! len = expected length
#! list = list to check
(d H #! for has-length
(q ((le li) #! le = the asserted length
#! li = the list to check
(i (e () li)
(e le 0)
(H (s le 1) (t li))
)
)
)
)
#! This is the main working force here.
#! I (for "is-valid") checks (recursively) whether a lambda expression is valid
#! in a given context of defined variable names.
(d I
(q ((L X)
#! L = candidate for a lambda function,
#! X (context) = list of defined variable names
(i (e (q abs) (h L))
(i (H 3 L)
(i (C (h (t L)) X)
0
(I (h (t (t L))) (c (h (t L)) X)))
0)
(i (e (q var) (h L))
(i (H 2 L)
(i (C (h (t L)) X)
1
0)
0
)
(i (e (q app) (h L))
(i (H 3 L)
(i (I (h (t L)) X)
(I (h (t (t L))) X)
0)
0)
0
)
)
)
)
)
)
#! V (for "verify") is the entry point to call from the outside.
#! `(V (...))` returns 1 when it's a valid lambda expression, 0 when it is not.
(d V
(q (()
(L)
(I L ())
)
)
)
Tiny Lisp, 318
(d C(q((E L)(i(e L())0(i(e E(h L))1(C E(t L)))))))(d H(q((le li)(i(e()li)(e le 0)(H(s le 1)(t li))))))(d I(q((L X)(i(e(q abs)(h L))(i(H 3 L)(i(C(h(t L))X)0(I(h(t(t L)))(c(h(t L))X)))0)(i(e(q var)(h L))(i(H 2 L)(i(C(h(t L))X)1 0)0)(i(e(q app)(h L))(i(H 3 L)(i(I(h(t L))X)(I(h(t(t L)))X)0)0)0))))))(d V(q(()(L)(I L()))))
This defines a macro V (for verify) which can be applied to a list, and will check whether it is of the proper form as defined in the question.
This can't do any checks on a lexical level, as Tiny Lisp has no string input (and not even a string type). Therefore it is running out of competition
Here are some test cases:
------examples-from-question-----
((V (abs x (abs y (var x)))) ––→ 1)
((V (app (abs x (var x)) (var x))) ––→ 0)
((V (abs x (abs x (var x)))) ––→ 0)
----examples-from-TIO----
((V (var x)) ––→ 0)
((V (abs vv (var vv))) ––→ 1)
((V (abs xy (var fg))) ––→ 0)
((V (abs x (abs y (var x)))) ––→ 1)
((V (app (abs x (var x)) (var x))) ––→ 0)
((V (abs x (app (var x) (var x)))) ––→ 1)
((V (app (abs x (app (var x) (var x))) (abs y (app (var y) (var y))))) ––→ 1)
((V (abs x (abs x (var x)))) ––→ 0)
((V (abs x (abs y (abs y (var x))))) ––→ 0)
((V (abs (var))) ––→ 0)
---reject---------
((V uuuuuuuuu) ––→ 0)
((V (mmm hummus)) ––→ 0)
((V (abs x (var y))) ––→ 0)
((V (abs x (abs x (var x)))) ––→ 0)
((V (app (abs x (var x)) (var x))) ––→ 0)
((V (abs (var k) (var (vark k)))) ––→ 0)
((V (abs x (abs y (abs y (var x))))) ––→ 0)
((V (abs x (var x))) ––→ 1)
--------accept--------
((V (abs x (var x))) ––→ 1)
((V (abs x (abs y (var x)))) ––→ 1)
((V (abs xx (app (var xx) (var xx)))) ––→ 1)
((V (app (abs ab (app (var ab) (var ab))) (abs ab (app (var ab) (var ab))))) ––→ 1)
The last "reject" case (with the missing space) is accepted, as we are parsing this as a tiny lisp list, not as a lambda. The test cases with unbalanced parentheses can't even be run.
Here is the code formatted, and with some comments (I've extended the reference implementation of Tiny Lisp to include Python-style line comments).
(The comments all start with #! because that can be handled by my automated whitespace-and-comment-remover made for Ceylon.)
#! tinylisp.py
#! Parse a lambda for correctness.
#! Question: https://codegolf.stackexchange.com/q/233453/2338
#! My answer: https://codegolf.stackexchange.com/a/233925/2338
#! checks whether some element is contained in a list.
(d C #! for "contains"
(q ((E L) #! E = the element to be checked
#! L = the list in which the element is searched
(i (e L ())
0
(i (e E (h L))
1
(C E (t L))
)
)
)
)
)
#! checks whether a list has a specified length.
#! len = expected length
#! list = list to check
(d H #! for has-length
(q ((le li) #! le = the asserted length
#! li = the list to check
(i (e () li)
(e le 0)
(H (s le 1) (t li))
)
)
)
)
#! This is the main working force here.
#! I (for "is-valid") checks (recursively) whether a lambda expression is valid
#! in a given context of defined variable names.
(d I
(q ((L X)
#! L = candidate for a lambda function,
#! X (context) = list of defined variable names
(i (e (q abs) (h L))
(i (H 3 L)
(i (C (h (t L)) X)
0
(I (h (t (t L))) (c (h (t L)) X)))
0)
(i (e (q var) (h L))
(i (H 2 L)
(i (C (h (t L)) X)
1
0)
0
)
(i (e (q app) (h L))
(i (H 3 L)
(i (I (h (t L)) X)
(I (h (t (t L))) X)
0)
0)
0
)
)
)
)
)
)
#! V (for "verify") is the entry point to call from the outside.
#! `(V (...))` returns 1 when it's a valid lambda expression, 0 when it is not.
(d V
(q (()
(L)
(I L ())
)
)
)
```