From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Lynn Winebarger Newsgroups: gmane.emacs.help Subject: Re: inline function expansion Date: Sun, 28 May 2023 18:42:26 -0400 Message-ID: References: <87bkivhqip.fsf@posteo.net> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="3108"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Philip Kaludercic , help-gnu-emacs@gnu.org To: Stefan Monnier Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Mon May 29 00:43:17 2023 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1q3P6b-0000ef-Jf for geh-help-gnu-emacs@m.gmane-mx.org; Mon, 29 May 2023 00:43:17 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1q3P64-0005o9-8s; Sun, 28 May 2023 18:42:44 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1q3P63-0005o1-2h for help-gnu-emacs@gnu.org; Sun, 28 May 2023 18:42:43 -0400 Original-Received: from mail-pj1-x1030.google.com ([2607:f8b0:4864:20::1030]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1q3P60-0006pQ-PC for help-gnu-emacs@gnu.org; Sun, 28 May 2023 18:42:42 -0400 Original-Received: by mail-pj1-x1030.google.com with SMTP id 98e67ed59e1d1-2566ed9328eso608539a91.2 for ; Sun, 28 May 2023 15:42:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1685313759; x=1687905759; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=FRip2cgPhKy5shVz/1JE3oHP1voKKH/kfrc4h7yMM9g=; b=MJuWvB+L7D+YYpeTbzZ6fv0oV4bHYDW1LMvtmfWiEwngRr4LHsInCUtGwG4wqUUgeM qTlnDjA7Zm8PpbpSJyeMYaUgWCpjkAoVysho29qGnNIyML3Mp/MgPTfhfR8te0YwAiC0 JMpxk5ix8+Q55ay5ODGuIn5HaAPCkEDqZDVomuTqWZfsk4Xh+K4dZdebkMbDsYLsvU+P JleRYtEmM+Lf3hA/e6Pk81V98epjN4kpCsnrVRaWYabmQdaofTSXIqWpYinAOlyXb5c4 SKNAjlNoAybMk1JKqchZK4paWZIVo7/jEfPqs2hz7FSC7jHsCzlLRGYGsIYK0NBo/tEQ 6+nA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685313759; x=1687905759; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=FRip2cgPhKy5shVz/1JE3oHP1voKKH/kfrc4h7yMM9g=; b=cnEeiaqZY7THwBuyx8uB+PsldCHgR7DYumAbB7UJ38KYq4SUw6R5go2XiRbafoEOvr lvZFvCb46T7stGMdVtf9zOXG1skh92xeqLBZzeZr3josJfT1F+/mV/hy92T6lJAGKRMY 7ohqfMlNWFWiZO2KEnYVjwqAcgZJqA2iAYd8hf7BoNfT7tieMPYeaxVe/u/a2JwReVoC SqGfMctbJEkbd41rrRlmXEMHW7+Qyd/1QujUxgdc+scSJhKou31i++VQpXNlwvbsqauV OqBWzLS58muAL5dtPjP43AL/cXwXfqfzwGwtpOB7n+M0EY8pkrUTg6WXnsjzrUBMErPY n0nQ== X-Gm-Message-State: AC+VfDwpmq6FSPHeffxOYemPDDF6qs/6Rawl5Ong9Kn+M6TksR/8F2AH PWvfdiy+E3Jmeb51jJGrTwi8d6UL0y1+gSUoRBY= X-Google-Smtp-Source: ACHHUZ706LN16A1Ky1Jvddf9Ue7t8hYQzTPVlnwlVEMB16X+LSt32PRddTvNujXbRrRmKE9muJYk0gELUUBRPw+XpQs= X-Received: by 2002:a17:902:cec4:b0:1af:b9ed:1677 with SMTP id d4-20020a170902cec400b001afb9ed1677mr11432348plg.2.1685313758628; Sun, 28 May 2023 15:42:38 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::1030; envelope-from=owinebar@gmail.com; helo=mail-pj1-x1030.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.help:143779 Archived-At: On Sun, May 28, 2023 at 10:57=E2=80=AFAM Stefan Monnier wrote: > > For my purposes, interfaces and realizations of interfaces are just a > > way to specify bindings of symbols in a more structured and > > encapsulated way than raw macros. > > I'm still spit-balling here, but I'm thinking a generic > > compile-time-dispatched (inlineable) "max" might be defined along > > these lines: > > > > ;; ordering interface has two parameters > > (define-interface ordering (bool-T elt-T) > > ;; return value of `lt' method satisfies bool-T interface > > (method (bool-T lt) (elt-T a) (elt-T b))) > > > > (define-realized-interface integer-ordering (ordering boolean integer) > > ;; bind lt method to built-in `<' > > (method lt <)) > > > > (defgeneric max (< a b) > > "Determine the larger of a and b according to <") > > > > (define-inline-method max ((ordering <) &opaque a b) > > "Determine the larger of a and b according to ordering <" > > ;; < is treated syntactically as a dispatcher > > (if (< lt a b) a b)) > > > > ;; because elisp does not allow applications in the operator position > > (define-inlined-method integer-max (max integer-ordering)) > > ;; Alternatively, > > ;; (integer-ordering lt) reduces at compile time to something like > > ;; #s(interface-method > > ;; #s(interface-realization > > ;; #s(interface ordering boolean integer) > > ;; <) > > ;; lt > > ;; <) > > ;; which `max' is specialized for by define-inline-method above, so > > (defun integer-max (a b) > > ;; inlined by compile-time dispatch of the max generic method > > (max (integer-ordering lt) a b)) > > > > ;; These should produce t > > (=3D (max integer-ordering 5 6) (integer-max 5 6)) > > (=3D (max (integer-ordering lt) 5 6) (integer-max 5 6)) > > (macroexp-const-p (macroexpand-all '(max (integer-ordering lt) 5 6))) > > OK, that helps me understand a bit what you're talking about, thanks. > > This example seems rather uninteresting (lots of extra code for very litt= le > gain), so I strongly suspect this is not your prime-motivator. Both parts of that are true - I was trying to come up with the smallest example that would illustrate the essence of the interface specification and dispatch mechanism. > What's the over-arching goal? The overhead makes more sense if you want to replace NxM functions by N interface realizations and M generic functions mediated through the same interface(s). My specific itch came about when I started rewriting my "unboxed" package file management code to run in asynchronous batches, where there are multiple types of files being managed, namely "source" files (files in the package archive), installed files, and generated files (e.g. elc and eln files), and I need to keep indexed collections of each type in at least two contexts - one for the asynchronous batch job, and one in the larger transaction split into batch jobs. In this case, there is one (or more) generic function, (each) with two compile-time interface parameters, one with 3 realizations and one with 2 (or more) realizations. There are obviously other applications. For example, a while ago I provided an implementation of Nuutilla's transitive closure algorithm with a set of very particular implementation choices. With the sort of mechanism described above, I could parameterize the code in terms of the node, stack, and set implementation for various use cases/performance characteristics. > > I think `define-inline` is definitely not a good starting point for > the above. If you mean literally the current implementation of define-inline, I'd agree, except for the trick of defining both a compile-time (macro) and a residual function. I definitely see what I've described above as a generalization of "define-inline" to generic functions (sans the need for the inline-* syntax variants), particularly in the sense of being able to see the inlining at source level using macroexpand-all. AFAICT, there is no (meaningful) way to inline generic functions currently, Even if there were, what you would see after macroexpand-all would be the code for performing the dynamic dispatch, which is not particularly desirable. What I'd like to see after inlining a generic function is a call to the specific method implementing the generic function in that case. In that case the inlined code is about the same size as the original code, but skips both a function call and the dynamic calculation of the dispatch. Plus, as a user, it's meaningful that the inlining transforms a call to a user-defined function by a call to a (more specific) user-defined function, rather than a bunch of dispatch code that is really full of hairy implementation details (of generic functions). To make the above concrete, I mentioned in my prior follow-up email that a "define-inline-generic" form for the generic max would produce a closure of the form (lambda (<-realized a-realized b-realized) ((lambda (a b) ...) (realized-interface-value a) (realized-interface-value b))) But that inner lambda would actually be bound to a symbol (inspired by the symbols used for generalized variables) generated by #0=3D(intern (format "%S" `(max ,<-realized ,a-realized ,b-realized))) So that the inlined form of (max (integer-ordering lt) a b) would be (#0 a b), where the "realized-interface-value" of the opaque parameters is simply the expression in the corresponding operand position. Another aspect that may not be clear is that the appearance of the parameters in operator position correspond to where "define-inline" would use "unquote", and everything else is implicitly "inline-quote"-ed. Finally, the system I described provides a kind of modular macro system that could address some of the issues with macros noted in the thread "bug#62762: circular dependencies in elisp files and make" on the bug-gnu-emacs mailing list. That is, if inlined-generic functions were used in place of macros (where it makes sense), then you would wind up with calls to those specialized functions that have the realized-interface object encoded in the symbol, which is a kind of dynamic linkage (assuming those function calls were not further inlined). I'm not saying every instance of macros could be replaced by one of these compile-time generics, but I'm sure there are some places where they could be employed. > OTOH you might be able to layer your `define-inlined-method` > on top of the current `cl-generic.el`. AFAICT the main thing you need is > some way to write a "call with enough =C2=ABtype=C2=BB annotations" such = that the > dispatch can be performed at compile time. I think that's the main point of designating parameters as "opaque", so they aren't really specialized against, and only the non-opaque parameters need to be wrapped in a form like (integer-ordering lt). I'm still not certain that's enough to avoid needing a full-fledged partial-evaluator embedded in the macroexpansion phase. > >> >> I'm still not sure why you're not using a `compiler-macro` which se= ems > >> >> to be exactly what you're after. > >> > > >> > I'm very finicky I suppose. I want to get constant expression > >> > evaluation as automatically as possible, to enable the compile-time > >> > dispatch cleanly. Or are you saying that generic methods can be > >> > directly made into compiler macros? > >> > >> And here I'm lost as well. AFAICT there's just as little "directly ma= de > >> into" for define-inline as for compiler-macros (`define-inline` is jus= t > >> a way to define a function and its `compiler-macro` in one go). > > > > Hopefully the example above clarified what I'm talking about > > Somewhat. Still doesn't explain why you're focusing on `define-inline` > rather than `compiler-macro`. A compiler macro is just like a macro > except: I suppose I see the above as a kind of generalization of the kind of thing your paper described "define-inline" doing for "cl-typep" to generic functions. I mean, I want the max inliner to be "max" itself, specialized on some either s-expressions directly or some specially-wrapped form of s-expressions. I mean, that would be the most elegant solution to my mind. > - It shares its name with a function. > - The returned expansion should behave identically to the > way the function call would behave. > - It's unspecified when or even *if* it's expanded (if it's not > expanded, the function is called at runtime instead). > - It receives an additional argument (the whole sexp), which it can use > to say "I don't want to expand anything this time, just call the > function at runtime instead". > > IOW it's a mechanism to implement compile-time (well, > macroexpansion-time in our case) optimizations. > > > Although I would change "inline-const-p" to test for function purity > > (exclude stateful closures or otherwise impure functions). > > I think that would be a mistake. "const-p" doesn't mean that the return > value is pure but that the expression itself always returns the same valu= e. I think you mean the argument value, not the return value? But that's exactly what I mean - a pure function is immutable, and other functions change with state, so that in the extensional sense they are not equal even if they are eq. For the purpose of partial evaluation, which I believe is the point of inline-const-p, an expression `expr' is constant if (equal (eval expr state0) (eval expr state1)) is true for all possible values of state0 and state1 (and eq is inherently dependent on those state values, so is not a useful test for this definition). Clearly exprs that are syntactic literals are constants by this definition. Also, if `f' is a pure function, then (f C1 C2 .. Cn) for constant expressions C1,..Cn is also a constant expression. But that is not the case for impure functions. An example is `format', which depends on the setting of variables used by the print functions. (format "%S" '()) may produce distinct strings depending on the state, despite both arguments being literals. Considering the semantic value of a function to be given a mapping from "State -> Value -> Value", then `+' is constant function of state while `format' is not. Or, `+' is a constant, and `format' is not. On the other hand, if that call to format is the body of a let expression binding those (dynamic) variables to constants, then the whole let expression will be a constant expression. Likewise, lisp constructors that have a readable print-syntax are not inherently constant even if all arguments are constant expressions, but if such a constant constructor expression appears as an argument to a pure function in which all arguments are likewise either constant or constant constructor expressions, then the expression as a whole (with the pure function in operator position) will be constant according to the definition above (i.e. (equal (eval expr state0) (eval expr state1)) is true for all state0 and state1). Lynn