I decided to write a simple tokenizer as the starting point for recursive descent parsers. Therefore, I needed nested linked lists of the sort that I can find in Lisp, Prolog and other languages. After searching the web, I came across a discussion from 2015 between andrea, def and Jehan, which convinced me that I would not find anything useful in the lists module. Therefore, I tried to implement singly linked lists on my own. However, the tokenizer became huge, 42 lines, mostly due to the linked list: 6 lines for the type declaration, 2 lines for templates, 10 lines for printing the list. I would appreciate if somebody in this forum could suggest a more terse way of solving the problem. Besides, since a lot of water has flowed under the bridge since 2015, Nim may have Lisp like lists by now. Here is my implementation of lists, with a tokenizer on top of it:
type
LLKind = enum Sym, consp
LL= ref object of RootObj
case kind: LLKind
of Sym: symb: string
of consp: car, cdr: LL
template sy*(s: string): LL= LL(kind: Sym, symb: `s`)
template `>>` (a,b: LL): LL= LL(kind: consp, car: a, cdr: b)
proc tkz*(s: string, ix: int): LL =
proc skp(s: string, i: int): int=
if i >= s.len: result= s.len
elif s[i] == ' ' : result= skp(s, i+1)
else: result= i
proc q1(s: string, i: int): int=
if i >= s.len: result= i-1
elif s[i] in {' ', ',', ';', '?'}: result= i-1
else: result= q1(s, i+1)
var i= skp(s, ix)
if i >= s.len: return nil
if s[i] in {',', ';', '?'}: return s[i..i].sy >> tkz(s, i+1)
var j= q1(s, i)
if j >= s.len: return s[i..s.len-1].sy >> nil
else: return s[i..j].sy >> tkz(s, j+1)
proc `$`*(se: LL): string=
case se.kind
of Sym: result = se.symb
of consp:
result.add("(")
var (r, ind) = (se, "")
while r != nil:
result.add(ind & $r.car)
(r, ind)= (r.cdr, " ")
result.add(")")
echo tkz(" She walks in beauty, like the night", 0) >>
(tkz("Of cloudless climes and starry skies;", 0) >> nil)
I also implemented the following version of lists in Chez Scheme:
(define (xcons x y) (lambda (m) (m x y)))
(define (xcar z) (z (lambda (p q) p)))
(define (xcdr z) (z (lambda (p q) q)))
(define (nlist i acc)
(cond ((< i 1) acc)
(else (nlist (- i 1) (xcons i acc)) )))
(define xs (nlist 10000000 '()))
(define (sum xs acc)
(if (null? xs) acc
(sum (xcdr xs) (+ (xcar xs) acc)) ))
(display (sum xs 0))
(newline)
(exit)
type
LLKind = enum Sym, Int, consp
LL= ref object of RootObj
case kind: LLKind
of Sym: symb: string
of Int: ix: int
of consp: car, cdr: LL
template sy*(s: string): LL= LL(kind: Sym, symb: `s`)
template inte(s: int): LL= LL(kind: Int, ix: `s`)
template `>>` (a,b: LL): LL= LL(kind: consp, car: a, cdr: b)
proc `$`*(se: LL): string=
case se.kind
of Sym: result = se.symb
of Int: result = $se.ix
of consp:
result.add("(")
var (r, ind) = (se, "")
while r != nil:
result.add(ind & $r.car)
(r, ind)= (r.cdr, " ")
result.add(")")
proc nlist(i: int, acc: LL): LL=
if i<1:
return acc
else:
return nlist(i-1, i.inte >> acc)
let xs= nlist(10000000, nil)
proc sum(s: LL, acc: int): int=
if s==nil: return acc
else: return sum(s.cdr, acc+s.car.ix)
echo sum(xs, 0)
Here is how I used the above program:
› time bin/ncons.x
50000005000000
bin/ncons.x 1.67s user 0.32s system 99% cpu 1.994 total