Re: New list commands ... What do you think ? (LONG)

Joe English wrote:
[...]
A more useful primitive IMO would be something like
[call $cmd $arg1 ... $argN], which interprets $cmd as
a command prefix, appends $arg1 ... $argN, and invokes
the resulting command.

This would be pretty useful. Possibly being able to specify the level to call in would also be useful, as in most of these combinators you usually want the call to occur in either the caller's scope (i.e. same as [uplevel 1]) or in the global scope.

[...]
This style of programming is familiar to Haskell and ML users;
once you get the hang of it it makes code much easier to read
and write. Tcl can *almost* support this style very well; all
that's missing is a "call" primitive or something similar.

Well, I'd prefer to have foldl implemented in C as it is likely to be a critical loop in many places. It's actually not too difficult to implement reasonably efficiently in C (where Tcl_EvalObjv stands-in for "call"):

/*
* fold.c --
*
* Fast C implementation of a foldl construct.
*
* Copyright (C) 2006 Neil Madden <nem@xxxxxxxxxxxxx>
*
* License: Tcl-style.
*
* RCS: @(#) $Id$
*/

#include <tcl.h>

static int
FoldCmd(
ClientData cdata, /* Unused. */
Tcl_Interp *interp,
int objc,
Tcl_Obj *CONST objv[])
{
int itemc, i, cmdLen, newObjc;
int result = TCL_OK;
Tcl_Obj **items;
Tcl_Obj *id;
Tcl_Obj **cmd, **newObjv;

if (objc != 4) {
Tcl_WrongNumArgs(interp, 1, objv, "proc id list");
return TCL_ERROR;
}

id = objv[2];
Tcl_IncrRefCount(id);

/* Extract command prefix. */
if (Tcl_ListObjGetElements(interp, objv[1], &cmdLen, &cmd)
!= TCL_OK)
{
return TCL_ERROR;
}
/* Allocate new array to hold command prefix + id + element */
newObjc = cmdLen + 2;
newObjv = (Tcl_Obj **)
ckalloc((unsigned) (newObjc * sizeof(Tcl_Obj *)));

/* Copy command prefix into new array. */
for (i = 0; i < cmdLen; ++i) {
newObjv[i] = cmd[i];
Tcl_IncrRefCount(newObjv[i]);
}

/* Extract items from list. */
if (Tcl_ListObjGetElements(interp, objv[3], &itemc, &items)
!= TCL_OK)
{
return TCL_ERROR;
}

/*
* Loop through the list, applying the procedure to the current
* item and the accumulator (which is initialised to the "id"
* argument).
*/
for (i = 0; i < itemc; ++i) {
newObjv[cmdLen] = id;
newObjv[cmdLen+1] = items[i];
result = Tcl_EvalObjv(interp, newObjc, newObjv,
TCL_EVAL_GLOBAL);
switch (result) {
case TCL_OK:
case TCL_CONTINUE:
/* Continue to next element. */
Tcl_DecrRefCount(id);
id = Tcl_GetObjResult(interp);
Tcl_IncrRefCount(id);
break;
case TCL_BREAK:
/* Abort loop with current value. */
goto done;
default:
/* Error. */
goto done;
}
}
done:

for (i = 0; i < cmdLen; ++i) {
Tcl_DecrRefCount(newObjv[i]);
}
ckfree((char *) newObjv);

Tcl_DecrRefCount(id);

return result;
}

int
Fold_Init(Tcl_Interp *interp)
{
if (Tcl_InitStubs(interp, "8.4", 0) == NULL) {
return TCL_ERROR;
}

Tcl_CreateObjCommand(interp, "foldl", FoldCmd, NULL, NULL);

Tcl_PkgProvide(interp, "foldl", "0.1");

return TCL_OK;
}

With this compiled and loaded, the other sum, product etc can be defined:

proc def {name = args} {
interp alias {} $name {} {expand}$args
}
foreach op {+ - * /} { proc $op {a b} " expr {\$a $op \$b} " }
def sum = foldl + 0
def prod = foldl * 1
# For comparison:
proc prod2 list {
set id 1
foreach item $list { set id [* $id $item] }
return $id
}
set test [list]
for {set i 0} {$i <= 100} {incr i} { lappend test $i }
time { prod $test } 100 ;# -> 1670.53 us per iteration
time { prod2 $test } 100 ;# -> 1868.18 us per iteration

So, foldl is competitive with a hand-coded foreach solution (slightly faster even).

Map and filter are easy to define:

proc map {proc list} { foldl [list map-helper $proc] [list] $list }
proc map-helper {proc accum item} {
lappend accum [{expand}$proc $item]
}
proc filter {proc list} {
foldl [list filter-helper $proc] [list] $list
}
proc filter-helper {proc accum item} {
if {[{expand}$proc item]} {
lappend accum $item
}
return $accum
}

These are quite a bit slower than the hand-coded foreach equivalents though. An extra proc invocation seems to really slow things down.

-- Neil
.

Relevant Pages

  • Re: Assigns in Initializer
    ... PROC Catch_startup_assign(rucb, passthru, message, msglen, match) ... INT .passthru; ... I am using the INITIALIZER guardian call with assignproc, ...
    (comp.sys.tandem)
  • Re: Getting Return Value From Stored Proccedure (Part 2)
    ... for a proc parameter to return a value to the caller, the proc must declare it as a output parameter as sql defaults to pass by value. ... create procdure test1 @i1 int, ... Dim conn As New SqlConnection ... Dim param As New SqlParameter ...
    (microsoft.public.dotnet.framework.aspnet)
  • Re: the necessity of drop temp table code
    ... Create Procedure FooProc As ... Create Table #T1 (X int); ... The second exec of that proc did not do any recompiles at all. ...
    (microsoft.public.sqlserver.programming)
  • Re: NEED Query to Find out all Databases sizes
    ... I thought CalcSpace was a cool proc, so just for kicks, I thought I would ... -- select * from #tblSize order by rows desc ... int)),sum-1) as int) + ... > I want to find out the SQL databases total size in SQL 2000 server, ...
    (microsoft.public.sqlserver.server)