Function: (count-up xs) : Returns a list of lists of the form (x n), where x is an element of xs and n is the number of times x occurs in xs. This list is sorted to present most frequent items first (otherwise it would be sorted pseudorandomly).
Useful for, well, counting things up; I've used this to count word and letter frequencies, calculate the totient function, create a couple of histograms, compute the number of distinct permutations of a list, help print out a number's prime factorization, test the randomness of supposedly random functions, and do some other things.
(def count-up (xs)
(let u (table)
(each x xs
(++ (u x 0)))
(sort (compare > cadr) (tablist u))))
Ah, that's a fun one. Could use counts to get a table in vanilla Arc, except that it hard-codes recursion on cdrs, so it won't work for strings. From arc.arc:
(def counts (seq (o c (table)))
(if (no seq)
c
(do (++ (c (car seq) 0))
(counts (cdr seq) c))))
It's also easy to not notice the built-in sortable from srv.arc:
(def sortable (ht (o f >))
(let res nil
(maptable (fn kv
(insort (compare f cadr) kv res))
ht)
res))
Function: (mapn f a b . xs) : "map n". Primary usage: (mapn f a b) = (map f (range a b)). Extra argument pairs will yield nested applications of 'mapn, with f applied to a kind of product of all ranges. The implementation and a demonstration will make this clearer:
(def mapn (f a b . xs)
(if no.xs
(map f (range a b))
(mapn [apply mapn (fn args (apply f _ args))
xs]
a b)))
arc> (mapn square 1 10)
(1 4 9 16 25 36 49 64 81 100)
arc> (mapn list 1 3 20 22)
(((1 20) (1 21) (1 22)) ((2 20) (2 21) (2 22)) ((3 20) (3 21) (3 22)))
'mapn is very nice for testing out a function on a numerical range, especially repeatedly. Also, given the 'grid function, we can construct two-dimensional tables of a function extremely easily:
Function: (accumulate comb f xs init next done) : A function useful for expressing many accumulation patterns: mapping, summation, products, and others. You use next to iterate over xs until xs is done, and the results are mapped by f and comb-ined one by one with init. For example:
(map f xs) = (rev:accumulate cons f:car xs nil cdr no)
(factorial n) = (accumulate * idfn 1 1 inc [> _ n])
(rev xs) = (accumulate cons car xs nil cdr no)
(range a b) = (rev:accumulate cons idfn a nil inc [> _ b])
(len xs) = (accumulate + [idfn 1] xs 0 cdr no)
(sum f a b) = (accumulate + f a 0 inc [> _ b])
(sumlist f xs) = (accumulate + f:car xs 0 cdr no)
(mapn f a b) = (rev:accumulate cons f a nil inc [> _ b])
Macros: (fromfile f . body), (tofile f . body), (ontofile f . body)
'fromfile executes body in a context where stdin is an input-port that reads the contents of the file described by the string f; it closes the port afterwards. 'tofile is similar, but instead binds stdout so that it writes to the file f. 'ontofile is similar to 'tofile, except that output is appended to the file f.
These macros, while not strictly necessary given the existence of 'w/infile, 'w/outfile, and 'w/appendfile (which are implemented almost identically), make it nicer to read from and write to files. There are several macros in Arc that come in pairs, one binding a variable and the other supplying a usually anaphoric default variable name. Examples: 'rfn and 'afn, 'each and 'on, 'iflet and 'aif (although these aren't quite identical). I think this is a good pattern.
'tofile and 'ontofile are especially useful when you want to write to a file using 'pr, 'prn, 'prs, etc., none of which take an optional output-port argument; alternatives would be rebinding stdout using 'w/stdout, or collecting output with 'tostring and 'disp-ing it all at once (which may not work as a substitute if it's important that output be generated incrementally).
Macro: (xloop var-vals . body) : Extremely useful macro to create and use a local recursive function named 'next. var-vals is a list of alternating variables and initial values (in the style of the built-in Arc 'with macro), and body is the body of the function (which probably contains calls to 'next). To illustrate, we shall calculate the factorial of n:
(xloop (i 1 total 1)
(if (> i n)
total
(next (+ i 1) (* total i)))))
This macroexpands to:
((rfn next (i total)
(if (> i n)
total
(next (+ i 1) (* total i))))
1 1)
This is my go-to when I want to write a function that needs looping or general recursion. I use this macro all the time:
$ grep -c xloop a general-poly.arc
a:38
general-poly.arc:18
Credit for xloop's current form goes to aw: http://awwx.ws/xloop0 That link also contains an implementation, which I will reproduce here for convenience (though, for consistency, I have renamed the first argument to var-vals, which I hope doesn't irritate aw):
(mac xloop (var-vals . body)
(let w (pair var-vals)
`((rfn next ,(map car w) ,@body) ,@(map cadr w))))
My 'xloop at http://github.com/rocketnia/lathe has a more convenient interface at the expense of overall simplicity. It supports the usual syntax, but it also lets you leave off the parentheses as long as the things you're binding to are non-nil, non-ssyntax symbols, like most variable names are.
(xloop i 1 total 1
(if (> i n)
total
(next (+ i 1) (* total i))))
The restriction on the bindings makes it possible to figure out where the body starts.
Gosh no! Most everything I write is based on code I've seen elsewhere; with either what I hope will be an incremental improvement or else with some minor change to make it fit a personal preference. For me to complain because other people then share their own improvements would be rather foolish... :)
Here are a bunch of printing functions, which I frequently use in combination.
Function: (prsn . args) : Prints the elements of args separated by spaces, then prints a newline. Extremely handy for debugging: add in (prsn a b c) when you want to see the state of a,b,c. Equivalent to the built-in prs, except this also prints a newline.
(def prsn args (apply prs args) (prn))
Function: (pad x wanted-len (o side 'left) (o pad-char #\space)) : Coerces x to a string, then adds enough pad-char characters on the left or right side to make x be wanted-len long. Returns the resulting string. If x is longer than wanted-len, this will throw an error.
Very handy for printing out a table of data, especially in conjunction with prsn. Also good for, e.g., printing out dates which you want to be constant-length. Look at this beautiful table:
arc> (for i 6 15 (prsn (pad i 2) (pad fib.i 3) (pad (fib:* 2 i) 6)))
6 8 144
7 13 377
8 21 987
9 34 2584
10 55 6765
11 89 17711
12 144 46368
13 233 121393
14 377 317811
15 610 832040
nil
(def pad (x wanted-len (o side 'left) (o pad-char #\space))
(zap string x)
(let padding (newstring (- wanted-len len.x) pad-char)
(case side
left (string padding x)
right (string x padding))))
Of course, in that demonstration, I found those values 3 and 6 by experiment and having 'pad throw errors until I increased wanted-len enough. This may suck for you; therefore, here is a function to print out a whole grid:
Function: (grid xses (o strict nil)) : Prints out xses, which should be a list of lists, in a grid; that is, it pads each element enough that all elements in each column are the same width. If strict is t, then all columns will be the same width. Works even if lists are different length. Note that my definition uses 'pad and 'prsn. Illustration with Pascal's triangle, first without strict, then with:
Function: (cp) : copy-paste. Runs the code in your clipboard. Write code in your favorite text editor, select it, copy it, then go to the REPL and type in (cp) instead of pasting it in. Useful when a) your terminal doesn't like it when you paste in multilined input or b) you don't want to clutter up your REPL interactions. Example implementation and usage:
(def cp () (map eval (readall:clipboard)))
;Now I redefine a couple of functions (e.g. to add or remove printlining)
; and copy the new definitions, then use (cp) at the REPL.
arc> (cp)
*** redefining int-nthroot
*** redefining cint-nthroot
*** redefining cint-omega
(#<procedure: int-nthroot> #<procedure: cint-nthroot> #<procedure: cint-omega>)
Obviously, the above requires a (clipboard) function, which is useful in its own right:
Function: (clipboard) : Returns the clipboard as a string. Useful when you want to give your program a string from somewhere (maybe capture it with (= x (clipboard)) and then use it), and your alternatives are a) pasting it in literally (which requires escaping), b) pasting to a file and reading it in, and c) trying to call (readline) a bunch of times or something. Also useful in implementing (cp).
(clipboard) probably takes a platform-specific system call. On Mac OS X, the shell command "pbpaste" prints out the clipboard, so I have it defined as:
(def clipboard () (tostring:system "pbpaste"))
(In fact, since I use "pbpaste" at the terminal, I find the name 'pbpaste more mnemonic.) It seems that on Linux, you can install a utility named 'xclip', and 'xclip -o' outputs the clipboard. I don't know about Windows. Alternatively, if you're using the Racket GUI libraries, there's some platform-independent way to get the clipboard string. And, for completeness, I'll mention pbcopy, which isn't as useful:
Function: (pbcopy x) : Coerces x to a string and sets the clipboard to that string. Named after the MacOSX utility. Useful mainly so I can add two spaces to each line when pasting code into this forum:
Implementation: To avoid issues with escaping and stuff, what you probably want to do is write the string to a temporary file, then do "cat tmpfile | pbcopy" (where "pbcopy" might be replaced with "xclip" on Linux and whatever on Windows).
(def pbcopy (s)
(let f (tmpfile)
(w/outfile gf f (disp s gf))
(system:string "cat " f " | pbcopy")
rmfile.f))
(def tmpfile ()
(let u (string "/tmp/arctmp" (rand-string 10))
(if (file-exists u)
(tmpfile)
u)))
You could modify that function directly, by sticking (if (eq? sym '.) '. <proceed-as-usual>) in front of it. Or, if the Anarki guys have been through it, I'm guessing they added a hook at the beginning of that function, and wrote another function that would make it easy to add things to the hook. Look for 'expand-ssyntax in ac.scm, and follow where it leads you.
Changing ac.scm's 'expand-ssyntax will make Arc's 'ssyntax predicate incorrect. The exception should be added in here, where there happen to already be a few exceptions that are currently meaningless:
(define (ssyntax? x)
(and (symbol? x)
(not (or (eqv? x '+) (eqv? x '++) (eqv? x '_)))
(let ((name (symbol->string x)))
(has-ssyntax-char? name (- (string-length name) 1)))))
(This is quoted from Anarki 'cause the source is handier for me right now.)
Note, however, that calling Arc's 'ssexpand will expand a symbol regardless of whether it's an exception. I don't know whether this is a bug or not; the workaround is just to check with 'ssyntax first if it matters.
Thanks for the tip, this is working well. The only minor issue I'm still dealing with on this is how to strip the dot of all special meaning except in the context of rest parameters.
By adding the dot ssyntax exception in ac and not applying the read-normal macro from the OP to #\., I've gotten this to work so long as dot is inside the scheme bars:
; Dot treated as a symbol when inside the bars
arc> (= |.| 2)
2
arc> (is (+ 1 1) |.|)
t
; It still works in the rest parameter context
arc> (def foo (x . args)
`(,x ,@args d))
#<procedure: foo>
arc> (foo 'a 'b 'c)
(a b c d)
; But it doesn't work as a symbol without the bars.
; Note that (read-normal #\.) can make this work but
; it breaks the rest parameter case.
arc> (= . 2)
Error: "map: expects type <proper list> as 2nd argument,
given: 2; other arguments were: #<procedure:ac-niltree>"
Interesting... very interesting. I have to say I like it. I suppose it makes theoretical sense: you don't need numbers to write a Lisp that can do 'eval, and they could in fact be implemented as whatever you like. Integers are only fundamental because they're fundamental to the machines that implement everything. And that is so elegant:
(/ (+ -.b (sqrt:- b.b 4.a.c))
2.a)
It's very reminiscent of using juxtaposition, as in "4xy", to represent multiplication; also of using little dots, as in "4·x·y". And, notwithstanding my dislike for using '+ for concatenation (which I could perhaps get used to), (3 '(a b c)) is quite nice--and it even fits the "juxtaposition as multiplication" rule. (We have a macro called n-of which does this too (though it multiply-evaluates), but it's nice when you don't need that.)
The only possible problem I can think of is difficulty of (efficient) implementation. Methinks a good Arc compiler will have to be extremely good with type inference, or perhaps a JIT compiler.
Other thing: Regarding the design of things that "simulate algebraic fields": Note that this might eventually lead to conflicts if you create a general-purpose algebra system, in which objects like polynomials are built from lists or hash tables, and you expect to be able to multiply diverse things with (poly n) [where poly = polynomial and n = integer], because that would require overriding lookups, which might destroy the functions that work with those objects. However, lists could be accessed anyway with car and cdr, and perhaps we should make a 'hash-ref function that will work no matter what. (A more heavy-duty solution might be to tag, or 'annotate, objects. Perhaps I should try that.)
It's very reminiscent ... also of using little dots, as in "4·x·y".
Wow, I missed that. XD I was mainly thinking of juxtaposition.
The only possible problem I can think of is difficulty of (efficient) implementation.
Yeah, certainly an issue. Optimized code can use (* 4 a c) like usual though.
Other thing
Custom types should already use 'annotate when they need custom 'defcall behavior, right? For instance, if ax^2+bx+c is built using (annotate 'poly (list a b c)), you can index it using rep._.i and call it using _.i. If you're talking about having polynomial calls do polynomial multiplication instead when they're called, then you may have a design conflict (although I think the cases are mostly distinguishable here).
Anyway, as you sorta suggest, the multiplication of diverse things is still a bit weird in general. The concern I have in mind is that multiple dispatch rears its head. I think I'd end up doing something like this (untested!):
; Extend numbers so that they use '* as their call behavior.
(mac defmulttype type
`(defcall ,type form (apply * form)))
defmulttype.int
defmulttype.num
; Define another variable bound to '* so we won't lose track of it
; when we redefine it.
(= *-base *)
; Define an extensible binary version of '*. This part's rudimentary
; for laziness's sake.
(def *-binary (a b)
(err:+ "Can't multiply " a " by " b "."))
(def fn-defmult (test-a test-b body)
(zap testify test-a)
(zap testify test-b)
(let old-*-binary *-binary
(= *-binary (fn (a b)
(if (and do.test-a.a do.test-b.b)
(do.body a b)
(do.old-*-binary a b))))))
(mac defmult (test-a test-b . body)
`(fn-defmult ,test-a ,test-b (fn (a b) ,@body)))
; Define '* in terms of '*-binary. It's left-associative.
(def * args
(case args nil 1
(reduce *-binary args)))
; Make multiplication with a nonnegative integer on the left use '+.
(defmult [and (isa _ 'int) (<= 0 _)] [do t]
(apply + (n-of a b)))
; Provide the multiplication cases that used to be built in,
; overriding the integer rule in the process.
(defmult number number
(*-base a b))
This gives just enough multiple dispatch for people to put (defmult [isa _ 'poly] [isa _ 'int] ...) in one library and (defmult [isa _ 'poly] [isa _ 'snargle] ...) in another one, and they can use (defmult 'poly [do t] ...) if they only need single dispatch.
I'd also give an actual example of using polynomials, but I'm out of time. :-p It would have just been an exploration of having (defmult [isa _ 'poly] isa-poly-arg ...) and (defmult [isa _ 'poly] [isa _ 'poly] ...) be separate cases.
;(pmul-deg m) returns a function that multiplies polynomials
; and throws out all terms with degree > m
;xs is a list of polynomials
((pmul-deg 5) (car xs) (cadr xs))
I do not want this to be interpreted as an assoc-list.
if x doesn't evaluate to a function, hash table, macro, (or whatever else is allowed as a first element), then as a last resort, we interpret the expression as a plain list
In your example, the first expression evaluates to a function, so the normal rules would apply as usual.
I see. I'll mention first that I wouldn't find this feature useful myself, and would likely be irritated that certain things didn't turn out to be errors. However, here's something I see as a problem that you can probably appreciate:
(1 2 3). Arc evaluates this expression. The car is a number. Therefore, this is interpreted as the literal list (1 2 3).
((1 2 3) 1). By the above, the car of this expression evaluates to the list (1 2 3). This, applied to the argument 1, should give us the second element (the 1th element with zero-origin indexing) of the list (1 2 3), which is 2.
(((1 2 3) 1) 6). Following the above method of evaluation, the car of this expression evaluates to 2, so we get (2 6), which you say should evaluate to the literal list (2 6). This is, of course, quite different from the list (((1 2 3) 1) 6), which is probably what someone who writes literal lists according to your system would expect. I don't think it's possible for (((1 2 3) 1) 6) to be interpreted as a literal list without throwing the Arc "data structure in functional position is interpreted as a lookup" model out the window.
For that matter, I think would already be pretty weird that, given that xs is (1 2 3), (xs u) will be either an element of xs (if u happens to be a number) or a literal list (if u isn't a number).
So, either you have a "literal lists" rule that works for nesting lists most of the time--just not when one of the lists happens to be length 2 and the cadr is a number--or you have to give up the "xs is a list --> (xs n) is the nth element of xs" rule. Perhaps you could restrict it to constructing lists of constant depth; that would be a consistent, easily understood rule that wouldn't infringe on list lookups, although it still would make (xs n) be a drastically different type of object depending on what n was, and I still wouldn't like it or find it useful.
Pedagogical digression:
You say this about using quasiquote in `((,a ,b) (,c ,d)):
> Too cumbersome and somewhat confusing. Actually I think subconsciously I want to get rid of these symbols when ever possible.
Then I think you are ignorant. My intent is not to insult you; I intend this as a statement of fact, and as implied advice (that you should learn more). Look at what quasiquote allows you to do:
`((,a ,b) (,c ,d)) ;evaluate keys and values in assoc-list
`((,a b) (,c d)) ;evaluate keys, not values, in assoc-list
`((a ,b) (c ,d)) ;evaluate values, not keys, in assoc-list
`(,(a b) ,(c d)) ;construct list of two function calls
By putting in a quasiquote and adding or not adding commas in various positions, you can specify any arbitrary pattern of evaluation for the list ((a b) (c d)). And I assure you, all of these are useful at times; above, I have merely listed ones that are common enough patterns for them to have names; attempting to define the language so that the compiler will always find the correct pattern and you'll never need to use quasiquote is a bad idea. And don't even try writing more than the most basic macros without quasiquote--it's like working without rlwrap, except that can be somewhat remedied by editing a file and defining (l) to load that file.
(Again, I don't intend to insult or flame you. I do intend to flame this idea, because I think it's bad.)
Philosophical digression:
Note, by the way, that the "data structures in functional position are interpreted as lookups" rule is pretty justifiable from a Lisp point of view. You could implement data structures as functions:
(def my-cons (a b)
(fn (x)
(case x
car a
cdr b
(if (isa x 'int)
(if (is x 0)
a
(b (- x 1)))
(err "Can't do this.")))))
(def my-car (x)
x!car)
(def my-cdr (x)
x!cdr)
arc> (= x (my-cons 1 (my-cons 2 (my-cons 3 nil))))
#<procedure: my-cons>
arc> (x 0)
1
arc> (my-car x)
1
arc> (my-car (my-cdr x))
2
arc> (x 1)
2
arc> (x 2)
3
The only issue is printing. Here's an example implementation:
It isn't perfect, because that 'print function will apply any function to the symbol 'type, which may cause errors. You need some access to the implementation of primitive operators to do this right. But, of course, the language designer has that power, and could quite plausibly have implemented conses and tables as functions, and given 'pr what it needs. So, it makes sense from a very-basic-Lisp point of view that "(the-list-xs 2)" could be a function call that yields the second element of the-list-xs.
I'll add that numbers and atoms are... atomic. Pure and indivisible, the building blocks that you can make everything else in Lisp with. I'm fine with compound data structures being functions, because they can be implemented with functions as featureful as you want, but I think atoms should be simple, basic pieces.
I was going to say something almost just like this, so kudos. ^_^ However, I cut myself off 'cause I realized that in someone's mind, 6 could primarily be a function that constructs lists that begin with 6, and only incidentally has useful behavior with '+, '-, etc. :-p To be fair, that's pretty silly, and you have other points that are good regardless.
I just noticed none of your alist examples work with the atoms-imply-lists thing -- unless you ditch list-indexing, like (xs 0). That is, even if a, b, c, and d are all atoms,
((a b) (c d))
would not be an explicit alist, since
(a b) == (list a b)
and
(c d) == (list c d)
Thus,
((a b) (c d)) == ((list a b) (list c d))
which throws an error since (list c d) isn't a proper index (i.e., isn't a number).
Even if you could write alists that way, you'd be restricted to only those with atom cars. Personally, I can't think of the last time I needed a literal alist. If I wanted to write them that much, couldn't use quote, and couldn't bare to use list, I'd probably just do
If [] wasn't already used for lambdas, I could've suggested using it as a raw-list literal. [1 2 3] wouldn't be that bad.
I don't think odd parentheses like [...] are substantially more convenient than operator applications like (list ...). In fact, when editing in a bare-bones text editor, it's a slight pain to have to figure out whether )))]))]))) is the right combination of brackets. :-p
That doesn't mean it's a bad idea altogether. I think Clojure probably has the best practical use of brackets. It uses [] for literal lists just like what you're talking about, but it also generally uses [] brackets wherever there's no operator-and-body format that needs highlighting and indenting. They're used for argument lists, for instance. I haven't heard of someone setting up an editor to take advantage of that consistency, but I'd be surprised if that wasn't the reason for it. ^_^
(Which is reason against PLT's use of [], but doesn't affect arc's chosen use.)
Incidentally [] has one major advantage over (): it doesn't require pressing the shift key every single time. In my vim and emacs I've swapped the two sets of keys in lisp mode.
Which is reason against PLT's use of [], but doesn't affect arc's chosen use.
Hmm? I don't provide any reasons against Racket's claim that "Using square brackets in a few key places makes Racket code even more readable." In fact, I think it does aid a bit in readability, but it doesn't help when my goal is to correct sloppy brackets. XD
What I am saying is that Arc's [+ 1 _] syntax is about as convenient as (f- + 1 _) or (f-:+ 1 _). Arc also shares the ))]))) issue, a little. It would be more noticeable if more operators accepted functions as their last argument rather than their first argument.
Incidentally [] has one major advantage over (): it doesn't require pressing the shift key every single time. In my vim and emacs I've swapped the two sets of keys in lisp mode.
You mentioned this a while ago, so I've been using only [] in my languages-in-progress. ^_^ It also helps that I begrudge () and {} for looking too similar to each other. :-p The one thing I'm worried about is that ] and [ might be less distinguishable from each other than ) and ( are.
It would be more noticeable if more operators accepted functions as their last argument rather than their first argument.
Yeah, but they don't. Lisp idiom tends to be to put the values being operated upon last, and with good reason: you want to put last the arg most likely to be a temporary. Otherwise you risk separating function calls from their args. Compare:
Since there's this major structural constraint I think any dispatch in lisp should be on the type of the last arg. (http://arclanguage.org/item?id=12646)
Hmm, it would involve reimplementing eval inside arc. So far the arc compiler simply converts arc expressions to scheme expressions. You can't evaluate anything then.
Guess I should've mentioned this in my first post. People shouldn't be getting hung up on it. The diff was in this function:
; call a function or perform an array ref, hash ref, &c
; Non-fn constants in functional position are valuable real estate, so
; should figure out the best way to exploit it. What could (1 foo) or
; ('a foo) mean? Maybe it should mean currying.
; For now the way to make the default val of a hash table be other than
; nil is to supply the val when doing the lookup. Later may also let
; defaults be supplied as an arg to table. To implement this, need: an
; eq table within scheme mapping tables to defaults, and to adapt the
; code in arc.arc that reads and writes tables to read and write their
; default vals with them. To make compatible with existing written tables,
; just use an atom or 3-elt list to keep the default.
(define (ar-apply fn args)
(cond ((procedure? fn)
(apply fn args))
((pair? fn)
(list-ref fn (car args)))
((string? fn)
(string-ref fn (car args)))
((hash-table? fn)
(ar-nill (hash-table-get fn
(car args)
(if (pair? (cdr args)) (cadr args) #f))))
; experiment: means e.g. [1] is a constant fn
; ((or (number? fn) (symbol? fn)) fn)
; another possibility: constant in functional pos means it gets
; passed to the first arg, i.e. ('kids item) means (item 'kids).
- (#t (err "Function call on inappropriate object" fn args))))
+ (#t (ac-niltree (apply list fn (ar-nil-terminate args))))))
It works the same as any other list/table/string referencing in Arc. Things that look like function calls are compiled to (ar-apply f args), generally speaking (see ac-call), so this logic happens at runtime. Thus,
arc> (let f [+ _ 1] (f 5)) ; evals as fn call
6
arc> (let xs '(a b c) (xs 0)) ; evals as cons ref
a
arc> (let xs "abc" (xs 0)) ; evals as string ref
#\a
arc> (let h (obj a 1 b 2) (h 'a)) ; evals as table ref
1
In standard Arc:
arc> (let x 'atom (x 5)) ; defaults to #t clause
Error: "Function call on inappropriate object atom (5)"
With the patch:
arc> (let x 'atom (x 5)) ; defaults to #t clause
(atom 5)
