Lawrence D'Oliveiro <
ldo@nz.invalid> writes:
On Sat, 01 Jun 2024 10:23:53 -0300, Julieta Shem wrote:
>
What's your definition of homoiconicity?
>
The AST can be represented in language objects.
That seems like an uninteresting definition. Any language whose data
objects are /insufficient/ to represent an abstract syntax tree is
clearly too weak to do much of any use. (Exercise: work out how to
represent trees in traditional Bourne shell.)
My definition, which I gave by implication earlier, is that the language
is /embedded/ in its own data values. That is, the source code that you
write is interpreted /first/ as data values, and then /those data
values/ are evaluated or compiled according to semantics assigned to
them by the language definition.
Common Lisp is homoiconic by this definition. Consider:
(defun fib (n)
(let ((a 0) (b 1))
(do ((i (1- (integer-length n)) (1- i)))
((minusp i) a)
(let ((aa (* a a)))
(psetf a (+ aa (* 2 a b))
b (+ aa (* b b))))
(when (logbitp i n)
(psetf a (+ a b)
b a)))))
This is a list of four elements: two symbols, `defun' and `fib'; and two
lists, `(n)' and `(let ...)'. If you evaluate or compile this list,
then you get a function named `fib' which computes the Nth Fibonacci
number, given a nonnegative integer N, but that's strictly secondary.
The non-Lisp homoiconic language which springs most immediately to my
mind is Tcl. Interestingly, Tcl lacks a direct analogy to Lisp's
`quote': Tcl procedures are essentially fexprs, and they always receive
their arguments unevaluated. A procedure must explicitly evaluate an
argument if that's what it wants. Complicating things a little, Tcl has
at lest /two/ evaluation schemes for its values: arithmetic evaluation
via `expr', and command evaluation via `eval' or (more commonly)
`uplevel'.
Perhaps the strongest objection to this classification is that Tcl's
only data types are strings and associative arrays: the latter lack a
literal syntax, and the former are too trivial to embed a language into
in an interesting way. Except that Tcl can reinterpret its strings in
multiple ways. This used to be in implementation detail for the
commands concerned, but Tcl 8 introduced `dual-ported' variables, which
are converted lazily between the strings which are the apparent values,
and internal formats defined by interpreter extensions. The most
interesting such interpretation is as a `list'. Tcl lists are split
into items at whitespace, except where prevented by double quotes or
matching braces.
For example:
package require math::bignum
foreach name {bits testbit add mul} {
namespace import ::math::bignum::$name
}
proc fib {n} {
set n [::math::bignum::fromstr $n]
set a 0; set b 1
set w [bits $n]
for {set i [expr {$w - 1}]} {$i >= 0} {incr i -1} {
set aa [mul $a $a]
set ab [mul $a $b]
set twice_ab [add $ab $ab]
set a [add $aa $twice_ab]
set b [add $aa [mul $b $b]]
if {[testbit $n $i]} {
set t $a
set a [add $a $b]
set b $t
}
}
return [::math::bignum::tostr $a]
}
This file contains four lists, though the third is empty. The first has
three elements: `package', `require', and `math::bignum'. The second
has four elements: `foreach', `name', `bits testbit add mul' (itself a
list of four elements), and `newline import ::math::bignum::$name' (with
some extraneous whitespace elided).
Command evaluation clearly can be seen as acting on Tcl lists.
(Internally, the interpreter actually maintains a compiled
representation of the code, but I don't see that as significant.)
Expression evaluation, somewhat sadly, does not, and isn't homoiconic in
any interesting sense.
-- [mdw]