LISP -通过参数搜索特定函数的程序
为了一个课程项目，我用lisp写了一个程序。
程序应该包含最重要的lisp函数，它们的输入和输出参数，以及可能的可选参数。
例如: function - first，input - list，output - object (list的第一个成员)。
程序应该以两种不同的方式工作：
输入函数参数您为程序指定了一个函数的名称，它应返回parameters.
- You
- 参数，如果存在具有这些参数的函数，则应返回该函数的名称。
我的问题：
- 在lisp中处理此类任务的正确方法是什么？我想也许一棵树可以解决这个问题？(制作一个包含所有函数和参数的树，然后编写一个程序来处理它)。
- 有比这更好的方法来完成这项任务吗？或者一些建议，从哪里开始/如何开始？或包含任何信息的教程？
目前，我有点不知道该如何开始。如果您能提供任何帮助，我们将不胜感激。
英语不是我的第一语言，所以我希望一切都是可以理解的。
欢迎光临。
回答 3
Stack Overflow用户
发布于 2019-03-14 19:03:55
首先，看一下如何准备常见的lisp开发环境。在那之后，我认为你应该，调查：
使用
和defun创建
- 函数
诸如此类的事情。下面我们来看看两个常见的lisp函数：
下面是一个小示例：
CL-USER> (defun my-sum (a b) "Add my-sum parameters A and B." (+ a b))
MY-SUM
CL-USER> (my-sum 2 3)
5 (3 bits, #x5, #o5, #b101)
CL-USER> (describe #'my-sum)
#<FUNCTION MY-SUM>
[compiled function]
Lambda-list: (A B)
Derived type: (FUNCTION (T T) (VALUES NUMBER &OPTIONAL))
Documentation:
Add my-sum parameters A and B.
Source form:
(SB-INT:NAMED-LAMBDA MY-SUM
(A B)
"Add my-sum parameters A and B."
(BLOCK MY-SUM (+ A B)))
; No values
CL-USER> (documentation 'my-sum 'function)
"Add my-sum parameters A and B."
CL-USER> (defun my-sum (a b) "Add my-sum parameters A and B." (declare (type fixnum a b)) (+ a b))
WARNING: redefining COMMON-LISP-USER::MY-SUM in DEFUN
MY-SUM
CL-USER> (describe #'my-sum)
#<FUNCTION MY-SUM>
[compiled function]
Lambda-list: (A B)
Derived type: (FUNCTION (FIXNUM FIXNUM)
(VALUES
(INTEGER -9223372036854775808 9223372036854775806)
&OPTIONAL))
Documentation:
Add my-sum parameters A and B.
Source form:
(SB-INT:NAMED-LAMBDA MY-SUM
(A B)
"Add my-sum parameters A and B."
(DECLARE (TYPE FIXNUM A B))
(BLOCK MY-SUM (+ A B)))
; No values最后，使用describe输出中的字符串的最后一个技巧：
CL-USER> (with-output-to-string (*standard-output*)
(describe #'my-sum))
"#<FUNCTION MY-SUM>
[compiled function]
Lambda-list: (A B)
Derived type: (FUNCTION (FIXNUM FIXNUM)
(VALUES
(INTEGER -9223372036854775808 9223372036854775806)
&OPTIONAL))
Documentation:
Add my-sum parameters A and B.
Source form:
(SB-INT:NAMED-LAMBDA MY-SUM
(A B)
\"Add my-sum parameters A and B.\"
(DECLARE (TYPE FIXNUM A B))
(BLOCK MY-SUM (+ A B)))
"Stack Overflow用户
发布于 2019-03-15 08:00:38
从表面上看，这项任务似乎是在内存中构建一个简单的符号数据库，可以通过两种方式进行搜索。数据库中的条目被理解为函数。“输出参数”可能可以理解为一个或多个返回值。这些东西在ANSI Lisp中没有命名。这项任务的一个有用的解释是，无论如何都要给返回值加上符号标签。此外，我们也许可以使用类型符号作为返回值和参数。例如，cons函数的数据库条目可能如下所示：
(cons (t t) cons) ;; function named cons takes two objects, returns a cons类型t是ANSI Lisp中所有类型的超类型；它的意思是“任何值”。
这类记录的列表可以放入某个全局变量中。然后我们编写一个可能被命名为get-params-by-name的函数，以便：
(get-params-by-name 'cons) -> (t t)另一个是：get-names-by-params
(get-names-by-params '(t t)) -> (cons)此函数以列表的形式返回所有匹配函数的。可以有多个函数具有此签名。
然后，诀窍是找到可选参数和rest参数的良好表示。它可能与该语言使用的符号相同：
(list (&rest t) list) ;; list takes rest arguments of any type, returns list因为我们只对精确匹配感兴趣，所以我们不必实际解析&rest表示法。当用户按参数查询时，他们的查询对象将是字面上的(&rest t)，使用相同的语法。
equal函数可用于判断两个符号列表是否相同：
(equal '(&rest t) '(&rest t)) -> t
(equal '(t t) '(t t)) -> nil因此，这个练习并不困难:只需映射列表，查找匹配项。
(defun get-name-by-params (database params)
(let ((matching-entries (remove-if-not (lambda (entry)
(equal (second entry) params))
database)))
(mapcar #'first matching-entries))) ;; just the names, please这里，该函数将数据库列表作为参数，而不是引用全局变量。我们将其集成到的整个程序可以提供替代接口，但这是我们的低级查找函数。
测试：
[1]> (get-name-by-params '((cons (t t) cons) (list (&rest t) list)) '(integer string))
NIL
[3]> (get-name-by-params '((cons (t t) cons) (list (&rest t) list)) '(t t))
(CONS)
[4]> (get-name-by-params '((cons (t t) cons) (list (&rest t) list)) '(&rest t))
(LIST)在作业到期之前，我会从讲师那里得到澄清，这是否是对模糊要求的正确解释。
Stack Overflow用户
发布于 2019-03-17 23:52:25
鉴于这是一个课程项目，我将提供一个不完整的答案，让你们填写空白处。
程序应该做什么
我对你被要求做的事情的解释是提供一个实用程序，它将
给定函数名称的
- 返回其参数列表(以下称为'lambda list‘)；给定lambda列表的
- 返回具有该lambda列表的所有函数。
所以，首先你需要决定两个lambda列表是否相同。举个例子，作为一个lambda列表，(x)和(y)一样吗？是的，它是:形式参数的名称只在函数的实现中重要，你通常不会知道它们:这两个lambda列表都意味着“一个参数的函数”。
interestring是各种类型的可选参数：(a &optional b)显然与(a)不同，但与(b &optional c)相同，但它与(a &optional (b 1 bp))相同吗？在这段代码中，我说是的，这是相同的:可选参数的默认值和当前参数不会改变lambda列表是否相同。这是因为这些通常是函数的实现细节。
一个包裹
我们将其放入一个包中，这样就可以清楚地知道接口是什么：
(defpackage :com.stackoverflow.lisp.fdesc-search
(:use :cl)
(:export
#:defun/recorded
#:record-function-description
#:clear-recorded-functions
#:name->lambda-list
#:lambda-list->names))
(in-package :com.stackoverflow.lisp.fdesc-search)记录信息
因此，首先我们需要一种记录函数信息的机制。我们将使用一个类似于defun但记录信息的宏来实现这一点，我称之为defun/recorded。我们希望甚至在程序存在之前就能够记录有关事物的信息&我们通过让defun/recorded将“挂起”的记录保存在一个列表中来实现这一点，一旦程序存在，它就会正确地提取和记录。这让我们可以在整个代码中使用defun/recorded。
;;; These define whether there is a recorder, and if not where pending
;;; records should be stashed
;;;
(defvar *function-description-recorder* nil)
(defvar *pending-function-records* '())
(defmacro defun/recorded (name lambda-list &body forms)
"Like DEFUN but record function information."
;; This deals with bootstrapping by, if there is not yet a recording
;; function, stashing pending records in *PENDING-FUNCTION-RECORDS*,
;; which gets replayed into the recorder at the point it becomes
;; available.
`(progn
;; do the DEFUN first, which ensures that the LAMBDA-LIST is OK
(defun ,name ,lambda-list ,@forms)
(if *function-description-recorder*
(progn
(dolist (p (reverse *pending-function-records*))
(funcall *function-description-recorder*
(car p) (cdr p)))
(setf *pending-function-records* '())
(funcall *function-description-recorder*
',name ',lambda-list))
(push (cons ',name ',lambda-list)
*pending-function-records*))
',name))匹配lambda列表，第一步
现在我们希望能够匹配lambda列表。因为我们显然要在某种树中存储由lambda列表索引的内容，所以我们只需要能够处理它们的匹配元素。而且(见上)我们不关心缺省值之类的东西。我选择这样做:首先简化lambda列表以删除它们，然后匹配简化元素:还有其他方法。
simplify-lambda-list进行了简化，argument-matches-p会告诉您两个参数是否匹配:有趣的是，它需要知道lambda list关键字，这些关键字必须完全匹配，而其他所有关键字都匹配。CL标准方便地提供了lambda-list-keywords常量。
(defun/recorded simplify-lambda-list (ll)
;; Simplify a lambda list by replacing optional arguments with inits
;; by their names. This does not validate the list
(loop for a in ll
collect (etypecase a
(symbol a)
(list (first a)))))
(defun/recorded argument-matches-p (argument prototype)
;; Does an argument match a prototype.
(unless (symbolp argument)
(error "argument ~S isn't a symbol" argument))
(unless (symbolp prototype)
(error "prototype ~S isn't a symbol" prototype))
(if (find-if (lambda (k)
(or (eq argument k) (eq prototype k)))
lambda-list-keywords)
(eq argument prototype)
t))函数描述(部分)
关于函数的信息存储在名为fdescs的对象中:这里不给出这些对象的定义，但我们需要回答的一个问题是“两个fdesc是否引用同一函数的版本？”好吧，如果这些函数的名称是相同的，它们就会这样做。请记住，函数名不必是符号(允许使用(defun (setf x) (...) ...))，因此我们必须与equal而不是eql进行比较
(defun/recorded fdescs-equivalent-p (fd1 fd2)
;; do FD1 & FD2 refer to the same function?
(equal (fdesc-name fd1)
(fdesc-name fd2)))存储由lambda列表索引的fdesc%s(部分)
为了有效地通过lambda列表对事物进行索引，我们构建了一棵树。此树中的节点称为lambda-list-tree-nodes，此处未给出其定义。
有一些函数将fdesc存储在树中，并返回由给定的fdesc列表索引的lambda列表。这两个都没有实现，但它们看起来是这样的：
(defun/recorded intern-lambda-list (lambda-list tree-node fdesc)
;; return the node where it was interned
...)
(defun/recorded lambda-list-fdescs (lambda-list tree-node)
;; Return a list of fdescs for a lambda list & T if there were any
;; or NIL & NIL if there were not (I don't think () & T is possible,
;; but it might be in some future version)
...)这些函数的实现可能需要使用use argument-matches-p和fdescs-equivalent-p。
顶级数据库(稍有偏颇)
现在，我们可以定义顶级数据库对象:用于按lambda列表进行索引的树根，以及用于按名称进行索引的哈希表
(defvar *lambda-list-tree* (make-lambda-list-tree-node))
(defvar *tree-nodes-by-name* (make-hash-table :test #'equal))请注意，*tree-nodes-by-name*从名称映射到存储有关该函数的信息的节点:这样做是为了简化重新定义，如以下函数所示：
(defun/recorded record-function-description (name lambda-list)
"Record information about a function called NAME with lambda list LAMBDA-LIST.
Replace any existing information abot NAME. Return NAME."
(let ((fdesc (make-fdesc :name name :lambda-list lambda-list)))
;; First of all remove any existing information
(multiple-value-bind (node foundp) (gethash name *tree-nodes-by-name*)
(when foundp
(setf (lambda-list-tree-node-values node)
(delete fdesc (lambda-list-tree-node-values node)
:test #'fdescs-equivalent-p))))
(setf (gethash name *tree-nodes-by-name*)
(intern-lambda-list lambda-list *lambda-list-tree* fdesc)))
name)请注意，此函数首先查找name的任何现有信息，如果存在，则将其从找到它的节点中删除。这确保了函数重定义不会在树中留下过时的信息。
此函数是defun/recorded想要了解的实际记录器，因此请告诉它：
(setf *function-description-recorder*
#'record-function-description)现在，下次我们调用defun/recorded时，它将通过插入所有挂起的定义来引导系统。
record-function-description是API to the package的一部分:它可以用来记录关于我们没有定义的函数的信息。
用户界面函数
除了defun/recorded和record-function-description之外，我们还想要一些可以让我们查询数据库的函数，以及一个重置内容的函数：
(defun/recorded clear-recorded-functions ()
"Clear function description records. Return no values"
(setf *lambda-list-tree* (make-lambda-list-tree-node)
*tree-nodes-by-name* (make-hash-table :test #'equal))
(values))
(defun/recorded name->lambda-list (name)
"Look up a function by name.
Return either its lambda list & T if it is found, or NIL & NIL if not."
(multiple-value-bind (node foundp) (gethash name *tree-nodes-by-name*)
(if foundp
(values
(fdesc-lambda-list
(find-if (lambda (fd)
(equal (fdesc-name fd) name))
(lambda-list-tree-node-values node)))
t)
(values nil nil))))
(defun/recorded lambda-list->names (lambda-list)
"find function names matching a lambda-list.
Return a list of name & T if there are any, or NIL & NIL if none.
Note that lambda lists are matched so that argument names do not match, and arguments with default values or presentp parameters match just on the argument."
(multiple-value-bind (fdescs foundp) (lambda-list-fdescs lambda-list
*lambda-list-tree*)
(if foundp
(values (mapcar #'fdesc-name fdescs) t)
(values nil nil))))就是这样。
示例
在编译、加载和使用包(添加了缺少的部分)之后，我们可以首先向其中注入一些有用的额外函数(这只是一个随机散射)
> (dolist (x '(car cdr null))
(record-function-description x '(thing)))
nil
> (dolist (x '(car cdr))
(record-function-description `(setf ,x) '(new thing)))
nil
> (record-function-description 'cons '(car cdr))
cons
> (record-function-description 'list '(&rest args))现在我们可以进行一些查询：
> (lambda-list->names '(x))
(null cdr
car
lambda-list->names
name->lambda-list
com.stackoverflow.lisp.fdesc-search::simplify-lambda-list)
t
> (lambda-list->names '(&rest anything))
(list)
t
> (name->lambda-list 'cons)
(car cdr)
t在树中存储事物的一个示例
下面是一些代码，它演示了一种在树中存储信息的方法(通常称为tries)。由于许多原因，这在上面是不可用的，但阅读它可能有助于实现缺少的部分。
;;;; Storing things in trees of nodes
;;;
;;; Node protocol
;;;
;;; Nodes have values which may or may not be bound, and which may be
;;; assigned. Things may be interned in (trees of) nodes with a
;;; value, and the value associated with a thing may be retrieved
;;; along with an indicator as to whether it is present in the tree
;;; under the root.
;;;
(defgeneric node-value (node)
;; the immediate value of a node
)
(defgeneric (setf node-value) (new node)
;; Set the immediate value of a node
)
(defgeneric node-value-boundp (node)
;; Is a node's value bound?
)
(defgeneric intern-thing (root thing value)
;; intern a thing in a root, returning the value
(:method :around (root thing value)
;; Lazy: this arround method just makes sure that primary methods
;; don't need to beother returning the value
(call-next-method)
value))
(defgeneric thing-value (root thing)
;; return two values: the value of THING in ROOT and T if is it present, or
;; NIL & NIL if not
)
;;; Implementatation for STRING-TRIE-NODEs, which store strings
;;;
;;; The performance of these will be bad if large numbers of strings
;;; with characters from a large alphabet are stored: how might you
;;; fix this without making the nodes enormous?
;;;
(defclass string-trie-node ()
;; a node in a string trie. This is conceptually some kind of
;; special case of an abstract 'node' class, but that doesn't
;; actually exist.
((children-map :accessor string-trie-node-children-map
:initform '())
(value :accessor node-value)))
(defmethod node-value-boundp ((node string-trie-node))
(slot-boundp node 'value))
(defmethod intern-thing ((root string-trie-node) (thing string) value)
;; intern a string into a STRING-TRIE-NODE, storing VALUE
(let ((pmax (length thing)))
(labels ((intern-loop (node p)
(if (= p pmax)
(setf (node-value node) value)
(let ((next-maybe (assoc (char thing p)
(string-trie-node-children-map node)
:test #'char=)))
(if next-maybe
(intern-loop (cdr next-maybe) (1+ p))
(let ((next (cons (char thing p)
(make-instance (class-of node)))))
(push next (string-trie-node-children-map node))
(intern-loop (cdr next) (1+ p))))))))
(intern-loop root 0))))
(defmethod thing-value ((root string-trie-node) (thing string))
;; Return the value associated with a string in a node & T or NIL &
;; NIL if there is no value for this string
(let ((pmax (length thing)))
(labels ((value-loop (node p)
(if (= p pmax)
(if (node-value-boundp node)
(values (node-value node) t)
(values nil nil))
(let ((next (assoc (char thing p)
(string-trie-node-children-map node)
:test #'char=)))
(if next
(value-loop (cdr next) (1+ p))
(values nil nil))))))
(value-loop root 0))))
;;; Draw node trees in LW
;;;
#+LispWorks
(defgeneric graph-node-tree (node))
(:method ((node string-trie-node))
(capi:contain
(make-instance 'capi:graph-pane
:roots `((nil . ,node))
:children-function (lambda (e)
(string-trie-node-children-map (cdr e)))
:edge-pane-function (lambda (pane parent child)
(declare (ignore pane parent))
(make-instance
'capi:labelled-line-pinboard-object
:text (format nil "~A" (car child))))
:print-function (lambda (n)
(let ((node (cdr n)))
(format nil "~A"
(if (node-value-boundp node)
(node-value node)
""))))))))https://stackoverflow.com/questions/55158158
复制相似问题